{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:12Z","timestamp":1750220592637,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T00:00:00Z","timestamp":1609545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Mexican National Council of Science and Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>\n            Suppose that an\n            <jats:italic>m<\/jats:italic>\n            -simplex is partitioned into\n            <jats:italic>n<\/jats:italic>\n            convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that occurs within some distance \u03b5 from that point. We present two algorithms for this task: Constant-Dimension Generalised Binary Search (CD-GBS), which for constant\n            <jats:italic>m<\/jats:italic>\n            uses poly(\n            <jats:italic>n<\/jats:italic>\n            , log (1\/\u03b5)) queries, and Constant-Region Generalised Binary Search (CR-GBS), which uses CD-GBS as a subroutine and for constant\n            <jats:italic>n<\/jats:italic>\n            uses poly(\n            <jats:italic>m<\/jats:italic>\n            , log (1\/\u03b5)) queries.\n          <\/jats:p>\n          <jats:p>We show via Kakutani\u2019s fixed-point theorem that these algorithms provide bounds on the best-response query complexity of computing approximate well-supported equilibria of bimatrix games in which one of the players has a constant number of pure strategies. We also partially extend our results to games with multiple players, establishing further query complexity bounds for computing approximate well-supported equilibria in this setting.<\/jats:p>","DOI":"10.1145\/3434412","type":"journal-article","created":{"date-parts":[[2021,1,3]],"date-time":"2021-01-03T05:04:13Z","timestamp":1609650253000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Learning Convex Partitions and Computing Game-theoretic Equilibria from Best-response Queries"],"prefix":"10.1145","volume":"9","author":[{"given":"Paul W.","family":"Goldberg","sequence":"first","affiliation":[{"name":"University of Oxford"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francisco J.","family":"Marmolejo-Coss\u00edo","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908734"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0794"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055407"},{"volume-title":"\u201cDemand Types","author":"Baldwin Elizabeth","key":"e_1_2_1_4_1","unstructured":"Elizabeth Baldwin and Paul Klemperer . 2016. Understanding Preferences: \u201cDemand Types \u201d and the Existence of Equilibrium with Indivisibilities. LSE Research Online Documents on Economics 63198. London School of Economics and Political Science, LSE Library . Retrieved from https:\/\/ideas.repec.org\/p\/ehl\/lserod\/63198.html. Elizabeth Baldwin and Paul Klemperer. 2016. Understanding Preferences: \u201cDemand Types\u201d and the Existence of Equilibrium with Indivisibilities. LSE Research Online Documents on Economics 63198. London School of Economics and Political Science, LSE Library. Retrieved from https:\/\/ideas.repec.org\/p\/ehl\/lserod\/63198.html."},{"volume-title":"Flavors of Geometry","author":"Ball Keith","key":"e_1_2_1_5_1","unstructured":"Keith Ball . 1997. An elementary introduction to modern convex geometry . In Flavors of Geometry , Silvio Levi (Ed.). Cambridge University Press , Cambridge, Chapter 1, 1--58. Keith Ball. 1997. An elementary introduction to modern convex geometry. In Flavors of Geometry, Silvio Levi (Ed.). Cambridge University Press, Cambridge, Chapter 1, 1--58."},{"key":"e_1_2_1_6_1","volume-title":"Some notes on computation of game solutions","author":"Brown George W.","year":"1949","unstructured":"George W. Brown . 1949. Some notes on computation of game solutions . RAND Corp. Rep . ( Apr. 1949 ), 78. George W. Brown. 1949. Some notes on computation of game solutions. RAND Corp. Rep. (Apr. 1949), 78."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794274246"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.10"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2886792"},{"key":"e_1_2_1_12_1","volume-title":"Levine","author":"Fudenberg Drew","year":"1998","unstructured":"Drew Fudenberg and David K . Levine . 1998 . The Theory of Learning in Games. MIT Press . Drew Fudenberg and David K. Levine. 1998. The Theory of Learning in Games. MIT Press."},{"volume-title":"Proceedings of the 13th Annual Conference on Learning Theory (COLT\u201900)","author":"Paul","key":"e_1_2_1_13_1","unstructured":"Paul W. Goldberg and Stephen Kwek. 2000. The precision of query points as a resource for learning convex polytopes with membership queries . In Proceedings of the 13th Annual Conference on Learning Theory (COLT\u201900) . Citeseer, 225--235. Paul W. Goldberg and Stephen Kwek. 2000. The precision of query points as a resource for learning convex polytopes with membership queries. In Proceedings of the 13th Annual Conference on Learning Theory (COLT\u201900). Citeseer, 225--235."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2956582"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-012-0362-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.07.002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2007.12.002"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2016.11.003"},{"volume-title":"Extremum Problems with Inequalities as Subsidiary Conditions","author":"John Fritz","key":"e_1_2_1_19_1","unstructured":"Fritz John . 2014. Extremum Problems with Inequalities as Subsidiary Conditions . Springer , Basel , 197--215. DOI:https:\/\/doi.org\/10.1007\/978-3-0348-0439-4_9 Fritz John. 2014. Extremum Problems with Inequalities as Subsidiary Conditions. Springer, Basel, 197--215. DOI:https:\/\/doi.org\/10.1007\/978-3-0348-0439-4_9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-41-00838-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1542-4774.2010.tb00523.x"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969530"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434412","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:48Z","timestamp":1750195908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,2]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3434412"],"URL":"https:\/\/doi.org\/10.1145\/3434412","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2021,1,2]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}