ACM DL

ACM Transactions on

Economics and Computation (TEAC)

Menu
Latest Articles

Truthful Mechanisms for Agents That Value Privacy

Recent work has constructed economic mechanisms that are both truthful and differentially private. In these mechanisms, privacy is treated separately... (more)

Whole-Page Optimization and Submodular Welfare Maximization with Online Bidders

In the context of online ad serving, display ads may appear on different types of webpages, where each page includes several ad slots and therefore... (more)

When Do Noisy Votes Reveal the Truth?

A well-studied approach to the design of voting rules views them as maximum likelihood estimators; given votes that are seen as noisy estimates of a true ranking of the alternatives, the rule must reconstruct the most likely true ranking. We argue that this is too stringent a requirement and instead ask: how many votes does a voting rule need to... (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

Introduction (Special Issue 4:3)

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.

Optimal and Robust Mechanism Design with Interdependent Values

We study interdependent value settings [Milgrom and Weber 1982] and extend several results from the well-studied independent private values model to these settings. For revenue-optimal mechanism design, we give conditions under which Myerson's virtual value-based mechanism remains optimal with interdependent values. One of these conditions is robustness of the truthfulness and individual rationality guarantees, in the sense that they are required to hold ex post. We then consider an even more robust class of mechanisms called ``prior independent'' (a.k.a. ``detail free''), and show that by simply using one of the bidders to set a reserve price, it is possible to extract near-optimal revenue in an interdependent values setting. This shows that a considerable level of robustness is achievable for interdependent values in single-parameter environments.

Ranking and Tradeoffs in Sponsored Search Auctions

In a sponsored search auction, decisions about how to rank ads impose tradeoffs between objectives such as revenue and welfare. In this paper, we examine how these tradeoffs should be made. We begin by arguing that the most natural solution concept to evaluate these tradeoffs is the lowest symmetric Nash equilibrium (SNE). As part of this argument, we generalise the well known connection between the lowest SNE and the VCG outcome. We then propose a new ranking algorithm, loosely based on the revenue-optimal auction, that uses a reserve price to order the ads (not just to filter them) and give conditions under which it raises more revenue than simply applying that reserve price. Finally, we conduct extensive simulations examining the tradeoffs enabled by different ranking algorithms and show that our proposed algorithm enables superior operating points by a variety of metrics.

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.

Optimal Contests 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 optimal {\em design} of mechanisms in these environments? In this paper, we explore this question in the context of optimal contest design for {\em simple} agents---agents who strategically reason about whether or not to participate in a system, but not about the input they provide to it. Specifically, consider a contest where $n$ potential contestants with types $(q_i,c_i)$ each choose between participating and producing a submission of quality $q_i$ at cost $c_i$, versus not participating at all, to maximize their utilities. How should a principal distribute a total prize $V$ amongst the $n$ ranks to maximize some increasing function of the qualities of elicited submissions in a contest with such simple agents? We first solve the optimal contest design problem for settings where agents have homogenous participation costs $c_i = c$. Here, the contest that maximizes every increasing function of the elicited contributions is always a {\em simple} contest, awarding equal prizes of $V/j^*$ each to the top $j^* =V/c - \Theta(\sqrt{V/(c\ln(V/c))})$ contestants. This is in contrast with the optimal contest structure in comparable models with strategic effort choices, where the optimal contest is either a winner-take-all contest or awards possibly unequal prizes, depending on the curvature of agents' effort cost functions. We next address the general case with heterogenous costs where agents' types $(q_i,c_i)$ are inherently two-dimensional, significantly complicating equilibrium analysis. With heterogenous costs, the optimal contest depends on the objective being maximized: our main result here is that the winner-take-all contest is a 3-approximation of the optimal contest when the principal's objective is to maximize the quality of the best elicited contribution. The proof of this result hinges around a `sub-equilibrium' lemma establishing a stochastic dominance relation between the distribution of qualities elicited in an equilibrium and a {\em sub-equilibrium}---a strategy profile that is a best response for all agents who choose to {\em participate} in that strategy profile; this relation between equilibria and sub-equilibria may be of more general interest.

Incentives, gamification, and game theory: An economic approach to badge design

Gamification is growing increasingly prevalent as a means to incentivize user engagement of social media sites that rely on user contributions. {\em Badges}, or equivalent rewards such as top-contributor lists that are used to recognize a user's contributions on a site, clearly appear to be valued by users who actively pursue and compete for them.
However, different sites use different badge {\em designs}, varying how, and for what, badges are awarded--- some sites such as StackOverflow award badges for meeting fixed levels of contribution, while others such as Amazon and Y! Answers reward users for being amongst some top set of contributors on the site, corresponding to a competitive standard of performance. Given that users value badges, and that contributing to a site requires effort, how badges are designed will affect the incentives--- and therefore the participation and effort--- elicited from strategic users on a site.

We take a game-theoretic approach to badge design, analyzing the incentives created by widely-used badge designs in a model where winning a badge is valued and effort is costly, and potential contributors to the site endogenously decide whether or not to participate, and how much total effort to put into their contributions to the site. We analyze equilibrium existence, and equilibrium participation and effort in an absolute standards mechanism $\Ma$ where badges are awarded for meeting some {\em absolute} level of (observed) effort, and a {\em relative} standards mechanism $\Mr$ corresponding to competitive standards as in a top-$\rs$ contributor badge. We find that equilibria always exist in both mechanisms, even when the value from winning a badge depends endogenously on the number of other winners. However, $\Ma$ has zero-participation equilibria for standards that are too high, whereas all equilibria in $\Mr$ elicit non-zero participation for all possible $\rho$, {\em provided} $\rho$ is specified as a fixed number rather than as a fraction of actual contributors (note that the two are not equivalent in a setting with endogenous participation).
Finally, we ask whether or not a site should explicitly announce the number of users winning a badge; the answer to this question is determined by the curvature of the value of winning the badge as a function of the number of other winners.

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 78
Citation Count 77
Available for Download 78
Downloads (6 weeks) 714
Downloads (12 Months) 4508
Downloads (cumulative) 11768
Average downloads per article 151
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 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 4
Randolph McAfee 4
Martin Hoefer 3
Ian Kash 3
Monika Henzinger 3
Moshe Tennenholtz 3
Paul Dütting 3
Ariel Procaccia 3
David Parkes 3
Yonatan Aumann 2
Rann Smorodinsky 2
Asuman Ozdaglar 2
Anna Karlin 2
Maria Balcan 2
Yiling Chen 2
Balasubramanian Sivan 2
George Christodoulou 2
Thomas Keßelheim 2
Martin Starnberger 2
Sergei Vassilvitskii 2
Dimitris Fotakis 2
Robert Kleinberg 2
Nicole Immorlica 2
Vahab Mirrokni 2
Tüomas Sandholm 2
Moshe Babaioff 2
Yair Dombb 2
Nisarg Shah 2
Nima Haghpanah 2
Alexander Skopalik 2
Nicholas Jennings 2
Martin Gairing 2
Nikhil Devanur 1
Vincent Conitzer 1
Suguru Ueda 1
Robert Bredereck 1
Yuval Peres 1
Lawrence Blume 1
Yishay Mansour 1
Abraham Othman 1
David Pennock 1
Ercan Yildiz 1
Okke Schrijvers 1
Michael Schwarz 1
Bart Keijzer 1
Christos Tzamos 1
Michael Wooldridge 1
Yakov Babichenko 1
Erik Vee 1
Mohammad Mahdian 1
Ronen Gradwohl 1
Victor Naroditskiy 1
Daniel Fragiadakis 1
Avinatan Hassidim 1
Stefan Kratsch 1
Gerhard Woeginger 1
Jaeok Park 1
Mihaela Van Der Schaar 1
Stefan Eilts 1
Bram De Rock 1
Bart Smeulders 1
Pablo Parrilo 1
Jon Kleinberg 1
Anna Scaglione 1
Christos, Papadimitriou 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
Chaitanya Swamy 1
Yuanzhang Xiao 1
Swaprava Nath 1
Aleksandrs Slivkins 1
Tal Moran 1
Noam Livne 1
Yishay Mansour 1
Susanne Albers 1
Frits Spieksma 1
George Pierrakos 1
Jacob Abernethy 1
David Easley 1
Amin Saberi 1
Annamária Kovács 1
Alkmini Sgouritsa 1
Mike Ruberry 1
Paul Goldberg 1
Xujin Chen 1
Saeed Alaei 1
David Kempe 1
Sara Krehbiel 1
Jinwoo Shin 1
Kshipra Bhawalkar 1
Pichayut Jirapinyo 1
Sam Ganzfried 1
Ioannis Caragiannis 1
Stephen Chong 1
Joeseph Halpern 1
Riccardo Colini-Baldeschi 1
Noga Alon 1
Eyal Even-Dar 1
Liam Roditty 1
Cam Nguyen 1
Elias Koutsoupias 1
Avrim Blum 1
Rahul Savani 1
Renato PaesLeme 1
Xiaodong Hu 1
Benjamin Edelman 1
Claire Mathieu 1
Piotr Szczepański 1
Emmanouil Zampetakis 1
Morteza Zadimoghaddam 1
Rahul Sami 1
John Lai 1
Benjamin Lubin 1
Christopher Wilkens 1
Daniel Goldstein 1
Mohammad Mahdian 1
Angelo Fanelli 1
Zhiyi Huang 1
Qiqi Yan 1
Davide Bilò 1
Luciano Gualà 1
Rolf Niedermeier 1
Orna Agmon Ben-Yehuda 1
Assaf Schuster 1
Daron Acemoğlu 1
Berthold Vöcking 1
Yuval Emek 1
Azarakhsh Malekian 1
Nadia Fawaz 1
Aparna Das 1
Silvio Micali 1
Marina Epelman 1
Siddharth Suri 1
Nick Gravin 1
Alon Rosen 1
Maria Polukarov 1
Atsushi Iwasaki 1
Makoto Yokoo 1
Stefano Leonardi 1
Yu Zhang 1
Kamesh Munagala 1
Bo Tang 1
Michal Feldman 1
Moshe Tennenholtz 1
Rakefet Rozen 1
Guido Schäfer 1
Georgios Piliouras 1
Tomasz Michalak 1
Agata Chrobak 1
Hadi Minooei 1
MohammadHossein Bateni 1
Rob Van Stee 1
Nitish Korula 1
Ioannis Caragiannis 1
Ruggiero Cavallo 1
Peter Troyan 1
Éva Tardos 1
Jason Hartline 1
Dan Tsafrir 1
Moran Feldman 1
Omer Tamuz 1
Carola Doerr 1
Ioannis Giotis 1
Scott Kominers 1
Talal Rahwan 1
Arunava Sen 1
Konstantinos Kollias 1
Siddharth Barman 1
Arpita Ghosh 1
Salil Vadhan 1
Eric Friedman 1
Guido Proietti 1
Shaili Jain 1
Ingmar Weber 1
Jiehua Chen 1
Gleb Polevoy 1
Laurens Cherchye 1
Ozan Candogan 1
Jennifer Vaughan 1
Bach Ha 1
Muli Ben-Yehuda 1
Daniel Reeves 1
David Sarne 1
Yiling Chen 1
Iftah Gamzu 1
Benjamin Doerr 1
Aravind Srinivasan 1
Stratis Ioannidis 1
Stanko Dimitrov 1
Mihaela Schaar 1
Shaddin Dughmi 1
Felix Fischer 1
Deepayan Chakrabarti 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
University of Pennsylvania 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
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
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
Tel Aviv University 3
Catholic University of Leuven 3
University of Waterloo 3
University of Maryland 3
Chinese Academy of Sciences 3
University of Southampton 4
Georgia Institute of Technology 4
University of Washington 4
Technical University of Berlin 4
Northwestern University 5
University of California, Los Angeles 5
University of Vienna 5
University of California, Berkeley 6
Bar-Ilan University 7
Max Planck Institute for Informatics 7
University of Liverpool 8
Technion - Israel Institute of Technology 8
Google Inc. 8
Cornell University 8
Stanford University 10
Massachusetts Institute of Technology 10
Carnegie Mellon University 10
Harvard University 13
Microsoft Research 17
 
All ACM Journals | See Full Journal Index