Addressing strategic behavior in a deployed microeconomic resource allocator

ABSTRACT

While market-based systems have long been proposed as solutions for distributed resource allocation, few have been deployed for production use in real computer systems. Towards this end, we present our initial experience using Mirage, a microeconomic resource allocation system based on a repeated combinatorial auction. Mirage allocates time on a heavily-used 148-node wireless sensor network testbed. In particular, we focus on observed strategic user behavior over a four-month period in which 312,148 node hours were allocated across 11 research projects. Based on these results, we present a set of key challenges for market-based resource allocation systems based on repeated combinatorial auctions. Finally, we propose refinements to the system's current auction scheme to mitigate the strategies observed to date and also comment on some initial steps toward building an approximately strategyproof repeated combinatorial auction.

REFERENCES

• 1: Crossbow corporation. http://www.xbow.com.
• 2: Buyya, R., Abramson, D., and Giddy, J. NimrodG: An Architecture of a Resource Management and Scheduling System in a Global Computational Grid. In Proceedings of the 4th International Conference on High Performance Computing in Asia-Pacific Region (May 2000).
• 3: Chun, B. N., Buonadonna, P., AuYoung, A., Ng, C., Parkes, D. C., Shneidman, J., Snoeren, A. C., and Vahdat, A. Mirage: A Microeconomic Resource Allocation System for SensorNet Testbeds. In Proceedings of the 2nd IEEE Workshop on Embedded Networked Sensors (May 2005).
• 4: Clarke, E. H. Multipart pricing of public goods. Public Choice 2 (1971), 19--33.
• 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: Groves, T. Incentives in Teams. Econometrica 41 (1973), 617--631.
• 7: Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988784]
• 8: Jackson, M. O. Mechanism Theory. In The Encyclopedia of Life Support Systems. EOLSS Publishers, 2000.
• 9: Lai, K., Huberman, B. A., and Fine, L. Tycoon: A Distributed Market-based Resource Allocation System. Tech. rep., Hewlett Packard, 2004.
• 10: Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
• 11: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
• 12: 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]
• 13: Chaki Ng , David C. Parkes , Margo Seltzer, Virtual worlds: fast and strategyproof auctions for dynamic resource allocation, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779977]
• 14: Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
• 15: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 16: 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]
• 17: Ori Regev , Noam Nisan, The POPCORN market—an online market for computational resources, Proceedings of the first international conference on Information and computation economies, p.148-157, October 25-28, 1998, Charleston, South Carolina, United States [doi>10.1145/288994.289027]
• 18: Varian, H., and MacKie-Mason, J. K. Generalized Vickrey auctions. Tech. rep., University of Michigan, 1995.
• 19: Vickrey, W. Counterspeculation, Auctions and Competitive Sealed Tenders. Journal of Finance (1961), 8--37.
• 20: Rich Wolski , James S. Plank , John Brevik , Todd Bryan, Analyzing Market-Based Resource Allocation Strategies for the Computational Grid, International Journal of High Performance Computing Applications, v.15 n.3, p.258-281, August 2001 [doi>10.1177/109434200101500305]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Design, Economics, Experimentation, Measurement

Keywords:
market-based systems, resource allocation, strategic behavior