Mechanism Design for Subadditive Agents via an Ex Ante Relaxation

ABSTRACT

We consider the problem of maximizing revenue for a monopolist offering multiple items to multiple heterogeneous buyers. We develop a simple mechanism that obtains a constant factor approximation under the assumption that the buyers' values are additive subject to a matroid feasibility constraint and independent across items. Importantly, different buyers in our setting can have different constraints on the sets of items they desire. Our mechanism is a sequential variant of two-part tariffs. Prior to our work, simple approximation mechanisms for such multi-buyer problems were known only for the special cases of all unit-demand or all additive value buyers.

Our work expands upon and unifies long lines of work on unit-demand settings and additive settings. We employ the ex ante relaxation approach developed by Alaei [2011] for reducing a multiple-buyer mechanism design problem with an ex post supply constraint into single-buyer problems with ex ante supply constraints. Solving the single-agent problems requires us to significantly extend a decomposition technique developed in the context of additive values Li and Yao [2013] and its extension to subadditive values by [2015].

References

1. Saeed Alaei. 2011. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. In IEEE Symp. on Foundations of Computer Science. 512--521.
2. Mark Armstrong. 1999. Price Discrimination by a Many-Product Firm. The Review of Economic Studies 66, 1 (1999), 151--168.
3. Moshe Babaioff, Nicole Immorlica, Brendan. Lucier, and S.Matthew Weinberg. 2014. A Simple and Approximately Optimal Mechanism for an Additive Buyer. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on. 21--30.
4. Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S. Matthew Weinberg. 2010. Pricing Randomized Allocations. In ACM Symp. on Discrete Algorithms. 585--597.
5. Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2012a. An algorithmic characterization of multi-dimensional mechanisms. In ACM Symp. on Theory of Computing. 459--478.
6. Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2012b. Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. In IEEE Symp. on Foundations of Computer Science. 130--139.
7. Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2013a. Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations. In ACM Symp. on Discrete Algorithms. 578--595.
8. Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2013b. Understanding Incentives: Mechanism Design Becomes Algorithm Design. In IEEE Symp. on Foundations of Computer Science. 618--627.
9. Yang Cai, Nikhil Devanur, and S. Matthew Weinberg. 2016. A Duality Based Unified Approach to Bayesian Mechanism Design. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC).\shownoteTo appear.
10. Shuchi Chawla, Jason Hartline, and Robert Kleinberg. 2007. Algorithmic Pricing via Virtual Valuations. In Proc. 9th ACM Conf. on Electronic Commerce. 243--251.
11. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010a. Multi-parameter mechanism design and sequential posted pricing. In ACM Symp. on Theory of Computing. 311--320.
12. Shuchi Chawla, David Malec, and Balasubramanian Sivan. 2010b. The power of randomness in Bayesian optimal mechanism design. In Proc. 12th ACM Conf. on Electronic Commerce.
13. hawla and Miller2016}% cm16-fullShuchi Chawla and J. Benjamin Miller. 2016.showarticletitleMechanism design for subadditive agents via an ex ante relaxation (full version). CoRR abs/1603.03806 (2016).\showURL%http://arxiv.org/abs/1603.03806
14. Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. 2012. Optimal Pricing Is Hard. In Workshop on Internet and Network Economics (WINE). 298--308.
15. Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. 2014. The Complexity of Optimal Mechanism Design. In ACM Symp. on Discrete Algorithms. 1302--1318.
16. Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. 2015. Strong Duality for a Multiple-Good Monopolist. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC'15. 449--450.
17. Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. 2011. Maximizing Non-monotone Submodular Functions. SIAM J. Comput. 40, 4 (July 2011), 1133--1153.
18. Moran Feldman, Ola Svensson, and Rico Zenklusen. 2016. Online Contention Resolution Schemes. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16). 1014--1033.
19. Yiannis Giannakopoulos and Elias Koutsoupias. 2014. Duality and Optimality of Auctions for Uniform Distributions. In Proceedings of the Fifteenth ACM Conference on Economics and Computation (EC '14). 259--276.
20. Yiannis Giannakopoulos and Elias Koutsoupias. 2015. Selling Two Goods Optimally. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015. 650--662.
21. Nima Haghpanah and Jason Hartline. 2015. Reverse Mechanism Design. In Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC '15). 757--758.
22. Sergiu Hart and Noam Nisan. 2012. Approximate revenue maximization with multiple items. In ACM Conf. on Electronic Commerce. 656.
23. Sergiu Hart and Noam Nisan. 2013. The menu-size complexity of auctions. In ACM Conf. on Electronic Commerce. 565--566.
24. Jason Hartline. 2016. Mechanism Design and Approximation. http://jasonhartline.com/MDnA/
25. Robert Kleinberg and S. Matthew Weinberg. 2012. Matroid prophet inequalities. In ACM Symp. on Theory of Computing. 123--136.
26. Xinye Li and Andrew Chi-Chih Yao. 2013. On revenue maximization for selling multiple independently distributed items. Proceedings of the National Academy of Sciences (2013).
27. Philip J. Reny and Sergiu Hart. 2015. Maximal revenue with multiple goods: nonmonotonicity and other observations. Theoretical Economics 10, 3 (2015).
28. Aviad Rubinstein and S. Matthew Weinberg. 2015. Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC'15. 377--394.
29. Gideon Schechtman. 1999. Concentration, Results and Applications. (1999).
30. Andrew Chi-Chih Yao. 2015. An N-to-1 Bidder Reduction for Multi-item Auctions and Its Applications. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15). 92--109.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Algorithmic mechanism design