PPAD-completeness of polyhedral versions of Sperner's Lemma

Tamás Király, Júlia Pap

Published in:
Discrete Mathematics 313:15 (2013), 1594-1599.


We show that certain polyhedral versions of Sperner's Lemma, where the colouring is given explicitly as part of the input, are PPAD-complete. The proofs are based on two recent results on the complexity of computational problems in game theory: the PPAD-completeness of 2-player Nash, proved by Chen and Deng, and of Scarf's Lemma, proved by Kintali. We show how colourings of polyhedra provide a link between these two results.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {PPAD-completeness of polyhedral versions of Sperner's Lemma},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-04}

Last modification: 13.3.2018. Please email your comments to Tamás Király!