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 from 12.00 - 13:00.

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

Upcoming speakers

Thursday 1 December - Sharat Ibrahimpur (LSE)
Hybrid - 14:00 on Zoom, and PAR.2.03

Stochastic Minimum Norm Combinatorial Optimization
In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. The goal is to find a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm. We give a framework for designing approximation algorithms for stochastic minimum-norm optimization and use it to obtain approximation algorithms for stochastic min-norm versions of load balancing and spanning tree problems.

Joint work with Chaitanya Swamy. A full version of our results can be found in the speaker's PhD thesis with the same title.

Friday 2 December - Alp Muyesser (UCL)
Hybrid - 12:00 on Zoom, and PAR.2.03

Matchings in hypergraphs defined by groups
When can we find perfect matchings in hypergraphs whose vertices represent group elements and edges represent solutions to systems of (linear) equations? Problems expressible in this language include the Hall-Paige conjecture, the n-queens problem, Graham-Sloane harmonious tree-labelling conjecture, Ringel's sequencability conjecture, Snevily's subsquare conjecture, Friedlander-Gordon-Tannenbaum conjecture, and many others. In this talk we discuss a novel approach to attack these problems.

Thursday 8 December - Tom Gur (University of Warwick)
Hybrid - 14:00 on Zoom, and PAR.2.03

Worst-Case to Average-Case Reductions via Additive Combinatorics
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time O(T \log T) that are correct *on all* inputs.
Using our framework, we obtain such efficient worst-case to average-case reductions for fundamental problems in a variety of computational models; namely, algorithms for matrix multiplication, streaming algorithms for the online matrix-vector multiplication problem, and static data structures for all linear problems as well as for the multivariate polynomial evaluation problem.
Our techniques crucially rely on additive combinatorics. In particular, we show a local correction lemma that relies on a new probabilistic version of the quasi-polynomial Bogolyubov-Ruzsa lemma.

Joint work with Vahid Asadi, Alexander Golovnev, and Igor Shinkar (STOC ’22).

Friday 9 December - Bento Natura (Georgia Tech)
Hybrid - 12:00 on Zoom, and PAR.2.03

Title and abstract TBC.

Previous seminars in the series:

Friday 18 November - Michael Savery (University of Oxford)

Invertibility of digraphs and tournaments: computational complexity and other aspects
For an oriented graph %%D%% and a set %%X\subseteq V(D)%%, the inversion of X in %%D%% is the digraph obtained by reversing the orientations of the edges of %%D%% with both endpoints in %%X%%. The inversion number of %%D%%, %%\operatorname{inv}(D)%%, is the minimum number of inversions which can be applied in turn to %%D%% to produce an acyclic digraph. Bang-Jensen, da Silva, and Havet recently posed a series of interesting conjectures and questions concerning inversions and inversion number; in this talk we will discuss the resolution of several of them. A particular focus will be the computational complexity of deciding for fixed %%k\in \mathbb{N}%% whether an input digraph %%D%% satisfies %%\operatorname{inv}(D)\leq k%%. We will see that in general this problem is NP-complete, but that when the input is restricted to tournaments %%T%% it can be solved in time %%O(|V(T)|^2)%%. These two results respectively confirm a conjecture and answer a question of the above group of authors.

This is joint work with Emil Powierski, Alex Scott, and Elizabeth Wilmer.

Thursday 17 November - Yani Pehova (LSE)

Transversal factors and spanning trees
In this talk we consider a recent transversal, or rainbow, variant of the classical question: for which d do n-vertex graphs with minimum degree d always contain a fixed subgraph H? We consider a collection of graphs %%G_1,G_2,...,G_m%% on the same set of n vertices whose minimum degree is at least d, and ask which d guarantee the existence of a fixed (m-edge) subgraph H using exactly one edge from each %%G_i%%. The obtained copy of H is called a transversal, or a rainbow copy if we view each %%G_i%% as a different colour. We give the correct minimum degree threshold for the existence of rainbow spanning trees with maximum degree %%o(n/\log n)%% and perfect F-tilings in this setting. This is joint work with Alp Müyesser and Richard Montgomery.

Friday 11 November - Mark Voorneveld (Stockholm School of Economics)

No bullying! A playful proof of Brouwer's fixed-point theorem
Consider a finite number of children, each with a single indivisible good (a toy) and preferences over those toys. Let's say that a group of children, possibly after exchanging toys, can bully some poor kid if all group members find their own current toy better than the toy of this victim. We provide an algorithmic proof of a "no-bullying lemma", which asserts that some group S of children can redistribute their toys among themselves in such a way that all members of S get their favorite toy from S, but they cannot bully anyone. This combinatorial lemma is a key ingredient in an elementary proof of Brouwer's fixed-point theorem. The only mathematical prerequisite is a version of the Bolzano-Weierstrass theorem: a sequence in a compact subset of n-dimensional Euclidean space has a convergent subsequence with a limit in that set.

Thursday 10 November - Andrea Celli (Bocconi University)

Online bidding in repeated auctions under long-term constraints
Budget-management systems are one of the key components of modern auction markets. Internet advertising platforms typically offer advertisers the possibility to pace the rate at which their budget is depleted, through budget-pacing mechanisms. In this setting, the (proxy) bidder is confronted with a series of advertising opportunities, and wants to maximize their expected reward without violating a finite set of resource constraints. The case of repeated second-price auctions is well-understood. In this talk, I will present a general framework for online learning problems with long-term constraints which can be applied, for example, to online bidding problems in repeated first-price auctions. The results are based on the adversarial bandits with knapsack framework. Our framework yields the first best-of-both-worlds type algorithm for this setting, with no-regret guarantees both under stochastic and adversarial inputs. When budgets grow at least linearly in the time horizon, it allows us to provide the first constant-factor competitive ratio for this setting in the adversarial case.

Friday 4 November - Tamio-Vesa Nakajima (University of Oxford)

Linearly Ordered Hypergraph Colouring
Consider a set of products, and subsets of r products that are, in some sense, comparable. Suppose we want to assign these products k ratings such that each set of comparable products has a clear best product i.e. a unique product with maximum rating. Such a collection of products can be seen as an r-uniform hypergraph, and such an assignment is called a linearly ordered colouring of that hypergraph. In this talk we will explore various promise problems dealing with linearly ordered Hypergraph colourings. In particular, we will explain a state-of-the-art algorithm for finding a linearly ordered colouring when we are promised that a linearly ordered colouring with 2 colours exists; and we will also discuss some intractable problems of this kind.

Friday 28 October - Sahar Jahani (LSE)

Automated Equilibrium Analysis of 2 × 2 × 2 Games
The set of all Nash equilibria of a non-cooperative game with more than two players is defined by equations and inequalities between nonlinear polynomials, which makes it challenging to compute. In this talk, we present an algorithm that computes this set for the simplest game with more than two players with arbitrary (possibly non-generic) payoffs, which has not been done before. We give new elegant formulas for completely mixed equilibria, and compute visual representations of the best-response correspondences and their intersections, which define the Nash equilibrium set. These have been implemented in Python and will be part of a public web-based software for automated equilibrium analysis.

Thursday 27 October - Matías Pavez-Signé (University of Warwick)

Counting spanning subgraphs in dense hypergraphs
In the 1990s, Bollobás and Bondy posed the question of estimating the number of distinct Hamilton cycles in graphs with large minimum degree. This question was solved by Cuckler and Kahn in 2009, who found precise estimates on both the number of Hamilton cycles and perfect matchings in graphs with large minimum degree. In recent years, there have been some efforts to extend this question in uniform hypergraphs. In this talk, we will introduce a technique that allows us to estimate the number of distinct copies of some families of spanning hypergraphs in k-graphs with large minimum degrees. In particular, we can estimate the number of distinct Hamilton l-cycles in hypergraphs with minimum codegree above the threshold for Hamiltonicity. This is joint work with Richard Montgomery.

Thursday 20 October - Daniel Kráľ (Masaryk University)

Common graphs with arbitrary large chromatic number
A graph is common if the number of its monochromatic copies in a 2-edge-coloring of a large complete graph is minimized by the random 2-edge-coloring. This notion goes back to the work of Erdős in the 1960s, who conjectured that every complete graph is common. The conjecture was disproved by Thomason in the 1980s, however, a classification of common graphs remains one of the most intriguing problems in extremal combinatorics.
Sidorenko's Conjecture (if true) would imply that every bipartite graph is common, and in fact, no bipartite common graph unsettled for Sidorenko's Conjecture is known. Until Hatami et al. showed that a 5-wheel is common about a decade ago, common graphs with chromatic number two or three only were known. We establish the existence of (connected) common graphs with arbitrarily large chromatic number.

The talk is based on joint work with Jan Volec and Fan Wei.

Friday 14 October - Research Catch-up
Hybrid - 12:00 on Zoom, and PAR.2.03

Speakers Robert Simon, Aled Williams, Yani Pehova, Mahsa Dalirrooyfard, Domenico Mergoni, and Sharat Ibrahimpur will speak about their research for 5-7 minutes each.

Wednesday 12 October - Nathan Klein (University of Washington)

A Deterministic Better-Than-3/2 Approximation Algorithm for Metric TSP
I will describe a deterministic algorithm with an approximation ratio below 3/2 for the metric traveling salesperson problem (TSP). The algorithm builds on recent work which showed the same ratio was achievable by a randomized algorithm; here, we show that the analysis in the prior work can be implemented in polynomial time. In this talk, I will assume no familiarity with prior work and give a relatively self-contained proof for a simple case. Our arguments rely on properties of strong Rayleigh distributions, the structure of near minimum cuts, and the fact that the generating polynomial of lambda-uniform spanning trees can be efficiently evaluated. Based on joint work with Anna Karlin and Shayan Oveis Gharan.

Friday 7 October - Abraham Neyman (The Hebrew University of Jerusalem)
Hybrid - 12:00 on Zoom, and PAR.2.03

Stochastic games with limited memory space
Uniform e-optimal strategies in two-person zero-sum stochastic games that use little public memory space (explicitly, O(log n) memory states are used in the first n stages of the game) are introduced, and it is shown that any strategy in the Big Match that uses a finite public memory is worthless.

Joint work with Kristoffer Arnsfelt Hansen and Rasmus Ibsen-Jensen.

Thursday 6 October - Kalina Petrova (ETH Zurich)

Size-Ramsey numbers of graphs with maximum degree three
The size-Ramsey number %%\hat{r}(H)%% of a graph %%H%% is the smallest number of edges a (host) graph %%G%% can have, such that for any red/blue colouring of %%G%%, there is a monochromatic copy of %%H%% in %%G%%. Recently, Conlon, Nenadov and Truji\'c showed that if %%H%% is a graph on %%n%% vertices and maximum degree three, then %%\hat{r}(H) = O(n^{8/5})%%, improving upon the upper bound of %%n^{5/3 + o(1)}%% by Kohayakawa, R\"odl, Schacht and Szemer\'edi. In joint work with Nemanja Dragani\'c (ETH Z\"urich), we show that %%\hat{r}(H)\leq n^{3/2+o(1)}%%. While the previously used host graphs were vanilla binomial random graphs, we prove our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods.

Friday 30 September - Simon Jantschgi (University of Zurich & Grenoble-Alpes)

Markets and Transaction Costs
Transaction costs are omnipresent in markets but are often omitted in economic models. In markets in which the price is set to equate revealed supply and demand, we show that the presence of transaction costs can fundamentally alter incentive and welfare properties.
We categorize transaction costs into two types. Asymptotically uninfluenceable transaction costs— such as fixed and price fees—preserve the key properties of markets without transaction costs, namely asymptotic strategyproofness, efficiency, and robustness to misspecified beliefs and to aggregate uncertainty.
In contrast, influenceable transaction costs—such as spread fees—lead to complex strategic behavior (price guessing) that may result in severe market failure.
Considering a social planner with a given objective function, we show that the same categorization determines their behavior.
Any asymptotically uninfluenceable transaction cost can maximize the objective function if optimally scaled, while purely influenceable transaction costs lead to zero revenue. Furthermore, all asymptotically uninfluenceable optimally-scaled transaction costs lead to the same welfare. Our insights extend beyond markets equalizing demand and supply.

Thursday 29 September - Zoltan Szabo (LSE)

Support Vector Machines with Hard Shape Constraints
Shape constraints enable one to incorporate prior knowledge into predictive models in a principled way with numerous successful applications. Including this side information in a hard fashion (for instance, at each point of an interval) for rich function classes however is a quite challenging task. I am going to present a convex optimization framework to encode hard affine constraints on function values and derivatives in the flexible family of kernel machines. The efficiency of the approach will be demonstrated in joint quantile regression (analysis of aircraft departures), convoy localization and safety-critical control (piloting a submarine vehicle while avoiding obstacles). [This is joint work with Pierre-Cyril Aubin-Frankowski. Preprint.

Thursday 22 September - Lucas Pahl (University of Bonn)

Robustness of Equilibria in Generic Extensive-Form Games
We prove the 2-player, generic extensive-form case of the conjecture of Govindan and Wilson (1996, 1997) and Hauk and Hurkens (2002) stating that an equilibrium component is essential in every equivalent game if and only if the index of the component is nonzero. This provides an index-theoretic characterization of the concept of hyperstable components of equilibria in generic extensive-form games, first formulated by Kohlberg-Mertens (1986). We explore consequences of the result for the literature on refinements.
Joint work with Carlos Pimienta (University of New South Wales, Sydney)

Friday 16 September - Dana Pizarro (Université Toulouse 1 Capitole)

Competition and Recall in Selection Problems
In this talk, I will present an extension of the prophet inequality problem to a competitive setting. At every period, a new sample from a known distribution arrives, which is publicly observed. Then, two players simultaneously decide whether to pick an available value or to pass and wait until the next period (ties are broken uniformly at random). As soon as a player gets one sample, he leaves the market, and his payoff is the value of the sample. In a first variant, namely no recall case, the agents can only bid in each period for the current value. In a second variant, the full recall case, the agents can also bid at each period for any of the previous samples that have not been already selected. For each variant, we study the two-player game induced by the optimal stopping problem, focusing on subgame-perfect Nash equilibria. In particular, I will describe the set of subgame-perfect Nash equilibria payoffs, I will compare the two model variants in terms of the payoffs of the players and I will provide tight bounds for the Price of Anarchy and Price of Stability of the former setting when the number of arrivals is two.

Joint work with Fabien Gensbittel and Jérôme Renault (TSE).

Seminar and PhD Seminar on Combinatorics, Games and Optimisation:

2021/22, 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