11 December 2008

Amin CojaOghlan (University of Edinburgh)
Efficient cut norm approximations of sparse graphs, matrices, and tensors
Abstract: Let A be a 0/1 matrix of size m×n, and let p be the density of A (i.e., the number of ones divided by mn). We show that A can be approximated in the cut norm within εmnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size mn of A, provided that A satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. The result extends the work of Frieze and Kannan to sparse matrices. As an application, we obtain efficient 1ε approximation algorithms for ``bounded'' instances of MAX CSP problems.
The talk is based on a joint paper with Alan Frieze and Colin Cooper.

4 December 2008

Harald Räcke (University of Warwick)
Oblivious Interference Scheduling
Abstract: In the interference scheduling problem, one is given a set of n communication requests described by pairs of points from a metric space. The points correspond to devices in a wireless network. In the directed version of the problem, each pair of points consists of a dedicated sending and a dedicated receiving device. In the bidirectional version the devices within a pair shall be able to exchange signals in both directions. In both versions, each pair must be assigned a power level and a colour such that the pairs in each colour class can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a colour class is defined in terms of the Signal to Interference Plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. This is commonly referred to as the ``physical model'' and is the established way of modelling interference in the engineering community. The objective is to minimize the number of colours corresponding to the time needed to schedule all requests.
We study oblivious power assignments in which the power value of a pair only depends on the distance between the points of this pair. We prove that oblivious power assignments cannot yield approximation ratios better than Ω(n) for the directed version of the problem. For the bidirectional version we can show the existence of a universally good oblivious power assignment: For any set of n bidirectional communication requests, the socalled ``square root assignment'' admits a colouring with at most polylog(n) times the minimal number of colours.
Joint work with Alexander Fanghänel, Thomas Kesselheim, and Berthold Vöcking.

27 November 2008

Carl Graham (Ecole Polytechnique)
Inequalities for positivity preserving operators using stochastic domination and the Hardy inequality
Abstract: We study positivitypreserving operators acting on the classical Lp spaces of signed measures on the integers. We derive bounds for operators of interest from bounds for other tractable operators dominating stochastically the first ones, up to a wellcontrolled constant factor. The main tools are the Hardy inequality, the definition of related auxiliary spaces suited to take advantage of the domination, and the proof that the norms are equivalent to the classical ones if the reference measure is quasigeometrically decreasing. This will be notably applied to derive exponential stability results.

20 November 2008

Rakesh Vohra (Northwestern University)
Optimal Auctions with Budget Constrained Bidders
Abstract: Auction theory revolves around the design and analysis of auctions when a seller with goods for sale is confronted with buyers whose willingness to pay he knows little about. A standard assumption is to conflate a buyer's willingness to pay with her ability to pay  an unpalatable assumption in a variety of situations. For instance, in government auctions (privatization, license sales etc.), the sale price may well exceed a buyers' liquid assets, and she may need to rely on an imperfect (i.e. costly) capital market to raise funds. These frictions limit her ability to pay, but not her valuation (how much she would pay if she had the money). For a seller, budget constraints mean that low budget bidders cannot put competitive pressure on high budget bidders. For this reason it has been suggested the seller should subsidize some bidders to foster competition. We investigate this question by analyzing the revenue maximizing Bayesian incentive compatible mechanism for the sale of a single good to buyers who have budget constraints. Both the valuation and the budget of the buyer are assumed to be private information.
This paper is based on joint work with Mallesh Pai.

13 November 2008

Arne Lokka (LSE)
Detection of critical events before public announcements
Abstract:
I consider a model for financial asset prices which incorporates the possibility of some market participants having more information than what is publicly available. In particular I consider the case of an acquisition situation where the asset price of the target company tend to exhibit above average return prior to the public announcement of the deal. By observing the asset price of the target company is it possible to "predict" the takeover before the deal is publicly announced. The aim is to use disorder detection techniques and to derive an explicit solution to this problem.

6 November 2008

Olivier Gossner (LSE and Paris School of Economics)
Information theory and game theory: applications and new questions
Abstract:
The study of communication, coordination and correlation between agents in Game Theory naturally calls for the use of tools that were developed in the context of information theory. We review several applications of Information Theory to Game Theory, and present new informationtheoretic problems arising from the study of games.

30 October 2008

Risi Kondor (UCL)
The Fourier transform of graphs
Abstract:
Permuting the vertices of a graph acts on the adjacency matrix by permuting the rows and the columns. This identifies the offdiagonal entries with the homogeneous space S_{n}/S_{n2}, and allows us to unleash the machinery of noncommutative harmonic analysis on graphs. I discuss two applications: (1) constructing graph invariants via the bispectrum and the skew spectrum; (2) efficient search over permutations for quadratic assignment type problems.

23 October 2008

István Juhász (Alfred Renyi Institute of Mathematics)
Discrete Subspaces of Compacta
Abstract:
In the first part of the talk we intend to survey the role that the behaviour of discrete subspaces (and related other subspaces, like free sequences) play in determining the cardinality properties of topological spaces, in particular of compacta (that is, compact Hausdorff spaces).
In the second part we review two recent results of ours that fall into this category. The first one gives a partial answer to a problem of A. Dow and the second yields a significant strengthening of a classical result of Cech and Pospisil.
Theorem 1. Under the generalised continuum hypothesis every countably tight compactum X has a discrete subspace whose closure is of the same cardinality as X.
(A space is countably tight if whenever a point belongs to the closure of a set it already belongs to the closure of a countable subset.)
Theorem 2. If in a compactum X the character of every point is at least k then X cannot be covered by fewer than 2^{k} many discrete subspaces.
(The character of a point is the smallest cardinality of a neighbourhood base of the point.)

16 October 2008

Bernhard von Stengel (LSE)
Index and Uniqueness of Symmetric Equilibria
Abstract:
We use elementary constructions of polytopes to prove a gametheoretic result for nondegenerate twoplayer games: The "potentially unique" symmetric equilibria of symmetric games are exactly those of positive symmetric index. An equilibrium is "potentially unique" if it is the unique equilibrium in a larger game obtained by adding further strategies (which are not played in the equilibrium). This characterizes the index, a topological notion, in gametheoretic terms.
Joint work with Anne Balthasar (LSE).

9 October 2008

Dan Romik (The Hebrew University of Jerusalem)
The oriented swap process
Abstract:
The oriented swap process is a random walk on the symmetric group of order N. Starting from the identity permutation, at each step an adjacent swap is chosen uniformly and applied to the current permutation, but only if it increases the number of inversions. Eventually the walk terminates when it reaches the permutation with maximal number of inversions.
In recent work with Omer Angel and Alexander Holroyd, we analyzed the asymptotic behavior of the oriented swap process when N tends to infinity using the theory of totally asymmetric exclusion processes, deriving formulas for the limiting trajectories of individual numbers ("particles") in the permutation and for the flow of particles en masse. I will explain these results and show computer simulations.

17 September 2008

Uri Zwick (Tel Aviv University)
Discounted Deterministic Markov Decision Processes
Abstract:
We present an O(mn+n^{2} log n)time algorithm for finding optimal strategies for discounted, infinitehorizon, Deterministic Markov Decision Processes (DMDP), where n is the number of vertices (or states) and m is the number of edges (or actions). This improves a recent O(mn^{2})time algorithm of Andersson and Vorobyov.
Joint work with Mikkel Thorup.

19 June 2008

Tobias Mueller (Technische Universiteit Eindhoven)
Circular choosability
Abstract:
The circular chromatic number of a graph is a refinement of the ordinary chromatic number that has attracted considerable attention since its introduction by Vince in 1988. One of the nice properties it enjoys that it is a rational number that lies between the chromatic number and the chromatic number minus one.
In 2002 Mohar introduced a ``list version'' of the circular chromatic number, the circular choosability. I will give an overview of known results and open problems on circular choosability. Time permitting, I may also give a proof of the (nontrivial) fact that the circular choosability is a rational number for all graphs.

12 June 2008

Xiaotie Deng (City University of Hong Kong)
Equilibrium Computation and Applications
Abstract:
The rise of the Internet has created a surge of human activities that make computation, communication and optimization of participating agents accessible at microeconomic levels. In response to the need of this great revolution, fundamental equilibrium problems of games and markets have become active (and highly interdisciplinary) research topics.
In this talk, I will discuss computational issues in fixed point and equilibria, their relationships, as well as impacts on application problems.

5 June 2008

Michael J. Pelsmajer (Illinois Institute of Technology)
Crossing Numbers
Abstract:
When drawing a graph on the plane or another surface, usually one tries to avoid having any two edges cross. When that is not possible, often people would like to minimize the number of crossings in a drawing, perhaps avoiding "unnecessary crossings". For example, this theorem of Hanani and Tutte:
If a graph can be drawn in the plane such that every two edges cross an even number of times, then it can be redrawn with no crossings at all.
We will give a short proof of this, and discuss other recent results of this nature. The work was done in collaboration with Marcus Schaefer (DePaul University), Daniel Stefankovic (University of Rochester), and Despina Stasi (a graduate student at University of Illinois Chicago).

29 May 2008

Peter Streufert (The University of Western Ontario)
Characterizing Consistent Beliefs by Means of Products of Relative Probabilities
Abstract:
When a player moves in an extensiveform game, she knows that she is at one node in her information set and has some belief about which node that is. Several equilibrium concepts (such as sequential equilibrium) require that her belief be "consistent" with the strategies of the players who have moved before her.
Now suppose that, in equilibrium, the player does not actually move (in the sense that the strategies of previous players imply that her information set is reached with zero probability). Nonetheless her belief may be important because her chosen strategy effected how the previous players chose their strategies. And furthermore, the consistency of her belief with the previous players' strategies may be a very subtle concept because it concerns probability over nodes that are reached with zero probability.
Essentially, we provide a new way of understanding consistency by using relative probabilities rather than the familiar absolute probabilities.
In particular, a "dispersion" specifies the relative probability between any two elements of a set. In game theory, one can replace a strategy with a dispersion and thereby specify the relative probability between any two actions, including two actions that are played with zero probability.
If one then takes the "product" of such dispersions, one could conceivably derive the relative probability between any two nodes in a game tree, and in particular, between any two nodes in any information set. It turns out that the appropriate definition of producthood is unexpected in several ways: two dispersions typically have many products, and further, the products of more than two dispersions cannot be defined by means of a binary operation.
Nonetheless, when the dust settles, the cancellation laws that define producthood lead to an intuitive characterization of consistency. Computationally, the set of all cancellation laws is an intractable sufficient condition, but each individual cancellation law provides an easily tested necessary condition.

8 May 2008

Felix Lazebnik (University of Delaware)
On the existence of certain generalized quadrangles
Abstract:
Let s>2 be an integer. A generalized triangle of order s is a bipartite (s+1)regular graph of girth six and diameter three. It is also known as the pointline incidence graph of a finite projective plane of order s, and it is known to exist for all s which are prime powers. For each prime power s>9 which is not a prime, there exist at least two pairwise nonisomorphic generalized triangles or order s, and the number of isomorphism classes grows fast with s.
A generalized quadrangle of order s is a bipartite (s+1)regular graph of girth eight and diameter four. It is known to exist for all s which are prime powers. Contrary to the case of generalized triangles, for each odd prime power s, only one (up to isomorphism) generalized quadrangle of order s is known.
We survey some recent results on generalized quadrangles, and study a relation between the existence of certain algebraically defined sregular graphs of girth eight and diameter six and the existence of generalized quadrangles of order s. Some questions are reduced to analysis of certain algebraic varieties over finite fields and permutation polynomials. We will present some nonexistence results and mention several open questions.

13 March 2008

Sylvain Sorin (Ecole Polytechnique and University of Paris 6)
Approachability and Differential Games
Abstract:
We develop the links between repeated games and differential games in the framework of approachability.
A first result due to N. Vieille (M.O.R., 17, 1992) exhibits the connection between the asymptotic approach in repeated games (limit of finitely repeated or discounted games) and differential games of fixed duration to prove the weakapproachability property.
The purpose of the current work is to exhibit a similar relation for the uniform approachability property (robustness of εoptimal strategies in long games) in repeated games and qualitative differential games.
Starting from a repeated game G, we first construct an alternative deterministic repeated game G* and a related differential game Γ. We then establish an alternative characterization of Bsets in G or G* as discriminant domains in Γ. We show that a set is *approachable in G* iff it contains a Bset. We finally provide a map from winning strategies in the differential game to approachability strategies and thus recover Spinat's characterization of approachability (M.O.R., 27, 2002).
(Joint work with S. Assoulamani and M. Qincampoix.)

11 March 2008

Louis Esperet (LaBRI, Bordeaux)
Adapted list colouring of planar graphs
Abstract:
Given a (possibly improper) edgecolouring F of a graph G, a vertex colouring of G is adapted to F if no colour appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that for any edgecolouring F of G, G admits a colouring c adapted to F, then G is said to be adaptably kcolorable. This colouring was recently introduced by Pavol Hell and Xuding Zhu, and has several applications in constraint satisfaction, resource allocation, and job assignment. In this talk, I will briefly survey what is known on adapted colouring, and then show some results we obtained on adapted colouring of planar graphs.
This is a joined work with Mickaël Montassier and Xuding Zhu.

6 March 2008

David Conlon (St John's College)
Ramsey numbers of sparse graphs
Abstract:
Let d be a fixed natural number. There is a theorem, due to Chvátal, Rodl, Szemerédi and Trotter (CRST), saying that the Ramsey number of any graph G with maximum degree d and n vertices is at most c(d)n, that is it grows linearly with the size of n. The original proof of this theorem uses the regularity lemma and the resulting dependence of c on d is of towertype. This bound has been improved over the years to the stage where we are now grappling with proving the correct dependency, believed to be an exponential in d. Our first main result is a proof that this is indeed the case if we assume additionally that G is bipartite, that is, for a bipartite graph G with n vertices and maximum degree d, we have r(G)≤ 2^{Cd} n, for some constant C. We also discuss how this result may be extended to hypergraphs. This allows us to give a clean and short proof of the hypergraph analogue of the CRST theorem. This latter work was done jointly with Jacob Fox and Benny Sudakov.

5 March 2008

Olivier Gossner (Paris School of Economics)
On the evolutionary foundation of rational choice
Abstract:
A choice rule maps subsets of available alternatives to subsets of chosen alternatives. It is strictly rational if it is induced by a strict order on the grand set of alternatives.
We compare intergenerational learning processes based on the distribution of choice rules a generation experiments with. We show that uniform experimentation on the set of strictly rational choice rules strictly dominates experimentation based on any other symmetric probability distribution on the set of choice rules. Furthermore, for a small number of generations, the performance of learning using the uniform distribution on strictly rational choice rules is linear on the number of generations, independently of the cardinality of the grand set of alternatives. This contrasts sharply with uniform experimentation on the whole set of choice rules, which performs optimally in the very long run, but for which the expected time to reach any level of performance is a double exponential in the cardinality of the grand set of alternatives.
Our model predicts a strong evolutionary advantage for a population endowed with genes that would force its agents to use strictly rational rules.
We discuss the connection with empirical evidence that humanoid cognitive capacity increases are historically related to periods of frequent changes in the environment and with findings that agents use strictly rational rules even when they are a priori indifferent between the offered alternatives.

28 February 2008

Oded Lachish (University of Warwick)
Sound 3query PCPPs are Long
Abstract:
We present a tradeoff between the length of a 3query probabilistically checkable proof of proximity (PCPP) and the best possible soundness obtained by querying it. Consider the task of distinguishing between ``good'' inputs w∈ {0,1}^{n} that are codewords of a linear error correcting code C over the binary alphabet and ``bad'' inputs that differ from every word of C on ∼1/2 of their bits. To perform this task, we allow oracle access to w and an auxiliary proof Π , however, we place the following limitations on our verifier: (i) it can read at most 3 bits from w and Π , (ii) it must accept every ``good'' input with probability one (when accompanied by a suitable proof), and (iii) its decision must be linear  i.e., based on the parity of the sum of the queried bits. We notice that all known techniques for PCPP constructions yield verifiers for linear codes that satisfy these conditions, so our tradeoff applies to all of them.
Our main result implies that for certain codes, every verifier accessing a proof of polynomial length (in the length of the input), will accept some ``bad'' words with probability at least ∼2/3. In contrast, if no limitation is placed on the proof length, we can construct a verifier that rejects any ``bad'' word with the largest possible probability of ∼1/2. In other words, the closer the rejection probability is to the best possible, the longer the proof our verifier will require. This tradeoff between proof length and soundness holds for any code that is not locally testable, including codes with large dual distance and most random Low Density Parity Check ( LDPC) codes.
Joint Work with: Eli BenSasson, Prahladh Harsha and Arie Matsliah.

21 February 2008

Sergiu Hart (The Hebrew University of Jerusalem)
Evolutionarily Stable Strategies of Random Games, and the Vertices of Random Polygons
Abstract:
An evolutionarily stable strategy (ESS) is an equilibrium strategy that is immune to invasions by rare alternative ("mutant") strategies. Unlike Nash equilibria, ESS do not always exist in finite games. In this paper, we address the question of what happens when the size of the game increases: does an ESS exist for "almost every large" game? Letting the entries in the n x n game matrix be randomly chosen according to an underlying distribution F, we study the number of ESS with support of size 2. In particular, we show that, as n goes to infinity, the probability of having such an ESS: (i) converges to 1 for distributions F with "exponential and faster decreasing tails" (e.g., uniform, normal, exponential); and (ii) it converges to 1  1/sqrt(e) for distributions F with "slower than exponential decreasing tails" (e.g., lognormal, Pareto, Cauchy). Our results also imply that the expected number of vertices of the convex hull of n random points in the plane converges to infinity for the distributions in (i), and to 4 for the distributions in (ii).
Joint work with Josef Rinott and Benjamin Weiss. http://www.ma.huji.ac.il/hart/abs/ess.html

14 February 2008

Pawel Hitczenko (Drexel University)
Limiting distribution for the number of parts in restricted partitions
Abstract:
Let S be a subset of positive integers. For a large integer n we consider partitions of n with parts in S. More specifically, under the uniform measure on the set of all such partitions and for S that are sufficiently regular we establish a limiting theorem for the (properly normalized) number of parts. Our result covers the case when S is an image of a polynomial. We mention a few specific examples that appeared earlier in the literature in rather unrelated contexts.
This is a joint work with Bill Goh.

7 February 2008

Chris Dowden (University of Oxford)
Components in random planar graphs with n vertices and m edges
Abstract:
Let P_{n,m} denote a graph taken uniformly at random from the set of all labelled planar graphs with n vertices and m(n) edges. We shall use elementary counting arguments to investigate the probability that P_{n,m} has a component isomorphic to H, for various fixed H, as n → ∞. We will provide a complete picture of exactly when the probability is bounded away from 0 and/or 1, showing that there is different behaviour depending on both the graph H and the ratio m/n.

31 January 2008

Arie Koster (University of Warwick)
Computing Treewidth  Theory and Practice
Abstract:
Many NPhard combinatorial problems can be solved in polynomial time if the underlying graph has a special structure, like for example a tree. The notion of a tree decomposition generalizes the tree structure in such a way that for many problems dynamic programming algorithms can be developed that run in polynomial time, except for one parameter, the width of the tree decomposition. Therefore, it is of utmost importance to find tree decompositions of smallest possible width, known as the treewidth of a graph.
In this talk, we discuss how such tree decompositions can be found, and how lower bounds on the treewidth can be determined. Computing the treewidth of a graph is itself an NPhard problem. Therefore, typically heuristics are applied to obtain good but possible nonoptimal tree decompositions. To benchmark such results, a wide variety of lower bounds have been derived in recent years. Finally, several approaches for exact methods have been developed and tested, including integer linear programming and exponential time and space algorithms.

24 January 2008

Akira Okada (Hitotsubashi University)
Coalitional Bargaining Games with Random Proposers: Theory and Application
Abstract:
We consider a noncooperative coalitional bargaining game with random proposers. In a general case that the recognition probability is arbitrary and players have different discount factors for future payoffs, the existence of a stationary subgame perfect equilibrium (SSPE) is proved, and the condition for the grand coalition to be formed is provided. We also prove that the grandcoalition SSPE is a unique symmetric SSPE for any discount factor in a symmetric game with nonempty core. In the last part of the paper, we apply the bargaining model to a production economy with one employer and multiple workers. When players are sufficiently patient, the economy has a unique SSPE payoff. The equilibrium allocation is compared with cooperative solutions such as the core, the Shapley value and the nucleolus. The SSPE payoff and the nucleolus have similar distributional properties.

17 January 2008

Norman Biggs (LSE)
Curious Curves and Graph Colouring
Abstract:
The chromatic polynomial tells us the number of propercolourings of a graph, with a given number of colours, say k. For large values of k the number is relatively wellbehaved, as the word 'polynomial' indicates. A longstanding aspiration is to use this good behaviour to obtain results about small values of k. In particular the chromatic number is clearly determined by the integer roots of the polynomial.
In this talk I shall describe certain families of graphs for which the chromatic polynomials can be expressed in a form that enables their roots (real and complex) to be determined. It turns out that the roots lie on socalled 'equimodular' curves. These curves have fascinating, and still largely mysterious, properties.

10 January 2008

Shmuel Zamir (The Hebrew University of Jerusalem)
Asymmetric FirstPrice Auctions with Uniform Distributions: Analytic Solutions to the General Case
Abstract:
We provide analytic solutions for any asymmetric firstprice auction, both with and without a minimum bid m, for two buyers having valuations uniformly distributed on [u, U] and [v, V]. We show that our solutions are consistent with the previously known subcases studied by Griesmer et al., (1967) when u = v, and Vickrey (1961), when one valuation is commonly known. We also show that the solution is continuous in u, U, v, V, and m. Several interesting examples are presented, including a class where the two bid functions are linear.
Joint work with Todd R. Kaplan (Exeter).
