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.1.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 30 April - Rahul Savani| (Liverpool)
The Complexity of the Simplex Method

The simplex method is a well-studied and widely-used pivoting method for solving linear programs. When Dantzig originally formulated the simplex method, he gave a natural pivot rule that pivots into the basis a variable with the most violated reduced cost. In their seminal work, Klee and Minty showed that this pivot rule takes exponential time in the worst case. We prove two main results on the simplex method. Firstly, we show that it is PSPACE -complete to find the solution that is computed by the simplex method using Dantzig’s pivot rule. Secondly, we prove that deciding whether Dantzig’s rule ever chooses a specific variable to enter the basis is PSPACE -complete. We use the known connection between Markov decision processes (MDPs) and linear programming, and an equivalence between Dantzig’s pivot rule and a natural variant of policy iteration for average-reward MDPs. We construct MDPs and show PSPACE -completeness results for single-switch policy iteration, which in turn imply our main results for the simplex method.

Joint work with John Fearnley.

Thursday 7 May -  Aytek Erdil| (Cambridge)
Title and abstract TBC

Thursday 14 May - no seminar due to the 2015 Colloquia in Combinatorics|

***CHANGE OF TIME AND DAY: Friday 15 May 15.00***
Ryan Martin| (Iowa State University) 
Room EAS.E304, East Building, LSE
Recent progress on diamond-free families

In the Boolean lattice, a diamond is a subposet of four distinct subsets A, B, C, D such that A ⊂ B, C and D ⊃ B, C. One of the most well-studied problems in extremal poset theory is determining the size of the largest diamond-free family in the n-dimensional Boolean lattice. We will discuss some recent progress on this problem.

Thursday 21 May -  Allan Lo| (Birmingham)
Title and abstract TBC

Thursday 28 May - seminar details TBA

Thursday 4 June - Sebastian Siebertz| (TU Berlin)
Title and abstract TBA

Thursday 11 June - Milan Vojnovic| (Microsoft Research)
Title and abstract TBC

Thursday 18 June -  Andre Nies| (University of Auckland)
Title and abstract TBC

Thursday 25 June -  Sylvain Sorin| (University of Paris 6)
On some advances in zero-sum repeated games

The purpose of this survey talk is to:

  1. present briefly the topic and the main issues
  2. describe some new approaches, results and directions of research. Topics include: uniform and asymptotic analysis, approachability, Shapley operator, stochastic games and games with incomplete information, link with games in continuous time, differential games and games with vanishing stage duration.

Thursday 2 July - seminar details TBA

Previous seminars in this series:

2015|, 2014|, 2013|, 2012|, 2011|, 2010|, 2009|, 2008|, 2007|, 2006|, 2005|, 2004 and before|