Distributed algorithmic mechanism design: recent results and future directions

ABSTRACT

Distributed Algorithmic Mechanism Design (DAMD) combines theoretical computer science's traditional focus on computational tractability with its more recent interest in incentive compatibility and distributed computing. The Internet's decentralized nature, in which distributed computation and autonomous agents prevail, makes DAMD a very natural approach for many Internet problems. This paper first outlines the basics of DAMD and then reviews previous DAMD results on multicast cost sharing and interdomain routing. The remainder of the paper describes several promising research directions and poses some specific open problems..

REFERENCES

• 1: D. Abreu and A. Sen, "Virtual Implementation in Nash Equilibrium," Econometrica 59 (1991), pages 997--1022.
• 2: E. Adar and B. Huberman, "Free Riding on Gnutella," in First Monday, http://www.firstmonday.dk/ issues/issue5_10/adar/index.html, October 2000.
• 3: Micah Adler , Dan Rubenstein, Pricing multicasting in more practical network models, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.981-990, January 06-08, 2002, San Francisco, California
• 4: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: A. Archer, J. Feigenbaum, A. Krishnamurthy, R. Sami, and S. Shenker, "Approximation and Collusion in Multicast Cost Sharing," submitted. http://www.cs.yale.edu/homes/jf/AFKSS.ps
• 6: Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
• 7: K. Arrow, "The Property-Rights Doctrine and Demand Revelation under Incomplete Information," in Economics and Human Welfare, Academic Press, New York, pages 23--39, 1979.
• 8: S. Barbera and M. Jackson, "Strategy-proof exchange," Econometrica 63 (1995), pages 51--87.
• 9: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 10: B. Bernheim, "Rationalizable Strategic Behavior," Econometrica 52 (1984), pages 1007--1028.
• 11: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 12: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 13: E. Clarke, "Multipart pricing of public goods," Public Choice 11 (1971), pages 17--33.
• 14: C. d'Aspremont and L.-A. Gérard-Varet, "Incentives and Incomplete Information," Journal of Public Economics 11 (1979), pages 25--45.
• 15: Yevgeniy Dodis , Shai Halevi , Tal Rabin, A Cryptographic Solution to a Game Theoretic Problem, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.112-130, August 20-24, 2000
• 16: B. Dutta and D. Ray, "A concept of egalitarianism under participation constraints," Econometrica 57 (1989), pages 615-635.
• 17: L. Erev and A. Roth, "Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria," American Economic Review 88 (1998), pages 848--881.
• 18: J. Feigenbaum, A. Krishnamurthy, R. Sami, and S. Shenker, "Hardness Results for Multicast Cost Sharing," Yale University Technical Report YALEU/DCS/TR1232, June 2002, http://ftp.cs.yale.edu/pub/TR/tr1232.ps
• 19: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 20: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 21: D. Ferguson, C. Nikolaou, and Y. Yemini, "An Economy for Flow Control in Computer Networks," in Proceedings of the 8th Infocom, IEEE Computer Society Press, Los Alamitos, pages 100--118, 1989.
• 22: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 23: D. Foster and R. Vohra, "Calibrated Learning and Correlated Equilibrium," Games and Economic Behavior 21 (1997), pages 40--55.
• 24: E. Friedman and S. Shenker, "Learning and Implementation on the Internet," http://www.icir.org/shenker/decent.ps
• 25: R. Gibbens and R. Kelly, "Resource Pricing and the Evolution of Congestion Control," Automatica 35 (1999), pages 1969--1985.
• 26: O. Goldreich, "Secure Multi-party Computation (working draft, Version 1.1)," 1998. http://philby.ucsd.edu/cryptoloib/BOOKS/oded-sc.html
• 27: J. Green, E. Kohlberg, J. and Laffont, "Partial equilibrium approach to the free rider problem," Journal of Public Economics 6 (1976), pages 375--394.
• 28: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.277-288, Oct. 1999
• 29: T. Groves, "Incentives in teams," Econometrica 41 (1973), pages 617--663.
• 30: J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.252, October 14-17, 2001
• 31: Man-tung T. Hsiao , Aurel A. Lazar, A Game Theoretic Approach to Decentralized Flow Control of Markovian Queueing Networks, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.55-73, December 07-09, 1987
• 32: M. Jackson, "A Crash Course in Implementation Theory," Social Choice and Welfare, 18 (2001), pages 655--708.
• 33: Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
• 34: T. Kelly, Y-M. Chan, S. Jamin, and J. MacKie-Mason, "Biased Replacement Policies for Web Caches: Differential Quality-of-Service and Aggregate User Value," in Proceedings of the 4th International Web Caching Workshop, pages 1--10, 1999.
• 35: Y. Korilis, A. Lazar, and A. Orda, "Architecting Noncooperative Networks," Journal on Selected Areas in Communications 13 (1995), pages 1241--1251.
• 36: James F. Kurose , Rahul Simha, A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems, IEEE Transactions on Computers, v.38 n.5, p.705-717, May 1989 [doi>10.1109/12.24272]
• 37: P. McAfee, "A Dominant-Strategy Double Auction," Journal of Economic Theory 56 (1992), pages 434--450.
• 38: E. Maskin, "Nash Equilibrium and Welfare Optimality," Review of Economic Studies 66 (1999), pages 23--38.
• 39: H. Matsushima, "A New Approach to the Implementation Problem," Journal of Economic Theory 45 (1988), pages 128--144.
• 40: J. McCoy, http://www.mojonation.net/
• 41: A. Mehta, S. Shenker, and V. Vazirani, "Profit-Maximizing Multicast Pricing by Approximating Fixed Points," submitted. http://www.cc.gatech.edu/ people/home/aranyak/multicast.ps
• 42: P. Milgrom and J. Roberts, "Adaptive and Sophisticated Learning in Normal Form Games," Games and Economic Behavior 3 (1991), pages 82--100.
• 43: J. Mitchell, R. Sami, K. Talwar, and V. Teague, Private communication, 2001.
• 44: J. Mitchell and V. Teague, Private communication, 2002.
• 45: H. Moulin. "Strategyproofness and Singlepeakedness," Public Choice 35 (1980), pages 437--455.
• 46: H. Moulin. "Incremental cost sharing: characterization by strategyproofness," Social Choice and Welfare 16 (1999), pages 279--320.
• 47: H. Moulin and S. Shenker, "Strategyproof Sharing of Submodular Costs: Budget Balance Versus Efficiency," Economic Theory 18 (2001), pages 511--533.
• 48: Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece [doi>10.1145/380752.380855]
• 49: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 50: N. Nisan, "Algorithms for Selfish Agents: Mechanism Design for Distributed Computation," in Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, volume 1563, Springer, Berlin, pages 1--17, 1999.
• 51: N. Nisan, "Rationality as a Paradigm for Internet Computing," Invited Talk at the U. C. Berkeley Workshop on Theory of Computation & the Sciences, http://www.cs.huji,il/~noam/rationality.ppt.
• 52: N. Nisan and A. Ronen, "Algorithmic mechanism design," Games and Economic Behavior 35 (2001), pages 166--196.
• 53: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 54: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 55: David Christopher Parkes , Lyle H. Ungar, Iterative combinatorial auctions: achieving economic and computational efficiency, 2001
• 56: D. Parkes, J. Kalagnanam, and M. Eso, "Achieving Budget-Balance with Vickrey-Based Payment Schemes in Exchanges," in Proceedings of the 17th International Joint Conference on Artificial Intelligence, Morgan Kaufman, San Francisco, pages 1161--1168, 2001.
• 57: D. Pearce, "Rationalizable Strategic Behavior and the Problem of Perfection," Econometrica 52 (1984), pages 1029--1050.
• 58: K. Roberts, "The Characterization of Implementable Choice Rules," in Aggregation and Revelation of Preferences, North-Holland, Amsterdam, pages 321--348, 1979.
• 59: S. Saroiu, P. Gummadi, and S. Gribble, "A Measurement Study of Peer-to-Peer File Sharing Systems," in Proceedings of Multimedia Computing and Networking, SPIE Press, Bellingham, pages 156--170, 2002.
• 60: J. Schummer, "Almost-dominant Strategy Implementation," http://www.kellogg.nwu.edu/faculty/schummer/ftp/research/esp.pdf
• 61: Craig Boutilier , Yoav Shoham , Michael P. Wellman, Economic principles of multi-agent systems, Artificial Intelligence, v.94 n.1-2, p.1-6, July 1997 [doi>10.1016/S0004-3702(97)00029-5]
• 62: J. Smith, Evolution and the Theory of Games, Cambridge University Press, Cambridge, 1982.
• 63: Y. Sprumont, "The division problem with single-peaked preferences: A characterization of the uniform rule," Econometrica 59 (1991), pages 509--519.
• 64: W. Vickrey, "Counterspeculation, auctions, and competitive sealed tenders," Journal of Finance 16 (1961), pages 8--37.
• 65: William E. Walsh , Michael P. Wellman, A Market Protocol for Decentralized Task Allocation, Proceedings of the 3rd International Conference on Multi Agent Systems, p.325, July 03-07, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
Internet algorithms, algorithmic mechanism design, distributed computation, multicast, routing