Seminar and PhD Seminar on Combinatorics, Games and Optimisation

Below you'll find the programme for the Seminar and PhD Seminar on Combinatorics, Games and Optimisation.

This seminar series covers many of the research areas in the Department: discrete mathematics, algorithms, game theory and operational research.

Unless stated below, this Seminar normally takes place:

on Thursdays from 14:00 - 15:00.
the PhD seminar takes place on Fridays at 12.00 on Zoom (the duration of the seminar will be 25 or 50 minutes, please see below for details).

Questions, suggestions, etc., about the seminar can be forwarded to Enfale Farooq, the Research Manager, on E.Farooq@lse.ac.uk

IMPORTANT - Due to the ongoing COVID-19 epidemic seminars will now take place online.

Upcoming speakers:

Thursday 14 October - Ahmad Abdi (LSE)
Hybrid - 14:00 on Zoom, and 32L.B.09 (LSE students and staff only)

Dyadic Linear Programming
Most linear programming solvers use fixed-precision floating points to approximate the rational numbers. Though successful on most real-world instances, solvers sometimes run into serious issues when carrying out sequential floating-point arithmetic, due to compounded error terms. This practical limitation leads to the following theoretical problem:

Given a linear program, determine whether it admits an optimal solution whose entries have an exact floating-point representation.

This question motivates the study of Dyadic Linear Programming, a problem that sits somewhere between Linear Programming and Integer Linear Programming, and benefits surprisingly from both worlds.
In this talk, I will talk about ongoing projects on this topic, and address some of the basic questions. I will also discuss applications and connections to some classical problems in Combinatorial Optimization, including the Cycle Double Cover Conjecture, and the Generalized Berge-Fulkerson Conjecture.
Based on collaborations with Bertrand Guenin, Gérard Cornuéjols, Zuzanna Palion, and Levent Tunçel.

Thursday 21 October - Ricahrd Cole (New York University)
Hybrid - 14:00 on Zoom, and 32L.B.09 (LSE students and staff only)

How many proposals suffice in stable matching?
It is well known that in many settings there are few stable matchings. But can participants exploit this to reduce the number of proposals they make?
We revisit the public-private model previously analyzed by Lee [Review of Economic Studies, 2017]. In this model valuations are obtained by combining a public score and a private assessment, for example by adding them. We show that with high probability, in any stable matching, all but the lowest rank participants obtain a match that is close to their public score assortative match (in which the rank i man is matched with the rank i woman when ordered by the public scores), while also obtaining close to the best possible private assessment. It follows that a relatively small number of proposals suffice.
We extend the result to the case of unequal numbers of men and women, and to the worker/employer setting where each employer has multiple identical positions.

This is joint work with Ishan Agarwal, Courant, NYU.

Thursday 28 October - János Flesch (Maastricht University)
Hybrid - 14:00 on Zoom, and 32L.B.09 (LSE students and staff only)

A competitive search game with a moving target
We introduce a discrete-time search game, in which two players compete to find an object first. The object moves according to a time-varying Markov chain on finitely many states. The players know the Markov chain and the initial probability distribution of the object, but do not observe the current state of the object. The players are active in turns. The active player chooses a state, and this choice is observed by the other player. If the object is in the chosen state, the active player wins and the game ends. Otherwise, the object moves according to the Markov chain and the game continues at the next period. We show that this game admits a value, and for any error-term epsilon>0, each player has a pure (subgame-perfect) epsilon-optimal strategy. Interestingly, a 0-optimal strategy does not always exist. We derive results on the properties of the value and the epsilon-optimal strategies. We devote special attention to the time-homogeneous case, where additional results hold. We also investigate a related model, where the active player is chosen randomly at each period. In this case, the results are quite different, and greedy strategies (which always recommend to choose a state that contains the object with the highest probability) play the main role.

The talk is based on two papers. The first is joint work with Benoit Duvocelle, Mathias Staudigl, Dries Vermeulen, and the second with Benoit Duvocelle, Hui Min Shi, Dries Vermeulen.

Previous seminars in the series:

Thursday 7 October - Franziska Eberle (LSE)

Online Graph Exploration – Old and New Results
Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. In this talk, we give an overview of the current state of the art in online graph exploration in the fixed graph scenario. We provide details and lower bound examples of some algorithms such as the Nearest Neighbour (NN) algorithm with its competitive ratio of O(log n).
Afterwards, we design a general framework to robustify algorithms that carefully interpolates between a given algorithm and NN. We prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs. This robustification schemes also allows us to initiate the study of a learning-augmented variant of the problem by adding access to machine-learned predictions and naturally integrating these predictions into the NN algorithm. This method significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality.

Seminar and PhD Seminar on Combinatorics, Games and Optimisation:

2020/21, 2019/20

Seminar on Combinatorics, Games and Optimisation

2018/19, 2017/18, 2016/17, 2015/16

The Seminar on Combinatorics, Games and Optimisation started in 2016. It is a combination of two previous seminar series:

Seminar on Discrete Mathematics and Game Theory:

2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003