Games on the Sperner Triangle
| dc.creator | Burke, Kyle | |
| dc.creator | Teng, Shang-Hua | |
| dc.date | 2007-02-26 | |
| dc.date.accessioned | 2026-07-07T07:48:40Z | |
| dc.date.available | 2026-07-07T07:48:40Z | |
| dc.description | We create a new two-player game on the Sperner Triangle based on Sperner's lemma. Our game has simple rules and several desirable properties. First, the game is always certain to have a winner. Second, like many other interesting games such as Hex and Geography, we prove that deciding whether one can win our game is a PSPACE-complete problem. Third, there is an elegant balance in the game such that neither the first nor the second player always has a decisive advantage. We provide a web-based version of the game, playable at: http://cs-people.bu.edu/paithan/spernerGame/ . In addition we propose other games, also based on fixed-point theorems. | |
| dc.description | 18 pages, 19 figures. Uses paithan.sty | |
| dc.identifier | https://arxiv.org/abs/cs/0702153 | |
| dc.identifier | http://arxiv.org/abs/cs/0702153 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/124583 | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Games on the Sperner Triangle | |
| dc.type | text |