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: Approximating Revenue and Welfare

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.

#### 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.

#### Applications of $\alpha$-strongly regular distributions to Bayesian auctions

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.

Sequential Posted Price Mechanisms with Correlated Valuations

We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted price mechanisms are conceptually simple mechanisms that work by proposing a "take-it-or-leave-it" offer to each buyer. We apply sequential posted price mechanisms to single-parameter multi-unit settings in which each buyer demands only one item and the mechanism can assign the service to at most $k$ of the buyers. For standard sequential posted price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the the case of a continuous valuation distribution when various standard assumptions hold simultaneously (i.e., everywhere-supported, continuous, symmetric, and normalized (conditional) distributions that satisfy regularity, the MHR condition, and affiliation). In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted price mechanism is proportional to ratio of the highest and lowest possible valuation. We prove that a simple generalization of these mechanisms allows to achieve a better revenue performance: if the sequential posted price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then an Omega(1/max{1,d}) fraction of the optimal revenue can be extracted, where d denotes the degree of dependence of the valuations, ranging from complete independence (d=0) to arbitrary dependence (d = n-1). In order to prove this result we generalize the sequential posted price mechanisms further, such that the mechanism has the ability to make a take-it-or-leave-it offer to the i-th buyer that depends on the valuations of all buyers except i's. We prove that a constant fraction (2 - sqrt(e))/4 (approximately 0.088) of the optimal revenue can be always extracted by this generalized mechanism.

### 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 Fellows (2017)
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)
Rebecca N. Wright ACM Distinguished Member (2017)

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
Monika Henzinger 3
Paul Dütting 3
Yonatan Aumann 3
Moshe Tennenholtz 3
David Parkes 3
Yishay Mansour 3
Arpita Ghosh 2
Dimitris Fotakis 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
Thomas Keßelheim 2
Georgios Piliouras 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
Pablo Azar 1
Poan Chen 1
Simina Brânzei 1
Stephen Chong 1
Jon Kleinberg 1
Pablo Parrilo 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
Saeed Alaei 1
Noam Nisan 1
Allan Borodin 1
Xujin Chen 1
Sara Krehbiel 1
Jinwoo Shin 1
Kshipra Bhawalkar 1
Tal Moran 1
Jacob Abernethy 1
Annamária Kovács 1
David Kempe 1
George Pierrakos 1
Alkmini Sgouritsa 1
Pichayut Jirapinyo 1
Hau Chan 1
Ioannis Caragiannis 1
Riccardo Colini-Baldeschi 1
Noga Alon 1
Eyal Even-Dar 1
Liam Roditty 1
Rahul Sami 1
Avrim Blum 1
Martin Bichler 1
Emmanouil Zampetakis 1
Renato PaesLeme 1
Christopher Wilkens 1
Patrick Hummel 1
Jeff Shamma 1
Daniel Goldstein 1
Philipp Von Falkenhausen 1
Benjamin Edelman 1
Claire Mathieu 1
Xiaodong Hu 1
Piotr Szczepański 1
Inbal Talgam-Cohen 1
Elias Koutsoupias 1
Cam Nguyen 1
John Lai 1
Benjamin Lubin 1
Jonathan Ullman 1
David Pennock 1
Angelo Fanelli 1
Davide Bilò 1
Luciano Gualà 1
Daron Acemoğlu 1
Rolf Niedermeier 1
Marina Epelman 1
Drew Fudenberg 1
Orna Agmon Ben-Yehuda 1
Assaf Schuster 1
Yuval Emek 1
Evdokia Nikolova 1
Azarakhsh Malekian 1
Siddharth Suri 1
Brendan Lucier 1
Aparna Das 1
Silvio Micali 1
Zhiyi Huang 1
Qiqi Yan 1
Bem Roberts 1
Peter Key 1
Berthold Vöcking 1
Nick Gravin 1
Atsushi Iwasaki 1
Makoto Yokoo 1
Stefano Leonardi 1
Yu Zhang 1
Michael Schapira 1
Rebecca Wright 1
Alon Rosen 1
Maria Polukarov 1
Moshe Tennenholtz 1
Rakefet Rozen 1
Tobias Harks 1
Khaled Elbassioni 1
Ofir Geri 1
Rob Van Stee 1
Tomasz Michalak 1
Agata Chrobak 1
Kamesh Munagala 1
Guido Schäfer 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
Konstantinos Kollias 1
Siddharth Barman 1
Dan Tsafrir 1
Arunava Sen 1
Ioannis Giotis 1
Arpita Ghosh 1
Haim Kaplan 1
Majid Khonji 1
Scott Kominers 1
Carola Doerr 1
Talal Rahwan 1
Ioannis Caragiannis 1
Nitish Korula 1
Éva Tardos 1
Jason Hartline 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
Shreyas Sekar 1
Stanko Dimitrov 1
Mihaela Schaar 1
Muli Ben-Yehuda 1
Shaili Jain 1
Jens Witkowski 1
Daniel Reeves 1
Yiling Chen 1
Iftah Gamzu 1
Aravind Srinivasan 1
Stratis Ioannidis 1
Deepayan Chakrabarti 1
Jugal Garg 1
László Végh 1
Chikin Chau 1
Benjamin Doerr 1
Bach Ha 1
Ozan Candogan 1
Jennifer Vaughan 1
Dinan Gunawardena 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
Erik Vee 1
Michael Schwarz 1
Bart Keijzer 1
Christos Tzamos 1
Michael Wooldridge 1
Lawrence Blume 1
Okke Schrijvers 1
Yuval Peres 1
Markus Brill 1
Jing Chen 1
Elchanan Mossel 1
Stefan Kratsch 1
Gerhard Woeginger 1
Anna Scaglione 1
Jaeok Park 1
Mihaela Van Der Schaar 1
Stefan Eilts 1
Bart Smeulders 1
Bram De Rock 1
Aaron Jaggard 1
Neil Lutz 1
Chaitanya Swamy 1
Yuanzhang Xiao 1
Victor Shnayder 1
Rafael Frongillo 1
Swaprava Nath 1
Shai Vardi 1
John Fearnley 1
Victor Naroditskiy 1
Pranav Dandekar 1
Matthew Cary 1
Kurtis Heimerl 1
Weidong Ma 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
Weizmann Institute of Science Israel 2
University of Warsaw 2
National Technical University of Athens 2
Microsoft Research Cambridge 2
Yahoo Research Labs 2
University of Roma La Sapienza 2
California Institute of Technology 2
University of Patras 2
Rutgers, The State University of New Jersey 2
Hebrew University of Jerusalem 2
Duke University 2
Stony Brook University 2
Kyushu University 2
Swiss Federal Institute of Technology, Zurich 2
University of Texas at Austin 2
Indian Statistical Institute (Delhi Centre) 2
University of Waterloo 3
London School of Economics and Political Science 3
University of Maryland 3
University of Southern California 3
University of Oxford 3
Microsoft Corporation 3
Rensselaer Polytechnic Institute 3
Catholic University of Leuven, Leuven 3
Technical University of Munich 3
University of Southampton 4
Georgia Institute of Technology 4
Khalifa University 4
University of Washington, Seattle 4
Northwestern University 5
University of Pennsylvania 5
University of Vienna 5
Technical University of Berlin 5
University of California, Los Angeles 5
Max Planck Institute for Informatics 7
University of California, Berkeley 8
Massachusetts Institute of Technology 8
Technion - Israel Institute of Technology 8
Tel Aviv University 9