{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:28Z","timestamp":1781031448215,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X039862\/1"],"award-info":[{"award-number":["EP\/X039862\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/W014750\/1"],"award-info":[{"award-number":["EP\/W014750\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800817","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1049-1060","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6513-6748","authenticated-orcid":false,"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[{"name":"Royal Holloway University of London, Egham, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0791-4342","authenticated-orcid":false,"given":"John","family":"Fearnley","sequence":"additional","affiliation":[{"name":"University of Liverpool, Liverpool, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5255-9349","authenticated-orcid":false,"given":"Alexandros","family":"Hollender","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9867-6257","authenticated-orcid":false,"given":"Themistoklis","family":"Melissourgos","sequence":"additional","affiliation":[{"name":"University of Essex, Colchester, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085150"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840731"},{"key":"e_1_3_2_1_3_1","unstructured":"Benjamin Birnbaum Nikhil R Devanur and Lin Xiao. 2010. New convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities. Unpublished manuscript."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1536-7150.2005.00349.x"},{"key":"e_1_3_2_1_5_1","unstructured":"Mark Braverman. 2021. Optimization-friendly generic mechanisms without money. arXiv preprint arXiv:2106.07752."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17572-5_43"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.90"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_66"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060601"},{"key":"e_1_3_2_1_11_1","first-page":"72","article-title":"On the polynomial time computation of equilibria for certain exchange economies","volume":"5","author":"Codenotti Bruno","year":"2005","unstructured":"Bruno Codenotti, Sriram V Pemmaraju, and Kasturi R Varadarajan. 2005. On the polynomial time computation of equilibria for certain exchange economies. In SODA. 5, 72\u201381.","journal-title":"SODA."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Bruno Codenotti and Kasturi Varadarajan. 2007. Computation of market equilibria by convex programming. Algorithmic Game Theory 135\u2013158.","DOI":"10.1017\/CBO9780511800481.008"},{"key":"e_1_3_2_1_13_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 4180\u20134234","author":"Daskalakis Constantinos","year":"2023","unstructured":"Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. 2023. The complexity of Markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory. 4180\u20134234."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i5.25695"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673533"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673533"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3678166"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/s0022-0000(03)00011-4"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007431"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.30"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411512"},{"key":"e_1_3_2_1_22_1","volume-title":"Improved Hardness Results for the Clearing Problem in Financial Networks with Credit Default Swaps. In International Symposium on Algorithmic Game Theory. 81\u201398","author":"Dohn Simon","year":"2025","unstructured":"Simon Dohn, Kristoffer Arnsfelt Hansen, and Asger Klinkby. 2025. Improved Hardness Results for the Clearing Problem in Financial Networks with Credit Default Swaps. In International Symposium on Algorithmic Game Theory. 81\u201398."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.7.4.337"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2019.0129"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/140971002"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.91"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2026.03.004"},{"key":"e_1_3_2_1_28_1","unstructured":"Kristoffer Arnsfelt Hansen and Xinhao Nie. 2025. On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games. arXiv preprint arXiv:2510.11550."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1086\/260757"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Stavros D Ioannidis Bart de Keijzer and Carmine Ventre. 2023. Clearing Financial Networks with Derivatives: From Intractability to Algorithms. arXiv preprint arXiv:2312.05139.","DOI":"10.2139\/ssrn.4980490"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_9"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2023.06.007"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27819-1_2"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77105-0_40"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(95)00763-6"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806731"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2956583"},{"key":"e_1_3_2_1_38_1","first-page":"37354","article-title":"Multi-player zero-sum Markov games with networked separable interactions","volume":"36","author":"Park Chanwoo","year":"2023","unstructured":"Chanwoo Park, Kaiqing Zhang, and Asuman Ozdaglar. 2023. Multi-player zero-sum Markov games with networked separable interactions. Advances in Neural Information Processing Systems, 36 (2023), 37354\u201337369.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs.2016.35"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1039274"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0450"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970394"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.59"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213981"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:02:44Z","timestamp":1781028164000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":44,"alternative-id":["10.1145\/3798129.3800817","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800817","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}