Resource Competition on Matroids
| Speaker: | Britta Peis |
|---|---|
| Affiliation: | RWTH Aachen University |
| Room: | M3 3103 |
Abstract:
Congestion
games
are
widely
used
to
model
and
analyse
the
behaviour
of
selfish
acting
uncontrolled
individuals
competing
over
a
commonly
used
set
of
resources.
A
typical
example
of
congestion
games
can
be
observed
every
day
at
rush
hour
in
a
congested
city:
each
individual
car
driver
chooses
a
route
through
a
street
network.
The
travel
time
of
each
of
the
streets
("resources")
in
use
highly
depends
on
the
congestion
caused
by
the
route
choices
of
the
other
car
drivers.
A
stable
state
("equilibrium")
is
reached
if
none
of
the
individuals
can
improve
its
outcome
by
unilateral
switching
to
an
alternative
route
("strategy").
The
famous
Braess
paradox
describes
the
interesting
phenomenon
that
improving
the
network
infrastructure,
for
example
by
building
new
streets,
may
in
fact
lead
to
higher
travel
times
under
an
equilibrium.
Game
theory
now
investigates
under
which
conditions
equilibria
exist,
are
efficient,
and
admit
a
Braess
paradox.
As
it
turns
out,
structural
properties
and
algorithmic
techniques
from
combinatorial
optimization
can
be
extremely
helpful
for
such
investigations.
For
example,
as
will
be
shown
in
the
talk,
matroids
are
the
only
structures
that
are
immune
to
Braess
paradox,
and
that
guarantee
the
existence
of
equilibria
for
several
variants
of
congestion
games.
(Joint
work
with
Tobias
Harks.)