# Reduction Rules for Auction conflicting Deals

This question addresses an interdisciplinary science between Computer Science and Economics (Modern Auction Design). I'm posting my question here to get ur expert opinion as economists on the significance of these rules, are any of them considered "new" or "important" to your field to build on? Or they're all already known/of no importance? .

Now there are some graph reduction rules that was developed in Oct 2018 by CS researchers, these rules are directly transformable to the following rules. .

## Terminology:

When bidder X offers a deal for items A, B and bidder Y offers a deal for items B, C we call X, Y conflicting deals because u can't select both deals in ur solution(or we say ur auction allows complementarities). So the problem in hand is that u have say thousands of deals with complementarities between them and u want to select the set of deals that maximizes ur profit. These rules offer some reductions to the set of deals to decrease the size of the problem (may be if we apply them we'll have to choose from hundred deals instead of thousand)

## ## The Rules ##

The straight forward thing is if the valuation of v is larger than the sum of valuation of all deals conflicting with it, then sure the deal v is accepted in the solution. The following if this is not the case. .

For 2 conflicting deals u & v, - if the valuation of u + the valuation of all deals conflicting with v (exexcluding those conflicting with u) is still less than or equal the valuation of v. -Then we can safely remove the deal u from our list of choices. (putting it differently, for a large valued deal v : check its conflicting deals try them separately against each other: is it better if u is taken& not v? ) .

If a deal v conflicts with a number of deals N(v) while those deals do not conflict with each other (indep), -and even more the sum of their valuation w(N(v)) is larger than of v, that is not enough yet to eliminate v!!! -If also removing their smallest deal make them have less value than v, -Then, now u can replace all (v & the one conflicting with it) with a virtual deal v' W(v') = W(N(v)) - W(v) and solve -In other words, if u have a choice to make bet a bundle of non-conflicting deals (N(v)) and one deal "v" that only conflicts with all of them (they can have separate other conflicts, but v NO only with them). Check if w(Deals) > w(v) > w(Deals- min of them) Then replace all with "v'" -I think this may also have a special value for the "after math" of a given solution. For example, if someone wants to investigate a specific choice in the selected output of an auction/game (What was the effect of choosing N(v) instead of v? What would have happened if we reversed? Or want to deter such decision to the final step… So don't approach any of them for now and work with the difference virtual deal v' Then the complains may be only on how did u calculate v', is there a better/another solution that would have flipped the decision for v'????) .

-If a set of deals r all conflicting with each other (the conflicting deals form alone a clique = fully connected) then u can remove the whole set of deals (clique) from ur input and consider only their max that is not conflicting with any node outside the clique (larger) weight(valuation) deal/bid (vertex) v in the solution. .

-If a deal v conflicts with only 2 deals x, y that r not conflicting with each other (x does not conflict with y): -AND If valuation of v is smaller than the sum of both deals(bids), but larger than their maximum (larger than each separately) -Then replace the 3 deals with a virtual deal v' that has a valuation of their difference (w(x) +w(y) - w(v)), AND add to ur resulting solution the original valuation of v. -If the resulting solution contains the virtual bid v' then pick the 2deals x, y; if not (v' is not in solution) pick v. .

If 2 deals conflicts with the same set of deals that do not conflict with each other (indep) : -If their valuation (whatever conflicting or not, ie. their sum or their max) is larger than the valuation of those deals (the whole set), then u can safely eliminate this whole set of deals from your input (keep the 2 deals) -However if their valuation (the 2 original deals) is smaller than the whole set but yet larger than the smallest of them, then replace ALL (including the original 2) with a virtual bid/deal v' and make its value equal the difference bet the two sets (as if we are solving this part of the auction separately) -After solving, if ur solution contain v' then u should select the indep subset of conflicting deals ({p, q, r} in our example). If not (v' was not selected) then u should pick the original two.

• I'm sorry, but what exactly is the question here? Apr 16, 2020 at 22:20
• The question (whatever it turns out to be) might be an interdisciplinary one, but it seems to be stated exclusively in the language of CS. I have never even heard of the term "conflicting deals" in connection with auction theory. Apr 16, 2020 at 22:27
• The Q is how significant r these rules to the Auction world(and their novelty too). Example of conflicting deals is when bidder X offers a deal for items say A, B and bidder Y's deal is for items B, C.... i.e., u can't select both deals in ur solution
– ShAr
Apr 17, 2020 at 4:25