Unique Games Conjecture

Imagine a group of friends standing at the corners of a network. You must hand each one a label — a color, a number, a name — and along every connecting edge the two friends must agree according to a fixed rule written on that edge. Satisfy every edge and you win. Satisfy as many as you can and you score partial credit.

That game is called Unique Games, and the word unique is the catch: on each edge, once you fix one friend's label, there is exactly one label that makes the other friend agree. No ambiguity, no freedom — each edge is a perfect matching between the two sets of labels.

It sounds easy. If almost all the edges can be satisfied at once, surely a computer can find an assignment that satisfies most of them? In 2002 Subhash Khot conjectured the opposite — that even telling apart "nearly all edges satisfiable" from "almost none satisfiable" is NP-hard. That single guess, still unproven today, would lock down the exact limit of thousands of algorithms.

Here is a small Unique Game. Each node gets one of three labels (colors). Every edge carries a rule: a one-to-one matching that says, "if this end is label X, the other end must be label Y." Click a node to cycle its color and try to make every edge agree.

<p class="hint">{{hint_para}}</p>
<svg id="stage" viewBox="0 0 320 240" role="img" aria-label="{{aria_stage}}"></svg>
<div class="status" id="status">{{status_idle}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="hint" type="button" class="ghost">{{btn_hint}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#stage { width: 100%; max-width: 360px; height: auto; display: block; margin: .2rem auto; }
.edge { stroke-width: 4; stroke: #adb1b8; transition: stroke .15s; }
.edge.ok { stroke: #0a7d33; }
.edge.bad { stroke: #c92f3c; }
.node { cursor: pointer; stroke: #1d3557; stroke-width: 2; transition: fill .12s; }
.node:hover { stroke-width: 3.5; }
.nlabel { font: 700 13px ui-monospace, monospace; fill: #fff; pointer-events: none; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; text-align: center; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice two things. First, checking a finished assignment is instant — walk each edge and confirm the rule holds. Second, on this hand-built board all edges can be satisfied at once. The conjecture is about the opposite regime: graphs where you can satisfy 99% of edges but no efficient algorithm can find an assignment that beats 1%. Press Solve to let the computer brute-force every labeling, and Hint to reveal one perfect assignment. Curious how this ties into the rest of complexity? See P vs NP.

So what is the precise status? Open. The Unique Games Conjecture (UGC) was posed by Subhash Khot in 2002 and, more than two decades later, it is neither proven nor disproven.

• The game is in NP to check. Given a labeling, verifying which edges are satisfied is trivial — a single pass.
• Exactly solving "can all edges be satisfied?" is easy when the answer is yes-and-perfect, but the interesting question is approximation: how close to the best can a fast algorithm get?
• The conjecture. For any tiny gap you pick, it is NP-hard to distinguish unique games where ~99% of edges are satisfiable from those where only ~1% are. In short: you can't even approximate the best labeling.
• The payoff. If UGC is true, it nails the exact approximation threshold for a whole zoo of problems. The famous Goemans–Williamson algorithm for Max-Cut reaches ratio ≈ 0.878 — and under UGC, no polynomial algorithm can do better. The same machinery pins down the optimal ratio for Vertex Cover and, via the work of Raghavendra (2008), for every constraint satisfaction problem at once.

That is why it matters so much that the question is still open. A proof would convert dozens of "we think this is the best possible" results into theorems. A disproof would hand us better algorithms for problems we currently believe are stuck. Either way the line between P vs NP-style tractability and intractability gets a lot sharper.

"Satisfy as many local agreement rules as you can" describes an enormous family of real optimization problems, and the Unique Games Conjecture tells us how good our best algorithms are allowed to be:

• Max-Cut and partitioning: splitting a network to cut the most connections — used in clustering, image segmentation and circuit layout. Under UGC, Goemans–Williamson's ≈0.878 is the ceiling.
• Vertex Cover and resource selection: choosing the fewest nodes to "cover" every edge. UGC implies the simple factor-2 algorithm is essentially optimal.
• Every CSP at once: scheduling, assignment and configuration problems are constraint satisfaction in disguise. Raghavendra showed UGC makes a single semidefinite-programming algorithm optimal for all of them.
• Knowing when to stop optimizing: hardness results save engineers from chasing algorithms that provably cannot exist — a practical payoff of a purely theoretical conjecture.

Understand Unique Games and you understand the modern map of inapproximability — the same terrain that surrounds Max-Cut and the broader P vs NP question.

The Unique Games Conjecture is a rare kind of open problem: a single, almost childlike game about handing out matching labels, whose answer would draw a precise line across the whole landscape of optimization. If Khot is right, then for problem after problem the algorithms we already have are the best there will ever be — and we would finally know it.

It remains unproven. Partial results, near-misses and powerful related theorems pile up each year, yet the central question stands open. The next time an app gives you a "good enough" answer instead of a perfect one, remember: somewhere behind it may sit a quiet labeling game, still waiting for someone to prove just how hard it really is. For the bigger picture, see P vs NP.