Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their formal introduction by Austrin, Guruswami, and Håstad, there has been a flurry of works on PCSPs, including recent breakthroughs in approximate graph coloring. The key tool in studying PCSPs is the algebraic framework developed in the context of CSPs where the closure properties of the satisfying solutions known as *polymorphisms* are analyzed.
The polymorphisms of PCSPs are significantly richer than CSPs---this is illustrated by the fact that even in the Boolean case, we still do not know if there exists a dichotomy result for PCSPs analogous to Schaefer's dichotomy result for CSPs. In this paper, we study a special case of Boolean PCSPs, namely Boolean *Ordered* PCSPs where the Boolean PCSPs have the predicate $x \leq y$. In the algebraic framework, this is the special case of Boolean PCSPs when the polymorphisms are *monotone* functions. We prove that Boolean Ordered PCSPs exhibit a computational dichotomy assuming the Rich $2$-to-$1$ Conjecture due to Braverman, Khot, and Minzer, which is a perfect completeness surrogate of the Unique Games Conjecture.
In particular, assuming the Rich $2$-to-$1$ Conjecture, we prove that a Boolean Ordered PCSP can be solved in polynomial time if for every $\epsilon >0$, it has polymorphisms where each coordinate has *Shapley value* at most $\epsilon$, else it is NP-hard. The algorithmic part of our dichotomy result is based on a structural lemma showing that Boolean monotone functions with each coordinate having low Shapley value have arbitrarily large threshold functions as minors. The hardness part proceeds by showing that the Shapley value is consistent under a uniformly random $2$-to-$1$ minor. As a structural result of independent interest, we construct an example to show that the Shapley value can be inconsistent under an adversarial $2$-to-$1$ minor.
