The early registration period for ACM EC 2014 ends today. Also, I’d like to draw your attention to this year’s EC tutorials (not without self-interest):
Recent progress in multi-dimensional mechanism design
Organizers: Yang Cai (UC Berkeley), Costis Daskalakis (MIT), and Matt Weinberg (MIT)
Abstract: Mechanism design in the presence of Bayesian priors has received much attention in the Economics literature, focusing among other problems on generalizing Myerson’s celebrated auction to multi-item settings. Nevertheless, only special cases have been solved, with a general solution remaining elusive. More recently, there has been an explosion of algorithmic work on the problem, focusing on computation of optimal auctions, and understanding their structure. The goal of this tutorial is to overview this work, with a focus on our own work. The tutorial will be self-contained and aims to develop a usable framework for mechanism design in multi-dimensional settings.
Axiomatic social choice theory: from Arrow’s impossibility to Fishburn’s maximal lotteries
Organizers: Felix Brandt (TU München)
Abstract: This tutorial will provide an overview of central results in social choice theory with a special focus on axiomatic characterizations as well as computational aspects. Topics to be covered include rational choice theory, choice consistency conditions, Arrovian impossibility theorems, tournament solutions, social decision schemes (i.e., randomized social choice functions), preferences over lotteries (including von Neumann-Morgenstern utility functions, stochastic dominance, and skew-symmetric bilinear utility functions), and the strategyproofness of social decision schemes. The overarching theme will be four escape routes from negative results such as the impossibilities due to Arrow and Gibbard-Satterthwaite: (i) restricting the domain of preferences, (ii) replacing choice consistency with variable-electorate consistency, (iii) only requiring expansion consistency, and (iv) randomization.
Bitcoin: the first decentralized digital currency
Organizers: Aviv Zohar (Hebrew Univ.)
Abstract: Bitcoin is a disruptive new protocol for a digital currency that has been growing in popularity.The most novel aspect of the protocol is its decentralized nature: It has no central entity in charge of the currency or backing it up, and no central issuer. Instead, Bitcoin is managed by a peer-to-peer network of nodes that process all its transactions securely. The protocol itself combines ideas from many areas of computer science. These range from its use of cryptographic primitives to secure transactions, its use of economic mechanisms to avoid denial-of-service attacks and to incentivize participation, through its solution to the Byzantine consensus problem, and the robust construction of its P2P network. The goal of the tutorial is to provide a basic understanding of the Bitcoin protocol, to discuss the main problems and challenges that it faces, and to provide a starting point for research on the protocol and its surrounding ecosystem.
Privacy, information economics, and mechanism design
Organizers: Cynthia Dwork (Microsoft Research), Mallesh Pai (UPenn), and Aaron Roth (UPenn)
Abstract: Internet scale interactions have implications to game theory and mechanism design in at least two ways. First, the ability of many entities to aggregate large amounts of sensitive data for purposes of financial gain has brought issues of privacy to the fore. As mechanism designers, it is therefore crucial that we understand both how to -model- agent costs for loss of privacy, as well as how to control them. Second, it has made “large markets and large games” the common case instead of the exception. Can mechanism designers leverage these large market conditions to design mechanisms with desirable properties that would not be possible to obtain in small games? What techniques can we use to enforce that players are “informationally small” with minimal assumptions on the economy? In this tutorial, we will discuss results and techniques from “differential privacy”, an approach developed over the last decade in the theoretical computer science literature, which remarkably can address both of these two issues. We will motivate the definition, and then show both how it can provably control agent costs for “privacy” under worst-case assumptions, and how it can be used to develop exactly and asymptotically truthful mechanisms with remarkable properties in various large market settings. We will survey recent results at the intersection of privacy and mechanism design, with the goal of getting participants up to the frontier of the research literature on the topic.