The Game of Hex implies Brouwer's fixed point theorem |
| T.E.S. Raghavan |
| Abstract |
| A key graph theoretic algorithm of Lemke and Howson for locating Nash equilibrium point is the starting point for all fixed point chasing algorithms. While Scarf gave such an algorithm for the so called KKM triangulation scheme, here we see how the well known Game of Hex has a winner implies the Brouwer's theorem. Its extensions to n-dimensions has not necessarily a unique winner. However the winning path of any player can be used to find approximate fixed point. |