Home > Department of Mathematics > Seminars > Seminar on Discrete Mathematics and Game Theory
How to contact us

Department of Mathematics
Columbia House
London School of Economics
Houghton Street
London WC2A 2AE, UK


Email: maths.info@lse.ac.uk|
Tel: +44(0)207 955 7732/7925
Connect with LSE Maths: Twitter|


Click here| for information on how to get to LSE using public transport and maps of the campus

Seminar on Discrete Mathematics and Game Theory

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 seminar@maths.lse.ac.uk|, for further information about any of these seminars.

Upcoming Speakers:

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|