計算量クラスTFNPに対する不動点定理およびアルゴリズム的ゲーム理論からのアプローチ

[Aar13] Scott Aaronson. Quantum Computing since Democritus. Cambridge Uni-versity Press, 2013. ISBN: 978-0-521-19956-8. DOI: 10.1017/CBO9780511979309.

[AB09] Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. ISBN: 978-0-521-42426- 4.

[ABB20] James Aisenberg, Maria Luisa Bonet, and Sam Buss. “2-D Tucker is PPA complete.” In: Journal of Computer and System Sciences 108 (2020), pp. 92–103. DOI: 10.1016/j.jcss.2019.09.002.

[AF03] Ron Aharoni and Tamás Fleiner. “On a lemma of Scarf.” In: Journal of Combinatorial Theory, Series B 87.1 (2003), pp. 72–80. DOI: 10.1016/ S0095-8956(02)00028-X.

[AKV05] Timothy G. Abbott, Daniel M. Kane, and Paul Valiant. “On the Com- plexity of Two-PlayerWin-Lose Games.” In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 2005, pp. 113–122. DOI: 10.1109/SFCS.2005.59.

[AOV07] Louigi Addario-Berry, Neil Olver, and Adrian Vetta. “A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games.” In: Journal of Graph Algorithms and Applications 11.1 (2007), pp. 309–319. DOI: 10.7155/jgaa.00147.

[Apt+17] Krzysztof R. Apt, Bart de Keijzer, Mona Rahn, Guido Schäfer, and Sunil Simon. “Coordination games on graphs”. In: International Journal of Game Thoery 46.3 (2017), pp. 851–877. DOI: 10.1007/s00182-016-0560-8.

[Ban+19] Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, and Aviad Rubinstein. “Reductions in PPP.” In: Information Processing Letters 145 (2019), pp. 48–52. DOI: 10.1016/j.ipl.2018.12.009.

[Ban22] S. Banach. “Sur les operations dans les ensembles abstraits et leur ap- plication aux equations integrales.” In: Fundamenta Mathematicae 3 (1922), pp. 133–181. DOI: 10.4064/fm-3-1-133-181.

[BF16] Péter Biró and Tamás Fleiner. “Fractional solutions for capacitated NTU- games, with applications to stable matchings.” In: Discrete Optimization 22 (2016), pp. 241–254. DOI: 10.1016/j.disopt.2015.02.002.

[BFI16] Péter Biró, Tamás Fleiner, and Robert W. Irving. “Matching couples with Scarf’s algorithm.” In: Annals of Mathematics and Artificial Intelligence 77.3-4 (2016), pp. 303–316. DOI: 10.1007/s10472-015-9491-5.

[BIL08] Vincenzo Bonifaci, Ugo Di Iorio, and Luigi Laura. “The complexity of uniform Nash equilibria and related regular subgraph problems.” In: Theoretical Computer Science 401.1-3 (2008), pp. 144–152. DOI: 10. 1016/j.tcs.2008.03.036.

[BK13] Péter Biró and Flip Klijn. “Matching with couples: a Multidisciplinary Survey.” In: International Game Theory Review 15.2 (2013). DOI: 10. 1142/S0219198913400082.

[BM21] Vittorio Bilò and Marios Mavronicolas. “The Complexity of Computa- tional Problems About Nash Equilibria in Symmetric Win-Lose Games.” In: Algorithmica 83.2 (2021), pp. 447–530. DOI: 10.1007/s00453- 020-00763-x.

[Bor16] Michaela Borzechowski. The complexity class Polynomial Local Search (PLS) and PLS-complete problems. 2016.

[BR21] Yakov Babichenko and Aviad Rubinstein. “Settling the complexity of Nash equilibrium in congestion games”. In: Proceedings of the 53rd An- nual ACM SIGACT Symposium on Theory of Computing, STOC. ACM, 2021, pp. 1426–1437. DOI: 10.1145/3406325.3451039.

[Bro11] L. E. J. Brouwer. “Über Abbildung von Mannigfaltigkeiten.” In: Math- ematische Annalen 71.1 (1911), pp. 97 –115. ISSN: 0025-5831. DOI: 10.1007/bf01456931.

[Brø74] Arne Brøndsted. “On a lemma of Bishop and Phelps.” In: Pacific Journal of Mathematics 55.2 (1974), pp. 335–341. DOI: 10.2140/pjm.1974.55.335.

[Cai+16] Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Pa- padimitriou. “Zero-Sum Polymatrix Games: A Generalization of Mmin- max.” In: Mathematics of Operations Research 41.2 (2016), pp. 648– 655. DOI: 10.1287/moor.2015.0745.

[Car76] J. Caristi. “Fixed point theorems for mapping satisfying inwardness con- ditions.” In: Transactions of the American Mathematical Society 215 (1976), pp. 241 –251. DOI: 10.1090/S0002-9947-1976-0394329-4.

[CD06] Xi Chen and Xiaotie Deng. “Settling the Complexity of Two-Player Nash Equilibrium.” In: Proceedings of the 47th Annual IEEE Sympo- sium on Foundations of Computer Science. IEEE Computer Society, 2006, pp. 261–272. DOI: 10.1109/FOCS.2006.69.

[CD07] Xi Chen and Xiaotie Deng. “Recent development in computational com- plexity characterization of Nash equilibrium.” In: Computer Science Re- view 1.2 (2007), pp. 88–99. DOI: 10.1016/j.cosrev.2007.09.002.

[CD09] Xi Chen and Xiaotie Deng. “On the complexity of 2D discrete fixed point problem.” In: Theoretical Computer Science 410.44 (2009), pp. 4448 –4456. ISSN: 0304-3975. DOI: 10.1016/j.tcs.2009.07.052.

[CD11] Yang Cai and Constantinos Daskalakis. “On Minmax Theorems for Mul- tiplayer Games.” In: Proceedings of the 22nd Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA. 2011, pp. 217–234. DOI: 10 . 1137/1.9781611973082.20.

[CDO15] Xi Chen, David Durfee, and Anthi Orfanou. “On the complexity of nash equilibria in anonymous games”. In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015, pp. 381–390. DOI: 10.1145/2746539.2746571.

[CDT09] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. “Settling the Complex- ity of Computing Two-Player Nash Equilibria.” In: Journal of the ACM 56.3 (2009), 14:1 –14:57. ISSN: 00045411. DOI: 10.1145/1516512. 1516516.

[Che+09] Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng. “Settling the Com- plexity of Arrow-Debreu Equilibria in Markets with Additively Sepa- rable Utilities.” In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, 2009, pp. 273–282. DOI: 10.1109/FOCS.2009.29.

[CKO18] Flavio Chierichetti, Jon Kleinberg, and Sigal Oren. “On discrete prefer- ences and coordination.” In: Journal of Computer and System Sciences 93 (2018), pp. 11–29. DOI: 10.1016/j.jcss.2017.11.002.

[CL10] Ching-Lueh Chang and Yuh-Dauh Lyuu. “Optimal bounds on finding fixed points of contraction mappings.” In: Theoretical Computer Science 411.16 (2010), pp. 1742 –1749. ISSN: 0304-3975. DOI: 10.1016/j. tcs.2010.01.016.

[CL22] Xi Chen and Yuhao Li. “Improved Upper Bounds for Finding Tarski Fixed Points.” In: CoRR abs/2202.05913 (2022). DOI: 10.48550/arXiv. 2202.05913. arXiv: 2202.05913.

[Con92] Anne Condon. “The complexity of stochastic games.” In: Information and Computation 96.2 (1992), pp. 203–224. DOI: 10 . 1016 / 0890 - 5401(92)90048-K.

[Coo71] Stephen A. Cook. “The Complexity of Theorem-Proving Procedures.” In: Proceedings of the 3rd Annual ACM Symposium on Theory of Com- puting. ACM, 1971, pp. 151–158. DOI: 10.1145/800157.805047.

[CS05] Bruno Codenotti and Daniel Stefankovic. “On the computational com- plexity of Nash equilibria for (0, 1) bimatrix games.” In: Information Processing Letters 94.3 (2005), pp. 145–150. DOI: 10.1016/j.ipl.2005.01.010.

[Csá21] Gergely Csáji. On the complexity of Stable Hypergraph Matching, Stable Multicommodity Flow and related problems. 2021.

[Das09] Constantinos Daskalakis. “Nash equilibria: Complexity, symmetries, and approximation.” In: Computer Science Review 3.2 (2009), pp. 87–100. DOI: 10.1016/j.cosrev.2009.03.003.

[Del+21] Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. “Computing exact solutions of consensus halving and the Borsuk-Ulam theorem.” In: Journal of Computer and System Sciences 117 (2021), pp. 75–98. DOI: 10.1016/j.jcss.2020.10.006.

[Den+21] Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu. “Understanding PPA-completeness.” In: Journal of Com- puter and System Sciences 115 (2021), pp. 146–168. DOI: 10.1016/j. jcss.2020.07.006.

[DFK17] Xiaotie Deng, Zhe Feng, and Rucha Kulkarni. “Octahedral Tucker is PPA-complete.” In: Electronic Coloquim on Computational Complexity TR17-118 (2017). URL: https://eccc.weizmann.ac.il/report/ 2017/118.

[DFS20] Argyrios Deligkas, John Fearnley, and Rahul Savani. “Tree Polymatrix Games Are PPAD-Hard.” In: Proceedings of the 47th International Col- loquium on Automata, Languages, and Programming, ICALP. Vol. 168. LIPIcs. 2020, 38:1–38:14. DOI: 10.4230/LIPIcs.ICALP.2020.38.

[DGP09] Constantinos. Daskalakis, Paul W. Goldberg, and Christos H. Papadim- itriou. “The Complexity of Computing a Nash Equilibrium.” In: SIAM Journal on Computing 39.1 (2009), pp. 195–259. DOI: 10.1137/070699652.

[DK11] Samir Datta and Nagarajan Krishnamurthy. “Some Tractable Win-Lose Games.” In: Proceedings of the 8th International Conference on The- ory and Applications of Models of Computation, TAMC. Vol. 6648. Lec- ture Notes in Computer Science. Springer, 2011, pp. 365–376. DOI: 10. 1007/978-3-642-20877-5_36.

[Doh+17] Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiˇrí Matoušek, and Emo Welzl. “ARRIVAL: a zero-player graph game in NP ∩ coNP.” In: A jour- ney through discrete mathematics. Springer, 2017, pp. 367–374. DOI: 10.1007/978-3-319-44479-6_14.

[DP06] Constantinos Daskalakis and Christos H. Papadimitriou. “Computing pure nash equilibria in graphical games via markov random fields.” In: Proceedings of the 7th ACM Conference on Electronic Commerce (EC- 2006). ACM, 2006, pp. 91–99. DOI: 10.1145/1134707.1134718.

[DP11] Constantinos Daskalakis and Christos Papadimitriou. “Continuous Lo- cal Ssearch.” In: Proceedings of the 22nd annual ACM-SIAM Sympo- sium on Discrete algorithms. 2011, pp. 790–804. DOI: 10 .1137 / 1 . 9781611973082.62.

[DP20] Constantinos Daskalakis and Christos H. Papadimitriou. Continuous Lo- cal Search - Corrigendum. 2020. URL:http://people.csail.mit. edu/costis/CLS-corrigendum.pdf.

[DQY11] Chuangyin Dang, Qi Qi, and Yinyu Ye. Computational models and com- plexities of Tarski’s fixed points. Tech. rep. 2011. URL: https://web. stanford.edu/~yyye/unitarski1.pdf.

[DTZ18] Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. “A converse to Banach’s fixed point theorem and its CLS-completeness.” In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018, pp. 44–50. DOI: 10.1145/3188745.3188968.

[EGG06] Edith Elkind, Leslie Ann Goldberg, and Paul Goldberg. “Nash Equilibria in Graphical Games on Trees Revisited.” In: Proceedings of the 7th ACM conference on Electronic Commerce, EC. 2006, pp. 100–109. DOI: 10. 1145/1134707.1134719.

[ET11] Robert Elsässer and Tobias Tscheuschner. “Settling the Complexity of Local Max-Cut (Almost) Completely.” In: Proceedings of the 38th An- nual International Colloquium on Automata, Languages, and Program- ming. Vol. 6755. 2011, pp. 171–182. DOI: 10 . 1007 / 978 - 3 - 642 - 22006-7_15.

[Ete+20] Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mi- halis Yannakakis. “Tarski’s Theorem, Supermodular Games, and the Com- plexity of Equilibria.” In: Proceedings of the 11th Innovations in The- oretical Computer Science Conference, ITCS. Vol. 151. LIPIcs. 2020, 18:1–18:19. ISBN: 978-3-95977-134-4. DOI: 10.4230/LIPIcs.ITCS. 2020.18.

[EY10] Kousha Etessami and Mihalis Yannakakis. “On the Complexity of Nash Equilibria and Other Fixed Points.” In: SIAM Journal on Computing 39.6 (2010), pp. 2531–2597. DOI: 10.1137/080720826.

[Fea+20] John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. “Unique end of potential line.” In: Journal of Computer and System Sciences 114 (2020), pp. 1–35. DOI: 10.1016/j.jcss.2020.05.007.

[Fea+21] John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Sa- vani. “The Complexity of Gradient Descent: CLS = PPAD ∩ PLS.” In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, 2021, 46–59. ISBN: 9781450380539. DOI: 10.1145/3406325.3451052.

[FGV16] Diodato Ferraioli, Paul W. Goldberg, and Carmine Ventre. “Decentral- ized dynamics for finite opinion games.” In: Theoretical Computer Sci- ence 648 (2016), pp. 96–115. ISSN: 0304-3975. DOI: 10.1016/j.tcs. 2016.08.011.

[FPS20] John Fearnley, Dömötör Pálvölgyi, and Rahul Savani. “A faster algo- rithm for finding Tarski fixed points.” In: CoRR abs/2010.02618 (2020). DOI: 10.48550/arXiv.2010.02618. arXiv: 2010.02618.

[FPT04] Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar. “The com- plexity of pure Nash equilibria.” In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing. 2004, pp. 604–612. DOI: 10.1145/1007352.1007445.

[FRG18] Aris Filos-Ratsikas and Paul W. Goldberg. “Consensus halving is PPA- complete.” In: Proceedings of the 50th Annual ACM SIGACT Sympo- sium on Theory of Computing. 2018, pp. 51–64. DOI: 10.1145/3188745. 3188880.

[FRG19] Aris Filos-Ratsikas and Paul W. Goldberg. “The Complexity of Split- ting Necklaces and Bisecting Ham Sandwiches.” In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019, pp. 638–649. DOI: 10.1145/3313276.3316334.

[FS21] John Fearnley and Rahul Savani. “A Faster Algorithm for Finding Tarski Fixed Points.” In: Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, STACS. Vol. 187. LIPIcs. 2021, 29:1–29:16. ISBN: 978-3-95977-180-1. DOI: 10.4230/LIPIcs.STACS. 2021.29.

[GD03] Andrzej Granas and James Dugundji. Fixed Point Theory. Springer, 2003. ISBN: 0387001735.

[GGS05] Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. “Pure Nash Equilibria: Hard and Easy Games.” In: Journal of Artificial Intelligence Research 24 (2005), pp. 347–406. DOI: 10.1613/jair.1683.

[GH19] Paul W. Goldberg and Alexandros Hollender. “The Hairy Ball Problem is PPAD-Complete.” In: Proceedings of the 46th International Collo- quium on Automata, Languages, and Programming. Vol. 132. LIPIcs. 2019, 65:1–65:14. DOI: 10.4230/LIPIcs.ICALP.2019.65.

[Göö+22] Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. “Further Collapses in TFNP.” In: CoRR abs/2202.07761 (2022). DOI: https://doi.org/10.48550/ arXiv.2202.07761. arXiv: 2202.07761.

[GS13] D. Gale and L. S. Shapley. “College Admissions and the Stability of Marriage.” In: The American Mathematical Monthly 120.5 (2013), pp. 386–391. DOI: 10.4169/amer.math.monthly.120.05.386.

[GZ11] Oded Goldreich and David Zuckerman. “Another Proof That BPP ⊆ PH(and More).” In: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Vol. 6650. Lec- ture Notes in Computer Science. Springer, 2011, pp. 40–53. DOI: 10. 1007/978-3-642-22670-0_6.

[HG18] Alexandros Hollender and Paul W. Goldberg. “The Complexity of Multi- source Variants of the End-of-Line Problem, and the Concise Multi- lated Chessboard.” In: Electronic Coloquim on Computational Com- plexity TR18-120 (2018). URL:https://eccc.weizmann.ac.il/ report/2018/120/.

[HV21] Pavel Hubácek and Jan Václavek. “On Search Complexity of Discrete Logarithm.” In: Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, MFCS. Ed. by Filippo Bonchi and Simon J. Puglisi. Vol. 202. LIPIcs. 2021, 60:1–60:16. DOI: 10.4230/LIPIcs.MFCS.2021.60.

[HY17] Pavel Hubácˇek and Eylon Yogev. “Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds.” In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. 2017, pp. 1352–1371. DOI: 10.1137/17M1118014.

[IK18] Takashi Ishizuka and Naoyuki Kamiyama. “On the Complexity of Sta- ble Fractional Hypergraph Matching.” In: Proceedings of the 29th In- ternational Symposium on Algorithms and Computation, ISAAC 2018. Vol. 123. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, 11:1–11:12. DOI: 10.4230/LIPIcs.ISAAC.2018.11.

[IK22a] Takashi Ishizuka and Naoyuki Kamiyama. NP-hardness of Computing Uniform Nash Equilibria on Planar Bimatrix Game. 2022. DOI: 10 . 48550/ARXIV.2205.03117.

[IK22b] Takashi Ishizuka and Naoyuki Kamiyama. On Finding Pure Nash Equi- libria of Discrete Preference Games and Network Coordination Games. 2022. DOI: 10.48550/arXiv.2207.01523.

[Ish21a] Takashi Ishizuka. “On the complexity of finding a Caristi’s fixed point.” In: Information Processing Letters 170 (2021), p. 106119. DOI: 10 . 1016/j.ipl.2021.106119.

[Ish21b] Takashi Ishizuka. “The complexity of the parity argument with poten- tial.” In: Journal of Computer and System Sciences 120 (2021), pp. 14–41. DOI: 10.1016/j.jcss.2021.03.004.

[Jeˇr16] Emil Jeˇrábek. “Integer factoring and modular square roots.” In: Journal of Computer and System Sciences 82.2 (2016), pp. 380–394. DOI: 10. 1016/j.jcss.2015.08.001.

[JPY88] David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. “How Easy is Local Search?” In: Journal of Computer and System Sci- ences 37.1 (1988), pp. 79–100. DOI: 10.1016/0022-0000(88)90046-3.

[Kha80] Leonid G Khachiyan. “Polynomial algorithms in linear programming.” In: USSR Computational Mathematics and Mathematical Physics 20.1 (1980), pp. 53–72. DOI: 10.1016/0041-5553(80)90061-0.

[Kin+13] Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, and Shang-Hua Teng. “Reducibility among Fractional Stability Prob- lems.” In: SIAM Journal on Computing 42.6 (2013), pp. 2063–2113. DOI: 10.1137/120874655.

[Kle+21] Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H. Papadimitriou. “Total Functions in the Polynomial Hierarchy.” In: Pro- ceedings of the 12th Innovations in Theoretical Computer Science Con- ference, ITCS. Vol. 185. LIPIcs. 2021, 44:1–44:18. DOI: 10 . 4230 / LIPIcs.ITCS.2021.44.

[KLS01] Michael J. Kearns, Michael L. Littman, and Satinder P. Singh. “Graph- ical Models for Game Theory.” In: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, UAI. 2001, pp. 253–260.

[KNY19] Ilan Komargodski, Moni Naor, and Eylon Yogev. “White-Box vs. Black- Box Complexity of Search Problems: Ramsey and Graph Property Test- ing.” In: Journal of the ACM 66.5 (2019), 34:1–34:28. DOI: 10.1145/ 3341106.

[LCS16] Quang Duy Lã, Yong Huat Chew, and Boon-Hee Soong. Potential Game Theory. Springer, Cham, 2016. ISBN: 9783319809038.

[Lev73] Leonid A. Levin. “Universal sequential search problems.” In: Problems of Information Transmission 9.3 (1973), pp. 265–266.

[Lol+19] Phani Raj Lolakapuri, Umang Bhaskar, Ramasuri Narayanam, Gyana R. Parija, and Pankaj S. Dayama. “Computational Aspects of Equilibria in Discrete Preference Games.” In: Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI. 2019, pp. 471–477. DOI: 10.24963/ijcai.2019/67.

[LSW15] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. “A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Opti- mization.” In: Proceeding of the IEEE 56th Annual Symposium on Foun- dations of Computer Science, FOCS. IEEE Computer Society, 2015, pp. 1049–1065. DOI: 10.1109/FOCS.2015.68.

[MP91] Nimrod Megiddo and Christos H. Papadimitriou. “On total functions, existence theorems and computational complexity.” In: Theoretical Com- puter Science 81.2 (1991), pp. 317–324. ISSN: 0304-3975. DOI: 10 . 1016/0304-3975(91)90200-L.

[MS21a] Serge Massar and Miklos Santha. “Characterising the intersection of QMA and coQMA.” In: Quantum Information Processing 20.12 (2021), p. 396. DOI: 10.1007/s11128-021-03326-3.

[MS21b] Serge Massar and Miklos Santha. “Total functions in QMA.” In: Quan- tum Information Processing 20.1 (2021), p. 35. DOI: 10.1007/s11128-020-02959-0.

[NJ50] John F Nash Jr. “Equilibrium points in n-person games.” In: Proceedings of the national academy of sciences 36.1 (1950), pp. 48–49. DOI: 10. 1073/pnas.36.1.48.

[NV15] Thanh Nguyen and Rakesh Vohra. “Near Feasible Stable Matchings.” In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, Portland, OR, USA, June 15-19, 2015. Ed. by Tim Roughgarden, Michal Feldman, and Michael Schwarz. ACM, 2015, pp. 41–42. DOI: 10.1145/2764468.2764471.

[OPR16] Abraham Othman, Christos Papadimitriou, and Aviad Rubinstein. “The complexity of fairness through equilibrium.” In: ACM Transactions on Economics and Computation (TEAC) 4.4 (2016), pp. 1–19. DOI: 10 . 1145/2956583.

[Orl09] James B. Orlin. “A faster strongly polynomial time algorithm for sub- modular function minimization.” In: Mathematical Programming 118.2 (2009), pp. 237–251. DOI: 10.1007/s10107-007-0189-2.

[Pap05] Christos H. Papadimitriou. “Computing correlated equilibria in multi- player games.” In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, 2005, pp. 49–56. DOI: 10.1145/1060590. 1060598.

[Pap07] Christos H Papadimitriou. “The complexity of finding Nash equilibria.” In: Algorithmic game theory 2 (2007), p. 30.

[Pap94a] Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1994. ISBN: 978-0-201-53082-7.

[Pap94b] Christos H. Papadimitriou. “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence.” In: Journal of Computer and System Sciences 48.3 (1994), pp. 498–532. DOI: 10 . 1016 / S0022 - 0000(05)80063-7.

[Pol95] Svatopluk Poljak. “Integer Linear Programs and Local Search for Max- Cut.” In: SIAM Journal on Computing 24.4 (1995), pp. 822–839. DOI: 10.1137/S0097539793245350.

[Sca67] Herbert E Scarf. “The core of an N person game.” In: Econometrica: Journal of the Econometric Society (1967), pp. 50–69. DOI: 10.2307/ 1909383.

[Sha53] Lloyd S Shapley. “Stochastic games.” In: Proceedings of the national academy of sciences 39.10 (1953), pp. 1095–1100. DOI: 10 . 1073 / pnas.39.10.1095.

[Sip97] Michael Sipser. Introduction to the theory of computation. PWS Pub- lishing Company, 1997. ISBN: 978-0-534-94728-6.

[Spe28] E. Sperner. “Neuer beweis für die invarianz der dimensionszahl und des gebietes.” In: Abhandlungen aus dem Mathematischen Seminar der Uni- versität Hamburg 6.1 (1928), pp. 265 –272. ISSN: 0025-5858. DOI: 10. 1007/BF02940617.

[SS04] Rahul Savani and Bernhard von Stengel. “Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game”. In: Proceedings of the 45th Symposium on Foundations of Computer Science. IEEE Computer Society, 2004, pp. 258–267. DOI: 10.1109/FOCS.2004.28.

[SZZ18] Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. “PPP- Completeness with Connections to Cryptography.” In: 59th IEEE An- nual Symposium on Foundations of Computer Science, FOCS 2018. IEEE Computer Society, 2018, pp. 148–158. DOI: 10 .1109 / FOCS .2018 . 00023.

[Tar55] Alfred Tarski. “A lattice-theoretical fixpoint theorem and its applica- tions.” In: Pacific journal of Mathematics 5.2 (1955), pp. 285–309. DOI: 10.2140/pjm.1955.5.285.

[Tsc10] Tobias Tscheuschner. “The local max-cut problem is PLS-complete even on graphs with maximum degree five.” In: CoRR abs/1004.5329 (2010). DOI: 10.48550/arXiv.1004.5329. arXiv: 1004.5329.

[Yan09] Mihalis Yannakakis. “Equilibria, fixed points, and complexity classes.” In: Computer Science Review 3.2 (2009), pp. 71–85. DOI: 10.1016/j. cosrev.2009.03.004.

[ZF87] Stathis Zachos and Martin Furer. “Probabilistic quantifiers vs. distrustful adversaries.” In: International Conference on Foundations of Software Technology and Theoretical Computer Science. Springer. 1987, pp. 443–455. DOI: 10.1007/3-540-18625-5_67.