Algorithmic game theory

Combinatorics and Optimization (CO) 759: Topics in Discrete Optimization

Topic for winter 2015: algorithmic game theory

Instructor:

Chaitanya Swamy

Class time:

10:30am-12:00pm Tuesday/Thursday, Mathematics and Computer Building (MC) 6486

Algorithmic game theory applies algorithmic reasoning to game-theoretic
settings. A prototypical motivating example for the problems we will
consider is the Internet, which is a fascinating computational artifact in
that it was not designed by any one central authority, or optimized for
one specific purpose, but rather emerged from the interaction of several
entities, such as network operators, ISPs, users, in varying degrees of
coordination and competition. This course will investigate a variety of
questions that arise from looking at problems (often classical
optimization problems) from this point of view. We will examine, in part,
algorithmic issues in games, and in part, algorithmic problems that arise
in settings with strategic players.

Some subset of the following topics will be covered

Introduction to games and algorithms

Algorithmic Mechanism Design

The design of computationally tractable games (called mechanisms) whose equilibria are efficient. Topics include:

Social-choice functions: dominant-strategy incentive compatibility, Bayesian incentive compatibility; truthful mechanism design with various social-choice functions
Combinatorial auctions: social-welfare maximization and profit maximization
Cost-sharing mechanisms

(In)Efficiency of equilibria

Quantifying the efficiency-loss in game-versions of various optimization problems due to uncoordinated behavior. Examples include:

Network routing or congestion games: flow/traffic controlled by strategic agents is routed between source-sink pairs
Smoothness analysis of price of anarchy
Load balancing games, bandwidth sharing games