|Norvig I 679
Mechanism Design/AI research/Norvig/Russell: design[ing] a game whose solutions, consisting of each agent pursuing its own rational strategy, result in the maximization of some global utility function. This problem is called mechanism design, or sometimes inverse game theory. Mechanism design is a staple of economics and political science. Capitalism 101 says that if everyone tries to get rich, the total wealth of society will increase. But (…) examples (..) show that proper mechanism design is necessary to keep the invisible hand on track. For collections of agents, mechanism design allows us to construct smart systems out of a collection of more limited systems—even uncooperative systems—in much the same way that teams of humans can achieve goals beyond the reach of any individual.
Examples of mechanism design include auctioning off cheap airline tickets, routing TCP packets between computers, deciding how medical interns will be assigned to hospitals, and deciding how robotic soccer players will cooperate with their teammates. Mechanism design became more than an academic subject in the 1990s when several nations, faced with the problem of auctioning off licenses to broadcast in various frequency bands, lost hundreds of millions of dollars in potential revenue as a result of poor mechanism design. Formally, a mechanism consists of (1) a language for describing the set of allowable strategies that agents may adopt, (2) a distinguished agent, called the center, that collects reports of strategy choices from the agents in the game, and (3) an outcome rule, known to all agents, that the center uses to determine the payoffs to each agent, given their strategy choices. >Game theory/RI research.
Norvig I 688
The 2007 Nobel Memorial Prize in Economics went to Hurwicz, Maskin, and Myerson “for having laid the foundations of mechanism design theory” (Hurwicz, 1973)(1). The tragedy of the commons, a motivating problem for the field, was presented by Hardin (1968)(2). The revelation
principle is due to Myerson (1986)(3), and the revenue equivalence theorem was developed independently by Myerson (1981(4)) and Riley and Samuelson (1981)(5). Two economists, Milgrom (1997)(6) and Klemperer (2002(7)), write about the multibillion-dollar spectrum auctions they were involved in.
Mechanism design is used in multiagent planning (Hunsberger and Grosz, 2000(8); Stone et al., 2009(9)) and scheduling (Rassenti et al., 1982)(10). Varian (1995)(11) gives a brief overview with connections to the computer science literature, and Rosenschein and Zlotkin (1994)(12) present a book-length treatment with applications to distributed AI.
Related work on distributed AI also goes under other names, including collective intelligence (Tumer and Wolpert, 2000(13); Segaran, 2007(14)) and market-based control (Clearwater, 1996)(15).
Since 2001 there has been an annual Trading Agents Competition (TAC), in which agents try to make the best profit on a series of auctions (Wellman et al., 2001(16) ; Arunachalam and Sadeh, 2005)(17). Papers on computational issues in auctions often appear in the ACM Conferences on Electronic Commerce.
1. Hurwicz, L. (1973). The design of mechanisms for resource allocation. American Economic Review Papers and Proceedings, 63(1), 1-30.
2. Hardin, G. (1968). The tragedy of the commons. Science, 162, 1243-1248.
3. Myerson, R. (1986). Multistage games with communication. Econometrica, 54, 323–358.
4. Myerson, R. (1981). Optimal auction design. Mathematics of Operations Research, 6, 58–73.
5. Riley, J. and Samuelson, W. (1981). Optimal auctions. American Economic Review, 71, 381–392.
6. Milgrom, P. (1997). Putting auction theory to work: The simultaneous ascending auction. Tech. rep.
Technical Report 98-0002, Stanford University Department of Economics.
7. Klemperer, P. (2002). What really matters in auction design. J. Economic Perspectives, 16(1).
8. Hunsberger, L. and Grosz, B. J. (2000). A combinatorial auction for collaborative planning. In Int.
Conference on Multi-Agent Systems (ICMAS-2000).
9. Stone, P., Kaminka, G., and Rosenschein, J. S. (2009). Leading a best-response teammate in an ad hoc team. In AAMAS Workshop in Agent Mediated Electronic Commerce.
10. Rassenti, S., Smith, V., and Bulfin, R. (1982). A combinatorial auction mechanism for airport time slot allocation. Bell Journal of Economics, 13, 402-417.
11. Varian, H. R. (1995). Economic mechanism design for computerized agents. In USENIX Workshop on
Electronic Commerce, pp. 13-21.
12. Rosenschein, J. S. and Zlotkin, G. (1994). Rules of Encounter. MIT Press.
13. Tumer, K. and Wolpert, D. (2000). Collective intelligence and braess’ paradox. In AAAI-00, pp. 104-
14. Segaran, T. (2007). Programming Collective Intelligence: Building Smart Web 2.0 Applications. O’Reilly.
15. Clearwater, S. H. (Ed.). (1996). Market-Based Control. World Scientific.
16. Wellman, M. P., Wurman, P., O’Malley, K., Bangera, R., Lin, S., Reeves, D., and Walsh, W. (2001). A trading agent competition. IEEE Internet Computing.
17. Arunachalam, R. and Sadeh, N. M. (2005). The supply chain trading agent competition. Electronic
Commerce Research and Applications, Spring, 66-84._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010