Matching Dependence for Approximately Dominating Sets in Elections

In a preprint submitted on August 7, 2026, Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang construct elections in which every $(1/2-\varepsilon)$-dominating set has size at least $(1+o(1))/(32\pi\varepsilon^2)$. Together with the recent upper bound of order $1/\varepsilon^2$, this establishes the asymptotically tight dependence $\Theta(1/\varepsilon^2)$ and resolves the central open question up to the constant factor.

A set of candidates is approximately dominating when, for every candidate outside the set, a candidate drawn uniformly from the set defeats it with probability at least $1/2-\varepsilon$. The authors say GPT-5.6 Sol Ultra originally generated both lower-bound proofs after being given the earlier paper and a prompt describing the problem. They subsequently supplied a streamlining idea and wrote their own exposition, and explicitly state that they take responsibility for the paper's contents.