skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · colloquia · 2001-2002 · 

Colloquium - Singh

ECCR 265

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

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.

The Department holds colloquia throughout the Fall and Spring semesters. These colloquia, open to the public, are typically held on Thursday afternoons, but sometimes occur at other times as well. If you would like to receive email notification of upcoming colloquia, subscribe to our Colloquia Mailing List. If you would like to schedule a colloquium, see Colloquium Scheduling.

Sign language interpreters are available upon request. Please contact Stephanie Morris at least five days prior to the colloquium.

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:29)