Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
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. We show that, if one assumes that this problem requires exponential time, several open problems in this area are settled. The most important im...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
2015
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1504.02411 http://arxiv.org/abs/1504.02411 |
| Tags: |
No Tags, Be the first to tag this record!
|