ACM DL

ACM Transactions on

Economics and Computation (TEAC)

Menu
Latest Articles

∃R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria

Pricing Equilibria and Graphical Valuations

Competitive Packet Routing with Priority Lists

NEWS

New Editors-In-Chief

David Pennock and Ilya Segal took over as co-Editors-in-Chief in March 2017.


About TEAC

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: read more

Forthcoming Articles
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.

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.

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)}$.

Near-Optimum Online Ad Allocation for Targeted Advertising

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.


Bibliometrics

Publication Years 2013-2018
Publication Count 118
Citation Count 232
Available for Download 118
Downloads (6 weeks) 473
Downloads (12 Months) 4129
Downloads (cumulative) 20301
Average downloads per article 172
Average citations per article 2
First Name Last Name Award
Noga Alon ACM Fellows (2016)
Allan Borodin ACM Fellows (2014)
Richard J Cole ACM Fellows (1998)
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)
Ruta Mehta ACM India Doctoral Dissertation Award (2012)
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)
Christos Papadimitriou ACM Fellows (2001)
David M Pennock ACM Senior Member (2006)
Tim Roughgarden ACM Grace Murray Hopper Award (2009)
ACM Doctoral Dissertation Award
Honorable Mention (2002)
Aviad Rubinstein ACM Doctoral Dissertation Award (2017)
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)
Vijay Vazirani ACM Fellows (2005)
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
Paul Dütting 3
Asuman Ozdaglar 3
Martin Hoefer 3
Moshe Tennenholtz 3
Moshe Babaioff 3
Ariel Procaccia 3
Yonatan Aumann 3
Yishay Mansour 3
Monika Henzinger 3
David Parkes 3
Avinatan Hassidim 3
Robert Kleinberg 3
Rann Smorodinsky 2
Paul Goldberg 2
Allan Borodin 2
Vahab Mirrokni 2
David Easley 2
Dimitris Fotakis 2
Arpita Ghosh 2
Rahul Savani 2
David Sarne 2
Alexander Skopalik 2
Yiling Chen 2
Maria Balcan 2
Aaron Roth 2
George Christodoulou 2
Georgios Piliouras 2
Tobias Harks 2
Thomas Keßelheim 2
Michal Feldman 2
Balasubramanian Sivan 2
Stefano Leonardi 2
Martin Starnberger 2
Sergei Vassilvitskii 2
Anna Karlin 2
Nicole Immorlica 2
Pablo Parrilo 2
Nisarg Shah 2
Tüomas Sandholm 2
Martin Gairing 2
Christos, Papadimitriou 2
Yair Dombb 2
Nikhil Devanur 2
Abraham Othman 2
Nima Haghpanah 2
Felix Fischer 2
Shaddin Dughmi 2
Ozan Candogan 2
Jugal Garg 2
Nicholas Jennings 2
Simina Brânzei 2
Davide Bilò 1
Luciano Gualà 1
Rolf Niedermeier 1
Daron Acemoğlu 1
Drew Fudenberg 1
Marina Epelman 1
Orna Agmon Ben-Yehuda 1
Assaf Schuster 1
Yuval Emek 1
Siddharth Suri 1
Brendan Lucier 1
Azarakhsh Malekian 1
Aparna Das 1
Evdokia Nikolova 1
Nadia Fawaz 1
Silvio Micali 1
Bem Roberts 1
Peter Key 1
Zhiyi Huang 1
Qiqi Yan 1
Berthold Vöcking 1
Liad Blumrosen 1
Nick Gravin 1
Antje Bjelde 1
Marek Adamczyk 1
Kristoffer Hansen 1
Yiannis Giannakopoulos 1
Daniel Schmand 1
Satoru Fujishige 1
Atsushi Iwasaki 1
Makoto Yokoo 1
Yu Zhang 1
Rebecca Wright 1
Michael Schapira 1
Hadi Minooei 1
MohammadHossein Bateni 1
Aviad Rubinstein 1
Alon Rosen 1
Maria Polukarov 1
Moshe Tennenholtz 1
Rakefet Rozen 1
Rob Van Stee 1
Khaled Elbassioni 1
Agata Chrobak 1
Ofir Geri 1
Guido Schäfer 1
Tomasz Michalak 1
Kamesh Munagala 1
Bo Tang 1
Amos Azaria 1
Gowtham Srinivasan 1
Mallesh Pai 1
Yaron Singer 1
Sanjeev Khanna 1
Shravas Rao 1
Vijay Vazirani 1
Ruggiero Cavallo 1
Peter Troyan 1
Omer Tamuz 1
Elliot Anshelevich 1
Siddharth Barman 1
Arunava Sen 1
Dan Tsafrir 1
Konstantinos Kollias 1
Arpita Ghosh 1
Haim Kaplan 1
Carola Doerr 1
Ioannis Giotis 1
Scott Kominers 1
Majid Khonji 1
Talal Rahwan 1
Ioannis Caragiannis 1
Nitish Korula 1
Éva Tardos 1
Jason Hartline 1
Moran Feldman 1
Felix Brandt 1
Yang Li 1
Bart De Keijzer 1
Laura Koch 1
Eric Friedman 1
Joseph Halpern 1
Guido Proietti 1
Ingmar Weber 1
Jiehua Chen 1
Laurens Cherchye 1
Gleb Polevoy 1
Shreyas Sekar 1
Jens Witkowski 1
Daniel Reeves 1
Stanko Dimitrov 1
Mihaela Schaar 1
Muli Ben-Yehuda 1
Iftah Gamzu 1
Deepayan Chakrabarti 1
Shaili Jain 1
Yiling Chen 1
László Végh 1
Benjamin Doerr 1
Chikin Chau 1
Aravind Srinivasan 1
Salil Vadhan 1
Stratis Ioannidis 1
Dinan Gunawardena 1
Bach Ha 1
Jennifer Vaughan 1
Ilya Segal 1
Max Klimm 1
Diodato Ferraioli 1
Maria Kyropoulou 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
Yuval Peres 1
Okke Schrijvers 1
Markus Brill 1
Jing Chen 1
Richard Cole 1
Peter Miltersen 1
Mohammad Mahdian 1
Daniel Fragiadakis 1
Stefan Kratsch 1
Elchanan Mossel 1
Anna Scaglione 1
Gerhard Woeginger 1
Jaeok Park 1
Mihaela Van Der Schaar 1
Stefan Eilts 1
Bart Smeulders 1
Bram De Rock 1
Rafael Frongillo 1
Salman Fadaei 1
Aaron Jaggard 1
Neil Lutz 1
Chaitanya Swamy 1
Shai Vardi 1
Yuanzhang Xiao 1
Swaprava Nath 1
John Fearnley 1
Ronen Gradwohl 1
Victor Naroditskiy 1
Victor Shnayder 1
Weidong Ma 1
Matthew Cary 1
Kurtis Heimerl 1
Poan Chen 1
Pranav Dandekar 1
Pablo Azar 1
Stephen Chong 1
Jon Kleinberg 1
Aleksandrs Slivkins 1
Sepehr Assadi 1
Rakesh Vohra 1
Ruta Mehta 1
Amin Saberi 1
Susanne Albers 1
Frits Spieksma 1
Koushik Kar 1
Alexander Peysakhovich 1
Noam Livne 1
Noam Nisan 1
Mike Ruberry 1
Sam Ganzfried 1
Xujin Chen 1
Saeed Alaei 1
Sara Krehbiel 1
Jinwoo Shin 1
Kshipra Bhawalkar 1
David Kempe 1
Tal Moran 1
Jacob Abernethy 1
George Pierrakos 1
Annamária Kovács 1
Alkmini Sgouritsa 1
Hau Chan 1
Pichayut Jirapinyo 1
Ioannis Caragiannis 1
Troels Lund 1
Britta Peis 1
Bjoern Tauer 1
Ping Zhan 1
Riccardo Colini-Baldeschi 1
Noga Alon 1
Eyal Even-Dar 1
Liam Roditty 1
Martin Bichler 1
Emmanouil Zampetakis 1
Morteza Zadimoghaddam 1
Rahul Sami 1
Avrim Blum 1
Renato PaesLeme 1
Daniel Goldstein 1
Patrick Hummel 1
Philipp Von Falkenhausen 1
Christopher Wilkens 1
Mohammad Mahdian 1
Xiaodong Hu 1
Benjamin Edelman 1
Claire Mathieu 1
Jeff Shamma 1
Piotr Szczepański 1
Inbal Talgam-Cohen 1
Cam Nguyen 1
Elias Koutsoupias 1
John Lai 1
Benjamin Lubin 1
David Pennock 1
Jonathan Ullman 1
Angelo Fanelli 1
Branislav Bošanský 1
Yoshio Sano 1
Sadra Yazdanbod 1

Affiliation Paper Counts
Universite Libre de Bruxelles 1
Ecole Normale Superieure 1
University of Michigan 1
University of Glasgow 1
Warsaw University of Technology 1
Yale University 1
Universite Paris 7- Denis Diderot 1
The University of Hong Kong 1
University of Salerno 1
Universitat Politecnica de Catalunya 1
CNRS Centre National de la Recherche Scientifique 1
Vrije Universiteit Amsterdam 1
University of Sassari 1
Edogawa University 1
Le Moyne College 1
Kyoto University 1
National Chiao Tung University Taiwan 1
The Interdisciplinary Center Herzliya 1
Czech Technical University in Prague 1
University of Tsukuba 1
University of California, Davis 1
Yonsei University 1
IT University of Copenhagen 1
University of L'Aquila 1
Harvard Business School 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 Chicago 1
Columbia University 1
TECH Lab 1
University of Cambridge 1
Korea Advanced Institute of Science & Technology 1
University of Wisconsin Madison 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
University of Augsburg 2
Weizmann Institute of Science Israel 2
Yahoo Research Labs 2
University of Texas at Austin 2
University of Toronto 2
Indian Statistical Institute (Delhi Centre) 2
California Institute of Technology 2
University of Patras 2
Rutgers, The State University of New Jersey 2
Stony Brook University 2
Swiss Federal Institute of Technology, Zurich 2
Microsoft Research Cambridge 2
Duke University 2
University of Paderborn 2
Kyushu University 2
Center for Mathematics and Computer Science - Amsterdam 2
National Technical University of Athens 2
University of Waterloo 3
University of Warsaw 3
Hebrew University of Jerusalem 3
London School of Economics and Political Science 3
Humboldt University of Berlin 3
University of Illinois at Urbana-Champaign 3
University of Roma La Sapienza 3
University of Aarhus 3
University of Southern California 3
Microsoft Corporation 3
Rensselaer Polytechnic Institute 3
Catholic University of Leuven, Leuven 3
University of Maryland 3
Technical University of Munich 3
Chinese Academy of Sciences 3
University of Washington, Seattle 4
Khalifa University 4
University of Oxford 4
University of Southampton 4
RWTH Aachen University 5
Technical University of Berlin 5
University of California, Los Angeles 5
Northwestern University 5
University of Vienna 5
Georgia Institute of Technology 6
Max Planck Institute for Informatics 7
Technion - Israel Institute of Technology 8
University of California, Berkeley 8
Massachusetts Institute of Technology 8
University of Pennsylvania 9
Tel Aviv University 9
Google Inc. 9
Carnegie Mellon University 10
University of Liverpool 11
Bar-Ilan University 11
Cornell University 12
Stanford University 12
Harvard University 16
Microsoft Research 25
 
All ACM Journals | See Full Journal Index

Search TEAC
enter search term and/or author name