Symposium on Auctions and Computational Game Theory in Honour of Robert Wilson

London School of Economics and Political Science Wednesday-Thursday July 11-12, 2018       Organizer: Bernhard von Stengel Speakers: Elizabeth Baldwin, Ken Binmore, Peter Cramton, Michal Feldman, Paul Goldberg, Paul Klemperer, Troels Bjerre Lund, Benny Moldovanu, Tim Roughgarden, Rahul Savani, Robert Wilson.

Registration and Conference Dinner:

Participants will need to register, with a non-refundable fee of GBP 20 which includes coffee/tea, drinks, and on Thursday a sandwich lunch at LSE. To purchase the conference ticket, please click here.

The Conference Dinner is on Wednesday evening, at GBP 40 per person (non-refundable). To purchase the conference dinner ticket, please click here.

All queries should be sent to Enfale Farooq.

Location at LSE:

Click here for a map of the LSE campus and for getting to LSE.

Schedule (as of 9 July 2018)

Click on a speaker name for title, abstract, and talk presentation (if available).

Presentation Details

Speaker	Title, Links	Abstract
Elizabeth Baldwin (Oxford)	Understanding Preferences: "Demand Types", and the Existence of Equilibrium with Indivisibilities Paper, PDF, 1.7MB	An equivalence theorem between geometric structures and utility functions allows new methods for understanding preferences. Our classification of valuations into "Demand Types" incorporates existing definitions (substitutes, complements, "strong substitutes", etc.) and permits new ones. Our Unimodularity Theorem generalises previous results about when competitive equilibrium exists for any set of agents whose valuations are all of a "demand type". Contrary to popular belief, equilibrium is guaranteed for more classes of purely-complements, than of purely-substitutes, preferences. Our Intersection Count Theorem checks equilibrium existence for combinations of agents with specific valuations by counting the intersection points of geometric objects. Applications include matching and coalition-formation, and the "Product-Mix Auction" introduced by the Bank of England in response to the financial crisis. Joint work with Paul Klemperer.
Ken Binmore (Bristol)	On the Foundations of Decision Theory Paper, PDF, 408kB	Bayesian decision theory was invented by Leonard Savage, who is on record as saying that it would be "preposterous" and "utterly ridiculous" to apply his theory except in a small world. But modern Bayesians proceed as though Savage's theory is always the rational way to make choices in all circumstances. What is a small world? Why did Savage restrict his theory to small worlds? Where did Savage think priors come from? What are the implications for behavioral applications? How could Savage's theory be generalized to apply to at least some large worlds? This paper offers some partial answers to such questions.
Peter Cramton (Cologne / Maryland)	Market Design Inspired by Robert Wilson Course webpage Talk slides, PDF, 1.9MB	Market design combines auction and matching theory with behavioral and experimental economics to design innovative markets to better meet goals. Applications are seen in almost all markets and government programs that assign and sometimes price scarce resources. Market design research leads to a better understanding of the incentives that guide behavior. Applications include matching students to schools, interns to hospitals, and kidneys to patients. In settings where prices are used to motivate behavior, auction markets are developed to assign and price scarce resources. Applications include markets in mobile communications, electricity, financial securities, transportation, and emissions.
Michal Feldman (Tel Aviv)	Interdependent Values Without Single Crossing Paper, PDF, 859kB	We consider a setting where an auctioneer sells a single item to n potential agents with interdependent values. This captures settings such as valuations for artwork, oil drilling rights, broadcast rights, and many more. In the interdependent value setting, all previous work has assumed a so-called single-crossing condition. Single-crossing means that the impact of agent i’s private signal, si, on her own valuation is greater than the impact of si on the valuation of any other agent. It is known that without the single-crossing condition an efficient outcome cannot be obtained. Motivated by this, we study welfare maximization for interdependent valuations through the lens of approximation. We show that, in general, without the single-crossing condition, one cannot hope to approximate the optimal social welfare any better than the approximation given by assigning the item to a random bidder. Consequently, we introduce two valuation properties that enable positive results. The first is a relaxed, parameterized version of single-crossing; the second is a (parameterized) submodularity condition over the signals. We obtain a host of approximation guarantees under these two notions. Joint work with Alon Eden, Amos Fiat, and Kira Goldner.
Paul Goldberg (Oxford)	The Computational Complexity of Consensus-Halving, Necklace-Splitting, and Ham Sandwich Bisection Paper on Necklaces and Ham Sandwich Bisection Paper on Consensus-Halving	We present three problems that have a common theme of fair division. We present recent results showing that they are all PPA-complete (in the talk, I will explain the complexity class PPA). These are the first examples of "natural" computational problems that are known to be PPA-complete, where by "natural" we mean that the problem does not have a general boolean circuit (or equivalently, a polynomial-time Turing machine) embedded explicitly in the problem definition. Joint work with Aris Filos-Ratsikas.
Paul Klemperer (Oxford)	Wilson, Equilibrium, and Auctions	Starting from Bob Wilson's work, I'll talk about my and co-authors' work developing practical multi-product auctions and about choices made in developing and analysing them. My recent work on this topic is joint with Elizabeth Baldwin; some of it is joint with Paul Goldberg; all of it is influenced, of course, by Bob Wilson.
Troels Bjerre Lund (IT-University Copenhagen)	The Proper Way to Compute Proper Equilibria Paper, PDF, 279kB	We provide the first pivoting-type algorithm that finds an exact proper equilibrium of a bimatrix game. This is achieved by using Lemke's algorithm to solve a linear complementarity problem (LCP) of polynomial size. This resolves an open problem in the positive: computing a proper equilibrium of a bimatrix game is in PPAD. The algorithm also computes a witness in the form of a parameterized strategy that is an ε-proper equilibrium for any given sufficiently small ε, allowing polynomial-time verification of the properties of the refined equilibrium. The same technique can be applied to matrix games, thereby computing a parameterized ε-proper strategy in polynomial time using linear programming.
Benny Moldovanu (Bonn)	A Theory of Auctions With Endogenous Valuations Paper, PDF, 440kB	We study the revenue maximizing allocation of m units among n symmetric agents that have unit demand and convex preferences over the probability of receiving an object. Such preferences are naturally induced by a game where the agents take costly actions that affect their values before participating in the mechanism. Both the uniform m + 1 price auction and the discriminatory pay-your-bid auction with reserve prices constitute symmetric revenue maximizing mechanisms. Contrasting the case with linear preferences, the optimal reserve price reacts to both demand and supply, i.e., it depends both on the number of objects m and on number of agents n. The main tool in our analysis is an integral inequality involving majorization, super-modularity and convexity due to Fan and Lorentz (1954). Joint work with Alex Gershkov and Philipp Strack.
Tim Roughgarden (Stanford)	When Are Equilibria of Simple Auctions Near-Optimal? Paper, PDF, 416kB	This survey outlines a general and modular theory for proving approximation guarantees for equilibria of auctions in complex settings. This theory complements traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings. We highlight three user-friendly analytical tools: smoothness-type inequalities, which immediately yield approximation guarantees for many auction formats of interest in the special case of complete information and deterministic strategies; extension theorems, which extend such guarantees to randomized strategies, no-regret learning outcomes, and incomplete-information settings; and composition theorems, which extend such guarantees from simpler to more complex auctions. Combining these tools yields tight worst-case approximation guarantees Joint work with Vasilis Syrgkanis and Éva Tardos.
Rahul Savani (Liverpool)	End of Potential Line Paper, PDF, 633kB	The complexity class PPAD has successfully characterized the complexity of many fixed point problems such as computing a mixed Nash equilibrium of a bimatrix game and computing a market equilibrium. The complexity class PLS has successfully characterized the complexity of computing local optima, such as a pure equilibrium in a congestion game. In this talk we introduce a complexity class, called EOPL, that lies within both PPAD and PLS. EOPL is based on the problem End-of-Potential-Line, which combines the canonical problems that define PPAD and PLS. We show that finding a solution to a P-matrix Linear Complementarity Problem (P-LCP) and finding a fixed point of a piecewise linear contraction map are in this new class EOPL. In doing so, we show that solving a `Simple Stochastic Game' is in EOPL. Along the way, we get new algorithms with improved running times for both solving P-LCPs and finding fixed points of contraction maps. Finally, we show that the problem of finding the sink of a Unique Sink Orientation of a cube is in EOPL; until now, this problem was not known to be in either PPAD or PLS. Joint work with John Fearnley, Spencer Gordon, and Ruta Mehta.
Robert Wilson (Stanford)	Repeated Games Played With Adaptive Automata Talk slides, PDF, 89kB	We study repeated games with players' strategies restricted to be implementable by finite adaptive automata. We have some results for the prisoner's dilemma with players moving alternately. Most remarkable is an anti-folk theorem: for generic stage-game payoffs there is a unique subgame perfect payoff. Moreover, for the class of bounded-recall adaptive automata with players' recalls less than 5 we find numerically that the payoff is the perfectly cooperative payoff (and conjecture that this is true generally). In my talk I will connect these results to issues in dynamic games and evolutionary processes. Joint work with Hari Govindan.