A unique game is a graph-labeling optimization problem in which each constraint is a permutation of a common finite alphabet 
(Trevisan 2008). An unweighted instance has a finite graph with a nonempty list of oriented
edges. For an edge 
with permutation 
, the constraint is satisfied when
the labels obey 
.
The value 
is the maximum fraction of constraints satisfied by
one labeling of all vertices. For 
, a permutation exchanging
0 and 1 requires different labels at its two endpoints.
Unique Game
See also
2-to-1 Game, NP-Hard Problem, Unique Games ConjectureExplore with Wolfram|Alpha
References
Trevisan, L. "Approximation Algorithms for Unique Games." Theory Comput. 4, 111-128, 2008. https://doi.org/10.4086/toc.2008.v004a005.Cite this as:
Weisstein, Eric W. "Unique Game." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/UniqueGame.html