Exploring bidding strategies for market-based scheduling

ABSTRACT

A market-based scheduling mechanism allocates resources indexed by time to alternative uses based on the bids of participating agents. Agents are typically interested in multiple time slots of the schedulable resource, with value determined by the earliest deadline by which they can complete their corresponding tasks. Despite the strong complementarities among slots induced by such preferences, it is often infeasible to deploy a mechanism that coordinates allocation across all time slots. We explore the case of separate, simultaneous markets for individual time slots, and the strategic problem it poses for bidding agents. Investigation of the straightforward bidding policy and its variants indicates that the efficacy of particular strategies depends critically on preferences and strategies of other agents, and that the strategy space is far too complex to yield to general game-theoretic analysis. For particular environments, however, it is often possible to derive constrained equilibria through evolutionary search methods.

REFERENCES

• 1: P. Bertsekas. Auction algorithms for network flow problems: A tutorial introduction. Computational Optimization and Applications, 1:7--66, 1992.
• 2: S. Bikhchandani and J. W. Mamer. Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory, 74:385--413, 1997.
• 3: William T. Scherer , Donald E. Brown, Intelligent Scheduling Systems, Kluwer Academic Publishers, Norwell, MA, 1995
• 4: D. Cliff. Evolving parameter sets for adaptive trading agents in continuous double-auction markets. In Agents-98 Workshop on Artificial Societies and Computational Markets, pages 38--47, Minneapolis, MN, May 1998.
• 5: D. Cliff. Evolution of market mechanism through a continuous space of auction-types II: Two-sided auction mechanisms evolve in response to market shocks. In Agents for Business Automation, Las Vegas, June 2002.
• 6: 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]
• 7: G. Demange, D. Gale, and M. Sotomayor. Multi-item auctions. Journal of Political Economy, 94:863--872, 1986.
• 8: D. Friedman. Evolutionary games in economics. Econometrica, 59:637--666, 1991.
• 9: F. Gul and E. Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87:95--124, 1999.
• 10: S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68:1127--1150, 2000.
• 11: A. S. Kelso and V. P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50:1483--1504, 1982.
• 12: Jeffrey O. Kephart , James E. Hanson , Jakka Sairamesh, Price and niche wars in a free-market economy of software agents, Artificial Life, v.4 n.1, p.1-23, Nov. 1997 [doi>10.1162/106454698568413]
• 13: P. D. Klemperer. Auction theory: A guide to the literature. Journal of Economic Surveys, 13:227--286, 1999.
• 14: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, New York, 1995.
• 15: R. P. McAfee and J. McMillan. Analyzing the airwaves auction. Journal of Economic Perspectives, 10(1):159--175, 1996.
• 16: R. D. McKelvey and A. McLennan. Computation of equilibria in finite games. In Handbook of Computational Economics, volume 1. Elsevier, 1996.
• 17: R. D. McKelvey, A. McLennan, and T. Turocy. Gambit game theory analysis software and tools, 1992. urlhttp://econweb.tamu.edu/gambit.
• 18: P. Milgrom. Putting auction theory to work: The simultaneous ascending auction. Journal of Political Economy, 108:245--272, 2000.
• 19: J. Nash. Non-cooperative games. PhD thesis, Princeton University, Department of Mathematics, 1950.
• 20: J. A. Nelder and R. Mead. A simplex method for function minimization. Computer Journal, 7:308--313, 1965.
• 21: J. Nicolaisen, V. Petrov, and L. Tesfatsion. Market power and efficiency in a computational electricity market with discriminatory double-auction pricing. IEEE Transactions on Evolutionary Computation, 5:504--523, 2001.
• 22: M. Peters and S. Severinov. Internet auctions with many traders. Technical report, University of Toronto, 2001.
• 23: S. Phelps, S. Parsons, P. McBurney, and E. Sklar. Co-evolution of auction mechanisms and trading strategies: Towards a novel approach to microeconomic design. In GECCO-02 Workshop on Evolutionary Computation in Multi-Agent Systems, pages 65--72, 2002.
• 24: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, New York, NY, 1992
• 25: T. C. Price. Using co-evolutionary programming to simulate strategic behaviour in markets. Journal of Evolutionary Economics, 7:219--254, 1997.
• 26: P. Schuster and K. Sigmund. Replicator dynamics. Journal of Theoretical Biology, 100:533--538, 1983.
• 27: P. Taylor and L. Jonker. Evolutionary stable strategies and game dynamics. Mathematical Biosciences, 40:145--156, 1978.
• 28: W. E. Walsh, R. Das, G. Tesauro, and J. O. Kephart. Analyzing complex strategic interactions in multi-agent systems. In AAAI-02 Workshop on Game-Theoretic and Decision-Theoretic Agents, Edmonton, 2002.
• 29: J. W. Weibull. Evolutionary Game Theory. MIT Press, 1995.
• 30: M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 35:271--303, 2001.
• 31: K. P. White. Advances in the theory and practice of production scheduling. In C. T. Leondes, editor, Advances in Control and Dynamic Systems, pages 115--157. Academic Press, 1990.

INDEX TERMS

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

General Terms:
Algorithms, Economics, Experimentation

Keywords:
Nash equilibrium, bidding strategies, evolutionary game theory, evolutionary search, market-based scheduling, replicator dynamics, simultaneous ascending auctions