Bureaucrats, editor, Administrators
373
edits
Changes
→Abstract
Line 22:
Line 22:
Suppose we are given n buckets with varying integral sizes, and+wish to fill some fraction alpha of them will balls, with a bucket+to minimize the number of balls used.+If we know the sizes of the buckets, this is a trivial problem:+Just identify the (alpha)n smallest buckets, and fill them.+But what if we do not know the sizes of the buckets in advance,+and after each ball placement only find out whether the bucket+is now full or not?+This problem models a cryptographic question. Suppose an adversary+wishes to prevent a multiparty protocol from succeeding. Typically+with such protocols, the adversary need only corrupt half (or a third)+of the parties to attain its goal. But suppose each party is protected+by a sequence of some number of cryptographic walls, each of which+requires a certain amount of computation to break through. If parties+have differing numbers of walls, and the adversary does not know how+many walls a given party has until it breaks through the last one,+we get our balls-and-buckets problem.
−This cryptographic connection is formalized in a paper I've written+with Juan Garay, Aggelos Kiayis, and Moti Yung. Here I will concentrate+on the combinatorial side, giving algorithms for the adversary (bucket+filler) in the presence various levels of partial information about the+sizes, and near-matching lower bounds on what is possible, both for+deterministic and randomized algorithms. I also address the question+building) in the hidden diversity setting.+
+
== Abstract ==
== Abstract ==
−Network routing games are instrumental in understanding
−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
−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
−of how a system-designer can best spend his security dollars (in wall
+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