ACM Transactions on

Economics and Computation (TEAC)

Latest Articles

An Antifolk Theorem for Large Repeated Games

In this article, we study infinitely repeated games in settings of imperfect monitoring. We first prove a family of theorems showing that when the signals observed by the players satisfy a condition known as (ε, γ)-differential privacy, the folk theorem has little bite: for values of ε and γ sufficiently small, for a fixed... (more)

On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions

We study mechanisms for the combinatorial auction (CA) problem, in which m objects are sold to rational agents and the goal is to maximize social... (more)

Robust Quantitative Comparative Statics for a Multimarket Paradox

We introduce a quantitative approach to comparative statics that allows to bound the maximum effect of an exogenous parameter change on a... (more)

When Does Improved Targeting Increase Revenue?

In second-price auctions, we find that improved targeting via enhanced information disclosure decreases revenue when there are two bidders and increases revenue if there are at least four symmetric bidders with values drawn from a distribution with a monotone hazard rate. With asymmetries, improved targeting increases revenue if the most frequent... (more)

A Rational Convex Program for Linear Arrow-Debreu Markets

We present a new flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously... (more)

Truthful Mechanisms for Combinatorial Allocation of Electric Power in Alternating Current Electric Systems for Smart Grid

Traditional studies of combinatorial auctions often only consider linear constraints. The rise of... (more)


Call for Nominations, Co-Editors-In-Chief

The term of the current co-Editors-in-Chief of the ACM Transactions on Economics and Computation is coming to an end, and the ACM Publications Board has set up a search committee to assist in selecting the next Editor-in-Chief or co-Editors-in-Chief.

TEAC started taking submissions in August 2011, and has been experiencing steady growth, with 53 submissions received in 2014 and 56 submissions in 2015 as of October 31, 2015.

Nominations, including self-nominations, are invited for a three-year term as an Editor-in-Chief beginning on July 1, 2016.

read more

About TEAC

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.

read more

Do Capacity Constraints Constrain Coalitions?

We study strong equilibria in symmetric capacitated cost-sharing games.
In these games, a graph with designated source s and sink t is given, and each edge is associated with some cost.
Each agent chooses strategically an s-t path, knowing that the cost of each edge is shared equally between all agents using it.
Two variants of cost-sharing games have been previously studied: (i) games where coalitions can form, and (ii) games where edges are associated with capacities; both variants are inspired by real-life scenarios.
In this work we combine these variants and analyze strong equilibria (profiles where no coalition can deviate) in capacitated games.
This combination gives rise to new phenomena that do not occur in the previous variants.
Our contribution is two-fold.
First, we provide a topological characterization of networks that always admit a strong equilibrium.
Second, we establish tight bounds on the efficiency loss that may be incurred due to strategic behavior, as quantified by the strong price of anarchy (and stability) measures.
Interestingly, our results are qualitatively different than those obtained in the analysis of each variant alone, and the combination of coalitions and capacities entails the introduction of more refined topology classes than previously studied.

Computing Dominance-Based Solution Concepts

Two common criticisms of Nash equilibrium are its dependence on very demanding epistemic assumptions and its computational intractability. We study the computational properties of less demanding set-valued solution concepts that are based on varying notions of dominance. These concepts are intuitively appealing, always exist, and admit unique minimal solutions in important subclasses of games. Examples include Shapley's saddles, Harsanyi and Selten's primitive formations, Basu and Weibull's CURB sets, and Dutta and Laslier's minimal covering set. Based on a unifying framework proposed by Duggan and Le Breton, we formulate two generic algorithms for computing these concepts and investigate for which classes of games and which properties of the underlying dominance notion the algorithms are sound and efficient. We identify two sets of conditions that are sufficient for polynomial-time computability and show that the conditions are satisfied, for instance, by saddles and primitive formations in normal-form games, minimal CURB sets in two-player games, and the minimal covering set in symmetric matrix games. Our positive algorithmic results explain regularities observed in the literature, but also apply to several solution concepts whose computational complexity was unknown.

Risk Sensitivity of Price of Anarchy under Uncertainty

In game theory, the price of anarchy framework studies efficiency loss in decentralized environments. Optimization and decision theory, on the other hand, explore tradeoffs between optimality and robustness in the case of single agent decision making under uncertainty. If an agent guards against worst case guarantees, then his actions tend to be suboptimal on average.

We examine connections between the efficiency loss due to decentralization and the efficiency loss due to uncertainty and establish tight performance guarantees for distributed systems in uncertain environments. We present applications of this framework to novel variants of atomic congestion games with uncertain costs, for which we provide tight performance bounds under a wide range of risk attitudes. Our results establish that the individual's attitude towards uncertainty has a critical effect on system performance and therefore should be a subject of close and systematic investigation.

Mechanism Design for Fair Division: Allocating Divisible Items without Payments

We revisit the classic problem of fair division from a mechanism design perspective, using {\em Proportional Fairness} as a benchmark. In particular, we aim to allocate a collection of divisible items to a set of agents while incentivizing the agents to be truthful in reporting their valuations. For the very large class of homogeneous valuations, we design a truthful mechanism that provides {\em every agent} with at least a $1/e\approx 0.368$ fraction of her Proportionally Fair valuation. To complement this result, we show that no truthful mechanism can guarantee more than a $0.5$ fraction, even for the restricted class of additive linear valuations. We also propose another mechanism for additive linear valuations that works really well when every item is highly demanded. To guarantee truthfulness, our mechanisms discard a carefully chosen fraction of the allocated resources; we conclude by uncovering interesting connections between our mechanisms and known mechanisms that use money instead.

The AND-OR Game

We consider a simple simultaneous first price auction for two
identical items in a complete information setting. Our goal is to analyze this setting, for a simple, yet highly interesting, AND-OR game, where one agent is single minded and the other is unit demand. We find a mixed equilibrium
of this game, and show that every other equilibrium admits the same expected allocation and payments. In addition, we study the equilibrium, highlighting the change in revenue and social welfare as a function of the players' valuations.

Affine Maximizers in Domains with Selfish Valuations

We consider the domain of selfish and continuous preferences over a ``rich'' allocation space and show that onto, strategyproof and allocation non-bossy social choice functions are affine maximizers. Roberts (1979) proves this result for a finite set of alternatives and an unrestricted valuation space. In this paper, we show that in a sub-domain of the unrestricted valuations with the additional assumption of allocation non-bossiness, using the richness of the allocations, the strategyproof social choice functions can be shown to be affine maximizers. We provide an example to show that allocation non-bossiness is indeed critical for this result. This work shows that an affine maximizer result needs certain amount of richness split across valuations and allocations.

Author Rights

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.


Publication Years 2013-2016
Publication Count 95
Citation Count 116
Available for Download 95
Downloads (6 weeks) 670
Downloads (12 Months) 4827
Downloads (cumulative) 14080
Average downloads per article 148
Average citations per article 1
First Name Last Name Award
Vincent Conitzer ACM Doctoral Dissertation Award
Honorable Mention (2007) ACM Doctoral Dissertation Award
Honorable Mention (2007)
Jon Kleinberg ACM AAAI Allen Newell Award (2014)
ACM Prize in Computing (2008)
Silvio Micali ACM A. M. Turing Award (2012)
David M Pennock ACM Senior Member (2006)
Tim Roughgarden ACM Grace Murray Hopper Award (2009)
ACM Doctoral Dissertation Award
Honorable Mention (2002)
Moshe Tennenholtz ACM AAAI Allen Newell Award (2012)
Salil P Vadhan ACM Doctoral Dissertation Award (2000)

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

Affiliation Paper Counts
Universite Libre de Bruxelles 1
Ecole Normale Superieure 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 Texas at Austin 1
University of California, Davis 1
RWTH Aachen University 1
Yonsei University 1
University of L'Aquila 1
Harvard Business School 1
Boston University 1
Texas A and M University 1
University of Virginia 1
University of Freiburg 1
Swiss Federal Institute of Technology, Zurich 1
University of Roma Tor Vergata 1
Swiss Federal Institute of Technology, Lausanne 1
University of Athens 1
University of Aarhus 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
Masdar Institute of Science and Technology 1
Qatar Computing Research institute 1
University of Paderborn 2
Indian Statistical Institute (Delhi Centre) 2
Yahoo Research Labs 2
University of Roma La Sapienza 2
California Institute of Technology 2
University of Patras 2
University of Southern California 2
University of Oxford 2
Microsoft 2
Microsoft Research Cambridge 2
Weizmann Institute of Science Israel 2
University of Warsaw 2
Kyushu University 2
Duke University 2
London School of Economics and Political Science 2
National Technical University of Athens 2
Catholic University of Leuven 3
University of Maryland 3
University of Waterloo 3
Chinese Academy of Sciences 3
University of Pennsylvania 3
Georgia Institute of Technology 4
Technical University of Berlin 4
University of Southampton 4
University of Washington 4
University of California, Los Angeles 5
Tel Aviv University 5
Northwestern University 5
University of Vienna 5
Max Planck Institute for Informatics 7
Google Inc. 8
University of California, Berkeley 8
Bar-Ilan University 8
Technion - Israel Institute of Technology 8
Massachusetts Institute of Technology 10
University of Liverpool 10
Carnegie Mellon University 10
Stanford University 12
Cornell University 12
Harvard University 15
Microsoft Research 21
All ACM Journals | See Full Journal Index