Theory

Changes

CATS-Apr-19-2013 (view source)

Revision as of 19:04, 15 April 2013

435 bytes added ,  19:04, 15 April 2013
→‎Abstract
Line 22: Line 22:     
== 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/1676"