Computationally-efficient combinatorial auctions for resource allocation in weakly-coupled MDPs

ABSTRACT

The capabilities of an autonomous agent are often determined by the resources that are available to it. We examine the problem of allocating scarce resources among multiple self-interested agents, operating in complex, stochastic environments (modeled as MDPs), where the value of a particular resource bundle to an agent is the expected payoff of the best control policy the agent can implement using these resources. Combinatorial auctions are popular mechanisms for allocating resource bundles among agents with such complex preferences. In particular, generalized Vickrey auctions (GVAs) yield socially optimal outcomes and have excellent strategic complexity, but suffer from high computational complexity for the agents' preference-valuation and the auctioneer's winner-determination problems. We describe a GVA-based mechanism that exploits knowledge of the agents' MDP-based resource preferences, and we show analytically and demonstrate empirically that this leads to an exponential improvement in computational efficiency over a straightforward GVA implementation with flat preferences. We also present a distributed implementation of the winner-determination problem that leads to further speedup while maintaining strategy-proofness of the mechanism, and without revealing agents' private MDP information.

REFERENCES

• 1: Craig Boutilier, Solving concisely expressed combinatorial auction problems, Eighteenth national conference on Artificial intelligence, p.359-366, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 2: C. Boutilier, R. Dearden, and M. Goldszmidt. Exploiting structure in policy construction. In Proc. of the 14th Int. Joint Conf. on Artificial Intelligence, pages 1104--1111. Morgan Kaufmann, 1995.
• 3: C. Boutilier and H. H. Hoos. Bidding languages for combinatorial auctions. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pages 1211--1217, 2001.
• 4: E. H. Clarke. Multipart pricing of public goods. Public Choice, 18:19--33, 1971.
• 5: Sven de Vries , Rakesh V. Vohra, Combinatorial Auctions: A Survey, INFORMS Journal on Computing, v.15 n.3, p.284-309, July 2003 [doi>10.1287/ijoc.15.3.284.16077]
• 6: D. A. Dolgov and E. H. Durfee. Optimal resource allocation and policy formulation in loosely-coupled Markov decision processes. In Proc. of the 14th Int. Conf. on Automated Planning and Scheduling, 2004.
• 7: Donald F. Ferguson , Christos Nikolaou , Jakka Sairamesh , Yechiam Yemini, Economic models for allocating resources in computer systems, Market-based control: a paradigm for distributed resource allocation, World Scientific Publishing Co., Inc., River Edge, NJ, 1996
• 8: T. Groves. Incentives in teams. Econometrica, 41(4):617--631, 1973.
• 9: L. Kallenberg. Linear Programming and Finite Markovian Control Problems. Math. Centrum, Amsterdam, 1983.
• 10: J. K. MacKie-Mason and H. Varian. Generalized Vickrey auctions. Technical report, University of Michigan, 1994.
• 11: Nicolas Meuleau , Milos Hauskrecht , Kee-Eung Kim , Leonid Peshkin , Leslie Pack Kaelbling , Thomas Dean , Craig Boutilier, Solving very large weakly coupled Markov decision processes, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.165-172, July 1998, Madison, Wisconsin, United States
• 12: David Christopher Parkes , Lyle H. Ungar, Iterative combinatorial auctions: achieving economic and computational efficiency, 2001
• 13: David C. Parkes , Jeffrey Shneidman, Distributed Implementations of Vickrey-Clarke-Groves Mechanisms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.261-268, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.108]
• 14: M. L. Puterman. Markov Decision Processes. John Wiley & Sons, New York, 1994.
• 15: Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
• 16: P. Schweitzer and A. Seidmann. Generalized polynomial approximations in Markovian decision processes. Journal of Math. Analysis and Applications, 110:568--582, 1985.
• 17: Satinder Singh , David Cohn, How to dynamically merge Markov decision processes, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.1057-1063, July 1998, Denver, Colorado, United States
• 18: W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. J. of Finance, 1961.
• 19: M. Wellman, W. Walsh, P. Wurman, and J. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 35:271--303, 2001.
• 20: L. Wolsey. Integer Programming. John Wiley & Sons, 1998.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

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

General Terms:
Algorithms, Design, Performance

Keywords:
combinatorial auctions, distributed implementation, generalized Vickrey auctions, markov decision processes