Home > Department of Mathematics > Seminars > Archive - past years > Seminar Abstracts for 2009

Contact and Address Details

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 directions to LSE and maps of the campus

Seminar Abstracts for 2009

 

3 December 2009

Bas Lemmens  (University of Kent)

Title: Non-linear Perron-Frobenius theory and stochastic games

Abstract: Properties of the value of a zero-sum two-player stochastic game with perfect information and finite states, are related to the iterative behaviour of the dynamic programming (Shapley) operator. This operator has two characteristic properties; namely, it is order-preserving and additively homogeneous. It fits within the framework of non-linear Perron-Frobenius theory. In this talk I will discuss some of my work on this theory in the context of stochastic games.

 

26 November 2009

Pierpaolo Battigalli (Innocenzo Gasparini Institute for Economic Research) 

Title: Context-Dependent Forward Induction Reasoning

Abstract: This paper studies the case where a game is played in a particular context. The context influences what beliefs players hold. As such, it may affect forward induction reasoning: If players rule out specific beliefs, they may not be able to rationalize observed behavior. The effcts are not obvious. Context-laden forward induction may allow outcomes precluded by context-free forward induction. At the formal level, forward induction and contextual reasoning are defined within an epistemic structure. In particular, we represent contextual forward induction reasoning as "rationality and common strong belief of rationality" (RCSBR) within an arbitrary type structure. (The concept is due to Battigalli-Siniscalchi [6, 2002].) We ask: What strategies are consistent with RCSBR (across all type structures)? We show that the RCSBR is characterized by a solution concept we call Extensive Form Best Response Sets (EFBRS's). We go on to study the EFBRS concept in games of interest.

 

19 November 2009

Mariko Hagita (Ochanomizu University, Tokyo)

Title: Colouring Algorithms and Dispersive Colouring of Graphs

Abstract: We improve the Welsh-Powell algorithm for colouring graphs and construct a colouring algorithm which use less than the maximum number of minimum degree of some subgraphs plus 1 colours. And introduce our study on dispersive colouring.

 

29 October 2009

Madhusudan Manjunath  (Max-Planck-Institut für Informatik)

Title: Voronoi Diagram of lattices under a simplicial distance function and its applications to the study of graphs

Abstract:  For an undirected connected graph, we associate a lattice that we call the Laplacian lattice of the graph. We describe the Voronoi diagram of this lattice under a certain simplicial distance function and use the properties of this Voronoi diagram to obtain a geometric proof of the Riemann-Roch theorem for graphs [Baker and Norine, Advances in Mathematics, 2007]. We also discuss its applications to algorithmic and classification problems.

Joint Work with Omid Amini, École Normale Supérieure, Paris.

 

22 October 2009

Alfredo Di Tillio (Bocconi University, Milan, Italy)

Title: Rationalizability and strategic topologies

Abstract:We characterize strategic topologies -- topologies on the players' beliefs defined in terms of continuity of the strict rationalizable correspondence in all incomplete information games -- by introducing and establishing connections with various topologies defined explicitly on beliefs. We prove that the uniform-weak topology is finer than the uniform-strategic topology and, around beliefs generated by finite type spaces, the strategic, uniform-weak, and common-belief topologies coincide. We then use our characterizations to provide strategic genericity results for finite type spaces and common-prior type spaces.

 

15 October 2009

Konrad Swanepoel (LSE)

Equilateral sets

Abstract: A set of points in a normed space X is equilateral if the distance between any two points is the same. How many points can an equilateral set have if X is n-dimensional? infinite-dimensonal? How small can a maximal equilateral set be in X? We also consider so-called subequilateral sets and their applications.

 

8 October 2009

Ulrich Berger (Vienna University of Economics and Business) 

Learning in games with strategic complementarities 

Abstract: Fictitious play is a classical learning process for games, and games with strategic complementarities are an important class including many economic applications. Knowledge about convergence properties of fictitious play in this class of games is scarce, however. Beyond games with a unique equilibrium, global convergence has only been claimed for games with diminishing returns [V. Krishna, Learning in games with strategic complementarities, HBS Working Paper 92-073, Harvard University, 1992]. This result remained unpublished, and it relies on a specific tie-breaking rule.

Here we prove an extension of it by showing that the ordinal version of strategic complementarities suffices. The proof does not rely on tie-breaking rules and provides some intuition for the result.

 

25 June 2009

Marzena Rostek (University of Wisconsin-Madison)

Dynamic Thin Markets

Abstract: This paper concerns modelling bilateral market power. We present a dynamic model with market power which extends the general-equilibrium framework by incorporating price impact. The paper further establishes that the nonstrategic general-equilibrium approach and the strategic approach to market interactions via Nash in demands are dual representations of a model with endogenous price impact. We argue that bilateral market power yields unique predictions in a large class of models based on a uniform price.

The model is then applied to study asset pricing. It is now well understood that in many markets institutional investors have a significant impact on prices and mitigate its adverse effects through their trading strategies. We show that modelling asset pricing with a bilaterally oligopolistic market structure qualitatively changes equilibrium properties of prices and dynamic trading strategies, compared to the existing theories of asset pricing. This allows us to understand a number of phenomena, which are hard to reconcile with the previous models, and arise naturally on the equilibrium path with price making agents.

 

18 June 2009

Shmuel Zamir (Hebrew University of Jerusalem)

Condorcet Jury Theorem: The dependent case

Abstract: We provide an extension of the Condorcet Jury Theorem (CJT), which states that with high probability, the majority decision of a large number of jurors is correct. Of interest are the assumptions about the signals the jurors get about the case. Our model includes both the Nitzan-Paroush framework of "unequal competencies" and Ladha's model of "correlated voting by the jurors." We assume that the jurors behave "informatively"; that is, they do not make a strategic use of their information in voting. For a general (dependent) distribution P we provide necessary as well as sufficient conditions for the CJT that establishes the validity of the CJT for a domain that strictly (and naturally) includes the domain of independent jurors. In particular we provide a full characterization of the exchangeable distributions that satisfy the CJT.

A PDF for this talk can be found here

 

11 June 2009

Tim Roughgarden (Stanford University)

Intrinsic Robustness of the Price of Anarchy

Abstract: The price of anarchy, the most popular measure of the inefficiency of selfish behavior, assumes that players successfully reach some Nash equilibrium. We prove that for most of the classes of games in which the price of anarchy has been studied, results are "intrinsically robust" in the following sense: an upper bound on the worst-case price of anarchy for pure Nash equilibria *necessarily* implies the exact same worst-case upper bound for a much larger sets of outcomes, including mixed Nash equilibria, correlated equilibria, and sequences of outcomes generated by natural experimentation strategies (such as successive best responses or simultaneous regret-minimization). Byproducts of our work include several new results for the inefficiency of equilibria in congestion games.

 

4 June 2009

Dona Strauss (University of Hull)

The semigroup βN

Abstract: If S denotes a discrete semigroup, its semigroup operation can be extended to its Stone-Cech compactification β S. The algebra of the semigroup β S has applications in combinatorics, providing concise proofs and new extensions of theorems such as Hindman's Theorem or van der Waerden's Theorem.

 

14 May 2009

Elena Boguslavskaya

Appell functions: a new way to solve perpetual optimal stopping problems for processes with independent stationary increments

Abstract: In this talk we generalize the result of Novikov and Shiryaev, where they constructed Appell functions to solve the perpetual optimal stopping problem with a power reward function for a process with independent stationary increments (a Levy process or a random walk). We construct a similar function to solve the optimal stopping problem for any continuous reward function. Our construction is based on Esscher transform and Inverse Laplace transform and is different from the one received by Surya.

 

26 March 2009

Tirthankar Bhattacharyya (Indian Institute of Science Bangalore)

Completely Bounded Kernels

Abstract: Starting with positive definite matrices, we shall show how positive definite kernels arise naturally. There has been a vast generalization of positive definite kernels in the last few years. These are called completely positive kernels. These kernels also generalize completely positive maps. A closely related concept is that of completely bounded maps. We shall discuss kernels which are completely bounded.

 

19 March 2009

David Ellis (University of Cambridge)

Intersection theorems in the symmetric group

Abstract: We say a family of permutations in Sn is t-intersecting if any two permutations in it agree on at least t points. Deza and Frankl conjectured that if n is sufficiently large depending on t, a t-intersecting family of permutations has size at most (n-t)!, with equality if and only if it is a coset of the stabilizer of t points. A proof of was the subject of a recently submitted paper of the speaker, Ehud Friedgut and Haran Pilpel. We will sketch this proof, which uses techniques from algebraic combinatorics and representation theory. We will also show how to obtain a Hilton-Milner type result for t-intersecting families, which generalizes the Cameron-Ku conjecture, using a stability analysis and some extra combinatorial arguments. If time permits we will discuss the solution of a recent conjecture of Janos Korner on t-setwise-intersecting families of permutations, the analogous results for the alternating group, and some other applications of representation theory in extremal combinatorics.

 

12 March 2009

Rahul Santhanam (University of Edinburgh)

Pseudorandomness

Abstract: Randomness is an important tool in the design of algorithms and cryptographic protocols - unbiased and independent random bits are often assumed to be freely available. However randomness as found in the real world is limited or flawed. The theory of pseudo-randomness studies how to derive useful randomness from real randomness - it does so by treating the primary characteristic of useful algorithms, their efficiency, as a limitation that can be exploited. I will describe some of the basic notions and insights of this theory, and sketch connections with combinatorics, complexity and cryptography.

 

11 March 2009

Joint CDAM and Choice Group Seminar   - Jacques Duparc (HEC Lausanne)

Infinite Games and the Foundations of Mathematics

Pre-talk: Logic and Games

 

5 March 2009

David Sirl (University of Nottingham)

Quasi-stationary distributions for Markov chains: motivations, methods and (occasional) musings

Abstract: Quasi-stationary distributions are an important tool in the analysis of Markov chains which have an absorbing state. I will discuss their usefulness, outline their theory and application and describe some current and future research directions. 

 

26 February 2009

Fernando Mário de Oliveira Filho (CWI, Amsterdam)

Linear programming, harmonic analysis, and densities of distance avoiding sets in Euclidean space

 Abstract: A subset A of Rn avoids distances d1, ..., dN if the distance between any two points in A is not d1, ..., dN. We consider the problem of determining the largest fraction of space that can be covered by a measurable set that avoids given distances d1, ..., dN or, in other words, the problem of determining the maximum density a set that avoids distances d1, ..., dN can have. We present a general method, based on linear programming and harmonic analysis, that provides an upper bound for this maximum density.

Our method gives improved upper bounds for the maximum density of a 1-avoiding set (i.e., N = 1 and d1 = 1) for n = 2, ..., 24. This also implies better lower bounds for the measurable chromatic number of Rn for n = 3, ..., 24; the measurable chromatic number of Rn is the minimum number of 1-avoiding measurable sets needed to partition Rn.

Finally, an immediate consequence of our approach is a short proof of a generalization of the following result of Furstenberg, Katznelson, and Weiss: if a measurable set A has positive density, then there is a number d0 such that for all d >= d0, there are two points in A at distance d from each other.

 

19 February 2009

Edith Elkind (University of Southampton) 

Computational aspects of stability in weighted voting games

 Abstract: Weighted voting games are a simple, but expressive class of coalitional games that can be used to model decision-making in political bodies as well as collaboration in multi-agent systems. In such settings, stability of the grand coalition is an important consideration: the gains from the collaboration should be distributed in such a way that the agents' incentives to deviate from the grand coalition are minimized. In this talk, we will discuss the computational complexity of several stability-related solution concepts in weighted voting games, such as the epsilon-core, the least core and the nucleolus. While computing many of these solution concepts appears to be hard, we will describe recent pseudopolynomial and approximation algorithms that mitigate the hardness results.

Based on joint work with Leslie Ann Goldberg, Paul Goldberg, Michael Wooldridge (University of Liverpool) and Dmitrii Pasechnik (NTU, Singapore).

 

29 January 2009

Christian Elsholtz (Royal Holloway, University of London)

Multidimensional problems in additive combinatorics

Abstract: We discuss bounds on extremal sets for problems like those below:

1) What is the largest subset of (Z/nZ)r that does not contain an arithmetic progression of length k?
2) What is the largest subset/(multiset) of (Z/nZ)r that does not contain n elements that sum to 0?
3) What is the largest subset of [1,...,n]r that does not contain a solution of x+y=z (ie which is a sum free set)?
4) Colour the elements of [1,..., n]r red and blue. How many monochromatic Schur triples are there? 

 

22 January 2009

Antal A. Járai  (University of Bath)

Abelian sandpiles on infinite graphs

Abstract: The Abelian sandpile model was introduced by physicists Bak, Tang and Wiesenfeld in 1987, as a simple model of self-organized criticality. The model has a rich mathematical structure, with connections to Abelian groups, random walk, spanning trees, determinantal processes, and 2D conformal invariance. I will give an introduction to the basic properties of this model, and discuss results that extend it to infinite graphs.

 

15 January 2009

Andrew Thomason (University of Cambridge)

2-colourings of complete graphs

Abstract: Motivated by applications in Ramsey games, random hereditary properties, and edit distance (property testing), we consider the extremal theory for graphs whose edges are coloured red and blue (or green, which is a wild colour). The theory includes the classical extremal theory for graphs but it is more involved. However, a reasonable, useful and sometimes surprising theory emerges in the end.

 

 

 

 

Share:Facebook|Twitter|LinkedIn|

CDAM@LSE logo