Document Open Access Logo

When Are Welfare Guarantees Robust?

Authors Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.22.pdf
  • Filesize: 0.82 MB
  • 23 pages

Document Identifiers

Author Details

Tim Roughgarden
Inbal Talgam-Cohen
Jan Vondrák

Cite As Get BibTex

Tim Roughgarden, Inbal Talgam-Cohen, and Jan Vondrák. When Are Welfare Guarantees Robust?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.22

Abstract

Computational and economic results suggest that social welfare maximization and combinatorial auction design are much easier when bidders' valuations satisfy the "gross substitutes" condition. The goal of this paper is to evaluate rigorously the folklore belief that the main take-aways from these results remain valid in settings where the gross substitutes condition holds only approximately. We show that for valuations that pointwise approximate a gross substitutes valuation (in fact even a linear valuation), optimal social welfare cannot be approximated to within a subpolynomial factor and demand oracles cannot be simulated using a subexponential number of value queries. We then provide several positive results by imposing additional structure on the valuations (beyond gross substitutes), using a more stringent notion of approximation, and/or using more powerful oracle access to the valuations.  For example, we prove that the performance of the greedy algorithm degrades gracefully for near-linear valuations with approximately decreasing marginal values; that with demand queries, approximate welfare guarantees for XOS valuations degrade gracefully for valuations that are pointwise close to XOS; and that the performance of the Kelso-Crawford auction degrades gracefully for valuations that are close to various subclasses of gross substitutes valuations.

Subject Classification

Keywords
  • Valuation (set) functions
  • gross substitutes
  • linearity
  • approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Lawrence M. Ausubel, Peter Cramton, R. Preston McAfee, and John McMillan. Synergies in wireless telephony: Evidence from the broadband PCS auctions. Journal of Economics and Management Strategy, 6(3):497-527, 1997. Google Scholar
  2. Lawrence M. Ausubel and Paul R. Milgrom. The lovely but lonely Vickrey auction. In Peter Cramton, Yoav Shoham, and Richard Steinberg, editors, Combinatorial Auctions, chapter 1, pages 57-95. MIT Press, Boston, MA, USA, 2006. Google Scholar
  3. Eric Balkanski, Aviad Rubinstein, and Yaron Singer. The limitations of optimization from samples. Working paper, 2016. Google Scholar
  4. Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Proceedings of the 28th Annual Conference on Learning Theory, pages 240-265, 2015. Google Scholar
  5. Dimitris Bertsimas and Aurélie Thiele. Robust and Data-Driven Optimization: Modern Decision Making Under Uncertainty, chapter 5, pages 95-122. INFORMS PubsOnline, 2014. TutORials in Operations Research. Google Scholar
  6. Sushil Bikhchandani and John W. Mamer. Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory, 74(2):385-413, 1997. Google Scholar
  7. Liad Blumrosen and Noam Nisan. Combinatorial auctions. In Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors, Algorithmic Game Theory, chapter 11. Cambridge University Press, 2007. Google Scholar
  8. M. M. Bykowsky, R. J. Cull, and J. O. Ledyard. Mutually destructive bidding: The FCC auction design problem. Journal of Regulatory Economics, 17(3):205-228, 2000. Google Scholar
  9. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740-1766, 2011. Google Scholar
  10. Flavio Chierichetti, Abhimanyu Das, Anirban Dasgupta, and Ravi Kumar. Approximate modularity. In Proceedings of the 56th Symposium on Foundations of Computer Science, pages 1143-1162, 2015. Google Scholar
  11. Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Applied Mathematics, 7(3):251-274, 1984. Google Scholar
  12. Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 39(1):122-142, 2009. Google Scholar
  13. Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, and Vasilis Syrgkanis. A unifying hierarchy of valuations with complements and substitutes. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 872-878, 2014. Google Scholar
  14. Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen. Approximate modularity revisited. In Proc. of the 49th Annual ACM Symp. on Theory of Computing, 2017. To appear. Google Scholar
  15. Uriel Feige and Jan Vondrák. The submodular welfare problem with demand queries. Theory of Computing, 6(1):247-290, 2010. Google Scholar
  16. M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. An analysis of approximations for maximizing submodular set functions - II. Mathematical Programming Study, 8:73-87, 1978. Google Scholar
  17. Hu Fu, Robert Kleinberg, and Ron Lavi. Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding. In Proceedings of the 13th ACM Conference on Economics and Computation, page 586, 2012. Extended abstract. Google Scholar
  18. Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87:95-124, 1999. Google Scholar
  19. Avinatan Hassidim and Yaron Singer. Submodular optimization under noise. Manuscript, 2016. Google Scholar
  20. John William Hatfield, Nicole Immorlica, and Scott Duke Kominers. Testing substitutability. Games and Economic Behavior, 75(2):639-645, 2012. Google Scholar
  21. Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra. Do prices coordinate markets? To appear in STOC 2016, 2016. Google Scholar
  22. Daniel Kahneman, Jack L. Knetsch, and Richard H. Thaler. Experimental tests of the endowment effect and the Coase theorem. Journal of Political Economy, 98(6):1325-1348, 1990. Google Scholar
  23. Chinmay Karande and Nikhil R. Devanur. Computing market equilibrium: Beyond weak gross substitutes. In Proceedings of the 3rd International Workshop on Internet and Network Economics, pages 368-373, 2007. Google Scholar
  24. A. Kelso and V. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):1483-1504, 1982. Google Scholar
  25. Subhash Khot, Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica, 52(1):3-18, 2008. Google Scholar
  26. Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55:270-296, 2006. Google Scholar
  27. Takanori Maehara and Kazuo Murota. Valuated matroid-based algorithm for submodular welfare problem. Annals of Operations Research, 229:565-590, 2015. Google Scholar
  28. Paul R. Milgrom. Putting auction theory to work: The simultaneous ascending auction. Journal of Political Economy, 108(2):245-272, 2000. Google Scholar
  29. Paul R. Milgrom. The substitution metric and the performance of clock auctions, 2015. Talk at Simons Insitute, available at URL: https://simons.berkeley.edu/talks/paul-milgrom-10-13.
  30. Vahab S. Mirrokni, Michael Schapira, , and Jan Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In Proceedings of the 9th ACM Conference on Economics and Computation, pages 70-77, 2008. Google Scholar
  31. Kazuo Murota. Valuated matroid intersection I: Optimality criteria. SIAM J. Discrete Math., 9(4):545-561, 1996. Google Scholar
  32. Kazuo Murota. Valuated matroid intersection II: Algorithms. SIAM J. Discrete Math., 9(4):562-576, 1996. Google Scholar
  33. Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, 129:192-224, 2006. Google Scholar
  34. Michael Ostrovsky and Renato Paes Leme. Gross substitutes and endowed assignment valuations. Theoretical Economics, 2014. Google Scholar
  35. J. G. Oxley. Matroid Theory. Oxford, 1992. Google Scholar
  36. Renato Paes Leme. Gross substitutability: An algorithmic survey. Working paper, 2014. Google Scholar
  37. Renato Paes Leme and Sam Chiu-wai Wong. Computing Walrasian equilibria: Fast algorithms and economic insights. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 632-651, 2017. Google Scholar
  38. Christos H. Papadimitriou, Michael Schapira, and Yaron Singer. On the hardness of being truthful. In Proceedings of the 49th Symposium on Foundations of Computer Science, pages 250-259, 2008. Google Scholar
  39. Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 2000. Google Scholar
  40. Tim Roughgarden, Inbal Talgam-Cohen, and Jan Vondrák. When are welfare guarantees robust? In 2nd Algorithmic Game Theory and Data Science Workshop, July 2016. Full version available at URL: https://arxiv.org/abs/1608.02402.
  41. A. Schrijver. Combinatorial Optimziation: Polyhedra and Efficiency. Springer, 2003. Google Scholar
  42. Dravyansh Sharma, Amit Deshpande, and Ashish Kapoor. On greedy maximization of entropy. In Proceedings of the 32nd International Conference on Machine Learning, pages 1330-1338, 2015. Google Scholar
  43. Yaron Singer and Jan Vondrák. Information-theoretic lower bounds for convex optimization with erroneous oracles. In Proceedings of the 28th Neural Information Processing Systems Conference, 2015. Google Scholar
  44. Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1134-1148, 2015. Google Scholar
  45. Rakesh V. Vohra. Mechanism Design: A Linear Programming Approach. Econometric Society Monographs, 2011. Google Scholar
  46. Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 67-74, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact