|
27th November 2009
|
Julian Merschen (LSE)
Title: n-Person Games, Scarf's Lemma and its Complexity
Abstract: Scarf showed that the core of an n-person game is non-empty by using an algorithmic pivoting algorithm to prove his famous Scarf's lemma, implying the non-emptiness of the core (1967). We present this algorithm and give an overview of a recent result analysing the complexity of the algorithm. Applying Todd's orientation technique, the complexity to solve Scarf's lemma is in PPAD and PPAD-complete by reducing Hypergraphic Preference Systems to Scarf.
|
|
20th November
2009
|
Jan van den Heuvel (LSE)
Title: Degrees of Perfectness
Abstract: In all areas of mathematics there exist obvious relations between certain parameters, and often those relations appear in the form of aninequality: parameter 1 is always smaller than or equal to parameter 2.
This kind of relations immediately raises the question under what conditions we have equality.
One of the fundamental examples of this in graph theory is the trivial observation that the clique number of a graph is at most the chromatic number of that graph. The question 'when are they equal?' lead to the introduction of perfect graphs.
In this talk I will put the area of perfect graphs into a more general setting, in terms of collections of subsets of some finite set.
It appears that even in a much more general setting it is almost impossible to get away from perfect graphs.
|
|
13th November 2009
|
Alexey Pokrovskiy (LSE)
On the growth of graph powers
Abstract: We study the rate of growth in the size of a graph when taking iterated powers; obtaining a linear bound bearing some relation to results in additive combinatorics.
|
|
6th November 2009
|
Ahmad Abu-Khazneh (LSE)
Primality is in P: The AKS Algorithm
Abstract: AKS Primality Test is the first known deterministic primality-proving algorithm, created in 2002. We outline the algorithm and explain some of the underlying concepts from number theory and algorithmic complexity.
|
|
30th October 2009
|
Marta Casetti (LSE)
On a lemma by Scarf and fractional kernels
Abstract: A theorem (originally a lemma) published by Scarf in 1967 can be used to prove existence theorems as the one on fractional kernels of digraphs given by Aharoni and Holzman in 1995.
|
|
23rd October 2009
|
Robbert Fokkink (Technical University of Delft)
A resource allocation game on the circle
Abstract: We consider the following win-lose game on a circle. Player I picks a measure M of total mass y. Player II picks an interval I of length x.
Player I wins if M(I) at least equal to 1, otherwise he loses. The circumference of the circle is 1 and 0<x<1<y<1/x. Let p/q in [x,y) be the rational of minimal denominator. Let n/m be the unique rational such that m<q and nq-mp=1. Then the value of the game is n/m and the optimal strategy of player I is based on a discrete measure of equidistant atoms of weight 1/n. This game is an asymptotic version of a discrete game due to William Ruckle. Our solution of this asymptotic game solves a problem posed by Ruckle.
This is joint work with Christos Pelekis and related to earlier work with Steve Alpern
|
|
16th October 2009
|
Somkiat Trakultraipruk (LSE)
Connectedness of Strong k-colour Graphs
Abstract: For a positive integer k and a graph G, we consider proper vertex-colourings of G with k colours in which all k colours actually appear. We call such a colouring a "strong k-vertex-colouring". The strong k-colour graph of G, S_k(G), is the graph that has all the strong k-vertex-colourings of G as its vertex set, and two such colourings are adjacent in S_k(G) if they differ in colour on only one vertex of G.
In this talk we discuss some results related to the question: When is S_k(G) connected?
|
|
19th June 2009
|
Mihyun Kang (TU Berlin)
Random planar graphs
Abstract: Random graphs on surfaces, in particular random planar graphs, have recently received much attention from the viewpoint of typical properties, uniform sampling and enumeration. The main focus of this talk will be the enumeration problem. We briefly survey recent results and methods of how to count labelled planar graphs with given numbers of vertices and edges. We also discuss the power and limitations of each method.
|
|
20th March 2009
|
Matthias Mnich (TU Eindhoven)
Computing Maximum Consistent Supertrees
Abstract: A chief problem in phylogenetics and database theory is the computation of a maximum consistent tree from a set of rooted or unrooted trees. A standard input are triplets, rooted binary trees on three leaves, or quartets, unrooted binary trees on four leaves. We give exact algorithms constructing rooted and unrooted maximum consistent supertrees in time O( (2+ε)n ), for any ε > 0 for a set of triplets (quartets), each one distinctly leaf-labeled by some subset of n labels. The algorithms extend to weighted triplets (quartets). We further present fast exact algorithms for constructing rooted and unrooted maximum consistent trees in polynomial space.
|
|
13th March 2009
|
David Wolpert
Schelling formalized: Strategic choices of non-rational personas
Abstract: A long-standing puzzle in economics is why people sometimes act non-rationally. Many previous explanations show how non-rationality by a player in an individual game can be optimal for that player if considered in the context of an infinite sequence of identical, repeated instances of that game. In this talk I present a framework that instead explains non-rationality in single, non-repeated games.
This framework starts from the observation that in the real world, an individual X often adopts a "persona" that they signal to others before interacting with them. By changing what persona they adopt, X may change the behavior of others in the interaction. In particular, I show that sometimes by adopting a "non-rational" persona, X induces behavior by others that ultimately increases the value of X's true utility function.
I use this framework to derive several quantitative predictions concerning non-rationality in non-repeated play of the Traveler's Dilemma and the Ultimatum Game. All of these predictions agree with experiment. I then use the framework to show how cooperation can arise even in a non-repeated play of certain versions of the Prisoner's Dilemma (PD).
In addition to explaining experimental data, the framework predicts a "crowding out" phenomenon in the PD, in which introducing incentives to cooperate actually causes players to stop cooperating and defect instead. It also predicts an aspect of the PD never previously considered: an unavoidable tradeoff between the robustness of cooperation in the PD and the benefit of the cooperation.
|
|
6th March 2009
|
David Ferguson (LSE)
Graph Colouring
|
|
27th February 2009
|
Zibo Xu (LSE)
Stochastic Ramsey's theorem in two colours
Abstract: Stochastic Ramsey's theorem is the extension of classical Ramsey's theorem (1928) in discrete random process. It comes from an open question proposed by Shmaya and Solan (2004). In this talk, I am going to show the definitions, results and constraints on this theorem.
|
|
20th February 2009
|
Anne Balthasar (LSE)
Computation of the Index of a Component of Nash equilibria for Bimatrix Games
Abstract: In game theory, the index of a component of Nash equilibria is an important topological notion which can be used to characterize certain properties of such a component. For example, an equilibrium component is hyperstable, i.e. does not vanish under certain manipulations of the game, if and only if its index is non-zero. For nondegenerate bimatrix games, the calculation of the index of an equilibrium is straightforward via an explicit formula, which boils down to computing determinants of square matrices. However, in degenerate cases, this formula fails to make sense, and index computation then amounts to calculating the (relatively complex) topological degree of a function. To resolve this difficulty we present an algorithm for the computation of the index in degenerate bimatrix games.
|
|
13th February 2009
|
Anatole Beck (LSE)
The Hare and the Tortoise and other paradoxes
Abstract: The paradox of the Hare and the Tortoise is a mathematical model which bears an interesting similarity to the La Fontaine fable of that name. In addition to that virtue, it is the basis of an answer to a question in the area of uniqueness of solutions of differential equations that went unsolved for decades.
We build a model for the following event: The Hare, having lost his first race with the Tortoise by taking a nap along the route, asks for and receives a re-match. This time he never stops, in the sense that his distance from the goal is a strongly monotonically decreasing function of time. The issue of smoothness is eliminated largely by the requirement that this function is infinitely often differentiable, though not analytic. The Hare and the Tortoise start at the same time and both move monotonically along the same straight-line course. At every point of the course, the velocity of the Hare is double that of the Tortoise, yet at every moment the Tortoise is ahead of the Hare, and finishes in half the time. That this circumstance, which seems at first glance to be impossible, is actually accomplished, constitutes the paradox. The key to this is that over a piece of the course (which has measure 0) both participants have the velocity 0. However, no one actually stops for any positive time at any point.
The question in the field of differential equations concerns continuous flows in Euclidean n-dimensional space which are the solutions of a continuous differential equation. That is, if there is a continuous vector field (even a continuous field of unit vectors) such that at every point the velocity of the flow at that point is represented by the vector there, then can there be a second flow, demonstrably different from the first, which is also a solution of that differential equation? The answer, surprisingly, is "yes". Indeed, there could be uncountably many such flows, and even carrying the provision that every orbit be the graph of a function that has infinitely many derivatives. It is even possible that two such flows in the Euclidean plane have orbits that intersect in a way that is homeomorphically equivalent with the horizontal and vertical lines of the Cartesian system of coordinates.
|
|
6th February 2009
|
Ovidiu Precup (LSE)
A Commodity Storage Valuation Model
Abstract: We consider a stochastic control problem that arises in the context of commodity storage valuation. The model allows for a range of operational characteristics and constraints that can be associated with different types of inventories such as hydro-electric reservoirs or gas storage facilities. The underlying commodity price is modelled by a stochastic process with seasonal and jump behaviours. We show that with a deterministic function transformation of the price process resulting in a martingale, the optimal storage strategy depends only on the planning horizon and the amount of commodity stored but not the commodity price.
|
|
30th January 2009
|
Raminder Ruprai (Royal Holloway)
Bounded Discrete Logarithms
Abstract: In this talk we will look at the algorithms to solve the Discrete Logarithms in general groups where we have a restricted bound on the solution of the dlog. I will then give a brief outline of my approach which is easily parallelisable and can be used to solve the Discrete Logarithm Problem in more than 1 dimension.
|
|
23rd January 2009
|
Tugkan Batu (LSE)
An Online Chains-into-Bins Process
Abstract: The study of balls-into-bins games or occupancy problems has a long history. These processes can be used to translate realistic problems into mathematical ones in a natural way. Typically, the goal of a balls-into-bins protocol is to allocate a set of independent objects (tasks, jobs, balls) to a set of resources (servers, bins, urns) and, thereby, to minimize the maximum load.
Here we look at a variant of this protocol and investigate the setting where balls are connected into chains. In particular, we analyse the maximum load for a chains-into-bins protocol where we have n bins and the balls are connected in m chains of length l. In this process, the balls of one chain have to be allocated to l consecutive bins. We allow each chain d independent and uniformly random bin choices. The chain is allocated using the rule that the maximum load of any bin receiving a ball of that chain is minimized. We show that, for d ≥ 2 and ml=O(n), the maximum load is (lnln m / ln d) + O(1) with probability 1-O(1/md-1). The result parallels the corresponding balls-into-bins result and is derived analogously.
Joint work with Petra Berenbrink and Colin Cooper.
|
|
16th January 2009
|
Raju Chinthalapti (LSE)
Volatility Forecast in Financial Time-Series Using Evolutionary Computing Techniques
Abstract: The volatility of a financial asset changes as a function of the underlying asset's price. Financial asset volatility exhibits key characteristics, such as mean-reversion and high autocorrelation. We introduce a preliminary framework for forecasting 5-day annualized volatility in GBP/USD, USD/JPY, and EUR/USD. It employs a series of standar and non-standard (Genetic Programming) forecasting methods. We employ Genetic Programming (GP) for volatility forecasting because of its ability to detect patterns such as the conditional mean and conditional variance of a time-series. When using GP for volatility forecast, in the learning phase we feed randomly generated (market data that may have noise) examples to a GP learner. I am working on a mathematical model of this learning process. One challenge with volatility forecasting using GP learning is that the training samples are not generated according to independent and identically distributed process, but instead form a noisy Markovian process. A key issue on which I have been working is to determine how many training examples must be presented to the GP in the learning phase for the learning to be successful under the `Probably Approximately Correct' paradigm (a standard probabilistic framework for machine learning analysis).
|