Below you'll find the programme for the Seminar on Discrete Mathematics and Game Theory. The Seminar normally takes place on Thursdays from 2.00 pm - 3.00 pm in room TW2.3.01 (Tower Two, Clement's Inn - entrance through Tower One), unless stated below. Please contact the seminar administrator on email@example.com, for further information about any of these seminars.
Thursday 26 February - Karen Gunderson (Bristol)
Bootstrap percolation on infinite trees
A bootstrap process is a type of cellular automaton with vertices of a graph in one of two states: `healthy' or `infected'. For any positive integer $r$, the $r$-neighbour bootstrap process is the following update rule for the states of vertices: infected vertices remain infected forever and each healthy vertex with at least $r$ infected neighbours becomes itself infected. These updates occur simultaneously and are repeated at discrete time intervals. Percolation is said to occur if all vertices are eventually infected.
Of interest is the random case, where each vertex is infected independently with a fixed probability $p$. For an infinite graph, one would like to know the values of $p$ for which the probability of percolation is positive. I will give some of the history of this problem for regular trees and present some new results for bootstrap percolation on certain classes of randomly generated trees: Galton--Watson trees.
Thursday 5 March - Will Perkins (Birmingham)
Algorithmic Partitioning of Random Hypergraphs
Consider a random hypergraph formed by fixing a bipartition of the vertex set and adding k-uniform hyperedges independently at random with probabilities that depend on how the edges cross the partition.
This general model includes both the stochastic block model (k=2) and planted random k-SAT, and arises in cryptography and the analysis of clustering algorithms. Depending on the distribution of hyperedges and their density, the computational problem of recovering the partition can be tractable or intractable. I will present new results identifying the algorithmic tractability threshold for a large class of algorithms. Based on joint work with Vitaly Feldman and Santosh Vempala.
Thursday 12 March - Yannai Gonczarowski (HUJI and MSR)
Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games
Drawing intuition from a (physical) hydraulic system, we present a novel framework, constructively showing the existence of a strong Nash equilibrium in resource selection games (i.e. asymmetric singleton congestion games) with nonatomic players, the coincidence of strong equilibria and Nash equilibria in such games, and the invariance of the cost of each given resource across all Nash equilibria. Our proofs allow for explicit calculation of Nash equilibrium and for explicit and direct calculation of the resulting (invariant) costs of resources, and do not hinge on any fixed-point theorem, on the Minimax theorem or any equivalent result, on the existence of a potential, or on linear programming. A generalization of resource selection games, called resource selection games with I.D.-dependent weighting, is defined, and the results are extended to this family, showing that while resource costs are no longer invariant across Nash equilibria in games of this family, they are nonetheless invariant across all strong Nash equilibria, drawing a novel fundamental connection between group deviation and I.D.-congestion. A natural application of the resulting machinery to a large class of constraint-satisfaction problems is also described.
Joint work with Moshe Tennenholtz.
Thursday 19 March - Elias Koutsoupias (Oxford)
Title and abstract TBC
Previous seminars in this series:
2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004 and before