Document Open Access Logo

Smoothed and Average-Case Approximation Ratios of Mechanisms: Beyond the Worst-Case Analysis

Authors Xiaotie Deng, Yansong Gao, Jie Zhang

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.16.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Xiaotie Deng
Yansong Gao
Jie Zhang

Cite As Get BibTex

Xiaotie Deng, Yansong Gao, and Jie Zhang. Smoothed and Average-Case Approximation Ratios of Mechanisms: Beyond the Worst-Case Analysis. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.16

Abstract

The approximation ratio has become one of the dominant measures in mechanism design problems. In light of analysis of algorithms, we define the smoothed approximation ratio to compare the performance of the optimal mechanism and a truthful mechanism when the inputs are subject to random perturbations of the worst-case inputs, and define the average-case approximation ratio to compare the performance of these two mechanisms when the inputs follow a distribution. For the one-sided matching problem, Filos-Ratsikas et al. [2014] show that, amongst all truthful mechanisms, random priority achieves the tight approximation ratio bound of Theta(sqrt{n}). We prove that, despite of this worst-case bound, random priority has a constant smoothed approximation ratio. This is, to our limited knowledge, the first work that asymptotically differentiates the smoothed approximation ratio from the worst-case approximation ratio for mechanism design problems. For the average-case, we show that our approximation ratio can be improved to 1+e. These results partially explain why random priority has been successfully used in practice, although in the worst case the optimal social welfare is Theta(sqrt{n}) times of what random priority achieves. 
These results also pave the way for further studies of smoothed and average-case analysis for approximate mechanism design problems, beyond the worst-case analysis.

Subject Classification

Keywords
  • mechanism design
  • approximation ratio
  • smoothed analysis
  • average-case analysis

Metrics

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

References

  1. Atila Abdulkadiroğlu and Tayfun Sönmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, pages 689-701, 1998. Google Scholar
  2. Atila Abdulkadiroğlu and Tayfun Sönmez. Matching Markets: Theory and Practice. Advances in Economics and Econometrics (Tenth World Congress), pages 3-47, 2013. Google Scholar
  3. Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, and Yang Yuan. Optimal auctions vs. anonymous pricing. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pages 1446-1463. IEEE Computer Society, 2015. Google Scholar
  4. Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, and Éva Tardos. An approximate truthful mechanism for combinatorial auctions with single parameter agents. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 205-214, 2003. Google Scholar
  5. David Arthur and Sergei Vassilvitskii. Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. SIAM J. Comput., 39(2):766-782, 2009. Google Scholar
  6. I. Ashlagi, F. Fischer, I. Kash, and Ariel D. Procaccia. Mix and match. In Proceedings of the 11th ACM conference on Electronic commerce (ACM-EC), pages 305-314, 2010. Google Scholar
  7. Cyril Banderier, René Beier, and Kurt Mehlhorn. Smoothed analysis of three combinatorial problems. In 28th International Symposium, Mathematical Foundations of Computer Science, MFCS, volume 2747 of Lecture Notes in Computer Science, pages 198-207. Springer, 2003. Google Scholar
  8. Salvador Barbera. Strategy-proof Social Choice. In K. J. Arrow, A. K. Sen, and K. Suzumura, editors, Handbook of Social Choice and Welfare, volume 2, chapter 25. North-Holland: Amsterdam, 2010. Google Scholar
  9. Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, and Tjark Vredeveld. Average case and smoothed competitive analysis of the multi-level feedback algorithm. In Algorithms for Optimization with Incomplete Information, pages 16-21, volume 05031 of Dagstuhl Seminar Proceedings, 2005. Google Scholar
  10. Markus Bläser, Bodo Manthey, and B. V. Raghavendra Rao. Smoothed analysis of partitioning algorithms for euclidean functionals. Algorithmica, 66(2):397-418, 2013. Google Scholar
  11. Avrim Blum and John Dunagan. Smoothed analysis of the perceptron algorithm for linear programming. In David Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 905-914, 2002. Google Scholar
  12. Anna Bogomolnaia and Hervé Moulin. A New Solution to the Random Assignment Problem. Journal of Economic Theory, 100:295-328, 2001. Google Scholar
  13. Karl-Heinz Borgwardt. The average number of pivot steps required by the simplex-method is polynomial. Zeitschr. für OR, 26(1):157-177, 1982. Google Scholar
  14. Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, and Bodo Manthey. Stochastic mean payoff games: Smoothed analysis and approximation schemes. In Automata, Languages and Programming - 38th International Colloquium, ICALP Part I, volume 6755 of Lecture Notes in Computer Science, pages 147-158. Springer, 2011. Google Scholar
  15. Shuchi Chawla and Balasubramanian Sivan. Bayesian algorithmic mechanism design. SIGecom Exchanges, 13(1):5-49, 2014. Google Scholar
  16. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3), 2009. URL: http://dx.doi.org/10.1145/1516512.1516516.
  17. George Christodoulou, Elias Koutsoupias, and Angelina Vidali. A lower bound for scheduling mechanisms. Algorithmica, 55(4):729-740, 2009. Google Scholar
  18. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. Google Scholar
  19. Shaddin Dughmi and Arpita Ghosh. Truthful assignment without money. In ACM Conference on Electronic Commerce, pages 325-334, 2010. Google Scholar
  20. Matthias Englert, Heiko Röglin, and Berthold Vöcking. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68(1):190-264, 2014. Google Scholar
  21. Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, and Jie Zhang. Social welfare in one-sided matchings: Random priority and beyond. In 7th International Symposium on Algorithmic Game Theory (SAGT), pages 1-12, 2014. Google Scholar
  22. Aris Filos-Ratsikas, Minming Li, Jie Zhang, and Qiang Zhang. Facility location with double-peaked preferences. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 893-899. AAAI Press, 2015. Google Scholar
  23. Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, and Nima Zeini Jahromi. On smoothed analysis of quicksort and hoare’s find. Algorithmica, 62(3-4):879-905, 2012. Google Scholar
  24. M. Guo and V. Conitzer. Strategy-proof allocation of multiple items between two agents without payments or priors. In Ninth International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS), volume 10, pages 881-888, 2010. Google Scholar
  25. Jason D. Hartline and Brendan Lucier. Bayesian algorithmic mechanism design. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pages 301-310, 2010. Google Scholar
  26. Jason D. Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings 10th ACM Conference on Electronic Commerce, ACM-EC, pages 225-234. ACM, 2009. Google Scholar
  27. Aanund Hylland and Richard Zeckhauser. The Efficient Allocation of Individuals to Positions. The Journal of Political Economy, 87(2):293-314, 1979. Google Scholar
  28. Elias Koutsoupias. Scheduling without payments. Theory Comput. Syst., 54(3):375-387, 2014. Google Scholar
  29. Elias Koutsoupias and Angelina Vidali. A lower bound of 1+ϕ for truthful scheduling mechanisms. In the 32nd International Symposium, Mathematical Foundations of Computer Science, MFCS, volume 4708 of Lecture Notes in Computer Science, pages 454-464. Springer, 2007. Google Scholar
  30. Daniel J. Lehmann, Liadan O'Callaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. J. ACM, 49(5):577-602, 2002. Google Scholar
  31. Bodo Manthey and Rüdiger Reischuk. Smoothed analysis of binary search trees. Theor. Comput. Sci., 378(3):292-315, 2007. Google Scholar
  32. Bodo Manthey and Heiko Röglin. Smoothed analysis: Analysis of algorithms beyond worst case. it - Information Technology, 53(6):280-286, 2011. Google Scholar
  33. Timo Mennle and Sven Seuken. An axiomatic approach to characterizing and relaxing strategyproofness of one-sided matching mechanisms. In Proceedings of the 15th ACM Conference on Economics and Computation, pages 37-38, 2014. Google Scholar
  34. Ahuva Mu'alem and Noam Nisan. Truthful approximation mechanisms for restricted combinatorial auctions. Games and Economic Behavior, 64(2):612-631, 2008. Google Scholar
  35. Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC, pages 129-140, 1999. Google Scholar
  36. Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1-2):166-196, 2001. Google Scholar
  37. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Thoery. Cambridge University Press, 2007. Google Scholar
  38. Jay Sethuraman Parag A. Pathak. Lotteries in student assignment: An equivalence result. Theoretical Economics, 6:1-17, 2011. Google Scholar
  39. Ariel D Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. In Proceedings of the 10th ACM Conference on Electronic Commerce, pages 177-186. ACM, 2009. Google Scholar
  40. Arvind Sankar, Daniel A. Spielman, and Shang-Hua Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM J. Matrix Analysis Applications, 28(2):446-476, 2006. Google Scholar
  41. Guido Schäfer and Naveen Sivadasan. Topology matters: Smoothed competitiveness of metrical task systems. Theor. Comput. Sci., 341(1-3):216-246, 2005. Google Scholar
  42. Tayfun Sönmez and Utku Ünver. Matching, allocation and exchange of discrete resources. Handbook of Social Economics, 1A:781-852, 2011. Google Scholar
  43. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, STOC, pages 296-305. ACM, 2001. Google Scholar
  44. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of termination of linear programming algorithms. Math. Program., 97(1-2):375-404, 2003. Google Scholar
  45. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM, 52(10):76-84, 2009. Google Scholar
  46. Lars-Gunnar Svensson. Strategy-proof allocation of indivisble goods. Social Choice and Welfare, 16(4):557-567, 1999. Google Scholar
  47. Lars-Gunnar Svensson. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4):557-567, 1999. Google Scholar
  48. Wojciech Szpankowsk. Average case analysis of algorithms. Chapman Hall CRC, 2010. Google Scholar
  49. John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton university press, 1953. Google Scholar
  50. John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior (60th Anniversary Commemorative Edition). Princeton university press, 2007. Google Scholar
  51. Lin Zhou. On a Conjecture by Gale about One-Sided Matching Problems. Journal of Economic Theory, 52:123-135, 1990. 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