Bernhard von Stengel (London School of Economics)
Title: Complexity of path-following and equilibrium problems

Abstract:
Existence of equilibria in various economic models is closely related to fixed point theorems, for example Brouwer's theorem that a continuous function on a simplex has a fixed point. Approximate fixed points exist by Sperner's lemma that asserts the existence of a properly colored simplex of certain colored simplicial subdivisions. An algorithmic proof follows a certain path of simplices. Many such path-following proofs are known, not only for approximate Brouwer fixed points, but also for Nash equilibra of two-player games (Lemke and Howson 1964) or for the core of a balanced N-person game (Scarf 1965).

Our goal is to find the right mathematical abstraction to explain the relationship between these concepts. Computationally, they seem equally difficult. A recent famous result due to Chen and Deng states that finding a Nash equilibrium of a bimatrix game is "PPAD-complete", that is, already as hard as finding an approximate Brouwer fixed point, a seemingly much harder problem. We explain the theorem but not its proof. We currently study how to capture the directedness of the path (the "D" in "PPAD") by oriented topological manifolds in a suitable abstraction.

Our exposition will use colorful pictures and examples wherever possible. (Joint work in progress with Jack Edmonds.)


Guido Schaefer (CWI and Free University, Amsterdam)
Title: The Impact of Stackelberg Routing in General Networks

Abstract:
We study the impact of Stackelberg routing to reduce the price of anarchy in network routing games. In this setting, some fraction of the entire demand is first routed centrally according to a given Stackelberg strategy and the remaining demand is then routed selfishly by (nonatomic) players. Although several advances have been made recently in proving that Stackelberg routing can in fact significantly reduce the price of anarchy for certain network topologies, the central question of whether this holds true in general is still open. We settle this question by constructing a family of single-commodity instances such that every Stackelberg strategy induces a price of anarchy that grows with the size of the network. Moreover, we rule out the possibility to construct constant-size networks to prove an unbounded price of anarchy. If time permits, we will also discuss the effectiveness of an easy-to-implement Stackelberg strategy called SCALE.
(Joint work with Vincenzo Bonifaci (U Rome) and Tobias Harks (TU Berlin).)


Vangelis Markakis (Athens University of Economics and Business)
Title: Welfare Maximization in Auctions and Public Project Problems

Abstract:
In the first part of the talk, we will focus on identifying mechanisms that maximize the final social welfare generated. To be able to
compare mechanisms with regard to their welfare, we introduce the concept of "welfare undominated mechanism". We focus on two domains, namely, public project problems and multi-unit auctions with unit demand bidders. We show that in the first case the VCG mechanism is
welfare undominated, whereas in the second domain we exhibit a family of mechanisms that are welfare undominated and include the
Bailey-Cavallo mechanism.

In the second part of the talk, we will study sequential versions of the VCG and the Bailey-Cavallo mechanism that we identified in the
first part, for single item auctions, again with the aim of improving the final welfare. In the sequential setting, being truthful is no longer a dominant strategy and in fact no other dominant strategies exist. For each mechanism we introduce natural optimal strategies that maximize the social welfare when each player follows it. Finally, we show that, when interpreting both mechanisms as simultaneous ones,
the vectors of the proposed strategies form a Pareto optimal Nash equilibrium in the class of optimal strategies.
(Joint work with K.R. Apt, Vincent Conitzer and Mingyu Guo.)


David C. Parkes (Harvard University)
Title: Heuristic Mechanism Design

Abstract:
Computational mechanism design (CMD) seeks to understand how to design game forms that induce desirable outcomes in multi-agent systems despite private information, self-interest and limited computational resources. In meeting the demands for CMD in real-world domains, we often need to bridge from the theory of economic mechanism design to the practice of deployable, computational mechanisms. In this talk, I advocate a heuristic approach to mechanism design in which state-of-the-art optimization algorithms are utilized in generating mechanisms with good incentive properties and good computational properties. One example is that of coupling online stochastic optimization algorithms with "output ironing" for the purpose of dynamic, multi-unit auctions. A second example is that of modifying the payment scheme in a combinatorial exchange to best match the payoffs, in distribution, of a fully strategyproof but undesirable mechanis. The result in both cases is an arguably useful, if not provably optimal, mechanism.
(Joint work with Florin Constantin, Quang Duong and Benjamin Lubin.)


Tomas Klos (Technical University Delft)
Title: Evolutionary Dynamics for Designing Multi-Period Auctions


Abstract:
Mechanism design (MD) has recently become a very popular approach in the design of distributed systems of autonomous agents. A key assumption required for the application of MD is that agents behave rationally in the mechanism or game, since this provides the
predictability of agent behavior required for optimal design of the mechanism. In many cases, however, we are confronted with the intractability both of establishing rational equilibrium behavior, as well as of designing optimal mechanisms even if rational agent behavior can be assumed.

In this talk, we study both sides of the problem simultaneously by designing and analyzing a .meta-game. involving both the designer of the mechanism (game, multi-agent system) and the agents interacting in the system. We use coupled replicator dynamics to investigate equilibrium outcomes in this game. In addition, we present an algorithm for determining the expected payoffs required for our analysis, thus sidestepping the need for extensive simulations as in previous work. Our results show the validity of the algorithm, some interesting conclusions about multi-period auction design, and the general feasibility of our approach.
(Joint work with Gerrit Jan van Ahee)

Valentin Robu (University of Southampton)
Title: Using priced options to reduce bidder exposure in sequential auctions

Abstract:
The exposure problem appears whenever an agent with complementary valuations bids to acquire a bundle of items sold sequentially, in separate auctions. In this talk, we review a possible solution that can help solve this problem, which involves selling options for the items, instead of the items themselves. We provide a brief overview of the state of the art in this field and discuss, based on our recent results, under which conditions using option mechanisms would be desirable for both buyers and sellers, by comparison to direct auctions. We conclude with a brief discussion of further research directions in this area, as well as the relation to other techniques proposed to address the problem, such as leveled commitment mechanisms.
(Joint work with Lonneke Mous, Han La Poutre.)