Home > Department of Mathematics > Seminars > Seminars on Discrete and Applicable Mathematics in 2013

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:

Click here for information on how to get to LSE using public transport and maps of the campus

# Seminars on Discrete and Applicable Mathematics in 2013

Below you'll find an overview of the 2013 seminars in this series. The seminars are listed in reverse chronological order, most recent first.

Thursday 12 December - Dominik Vu (Memphis)
Cops and Robber on the torus

The pursuit-evasion game "Cops and Robbers" has enjoyed some attention in both discrete mathematics and theoretical computer science. It concerns a set of cops chasing one or more robbers on a fixed graph. Natural questions to ask are those for the number of cops required to ensure capture in finite time, and for the number of steps required in this case. Previous work both asked these questions for all graphs of fixed order, as well as for certain classes of graphs where bounds may be better due to the underlying structure of the graph. Considering the n-dimensional torus, we determine the number of cops needed in order to capture a single robber and give bounds on the capture time.

Joint work with Sebastian Koch.

Thursday 5 December - Tereza Klimosova (Warwick)
Infinite dimensional finitely forcible graphon

Graphons are analytic objects associated with convergent sequences of graphs. Problems from extremal combinatorics and theoretical computer science led to a study of graphons determined by finitely many subgraph densities, which are referred to as finitely forcible. We show that there exists a finitely forcible graphon such that the topological space of its typical points has infinite Lebesgue covering dimension, disproving the conjecture by Lovasz and Szegedy.

The talk is based on joint work with Roman Glebov and Daniel Kral.

Thursday 28 November - John Yehuda Levy (Oxford)
Bayesian Games with Uncountable State Spaces

We discuss Bayesian games in which the state space is a standard Borel space. We address questions such as the existence of Bayesian equilibrium, common priors on common knowledge components, and others. It turns out that the existence of these is guaranteed if - and, to some extent, only if - the common knowledge sigma-algebra is countably generated. We discuss these results and related curiosities of these games.

Joint work with Ziv Hellman.

Thursday 21 November - Francis Edward Su (Cambridge, Harvey Mudd College)
A Polytopal Generalization of Sperner's Lemma

Abstract: Sperner's lemma is a combinatorial statement whose claim to fame is its equivalent to the Brouwer fixed point theorem in topology. In 2002, J. DeLoera and E. Peterson and I proved a generalization of Sperner's lemma to polytopes. In this talk, I'll demonstrate several proofs of the Polytopal Sperner Lemma that extend the classical proofs of the usual Sperner lemma, and I'll outline several applications that I have encountered since then in game theory and geometric combinatorics.

Thursday 14 November - Oded Lachish (Birkbeck, University of London)
Improved competitive ratio for the Matroid Secretary Problem

The Matroid Secretary Problem, introduced by Babaioff et al (2007), is a generalization of the Classical Secretary Problem. In this problem, elements from a matroid are presented to an on-line algorithm in a random order. Each element has a weight associated with it, which is revealed to the algorithm along with the element. After each element is revealed the algorithm must make an irrevocable decision on whether or not to select it. The goal is to pick an independent set with the sum of the weights of the selected elements as large as possible.

Babaioff et al gave an algorithm for the Matroid Secretary Problem with a competitive ratio of O(log(rho)), where rho is the rank of the matroid. It has been conjectured that a constant competitive-ratio is achievable for this problem. This will be about an algorithm that has a competitive ratio of O(sqrt(log(rho))).

This is joint work with Sourav Chakrabort.

Thursday 7 November - Andy Lewis-Pye (LSE)
Digital morphogenesis via Schelling segregation

Schelling's model of segregation looks to explain the way in which  particles or agents of two types may come to arrange themselves spatially into configurations consisting of large homogeneous clusters, i.e. connected regions consisting of only one type.
As one of the earliest agent based models studied by economists and perhaps the most famous model of self-organising behaviour, it also has direct links to areas at the interface between computer science and statistical mechanics, such as the  Ising model and  the study of contagion and cascading phenomena in networks.

While the model has been extensively studied it has largely resisted rigorous analysis, prior results from the literature generally pertaining to variants of the model which are tweaked so as to be  amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory.    In 2012, Brandt, Immorlica, Kamath and Kleinberg provided the first  rigorous analysis of the  unperturbed model,  for a specific set of input parameters.  Here we provide a rigorous analysis of the model's behaviour much more generally and establish some  surprising forms of threshold behaviour, notably the existence of situations where an increased level of intolerance for neighbouring agents of opposite type  leads almost certainly to decreased segregation.

This is joint work with George Barmpalias and Richard Elwes.

Thursday 31 October - Eilon Solan (Tel-Aviv)
Repeated Games with Costly Observations

Abstract: We study two-player discounted repeated games in which the players do not observe each other's actions nor their own stage payoff. Rather, after every stage, each player can pay a fixed amount c and observe the action that the other player has just played. We are interested in the game in which the time between stages is small, and the cost c is much smaller than that. We prove that the limit set of Nash equilibrium payoffs, as both the time between stages and the cost of observation go to 0, is equal to the set of public perfect equilibrium payoffs, and we provide a characterization to this limit set. Surprisingly this set is, in general, a strict subset of the set of feasible and individually rational payoffs.

Thursday 24 October - Chris Dowden (Royal Holloway)
Agreement Protocols in the Presence of a Mobile Adversary

Suppose various processors in a network wish to reach agreement on a particular decision. Unfortunately, some unknown subset of these may be under the control of a malicious adversary who desires to prevent such an agreement being possible.

To this end, the adversary will instruct his "faulty" processors to provide inaccurate information to the non-faulty processors in an attempt to mislead them. The aim is to construct an "agreement protocol" that will always foil the adversary and enable the non-faulty processors to reach agreement successfully (perhaps after several rounds of communication).

In traditional agreement problems, it is usually assumed that the set of faulty processors is "static", in the sense that it is chosen by the adversary at the start of the process and then remains fixed throughout all communication rounds. In this talk, we shall instead focus on a "mobile" version of the problem, providing results both for the case when the communications network forms a complete graph and also for the general case when the network is not complete.

Thursday 10 October - Frank Page (Indiana)
Approximable Discounted Stochastic Games and Stationary Markov Equilibria
Abstract available here

Thursday 4 July -  Rafael Villa University of Seville)
Brunn-Minkowski and other inequalities for convolution bodies

The Brunn-Minkowski inequality, regardless of its entirely geometric flavour, has been widely used as a very important tool for a series of fundamental problems in Mathematical Analysis. In this talk, after introducing the aforesaid inequality and some of its applications, we describe a modified Minkowski sum in Rⁿ. For the modified Minkowski sum we show its relation with a class of convex bodies named convolution bodies and provide a Brunn-Minkowski type inequality that extends the classical inequality. We provide some applications of this modified notion of sum to extend some classical inequalities in convex geometry of Zhang and Rogers and Shephard with proofs notably shorter than their classical counterparts still recovering their equality cases. Finally, we provide an extension of this notion to more than two bodies.

This is joint work with D. Alonso-Gutiérrez and C. Hugo Jiménez.

Thursday 27 June - Ryan Martin (Iowa State University)
Recent results on the edit distance in
graphs

In this talk, we will discuss the edit distance function, a function of a hereditary property $\mathcal{H}$ and of $p$, which measures the maximum proportion of edges in a density-$p$ graph that need to be inserted/deleted in order to transform it into a member of $\mathcal{H}$.  We will describe a method of computing this function and give some results that have been attained using it. The edit distance problem has applications in property testing and evolutionary biology and is closely related to well-studied Tur\'an-type problems.  The results we address will include cycle-free graphs and shows a close relationship between the problem of Zarankiewicz as well as strongly regular graphs.

This is joint work with Tracy McKay (Dickinson College) and Chelsea Peck (Iowa State University).

Thursday 20 June -  Yves Crama (Liege)
Quadratic reformulations of nonlinear binary optimization
problems

We consider the problem of minimizing a pseudo-Boolean function f(x), i.e., a real-valued function of 0-1 variables. Several authors have recently proposed to reduce this problem to the quadratic case by expressing f(x) as min{g(x,y): y in {0,1}}, where g is a quadratic function of x and of additional binary variables y. We establish lower and upper bounds on the number of additional y-variables needed in such a reformulation, both for the general case and for the special case of symmetric functions like positive or negative monomials, k-out-of-n majority functions, or parity functions.

This is joint work with Martin Anthony, Endre Boros and Aritanan Gruber.

Thursday 13 June -  Asaf Cohen (Tel Aviv)
Diffusion Approximations in Bayesian Hypothesis-Testing Models

The model of a decision maker that observes a Brownian motion with an unknown drift (and a known variance) is well explored in the literature; it appears in the context of filtering theory, optimal stopping time problems, and economics. In many cases the posterior distribution over the drift plays a key role in solving optimal stopping time problems (see, e.g., Shiryaev (1978), Gapeev and Peskir (2004), and Cohen and Solan (2012)).

In practical situations a Brownian motion is an approximation for discrete processes. I study a model in which a sequence of discrete processes is given; these processes depend on an unknown parameter $\theta$ with a known prior distribution. I assume that this sequence converges to a Brownian motion with drift $\theta$ (which is unknown but whose prior distribution is known). For each such discrete process, define a Bayesian posterior process about the parameter $\theta$, given the observations from that process. Similarly, define a Bayesian posterior process about the parameter $\theta$, given the observations from the Brownian motion. I show that, generally, the sequence of the Bayesian posterior processes does not converge to the Bayesian posterior process of the Brownian motion, unless the discrete processes are sufficiently stationary'. Therefore, it is incorrect to estimate the unknown parameter $\theta$ using the Brownian motion with the unknown drift. Surprisingly, it turns out that if the limit of the Bayesian posterior processes is not degenerate, then its structure is identical to that of the Bayesian posterior process of the Brownian motion; the only difference between the two processes is that they have different parameters. That is,the limit of the Bayesian posterior processes can be presented as a Bayesian posterior process of a Brownian motion with prior distribution about the unknown drift and adifferent standard deviation, which depends on the structure of the sequence of the discrete processes. This gives another motivation for analyzing the Bayesian posterior process of a Brownian motion with unknown drift

.

Thursday 30 May -  Oleg Pikhurko (Warwick)
On Possible Turan
Densities

The Turan density of a family F of k-graphs is the limit superior of the edge densities of F-free k-graphs. We show that the set of all possible Turan densities has cardinality of the continuum; in particular, it is strictly larger than Pi_k, the set of the Turan densities of finite k-graph families. On the other hand, we show that Pi_k contains every density realised by optimally blowing up a finite pattern. As an application, we derive that Pi_k contains an irrational number for every k at least 3.

Thursday 24 May -  Carolyn Chun (Brunel)
Fundamental questions in matroids

A matroid is a mathematical structure that generalizes the notion of linear independence in a matrix. In this talk, I will discuss recent progress on the most compelling open question in matroid theory, Rota’s conjecture.

Thursday 2 May -  Andrew Treglown (QMUL)
Minimum degree thresholds for perfect matchings in hypergraphs

A k-uniform hypergraph is a hypergraph in which every edge contains precisely k vertices. A perfect matching in a hypergraph H is a collection of disjoint edges which together cover all the vertices in H. A theorem of Tutte gives a characterisation of all those graphs which contain a perfect matching. On the other hand, the decision problem whether a k-uniform hypergraph contains a perfect matching is NP-complete for k>2. It is natural therefore to seek simple sufficient conditions, such as minimum degree conditions, that ensure a perfect matching in a k-uniform hypergraph. I will discuss recent work with Yi Zhao (Georgia State University) on this problem: Given positive integers k and r with k/2 ≤ r ≤ k−1, we give a minimum r-degree condition that ensures a perfect matching in a k-uniform hypergraph. This condition is best possible and improves on work of Pikhurko, who gave an asymptotically exact result.

Thursday 14 March - Yuval Heller (Oxford)

We study how the power to commit and to lie influences strategic interactions. Specifically, we extend symmetric 2-player games by adding a pre-play stage in which players can: (1) commit - restrict their set of possible actions to a smaller one, (2) lie - costly signalling a false commitment to the opponent, and (3) inspect - costly detecting the truth about the opponent's commitment. We characterize pure stable outcomes in any such game. Next, we present four applications (specific games), and characterize a unique stable outcome in each: (1) Prisoner's Dilemma - always defecting; (2) coordination games - the payoff - efficient outcome; (3) Hawk-Dove games - heterogeneous population of committed hawks and uncommitted agents pretending to be hawks; and (4) “Partnership” games - heterogeneous population of conditionally-cooperative agents and slightly-shirkers. Finally, we develop a methodology to study the evolution of preferences with endogenous observability of types.

Thursday 7 March - Mathias Staudigl (IMW, Bielefeld)
Stochastic Stability in Games

In this talk I will give an overview about new tools for equilibrium selection in games in the framework of stochastic evolutionary game theory. The talk is based on joint work with William H. Sandholm and Michel Benaim. In this project we investigate stochastic stability theory from a new angle. We elaborate on the precise role of the parameters in this game theoretic model, which are the population size and the level of noise in the agents' updating decisions. Stochastic stability theory is concerned with understanding the long-run properties of the stochastic evolutionary game dynamics when these parameters are taken to their respective limits separately, or simultaneously. For each possible way of taking limits, we present the appropriate technique to understand the long-run of the game dynamics. This requires a novel and interesting combination of various mathematical techniques, such as large deviations theory and optimal control. We also discuss the computational problem of stochastic stability in simple game settings.

Thursday 21 February - Marcus Pivato (Trent University, Peterborough, Canada)
Ranking Multidimensional Alternatives and Uncertain Prospects

We introduce a two-stage ranking of multidimensional alternatives, including uncertain prospects as particular case, when these objects can be given a suitable matrix form. The first stage defines a ranking of rows and a ranking of columns, and the second stage ranks matrices by applying natural monotonicity conditions to these auxiliary rankings. Owing to the Debreu-Gorman theory of additive separability, this framework is sufficient to generate very precise numerical representations. We apply them to three main types of multidimensional objects: streams of commodity baskets through time, monetary input-output matrices, and most extensively, uncertain prospects either in a social or an individual context of decision. Among other applications, the new approach delivers the strongest existing form of Harsanyi's (1955) Aggregation Theorem and casts light on the classic comparison between the *ex ante* and *ex post*Pareto principle. It also provides a novel derivation of subjective probability from preferences, in the style of Anscombe and Aumann (1963).

Joint work with Philippe Mongin (Paris).

Thursday 14 February - Krzysztof R. Apt (CWI and University of Amsterdam, The Netherlands)
Social Network Games

To better understand the spread of various products through a social network, in 2011 Apt and Markakis introduced a threshold model, in which the nodes influenced by their neighbours can adopt one out of several products. To analyze the consequences of such product adoption we associate with each such social network a natural strategic game between the agents.

In these games the payoff of each player weakly increases when more players choose his strategy, which is exactly opposite to the congestion games. The possibility of not choosing any product results in two special types of (pure) Nash equilibria.

We show that such games may have no Nash equilibrium and that determining an existence of a Nash equilibrium, also of a special type, is NP-complete. The situation changes when the underlying graph of the social network is a DAG, a simple cycle, or, more generally, has no source nodes. For these three classes we determine the complexity of an existence of (a special type of) Nash equilibria.

We also clarify for these three classes the status and the complexity of the finite best response property (FBRP), the finite improvement property (FIP), and of a new property that we call the uniform FIP.

Joint work with Sunil Simon.

Thursday 7 February - Ziv Hellman (Tel Aviv)
Bayesian Games over Continuum Many States

We present an example of a Bayesian game with a continuum of states that possesses no Bayesian approximate equilibria, resolving an open question since Simon (2003) showed the existence of a game with no Bayesian exact equilibria. To achieve this we show a close relationship between strategic considerations in overlapping generations games (a type of stochastic game ) and certain Bayesian games. That "bridge" enables us to use an example of Levy (2012) of a stochastic game with no stationary equilibria to attain the desired result.

That further naturally leads to the question of finding necessary and sufficient conditions for the existence of Bayesian equilibria in games with a continuum of states, a question that will also be resolved in the talk.

Thursday 31 January - Bernhard von Stengel (LSE)
Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)

Existence of an equilibrium in various economic models can be shown to exist by following a certain combinatorially defined path, for example of edges of a labelled polytope similar to the simplex algorithm for linear programming. In addition, such a path has a direction that defines the "index" of an equilibrium. Examples include Sperner's lemma about completely labelled simplices and Nash equilibria in games. We present a general model of "pivoting systems" that shows the essence of the path-following and the directedness argument. We also present a connection of bimatrix games where the paths are exponentially long with signed perfect matchings in Euler graphs, and an algorithm that gives a polynomial-time "shortcut" for these paths. We also present a concept of orientation for the "Euler complexes" or oiks introduced by Edmonds, which generalizes the orientability of abstract simplicial manifolds. Our exposition uses colourful pictures and examples wherever possible.

Joint work with L. Vegh

Thursday 24 January - Dvir Falik (Queen Mary)
An Algebraic Proof of a Robust Social Choice Impossibility Theorem

A central theme in social choice theory is that of impossibility theorems, such as Arrow's theorem and the Gibbard-Satterthwaite theorem, which state that under certain natural constraints, social choice mechanisms are impossible to construct. In recent years, beginning in Kalai01, much work has been done in finding \textit{robust} versions of these theorems, showing "approximate" impossibility remains even when most, but not all, of the constraints are satisfied. We study a spectrum of settings between the case where society chooses a single outcome (\'a-la-Gibbard-Satterthwaite) and the choice of a complete order (as in Arrow's theorem). We use algebraic techniques, specifically representation theory of the symmetric group, and also prove robust versions of the theorems that we state. Our relaxations of the constraints involve relaxing of a version of "independence of irrelevant alternatives", rather than relaxing the demand of a transitive outcome, as is done in most other robustness results.

Joint work with Ehud Friedgut.

Thursday 17 January - Peter Windridge (Queen Mary)
Law of large numbers for the SIR epidemic on a random graph with given vertex degrees

We consider the limiting behaviour of the SIR epidemic model on a random graph chosen uniformly subject to having given vertex degrees.

In the model, each vertex is either susceptible, infective or recovered.  Infective vertices infect their susceptible neighbours, and recover, at a constant rate.  Initially there is only one infective vertex.

The infection and recovery rates, together with the limiting vertex degree distribution, determine a 'growth' parameter for the disease.  If this parameter is below a (specified) critical threshold then, with high probability, only a small number of vertices ever get infected.

Above the threshold there is a positive probability that many vertices get infected.

After that, the evolution of the epidemic is almost deterministic in the sense that key quantities, such as the fraction of infective vertices, are concentrated around the solutions to certain ordinary differential equations.

I'll sketch our new proof of these results.  Compared to existing approaches, ours surmounts a technical assumption on the degree sequence and is simpler.

This is joint work with Malwina Luczak and Svante Janson.

Share:|||