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 firstname.lastname@example.org, for further information about any of these seminars.
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)
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