Below you can find information about past seminars in this series from 2013. The seminars are listed in reverse chronological order, most recent first.
Friday 6 December - Nicola Wittur (LSE)
Online information transmission
I introduce a repeated game between a team of two players and nature. The team members have unequal knowledge about future states of nature in the following sense: while the second player (the follower) has no knowledge at all about the future, the first player (the prophet) is fully informed and is able to signal some of his knowledge to the follower via his action choices. The team’s stage payoff not only depends on both team members’ actions, but also on the state of nature. Therefore, the prophet would like to transmit as much of his knowledge about future states of nature as possible to the follower. At the same time, however, this information transmission may reduce the stage payoff. Under these circumstances, what is the best payoff the team can achieve?
This game is a simplified model of the problem of costly communication between agents (forming a team or a firm) who are faced with information asymmetries.
Friday 29 November - Ewan Davies (LSE)
The Erdos--Hajnal Conjecture
Call a graph non-Ramsey if it has no 'large' clique or independent set. The fact that random methods give by far the best lower bounds for two-colour Ramsey numbers, with explicit constructions currently coming nowhere close, has led to a sense that good non-Ramsey graphs must in some way be 'random-like'. A long-unsolved conjecture of Erdos and Hajnal states that, for fixed H, no large graphs without induced H can be non-Ramsey. I will make this idea precise and discuss some progress in solving the problem.
Friday 15 November - Pongphat Taptagaporn (LSE)
Universal Portfolios
We consider the problem of how to allocate our wealth among N assets such that to maximize utility. A 'universal portfolio' is obtained by taking a continuous integral over the convex set of possible portfolios with some pre-specified distribution. This talk will review the past research in this field, attempt to extend some current models, and talk about possible research directions.
Friday 25 October - Alex Gershkov (Jerusalem / Surrey)
Optimal Voting Rules
We study dominant strategy incentive compatible (DIC) and deterministic mechanisms in a social choice setting with several alternatives. The agents are privately informed about their preferences, and have single-crossing utility functions. Monetary transfers are not feasible. We use an equivalence between deterministic, DIC mechanisms and generalized median voter schemes to construct the constrained-e cient, optimal mechanism for an utilitarian planner. Optimal schemes for other welfare criteria such as, say, a Rawlsian maximin can be analogously obtained.
Joint work with Benny Moldovanu and Xianwen Shi.
Friday 18 October - Yi Zhao (Georgia State)
Minimum degree thresholds for Hamilton cycles in k-uniform hypergraphs
Given positive integers t<k, a k-uniform hypergraph (k-graph) is called a (k, t)-cycle if its vertices can be ordered cyclically such that each of its edges contains k consecutive vertices and two consecutive edges share exactly t vertices. We determine the minimum (k-1)-degree threshold that ensures a Hamilton t-cycle in a k-graph for all t< k/2, and the minimum 1-degree threshold that ensures a Hamilton 1-cycle in a 3-graph. This improves several asymptotic results obtained earlier.
This is a joint work with Jie Han.
Friday 11 October - Anita Liebanau (Warwick)
Fast strategies in Maker-Breaker games played on random boards
A Maker-Breaker game is defined as follows: Given a set X, called the board, and a subset F of the power set of X, called the family of winning sets, two players, Maker and Breaker, alternately claim elements of X. Maker wins if she claims all elements of some element in F. Otherwise, Breaker wins. We will see that, playing on the edge set of a sparse random graph G(n,p) with p > polylog(n)/n, a.a.s. Maker can claim a perfect matching, a Hamilton cycle or a k-connected spanning subgraph asymptotically as fast as possible, i.e. in n/2+o(n), n+o(n) and kn/2+o(n) moves respectively. Fast winning strategies for Maker may help to find winning strategies for the first player in so-called strong games, where both players try to occupy a winning set first.
Friday 5 July - Steffen Issleib (LSE)
Monte Carlo Simulation results for evolution of different trial and error Markov processes on cooperative games
A specific Markov trial and error process moving on the state space of generic cooperative games is simulated. The concept of asymmetric state structures is introduced and via simulation the behaviour of different processes along such structures for some example games are summarized. The concept of Markovian cooperative equilibrium is introduced via examples.
Friday 21 June - Gilad Bavly (Tel Aviv)
How to Gamble Against All Odds
Player 0, the cousin of the casino owner, is only allowed to bet sums of money within a set A (a subset of the real numbers). The regular casino players 1,2,3,... (countably many players) are only allowed to make bets within another set B. Player 0 announces her betting strategy first, then the regular players announce theirs. Now the casino owner wants to fix an infinite sequence of Reds and Blacks, such that player 0 makes infinite gains, while every regular player only gains a finite amount. Can this be done when, e.g., A is the set of all even integers, and B the set of all odds? We present some sufficient and necessary conditions on the pair of sets A and B.
This is joint work with Ron Peretz.
Friday 14 June – David L. Russell (Virginia Tech)
Computing Convex Spline Approximations
Abstract
Friday 7 June - Alexey Pokrovskiy (LSE)
Advantage in the discrete Voronoi game
We will study a model of competitive facility location known as the Voronoi game. In this game, two players take turns claiming the vertices of a graph for some fixed number of rounds. At the end of the game, the remaining vertices are distributed between the two players. Each player receiving the vertices which are closer to his claimed vertices than to his opponents. The winner is the player who controls the most vertices at the end of the game. We will focus on finding situations when one player can claim a large proportion of vertices.
This is joint work with Dániel Gerbner, Viola Mészáros, Dömötör Pálvölgyi, and Günter Rote.
Friday 24 May - Guus Regts (CWI, Amsterdam)
Graph parameters and invariants of the orthogonal group
An edge coloring model is a generalization of the Ising-Potts model of statistical mechanics. Partition functions of edge coloring models were introduced as graph parameters by de la Harpe and Jones (P. de la Harpe, V.F.R. Jones, Graph invariants related to statistical mechanical models: examples and problems, Journal of Combinatorial Theory, Series B 57, 207–227, 1993).
In this talk I will characterize which graph parameters are partition functions of complex edge coloring models. The proofs are based on the first and second fundamental theorem for the orthogonal group and on Hilbert’s Nullstellensatz.
This talk is based on joint work with Jan Draisma, László Lovász, Dion Gijswijt and Lex Schrijver.
Friday 17 May - Erik Mohlin (Oxford)
Optimal Categorization
This paper models categorizations that are optimal for the purpose of making predictions. A subject encounters an object (x; y), observes the first component, x, and has to predict the second component, y. The space of objects is partitioned into categories. The subject determines what category the new object belongs to on the basis of x, and predicts that its y-value will be equal to the average y-value among the past observations in that category. The optimal categorization minimizes the expected prediction error. The main results are driven by a bias-variance trade-off: The optimal size of a category around x, is increasing in the variance of y conditional on x, decreasing in the variance of the conditional mean, decreasing in the size of the data base, and decreasing in the marginal density over x.
Full details here.
Friday 22 March - Somkiat Trakultraipruk (LSE)
On the Complexity of Finding Shortest Paths between Token Configurations on Graphs
Abstract
Friday 15 March - Pongphat Taptagaporn (LSE)
Communication Algorithms in Gaussian Graphs
Gaussian graphs are a class of graphs induced by Gaussian integers. We look at communication protocols in these graphs such as routing, gossiping, transmitting. Studies of these graphs were previously motivated by coding theory as they were known to generate "perfect" codes. Thorough examination also shows that these graphs exhibit close connections to first-kind Frobenius graphs, circulant graphs and tori.
Friday 8 March - Elnaz Bajoori (Maastricht University)
Distributional Perfect Equilibrium in Bayesian Games with Applications to Auctions
In second-price auctions with interdependent values, bidders do not necessarily have dominant strategies. Moreover, such auctions may have many equilibria. To use the concept of trembling hand perfect equilibrium as a tool to rule out the less intuitive equilibria, we define the notion of distributional perfect equilibrium for Bayesian games with infinite type and action spaces. We prove that every Bayesian game has a distributional perfect equilibrium if the information structure of the game is absolutely continuous and the payoffs are equicontinuous. We apply distributional perfection to a class of symmetric second-price auctions with interdependent values and observe that a specific type of equilibrium is perfect, while many of less intuitive equilibria are not.
Friday 22 February - Tom Lidbetter (LSE)
Optimal search for k balls in n boxes
Suppose k balls are hidden in n>k boxes, each box with a given search cost. A Searcher chooses an ordering of the boxes and opens them in this order, paying the associated search costs until he finds all k balls. We view this as a zero-sum game between the Searcher who wishes to minimize the total cost of finding all the balls, and a malevolent Hider who wishes to maximize the total cost. We show that it is optimal for the Hider to choose a k-subset (subset of size k) of boxes H with probability p(H) proportional to the product of the search costs of the boxes in H. It is optimal for the Searcher to begin by searching a k-subset S of boxes in any order with probability p(S) and then search the rest of the boxes in a (uniformly) random order. We also give a simple formula for the value of the game, and we discuss extensions of the game where the players are permitted to adapt their strategies as they go along.
Friday 15 February - Maya Stein (University of Chile)
Small degree vertices in minimal bricks
An important tool in matching theory is Lovász' brick and brace decomposition for matching covered graphs. The final graphs of this decomposition are divided into bricks and braces. We are interested in bricks, it is known that these are exactly the 3-connected bicritical graphs. (Bicriticality here means that after deleting any two vertices, the remaining graph has a perfect matching.)
A brick is said to be minimal if upon deletion of any edge it ceases to be a brick. Norine and Thomas conjecture that every minimal brick has some fixed positive fraction of vertices of degree 3. We prove that every minimal brick on n vertices has at least n/9 vertices of degree at most 4.
This is joint work with Henning Bruhn.
Friday 8 February - Charl Ras (University of Melbourne)
Geometric range assignment and min-power centres
One of the most important problems in the optimal design of wireless ad hoc radio networks is that of power minimisation. The most appropriate model is the "power efficient range assignment problem", where communication ranges are assigned to all nodes such that total power is minimised, and where it is assumed that the power of each node is proportional to its assigned communication range raised to an exponent $\alpha>1$. Solving the range assignment problem whilst allowing for the introduction of a bounded number of additional nodes anywhere in the plane constitutes a very general and highly applicable geometric network problem, which has only been solved in certain restricted settings. A first step towards this goal is a solution to the "min-power centre problem", where exactly one new node is introduced. We use farthest point Voronoi diagrams and Delaunay triangulations to provide a complete geometric description of the min-power centre of a finite set of nodes in the Euclidean plane when cost is a quadratic function. This leads to a new sub-quadratic time algorithm for its construction. We also construct an upper bound for the performance of the centroid as an approximation to the quadratic min-power centre.
Friday 1 February - Peter Allen (LSE) and Ron Peretz (LSE)
Suggested reading
Topics included the entropy method (e.g. Imre Csiszar: "The Method of Types"; Ehud Friedgut: "Hypergraphs, Entropy, and Inequalities").
Friday 25 January - Miquel Oliu Barton (Paris)
The asymptotic value in finite stochastic games : a new approach
Stochastic games were introduced by Shapley in 1953, and the discounted value $v_\lambda$ was proved to exist for any discount factor $\lambda \in (0,1]$.The existence of $\lim_{\lambda\to 0} v_\lambda$ was established by Bewley and Kohlberg in 1976, using Tarski-Seidenberg projection theorem. No other proof was known so far for this celebrated result. In this talk we provide a new, direct and elementary proof for this result.