Below you'll find an overview of the past seminars in this series from 2014. The seminars are listed in reverse chronological order, most recent first.
Thursday 16 October - Paul Goldberg| (University of Oxford)
Learning game-theoretic equilibria via query protocols
In the traditional model of algorithmically solving a game, the entire game is the "input data", which is presented in its entirety to an algorithm that is supposed to compute a solution, for example an exact/approximate Nash/correlated equilibrium. In some situations it may be preferable to regard the game as a "black box" which the algorithm can find out about via queries. For example, a complete description of a multi-player game may be infeasibly large. In this talk, we give an overview of recent work on algorithms that find game-theoretic equilibria via a sequence of queries that specify pure-strategy profiles, and answer with the associated payoffs. The main research issue is "query complexity", which refers to how many queries are needed in order to find a given kind of solution.
Thursday 9 October - Arkadi Predtetchinski| (Maastricht University)
Subgame-perfect epsilon-equilibria in perfect information games with common preferences at the limit
We prove the existence of a pure subgame-perfect epsilon-equilibrium, for every epsilon >0, in multi-player perfect information games, provided that the payoff functions are bounded and exhibit common preferences at the limit. If, in addition, the payoff functions have finite range, then there exists a pure subgame-perfect 0-equilibrium. These results extend and unify the existence theorems for bounded and semicontinuous payoffs in Flesch et al [2010] and Purves and Sudderth [2011].
This is joint work with Janos Flesch.
Thursday 3 July - Paul Duetting| (Stanford)
Mechanisms for Matching Markets with Budgets
In this talk we review several recent results regarding matching markets with budgets. We begin by establishing the existence of a bidder optimal (BO) and envy free (EF) outcome for general non-linear and discontinuous utilities. Afterwards we prove that if these utilities satisfy a certain non-degeneracy assumption, then every mechanism that computes a BO and EF outcome is dominant strategy incentive compatible. We conclude by showing how a BO and EF outcome can be computed in polynomial time for piece-wise linear utilities with non-identical slopes and multiple discontinuities.
Based on joint work with Monika Henzinger and Ingmar Weber.
Thursday 26 June - Omer Edhan| (Manchester)
Cost Sharing with Dependencies
Two common assumptions in many works on cost sharing are 1. the lack of reciprocal demand constraints; namely, it is assumed that the set of feasible aggregate demand vectors is a rectangle, and 2. the cost function is (essentially) differentiable. This is not the case in many cost problems of interest, such as cost sharing in networks and risk sharing. Haimanko (2002) addressed the second matter but not the first, and his methods can not be extended to treat the first matter. We consider two classes of cost problems with no such restriction on demand vectors, and essentially non-differentiable cost functions. The cost functions in the first class are convex exhibiting non-decreasing marginal costs to scale, and those in the second class are piecewise linear. We prove existence and uniqueness of a cost allocation mechanism, satisfying standard axioms, on these classes. If time allows, generalizations of these results will be discussed.
Thursday 19 June - Matthew Jennsen (LSE)
A Hypergraph Turán theorem via a generalised notion of Lagrangian
Abstract: not available
Thursday 12 June - Eoin Patrick Long| (Oxford)
Frankl-Rödl type theorems for codes and permutations
How large can a family ${\cal A} \subset {\cal P}[n]$ be if $|A \cap B| \neq t$ for all $A,B \in {\cal A}$? The Frankl-Rödl theorem shows that if $0 < \epsilon n< t < (1/2-\epsilon )n$ then $|{\cal A}| \leq (2-\delta )^n$, where $\delta = \delta (\epsilon )> 0$. In this talk I will describe a new proof of this theorem. Our method extends to codes with forbidden distances, where over large alphabets our bound is significantly better than that obtained by Frankl and Rödl.
One consequence of this result is a Frankl-Rödl type theorem for permutations with a forbidden distance.
Joint work with Peter Keevash.
Thursday 29 May - Jan Foniok| (Warwick)
Deciding the Bell Number for Hereditary Graph Classes
The \emph{speed} of a hereditary graph class is the number of (labelled) graphs on {1,2,…,n} in the class, as a function of n. It is known that not every function can be obtained as the speed of some such class; e.g., if the speed grows faster than any polynomial, than it is at least exponential.
Another such jump was identified by Balogh--Bollobas--Weinreich (2005): if the speed is at least n(1−o(1))n, then it is bounded from below by the nth Bell number (the number of partitions of an n-element set). We study the computational problem to decide for a given hereditary class whether its speed is below or above* the Bell number.
We provide an algorithm that solves this problem for classes described by a finite list of forbidden induced subgraphs. It is based on a characterisation of minimal classes with speed above* the Bell number.
* By “above” I mean “greater than or equal to”.
Joint work with A Atminas, A Collins, V Lozin.
Thursday 8 May - Jeroen Schillewaert |(Imperial College)
Probabilistic Constructions in Finite Geometries
In ongoing work, we study random constructions of small maximal independent sets in incidence structures. To illustrate our ideas, I will discuss a well-studied example from finite geometry. No background on the latter will be assumed.
Joint work with Jacques Verstraete.
Thursday 1 May - Krzysztof R. Apt| (CWI and University of Amsterdam)
Selfishness Level of Strategic Games
We introduce a new measure of the discrepancy in strategic games between the social welfare in a Nash equilibrium and in a social optimum, that we call selfishness level. It is the smallest fraction of the social welfare that needs to be offered to each player to achieve that a social optimum is realized in a pure Nash equilibrium. The selfishness level is unrelated to the price of stability and the price of anarchy.
We study the selfishness level of several well-known strategic games. This allows us to quantify the implicit tension within a game between players' individual interests and the impact of their decisions on the society as a whole. Our analyses reveal that the selfishness level often provides a deeper understanding of the characteristics of the underlying game that influence the players' willingness to cooperate.
For instance, the selfishness level of the n-players Prisoner's Dilemma is c/(b(n-1)-c), where b and c are the benefit and cost for cooperation, respectively, and that of the n-players public goods game is (1-cn)/(c-1), where c is the public good multiplier. In turn, the selfishness level of Cournot competition, Tragedy of the Commons, and Bertrand competition is infinite.
This is a joint work with Guido Schaefer.
Thursday 20 March - Richard Montgomery| (Cambridge)
Spanning Trees in Random Graphs
Following on from the sharp determination of the threshold for a Hamiltonian path appearing in an Erdos-Renyi random graph, attention has been given to more general questions about the threshold for the appearance of other bounded degree spanning trees. We will outline a recent reduction of the probability required to embed a bounded degree spanning tree in a random graph, as well as mentioning the related problem of finding all such trees simultaneously.
Thursday 13 March - Jacques Verstraete| (University of California, San Diego)
Generalized factors of graphs
Abstract|
Thursday 6 March - Yoram Bachrach| (Microsoft Research, Cambridge)
On Agent Failures and Decomposing The Intelligence of Crowds
Cooperative game theory deals with selfish agents who need each other to achieve their goals, but who want to maximize their share of the total value generated. I'll demonstrate how solution concepts, such as the Shapley value or the core, can be used to measure the individual contribution of an agent to the intelligence of a crowd, and discuss how the potential for agent failures may actually help them collaborate.
Thursday 27 February
Barnaby Roberts (LSE)
A Random Graph Analogue of the Andrasfai-Erdos-Sos Theorem
Andrasfai, Erdos and Sos proved that all triangle-free graphs with minimum degree strictly greater than 2n/5 are bipartite. We consider an adaptation of this result to a random graph setting and discuss some other random graph versions of classical results.
This lecture forms part of the Lunchtime Seminar Series|.
Thursday 20 February - Eskil Rydhe| (Lund University, Sweden)
Weighted admissibility with respect to the right shift on H^{2}
Abstract|
Thursday 13 February - Marina Iliopoulou (University of Edinburgh)
The polynomial method in computational geometry
Recently, algebraic techniques have been introduced to count incidences between lines and points. The main idea behind these methods is decomposing the space we are working in—and therefore of our original set of points as well— by the zero set of a polynomial. This enriches our setting with extra structure, allowing us to understand it better. Such techniques were first used in incidence geometry by Dvir, for the solution of the Kakeya problem in finite field settings. The aim of this talk is to give a taste of these techniques (including Dvir’s basic argument), via the study of the joints problem in $\mathbb{R}^n$.
More specifically, if $\mathfrak{L}$ is a finite set of lines in $\mathbb{R}^n$, we say that a point $x \in \mathbb{R}^n$ is a joint formed by $\mathfrak{L}$ if at least $n$ lines of $\mathfrak{L}$ are passing through $x$, such that their directions span $\mathbb{R}^n$. The joints problem asks for the optimal upper bound of the number of joints formed by $\mathfrak{L}$, depending only on the cardinality of $\mathfrak{L}$. The joints problem was solved in $\mathbb{R}^3$ by Guth and Katz, and later in $\mathbb{R}^n$ by Kaplan, Sharir and Shustin, and independently by Quilodran; all the solutions involved algebraic techniques. In particular, we will present Quilodran’s solution, which involves Dvir’s essential argument for his solution of the Kakeya problem in finite fields.
Thursday 6 February - Filip Moric| (EPFL Lausanne)
Upper bounds for the perimeter of plane convex bodies
Given a plane convex body S and another convex set C contained in S, it is a well known fact that per(C)\leq per(S). In other words, the largest possible perimeter of a convex body that lies inside another convex body S equals per(S). We raise the following more general question: Given a compact convex body S in the plane and k\in\mathbb N, how large can the sum of perimeters of k pairwise disjoint convex sets contained in S be? We conjecture that the sum is always bounded from above by per(S) + 2(k-1) diam(S), which would be tight. We prove this conjecture in the case when S is a square or an arbitrary triangle. A slightly weaker bound is obtained for general plane convex bodies. As a consequence, we establish a bound on the perimeter of a polygon with at most k reflex angles lying inside a given plane convex body. We will also discuss some other related problems.
Based on joint work with Alexey Glazyrin
Thursday 30 January - Ziv Hellman| (Bar Ilan University, Israel)
Graph value for cooperative games
We suppose that players in a cooperative game are located within a graph structure, such as a social network or supply route, that limits coalition formation to coalitions along connected paths within the graph. This leads to a generalisation of the Shapley value that is studied here from an axiomatic perspective. The resulting ‘graph value’ is endogenously asymmetric, with the automorphism group of the graph playing a crucial role in determining the relative values of players.
Joint work with Ron Peretz
Thursday 23 January - Dario Bauso| (Palermo)
Robust Mean-Field Games
Within the realm of mean field games under uncertainty, we study a population of players with individual states driven by a standard Brownian motion and a disturbance term. The contribution is three-fold: First, we establish a mean field system for such robust games. Second, we analyze robust mean field equilibria. Third, we show that the dimension of the mean field system can be significantly reduced by considering a functional of the first moment of the mean field process. Applications to production, opinion dynamics and cyber-physical systems will be discussed.
Based on joint work with Tamer Basar and Hamidou Tembine.
Thursday 16 January - Yufei Zhao| (MIT)
The Green-Tao theorem and a relative Szemerédi theorem
The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and discuss our recent simplifications.
One of the main ingredients in the proof is a relative Szemerédi theorem, which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. Our main advance is both a simplification and a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition suffices. I will explain the transference principle strategy used in the proof.
Based on joint work with David Conlon and Jacob Fox.