Group-Strategy Proof Mechanisms for Network Design Games
| Speaker: | Jochen Könemann |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
About
15
years
ago,
Goemans
and
Williamson
formally
introduced
the
primal-dual
framework
for
approximation
algorithms
and
applied
it
to
a
class
of
network
design
optimization
problems.
Since
then
literally
hundreds
of
results
appeared
that
extended,
modified
and
applied
the
technique
to
a
wide
range
of
optimization
problems.
In
this
talk
we
define
a
class
of
cost-sharing
games
arising
from
Goemans'
and
Williamson's
original
network
design
problems.
We
then
show
how
to
derive
a
group-strategyproof
(
i.e.,
collusion
resistant)
mechanism
for
such
a
game
from
an
existing
primal-dual
algorithm
for
the
underlying
optimization
problem.
We
further
show
that
the
budget-balance
factor
of
the
resulting
mechanism
is
proportional
to
the
performance
ratio
of
the
primal-dual
algorithm
if
the
optimization
problem
satisfies
an
additional
technical
condition.
Joint work with S. Leonardi, G. Schaefer and D. Wheatley.