Theory

Difference between revisions of "CATS-Apr-19-2013"

 
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Title ==
 
== Title ==
−
The Combinatorics of Hidden Diversity
+
Risk in network routing games
  
 
== Speaker ==
 
== Speaker ==
−
David Johnson is Head of the Algorithms and Optimization Department
+
Evdokia Nikolova is an Assistant Professor at the Computer Science &
−
at AT&T Labs-Research in Florham Park, NJ, and has been a researcher
+
Engineering Department at Texas A&M University. Previously she was a
−
at the Labs (in its many incarnations) since 1973, when he received his
+
postdoctoral associate in the Computer Science and Artificial
−
PhD from MIT. He is perhaps best known as the co-author of COMPUTERS
+
Intelligence Laboratory at MIT. She graduated with a BA in Applied
−
AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which
+
Mathematics with Economics from Harvard University, MS in Mathematics
−
he and his co-author M. R. Garey won the INFORMS Lanchester Prize.
+
from Cambridge University (U.K.) and Ph.D. in Computer Science from
−
His research interests include approximation algorithms for combinatorial
+
MIT. She is interested in risk analysis from an algorithmic
−
problems, a subject on which he had several of the first key papers,
+
perspective arising in stochastic optimization, networks, economics
−
starting with his PhD thesis on the infamous "bin packing" problem.
+
and complex systems.  She has worked on applications to transportation
−
In recent years he has become a leader in the experimental analysis of
+
and is also interested in energy and other domains where her work may
−
algorithms, and has been the creator and lead organizer for the series
+
apply.
−
of DIMACS Implementation Challenges, covering topics from Network Flows
 
−
to the Traveling Salesman Problem.  He also founded the ACM-SIAM
 
−
Symposium on Discrete Algorithms (SODA), and served as its Steering
 
−
Committee Chair for its first 23 years.  He is an ACM Fellow, a SIAM
 
−
Fellow, an AT&T Fellow, and the winner of the 2010 Knuth Prize for
 
−
outstanding contributions to the foundations of computer science.
 
  
 
== Abstract ==
 
== Abstract ==
−
Suppose we are given n buckets with varying integral sizes, and
+
Network routing games are instrumental in understanding
−
wish to fill some fraction alpha of them will balls, with a bucket
+
traffic patterns and improving congestion in networks.  They have a
−
of size k being filled as soon as it receives k balls. Our goal is
+
direct application in transportation and telecommunication networks
−
to minimize the number of balls used.
+
and extend to many other applications such as task planning, etc.
 +
Theoretically, network games were one of the central examples in the
 +
development of algorithmic game theory.
  
−
If we know the sizes of the buckets, this is a trivial problem:
+
In these games, multiple users need to route between di fferent
−
Just identify the (alpha)n smallest buckets, and fill them.
+
source-destination pairs and links are congestible, namely, each link
−
But what if we do not know the sizes of the buckets in advance,
+
delay is a non-decreasing function of the flow on the link. Many of
−
and after each ball placement only find out whether the bucket
+
the fundamental game theoretic questions are now well understood for
−
is now full or not?
+
these games, for example, does equilibrium exist, is it unique, can it
 +
be computed e fficiently, does
 +
it have a compact representation; the same questions can be asked of
 +
the socially optimal solution that minimizes the total user delay.
  
−
This problem models a cryptographic question. Suppose an adversary
+
So far, most research has focused on the classical models in which the
−
wishes to prevent a multiparty protocol from succeeding. Typically
+
link delays are deterministic. In contrast, real world applications
−
with such protocols, the adversary need only corrupt half (or a third)
+
contain a lot of uncertainty, which may stem from exogenous factors
−
of the parties to attain its goal. But suppose each party is protected
+
such as weather, time of day, weekday versus weekend, etc. or
−
by a sequence of some number of cryptographic walls, each of which
+
endogenous factors such as the network tra ffic. Furthermore, many
−
requires a certain amount of computation to break through. If parties
+
users are risk-averse in the presence of uncertainty, so that they do
−
have differing numbers of walls, and the adversary does not know how
+
not simply want to minimize expected delays and instead may need to
−
many walls a given party has until it breaks through the last one,
+
add a bu ffer to ensure a guaranteed arrival time to a destination.
−
we get our balls-and-buckets problem.
 
  
−
This cryptographic connection is formalized in a paper I've written
+
I present my recent work on a new stochastic network game model with
−
with Juan Garay, Aggelos Kiayis, and Moti Yung. Here I will concentrate
+
risk-averse users.  Risk-aversion poses a computational challenge and
−
on the combinatorial side, giving algorithms for the adversary (bucket
+
it often fundamentally alters the mathematical structure of the game
−
filler) in the presence various levels of partial information about the
+
compared to its deterministic counterpart, requiring new tools for
−
sizes, and near-matching lower bounds on what is possible, both for
+
analysis.  The talk will discuss best response and equilibrium
−
deterministic and randomized algorithms.  I also address the question
+
analysis, as well as equilibrium efficiency (price of anarchy) and a
−
of how a system-designer can best spend his security dollars (in wall
+
new concept, the price of risk.
−
building) in the hidden diversity setting.
+
 
 +
One relevant paper is here:
 +
http://faculty.cse.tamu.edu/nikolova/papers/Stochastic-selfish-routing-full.pdf
 +
 
 +
A short summary of the paper is here:
 +
http://www.sigecom.org/exchanges/volume_11/1/NIKOLOVA.pdf

Latest revision as of 19:05, 15 April 2013

Title

Risk in network routing games

Speaker

Evdokia Nikolova is an Assistant Professor at the Computer Science & Engineering Department at Texas A&M University. Previously she was a postdoctoral associate in the Computer Science and Artificial Intelligence Laboratory at MIT. She graduated with a BA in Applied Mathematics with Economics from Harvard University, MS in Mathematics from Cambridge University (U.K.) and Ph.D. in Computer Science from MIT. She is interested in risk analysis from an algorithmic perspective arising in stochastic optimization, networks, economics and complex systems. She has worked on applications to transportation and is also interested in energy and other domains where her work may apply.

Abstract

Network routing games are instrumental in understanding traffic patterns and improving congestion in networks. They have a direct application in transportation and telecommunication networks and extend to many other applications such as task planning, etc. Theoretically, network games were one of the central examples in the development of algorithmic game theory.

In these games, multiple users need to route between di fferent source-destination pairs and links are congestible, namely, each link delay is a non-decreasing function of the flow on the link. Many of the fundamental game theoretic questions are now well understood for these games, for example, does equilibrium exist, is it unique, can it be computed e fficiently, does it have a compact representation; the same questions can be asked of the socially optimal solution that minimizes the total user delay.

So far, most research has focused on the classical models in which the link delays are deterministic. In contrast, real world applications contain a lot of uncertainty, which may stem from exogenous factors such as weather, time of day, weekday versus weekend, etc. or endogenous factors such as the network tra ffic. Furthermore, many users are risk-averse in the presence of uncertainty, so that they do not simply want to minimize expected delays and instead may need to add a bu ffer to ensure a guaranteed arrival time to a destination.

I present my recent work on a new stochastic network game model with risk-averse users. Risk-aversion poses a computational challenge and it often fundamentally alters the mathematical structure of the game compared to its deterministic counterpart, requiring new tools for analysis. The talk will discuss best response and equilibrium analysis, as well as equilibrium efficiency (price of anarchy) and a new concept, the price of risk.

One relevant paper is here: http://faculty.cse.tamu.edu/nikolova/papers/Stochastic-selfish-routing-full.pdf

A short summary of the paper is here: http://www.sigecom.org/exchanges/volume_11/1/NIKOLOVA.pdf

Web Accessibility

Retrieved from "https://wiki.cs.umd.edu/theory/w/index.php?title=CATS-Apr-19-2013&oldid=1679"