Tutorials

Price of Anarchy in Auctions, by Jason Hartline and Vasilis Syrgkanis (part 1, part 2, and part 3)

The economic analysis of auctions and other mechanisms for agents with private information is predicated on the understanding of equilibrium in games of incomplete information.  In complex environments solving for these equilibria is analytically intractable.  Even solving for the equilibrium of a two-bidder first-price auction where the bidders’ values are drawn from asymmetric distributions poses considerable challenge.

The Price of Anarchy quantifies the performance of a mechanism in equilibrium relative to a target optimal performance (e.g., the optimal performance were the actions of the agents coordinated by a central authority).  Instead of explicitly solving for equilibrium, a typical price of anarchy analysis uses best-response arguments to show that any equilibrium performance is good.  Moreover, via the so-called smoothness framework, if the best-response argument is sufficiently simplistic then the price of anarchy bound automatically extends to more general settings for the mechanism.  For example, a smoothness based proof of the price of anarchy for full information mechanisms directly extends (a) to the setting of incomplete information, (b) to the setting where several mechanisms are run simultaneously and agents have additive utilities across mechanism outcomes, and (c) from additive utilities across mechanism outcomes to more general utilities.

In this tutorial we will present fundamental techniques for analyzing the price of anarchy in games of incomplete information such as auctions.   We will focus on classes of best-response arguments that admit automatic extension via the smoothness paradigm.  Examples will be given for auctions and settings that are central to auction theory.

How, When, and Why to Conduct Online Behavioral Experiments, by Andrew Mao and Sid Suri

As algorithms and mechanisms begin to incorporate human agents, computer scientists often aim to describe and model human behavior in a realistic way.  In this seminar we present an overview of using behavioral experiments as a complementary technique to the more widely used methods of theoretical modeling and empirical data mining, for studying human behavior in various settings. We will review the benefits and drawbacks of experimental studies in general. We will focus on techniques for conducting clean experiments that yield causal conclusions as well as common pitfalls to avoid. Finally, we will also outline the relatively unexplored but rapidly growing space of experiments using participants from the Internet and review the various tools and platforms that can be used to execute online experiments.  Throughout the tutorial, we explore how computer scientists are uniquely equipped to execute online behavioral experiments and gather data for developing rich behavioral models. We also show how such causal studies of behavior can be a powerful tool for the future of computer science.

Budget Feasible Mechanisms, by Nick Gravin and Yaron Singer

In this tutorial we will introduce and discuss the budget feasible mechanism design framework.  This framework captures scenarios where the goal is to buy items or services from strategic agents under budget.  The setting poses interesting combinatorial optimization problems with application domains that include crowdsourcing, marketing in social networks, recommendation systems, spectrum auctions, and privacy auctions.

We will focus on both the theory and the applications. The theoretical developments are concerned with combinatorial optimization, competitive analysis, approximation ratios, Bayesian models, posted price mechanisms, and leave many open questions. The applications we will discuss would be relevant to those interested in influence in social networks, pricing and matching crowdsourcing tasks, and privacy auctions.

We will aim to provide a useful toolbox for procurement-related problems, as well as a good exposure to open problems for those interested in combinatorial optimization, mechanism design, and online learning.

Computational Social Choice, by Lirong Xia
Social choice theory studies representation and aggregation of individual preferences. In this tutorial, we will give a brief overview of classical social choice theory and its computational aspects from two different viewpoints: reaching a compromise and revealing the ground truth.