资源论文Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization?

Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization?

2019-11-12 | |  59 |   38 |   0
Abstract The VCG mechanism is the gold standard for combinatorial auctions (CAs), and it maximizes social welfare. In contrast, the revenue-maximizing (aka optimal) CA is unknown, and designing one is NP-hard. Therefore, research on optimal CAs has progressed into special settings. Notably, Levin [1997] derived the optimal CA for complements when each agent’s private type is one-dimensional. (This does not fall inside the well-studied “singleparameter environment”.) We introduce a new research avenue for increasing revenue where we poke holes in the allocation space—based on the bids—and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the ?rst step down this avenue, we introduce a new form of “reserve pricing” into CAs. We show that Levin’s optimal revenue can be 2-approximated by using “monopoly reserve prices” to curtail the allocation set, followed by welfare-maximizing allocation and Levin’s payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocation-monotonic mechanism equals the expected virtual valuation; this generalizes Myerson’s lemma [1981] from the single-parameter environment. Our mechanism is close to the gold standard and thus easier to adopt than Levin’s. It also requires less information about the prior over the bidders’ types, and is always more ef?cient. Finally, we show that the optimal revenue can be 6approximated even if the “reserve pricing” is required to be symmetric across bidders.

上一篇:Emergence and Stability of Social Conventions in Con?ict Situations Toshiharu Sugawara

下一篇:Generalizing Envy-Freeness Toward Group of Agents

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...