Latest Articles

## A Truthful Mechanism for the Generalized Assignment Problem

We propose a truthful-in-expectation, (1-1/e)-approximation mechanism for a strategic variant of the generalized assignment problem (GAP). In GAP, a... (more)

## Dynamics at the Boundary of Game Theory and Distributed Computing

We use ideas from distributed computing and game theory to study dynamic and decentralized environments in which computational nodes, or decision... (more)

## Envy-Free Pricing in Large Markets

We study the classic setting of envy-free pricing, in which a single seller chooses prices for its many items, with the goal of maximizing revenue once the items are allocated. Despite the large body of work addressing such settings, most versions of this problem have resisted good approximation factors for maximizing revenue; this is true even for... (more)

## A Geometric Perspective on Minimal Peer Prediction

Minimal peer prediction mechanisms truthfully elicit private information (e.g., opinions or experiences) from rational agents without the requirement... (more)

### New Editors-In-Chief

David Pennock and Ilya Segal took over as co-editors-in-chief in March 2017.

The ACM Transactions on Economics and Computation (TEAC) is a journal focusing on the intersection of computer science and economics. Of interest to the journal is any topic relevant to both economists and computer scientists, including but not limited to the following: algorithmic game theory, mechanism design, design and analysis of electronic markets, computation of equilibria, cost of strategic behavior and cost of decentralization, learning in games and markets, systems resilient against malicious agents, economics of computational advertising, paid search auctions, agents in networks, electronic commerce, computational social choice, recommendation/reputation/trust systems, and privacy.

Socially-Optimal Design of Service Exchange Platforms with Imperfect Monitoring

We study the design of service exchange platforms in which long-lived anonymous users exchange services with each other. The users are randomly matched into pairs of clients and servers repeatedly, and each server can choose whether to provide high-quality or low-quality services to the
client with whom it is matched. Since the users are anonymous and incur high costs (e.g. exert high effort) in providing high-quality services, it is crucial that the platform incentivizes users to provide high-quality services. Rating mechanisms have been shown to work effectively as incentive schemes in such platforms. A rating mechanism labels each user by a rating, which summarizes the user's past behaviors, recommends a desirable behavior to each server (e.g., provide higher-quality services for clients with higher ratings), and updates each server's rating based on the recommendation and its client's report on the service quality. Based on this recommendation, a low-rating user is less likely to obtain high-quality services, thereby providing users with incentives to obtain high ratings by providing high-quality services.

However, if monitoring or reporting is imperfect -- clients do not perfectly assess the quality or the reports are lost -- a user's rating may not be updated correctly. In the presence of such errors, existing rating mechanisms cannot achieve the social optimum. In this paper, we propose the first rating mechanism that does achieve the social optimum, even in the presence of monitoring or reporting errors. On one hand, the socially-optimal rating mechanism needs to be complicated enough, because the optimal recommended behavior depends not only on the current rating distribution, but
also (necessarily) on the history of past rating distributions in the platform. On the other hand, we prove that the social optimum can be achieved by "simple" rating mechanisms that use binary rating labels and a small set of (three) recommended behaviors. We provide design guidelines of socially-optimal rating mechanisms, and a low-complexity online algorithm for the rating mechanism to determine the optimal recommended behavior.

#### The VCG Mechanism for Bayesian Scheduling

Fast Convergence in the Double Oral Auction

A classical trading experiment consists of a set of unit demand buyers and unit supply sellers with identical items. Each agent's value or opportunity cost for the item is their private information and preferences are quasi-linear. Trade between agents employs a double oral auction (DOA) in which both buyers and sellers call out bids or offers which an auctioneer recognizes. Transactions resulting from accepted bids and offers are recorded. This continues until there are no more acceptable bids or offers. Remarkably, the experiment consistently terminates in a Walrasian price. The main result of this paper is a mechanism in the spirit of the DOA that converges to a Walrasian equilibrium in a polynomial number of steps, thus providing a theoretical basis for the above-described empirical phenomenon. It is well-known that computation of a Walrasian equilibrium for this market corresponds to solving a maximum weight bipartite matching problem. The uncoordinated but rational responses of agents thus solve in a distributed fashion a maximum weight bipartite matching problem that is encoded by their private valuations. We show, furthermore, that every Walrasian equilibrium is reachable by some sequence of responses. This is in contrast to the well known auction algorithms for this problem which only allow one side to make offers and thus essentially choose an equilibrium that maximizes the surplus for the side making offers. Our results extend to the setting where not every agent pair is allowed to trade with each other.

#### Computation of Stackelberg Equilibria of Finite Sequential Games

Query Complexity of Correlated Equilibrium

We study lower bounds on the query complexity of determining correlated equilibrium. In particular, we consider a query model in which an n-player game is specified via a black box that returns players' utilities at pure action profiles. In this model we establish that in order to compute a correlated equilibrium any deterministic algorithm must query the black box an exponential (in n) number of times.

Private Pareto Optimal Exchange

We consider the problem of implementing an individually rational,
asymptotically Pareto optimal allocation in a barter-exchange
economy where agents are endowed with goods and preferences over the goods of others, but may not use money as a medium of
exchange. Because one of the most important instantiations of such
economies is kidney exchange -- where the input'' to the problem
consists of sensitive patient medical records -- we ask to what
extent such exchanges can be carried out while providing formal
privacy guarantees to the participants. We show that individually
rational allocations cannot achieve any non-trivial approximation to
Pareto optimality if carried out under the constraint of
differential privacy -- or even the relaxation of
\emph{joint}-differential privacy, under which it is known that
asymptotically optimal allocations can be computed in two sided
markets [Hsu et al. STOC 2014]. We therefore consider a further
relaxation that we call \emph{marginal}-differential privacy --
which promises, informally, that the privacy of every agent $i$ is
protected from every other agent $j \neq i$ so long as $j$ does not
collude or share allocation information with other agents. We show
that under marginal differential privacy, it is possible to compute
an individually rational and asymptotically Pareto optimal
allocation in such exchange economies.

Impartial Selection and the Power of Up to Two Choices

We study mechanisms that select members of a set of agents based on nominations by other members and that are impartial in the sense that agents cannot influence their own chance of selection. Prior work has shown that deterministic mechanisms for selecting any fixed number k of agents are severely limited and cannot extract a constant fraction of the nominations of the k most highly nominated agents. We prove here that this impossibility result can be circumvented by allowing the mechanism to sometimes but not always select fewer than k agents.
This added flexibility also improves the performance of randomized mechanisms, for which we show a separation between mechanisms that make exactly two or up to two choices and give upper and lower bounds for mechanisms allowed more than two choices.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

Motivated by Internet advertising applications, online allocation problems have been studied extensively in various adversarial and stochastic models. While the adversarial arrival models are too pessimistic, many of the stochastic (such as i.i.d or random-order) arrival models do not realistically capture uncertainty in predictions. A significant cause for such uncertainty is the presence of unpredictable traffic spikes, often due to breaking news or similar events. To address this issue, a simultaneous approximation framework has been proposed to develop algorithms that work well both in the adversarial and stochastic models; however, this framework does not enable algorithms that make good use of partially accurate forecasts when making online decisions. In this paper, we propose a robust online stochastic model that captures the nature of traffic spikes in online advertising. In our model, in addition to the stochastic input for which we have good forecasts, an unknown number of impressions arrive that are adversarially chosen.

We design algorithms that combine a stochastic algorithm with an online algorithm to adaptively react to inaccurate predictions. We provide provable bounds for our new algorithms in this framework. We accompany our positive results with a set of hardness results showing that that our algorithms are not far from optimal in this framework. As a byproduct of our results, we also present improved online algorithms for a slight variant of the simultaneous approximation framework.

Bounded-Distance Network Creation Games

A \emph{network creation game} simulates a decentralized and non-cooperative construction of a communication network. Informally, there are $n$ players
sitting on the network nodes, which attempt to establish a reciprocal communication by activating, incurring a certain cost,
any of their incident links. The goal of each player is to have all the other nodes as close as possible in the resulting network, while buying as few links as possible. According to this intuition, any model of the game must then appropriately address a balance between these two conflicting objectives. Motivated by the fact that a player might have a strong requirement about her centrality in the network, in this paper we introduce a new setting in which if a player maintains her (either \emph{maximum} or \emph{average}) distance to the other nodes within a given \emph{bound}, then her cost is simply equal to the \emph{number} of activated edges, otherwise her cost is unbounded.
We study the problem of understanding the structure of pure Nash equilibria of the resulting games, that we call \textsc{MaxBD} and
\textsc{SumBD}, respectively. For both games, we show that when distance bounds associated with
players are \emph{non-uniform}, then equilibria can be arbitrarily bad.
On the other hand, for \textsc{MaxBD}, we show that when nodes have a \emph{uniform} bound $D \geq 3$ on the maximum distance, then the \emph{Price of Anarchy} (PoA)
is lower and upper bounded by $2$ and $O\left(n^{\frac{1}{\lfloor\log_3 D \rfloor+1}}\right)$, respectively (i.e., the PoA is constant as soon as $D$ is $\Omega(n^{\epsilon})$, for some $\epsilon>0$), while for the interesting case $D=2$, we are able to prove that the PoA is $\Omega(\sqrt{n})$ and $O(\sqrt{n \log n} )$. For the uniform \textsc{SumBD} we obtain similar (asymptotically) results, and moreover we show that the PoA becomes constant as soon as the bound on the average distance is $2^{\omega\big({\sqrt{\log n}}\big)}$.

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than $(1-\frac{1}{e})$-competitive (see \cite{karp1990optimal,mehta2007adwords}), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by \cite{buchbinder2007online}, graphs which we call $(k,d)-bounded$. In such graphs the maximal degree on the online side is at most $d$ and the minimal degree on the offline side is at least $k$. We prove that for such graphs, these problems' natural greedy algorithms attain competitive ratio $1-\frac{d-1}{k+d-1}$, tending to \emph{one} as $d/k$ tends to zero. We prove this bound is tight for these algorithms.

Next, we develop deterministic primal-dual algorithms for the above problems achieving competitive ratio $1-(1-\frac{1}{d})^k>1-\frac{1}{e^{k/d}}$, or \emph{exponentially} better loss as a function of $k/d$, and strictly better than $1-\frac{1}{e}$ whenever $k\geq d$. We complement our lower bounds with matching upper bounds for the vertex-weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder's budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms, as they do not maintain dual feasibility, but only primal-to-dual ratio, and only attain dual feasibility upon termination. We believe our techniques could find applications to other well-behaved online packing problems.

### New options for ACM authors to manage rights and permissions for their work

ACM introduces a new publishing license agreement, an updated copyright transfer agreement, and a new author-pays option which allows for perpetual open access through the ACM Digital Library. For more information, visit the ACM Author Rights webpage.

#### Bibliometrics

First Name Last Name Award
Noga Alon ACM Fellows (2016)
Allan Borodin ACM Fellows (2014)
Vincent Conitzer ACM Doctoral Dissertation Award
Honorable Mention (2007) ACM Doctoral Dissertation Award
Honorable Mention (2007)
Joseph Halpern ACM AAAI Allen Newell Award (2008)
ACM Fellows (2002)
Monika Henzinger ACM Fellows (2016)
Anna Karlin ACM Fellows (2012)
Peter B. Key ACM Fellows (2011)
Jon Kleinberg ACM AAAI Allen Newell Award (2014)
ACM Fellows (2013)
ACM Prize in Computing (2008)
Yishay Mansour ACM Fellows (2014)
Silvio Micali ACM A. M. Turing Award (2012)
Noam Nissan ACM Doctoral Dissertation Award
Series Winner (1990) ACM Doctoral Dissertation Award
Series Winner (1990)
David M Pennock ACM Senior Member (2006)
Tim Roughgarden ACM Grace Murray Hopper Award (2009)
ACM Doctoral Dissertation Award
Honorable Mention (2002)
Tuomas Sandholm ACM Fellows (2008)
Assaf Schuster ACM Fellows (2015)
Aravind Srinivasan ACM Fellows (2014)
Eva Tardos ACM Fellows (1998)
Moshe Tennenholtz ACM AAAI Allen Newell Award (2012)
Salil P Vadhan ACM Doctoral Dissertation Award (2000)
Ingmar Weber ACM Senior Member (2017)
Michael Wooldridge ACM Fellows (2015)

First Name Last Name Paper Counts
Tim Roughgarden 5
Randolph McAfee 5
Ian Kash 4
Avinatan Hassidim 3
Robert Kleinberg 3
Martin Hoefer 3
Ariel Procaccia 3
Moshe Babaioff 3
Paul Dütting 3
Monika Henzinger 3
Yonatan Aumann 3
Moshe Tennenholtz 3
David Parkes 3
Yishay Mansour 3
Dimitris Fotakis 2
Arpita Ghosh 2
Rahul Savani 2
Nicholas Jennings 2
David Sarne 2
Alexander Skopalik 2
Yiling Chen 2
Maria Balcan 2
Aaron Roth 2
George Christodoulou 2
Georgios Piliouras 2
Thomas Keßelheim 2
Michal Feldman 2
Balasubramanian Sivan 2
Martin Starnberger 2
Sergei Vassilvitskii 2
Anna Karlin 2
Asuman Ozdaglar 2
David Easley 2
Vahab Mirrokni 2
Paul Goldberg 2
Rann Smorodinsky 2
Tüomas Sandholm 2
Nisarg Shah 2
Martin Gairing 2
Yair Dombb 2
Nikhil Devanur 2
Abraham Othman 2
Nima Haghpanah 2
Nicole Immorlica 2
Davide Bilò 1
Luciano Gualà 1
Rolf Niedermeier 1
Daron Acemoğlu 1
Marina Epelman 1
Drew Fudenberg 1
Orna Agmon Ben-Yehuda 1
Assaf Schuster 1
Yuval Emek 1
Siddharth Suri 1
Evdokia Nikolova 1
Brendan Lucier 1
Azarakhsh Malekian 1
Aparna Das 1
Silvio Micali 1
Bem Roberts 1
Peter Key 1
Zhiyi Huang 1
Qiqi Yan 1
Berthold Vöcking 1
Nick Gravin 1
Atsushi Iwasaki 1
Makoto Yokoo 1
Stefano Leonardi 1
Yu Zhang 1
Rebecca Wright 1
Michael Schapira 1
Alon Rosen 1
Maria Polukarov 1
Moshe Tennenholtz 1
Rakefet Rozen 1
Tobias Harks 1
Ofir Geri 1
Kamesh Munagala 1
Khaled Elbassioni 1
Guido Schäfer 1
Rob Van Stee 1
Tomasz Michalak 1
Agata Chrobak 1
Bo Tang 1
Gowtham Srinivasan 1
Mallesh Pai 1
Yaron Singer 1
Amos Azaria 1
Ruggiero Cavallo 1
Peter Troyan 1
Omer Tamuz 1
Elliot Anshelevich 1
Arunava Sen 1
Konstantinos Kollias 1
Siddharth Barman 1
Dan Tsafrir 1
Arpita Ghosh 1
Haim Kaplan 1
Ioannis Giotis 1
Scott Kominers 1
Ioannis Caragiannis 1
Nitish Korula 1
Éva Tardos 1
Jason Hartline 1
Majid Khonji 1
Carola Doerr 1
Talal Rahwan 1
Moran Feldman 1
Felix Brandt 1
Eric Friedman 1
Joseph Halpern 1
Guido Proietti 1
Ingmar Weber 1
Jiehua Chen 1
Gleb Polevoy 1
Laurens Cherchye 1
Jens Witkowski 1
Shreyas Sekar 1
Stanko Dimitrov 1
Mihaela Schaar 1
Muli Ben-Yehuda 1
Daniel Reeves 1
Shaili Jain 1
Yiling Chen 1
Iftah Gamzu 1
Jugal Garg 1
László Végh 1
Aravind Srinivasan 1
Stratis Ioannidis 1
Dinan Gunawardena 1
Bach Ha 1
Ozan Candogan 1
Jennifer Vaughan 1
Deepayan Chakrabarti 1
Chikin Chau 1
Benjamin Doerr 1
Felix Fischer 1
Ilya Segal 1
Suguru Ueda 1
Robert Bredereck 1
Ercan Yildiz 1
Yakov Babichenko 1
Yishay Mansour 1
David Pennock 1
Vincent Conitzer 1
Michael Schwarz 1
Lawrence Blume 1
Yuval Peres 1
Erik Vee 1
Bart Keijzer 1
Christos Tzamos 1
Michael Wooldridge 1
Okke Schrijvers 1
Markus Brill 1
Jing Chen 1
Stefan Kratsch 1
Gerhard Woeginger 1
Anna Scaglione 1
Elchanan Mossel 1
Jaeok Park 1
Mihaela Van Der Schaar 1
Stefan Eilts 1
Bart Smeulders 1
Bram De Rock 1
Rafael Frongillo 1
Chaitanya Swamy 1
Yuanzhang Xiao 1
Swaprava Nath 1
Aaron Jaggard 1
Neil Lutz 1
Shai Vardi 1
John Fearnley 1
Victor Naroditskiy 1
Victor Shnayder 1
Pranav Dandekar 1
Matthew Cary 1
Kurtis Heimerl 1
Pablo Azar 1
Stephen Chong 1
Jon Kleinberg 1
Pablo Parrilo 1
Poan Chen 1
Weidong Ma 1
Simina Brânzei 1
Aleksandrs Slivkins 1
Amin Saberi 1
Susanne Albers 1
Frits Spieksma 1
Koushik Kar 1
Alexander Peysakhovich 1
Noam Livne 1
Mike Ruberry 1
Sam Ganzfried 1
Noam Nisan 1
Saeed Alaei 1
Sara Krehbiel 1
Jinwoo Shin 1
Kshipra Bhawalkar 1
Tal Moran 1
George Pierrakos 1
Jacob Abernethy 1
Allan Borodin 1
David Kempe 1
Xujin Chen 1
Annamária Kovács 1
Alkmini Sgouritsa 1
Ioannis Caragiannis 1
Pichayut Jirapinyo 1
Hau Chan 1
Riccardo Colini-Baldeschi 1
Noga Alon 1
Eyal Even-Dar 1
Liam Roditty 1
Martin Bichler 1
Emmanouil Zampetakis 1
Rahul Sami 1
Avrim Blum 1
Renato PaesLeme 1
Christopher Wilkens 1
Daniel Goldstein 1
Patrick Hummel 1
Philipp Von Falkenhausen 1
Jeff Shamma 1
Benjamin Edelman 1
Claire Mathieu 1
Inbal Talgam-Cohen 1
Cam Nguyen 1
Elias Koutsoupias 1
Xiaodong Hu 1
Piotr Szczepański 1
Angelo Fanelli 1
John Lai 1
Benjamin Lubin 1
David Pennock 1
Jonathan Ullman 1

Affiliation Paper Counts
Universite Libre de Bruxelles 1
Ecole Normale Superieure 1
University of Illinois at Urbana-Champaign 1
Humboldt University of Berlin 1
University of Michigan 1
Warsaw University of Technology 1
Yale University 1
Universite Paris 7- Denis Diderot 1
The University of Hong Kong 1
Universitat Politecnica de Catalunya 1
CNRS Centre National de la Recherche Scientifique 1
Vrije Universiteit Amsterdam 1
University of Sassari 1
Le Moyne College 1
Center for Mathematics and Computer Science - Amsterdam 1
National Chiao Tung University Taiwan 1
The Interdisciplinary Center Herzliya 1
University of California, Davis 1
University of Augsburg 1
RWTH Aachen University 1
University of Toronto 1
Yonsei University 1
University of L'Aquila 1
Boston University 1
Texas A and M University 1
University of Virginia 1
Trinity University 1
University of Freiburg 1
Naval Research Laboratory 1
University of Roma Tor Vergata 1
Swiss Federal Institute of Technology, Lausanne 1
University of Athens 1
University of Aarhus 1
Columbia University 1
TECH Lab 1
University of Cambridge 1
Korea Advanced Institute of Science & Technology 1
University of Electro-Communications 1
Eindhoven University of Technology 1
Yahoo Inc. 1
King Abdullah University of Science and Technology 1
Singapore University of Technology and Design 1
Qatar Computing Research institute 1
Stony Brook University 2
University of Warsaw 2
University of Patras 2
Indian Statistical Institute (Delhi Centre) 2
California Institute of Technology 2
Weizmann Institute of Science Israel 2
Microsoft Research Cambridge 2
University of Roma La Sapienza 2
Hebrew University of Jerusalem 2
Duke University 2
National Technical University of Athens 2
Kyushu University 2
Swiss Federal Institute of Technology, Zurich 2
Yahoo Research Labs 2
University of Texas at Austin 2
Rutgers, The State University of New Jersey 2
University of Maryland 3
Technical University of Munich 3
University of Waterloo 3
Microsoft Corporation 3
University of Oxford 3
University of Southern California 3
London School of Economics and Political Science 3
Catholic University of Leuven, Leuven 3
Rensselaer Polytechnic Institute 3
Georgia Institute of Technology 4
University of Washington, Seattle 4
Masdar Institute of Science and Technology 4
University of Southampton 4
Northwestern University 5
University of Pennsylvania 5
University of California, Los Angeles 5
University of Vienna 5
Technical University of Berlin 5
Max Planck Institute for Informatics 7
Technion - Israel Institute of Technology 8
University of California, Berkeley 8
Tel Aviv University 9
Carnegie Mellon University 10
University of Liverpool 10
Massachusetts Institute of Technology 10
Bar-Ilan University 11
Stanford University 12
Cornell University 12
Harvard University 16
Microsoft Research 25

###### All ACM Journals | See Full Journal Index

Search TEAC
enter search term and/or author name