ACM DL

ACM Transactions on

Economics and Computation (TEAC)

Menu
Latest Articles

Introduction to the Special Issue on EC'14

The Complexity of Fairness Through Equilibrium

Competitive equilibrium from equal incomes (CEEI) is a well-known fair allocation mechanism with desirable fairness and efficiency properties; however, with indivisible resources, a CEEI may not exist [Foley 1967; Varian 1974; Thomson and Varian 1985]. It was shown in Budish [2011] that in the case of indivisible resources, there is always an... (more)

Local Computation Mechanism Design

We introduce the notion of local computation mechanism design—designing game-theoretic mechanisms that run in polylogarithmic time and space. Local computation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. When the mechanism employs... (more)

Optimal Contest Design for Simple Agents

Incentives are more likely to elicit desired outcomes when they are designed based on accurate models of agents’ strategic behavior. A growing literature, however, suggests that people do not quite behave like standard economic agents in a variety of environments, both online and offline. What consequences might such differences have for the... (more)

Recency, Records, and Recaps

Nash equilibrium takes optimization as a primitive, but suboptimal behavior can persist in simple stochastic decision problems. This has motivated the development of other equilibrium concepts such as cursed equilibrium and behavioral equilibrium. We experimentally study a simple adverse selection (or “lemons”) problem and find that... (more)

Bounds for the Query Complexity of Approximate Equilibria

We analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective... (more)

Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

We study the deterministic and randomized query complexity of finding approximate equilibria in a k × k bimatrix game. We show that the... (more)

NEWS

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

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.

An Anti-Folk Theorem For Large Games with Imperfect Monitoring

We study infinitely repeated games in settings of imperfect monitoring. We first prove a family of theorems that show that when the signals observed by the players satisfy a condition known as (µ,³)-differential privacy, that the folk theorem has little bite: for values of µ and ³ sufficiently small, for a fixed discount factor, any equilibrium of the repeated game involve players playing approximate equilibria of the stage game in every period. Next, we argue that in large games (n player games in which unilateral deviations by single players have only a small impact on the utility of other players), many monitoring settings naturally lead to signals that satisfy (µ,³)-differential privacy, for µ and ³ tending to zero as the number of players n grows large. We conclude that in such settings, the set of equilibria of the repeated game collapse to the set of equilibria of the stage game. Our results nest and generalize previous results of Green (1980), Sabourian (1990) and suggest that differential privacy is a natural measure of the "largeness" of a game. Further, techniques from the literature on differential privacy allow us to prove quantitative bounds, where the existing literature focuses on limiting results.

A Rational Convex Program for Linear Arrow-Debreu Markets

We give a new, flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known ([Nenakov and Primak 1983; Jain 2007; Cornet 1989]), our program exhibits several new features. It gives a simple necessary and sufficient condition and a concise proof of the existence and rationality of equilibria, settling an open question raised by Vazirani [2012]. As a consequence we also obtain a simple new proof of Mertens's [2003] result that the equilibrium prices form a convex polyhedral set.

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 smart grid presents a new class of auctions, characterized by quadratic constraints. This paper studies the {\em complex-demand knapsack problem}, in which the demands are complex-valued and the capacity of supplies is described by the magnitude of total complex-valued demand. This naturally captures the power constraints in alternating current (AC) electric systems. In this paper, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known $\frac{1}{2}$-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful PTAS for the case $\phi\in[0,\frac{\pi}{2}-\delta]$, and a truthful FPTAS, which {\it fully} optimizes the objective function but violates the capacity constraint by at most $(1+\epsilon)$, for the case $\phi\in(\frac{\pi}{2},\pi-\delta]$, where $\phi$ is the maximum angle between any two complex-valued demands and $\epsilon,\delta>0$ are arbitrarily small constants. We complement these results by showing that, unless P=NP, neither a PTAS can exist for the case $\phi\in(\frac{\pi}{2},\pi-\delta]$ nor any bi-criteria approximation algorithm with polynomial guarantees for the case when $\phi$ is arbitrarily close to $\pi$ (that is, when $\delta$ is arbitrarily close $0$).

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.

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 system's equilibrium. The motivation for this approach is a well known paradox in multimarket Cournot competition, where a positive price shock on a monopoly market may actually reduce the monopolist's profit. We use our approach to quantify for the first time the worst case profit reduction for multimarket oligopolies exposed to arbitrary positive price shocks. For markets with affine price functions and firms with convex cost technologies, we show that the relative profit loss of \emph{any} firm is at most 25% no matter how many firms compete in the oligopoly. We further investigate the impact of positive price shocks on total profit of all firms as well as on social surplus. We find tight bounds also for these measures showing that total profit and social surplus decreases by at most 25% and 16.6%, respectively.

On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions

We study mechanisms for the combinatorial auction (CA) problem, in which $m$ objec
ts are sold to rational agents and the goal is to maximize social welfare.Of particular interest is the special case of $s$-CAs, where agents are interested in sets of size at most $s$, for which a simple greedy algorithm obtains an $s+1$
approximation but no deterministictruthful mechanism is known to attain an approximation ratio better than $O(m/\sqr
t{\log m})$. We view this as an extreme gap not only between
the power of greedy auctions and truthful greedy auctions, but also as
%an apparent
a conjectured largest gap between the known power of truthful and non-truthfulpolynomial time deterministic algorithms. We associate the notion of greediness with a broad class of algorithms, known as priority algorithms, which encapsulates many natural auction methods. This motivates us to ask: how well can a truthful greedy algorithm approximate the optimal social welfare for CA problems? We show that no truthful greedy priority algorithm can obtain an approximation to the CA problem that is sublinear in $m$, even for $s$-CAs with $s \geq 2$. We conclude that any truthful combinatorial auction mechanism with non-trivial approximation fact
or must fall outside the scope of many natural auction methods.

When Does Improved Targeting Increase Revenue?

In second-price auctions with symmetric bidders, 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 bidders. With asymmetries, improved targeting increases revenue if the most frequent winner wins less than 30.4% of the time, but can decrease revenue otherwise. We derive analogous results for position auctions. Finally, we show that revenue can vary non-monotonically with the number of bidders who are able to take advantage of improved targeting.

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.

Bibliometrics

Publication Years 2013-2016
Publication Count 89
Citation Count 100
Available for Download 89
Downloads (6 weeks) 294
Downloads (12 Months) 4551
Downloads (cumulative) 13098
Average downloads per article 147
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-Infosys Foundation Award in the Computing Sciences (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
Ian Kash 4
Randolph McAfee 4
Martin Hoefer 3
Moshe Tennenholtz 3
David Parkes 3
Monika Henzinger 3
Paul Dütting 3
Robert Kleinberg 3
Ariel Procaccia 3
Yishay Mansour 2
Rann Smorodinsky 2
Vahab Mirrokni 2
David Easley 2
Dimitris Fotakis 2
Arpita Ghosh 2
Asuman Ozdaglar 2
Alexander Skopalik 2
Nicholas Jennings 2
Yiling Chen 2
Maria Balcan 2
George Christodoulou 2
Thomas Keßelheim 2
Balasubramanian Sivan 2
Martin Starnberger 2
Sergei Vassilvitskii 2
Anna Karlin 2
Yonatan Aumann 2
Tüomas Sandholm 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
Nicole Immorlica 2
Davide Bilò 1
Luciano Gualà 1
Rolf Niedermeier 1
Marina Epelman 1
Orna Agmon Ben-Yehuda 1
Assaf Schuster 1
Daron Acemoğlu 1
Yuval Emek 1
Siddharth Suri 1
Azarakhsh Malekian 1
Aparna Das 1
Nadia Fawaz 1
Silvio Micali 1
Bem Roberts 1
Peter Key 1
Zhiyi Huang 1
Qiqi Yan 1
Berthold Vöcking 1
Nick Gravin 1
Alon Rosen 1
Maria Polukarov 1
Atsushi Iwasaki 1
Makoto Yokoo 1
Stefano Leonardi 1
Yu Zhang 1
Hadi Minooei 1
MohammadHossein Bateni 1
Aviad Rubinstein 1
Michal Feldman 1
Moshe Tennenholtz 1
Rakefet Rozen 1
Guido Schäfer 1
Georgios Piliouras 1
Rob Van Stee 1
Tomasz Michalak 1
Agata Chrobak 1
Kamesh Munagala 1
Bo Tang 1
Ruggiero Cavallo 1
Peter Troyan 1
Arunava Sen 1
Konstantinos Kollias 1
Siddharth Barman 1
Omer Tamuz 1
Dan Tsafrir 1
Arpita Ghosh 1
Ioannis Giotis 1
Scott Kominers 1
Carola Doerr 1
Talal Rahwan 1
Nitish Korula 1
Ioannis Caragiannis 1
Éva Tardos 1
Jason Hartline 1
Moran Feldman 1
Eric Friedman 1
Guido Proietti 1
Shaili Jain 1
Ingmar Weber 1
Jiehua Chen 1
Laurens Cherchye 1
Gleb Polevoy 1
Stanko Dimitrov 1
Mihaela Schaar 1
Daniel Reeves 1
David Sarne 1
Muli Ben-Yehuda 1
Yiling Chen 1
Iftah Gamzu 1
Deepayan Chakrabarti 1
Aravind Srinivasan 1
Stratis Ioannidis 1
Benjamin Doerr 1
Dinan Gunawardena 1
Salil Vadhan 1
Bach Ha 1
Jennifer Vaughan 1
Ozan Candogan 1
Felix Fischer 1
Shaddin Dughmi 1
Vincent Conitzer 1
Suguru Ueda 1
Robert Bredereck 1
Yakov Babichenko 1
David Pennock 1
Ercan Yildiz 1
Yishay Mansour 1
Erik Vee 1
Michael Schwarz 1
Bart Keijzer 1
Christos Tzamos 1
Michael Wooldridge 1
Nikhil Devanur 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
Mihaela Van Der Schaar 1
Gerhard Woeginger 1
Jaeok Park 1
Stefan Eilts 1
Bart Smeulders 1
Bram De Rock 1
Chaitanya Swamy 1
Yuanzhang Xiao 1
Swaprava Nath 1
Shai Vardi 1
Elchanan Mossel 1
Anna Scaglione 1
Victor Shnayder 1
Pranav Dandekar 1
Matthew Cary 1
Kurtis Heimerl 1
Pablo Azar 1
Poan Chen 1
Weidong Ma 1
Simina Brânzei 1
Stephen Chong 1
Jon Kleinberg 1
Pablo Parrilo 1
Aleksandrs Slivkins 1
Noam Livne 1
Susanne Albers 1
Frits Spieksma 1
Amin Saberi 1
Mike Ruberry 1
Sam Ganzfried 1
Saeed Alaei 1
David Kempe 1
Sara Krehbiel 1
Jinwoo Shin 1
Xujin Chen 1
Kshipra Bhawalkar 1
Tal Moran 1
Paul Goldberg 1
Jacob Abernethy 1
George Pierrakos 1
Annamária Kovács 1
Alkmini Sgouritsa 1
Pichayut Jirapinyo 1
Ioannis Caragiannis 1
Joeseph Halpern 1
Riccardo Colini-Baldeschi 1
Noga Alon 1
Eyal Even-Dar 1
Liam Roditty 1
Emmanouil Zampetakis 1
Morteza Zadimoghaddam 1
Rahul Sami 1
Avrim Blum 1
Renato PaesLeme 1
Christopher Wilkens 1
Daniel Goldstein 1
Mohammad Mahdian 1
Benjamin Edelman 1
Claire Mathieu 1
Xiaodong Hu 1
Piotr Szczepański 1
Inbal Talgam-Cohen 1
Rahul Savani 1
Cam Nguyen 1
Elias Koutsoupias 1
John Lai 1
Benjamin Lubin 1
Angelo Fanelli 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 Oxford 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
Weizmann Institute of Science Israel 2
Yahoo Research Labs 2
University of Warsaw 2
Microsoft Research Cambridge 2
National Technical University of Athens 2
London School of Economics and Political Science 2
University of Roma La Sapienza 2
California Institute of Technology 2
University of Pennsylvania 2
University of Patras 2
University of Southern California 2
Duke University 2
Microsoft 2
Kyushu University 2
Indian Statistical Institute (Delhi Centre) 2
University of Waterloo 3
Chinese Academy of Sciences 3
Catholic University of Leuven 3
University of Maryland 3
University of Washington 4
Technical University of Berlin 4
Georgia Institute of Technology 4
University of Southampton 4
University of California, Los Angeles 5
University of Vienna 5
Tel Aviv University 5
Northwestern University 5
Max Planck Institute for Informatics 7
University of California, Berkeley 8
University of Liverpool 8
Technion - Israel Institute of Technology 8
Bar-Ilan University 8
Google Inc. 8
Massachusetts Institute of Technology 10
Carnegie Mellon University 10
Stanford University 12
Cornell University 12
Harvard University 13
Microsoft Research 21

ACM Transactions on Economics and Computation (TEAC) - Special Issue on EC'14 Archive

 
All ACM Journals | See Full Journal Index