| Erdös Magic for Algorithms and Games
24-29 April 2005 |
 |
|---|
| Erdös Magic for Algorithms and Games
24-29 April 2005 |
|
|---|
The goal of the workshop is to bring together researchers from various areas related to the application of the probabilistic method. This includes such topics as such as probabilistic combinatorics, (probabilistic) games, discrepancy and randomized algorithms. We plan to have ample time for discussions and joint work.
Monday, 25th
| 7:00 - 9:00 | Breakfast | |
| 9:40 - 10:30 |
Tic-Tac-Toe like games Jozsef Beck |
|
| 10:30 | Coffee | |
| 11:00 - 11:30 |
Liar games over an arbitrary channel Ioana Dumitriu |
|
| 11:35 - 12:05 |
Positional Games on random graphs Milos Stojakovic |
|
| 12:30 | Lunch | |
| 15:30 |
Afternoon Coffee |
|
| 16:15 - 16:55 |
Selfish Multicast Routing Lasse Kliemann |
|
| 17:00 - 17:30 |
Selfish Routing with Incomplete Information Martin Gairing |
|
| 17:35 - 18:05 |
The Fully Mixed Nash Equilibrium Conjecture (and Supermarket Queing) Andreas Baltz |
|
| 19:30 |
Dinner |
|
Tuesday, 26th
| 7:00 - 9:00 | Breakfast | |
| 9:40 - 10:30 |
Large girth regular graphs versus random regular
graphs Nick Wormald |
|
| 10:30 | Coffee | |
| 11:00 - 11:30 |
Random constraint satisfaction problems Michael Molloy |
|
| 11:35 - 12:05 |
Planar subgraphs in dense graphs, sparse random graphs and random graph processes Anusch Taraz |
|
| 12:30 | Lunch | |
| 15:30 |
Afternoon Coffee |
|
| 16:15 - 16:45 |
How many queries does it take to decide if there's a percolating cluster? David Bruce Wilson |
|
| 16:55 - 17:25 |
Optimal Group Testing Algorithms with Interval Queries and Their Application to Slice Site Detection Ferdinando Cicalese |
|
| 17:30 - 18:00 |
A Separation Theorem in Property Testing Asaf Shapira |
|
| 19:30 | Dinner | |
Wednesday, 27th
| 7:00 - 9:00 | Breakfast | |
| 9:40 - 10:30 |
Lifts of Graphs Nati Linial |
|
| 10:30 | Coffee | |
| 11:00 - 11:30 |
A Sophisticated Solution to an Elementary Problem Devdatt Dubhashi |
|
| 11:35 - 12:05 |
Balls-in-Bins with feedback and Brownian motion Roberto Oliveira |
|
| 12:30 | Lunch | |
| 15:30 |
Afternoon Coffee |
|
| 19:30 | Dinner | |
Thursday, 28th
| 7:00 - 9:00 | Breakfast | |
| 9:40 - 10:30 |
The game of JumbleG Michael Krivelevich |
|
| 10:30 | Coffee | |
| 11:00 - 11:30 |
On Avoider-Enforcer Games Dan Hefetz |
|
| 11:35 - 12:05 |
Random walk on oriented hypercubes Tibor Szabo |
|
| 12:30 | Lunch | |
| 15:30 |
Afternoon Coffee |
|
| 16:15 - 16:45 |
Discrepancy of Arithmetic Structures Nils Hebbinghaus |
|
| 16:55 - 17:25 |
Discretisation of Discrepancy and Applications Michael Gnewuch |
|
| 17:30 - 18:00 |
Randomized Rounding: Binary Reductions Make Life
Easy Benjamin Doerr |
|
| 19:30 | Dinner | |
Friday, 29th
| 7:00 - 9:00 | Breakfast | |
| 9:40 - 10:30 |
Exact values of infinitely many game numbers Jozsef Beck |
|
| 10:30 | Coffee | |
| 11:00 - 11:30 |
Planar Multi-Depot TSP for Random Points Anand Srivastav |
|
| 11:35 - 12:05 |
Generalized Turan Theorem Jozef Skokan |
|
| 12:30 | Lunch and End of the Workshop | |
| Arrival: | Sunday 24 April, 2005 |
|---|---|
| Departure: | Friday 29 April, 2005 |
Bertinoro itself is picturesque, with many narrow streets and walkways winding around the central peak. From the fortress you can enjoy a beautiful the vista that stretches from the Tuscan Apennines to the Adriatic coast.
Gairing, Lücking, Mavronicolas, Monien, and Spirakis (2003)
conjectured that
the worst Nash equilibrium (with respect to social cost) in the
Koutsoupias/Papadimitriou model of selfish routing games is a fully mixed one,
where every player chooses every edge with positive probability. We prove
that the conjecture asymptotically holds for a special case related to the
worst queing strategy for shopping in a supermarket.
This is joint work with Anand Srivastav.
There are two main subjects that I can talk about. The first subject is: ``What can a player build (but not necessarily first!)?''
The second subject is: ``Exact values of infinitely many game numbers''.
I begin with mentioning a new lower bound for the Hales-Jewett number HJ(n)
in Ramsey theory; this leads to multi-dimensional Tic-Tac-Toe; and
finally I discuss ``exact solutions''.
The material covered by the talk is part of joint works with
Peter Damaschke, Libertad Tansini, Soeren Werth, Ugo Vaccaro.
We show that the general problem of generating and derandomizing
randomized roundings with cardinality constraints can be reduced to the
problem for 0, 1/2 vectors. Once we have this reduction, it is easy to
generate Srinivasan's (FOCS 2001) randomized roundings on level sets and
Gandhi et al.'s (FOCS 2002) degree preserving edge weight roundings.
However, and often this has nothing to do with the way one generates
randomized roundings with constraints, one has to be careful. A number of
natural conditions that are satisfied by independent randomized
roundings are not valid anymore for randomized roundings that respect some
cardinality constraints.
We give a proof of natural correlation inequalities in certain
models of "Balls and Bins" using a coupling of Markov chains.
We consider a variant of the Renyi-Ulam liar game, in which
one of n possibilities must be guessed, t-ary questions are asked, and
the responder may lie at most k times. As an additional constraint,
there is an arbitrary (but prescribed) list of permissible types of lies
(the channel). For fixed t, k, and channel, we determine exact
asymptotics of the number n of possibilities we can distinguish between,
in terms of the number q of queries (which we let go to infinity).
We will present our results both for a completely online version of the
game (in which each query depends on all past queries), and for a
two-batch version (in which the questioneer asks one full batch of
questions offline, receives all answers, and then asks a second and
final batch of questions offline). We will show that, though the second
version is more restrictive, the effect of this restriction is
asymptotically negligible. We will also give an explicit strategy for the
two-batch version of the game.
This is joint work with Joel Spencer.
In his seminal work Harsanyi [Har67] introduced an elegant approach to
study non-cooperative games with incomplete information where the
players are uncertain about some parameters.
To model such games he introduced the Harsanyi transformation, which
converts a game with incomplete information to a strategic game where
players may have different types. In the resulting Bayesian game
players' uncertainty about each others types is described by a
probability distribution over all possible type profiles.
In this work, we introduce a particular selfish routing game with
incomplete information that we call Bayesian routing game. Here, n
selfish users wish to assign their traffic to one of m parallel links.
Users do not know each others traffic. Following Harsanyi's approach, we
introduce for each user a set of possible types.
This paper presents a comprehensive collection of results for the
Bayesian routing game.
We prove, with help of a potential function, that every Bayesian
routing game possesses a pure Bayesian Nash equilibrium. For the model
of identical links and independent type distribution we give a
polynomial time algorithm to compute a pure Bayesian Nash equilibrium.
We study structural properties of fully mixed Bayesian Nash equilibria
for the model of identical links and show that they maximize individual
cost. In general there exists more than one fully mixed Bayesian Nash
equilibrium. We characterize the class of fully mixed Bayesian Nash
equilibria in the case of independent type distribution.
We conclude with results on coordination ratio for the model of
identical links for three social cost measures, that is, social cost as
maximum expected congestion, sum of individual costs and maximum
individual cost. For the latter two we are able to give (asymptotic)
tight bounds using our results on fully mixed Bayesian Nash equilibria.
This is joint work with Burkhard Monien and Karsten Tiemann.
We give upper and lower bounds for the bracketing
number of axis-parallel boxes in the d-dimensional
unit cube. The constructive upper bounds lead to some
kind of
discretisation of the L∞-discrepancy.
As an application we get probabilistic upper bounds for
the L∞-star and L∞-extreme discrepancy
with the optimal behaviour in the dimension d and with
explicitly given small constants.
Point configurations satisfying our bounds can be computed
with a derandomized algorithm.
Another application is the computation of the discrepancy
of a given n-point configuration in the
d-dimensional unit cube up to some admissible error δ.
Lower bounds for the discrepancy of hypergraphs that are related to
the classical hypergraph of arithmetic progressions are the topic of
this talk. We consider the hypergraphs of arithmetic progressions in
Zp, of Bohr sets in Zp and of
higher-dimensional arithmetic progressions with common difference. For
the calculation of these lower bounds we use Fourier analysis and
generate a tool that is also usefull for determining lower bounds for
other hypergraphs.
Let p and q be positive integers and let H be a
hypergraph. In a (p,q,H) Avoider-Enforcer game two
players, called Avoider and Enforcer, take turns selecting
previously unclaimed vertices of H. Avoider selects p
vertices per move and Enforcer selects q vertices per move.
Avoider loses if he claims all the vertices of some hyperedge of
H, otherwise Enforcer loses. We prove a sufficient
condition for Avoider to win the (p,q,H) game, and use it
to analyze several classic games - connectivity, hamiltonicity and perfect
matching. Some of our results are quite surprising as they differ from those
obtained for the analogous Maker-Breaker games.
Joint work with Michael Krivelevich and Tibor Szabo.
Selfish routing is about networks that are shared by a number of selfish users
(also called players). A selfish player is one that tries to minimize
some form of individual cost, while disregarding the costs experienced by other
players (and hence disregarding the total cost). Usually, the cost is measured
in terms of latency. The basic concept for the analysis of such scenarios is
Nash equlibrium. This is a set of routing decisions such that no
player has an incentive to unilaterally deviate from his current decision. To
quantify the loss of performance due to selfish behavior, we introduce the
price of anarchy. This is the ratio between the cost of a worst-case
Nash equlilibrium and the cost of an optimal flow.
Selfish routing has very well been studied in a unicast setup, i.e., where we
associate with each source exactly one terminal. Roughgarden showed that
--- from a worst-case point of view --- the price of anarchy is independent of
the network topology.
Our focus now is on multicast routing. I.e., we associate with each source a
number of terminals. Routing is done along a collection of paths, each of the
paths connecting the source with one of the terminals. Such a collection will
be called a strategy. We distinguish multicast with
conservation flows, where we have flows that obey the Kirchhoff rule, and
multicast with duplication flows, where the nodes of our network have the
capability of duplicating data. This way, we only need to send our
transmission once down a link, even if it leads to several terminals.
We also distinguish different understandings of the latency of a strategy,
i.e., of a collection of paths.
We can (a) sum up the latencies of all links used by the paths, or (b) sum up
the latencies of all paths in the strategy, or (c) consider the average, or
(d) the maximum latency over all paths in the strategy.
In total, we have eight different variants to study. So far, we know that
some of them can be identified with non-atomic congestion games (with separable
latencies). For some others, this approach only works under certain topological
conditions. Again others show
a dependence on the network topology and the structure of the allowed
strategies (even from a worst-case point of view). Because of that dependence,
we introduced two new parameters ν and ν*, which capture the
maximum resp. minimum consumption of bandwidth considered all links and all
possible strategies.
We have proved an upper bound that uses these parameters
for two variants of multicast and linear latency functions.
We have also constructed examples that show that due to selfish behavior, it is
possible that the benefits of duplication (compared to multicast with
conservation flows) can remain completely unexploited by the players. This
leads to the slightly paradoxical situation that in these examples, which have
latency functions that are polynomials of degree p, we have a price of anarchy
of O(p) for multicast with conservation flows, but Ω(2p) for
multicast with duplication flows.
This is joint work with Andreas Baltz and Anand Srivastav.
We consider the following game, played by two players whom we call
Maker and Breaker. The players take turns in occupying edges of a
complete graph on n vertices. Maker's aim is to create a graph M,
whose edge distribution is close to that of a random graph
G(n,0.5) - what is customary called a pseudo-random (or a jumbled,
borrowing the terminology of Andrew Thomason) graph; Breaker tries
to prevent Maker from fulfilling his goal. We show that Maker has a
strategy for ensuring that by the end of the game the graph M of his
edges will possess strong pseudo-random properties. As pseudo-random
graph are known to enjoy many nice graph theoretic properties,
this result guarantees Maker's win in several other games, to be
discussed as well in this talk.
This is a joint work with Alan Frieze and Oleg Pikhurko (CMU) and Tibor
Szabo (ETH).
If we view a graph as a one-dimensional simplicial complex,
then some notions from topology may be considered, in particular, the
basic notion of a covering map. If there is an n-fold covering map
from H to G - a finite connected graph, we say that H is an n-lift
of G. In concrete combinatorial terms this means that H is a graph
on vertex set V(G) x [n]. For every vertex x in V(G) we call the set
Fx = {x} x [n] the fiber over x. For every edge xy in E(G)
there is in E(H) a matching between Fx and Fy.
If this matching is selected at
random we get a randon n-lift of G. I will review my joint work with others
on these graphs and their properties. We already have a substantial
body of knowledge about typical properties of lifts. Lifts were
recently employed to construct large regular graphs with nearly optimal
spectral gap. Also, Khot's "unique games conjecture" highlights the
importance of various algorithmic problems on graph lifts.
Talk based on work done jointly with: A. Amit, Y. Bilu, Y. Drier,
J. Matousek, and E. Rozenman.
Constraint satisfaction problems are generalizations of
CNF boolean formulas.
We are given a set of variables, and a domain of values that
the variables can take. Some subsets of the variables have ``constraints''
which restrict the value-assignments that can be made to those variables.
A problem is satisfiable if there is an assignment of values to the
variables which does not violate any of the constraints.
Some well-studied special cases are k-SAT, graph colourability
and graph homomorphism.
In this talk, we discuss models of random constraint satisfaction problems
and survey what is known so far. We focus on a family of models
that includes most of the well-studied individual models, and
look at questions regarding the entire family.
For example, which models from this family exhibit a sharp threshold
of satisfiability? The study of such thresholds generalizes the
study of the threshold of satisfiability for
a random instance of k-SAT and the threshold of k-colourability
for a random graph.
In a balls-in-bins process with feedback, there is a fixed number B of
bins at which balls arrive, each ball going to a given bin with
probability proportional to a function f of the number of balls in
that bin. In this work, we employ a continous-time embedding of these
processes (due to Rubin and Davis) and an approximation by Brownian
motion to compute asymptotic results for a large initial number t of
balls. That is, we compute
Property Testers (or Testers) are randomized algorithms that can
distinguish whp between graphs satisfying some property from those
that are far from satisfying it. A graph property P is said to be
non-uniformly-testable if for every fixed ε there is a tester
for P that can distinguish between graphs satisfying P from those
that are ε-far from satisfying it, and whose number of queries
is bounded by a function of ε. P is said to be uniformly-testable
if the above tester works for any ε, namely if it can receive
ε as part of the input.
In this talk I will describe a combinatorially natural graph property
in coNP, which is non-uniformly-testable but cannot be uniformly tested.
The proof combines two classical results of Erdös in Extremal Graph
Theory, results from the theory of Property Testing as well as arguments
from the theory of Recursive Functions.
Joint work with Noga Alon.
For two graphs G and H we denote by ex(G, H) the maximum number of edges
in a subgraph of G that does not contain H. When G is the complete graph on n
vertices we obtain the Turan number ex(n, H) whose value is asymptotically
given by Erdos-Stone-Simonovits theorem. In this talk we will review results
and present some new ones for the case when G is not the complete graph.
We give a probabilistic analysis of the multidepot vehicle routing
problem (MDVRP) where an instance of the problem consists of
k points in [0,1]2 forming the set D
of depots, and n points in [0,1]2 forming the set P of points. The
optimization problem is to find a collection of disjoint TSP tours with
minimum total length such that all points are covered and each tour contains
exactly one depot (not all depots have to be used). In the random setting
the depots as well as the points are given by independently and uniformly
distributed random variables in [0,1]2. We show that the asymptotic
behavior of MDVRP depends on the ratio k/n. We distinguish the cases
k=λ n for λ>0, k=o(n) and k=Ω(n1+ε) for
ε>0.
In the first two cases the optimal MDVRP tour length is asymptotically
n1/2 almost surely. In the last case the problem changes its
character as it becomes the all nearest neighbor
problem. Here we show an asymptotic tour length of $n/k1/2.
A heuristic which first clusters points around the nearest depot and then does
the TSP routing is shown to find an optimal tour almost surely. We also
outline the proof that the problem admits a polynomial-time approximation
scheme (in the deterministic stetting) for a constant number of depots.
This is joint work with Andreas Baltz and Sören Werth (Kiel)
and Devdatt Dubhashi and Libertad Tansini (Göteborg).
For X a finite nonempty set and a subset F of 2X, the pair
(X, F) is called a positional game on X. It is played by two players
Maker and Breaker, where in each move Maker claims one previously
unclaimed element of X and then Breaker claims one previously
unclaimed element of X. Maker wins if he claims all the elements of
some set in F, otherwise Breaker wins. For positive integers a and
b, the game is called (a:b) biased if Maker claims a elements
(instead of 1) and Breaker claims b elements (instead of 1) in each
move.
We introduce and study positional games on
random graphs. Our main concern is to determine the threshold
probability pF for the existence of Maker's strategy
to win in the unbiased game played on the edges of
random graph G(n,p), for various target families F of winning sets.
More generally, for each probability above this threshold
we study the smallest bias b such that Maker wins the (1:b) biased game.
We investigate these functions for a number of basic games,
like the connectivity game, the perfect matching game, the clique game
and the Hamiltonian cycle game.
Joint work with Tibor Szabo.
Given a polytop P with a real-valued objective function f on its
vertices, we consider the problem of finding a minima of f.
Arguably the simplest randomized approach is the simplex algorithm
RANDOMEDGE. Sitting at a vertex of P, RANDOMEDGE chooses an edge
uniformly at random among all incident edges decreasing the
objective function value, and proceeds on it to the neighboring
vertex. In the most important special case, i.e. when f is given by
a linear function, the performance of RANDOMEDGE is not known.
The most widely studied combinatorial generalization of linear
functions is the concept of "abstract objective function".
Abstract objective functions have a unique minima on every face,
which is certainly true for generic linear functions.
It was conjectured that RANDOMEDGE finds the minima of abstract
objective functions in polynomial or even quadratic expected time.
In the talk we exhibit an abstract objective function on the
n-dimensional hypercube, such that RANDOMEDGE takes a
mildly exponential expected time to find its minima.
Joint work with J. Matousek.
We investigate algorithms and existence proofs for finding large planar
subgraphs in different settings. One example is the following question:
Suppose that we modify the classical random graph process in such a way
that we add a randomly chosen edge only if the produced graph remains
planar (and reject the edge otherwise). What is the evolution of
this process?
In percolation in an L x L box, there is a simple algorithm which
decides whether or not there is a path connecting opposite sides of the
box after looking at order L7/4 sites. A lower bound is given by the
minimum path length, which has been measured by Grassberger to be order
L1.131. We study a random-turn version of the classical game of Hex
and determine the optimal strategy, which leads to an algorithm for the
percolation question that appears to take order L1.6 queries.
Joint work with Yuval Peres, Oded Schramm, and Scott Sheffield.
This talk is on the relation between random graphs with bounded
degrees, and their nonrandom counterparts with large girth. The
passing of a property of all d-regular graphs with large girth to
random d-regular graphs (without girth restriction) is common. A
completely new development is that we may be able to prove something
about all regular graphs (or, sometimes, graphs of bounded degree)
with large girth by adapting methods using randomised algorithms
which were tailor-made for random regular graphs. Although only one
case has been fully investigated so far, it would appear that many
results obtained for random regular graphs may translate back to the
nonrandom, large girth case in a similar way, thereby providing an
alternative proof of (some/many of?) the properties of random regular
graphs. The new result to be discussed in detail is on the size of
independent sets, obtained jointly with Joe Lauer.
Organization and Sponsorship
Scientific Organizing Committee
Tomasz Luczak,
Uniwersytet im. Adama Mickiewicza, Poznañ
Joel
Spencer,
New York University
Anand Srivastav,
Christian-Albrechts-Universität zu Kiel
Local Organization
Elena Della Godenza, Centro Congressi di Bertinoro
Sponsored by
BICI Bertinoro International Center for Informatics
CAU Christian-Albrechts-Universität zu Kiel
DFG Deutsche Forschungsgemeinschaft, Schwerpunkt 1126 Algorithmik großer und komplexer Netzwerke
ABSTRACTS
(1) Consider the following game: there are two players, Maker and Breaker,
who alternately occupy new points of the plane;
assume that Maker colors his points
red and Breaker colors his points blue. Let S be an arbitrary finite
point set on the plane; Maker's goal is to build a red congruent copy
of S; Breaker's goal is to stop Maker. I proved that Maker can win
in a finite number of moves for every set S.
This remains true even if Maker is the underdog: if (say) Breaker
takes 1000 points per move and Maker takes 1 point per move only.
A family of goal sets is called a Weak Winner if Maker can achieve it
but not necessarily first.
The previous result says that ``every finite point set in the plane''
is a Weak Winner. I give a list of other Weak Winners.
(2) Playing on the whole plane, ``n-points-on-an-opponent-free-line''
is a Weak Winner for every n.
(3) Playing on the set of lattice points, ``n-consecutive-on-a-line'' is a Weak Winner for every n.
(4) Playing on a sufficiently large clique (the players take edges),
every given ``two-colored clique'' (some given edges are required to
be red---owned by Maker---and the rest of the edges are required to be
blue---owned by Breaker) is a Weak Winner.
I just mentioned 4 classes of Weak Winners; there are many more. Another natural question: how long does it take to achieve a Weak Win;
I call it the Move Number. I give some upper and lower bounds
on the Move Number.
Long version of the abstract (ps-File)
Conference Photos
