Theory

Changes

CATS-Apr-19-2013 (view source)

Revision as of 19:05, 15 April 2013

69 bytes removed ,  19:05, 15 April 2013
→‎Title
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
Retrieved from "https://wiki.cs.umd.edu/theory/view/Special:MobileDiff/1675...1679"