TY - JOUR

T1 - On Communication Complexity of Fixed Point Computation

AU - Ganor, Anat

AU - Karthik, C. S.

AU - Pálvölgyi, Dömötör

N1 - Funding Information:
Anat Ganor received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 740282). Karthik C. S. was supported by Irit Dinur’s ERC-CoG grant 772839. Dömötör Pálvölgyi was supported by the Lendület program of the Hungarian Academy of Sciences (MTA), under grant number LP2017-19/2017. Authors’ addresses: A. Ganor, Rothberg building, School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem 9190401, Israel; email: anat.ganor@gmail.com; Karthik C. S., Weizmann Institute of Science, 234 Herzl Street, Rehovot 7610001, Israel; email: karthik0112358@gmail.com; D. Pálvölgyi, Institute of Mathematics, Eötvös Loránd University (ELTE), Pázmány Péter sétány 1/C, Budapest H-1117, Hungary; email: dom@cs.elte.hu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2021 Association for Computing Machinery. 2167-8375/2021/10-ART25 $15.00 https://doi.org/10.1145/3485004
Publisher Copyright:
© 2021 Association for Computing Machinery.

PY - 2021/12

Y1 - 2021/12

N2 - Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from to , and their goal is to find an approximate fixed point of the composition of the two functions. They left it as an open question to show a lower bound of for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively. Additionally, we introduce two natural fixed point problems in the two-player communication model.Each player is given a function from to , and their goal is to find an approximate fixed point of the concatenation of the functions.Each player is given a function from to , and their goal is to find an approximate fixed point of the mean of the functions. We show a randomized communication complexity lower bound of for these problems (for some constant approximation factor). Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner's lemma) in the two-player communication model: A triangulation of the-simplex is publicly known and one player is given a set and a coloring function from to , and the other player is given a set and a coloring function from to , such that , and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of for the aforementioned problem as well (when is large). On the positive side, we show that if then there is a deterministic protocol for the Sperner problem with bits of communication.

AB - Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from to , and their goal is to find an approximate fixed point of the composition of the two functions. They left it as an open question to show a lower bound of for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively. Additionally, we introduce two natural fixed point problems in the two-player communication model.Each player is given a function from to , and their goal is to find an approximate fixed point of the concatenation of the functions.Each player is given a function from to , and their goal is to find an approximate fixed point of the mean of the functions. We show a randomized communication complexity lower bound of for these problems (for some constant approximation factor). Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner's lemma) in the two-player communication model: A triangulation of the-simplex is publicly known and one player is given a set and a coloring function from to , and the other player is given a set and a coloring function from to , such that , and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of for the aforementioned problem as well (when is large). On the positive side, we show that if then there is a deterministic protocol for the Sperner problem with bits of communication.

KW - Brouwer's fixed point theorem

KW - Nash equilibrium

KW - Sperner's lemma

KW - communication complexity

UR - http://www.scopus.com/inward/record.url?scp=85118632749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85118632749&partnerID=8YFLogxK

U2 - 10.1145/3485004

DO - 10.1145/3485004

M3 - Article

AN - SCOPUS:85118632749

SN - 2167-8375

VL - 9

JO - ACM Transactions on Economics and Computation

JF - ACM Transactions on Economics and Computation

IS - 4

M1 - 3485004

ER -