TR-2012-04

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.



Abstract

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:

@techreport{egres-12-04,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {PPAD-completeness of polyhedral versions of Sperner's Lemma},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-04}
}


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