home · mobile · calendar · colloquia · 2001-2002 · 

Colloquium - Singh

Electronic Commerce, Auctions, and Computational Game Theory: Some Results that Exploit Computational and Representational Restrictions on the Behavior of Agents
Syntek Capital

Multi-agent games are becoming an increasingly prevalent formalism for the study of electronic commerce and auctions. In order to act efficiently in such complex settings agents will adopt both representational and computational restrictions on their behavior (much as in the rest of artificial intelligence and machine learning). Computational game theory studies the impact of such restrictions on the outcome of games.

In this talk, I will present some of my recent work with colleagues at AT&T Labs in this area beginning with a motivating description of a trading-agent competition in which we participated. Following that, I will present a result that analyzes 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. I will show that surprisingly either the agents will converge to a Nash equilibrium, or if the strategies themselves do not converge, then their average payoffs will nevertheless converge to the payoffs of a Nash equilibrium. Finally, I will introduce a compact graph-theoretic representation for multi-party game theory and provide a provably correct and efficient algorithm for computing approximate Nash equilibria in (one-stage) games represented by trees or sparse graphs.

Hosted by Michael Mozer.
Refreshments will be served immediately following the talk in ECOT 831.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)