Unique Games Conjecture

Start with arithmetic on a small clock. With 5 values, the numbers are 0, 1, 2, 3 and 4, and after 4 you return to 0. So $3 + 4 = 2$ on this clock. This is called arithmetic modulo 5.

A unique game is a list of rules about some unknown values on such a clock. Each rule links two unknowns, for example: $b$ equals $a$ plus 2. If you know $a$ , the rule gives exactly one value for $b$ . That is the meaning of "unique". The word "game" comes from an older form of the problem with two players.

Five unknowns on a clock with 5 values. Each arrow adds its number. These values satisfy all eight rules.

If all the rules can hold together, a solution is easy to find. Choose a value for $a$ , follow the rules, and fill in everything else. In the figure, $a = 0$ gives $b = 2$ , then $c = 3$ , $d = 2$ and $e = 0$ , and all eight rules hold.

Now suppose that only 99% of the rules can hold, and you do not know which 1% are bad. Following the rules now fails. A chain of 100 rules has about a 63% chance of hitting a bad rule. After that point, every value is wrong.

So you might aim much lower and try to satisfy only 1% of the rules. That sounds easy. The Unique Games Conjecture says that it is still hard, if the clock is large enough. When 99% of the rules can hold, finding values that satisfy even 1% of them is NP-hard.

NP-hard means that a fast method for this task would also solve every problem in a large family called NP. One of those problems is 3-SAT, a puzzle that asks if a row of on-off switches can obey a list of rules. Nobody has a fast method for those problems, and most researchers expect that none exists. "Fast" here means that the work grows like a fixed power of the input size.

An OpenAI paper reports a proof. It gives a fast way to turn any 3-SAT puzzle into a unique game. If the puzzle has a solution, nearly all the rules can hold. If not, almost none can. So a fast way to tell these two kinds of game apart would solve 3-SAT.

The conjecture is famous because of what it implies. Many problems have a fast method that gives a good but not perfect answer. The conjecture says that many of those methods are already the best possible, unless every problem in NP has a fast method.

Here is one example. Split the people at a party into two groups, so that as many pairs of rivals as possible end up in different groups. A known method guarantees at least 87.8% of the best possible count. If the proof is right, no fast method can guarantee more, unless every problem in NP has a fast method.