ACM DL

ACM Transactions on

Economics and Computation (TEAC)

Menu
Latest Articles

Fast Convergence in the Double Oral Auction

Impartial Selection and the Power of Up to Two Choices

Sequential Posted-Price Mechanisms with Correlated Valuations

The VCG Mechanism for Bayesian Scheduling

Computation of Stackelberg Equilibria of Finite Sequential Games

NEWS

New Editors-In-Chief

David Pennock and Ilya Segal took over as co-editors-in-chief in March 2017.


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
Pricing Equilibria and Graphical Valuations

We study pricing equilibria for graphical valuations, which is a class of valuations that admit a compact representation. These valuations are associated with a value graph, whose nodes correspond to items, and edges encode (pairwise) complementarities/substitutabilities between items. It is known that for graphical valuations a Walrasian equilibrium (a pricing equilibrium that relies on anonymous item prices) does not exist in general. On the other hand, a pricing equilibrium exists when the seller uses an agent-specific graphical pricing rule that involves prices for each item and markups/discounts for pairs of items. We study the existence of pricing equilibria with simpler pricing rules which either (i) require anonymity (so that prices are identical for all agents) while allowing for pairwise markups/discounts, or (ii) involve offering prices only for items. We show that a pricing equilibrium with the latter pricing rule exists if and only if a Walrasian equilibrium exists, whereas the former pricing rule may guarantee the existence of a pricing equilibrium even for graphical valuations that do not admit a Walrasian equilibrium. Interestingly, by exploiting a novel connection between the existence of a pricing equilibrium and the partitioning polytope associated with the underlying graph, we also establish that for simple (series-parallel) value graphs a pricing equilibrium with anonymous graphical pricing rule exists if and only if a Walrasian equilibrium exists. These equivalence results imply that simpler pricing rules (i) and (ii) do not guarantee the existence of a pricing equilibrium for all graphical valuations.

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

As a result of a series of important works, the complexity of 2-player Nash equilibrium is by now well understood, even when equilibria with special properties are desired and when the game is symmetric. However, for multi-player games, when equilibria with special properties are desired, the only result known is due to Schaefer and Stefankovic: that checking whether a 3-player Nash Equilibrium (3-Nash) instance has an equilibrium in a ball of radius half in l_{infty}-norm is ETR-complete, where ETR is the class Existential Theory of Reals.

Building on their work, we show that the following decision versions of 3-Nash are also ETR-complete: checking
whether (i) there are two or more equilibria, (ii) there exists an equilibrium in which each player gets at least h
payoff, where h is a rational number, (iii) a given set of strategies are played with non-zero probability, and
(iv) all the played strategies belong to a given set.

Next, we give a reduction from 3-Nash to symmetric 3-Nash, hence resolving an open problem of Papadimitriou (2011). This yields ETR-completeness for symmetric 3-Nash for the last two problems stated above as well as completeness for the class FIXP_a, a variant of FIXP for strong approximation. All our results extend to k-Nash, for any constant k >= 3.


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

Affiliation Paper Counts
Universite Libre de Bruxelles 1
Ecole Normale Superieure 1
University of Illinois at Urbana-Champaign 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
Le Moyne College 1
National Chiao Tung University Taiwan 1
The Interdisciplinary Center Herzliya 1
Czech Technical University in Prague 1
University of California, Davis 1
University of Augsburg 1
RWTH Aachen University 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
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 Paderborn 2
Microsoft Research Cambridge 2
Indian Statistical Institute (Delhi Centre) 2
Yahoo Research Labs 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
Weizmann Institute of Science Israel 2
University of Toronto 2
University of Texas at Austin 2
Center for Mathematics and Computer Science - Amsterdam 2
Kyushu University 2
Duke University 2
National Technical University of Athens 2
Catholic University of Leuven, Leuven 3
Rensselaer Polytechnic Institute 3
University of Aarhus 3
University of Waterloo 3
Humboldt University of Berlin 3
Hebrew University of Jerusalem 3
Microsoft Corporation 3
Chinese Academy of Sciences 3
London School of Economics and Political Science 3
Technical University of Munich 3
University of Warsaw 3
University of Maryland 3
University of Roma La Sapienza 3
University of Southern California 3
Khalifa University 4
Georgia Institute of Technology 4
University of Washington, Seattle 4
University of Southampton 4
University of Oxford 4
Northwestern University 5
University of California, Los Angeles 5
Technical University of Berlin 5
University of Vienna 5
Max Planck Institute for Informatics 7
University of California, Berkeley 8
Technion - Israel Institute of Technology 8
Massachusetts Institute of Technology 8
Tel Aviv University 9
Google Inc. 9
University of Pennsylvania 9
Carnegie Mellon University 10
Bar-Ilan University 11
University of Liverpool 11
Stanford University 12
Cornell University 12
Harvard University 16
Microsoft Research 25
 
All ACM Journals | See Full Journal Index

Search TEAC
enter search term and/or author name