Maps of the LSE campus can be found here: http://www2.lse.ac.uk/mapsAndDirections/findingYourWayAroundLSE.aspx
Click on a speaker name for title, abstract, and talk presentation (if available).
Thursday 17 October 2013 St. Clement's Building STC.S221 
Friday 18 October 2013 Kingsway Building KSW.G.01 (9:0013:00) and KSW.1.04 (13:0018:15)

9:00  9:45


9:45  10:00 coffee break 

10:00  10:45
10:45  11:15


11:15  11:45 coffee break 

11:45  12:15
12:15  13:00 

13:00  14:00 lunch (provided) in new room KSW.1.04 

14:00  14:45

14:00  14:45

14:45  15:15 coffee break 
14:45  15:15 coffee break 
15:15  15:45
15:45  16:30

15:15  15:45
15:45  16:30

16:30  17:00 coffee break 
16:30  17:00 coffee break 
17:00  17:45
17:45  18:15

17:00  17:30
17:30  18:15

Query Complexity of Approximate Nash Equilibria 
We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n and a constant number of actions m. Our main result states that even for constant ε, the query complexity of an εwellsupported Nash equilibrium is exponential in n. 

Reductions from Mechanism to Algorithm Design 
Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient reductions from mechanism design (i.e. optimizing over rational inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated singleitem auction to multiitem settings. 

A Characterization of SinglePeaked SingleCrossing Domain 
In this talk we focus on two classic domain restrictions that are often considered in social choice: singlepeaked and singlecrossing preferences. We characterize the preference profiles that are simultaneously singlepeaked and singlecrossing. We also discuss some algorithmic implications of our characterization for the problem of fully proportional representation. 

Branching Stochastic Games 
Branching stochastic
games are twoplayer zerosum stochastic games
that generalize multitype branching processes,
a classic discretetime stochastic process. The
goal of the two players is to
maximizing/minimizing extinction probability,
starting with a given population of objects.


(Approximately) Optimal Impartial Selection 
We study impartial mechanisms for selecting a
member of a set of agents based on nominations
by agents from that set. Here, impartiality
means that nominations submitted by an agent do
not affect its own chances of being selected.
Our main result concerns a randomized mechanism
that in expectation selects an agent with at
least half the maximum number of nominations.
Subject to impartiality, this is optimal.


Complexity and Approximation of the Continuous Network Design Problem 
We revisit a classical problem in
transportation, known as the continuous
(bilevel) network design problem, CNDP for
short. We are given a graph for which the
latency of each edge depends on the ratio of the
edge flow and the capacity installed. The goal
is to find an optimal investment in edge
capacities so as to minimize the sum of the
routing cost of the induced Wardrop equilibrium
and the investment cost. While this problem is
considered as challenging in the literature, its
complexity status was still unknown. We close
this gap showing that CNDP is strongly
NPcomplete and APXhard, even for instances
with affine latencies.


The Complexity of Computing the Solution Obtained by a Specific Algorithm 
In a recent paper, we showed that it is PSPACEcomplete to compute any of the Nash equilibria that are found by the LemkeHowson algorithm. I will give an overview of the complexitytheoretic background to that result, and discuss possible generalizations. 

NearOptimal MultiUnit Auctions With Ordered Bidders 
I will discuss priorfree profitmaximizing auctions for digital goods. In particular, I will give an overview of the area and I will focus on priorfree auctions with ordered bidders and identical items. In this model, we compare the expected revenue of an auction to the monotone price benchmark: the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the secondhighest bid. I will discuss an auction with constantfactor approximation guarantee for identical items, in both unlimited and limited supply settings. Consequently, this auction is simultaneously nearoptimal for essentially every Bayesian environment in which bidders' valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. 

Equilibrium Computation in Bimatrix Games: Rank1 and Beyond 
The rank of a bimatrix game (A, B) is
defined as the matrix rank of A + B.
For zerosum games, i.e., rank0, von Neumann
(1928) showed that Nash equilibrium are minmax
strategies. Its existence is equivalent to the
linear programming duality. We solve the open
question of Kannan and Theobald (2005) of
designing an efficient algorithm for rank1
games. The main difficulty is that the set of
equilibria can be disconnected. We circumvent
this by moving to a space of rank1 games which
contains our game (A, B), and defining a
quadratic program whose optimal solutions are
Nash equilibria of all games in this space. We
then isolate the Nash equilibrium of (A, B)
as the fixed point of a single variable function
which can be found in polynomial time via an
easy binary search.


Learning Equilibria of Games via Payoff Queries 
We study a computational learning model for games in which an algorithm queries the payoffs of players at pure strategy profiles. The goal of the algorithm is to find an exact or approximate Nash equilibrium of the game with as few queries as possible. We give basic results on the payoff query complexity of bimatrix and graphical games. Our focus is on symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of purestrategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values. 

Strong Bounds for Evolution in Networks 
The work concerns evolutionary antagonism in
undirected networks (graphs) and thus it concerns
evolutionary game theory issues. Given is a network
whose nodes are occupied by members of a resident
population. Each member has a fitness normalized to
one. A single nonresident (mutant) is then placed
at a node, and has a fitness, usually bigger than
one. Mutants and residents can copy themselves on
neighbours, replacing the previous inhabitant. The
selection of a node to copy itself on a random
neighbour is based on a probabilistic experiment
which gives more probability to bigger fitness. This
process may result in (a) the whole net occupied by
mutants (fixation) or (b) elimination of mutants
(extinction). A main magnitude of interest is the
probability of fixation (given the graph). Here we
describe work done in ICALP 2013 (and also refer to
previous works by the speaker and coauthors, in WINE
2011 and SODA 2012).


Complexity of the Guarding Game 
The guarding game is a game in which several
cops try to guard a region in a (directed or
undirected) graph against a robber. The robber
and the cops are placed on the vertices of the
graph; they take turns in moving to adjacent
vertices (or staying), cops inside the guarded
region, the robber on the remaining vertices
(the robberregion). The goal of the robber is
to enter the guarded region at a vertex with no
cop on it. The problem is to determine whether
for a given graph and given number of cops the
cops are able to prevent the robber from
entering the guarded region. Fomin et al.
proved that the problem is NPcomplete when the
robberregion is restricted to a tree. Further
they prove that is it PSPACEcomplete when the
robberregion is restricted to a directed
acyclic graph, and they ask about the problem
complexity for arbitrary graphs. In this paper
we prove that for arbitrary graphs (directed or
undirected) the problem is Ecomplete.


Algebraic Combinatorics and the Parity Argument 
The topic of this talk is related to PPA membership of the Combinatorial Nullstellensatz and related problems. We present new generalizations of Olson's theorem and of a consequence of Alon's Combinatorial Nullstellensatz. These enable us to extend some of its combinatorial applications with conditions modulo primes to conditions modulo prime powers. We analyze computational search problems corresponding to these kinds of combinatorial questions and we prove that the problem of finding degreeconstrained subgraphs modulo 2^{d} such as 2^{d}divisible subgraphs and the search problem corresponding to the Combinatorial Nullstellensatz over F_{2} belongs to the complexity class Polynomial Parity Argument (PPA). 

Convex Programs for Linear ArrowDebreu Markets 
We give a new, flowtype
convex program for linear ArrowDebreu markets,
along with a simple proof of the existence of
equilibria and some further properties. We also
survey previous convex programs for the problem
and investigate connections between them.


How do you price a durable good? 
A duropolist is a
monopolist for a good that is longlasting and
can be consumed repeatedly over time.
Such goods are evidently desirable but Richard
Coase (1972) made the startling conjecture that
a duropolist has no monopoly power at all! We
discuss this issue and the various pricing
mechanisms available to a duropolist. We then
quantify the extent to which a duropolist can,
in fact, generate higher profits than an
equivalent monopolist for a perishable good.
