GPT-5.6 Sol Ultra helps prove tight bound for election committees

In social choice theory, Condorcet's paradox shows that majority preferences can cycle, leaving no true winner. A recent line of work revealed that things improve if you pick a committee: for any ε > 0, there exists a committee of O(1/ε²) winners such that no losing candidate is preferred to every winner by more than 1/2 + ε of voters. In the new paper "Pessimal Elections for Approximately Dominating Sets" (arXiv:2608.06872), Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang construct elections where this bound is essentially the best possible, up to a constant factor. Notably, the construction was found by GPT-5.6 Sol Ultra, making it a striking example of AI-assisted mathematical discovery.

The result has direct implications for computational social choice, proportional representation, and the design of multi-winner voting rules. It establishes that any algorithm guaranteeing a committee with no majority-preferred loser requires a committee size of at least Ω(1/ε²) in the worst case, so the earlier existential bound is asymptotically tight. The paper also connects these committees to approximately dominating sets, linking election theory to combinatorial optimization. While the construction is worst-case, it helps map the fundamental limits of democratic decision-making. For researchers, the proof closes a gap in the theory and demonstrates how large language models can contribute novel, verifiable constructions in theoretical computer science.