New (Practical) Complementary Pivot Algorithms for Market Equilibria
| Speaker: | Vijay Vazirani |
|---|---|
| Affiliation: | Georgia Tech |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
Complementary pivot algorithms, in the style of the simplex algorithm, tend to work well in practice despite having an exponential worst case behavior -- a case in point being the classic Lemke-Howson algorithm (1964) for 2-player Nash equilibrium. This algorithm also gives a direct proof of membership of the problem in the class PPAD and yields deep structural insights, such as oddness of the number of equilibria.
Our
first
result
accomplishes
all
of
the
above
for
the
problem
of
finding
an
equilibrium
for
an
Arrow-Debreu
market
under
separable,
piecewise
linear
concave
utilities.
Our
second
result
extends
this
to
markets
with
production.
Based
on
the
following
paper,
and
a
recent
joint
work
with
Jugal
Garg
and
Ruta
Mehta:
A
complementary
pivot
algorithm
for
market
equilibrium
under
separable,
piecewise-linear
concave
utilities
(PDF).