Achieving target equilibria in network routing games without knowing the latency functions
| Speaker: | Umang Bhaskar |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5479 |
Abstract:
Network
routing
games
are
game-theoretic
models
of
traffic
in
networks.
In
a
network
routing
game,
each
agent
picks
a
route
from
its
source
to
its
destination
in
the
network
to
minimize
its
latency,
where
the
latency
on
each
edge
depends
on
the
population
of
agents
that
use
the
edge.
Properties
of
equilibrium
in
network
routing
games
are
well-studied.
In
particular,
we
can,
in
polynomial
time,
compute
tolls
on
the
edges
of
the
network
to
induce
any
given
target
flow
as
the
equilibrium.
This
approach
however
assumes
precise,
detailed
information
about
the
underlying
edge
latency
functions,
which
may
be
unavailable
and
difficult
to
obtain.
We
study
whether
one
can
induce
a
given
target
flow
as
the
equilibrium
in
a
network
routing
game
without
knowing
the
underlying
latency
functions.
We
give
a
positive
answer
to
this
question,
showing
that,
under
fairly
general
settings,
we
can
efficiently
compute
edge
tolls
that
induce
a
given
target
flow
as
the
equilibrium
with
a
polynomial
number
of
queries
to
an
oracle.
The
oracle
takes
candidate
tolls
as
input,
and
returns
the
induced
equilibrium
flow.
We
obtain
this
result
via
a
novel
application
of
the
ellipsoid
method.
We
give
tighter
bounds
on
the
query
complexity
for
a
number
of
special
cases.
This
is
joint
work
with
Katrina
Ligett,
Leonard
J.
Schulman,
and
Chaitanya
Swamy.