Introduction

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.

Play the Labeling Game

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">Each node carries one of three labels (colors). Every edge has a <b>rule</b> — a one-to-one matching: if the lit end is label A, the other end must be the label the rule sends A to. Click a node to cycle its color and try to satisfy <b>every</b> edge. Green edge = rule holds, red = broken.</p>
<svg id="stage" viewBox="0 0 320 240" role="img" aria-label="Unique games graph"></svg>
<div class="status" id="status">Click nodes. Make every edge green.</div>
<div class="btns">
  <button id="check" type="button">Check</button>
  <button id="solve" type="button">Solve</button>
  <button id="hint" type="button" class="ghost">Hint</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A Unique Game: each node gets a label in {0,1,2}. Each edge carries a
// permutation P (a bijection on the labels). The edge (u->v) is satisfied iff
// label[v] === P(label[u]). Because P is a bijection, fixing one end forces a
// UNIQUE label on the other end — hence "unique" games. Checking an assignment
// is one pass; finding the best one is, in general, the hard part. Khot's 2002 conjecture says distinguishing ~99%-satisfiable from ~1% is NP-hard (OPEN).
const COLORS = ['#e63946', '#2a9d8f', '#e9c46a']; // labels 0,1,2
const NODES = [
  { x: 60,  y: 60  }, // 0
  { x: 260, y: 55  }, // 1
  { x: 165, y: 120 }, // 2 (center)
  { x: 55,  y: 185 }, // 3
  { x: 265, y: 190 }, // 4
];
// perm[a] = required label on the v-end when u-end is label a.
const ID     = [0, 1, 2];         // identity: ends must match
const SHIFT  = [1, 2, 0];         // v = u + 1 (mod 3)
const SHIFT2 = [2, 0, 1];         // v = u + 2 (mod 3)
// Edges chosen so a perfect assignment exists (labels 0 2 1 2 1). Each perm is
// a bijection, so fixing one end forces a UNIQUE label on the other.
const EDGES = [
  { u: 0, v: 2, perm: SHIFT  },
  { u: 1, v: 2, perm: SHIFT2 },
  { u: 3, v: 2, perm: SHIFT2 },
  { u: 4, v: 2, perm: ID     },
  { u: 0, v: 3, perm: SHIFT2 },
  { u: 1, v: 4, perm: SHIFT2 },
];
const K = 3, n = NODES.length;
let label = new Array(n).fill(0);

const svg = document.getElementById('stage');
const NS = 'http://www.w3.org/2000/svg';
function el(tag, attrs){ const e=document.createElementNS(NS,tag);
  for(const k in attrs) e.setAttribute(k, attrs[k]); return e; }

// An edge u->v is satisfied iff label[v] === perm[label[u]].
function edgeOk(e){ return label[e.v] === e.perm[label[e.u]]; }

function render(){
  svg.innerHTML = '';
  for(const e of EDGES){
    const a=NODES[e.u], b=NODES[e.v];
    const ln = el('line', { x1:a.x, y1:a.y, x2:b.x, y2:b.y,
      class:'edge'+(edgeOk(e)?' ok':' bad') });
    svg.appendChild(ln);
  }
  NODES.forEach((p,i)=>{
    const c = el('circle', { cx:p.x, cy:p.y, r:18, class:'node', fill:COLORS[label[i]] });
    c.addEventListener('click', ()=>{ label[i]=(label[i]+1)%K; render();
      setStatus('Click nodes. Make every edge green.',''); });
    svg.appendChild(c);
    const t = el('text', { x:p.x, y:p.y+4, 'text-anchor':'middle', class:'nlabel' });
    t.textContent = label[i]; svg.appendChild(t);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function countSat(asg){ let c=0; for(const e of EDGES) if(asg[e.v]===e.perm[asg[e.u]]) c++; return c; }

function check(){
  const sat = countSat(label);
  if(sat===EDGES.length) setStatus(fmt('✓ All %length% edges satisfied — you won the game!', { length: EDGES.length }),'ok');
  else setStatus(fmt('✗ %sat% of %length% edges satisfied. Keep going.', { sat: sat, length: EDGES.length }),'bad');
}
// Brute force: try all K^n labelings, keep the best (max satisfied edges).
function bestAssignment(){
  let best=null, bestSat=-1, tried=0;
  const cur=new Array(n).fill(0);
  function rec(i){
    if(i===n){ tried++; const s=countSat(cur);
      if(s>bestSat){ bestSat=s; best=cur.slice(); } return; }
    for(let l=0;l<K;l++){ cur[i]=l; rec(i+1); }
  }
  rec(0);
  return { best, bestSat, tried };
}
function solve(){
  const { best, bestSat, tried } = bestAssignment();
  label = best.slice(); render();
  const all = bestSat===EDGES.length;
  setStatus(fmt('%v% Best layout satisfies %bestSat%/%length% edges (searched %tried% = 3^%n% labelings).', { v: all?'✓ ':'', bestSat: bestSat, length: EDGES.length, tried: tried, n: n }), all?'ok':'bad');
  console.log('Brute force checked', tried, 'labelings; best satisfies', bestSat, 'of', EDGES.length, 'edges. Labels:', best.join(' '));
}
function hint(){
  const { best, bestSat } = bestAssignment();
  // reveal one node toward a perfect assignment
  let changed=-1;
  for(let i=0;i<n;i++) if(label[i]!==best[i]){ label[i]=best[i]; changed=i; break; }
  render();
  if(changed<0) setStatus(fmt('Already matching a best assignment (%bestSat%/%length%).', { bestSat: bestSat, length: EDGES.length }),'ok');
  else setStatus(fmt('Hint: node %changed% should be label %v%. Keep going!', { changed: changed, v: best[changed] }),'');
}
document.getElementById('check').addEventListener('click', check);
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('hint').addEventListener('click', hint);
document.getElementById('reset').addEventListener('click', ()=>{ label=new Array(n).fill(0); render(); setStatus('Click nodes. Make every edge green.',''); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/unique-games-conjecture/Content licensed under CC BY-NC 4.0.