<p>The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite this claim but I never found a formal proof. I think that there is a caveat in the "in $\mathbf{PPAD}$" part.</p>

<p>Recall the formulation of the Kakutani theorem: Let $S$ be a non-empty, compact and convex subset of Euclidean space and $F$ be an upper hemicontinuous set-valued function from $S$ to $2^S$ with non-empty and convex values. Then there exists a fixed point, i.e., $x$ such that $x\subset F(x)$.</p>

<p>When we deal with a computational version, first of all, $F$ must be somehow succinctly defined. But also we may hope to find only an approximate solution. And here comes the caveat.</p>

<ul>
<li>We may try to find a strong approximation, i.e., a point $x$ in $\epsilon$ vicinity of some fixed point $x^*$. Such a problem would be complete in $\mathbf{FIXP}$ (see [2]) and thus is believed to be harder than $\mathbf{PPAD}$. </li>
<li>We may try to find a weak approximation, i.e., a point $x$ such that $|F(x)-x|&lt;\epsilon$. This kind of approximation is typical for $\mathbf{PPAD}$ and is used in problems like BROUWER, NASH, EXCHANGE EQUILIBRIUM etc. The caveat is that in Kakutani theorem sometimes there are no such points besides the exact solution. (A trivial example: $F\colon [0,1]\to [0,1]$, $F(x)=1$ for $x&lt;a$, $F(x)=0$ for $x&gt;a$, $F(x)=[0,1]$ for $x=a$).</li>
</ul>

<p>So, my question is the following: does the search for a weakly approximate fixed point lie in $\mathbf{PPAD}$ when $F$ is a general succinctly defined set-valued function? (And thus if an $\epsilon$-fixed point is single then it must be simple). Or must we narrow the domain to something like partially linear functions? I believe, this is sufficient for applications but does not have the specified issue.</p>

<hr>

<p>[1] C. H. Papadimitriou. “On the Complexity of the Parity Argument and Other
Inefficient Proofs of Existence”. In: J. Comput. Syst. Sci. 48.3 (1994),
pp. 498–532. </p>

<p>[2] K. Etessami and M. Yannakakis. “On the complexity of Nash equilibria and
other fixed points”. In: SIAM Journal on Computing 39.6 (2010), pp. 2531–
2597.</p>

CC BY-SA 4.0
2018-08-10T15:20:00.807Z
I think the correct version would be that $\exists y$ such that $|y-x|<\epsilon$ and $x\in F(y)$.
domotorp
CC BY-SA 4.0
2018-08-13T07:32:34.730Z
As far as I know there is no known "good" definition of weak approximation for Kakutani fixed points in general. Also, I don't think that Etessami and Yannakakis make any claims about Kakutani fixed points. It is not even clear what is the "right" way to represent the set-valued function in general!
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2018-08-13T07:37:00.027Z
@Domotorp: That would be strong approximation, and thus at least FIXP-hard.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2018-08-13T08:14:06.640Z
What if we replace $x\in F(y)$ by $x\in N_{\epsilon}(F(y))$?
Daniil Musatov
CC BY-SA 4.0
2018-08-13T10:33:22.277Z
Yes, that would be a natural candidate definition.
Kristoffer Arnsfelt Hansen
<approximation-hardness><ppad><fixed-points>
Which version of KAKUTANI does lie in PPAD?
Daniil Musatov
# Which version of KAKUTANI does lie in PPAD?

(Asked by: username_0 on 2018-08-10)

The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite this claim but I never found a formal proof. I think that there is a caveat in the "in $\mathbf{PPAD}$" part.

Recall the formulation of the Kakutani theorem: Let $S$ be a non-empty, compact and convex subset of Euclidean space and $F$ be an upper hemicontinuous set-valued function from $S$ to $2^S$ with non-empty and convex values. Then there exists a fixed point, i.e., $x$ such that $x\subset F(x)$.

When we deal with a computational version, first of all, $F$ must be somehow succinctly defined. But also we may hope to find only an approximate solution. And here comes the caveat.

* We may try to find a strong approximation, i.e., a point $x$ in $\epsilon$ vicinity of some fixed point $x^\*$. Such a problem would be complete in $\mathbf{FIXP}$ (see [2]) and thus is believed to be harder than $\mathbf{PPAD}$.
* We may try to find a weak approximation, i.e., a point $x$ such that $|F(x)-x|<\epsilon$. This kind of approximation is typical for $\mathbf{PPAD}$ and is used in problems like BROUWER, NASH, EXCHANGE EQUILIBRIUM etc. The caveat is that in Kakutani theorem sometimes there are no such points besides the exact solution. (A trivial example: $F\colon [0,1]\to [0,1]$, $F(x)=1$ for $xa$, $F(x)=[0,1]$ for $x=a$).

So, my question is the following: does the search for a weakly approximate fixed point lie in $\mathbf{PPAD}$ when $F$ is a general succinctly defined set-valued function? (And thus if an $\epsilon$-fixed point is single then it must be simple). Or must we narrow the domain to something like partially linear functions? I believe, this is sufficient for applications but does not have the specified issue.

---

[1] C. H. Papadimitriou. “On the Complexity of the Parity Argument and Other
Inefficient Proofs of Existence”. In: J. Comput. Syst. Sci. 48.3 (1994),
pp. 498–532.

[2] K. Etessami and M. Yannakakis. “On the complexity of Nash equilibria and
other fixed points”. In: SIAM Journal on Computing 39.6 (2010), pp. 2531–
2597.

**Tags:** approximation-hardness, ppad, fixed-points
> **Comments:**
> **username_1**: I think the correct version would be that $\exists y$ such that $|y-x|<\epsilon$ and $x\in F(y)$.  
> **username_2**: As far as I know there is no known "good" definition of weak approximation for Kakutani fixed points in general. Also, I don't think that Etessami and Yannakakis make any claims about Kakutani fixed points. It is not even clear what is the "right" way to represent the set-valued function in general!  
> **username_2**: @Domotorp: That would be strong approximation, and thus at least FIXP-hard.  
> **username_0**: What if we replace $x\in F(y)$ by $x\in N_{\epsilon}(F(y))$?  
> **username_2**: Yes, that would be a natural candidate definition.  

---

## 0 answers

