Algorithmic mechanism design. (English) Zbl 0996.68251
Summary: The authors consider algorithmic problems in a distributed setting where the participants cannot he assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are capable of manipulating the algorithm, the algorithm designer should ensure in advance that the agents’ interests are best screed by behaving correctly. Following notions from the field of mechanism design, we suggest a framework for studying such algorithms. The main technical contribution concerns the study of a representative task scheduling problem for which the standard mechanism design tools do not suffice.
MSC:
| 68W15 | Distributed algorithms |
| 68M14 | Distributed systems |
| 68W25 | Approximation algorithms |
| 91A10 | Noncooperative games |
Keywords:
schedulingReferences:
| [1] | Clarke, E. H., Multipart Pricing of Public Goods, Public Choice, 17-33 (1971) |
| [2] | Ephrati, E.; Rosenschein, J. S., The Clarke Tax As a Concensus Mechanism among Automated Agents, Proceedings of the National Conference on Artificial Intelligence (1991), p. 173-178 |
| [3] | Ferguson, D. F.; Nikolaou, C.; Yemini, Y., Economic Models for Allocating Resources in Computer Systems, (Clearwater, S., Market-Based Control: A Paradigm for Distributed Resource Allocation (1995), World Scientific) |
| [4] | Green, J.; Laffont, J. J., Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods, Econometrica, 427-438 (1977) · Zbl 0366.90021 |
| [5] | Groves, T., Incentives in Teams, Econometrica, 617-631 (1973) · Zbl 0311.90002 |
| [6] | Harstad, R. M, Rothkopf, M. H, and, Pekec, A. 1995, Computationally Manageable Combinatorial Auctions, Technical Report, 95-09, DIMACS, Rutgers University.; Harstad, R. M, Rothkopf, M. H, and, Pekec, A. 1995, Computationally Manageable Combinatorial Auctions, Technical Report, 95-09, DIMACS, Rutgers University. · Zbl 0989.90094 |
| [7] | Hochbaum, D. S., Approximation Algorithms for NP-Hard Problems (1997), PWS Publishing Company |
| [8] | Horowitz, E.; Sahni, S., Exact and Approximate Algorithms for Scheduling Nonidentical Processors, J. Assoc. Comput. Machinery, 317-327 (1976) · Zbl 0329.68041 |
| [9] | Huberman, B. A.; Hogg, T., Distributed Computation As an Economic System, J. Econom. Perspect., 141-152 (1995) |
| [10] | Korilis, Y. A.; Lazar, A. A.; Orda, A., Architecting Noncooperative Networks, IEEE J. Selected Areas Commun. (Special Issue on Advances in the Fundamentals of Networking), 13, 1241-1251 (September 1991) |
| [11] | Lamport, L.; Shostak, R. E.; Pease, C., The Byzantine Generals Problem, ACM Trans. Program. Lang. Syst., 382-401 (1982) · Zbl 0483.68021 |
| [12] | Lazar, A. A.; Semret, N., The Progressive Second Price Auction Mechanism for Network Resource Sharing, 8th International Symposium on Dynamic Games (1998) |
| [13] | Lehmann, D. 1999, Private Communication.; Lehmann, D. 1999, Private Communication. |
| [14] | Lenstra, J. K.; Shmoys, D. B.; Tardos, E., Approximation Algorithms for Scheduling Unrelated Parallel Machines, 28th Annual Symposium on Foundations of Computer Science (1987), IEEE, p. 217-224 |
| [15] | Lineal, N., Game Theoretic Aspects of Computing, Handbook of Game Theory (1994), Elsevier Science Publishers B.V, p. 1339-1395 · Zbl 0925.90092 |
| [16] | Mas-Collel, A.; Whinston, W.; Green, J., Microeconomic Theory (1995), Oxford University Press · Zbl 1256.91002 |
| [17] | McMillan, J., Selling Spectrum Rights, J. Econ. Perspect., 145-162 (1994) |
| [18] | Market design Inc, Web Page, http://www.market-design.com; Market design Inc, Web Page, http://www.market-design.com |
| [19] | Monderer, D, and, Tennenholtz, M. Distributed Games, Games Econ. Behav, forthcoming.; Monderer, D, and, Tennenholtz, M. Distributed Games, Games Econ. Behav, forthcoming. · Zbl 0937.91011 |
| [20] | Nisan, N., Algorithms for Selfish Agents, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (1999) |
| [21] | Nisan, N.; Ronen, A., “Algorithmic Mechanism Design” (extended abstract), The Thirty-First Annual ACM Symposium om Theory of Computing (STOC99) (1999), p. 129-140 · Zbl 1346.68246 |
| [22] | Osborne, M. J.; Rubistein, A., A Course in Game Theory (1994), MIT Press · Zbl 1194.91003 |
| [23] | Papadimitriou, C. H., Computational Aspects of Organization Theory, Proceedings of the 1996 European Symposium on Algorithms (1996), Springer LNCS |
| [24] | Papadimitriou, C. H.; Yannakakis, M., On the Value of Information in Distributed Decision-Making (extended abstract), Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing (1991), p. 61-64 · Zbl 1314.91068 |
| [25] | Papadimitriou, C. H.; Yannakakis, M., “Linear Programming without the Matrix” (extended abstract), Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing (1993), p. 121-129 · Zbl 1310.90073 |
| [26] | Roberts, K., The Characterization of Implementable Choice Rules, (Laffont, J.-J., Aggregation and Revelation of Preferences (1979), North-Holland), 321-349 · Zbl 0429.90009 |
| [27] | Rosenschein, J. S.; Zlotkin, G., Rules of Encounter: Designing Conventions for Automated Negotiation among Computers (1994), MIT Pres |
| [28] | Sandholm, T. W., Limitations of the Vickrey Auction in Computational Multiagent Systems, Proceedings of the Second International Conference on Multiagent Systems (ICMAS-96) (1996), Keihanna Plaza: Keihanna Plaza Kyoto, p. 299-306 |
| [29] | Shenkar, S.; Clark, D. E.; Hertzog, S., Pricing in Computer Networks: Reshaping the Research Agenda, ACM Computational Comm. Rev., 19-43 (1996) |
| [30] | Shoham, Y.; Tanaka, K., “A Dynamic Theory of Incentives in Multi-Agent Systems” (preliminary report), Proceedings of the Fifteenth International Joint Conferences on Artificial Intelligence (1997), p. 626-631 |
| [31] | Vickrey, W., Counterspeculation, Auctions and Competitive Sealed Tenders, J. Finance, 8-37 (1961) |
| [32] | Walsh, W. E.; Wellman, M. P., A Market Protocol for Decentralized Task Allocation: Extended Version, Proceedings of the Third International Conference on Multi-Agent Systems (ICMAS-98) (1998) |
| [33] | Walsh, W. E.; Wellman, M. P.; Wurman, P. R.; MacKie-Mason, J. K., Auction Protocols for Decentralized Scheduling, Proceedings of The Eighteenth International Conference on Distributed Computing Systems (ICDCS-98) (1998) · Zbl 0996.90047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
