Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Nash Convergence of Gradient Dynamics in Iterated General-Sum Games
Satinder Singh, Michael Kearns, Yishay Mansour
Abstract:
Multi-agent games are becoming an increasing prevalent formalism for the study of electronic commerce and auctions. The speed at which transactions can take place and the growing complexity of electronic marketplaces makes the study of computationally simple agents an appealing direction. In this work, we analyze the behavior of agents that incrementally adapt their strategy through gradient ascent on expected payoff, in the simple setting of two-player, two-action, iterated general-sum games, and present a surprising result. We show that either the agents will converge to Nash equilibrium, or if the strategies themselves do not converge, then their average payoffs will nevertheless converge to the payoffs of a Nash equilibrium.
Keywords:
Pages: 541-548
PS Link:
PDF Link: /papers/00/p541-singh.pdf
BibTex:
@INPROCEEDINGS{Singh00,
AUTHOR = "Satinder Singh and Michael Kearns and Yishay Mansour",
TITLE = "Nash Convergence of Gradient Dynamics in Iterated General-Sum Games",
BOOKTITLE = "Proceedings of the Sixteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-00)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2000",
PAGES = "541--548"
}


hosted by DSL   •   site info   •   help