Unique games conjecture

The following formulation of the unique games conjecture is often used in hardness of approximation. The conjecture postulates the NP-hardness of the following promise problem known as label cover with unique constraints. For each edge, the colors on the two vertices are restricted to some particular ordered pairs. Unique constraints means that for each edge none of the ordered pairs have the same color for the same node.

This means that an instance of label cover with unique constraints over an alphabet of size ${\displaystyle k}$ can be represented as a directed graph together with a collection of permutations${\displaystyle \pi _{e}:[k]\to [k]}$, one for each edge ${\displaystyle e}$ of the graph. An assignment to a label cover instance gives to each vertex of ${\displaystyle G}$ a value in the set ${\displaystyle [k]=\{1,2,\ldots ,k\}}$, often called “colours”.

• 
  An instance of unique label cover. The 4 vertices may be assigned the colors red, blue, and green while satisfying the constraints at each edge.
• 
  A solution to the unique label cover instance.

Such instances are strongly constrained in the sense that the colour of a vertex uniquely defines the colours of its neighbours, and hence for its entire connected component. Thus, if the input instance admits a valid assignment, then such an assignment can be found efficiently by iterating over all colours of a single node. In particular, the problem of deciding if a given instance admits a satisfying assignment can be solved in polynomial time.

• 
  An instance of unique label cover that does not allow a satisfying assignment.
• 
  An assignment that satisfies all edges except the thick edge. Thus, this instance has value 3/4.

The value of a unique label cover instance is the fraction of constraints that can be satisfied by any assignment. For satisfiable instances, this value is 1 and is easy to find. On the other hand, it seems to be very difficult to determine the value of an unsatisfiable game, even approximately. The unique games conjecture formalises this difficulty.

More formally, the ${\displaystyle (c,s)}$-gap label-cover problem with unique constraints is the following promise problem ${\displaystyle (L_{\text{yes}},L_{\text{no}})}$:

• ${\displaystyle L_{\text{yes}}=\{G:{\text{some assignment satisfies at least a }}c{\text{-fraction of constraints in }}G\}}$,
• ${\displaystyle L_{\text{no}}=\{G:{\text{every assignment satisfies at most an }}s{\text{-fraction of constraints in }}G\}}$,

where ${\displaystyle G}$ is an instance of the label cover problem with unique constraints.

The unique games conjecture states that for every sufficiently small pair of constants ${\displaystyle \varepsilon ,\delta >0}$, there exists a constant ${\displaystyle k}$ such that the ${\displaystyle (1-\delta ,\varepsilon )}$-gap label-cover problem with unique constraints over alphabet of size ${\displaystyle k}$ is NP-hard.

Consider the following system of linear equations over the integers modulo ${\displaystyle k}$:$${\displaystyle {\begin{aligned}a_{1}x_{1}&\equiv b_{1}\cdot x_{2}+c_{1}{\pmod {k}},\\a_{2}x_{2}&\equiv b_{2}\cdot x_{5}+c_{2}{\pmod {k}},\\&{}\ \ \vdots \\a_{m}x_{1}&\equiv b_{m}\cdot x_{7}+c_{m}{\pmod {k}}.\end{aligned}}}$$When each equation involves exactly two variables, this is an instance of the label cover problem with unique constraints; such instances are known as instances of the Max2Lin(k) problem. It is not immediately obvious that the inapproximability of Max2Lin(k) is equivalent to the UGC, but this is in fact the case, by a reduction.^[5] Namely, the UGC is equivalent to: for every sufficiently small pair of constants ε, δ > 0, there exists a constant k such that the (1 − δ, ε)-gap Max2Lin(k) problem is NP-hard.

It has been argued that the UGC is essentially a question of computational topology,^[6] involving local-global principles (the latter are also evident in the proof of the 2-2 Games Conjecture, see below).

Linial^[7] observed that unique label cover is an instance of the Maximum Section of a Covering Graph problem (covering graphs is the terminology from topology; in the context of unique games these are often referred to as graph lifts). To date, all known problems whose inapproximability is equivalent to the UGC are instances of this problem, including Unique Label Cover and Max2Lin(k). When the latter two problems are viewed as instances of Max Section of a Covering Graph, the reduction between them^[5] preserves the structure of the graph covering spaces,^[6] so not only the problems, but the reduction between them has a natural topological interpretation. Grochow and Tucker-Foltz exhibited a third computational topology problem whose inapproximability is equivalent to the UGC: 1-Cohomology Localization on Triangulations of 2-Manifolds.^[6]

A unique game is a special case of a two-prover one-round (2P1R) game. A two-prover one-round game has two players (also known as provers) and a referee. The referee sends each player a question drawn from a known probability distribution, and the players each have to send an answer. The answers come from a set of fixed size. The game is specified by a predicate that depends on the questions sent to the players and the answers provided by them.

The players may decide on a strategy beforehand, although they cannot communicate with each other during the game. The players win if the predicate is satisfied by their questions and their answers.

A two-prover one-round game is called a unique game if for every question and every answer by the first player, there is exactly one answer by the second player that results in a win for the players, and vice versa. The value of a game is the maximum winning probability for the players over all strategies.

The unique games conjecture states that for every sufficiently small pair of constants ε, δ > 0, there exists a constant k such that the following promise problem (L_yes, L_no) is NP-hard:

• L_yes = {G: the value of G is at least 1 − δ}
• L_no = {G: the value of G is at most ε}

where G is a unique game whose answers come from a set of size k.

Alternatively, the unique games conjecture postulates the existence of a certain type of probabilistically checkable proof for problems in NP.

A unique game can be viewed as a special kind of nonadaptive probabilistically checkable proof with query complexity 2, where for each pair of possible queries of the verifier and each possible answer to the first query, there is exactly one possible answer to the second query that makes the verifier accept, and vice versa.

The unique games conjecture states that for every sufficiently small pair of constants ${\displaystyle \varepsilon ,\delta >0}$ there is a constant ${\displaystyle K}$ such that every problem in NP has a probabilistically checkable proof over an alphabet of size ${\displaystyle K}$ with completeness ${\displaystyle 1-\delta }$, soundness ${\displaystyle \varepsilon }$, and randomness complexity ${\displaystyle O(\log n)}$ which is a unique game.