Fetching the paper…
Reading the bibliography…
We conjecture that PPAD has a PCP-like complete problem, seeking a near equilibrium in which all but very few players have very little incentive to deviate.
Variabilità e mutabilità
Corrado Gini · 1912
Earlier work this paper cites.
Resource Allocation and the Public Sector
D.K. Foley · 1967
Earlier work this paper cites.
Equity, envy, and efficiency
H. Varian · 1974
Earlier work this paper cites.
Theories of justice based on symmetry
W. Thomson and H.R. Varian · 1985
Earlier work this paper cites.
Exponential lower bounds for finding brouwer fix points
Michael D. Hirsch, Christos H. Papadimitriou, and Stephen A. Vavasis · 1989
Earlier work this paper cites.
On sparse approximations to randomized strategies and convex combinations
Ingo Althöfer · 1994
Earlier work this paper cites.
Proof verification and the hardness of approximation problems
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy · 1998
Earlier work this paper cites.
Probabilistic checking of proofs: A new characterization of NP
Sanjeev Arora and Shmuel Safra · 1998
Earlier work this paper cites.
The relative complexity of NP search problems
Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi · 1998
Earlier work this paper cites.
On the complexity of k-sat
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
Playing large games using simple strategies
Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta · 2003
Cited alongside, same era.
Robust pcps of proximity, shorter pcps, and applications to coding
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan · 2006
Cited alongside, same era.
Robust locally testable codes and products of codes
Eli Ben-Sasson and Madhu Sudan · 2006
Cited alongside, same era.
The PCP theorem by gap amplification
Irit Dinur · 2007
Cited alongside, same era.
Approximate nash equilibria for multi-player games
Sébastien Hémon, Michel de Rougemont, and Miklos Santha · 2008
Cited alongside, same era.
An optimization approach for approximate nash equilibria
Haralampos Tsaknakis and Paul G. Spirakis · 2008
Cited alongside, same era.
Sub-constant error probabilistically checkable proof of almost-linear size
Dana Moshkovitz and Ran Raz · 2010
Later among the works it cites.
The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes
Eric Budish · 2011
Later among the works it cites.
Measuring inequality
Frank Cowell · 2011
Later among the works it cites.
On the complexity of approximating a nash equilibrium
Constantinos Daskalakis · 2013
Later among the works it cites.
Am with multiple merlins
Scott Aaronson, Russell Impagliazzo, and Dana Moshkovitz · 2014
Later among the works it cites.
Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation
Eric Budish, Gerard P. Cachon, Judd Kessler, and Abraham Othman · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Settling the complexity of computing two-player nash equilibria
Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2009
Cited alongside, same era.
The complexity of computing a nash equilibrium
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou · 2009
Cited alongside, same era.
On oblivious ptas’s for nash equilibrium
Constantinos Daskalakis and Christos H. Papadimitriou · 2009
Cited alongside, same era.
ETH Hardness for Densest- k k -Subgraph with Perfect Completeness
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, and Omri Weinstein
Cited in the paper.
Approximating the best nash equilibrium in n o {}^{\mbox{o}} (log n ) -time breaks the exponential time hypothesis
Mark Braverman, Young Kun-Ko, and Omri Weinstein · 2015
Closest in time.
The complexity of fairness through equilibrium
Abraham Othman, Christos H. Papadimitriou, and Aviad Rubinstein · 2016
Closest in time.
Inapproximability of nash equilibrium
Aviad Rubinstein · 2018
Closest in time.