Date and Time

Monday, April 14, 2003 - 4:00pm to 5:30pm

Location

Computer Science Small Auditorium (Room 105)

Type

Colloquium

Speaker

Kevin Leyton-Brown [1], from Stanford University

Host

Kenneth Steiglitz

Website

The last few years have seen a surge of interest in problems
at the intersection between computer science and game theoretic
economics. Sometimes, practical use of game theoretic mechanisms
or solution concepts requires the application of ideas from computer
science; in other cases problems in computer systems can be best
addressed by the introduction of game theoretic incentives. Finally,
the influence between the disciplines can be more symmetric,
requiring a synthesized view of both computational limitations
and the self-interested behavior of agents. This talk will describe
one example of each of these three cases:

- modeling the empirical computational hardness of selecting the winners of a combinatorial auction, analyzing these models, and applying them to construct algorithm portfolios and to generate hard problem instances
- using incentives to diffuse temporally-focused usage of network resources at the lowest possible cost
- local-effect games, a novel class of multi-player general-sum games for which representation is compact, pure-strategy Nash equilibria often exist, and equilibria can often be computed efficiently