1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Economics
  4. Volume 11, 2019
  5. Article

Annual Review of Economics

Volume 11, 2019

Approximately Optimal Mechanism Design

Abstract

The field of optimal mechanism design enjoys a beautiful and well-developed theory, as well as several killer applications. Rules of thumb produced by the field influence everything from how governments sell wireless spectrum licenses to how the major search engines auction off online advertising. There are, however, some basic problems for which the traditional optimal mechanism design approach is ill suited—either because it makes overly strong assumptions or because it advocates overly complex designs. This article reviews several common issues with optimal mechanisms, including exorbitant communication, computation, and informational requirements; it also presents several examples demonstrating that relaxing the goal to designing an approximately optimal mechanism allows us to reason about fundamental questions that seem out of reach of the traditional theory.

Keyword(s): algorithmic game theory, auction theory, complexity, computational complexity, detail dependence, JEL D44, JEL D82, multiparameter settings, revenue maximization, simplicity, social welfare
Loading

Article metrics loading...

/content/journals/10.1146/annurev-economics-080218-025607
2019-08-02
2024-04-16
Loading full text...

Full text loading...

/deliver/fulltext/economics/11/1/annurev-economics-080218-025607.html?itemId=/content/journals/10.1146/annurev-economics-080218-025607&mimeType=html&fmt=ahah

Literature Cited

  1. Akbarpour M, Malladi S, Saberi A 2018. Just a few seeds more: value of network information for diffusion Work. Pap., Stanford Univ., Stanford, CA
  2. Alaei S, Hartline JD, Niazadeh R, Pountourakis E, Yuan Y 2015. Optimal auctions versus anonymous pricing. Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS)1446–63 Piscataway, NJ: IEEE
     [Google Scholar]
  3. Arnosti N, Beck M, Milgrom P 2016. Adverse selection and auction design for Internet display advertising. Am. Econ. Rev. 106:2852–66
     [Google Scholar]
  4. Ausubel LM, Milgrom PR 2006. The lovely but lonely Vickrey auction. Combinatorial Auctions P Cramton, Y Shoham, R Steinberg57–95 Cambridge, MA: MIT Press
     [Google Scholar]
  5. Babaioff M, Immorlica N, Lucier B, Weinberg SM 2014. A simple and approximately optimal mechanism for an additive buyer. Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS)21–30 Piscataway, NJ: IEEE
     [Google Scholar]
  6. Baliga S, Vohra R 2003. Market research and market design. Adv. Theor. Econ. 3:5
     [Google Scholar]
  7. Bandi C, Bertsimas D 2014. Optimal design for multi-item auctions: a robust optimization approach. Math. Oper. Res. 39:1012–38
     [Google Scholar]
  8. Barman S, Bhaskar U, Echenique F, Wierman A 2014. On the existence of low-rank explanations for mixed strategy behavior. Proceedings of the 10th International Conference on Web and Internet Economics T-Y Liu, Q Qi, Y Ye447–52 Berlin: Springer
     [Google Scholar]
  9. Bei X, Huang Z 2011. Bayesian incentive compatibility via fractional assignments. SODA ‘11: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms720–33 New York: ACM
     [Google Scholar]
  10. Bikhchandani S 1999. Auctions of heterogeneous objects. Games Econ. Behav. 26:193–220
     [Google Scholar]
  11. Briest P, Krysta P, Vöcking B 2011. Approximation techniques for utilitarian mechanism design. SIAM J. Comput. 40:1587–622
     [Google Scholar]
  12. Budish E 2011. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Political Econ. 119:1061–103
     [Google Scholar]
  13. Bulow J, Klemperer P 1996. Auctions versus negotiations. Am. Econ. Rev. 86:180–94
     [Google Scholar]
  14. Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J 2019. The unreasonable fairness of maximum Nash welfare. Proceedings of the 2016 ACM Conference on Economics and Computation305–22 New York: ACM
     [Google Scholar]
  15. Carroll G 2015. Robustness and linear contracts. Am. Econ. Rev. 105:536–63
     [Google Scholar]
  16. Carroll G 2017. Robustness and separation in multidimensional screening. Econometrica 85:453–88
     [Google Scholar]
  17. Carroll G 2019. Robustness in mechanism design and contracting. Annu. Rev. Econ. 11:139–66
     [Google Scholar]
  18. Chawla S, Hartline JD, Kleinberg RD 2007. Algorithmic pricing via virtual valuations. EC ‘07: Proceedings of the 8th ACM Conference on Electronic Commerce243–51 New York: ACM
     [Google Scholar]
  19. Che YK, Kim J, Kojima F 2019. Stable matching in large economies. Econometrica 87:65–110
     [Google Scholar]
  20. Che YK, Kojima F 2010. Asymptotic equivalence of probabilistic serial and random priority mechanisms. Econometrica 78:1625–72
     [Google Scholar]
  21. Clarke EH 1971. Multipart pricing of public goods. Public Choice 11:17–33
     [Google Scholar]
  22. Cramton P 1998. The efficiency of the FCC spectrum auctions. J. Law Econ. 41:727–36
     [Google Scholar]
  23. Daniely A, Schapira M, Shahaf G 2018. Inapproximability of truthful mechanisms via generalizations of the Vapnik-Chervonenkis dimension. SIAM J. Comput. 47:96–120
     [Google Scholar]
  24. Daskalakis C, Deckelbaum A, Tzamos C 2017. Strong duality for a multiple-good monopolist. Econometrica 85:735–67
     [Google Scholar]
  25. Devanur NR, Hartline JD, Karlin AR, Nguyen CT 2011. Prior-independent multi-parameter mechanism design. WINE‘11: Proceedings of the 7th International Conference on Internet and Network Economics122–33 New York: ACM
     [Google Scholar]
  26. Dobzinski S 2011. An impossibility result for truthful combinatorial auctions with submodular valuations. STOC ‘11: Proceedings of the 43rd ACM Symposium on Theory of Computing129–48 New York: ACM
     [Google Scholar]
  27. Dobzinski S 2016. Computational efficiency requires simple taxation. Proceedings of the 57th Annual Symposium on the Foundations of Computer Science (FOCS)209–18 Piscataway, NJ: IEEE
     [Google Scholar]
  28. Dobzinski S, Dughmi S 2013. On the power of randomization in algorithmic mechanism design. SIAM J. Comput. 42:2287–304
     [Google Scholar]
  29. Dobzinski S, Nisan N 2010. Mechanisms for multi-unit auctions. J. Artif. Intell. Res. 37:85–98
     [Google Scholar]
  30. Dobzinski S, Vondrák J 2016. Impossibility results for truthful combinatorial auctions with submodular valuations. J. ACM 63:5
     [Google Scholar]
  31. Dughmi S, Hartline JD, Kleinberg R, Niazadeh R 2017. Bernoulli factories and black-box reductions in mechanism design. ACM SIGecom Exchanges 16:60–73
     [Google Scholar]
  32. Dughmi S, Roughgarden T, Yan Q 2016. Optimal mechanisms for combinatorial auctions and combinatorial public projects via convex rounding. J. ACM 63:30
     [Google Scholar]
  33. Dughmi S, Vondrák J 2015. Limitations of randomized mechanisms for combinatorial auctions. Games Econ. Behav. 92:370–400
     [Google Scholar]
  34. Dütting P, Gkatzelis V, Roughgarden T 2017a. The performance of deferred-acceptance auctions. Math. Oper. Res. 42:4897–914
     [Google Scholar]
  35. Dütting P, Roughgarden T, Talgam-Cohen I 2017b. Modularity and greed in double auctions. Games Econ. Behav. 105:59–83
     [Google Scholar]
  36. Dütting P, Roughgarden T, Talgam-Cohen I 2018. Simple versus optimal contracts Work. Pap., London School Econ.
  37. Echenique F, Golovin D, Wierman A 2011. A revealed preference approach to computational complexity in economics. EC ‘11: Proceedings of the 12th ACM Conference on Electronic Commerce101–10 New York: ACM
     [Google Scholar]
  38. Eden A, Feldman M, Friedler O, Talgam-Cohen I, Weinberg SM 2017. The competition complexity of auctions: a Bulow-Klemperer result for multi-dimensional bidders. EC ‘17: Proceedings of the 18th ACM Conference on Economics and Computation343 New York: ACM
     [Google Scholar]
  39. Feldman M, Feige U, Immorlica N, Izsak R, Lucier B, Syrgkanis V 2015. A unifying hierarchy of valuations with complements and substitutes. Proceedings of the 29th AAAI Conference on Artificial Intelligence872–78 Menlo Park, CA: AAAI
     [Google Scholar]
  40. Feldman M, Friedler O, Rubinstein A 2017. 99 percent revenue via enhanced competition. EC ‘17: Proceedings of the 19th ACM Conference on Economics and Computation443–60 New York: ACM
     [Google Scholar]
  41. Feldman M, Fu H, Gravin N, Lucier B 2013. Simultaneous auctions are (almost) efficient. STOC ‘13: Proceedings of the 45th ACM Symposium on Theory of Computing201–10 New York: ACM
     [Google Scholar]
  42. Feldman M, Immorlica N, Lucier B, Roughgarden T, Syrgkanis V 2016. The price of anarchy in large games. STOC ‘16: Proceedings of the 48th Annual ACM Symposium on Theory of Computing963–76 New York: ACM
     [Google Scholar]
  43. Gkatzelis V, Markakis E, Roughgarden T 2017. Deferred-acceptance auctions for multiple levels of service. EC ‘17: Proceedings of the 18th ACM Conference on Electronic Commerce21–38 New York: ACM
     [Google Scholar]
  44. Goldberg AV, Hartline JD, Karlin A, Saks M, Wright A 2006. Competitive auctions. Games Econ. Behav. 55:242–69
     [Google Scholar]
  45. Gonczarowski YA, Nisan N 2017. Efficient empirical revenue maximization in single-parameter auction environments. STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing856–68 New York: ACM
     [Google Scholar]
  46. Groves T 1973. Incentives in teams. Econometrica 41:617–31
     [Google Scholar]
  47. Gul F, Stacchetti E 1999. Walrasian equilibrium with gross substitutes. J. Econ. Theory 87:95–124
     [Google Scholar]
  48. Hart S, Nisan N 2017. Approximate revenue maximization with multiple items. J. Econ. Theory 172:313–47
     [Google Scholar]
  49. Hart S, Reny PJ 2015. Maximal revenue with multiple goods: nonmonotonicity and other observations. Theor. Econ. 10:893–922
     [Google Scholar]
  50. Hartline JD 2017. Mechanism design and approximation Unpublished manuscript, Northwestern Univ., Evanston, IL
  51. Hartline JD, Kleinberg RD, Malekian A 2015. Bayesian incentive compatibility via matchings. Games Econ. Behav. 92:401–29
     [Google Scholar]
  52. Hartline JD, Lucier B 2015. Non-optimal mechanism design. Am. Econ. Rev. 105:3102–24
     [Google Scholar]
  53. Hartline JD, Roughgarden T 2009. Simple versus optimal mechanisms. EC ‘09: Proceedings of the 10th ACM Conference on Electronic Commerce225–34 New York: ACM
     [Google Scholar]
  54. Hassidim A, Kaplan H, Mansour M, Nisan N 2011. Non-price equilibria in markets of discrete goods. EC ‘11: Proceedings of the 12th ACM Conference on Electronic Commerce295–96 New York: ACM
     [Google Scholar]
  55. Ibarra OH, Kim CE 1975. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22:463–68
     [Google Scholar]
  56. Kalyanasundaram B, Pruhs K 2000. Speed is as powerful as clairvoyance. J. ACM 47:617–43
     [Google Scholar]
  57. Kelso A, Crawford V 1982. Job matching, coalition formation, and gross substitutes. Econometrica 50:1483–504
     [Google Scholar]
  58. Krishna V 2010. Auction Theory Cambridge, MA: Academic. 2nd ed.
  59. Kushilevitz E, Nisan N 1996. Communication Complexity Cambridge, UK: Cambridge Univ. Press
  60. Lehmann B, Lehmann D, Nisan N 2006. Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55:270–96
     [Google Scholar]
  61. Lehmann D, O'Callaghan LI, Shoham Y 2002. Truth revelation in approximately efficient combinatorial auctions. J. ACM 49:577–602
     [Google Scholar]
  62. Liu S, Psomas CA 2018. On the competition complexity of dynamic mechanism design. SODA ‘18: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms2008–25 New York: ACM
     [Google Scholar]
  63. Milgrom P 2004. Putting Auction Theory to Work Cambridge, UK: Cambridge Univ. Press
  64. Milgrom P 2017. Discovering Prices: Auction Design in Markets with Complex Constraints New York: Columbia Univ. Press
  65. Milgrom P, Segal I 2017. Deferred-acceptance clock auctions and radio spectrum reallocation Work. Pap., Stanford Univ., Stanford, CA
  66. Morgenstern J, Roughgarden T 2015. The psuedo-dimension of near-optimal auctions. NIPS‘15: Proceedings of the 28th Annual Conference on Neural Information Processing Systems 1:136–44 New York: ACM
     [Google Scholar]
  67. Myerson RB 1981. Optimal auction design. Math. Oper. Res. 6:58–73
     [Google Scholar]
  68. Neeman Z 2003. The effectiveness of English auctions. Games Econ. Behav. 43:214–38
     [Google Scholar]
  69. Newman N, Leyton-Brown K, Milgrom P, Segal I 2017. Assessing economic outcomes in simulated reverse clock auctions for radio spectrum Work. Pap., Stanford Univ., Stanford, CA
  70. Nisan N 2019. Complexity and simplicity in economic design. Future of Economic Design J-F Laslier, H Moulin, R Sanver, WS Zwicker Berlin: Springer In press
    [Google Scholar]
  71. Nisan N, Ronen A 2001. Algorithmic mechanism design. Games Econ. Behav. 35:166–96
     [Google Scholar]
  72. Nisan N, Ronen A 2007. Computationally feasible VCG mechanisms. J. Artif. Intell. Res. 29:19–47
     [Google Scholar]
  73. Oxley JG 1992. Matroid Theory Oxford, UK: Oxford Univ. Press
  74. Papadimitriou CH, Schapira M, Singer Y 2008. On the hardness of being truthful. FOCS ‘09: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science250–59 Piscataway, NJ: IEEE
     [Google Scholar]
  75. Psomas CA, Schvartzman A, Weinberg SM 2018. Beyond worst-case analysis of multi-item auctions with correlated values Work. Pap., Princeton Univ., Princeton, NJ
  76. Roberts DJ, Postlewaite A 1976. The incentives for price-taking behavior in large exchange economies. Econometrica 44:115–27
     [Google Scholar]
  77. Rochet JC 1987. A necessary and sufficient condition for rationalizability in a quasilinear context. J. Math. Econ. 16:191–200
     [Google Scholar]
  78. Roughgarden T 2010. Computing equilibria: a computational complexity perspective. Econ. Theory 42:193–236
     [Google Scholar]
  79. Roughgarden T 2014a. Approximately optimal mechanism design: motivation, examples, and lessons learned. ACM SIGEcom Exchanges 13:4–20
     [Google Scholar]
  80. Roughgarden T 2014b. Barriers to near-optimal equilibria. FOCS ‘14: Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science71–80 Piscataway, NJ: IEEE
     [Google Scholar]
  81. Roughgarden T 2016a. Communication complexity (for algorithm designers). Found. Trends Theor. Comput. Sci. 11:217–404
     [Google Scholar]
  82. Roughgarden T 2016b. Twenty Lectures on Algorithmic Game Theory Cambridge, UK: Cambridge Univ. Press
  83. Roughgarden T, Syrgkanis V, Tardos E 2017a. The price of anarchy in auctions. J. Artif. Intell. Res. 59:59–101
     [Google Scholar]
  84. Roughgarden T, Talgam-Cohen I, Yan Q 2017b. Robust auctions for revenue via enhanced competition Work. Pap., Stanford Univ., Stanford, CA
  85. Rubinstein A, Weinberg SM 2015. Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. EC ‘15: Proceedings of the 16th ACM Conference on Electronic Commerce377–94 New York: ACM
     [Google Scholar]
  86. Samuel-Cahn E 1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12:1213–16
     [Google Scholar]
  87. Segal I 2003. Optimal pricing mechanisms with unknown demand. Am. Econ. Rev 93:509–29
     [Google Scholar]
  88. Sipser M 2006. Introduction to the Theory of Computation Boston, MA: Cengage
  89. Sivan B, Syrgkanis V 2013. Vickrey auctions for irregular distributions. WINE 2013: Proceedings of the 9th International Conference on Web and Internet Economics422–35 Berlin: Springer
     [Google Scholar]
  90. Sleator DD, Tarjan RE 1985. Amortized efficiency of list update and paging rules. Commun. ACM 28:202–8
     [Google Scholar]
  91. Swinkels JM 2001. Efficiency of large private value auctions. Econometrica 69:37–68
     [Google Scholar]
  92. Syrgkanis V, Tardos É 2013. Composable and efficient mechanisms. STOC ‘13: Proceedings of the 45th Annual ACM Symposium on Theory of Computing211–20 New York: ACM
     [Google Scholar]
  93. Vickrey W 1961. Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16:8–37
     [Google Scholar]
  94. Wilson RB 1987. Game-theoretic analyses of trading processes. Advances in Economic Theory: Fifth World Congress TF Bewley33–70 Cambridge, UK: Cambridge Univ. Press
     [Google Scholar]
  95. Yao ACC 2015. An -to-1 bidder reduction for multi-item auctions and its applications. SODA ‘15: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms92–109 New York: ACM
     [Google Scholar]
/content/journals/10.1146/annurev-economics-080218-025607
Loading
Approximately Optimal Mechanism Design
Annual Review of Economics 11, 355 (2019); https://doi.org/10.1146/annurev-economics-080218-025607
/content/journals/10.1146/annurev-economics-080218-025607
/content/journals/10.1146/annurev-economics-080218-025607
Loading

Data & Media loading...

  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error