Algorithmic mechanism design

Computational complexity and fairness results for markets and games



Mecha design, courtesy blueprintbox.

Hard theory of incetnive mechanism, where we can plug numbers into sufficiently abstract models and maybe extract computational complexity results.

Every blockchain-style cryptowhatsit is a mechanism design problem. Better governance is a mechanism design problem.

Tutorials

Aaron Roth’s Algorithmic Game theory course

In this course, we will take an algorithmic perspective on problems in game theory. We will consider questions such as: how should an auction for scarce goods be structured if the seller wishes to maximize his revenue? How badly will traffic be snarled if drivers each selfishly try to minimize their commute time, compared to if a benevolent dictator directed traffic? How can couples be paired so that no two couples wish to swap partners in hindsight? How can you be as successful at betting on horse races as the best horse racing expert, without knowing anything about horse racing? How can we set prices so that all goods get sold, and everyone gets their favorite good?

A mechanism incentivising coordination.

References

Arthur, W Brian. 1995. “Complexity in Economic and Financial Markets.” Complexity 1 (1): 20–25.
Atanasov, Pavel, Philip Rescober, Eric Stone, Samuel A Swift, Emile Servan-Schreiber, Philip E. Tetlock, Lyle Ungar, and Barbara Mellers. 2015. Distilling the Wisdom of Crowds: Prediction Markets Versus Prediction Polls.” Academy of Management Proceedings 2015 (1): 15192.
Aziz, Haris. 2020. Developments in Multi-Agent Fair Allocation.” In Proceedings of the AAAI Conference on Artificial Intelligence, 34:13563–68.
Aziz, Haris, Péter Biró, Ronald de Haan, and Baharak Rastegari. 2019. Pareto Optimal Allocation Under Uncertain Preferences: Uncertainty Models, Algorithms, and Complexity.” Artificial Intelligence 276 (November): 57–78.
Aziz, Haris, Sylvain Bouveret, Ioannis Caragiannis, Ira Giagkousi, and Jérôme Lang. 2018. Knowledge, Fairness, and Social Constraints.” Proceedings of the AAAI Conference on Artificial Intelligence 32 (1).
Aziz, Haris, and Florian Brandl. 2012. Existence of Stability in Hedonic Coalition Formation Games.” arXiv.
Aziz, Haris, Florian Brandl, Felix Brandt, and Markus Brill. 2018. On the Tradeoff Between Efficiency and Strategyproofness.” Games and Economic Behavior 110 (July): 1–18.
Aziz, Haris, Felix Brandt, and Paul Harrenstein. 2013. Pareto Optimality in Coalition Formation.” In Games and Economic Behavior, 82:562–81.
Aziz, Haris, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. 2021. Fair Allocation of Combinations of Indivisible Goods and Chores.” arXiv.
Aziz, Haris, and Bart de Keijzer. 2011. Complexity of Coalition Structure Generation.” arXiv.
Aziz, Haris, and Simon Rey. 2019. Almost Group Envy-Free Allocation of Indivisible Goods and Chores.” arXiv.
Berg, Nathan. 2003. “Normative Behavioral Economics.” The Journal of Socio-Economics 32 (4): 411–27.
Börgers, Tilman. 2015. An Introduction to the Theory of Mechanism Design. New York, NY: Oxford University Press, USA.
Brandt, Felix, and Martin Bullinger. 2020. “Finding and Recognizing Popular Coalition Structures.” In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, 195–203. AAMAS ’20. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems.
———. 2022. Finding and Recognizing Popular Coalition Structures.” Journal of Artificial Intelligence Research 74 (June): 569–626.
Buterin, Vitalik, Zoë Hitzig, and E. Glen Weyl. 2019. A Flexible Design for Funding Public Goods.” Management Science 65 (11): 5171–87.
Cai, Yang, Constantinos Daskalakis, and S. Matthew Weinberg. 2013. Understanding Incentives: Mechanism Design Becomes Algorithm Design.” arXiv:1305.4002 [Cs], May.
Challet, Damien, Matteo Marsili, and Yi-Chang Zhang. 2000. “Modeling Market Mechanism with Minority Game.” Physica A: Statistical and Theoretical Physics 276 (1-2): 284–315.
Daskalakis, Constantinos, Alan Deckelbaum, and Christos Tzamos. 2012a. Optimal Pricing Is Hard.” In Internet and Network Economics, edited by Paul W. Goldberg, 7695:298–308. Berlin, Heidelberg: Springer Berlin Heidelberg.
———. 2012b. The Complexity of Optimal Mechanism Design.” arXiv:1211.1703 [Cs], November.
———. 2013. Mechanism Design via Optimal Transport.” In, 269. ACM Press.
Gasparyan, Armen Yuri, Alexey N. Gerasimov, Alexander A. Voronov, and George D. Kitas. 2015. Rewarding Peer Reviewers: Maintaining the Integrity of Science Communication.” Journal of Korean Medical Science 30 (4): 360–64.
Gemp, Ian, Brian McWilliams, Claire Vernade, and Thore Graepel. 2020. EigenGame: PCA as a Nash Equilibrium.” In.
Gode, Dhananjay K, and Shyam Sunder. 1993. Allocative Efficiency of Markets with Zero-Intelligence Traders: Market as a Partial Substitute for Individual Rationality.” The Journal of Political Economy 101: 119–37.
———. 1997. “What Makes Markets Allocationally Efficient?” The Quarterly Journal of Economics 112: 603–30.
Goldbaum, David. 2004. On the Possibility of Informationally Efficient Markets.” Working Papers Rutgers University, Newark 2004-009. Department of Economics, Rutgers University, Newark.
Jackson, Matthew O. 2014. Mechanism Theory.” SSRN Scholarly Paper ID 2542983. Rochester, NY: Social Science Research Network.
Jan, Zeeshan. n.d. “Recognition and Reward System for Peer-Reviewers,” 9.
Maital, Shlomo. 1986. Prometheus Rebound: On Welfare-Improving Constraints.” Eastern Economic Journal 12 (3): 337–44.
Mcleod, Doug, Garry Emmerson, Robert Kohn, and Geoff Kingston (universit. 2008. “Finding the Invisible Hand: An Objective Model of Financial Markets.”
Merrifield, Michael R, and Donald G Saari. 2009. Telescope Time Without Tears: A Distributed Approach to Peer Review.” Astronomy & Geophysics 50 (4): 4.16–20.
Milgrom, Paul. 2019. Auction Market Design: Recent Innovations.” Annual Review of Economics 11 (1): 383–405.
Nisan, Noam. 2007. Algorithmic Game Theory. Cambridge ; New York: Cambridge University Press.
Ohsawa, Shohei. 2021. Unbiased Self-Play.” arXiv:2106.03007 [Cs, Econ, Stat], June.
Raghavan, Manish. 2021. The Societal Impacts of Algorithmic Decision-Making.” Cornell University Library.
Roughgarden, Tim, and Inbal Talgam-Cohen. 2019. Approximately Optimal Mechanism Design.” Annual Review of Economics 11 (1): 355–81.
Sadrieh, Abdolkarim. 1998. The Alternating Double Auction Market: A Game Theoretic and Experimental Investigation (Lecture Notes in Economics and Mathematical Systems). Springer.
Shah, Nihar B. 2022. Challenges, Experiments, and Computational Solutions in Peer Review.” Communications of the ACM 65 (6): 76–87.
Solomon, David J. 2007. The Role of Peer Review for Scholarly Journals in the Information Age.” Journal of Electronic Publishing 10 (1).
Su, Francis Edward. 1999. Rental Harmony: Sperner’s Lemma in Fair Division.” The American Mathematical Monthly 106 (10): 930–42.
Sun, Albert. 2014. To Divide the Rent, Start With a Triangle.” The New York Times, April 28, 2014.
Wojtowicz, Zachary, Nick Chater, and George Loewenstein. 2019. Boredom and Flow: An Opportunity Cost Theory of Attention-Directing Motivational States.” SSRN Scholarly Paper. Rochester, NY.
Xiao, Yuanzhang, Florian Dörfler, and Mihaela van der Schaar. 2014. Incentive Design in Peer Review: Rating and Repeated Endogenous Matching.” arXiv:1411.2139 [Cs], November.
Xu, Yichong, Han Zhao, and Xiaofei Shi. n.d. “Mechanism Design for Paper Review,” 9.
Ye, Yinyu. 2008. A Path to the Arrow–Debreu Competitive Market Equilibrium.” Mathematical Programming 111 (1-2): 315–48.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.