3 December 2009

Bas Lemmens (University of Kent)
Title: Nonlinear PerronFrobenius theory and stochastic games
Abstract: Properties of the value of a zerosum twoplayer 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 orderpreserving and additively homogeneous. It fits within the framework of nonlinear PerronFrobenius 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: ContextDependent 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. Contextladen forward induction may allow outcomes precluded by contextfree 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 BattigalliSiniscalchi [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 WelshPowell 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 (MaxPlanckInstitut 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 RiemannRoch 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 uniformweak topology is finer than the uniformstrategic topology and, around beliefs generated by finite type spaces, the strategic, uniformweak, and commonbelief topologies coincide. We then use our characterizations to provide strategic genericity results for finite type spaces and commonprior 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 ndimensional? infinitedimensonal? How small can a maximal equilateral set be in X? We also consider socalled 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 92073, Harvard University, 1992]. This result remained unpublished, and it relies on a specific tiebreaking rule.
Here we prove an extension of it by showing that the ordinal version of strategic complementarities suffices. The proof does not rely on tiebreaking rules and provides some intuition for the result.

25 June 2009

Marzena Rostek (University of WisconsinMadison)
Dynamic Thin Markets
Abstract: This paper concerns modelling bilateral market power. We present a dynamic model with market power which extends the generalequilibrium framework by incorporating price impact. The paper further establishes that the nonstrategic generalequilibrium 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 NitzanParoush 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 worstcase price of anarchy for pure Nash equilibria *necessarily* implies the exact same worstcase 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 regretminimization). 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 StoneCech 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 S_{n} is tintersecting 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 tintersecting family of permutations has size at most (nt)!, 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 HiltonMilner type result for tintersecting families, which generalizes the CameronKu 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 tsetwiseintersecting 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 pseudorandomness 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
Pretalk: Logic and Games

5 March 2009

David Sirl (University of Nottingham)
Quasistationary distributions for Markov chains: motivations, methods and (occasional) musings
Abstract: Quasistationary 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 R^{n} avoids distances d_{1}, ..., d_{N} if the distance between any two points in A is not d_{1}, ..., d_{N}. We consider the problem of determining the largest fraction of space that can be covered by a measurable set that avoids given distances d_{1}, ..., d_{N} or, in other words, the problem of determining the maximum density a set that avoids distances d_{1}, ..., d_{N} 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 1avoiding set (i.e., N = 1 and d_{1} = 1) for n = 2, ..., 24. This also implies better lower bounds for the measurable chromatic number of R^{n} for n = 3, ..., 24; the measurable chromatic number of R^{n} is the minimum number of 1avoiding measurable sets needed to partition R^{n}.
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 d_{0} such that for all d >= d_{0}, 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 decisionmaking in political bodies as well as collaboration in multiagent 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 stabilityrelated solution concepts in weighted voting games, such as the epsiloncore, 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 selforganized 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)
2colourings 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.


