Abstracts

Computing Game-Theoretic Solutions for Security

Vincent Conitzer, PhD, Duke University

Algorithms for computing game-theoretic solutions are now deployed in real-world security domains, notably air travel. These applications raise some hard questions. How do we deal with the equilibrium selection problem? How is the temporal and informational structure of the game best modeled? What assumptions can we reasonably make about the utility functions of the attacker and the defender? And, last but not least, can we make all these modeling decisions in a way that allows us to scale to realistic instances? I will present our ongoing work on answering these questions.

Coauthors: Dmytro Korzhyk, Joshua Letchford, Kamesh Munagala, Ronald Parr (Duke University); Manish Jain, Zhengyu Yin, Milind Tambe (University of Southern California); Christopher Kiekintveld (University of Texas El Paso); Ondrej Vanek, Michal Pechoucek (Czech Technical University); and Tuomas Sandholm (Carnegie Mellon University)

Payment Rules for Combinatorial Auctions via Structural Support Vector Machines

David Parkes, PhD, Harvard University

How can machine learning be used for the design of mechanisms? In this talk, I will outline a new connection in which structural support vector machines are used for the design of payment rules for combinatorial auctions. Given an algorithm that defines an allocation rule, the proposed methodology first constructs training data according to a prior on agent valuations, and then trains a classifier, where the discriminant function of the classifier provides a payment rule. For an appropriately constrained hypothesis space, an exact classifier generates a strategyproof mechanism, while minimizing regularized empirical error training error corresponds to minimizing a regularized upper bound on ex post regret. I present experimental results on single-minded and multi-minded distributions and also provide a discussion of ex post IR properties, along with other connections between kernel methods and combinatorial auctions.

Coauthors: Paul Duetting, Felix Fischer, Pichayut Jirapinyo, John Lai, and Benjamin Lubin

Learning from Seller Experiments in Online Markets

Jonathan Levin, PhD, Stanford University

The internet has dramatically reduced the cost of varying prices, displays, and information provided to consumers, facilitating both active and passive experimentation. We document the prevalence of targeted pricing and auction design variation on eBay and identify hundreds of thousands of experiments across a wide array of retail products. We show how this type of data can be used to address questions about consumer behavior and market outcomes. We argue that leveraging the experiments of others can be a powerful approach to economic measurement that takes advantage of the scale and heterogeneity of online markets.

Welfare and Revenue in Ad Auctions

Éva Tardos, PhD, Cornell University

The Generalized Second Price Auction for selling advertisement space has been the main mechanism used to monetize Internet services. These auctions give rise to a number of interesting challenges not traditionally considered by auction theory, e.g., search advertising gives rise of an enormous number of auctions running simultaneously, limiting the applicability of traditional auction theory. In this talk we will talk about various models for this auction and consider the social welfare and revenue of the Nash equilibria of this game in various models, including the full information setting, a information setting, and in the Bayesian setting.