Empirical game-theoretic analysis of the TAC Supply Chain game

ABSTRACT

The TAC Supply Chain Management (TAC/SCM) game presents a challenging dynamic environment for autonomous decision-making in a salient application domain. Strategic interactions complicate the analysis of games such as TAC/SCM. since the effectiveness of a given strategy depends on the strategies played by other agents on the supply chain. The TAC tournament generates results from one particular path of combinations, and success in the tournament is rightly regarded as evidence for agent quality. Such results along with post-competition controlled experiments provide useful evaluations of novel techniques employed in the game. We argue that a broader game-theoretic analysis framework can provide a firmer foundation for choice of experimental contexts. Exploiting a repository of agents from the 2005 and 2006 TAC/SCM tournaments, we demonstrate an empirical game-theoretic methodology based on extensive simulation and careful measurement. Our analysis of agents from TAC-05 reveals interesting interactions not seen in the tournament. Extending the analysis to TAC-06 enables us to measure progress from year-to-year, and generates a candidate empirical equilibrium among the best known strategies. We use this equilibrium as a stable background population for comparing relative performance of the 2006 agents, yielding insights complementing the tournament results.

REFERENCES

• 1: R. Arunachalam and N. M. Sadeh. The supply chain trading agent competition. Electronic Commerce Research and Applications, 4:63--81, 2005.
• 2: R. Axelrod. The Evolution of Cooperation. Basic Books, 1984.
• 3: J. Collins, R. Arunachalam, N. Sadeh, J. Eriksson, N. Finne, and S. Janson. The Supply Chain Management Game for the 2005 Trading Agent Competition. Technical Report CMU-ISRI-04-139, Carnegie Mellon University, 2004.
• 4: Joakim Eriksson , Niclas Finne , Sverker Janson, Evolution of a supply chain management game for the trading agent competition, AI Communications, v.19 n.1, p.1-12, January 2006
• 5: D. Friedman. Evolutionary games in economics. Econometrica, 59:637--666, 1991.
• 6: Minghua He , Alex Rogers , Xudong Luo , Nicholas R. Jennings, Designing a successful trading agent for supply chain management, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160843]
• 7: Christopher Kiekintveld , Jason Miller , Patrick R. Jordan , Michael P. Wellman, Controlling a supply chain agent using value-based decomposition, Proceedings of the 7th ACM conference on Electronic commerce, p.208-217, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134730]
• 8: C. Kiekintveld, Y. Vorobeychik, and M. P. Wellman. An Analysis of the 2004 Supply Chain Management Trading Agent Competition. In IJCAI-05 Workshop on Trading Agent Design and Analysis, 2005.
• 9: I. Kontogounis, K. C. Chatzidimitriou, A. L. Symeonidis, and P. A. Mitkas. A robust agent design for dynamic SCM environments. In Fourth Hellenic Conference on Artificial Intelligence, Heraklion, Greece, 2006.
• 10: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 11: D. Pardoe and P. Stone. Predictive planning for supply chain management. In Sixteenth International Conference on Automated Planning and Scheduling, Cumbria, UK, 2006.
• 12: D. Pardoe and P. Stone. TacTex-05: A champion supply chain management agent. In Twenty-First National Conference on Artificial Intelligence, pages 1489--1494, Boston, 2006.
• 13: S. Phelps , M. Marcinkiewicz , S. Parsons, A novel method for automatic strategy acquisition in N-player non-zero-sum games, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160760]
• 14: Daniel M. Reeves , Michael P. Wellman, Generating trading agent strategies: analytic and empirical methods for infinite and large games, University of Michigan, Ann Arbor, MI, 2005
• 15: Sheldon M. Ross, Simulation, Academic Press, Inc., Orlando, FL, 2002
• 16: P. Taylor and L. Jonker. Evolutionary stable strategies and game dynamics. Mathematical Biosciences, 40:145--156, 1978.
• 17: Leigh Tesfatsion, Agent-based computational economics: modeling economies as complex adaptive systems, Information Sciences—Informatics and Computer Science: An International Journal, v.149 n.4, p.263-269, February 2003
• 18: Yevgeniy Vorobeychik , Christopher Kiekintveld , Michael P. Wellman, Empirical mechanism design: methods, with application to a supply-chain scenario, Proceedings of the 7th ACM conference on Electronic commerce, p.306-315, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134741]
• 19: W. Walsh, D. Parkes, and R. Das. Choosing samples to compute heuristic-strategy Nash equilibrium. In Fifth Workshop on Agent-Mediated Electronic Commerce, 2003.
• 20: M. P. Wellman, J. Estelle, S. Singh, Y. Vorobeychik, C. Kiekintveld, and V. Soni. Strategic Interactions in a Supply Chain Game. Computational Intelligence, 21:1--26, 2005.
• 21: M. P. Wellman, D. M. Reeves, K. M. Lochner, S.-F. Chen, and R. Suri. Approximate Strategic Reasoning through Hierarchical Reduction of Large Symmetric Games. Twentieth National Conference on Artificial Intelligence, pages 502--508, 2005.
• 22: TAC Team , Michael P. Wellman , Peter R. Wurman , Kevin O'Malley , Roshan Bangera , Shou-de Lin , Daniel Reeves , William E. Walsh, Designing the Market Game for a Trading Agent Competition, IEEE Internet Computing, v.5 n.2, p.43-51, March 2001 [doi>10.1109/4236.914647]

INDEX TERMS

General Terms:
Economics, Experimentation, Measurement

Keywords:
electronic markets, empirical game theory, multiagent systems, supply chain management, trading agent competition