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.

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{TR-2012-04}

}