Sperner's colorings, hypergraph labeling problems and fair division

Abstract

We prove three results about colorings of the simplex reminiscent of Sperner's Lemma, with applications in hardness of approximation and fair division. First, we prove a coloring lemma conjectured by [5]: Let Vk, q={v ∈ ℤk)+:σ ki=1vi=q} and Ek, q={{a + e1, a + e2, ⋯, a + ek}: a ∈ℤk+, σki-1ai=q-1}. Then for ev-ery Sperner-admissible labeling (ℓ: Vk, q → [k] such that vℓ (v) > 0 for each v ∈Vk, q), there are at least (q+k-3k-2) monochromatic hyperedges in Ek, q. This implies an optimal Unique-Games hardness of (k-1-∈)-approximation for the Hypergraph Labeling with Color Lists problem [2]: Given a A;-uniform hypergraph H=(V, E) with color lists L (v) ⊆ [k] ∀v ∈V, find a labeling ℓ (v) ∈L (v) that minimizes the number of non-monochromatic hyperedges. We also show that a (k-l)-approximation can be achieved. Second, we show that in contrast to Sperner's Lemma, there is a Sperner-admissible labeling of Vk, q such that every hy-peredge in Ek, q contains at most 4 colors. We present an interpretation of this statement in the context of fair division: There is a preference function on Δk, q={x ∈ℝk+: σ=1xi=q} such that for any division of q units of a resource, (xi, x2, ⋯ xk) ∈δk, q such that σki=1 ⌊xi⌋=q-1> at most 4 players out of k are satisfied. Third, we prove that there are subdivisions of the simplex with a fractional labeling (analogous to a fractional solution for Min-CSP problems) such that every hyperedge in the subdivision uses only labelings with 1 or 2 colors. This means that a natural LP cannot distinguish instances of Hypergraph Labeling with Color Lists that can be labeled so that every hyperedge uses at most 2 colors, and instances that must have a rainbow hyperedge. We prove that this problem is indeed NP-hard for k=3.