Recent advances and techniques in algorithmic mechanism design Room 1.6 (upstairs) Link to Tutorial
Tutors: Shaddin Dughmi (MSR Redmond) and Brendan Lucier (Microsoft Research)

Algorithmic mechanism design is concerned with the design of protocols
(mechanisms) for allocating resources among different competing users in the presence of both economic and computational constraints. Since its inception more than a decade ago, researchers have embarked on answering some fascinating questions: For which economic objectives can we design practical mechanisms? What is the power of randomization in the design of computationally efficient mechanisms? What additional power, if any, is afforded by Bayesian settings?

The goal of this tutorial is to survey the landscape of algorithmic mechanism design, focusing on results and techniques of a general flavor. In the first half of the tutorial, we survey results from non-Bayesian algorithmic mechanism design; this model adopts the worst-case paradigm traditional in computer science, and the goal is to design polynomial-time and dominant strategy truthful mechanisms. The second half will be concerned with Bayesian mechanism design, in which agent types are drawn from publicly-known distributions. This probabilistic model is especially well-suited to the goal of generating revenue, but has also been recently studied in the context of maximizing social efficiency.

This tutorial will be aimed most directly at computer science theorists; no prior knowledge of mechanism design is required. The tutorial will also be made accessible to economic theorists wishing to learn more about computational issues in mechanism design.

Mean-field equilibria Room 1.6 (upstairs) Link to Tutorial
Tutor: Ramesh Johari (Stanford University)

This tutorial will survey recent progress in the use of mean field models for analysis of strategic interactions in dynamic auction markets. Dynamic auctions can be viewed as a significant special class of dynamic stochastic games; in these games agents’ actions directly affect underlying state variables that influence their payoff. Dynamic auctions are of wide interest to the EC community, including sponsored search markets, online marketplaces such as eBay, and dynamic resource sharing markets (such as cloud services).

The tutorial will be self-contained and require some mathematical maturity and a basic background in game theory, but it will not be assumed that the audience members are experts in dynamic games. A significant goal for the tutorial would be to introduce MFE to engineers actively working on the design and implementation of dynamic auctions.

Diffusion of networking technologies Room 1.6 (upstairs) Link to Tutorial
Tutor: Sharon Goldberg (Boston University)

While the EC community has shown great interest in understanding diffusion and cascade processes in social networks, there is a vast array of diffusion processes on networks that remain under the community's radar. The purpose of this tutorial is introduce the EC community to a different set of technology diffusion problems --- the diffusion of new networking technologies in the Internet's infrastructure, and communication networks in general --- and contrast the problem in this context with the classical models of technology diffusion. While the majority of the work on this topic has appeared in the networking/security literature, there is a rich set of open problems in this area that could benefit from the skills and tools developed in the EC community.

As the literature in this area is far from complete, this tutorial will (a) review the classical literature on technology diffusion, (b) discuss the major technologies that are currently under deployment in the Internet (IPv6, DNSsec, BGPsec, etc), and (c) survey results related to the diffusion of these networking technologies, with the goal of introducing participants to the exciting open problems in this area.

Computational social choice Room 1.6 (upstairs) (Link to Tutorial)
Tutor: Lirong Xia (Harvard University)

Social choice theory is a traditional discipline that studies representation and aggregation of individual preferences. It dates back to the 4th century B.C., and prospered since the 18th century. In the past few decades, rapid developments in computer science and internet technologies have brought fresh air to social choice by introducing not only many new applications, but also a computational point of view on preference representation and aggregation. As a result, an interdisciplinary area called computational social choice emerged and has attracted much attention of researchers in artificial intelligence, economics, and theory of computation. In particular, computational social choice has found its place in many multi-agent system settings where the agents have conflicting preferences but they must make a joint decision.

In this tutorial, we will give an overview of computational social choice from two different viewpoints: the first views social choice systems as methods that compromise agents’ preferences, and the second views social choice systems as methods that reveal the true status of the world. We will discuss objectives and principles of design, with more emphasis on computational considerations. More precisely, we will mainly focus on the first viewpoint by discussing the rationale and possibility of using computational complexity as a barrier against strategic behavior, and preference representation and aggregation when the set of alternatives is exponentially large and has a combinatorial structure. For the second viewpoint we plan to discuss a maximum likelihood approach. We will also discuss connections between some promising future directions.

Computation of Stackelberg equilibria with Applications to security Room 1.6 (upstairs) Link to Tutorial
Tutors: Christopher Kiekintveld (University of Texas at El Paso), Albert Xin Jiang and Bo An (University of Southern California)

Game theory is an increasingly important paradigm for modeling decision-making in security domains, in which it is important to randomize critical security decisions to prevent terrorist adversaries from exploiting a predictable security schedule. In particular, Stackelberg game models have been used as the basis of successfully deployed decision-support systems for security agencies, including ARMOR at the LAX airport and IRIS at the Federal Air Marshals Service.
Solution of these models requires the computation of Stackelberg equilibrium. Besides its practical importance, this computational problem has interesting properties that are distinct from the computation of other solution concepts such as Nash and correlated equilibria.

This tutorial will introduce a wide variety of techniques and algorithms that have been developed in recent years on the problem of computing Stackelberg equilibria, especially for games arising from security problems. After introducing the motivating domains, we will define Stackelberg equilibrium and discuss its relation to other solution concepts. We will describe existing complexity and algorithmic results for the computation of Stackelberg equilibrium in arbitrary games, then focus on the class of security games which has structure that commonly arises in security domains. While in many cases we will describe algorithms that are able to scale to very large games, for many cases there remain significant computational challenges and we will highlight these open problems.

We believe that the EC community, with its strong theoretical CS background, can make significant contributions to the theoretical foundations of what has become one of the most important areas of applied multi-agent systems research. To this end, this tutorial will focus on topics that are likely to be of interest to the EC audience, while highlighting the many opportunities for future work in this area, including fundamental theoretical and algorithmic challenges.