0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm sorry, but what exactly is the question here? $\endgroup$
    – Walrasian Auctioneer
    Commented Apr 16, 2020 at 22:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – VARulle
    Commented Apr 16, 2020 at 22:27
  • $\begingroup$ 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 $\endgroup$
    – ShAr
    Commented Apr 17, 2020 at 4:25

1 Answer 1

Reset to default
1
$\begingroup$

To my understanding, this is a relevant question. I am not an expert on auction design, but I know that Paul Milgrom has several papers dealing with auctions where these problems arise (see for example this). He and coauthors have studied these problems both theoretically and in applications. I am not sure if they have considered any of the rules you mention, but diving into that literature will probably give you a good idea of the state of the literature from the economics side.

It is also my understanding that, at least in the radio spectrum auction that inspired much of the literature, the hard part was identifying the set of conflicting deals. Which your rules seem to take as a computable object.

Hope this helps.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The idea is that taking care of all conflicts/contradictions between the offered deals while trying to maximize ur profit, an exact optimal solution takes exponential time on the number of deals. These rules try to reduce the number of deals u have in hand. If a real auctioneer sometimes puts other factors into consideration like his going business with a certain investor,... etc; either these factors can be included in a virtual bid or as intermediate step(joint research with the rules).My Q is any of the given reductions new or important/of considerable value/was really needed from ur side? $\endgroup$
    – ShAr
    Commented Apr 22, 2020 at 8:43
  • $\begingroup$ I see the goal of your research agenda and the point of your question. I think that being able to select the exact optimal combination of feasible deals in exponential time is certainly interesting and relevant. Unfortunately, I don't know the literature enough to point if any of these rules have been considered or if they are valuable. $\endgroup$
    – Regio
    Commented Apr 22, 2020 at 16:24
  • $\begingroup$ However, I do see an important limitation of your approach. It takes as given the strategies of bidders. In general, the way that bids will be processed by the auctioneer to allocate the goods or deals affects the way that bidders submit their bids. So, as you will see in the literature from the econ side, we worry about the auction design being incentive-compatible, strategy-proof etc. There is evidence from real-world procurements, that this is a first-order concern as bidders are highly strategic. I'm not saying the research question is not interesting, simply giving some feedback. $\endgroup$
    – Regio
    Commented Apr 22, 2020 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.