Discrete Fixed Points: Models, Complexities, and Applications

• 成果类型: Article
• 署名作者: Deng, Xiaotie; Qi, Qi; Saberi, Amin; Zhang, Jie
• 署名单位: University of Liverpool; Stanford University; City University of Hong Kong
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0511
• 发表日期: 2011
• 页码: 636-652
• 关键词: variable dimension complexes; sperners lemma; algorithm; equilibrium; EXISTENCE; THEOREMS; PROOF

摘要

We study three discrete fixed point concept (SPERNER, DPZP, BROUWER) under two different models: the polynomial-time function model and the oracle function model. We fully characterize the computational complexities of these three problems. The computational complexity unification of the above problems gives us more choices in the study of different applications. As an example, by a reduction from DPZP, we derive asymptotically equal lower and upper bound for TUCKER in the oracle model. The same reduction also allows us to derive a single proof for the PPAD-completeness of TUCKER in any constant dimension, which is significantly simpler than the recent proofs.