Erdös Magic for Algorithms and Games
2429 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 
TicTacToe 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 
BallsinBins 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 AvoiderEnforcer 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 MultiDepot 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.
Scientific Organizing Committee  Tomasz Luczak, Uniwersytet im. Adama Mickiewicza, Poznañ 

Joel Spencer, New York University  
Anand Srivastav, ChristianAlbrechtsUniversität zu Kiel  
Local Organization  
Elena Della Godenza, Centro Congressi di Bertinoro  
Sponsored by 
BICI Bertinoro International Center for Informatics
CAU ChristianAlbrechtsUniversität zu Kiel DFG Deutsche Forschungsgemeinschaft, Schwerpunkt 1126 Algorithmik großer und komplexer Netzwerke 
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!)?''
(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, ``npointsonanopponentfreeline''
is a Weak Winner for every n.
(3) Playing on the set of lattice points, ``nconsecutiveonaline'' is a Weak Winner for every n.
(4) Playing on a sufficiently large clique (the players take edges),
every given ``twocolored clique'' (some given edges are required to
be redowned by Makerand the rest of the edges are required to be
blueowned 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.
The second subject is: ``Exact values of infinitely many game numbers''.
I begin with mentioning a new lower bound for the HalesJewett number HJ(n)
in Ramsey theory; this leads to multidimensional TicTacToe; and
finally I discuss ``exact solutions''.
Long version of the abstract (psFile)
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 RenyiUlam liar game, in which one of n possibilities must be guessed, tary 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 twobatch 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 twobatch version of the game.
This is joint work with Joel Spencer.
In his seminal work Harsanyi [Har67] introduced an elegant approach to study noncooperative 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 axisparallel boxes in the ddimensional 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 npoint configuration in the ddimensional 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 Z_{p}, of Bohr sets in Z_{p} and of higherdimensional 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) AvoiderEnforcer 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 MakerBreaker 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 worstcase 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 worstcase 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 nonatomic 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 worstcase 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 Ω(2^{p}) 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 pseudorandom (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 pseudorandom properties. As pseudorandom 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 onedimensional simplicial complex, then some notions from topology may be considered, in particular, the basic notion of a covering map. If there is an nfold covering map from H to G  a finite connected graph, we say that H is an nlift 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 F_{x} = {x} x [n] the fiber over x. For every edge xy in E(G) there is in E(H) a matching between F_{x} and F_{y}. If this matching is selected at random we get a randon nlift 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 valueassignments 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 wellstudied special cases are kSAT, 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 wellstudied 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 kSAT and the threshold of kcolourability for a random graph.
In a ballsinbins 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 continoustime 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 nonuniformlytestable 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 uniformlytestable 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 nonuniformlytestable 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 ErdosStoneSimonovits 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=Ω(n^{1+ε}) for ε>0. In the first two cases the optimal MDVRP tour length is asymptotically n^{1/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/k^{1/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 polynomialtime 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 2^{X}, 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 p_{F} 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 realvalued 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 ndimensional 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 L^{7/4} sites. A lower bound is given by the minimum path length, which has been measured by Grassberger to be order L^{1.131}. We study a randomturn 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 L^{1.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 dregular graphs with large girth to random dregular 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 tailormade 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.