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
Computational aspects of equilibria
- Existence, complexity, and algorithmic aspects of Nash equilibria
- Correlated equilibria and their computation
- Markets and the computation of market equilibria