Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2015
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914022724468736 |
|---|---|
| author | Babichenko, Yakov Papadimitriou, Christos Rubinstein, Aviad |
| author_facet | Babichenko, Yakov Papadimitriou, Christos Rubinstein, Aviad |
| contents | 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 implication, proved via a "birthday repetition" reduction, is that the n^O(log n) approximation scheme of [LMM03] for the Nash equilibrium of two-player games is essentially optimum. Two other open problems in the area are resolved once one assumes this conjecture, establishing that certain approximate equilibria are PPAD-complete: Finding a relative approximation of two-player Nash equilibria (without the well-supported restriction of [Das13]), and an approximate competitive equilibrium with equal incomes [Bud11] with small clearing error and near-optimal Gini coefficient. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1504_02411 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash Babichenko, Yakov Papadimitriou, Christos Rubinstein, Aviad Computational Complexity Computer Science and Game Theory 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 implication, proved via a "birthday repetition" reduction, is that the n^O(log n) approximation scheme of [LMM03] for the Nash equilibrium of two-player games is essentially optimum. Two other open problems in the area are resolved once one assumes this conjecture, establishing that certain approximate equilibria are PPAD-complete: Finding a relative approximation of two-player Nash equilibria (without the well-supported restriction of [Das13]), and an approximate competitive equilibrium with equal incomes [Bud11] with small clearing error and near-optimal Gini coefficient. |
| title | Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash |
| topic | Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/1504.02411 |