Abstract
We consider a class of games with real-valued strategies and payoff information available only in the form of data from a given sample of strategy profiles. Solving such games with respect to the underlying strategy space requires generalizing from the data to a complete payoff-function representation. We address payoff-function learning as a standard regression problem, with provision for capturing known structure (e.g., symmetry) in the multiagent environment. To measure learning performance, we consider the relative utility of prescribed strategies, rather than the accuracy of payoff functions per se. We demonstrate our approach and evaluate its effectiveness on two examples: a two-player version of the first-price sealed-bid auction (with known analytical form), and a five-player market-based scheduling game (with no known solution). Additionally, we explore the efficacy of using relative utility of strategies as a target of supervised learning and as a learning model selector. Our experiments demonstrate its effectiveness in the former case, though not in the latter.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Atkeson, C. G., Moore, A. W., & Schaal, S. (1997). Locally Weighted Learning., Artificial Intelligence Review, 11, 11–73.
Balder, E. J. (1996). Remarks on Nash equilibria for games with additively coupled payoffs. Economic Theory, 9(1), 161–167.
Brafman, R. I., & Tennenholtz, M. (2003). Learning to coordinate efficiently: A model-based approach. Journal of Artificial Intelligence Research, 19, 11–23.
Brafman, R. I., & Tennenholtz, M. (2004). Efficient Learning Equilibrium. Artificial Intelligence, 159, 27–47.
Cheng, S.-F., Reeves, D. M., Vorobeychik, Y., & Wellman, M. P. (2004). Notes on Equilibria in Symmetric Games. In AAMAS-04 Workshop on Game-Theoretic and Decision-Theoretic Agents. New York.
Cohn, D. A., Atlas, L., & Ladner, R. E. (1994). Improving Generalization with Active Learning. Machine Learning, 15(2), 201–221.
Cramton, P. (2005). Simultaneous ascending auctions. In P. Cramton, Y. Shoham, & R. Steinberg (Eds.), Combinatorial auctions. MIT Press.
Friedman, D. (1991). Evolutionary games in economics. Econometrica, 59, 637–666.
Fudenberg, D., & Levine, D. (1998). The Theory of Learning in Games. MIT Press.
Hastie, T., Tibshirani, R., & Friedman, J. (2001). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer.
Joachims, T. (1999). Making large-scale SVM learning practical. In B. Scholkopf, C. Burges, & A. Smola (Eds.), Advances in Kernel Methods—Support Vector Learning. MIT Press.
Kreps, D. M. (1990). Game Theory and Economic Modelling. Oxford University Press.
Krishna, V. (2002). Auction theory. Academic Press.
Mas-Colell, A., Whinston M. D., & Green J. R. (1995). Microeconomic theory. New York: Oxford University Press.
Milgrom, P. (2000). Putting auction theory to work: The simultaneous ascending auction. Journal of Political Economy, 108, 245–272.
Nash, J. (1951). Non-cooperative games. Annals of Mathematics, 54, 286–295.
Reeves, D. M. (2005). Generating Trading Agent Strategies. Ph.D. thesis, University of Michigan.
Reeves, D. M. & Wellman M. P. (2004). Computing Best-Response Strategies in Infinite Games of Incomplete Information. In Twentieth Conference on Uncertainty in Artificial Intelligence, (pp. 470–478).
Reeves, D. M., Wellman, M. P., MacKie-Mason, J. K., & Osepayshvili, A. (2005). Exploring Bidding Strategies for Market-Based Scheduling. Decision Support Systems, 39, 67–85.
Selten, R., & Buchta, J. (1994). Experimental Sealed Bid First Price Auctions with Directly Observed Bid Functions. Technical Report Discussion Paper B-270, University of Bonn.
Shoham, Y., Powers, R., & Grenager, T. (forthcoming), If multi-agent learning is the answer, what is the question? Artificial Intelligence.
Vapnik, V. (1995). The Nature of Statistical Learning Theory. Springer-Verlag.
Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16, 8–37.
Vorobeychik, Y., Wellman, M. P., & Singh, S. (2005). Learning Payoff Functions in Infinite Games. In Nineteenth International Joint Conference on Artificial Intelligence, (pp. 977–982).
Author information
Authors and Affiliations
Corresponding author
Additional information
Editors: Amy Greenwald and Michael Littman
Revised and extended version of a paper presented at IJCAI-05 (Vorobeychik, Wellman, & Singh, 2005).
Rights and permissions
About this article
Cite this article
Vorobeychik, Y., Wellman, M.P. & Singh, S. Learning payoff functions in infinite games. Mach Learn 67, 145–168 (2007). https://doi.org/10.1007/s10994-007-0715-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10994-007-0715-8