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
The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms and Fundamental Limits

We study the value of data privacy in a game-theoretic model of trading private data, where a data collector purchases private data from strategic data subjects (individuals) through an incentive mechanism. The private data of each individual represents her knowledge about an underlying state, which is the information that the data collector desires to learn. Different from most of the existing work on privacy-aware surveys, our model does not assume the data collector to be trustworthy. Then, an individual takes full control of its own data privacy and reports only a privacy-preserving version of her data.

In this paper, the value of $\epsilon$ units of privacy is measured by the minimum payment of all nonnegative payment mechanisms, under which an individual's best response at a Nash equilibrium is to report her data in an $\epsilon$-locally differentially private manner. The higher $\epsilon$ is, the less private the reported data is. We derive lower and upper bounds on the value of privacy which are asymptotically tight as the number of data subjects becomes large. Specifically, the lower bound assures that it is impossible to use lower payment to buy $\epsilon$ units of privacy, and the upper bound is given by an achievable payment mechanism that we designed. Based on these fundamental limits, we further derive lower and upper bounds on the minimum total payment for the data collector to achieve a given learning accuracy target, and show that the total payment of the designed mechanism is at most one individual's payment away from the minimum.

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.

Cardinal Contests

We model and analyze cardinal contests, where a principal running a rank-order tournament has access to an absolute measure of the quality of agents' submissions in addition to their relative rankings. We show that a mechanism that compares each agent's output quality against a threshold to decide whether to award her the prize corresponding to her rank is optimal amongst the set of all mixed cardinal-ordinal mechanisms where the j-th ranked submission receives a fraction of the j-th prize that is a non-decreasing function of the submission's quality. Furthermore, the optimal threshold mechanism uses exactly the same threshold for each rank.

Causal Strategic Inference in a Game-Theoretic Model of Multiplayer Networked Microfinance Markets

Performing interventions is a major challenge in economic policy-making. We propose causal strategic inference as a framework for conducting interventions and apply it to large, networked microfinance economies. The basic solution platform consists of modeling a microfinance market as a networked economy, learning the parameters of the model from the real-world microfinance data, and designing algorithms for various causal questions. For a special case of our model, we show that an equilibrium point always exists and that the equilibrium interest rates are unique. For the general case, we give a constructive proof of the existence of an equilibrium point. Our empirical study is based on the microfinance data from Bangladesh and Bolivia, which we use to first learn our models. We show that causal strategic inference can assist policy-makers by evaluating the outcomes of various types of interventions, such as removing a loss-making bank from the market, imposing an interest-rate cap, and subsidizing banks.

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.

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.

Valuation Compressions in VCG-Based Combinatorial Auctions

The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions the truthful direct-revelation mechanism that maximizes social welfare is the VCG mechanism. For many valuation spaces computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that the welfare loss increases in expressiveness. All our bounds apply to equilibrium concepts that can be computed in polynomial time as well as to learning outcomes.


Bibliometrics

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

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