8
$\begingroup$

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 $x<a$, $F(x)=0$ for $x>a$, $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.

$\endgroup$
  • 1
    $\begingroup$ I think the correct version would be that $\exists y$ such that $|y-x|<\epsilon$ and $x\in F(y)$. $\endgroup$ – domotorp Aug 10 '18 at 15:20
  • 1
    $\begingroup$ 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! $\endgroup$ – Kristoffer Arnsfelt Hansen Aug 13 '18 at 7:32
  • 1
    $\begingroup$ @Domotorp: That would be strong approximation, and thus at least FIXP-hard. $\endgroup$ – Kristoffer Arnsfelt Hansen Aug 13 '18 at 7:37
  • 1
    $\begingroup$ What if we replace $x\in F(y)$ by $x\in N_{\epsilon}(F(y))$? $\endgroup$ – Daniil Musatov Aug 13 '18 at 8:14
  • 1
    $\begingroup$ Yes, that would be a natural candidate definition. $\endgroup$ – Kristoffer Arnsfelt Hansen Aug 13 '18 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.