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


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 27 November - Costantinos Daskalakis| (MIT)
Computing on Strategic Inputs

Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient reductions from mechanism design (i.e.optimizing over rational inputs) to algorithm design(i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.

Bio: Constantinos Daskalakis is the x-window consortium associate professor of computer science at MIT. He holds a diploma in electrical and computer engineering from the National Technical University of Athens, and a Ph.D. in electrical engineering and computer sciences from UC-Berkeley. His research interests lie in theoretical computer science and its interface with economics and probability. Daskalakis has been honored with the 2007 Microsoft Graduate Research Fellowship, the 2008 ACM Doctoral Dissertation Award, the Game Theory and Computer Science Prize from the Game Theory Society, the 2010 Sloan Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, the 2011 Ruth and Joel Spira Award for Distinguished Teaching, and the 2012 Microsoft Research Faculty Fellowship. He is also a recipient of Best Paper awards at the ACM Conference on Economics and Computation in 2006 and in 2013.

Thursday 4 December - Klas Markström| (Umeå Universitet)
Full subgraphs

Given a graph G with n vertices and edge density p,  a subgraph H on k vertices is said to be full if the minimum degree of H is at least p(k-1).  Our basic question is: How large is the largest full subgraph of  G?   Erdös, Luczak and Spencer showed that if p=1/2 then the answer is at least of order n^0.5 and there are graphs where it less than n^(2/3)log(n)^(1/3). The lower bound is given by a constructive greedy algorithm


In this talk I will discuss my recent joint work on this problemwith Victor Falgas-Ravry and Jacques Verstraete. Among other things we prove that for p=1/2 the optimal upper and lower bounds are of order n^(2/3). We also show that the simple greedy algorithm can fail to give a full subgraph of the optimal order and that there is another algorithm which finds a full subgraph of the same order as the optimal one.

Thursday 11 December - Jop Briet| (NYU/CWI)
Title and abstract TBC

Previous seminars in this series:

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