Miscomputing ratio: social cost of selfish computing

ABSTRACT

Auctions are useful mechanism for allocating items (goods, tasks, resources, etc.) in multiagent systems. The bulk of auction theory assumes that the bidders' valuations for items are given a priori. However, in many applications the bidders need to expend significant computational effort to determine their valuations. We introduce a way of measuring the negative impact of agents choosing computing strategies selfishly. Our miscomputing ratio isolates the effect of selfish computing from that of selfish bidding. We present a Bayes-Nash equilibrium analysis of a Vickrey auction where the bidders' strategies include computational actions. This equilibrium analysis allows us to predict the overhead caused by miscomputing, as measured by the miscomputing ratio. We show that in some situations, the outcome can be arbitrarily far from optimal. However, by carefully designing cost functions for agents, it is possible to provide incentives for bidders to choose computing policies that result in optimal social welfare.

REFERENCES

• 1: Dirk Bergemann and Juuso Välimäki. Information acquisition and efficient mechanism design. Econometrica, 70:1007--1034, 2002.
• 2: Mark Boddy , Thomas L. Dean, Deliberation scheduling for problem solving in time-constrained environments, Artificial Intelligence, v.67 n.2, p.245-285, June 1994 [doi>10.1016/0004-3702(94)90054-X]
• 3: Eric A. Hansen , Shlomo Zilberstein, Monitoring and control of anytime algorithms: a dynamic programming approach, Artificial Intelligence, v.126 n.1-2, p.139-157, Feb., 2001 [doi>10.1016/S0004-3702(00)00068-0]
• 4: Mechanism Design for Resource Bounded Agents, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.309, July 10-12, 2000
• 5: Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Symposium on Theoretical Aspects in Computer Science, 1999.
• 6: Kate Larson , Tuomas Sandholm, Bargaining with limited computation: deliberation equilibrium, Artificial Intelligence, v.132 n.2, p.183-217, November 2001 [doi>10.1016/S0004-3702(01)00132-1]
• 7: Kate Larson and Tuomas Sandholm. Computationally limited agents in auctions. In AGENTS-01 Workshop of Agents for B2B, pages 27--34, Montreal, Canada, May 2001.
• 8: Kate Larson , Tuomas Sandholm, Costly valuation computation in auctions, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
• 9: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 10: 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]
• 11: 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]
• 12: David C Parkes. Optimal auction design for agents with hard valuation problems. In Agent Mediated Electronic Commerce Workshop at the International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 1999.
• 13: Nicola Perisco. Information acquisition in auctions. Econometrica, 68(1):135--148, January 2000.
• 14: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 15: Stuart Russell , Eric Wefald, Do the right thing: studies in limited rationality, MIT Press, Cambridge, MA, 1991
• 16: Tuomas Sandholm. Issues in computational Vickrey auctions. International Journal of Electronic Commerce, 4(3):107--129, 2000.
• 17: Herbert A Simon. Models of bounded rationality, volume 2. MIT Press, 1982.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Design, Theory

Keywords:
auctions, resource-bounded agents