{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T12:01:44Z","timestamp":1743076904393,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031095733"},{"type":"electronic","value":"9783031095740"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09574-0_11","type":"book-chapter","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T17:36:07Z","timestamp":1656005767000},"page":"170-189","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Discrete Versions of\u00a0the\u00a0KKM Lemma and\u00a0Their PPAD-Completeness"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Grishutin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1779-2513","authenticated-orcid":false,"given":"Daniil","family":"Musatov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"issue":"3","key":"11_CR1","doi-asserted-by":"publisher","first-page":"265","DOI":"10.2307\/1907353","volume":"22","author":"KJ Arrow","year":"1954","unstructured":"Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica 22(3), 265\u201390 (1954)","journal-title":"Econometrica"},{"doi-asserted-by":"crossref","unstructured":"Babichenko, Y., Rubinstein, A.: Settling the complexity of Nash equilibrium in congestion games. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1426\u20131437 (2021)","key":"11_CR2","DOI":"10.1145\/3406325.3451039"},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1998.1575","volume":"57","author":"P Beame","year":"1998","unstructured":"Beame, P., Cook, S., Edmonds, J., Impagliazzo, R., Pitassi, T.: The relative complexity of NP search problems. J. Comput. Syst. Sci. 57(1), 3\u201319 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511625756","volume-title":"Fixed Point Theorems With Applications to Economics and Game Theory","author":"KC Border","year":"1985","unstructured":"Border, K.C.: Fixed Point Theorems With Applications to Economics and Game Theory. Cambridge University Press, Cambridge (1985)"},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01456931","volume":"71","author":"LEJ Brouwer","year":"1911","unstructured":"Brouwer, L.E.J.: \u00dcber abbildung von mannigfaltigkeiten. Math. Ann. 71(1), 97\u2013115 (1911)","journal-title":"Math. Ann."},{"issue":"2","key":"11_CR6","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01768703","volume":"8","author":"V Bubelis","year":"1979","unstructured":"Bubelis, V.: On equilibria in finite games. Int. J. Game Theory 8(2), 65\u201379 (1979)","journal-title":"Int. J. Game Theory"},{"doi-asserted-by":"crossref","unstructured":"Chen, X., Dai, D., Du, Y., Teng, S.H.: Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. In: 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 273\u2013282 (2009)","key":"11_CR7","DOI":"10.1109\/FOCS.2009.29"},{"unstructured":"Chen, X., Deng, X.: Settling the complexity of 2-player Nash-equilibrium. Electronic Colloquium on Computational Complexity (ECCC), 140 (2005). http:\/\/eccc.hpi-web.de\/eccc-reports\/2005\/TR05-140\/index.html","key":"11_CR8"},{"issue":"44","key":"11_CR9","doi-asserted-by":"publisher","first-page":"4448","DOI":"10.1016\/j.tcs.2009.07.052","volume":"410","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X.: On the complexity of 2D discrete fixed point problem. Theoret. Comput. Sci. 410(44), 4448\u20134456 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. J. ACM (JACM) 56(3), 14 (2009)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"11_CR11","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009). https:\/\/doi.org\/10.1137\/070699652","journal-title":"SIAM J. Comput."},{"issue":"6","key":"11_CR12","doi-asserted-by":"publisher","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531\u20132597 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01769865","volume":"13","author":"D Gale","year":"1984","unstructured":"Gale, D.: Equilibrium in a discrete exchange economy with money. Int. J. Game Theory 13(1), 61\u201364 (1984)","journal-title":"Int. J. Game Theory"},{"doi-asserted-by":"crossref","unstructured":"Garg, J., Mehta, R., Vazirani, V.V., Yazdanbod, S.: Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. In: Proceedings of the 49th STOC, pp. 890\u2013901. ACM (2017)","key":"11_CR14","DOI":"10.1145\/3055399.3055474"},{"unstructured":"Goldberg, P.W.: A survey of PPAD-completeness for computing Nash equilibria. CoRR abs\/1103.2709 (2011). http:\/\/arxiv.org\/abs\/1103.2709","key":"11_CR15"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jcss.2021.05.004","volume":"122","author":"PW Goldberg","year":"2021","unstructured":"Goldberg, P.W., Hollender, A.: The hairy ball problem is PPAD-complete. J. Comput. Syst. Sci. 122, 34\u201362 (2021)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Hollender, A., Goldberg, P.: The complexity of multi-source variants of the end-of-line problem, and the concise mutilated chessboard. In: Electronic Colloquium on Computational Complexity, vol. 25, p. 120 (2018)","key":"11_CR17"},{"issue":"3","key":"11_CR18","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1215\/S0012-7094-41-00838-4","volume":"8","author":"S Kakutani","year":"1941","unstructured":"Kakutani, S.: A generalization of Brouwer\u2019s fixed point theorem. Duke Math. J. 8(3), 457\u2013459 (1941)","journal-title":"Duke Math. J."},{"issue":"6","key":"11_CR19","doi-asserted-by":"publisher","first-page":"2063","DOI":"10.1137\/120874655","volume":"42","author":"S Kintali","year":"2013","unstructured":"Kintali, S., Poplawski, L.J., Rajaraman, R., Sundaram, R., Teng, S.H.: Reducibility among fractional stability problems. SIAM J. Comp. 42(6), 2063\u20132113 (2013)","journal-title":"SIAM J. Comp."},{"issue":"1","key":"11_CR20","doi-asserted-by":"publisher","first-page":"132","DOI":"10.4064\/fm-14-1-132-137","volume":"14","author":"B Knaster","year":"1929","unstructured":"Knaster, B., Kuratowski, C., Mazurkiewicz, S.: Ein beweis des fixpunktsatzes f\u00fcr n-dimensionale simplexe. Fundam. Math. 14(1), 132\u2013137 (1929). https:\/\/doi.org\/10.4064\/fm-14-1-132-137","journal-title":"Fundam. Math."},{"doi-asserted-by":"publisher","unstructured":"Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theoret. Comput. Sci. 81(2), 317\u2013324 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90200-L, http:\/\/dx.doi.org\/10.1016\/0304-3975(91)90200-L","key":"11_CR21","DOI":"10.1016\/0304-3975(91)90200-L"},{"unstructured":"Musatov, D., Yakunin, A.: How hard is to find a stable jurisdiction structure? (2022). (forthcoming)","key":"11_CR22"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"1","author":"J Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Ann. Math. 1, 286\u2013295 (1951)","journal-title":"Ann. Math."},{"issue":"1","key":"11_CR24","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"JF Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium points in n-person games. Proc. Natl. Acad. Sci. 36(1), 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"11_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)"},{"issue":"4","key":"11_CR26","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/2956583","volume":"4","author":"A Othman","year":"2016","unstructured":"Othman, A., Papadimitriou, C., Rubinstein, A.: The complexity of fairness through equilibrium. ACM Trans. Econ. Comput. 4(4), 20 (2016)","journal-title":"ACM Trans. Econ. Comput."},{"doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Peng, B.: Public good games in directed networks. arXiv preprint arXiv:2106.00718 (2021)","key":"11_CR27","DOI":"10.1145\/3465456.3467616"},{"issue":"3","key":"11_CR28","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994). https:\/\/doi.org\/10.1016\/S0022-0000(05)80063-7","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Settling the complexity of computing approximate two-player Nash equilibria. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 258\u2013265. IEEE (2016)","key":"11_CR29","DOI":"10.1109\/FOCS.2016.35"},{"key":"11_CR30","first-page":"50","volume":"1","author":"HE Scarf","year":"1967","unstructured":"Scarf, H.E.: The core of an N person game. Econom. J. Econom. Soc. 1, 50\u201369 (1967)","journal-title":"Econom. J. Econom. Soc."},{"doi-asserted-by":"crossref","unstructured":"Schuldenzucker, S., Seuken, S., Battiston, S.: Finding clearing payments in financial networks with credit default swaps is PPAD-complete. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 67 (2017)","key":"11_CR31","DOI":"10.1145\/2940716.2940791"},{"doi-asserted-by":"crossref","unstructured":"Shapley, L.S.: On balanced games without side payments. In: Mathematical Programming, pp. 261\u2013290. Elsevier (1973)","key":"11_CR32","DOI":"10.1016\/B978-0-12-358350-5.50012-9"},{"issue":"1","key":"11_CR33","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0165-4896(02)00087-2","volume":"45","author":"FW Simmons","year":"2003","unstructured":"Simmons, F.W., Su, F.E.: Consensus-halving via theorems of Borsuk-Ulam and Tucker. Math. Soc. Sci. 45(1), 15\u201325 (2003)","journal-title":"Math. Soc. Sci."},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02940617","volume":"6","author":"E Sperner","year":"1928","unstructured":"Sperner, E.: Neuer beweis f\u00fcr die invarianz der dimensionszahl und des gebietes. Abh. Math. Semi. Univ. Hamb. 6, 265\u2013272 (1928)","journal-title":"Abh. Math. Semi. Univ. Hamb."},{"issue":"10","key":"11_CR35","doi-asserted-by":"publisher","first-page":"930","DOI":"10.2307\/2589747","volume":"106","author":"FE Su","year":"1999","unstructured":"Su, F.E.: Rental harmony: Sperner\u2019s lemma in fair division. Am. Math. Monthly 106(10), 930\u2013942 (1999)","journal-title":"Am. Math. Monthly"},{"issue":"3","key":"11_CR36","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/1970392.1970394","volume":"58","author":"VV Vazirani","year":"2011","unstructured":"Vazirani, V.V., Yannakakis, M.: Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM (JACM) 58(3), 10 (2011)","journal-title":"J. ACM (JACM)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09574-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T23:03:32Z","timestamp":1656284612000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09574-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031095733","9783031095740"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09574-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"24 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. Petersburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}