analiza aiqbench
This research applies mixed-integer linear programming to resolve theoretical bounds in computational social choice, directly addressing challenges in AI evaluation, alignment, and recommendation systems where conflicting model rankings must be aggregated. By eliminating dependence on electorate size, the study provides exact mathematical guarantees for selecting stable committees of AI models or benchmarks. This work advances the rigorous foundations required for reliable automated reasoning in multi-agent and evaluative AI contexts.
MILP the Gap: An Automated Reasoning Approach to Condorcet's Paradox
arXiv:2604.19851v2 Announce Type: replace-cross Abstract: Computational social choice studies how conflicting individual preferences are aggregated into a collective decision, with applications to elections, AI evaluation/alignment, and recommendation systems. We focus on settings where $n$ voters (e.g., human evaluators or algorithmic benchmarks) each rank $m$ alternatives (e.g., human candidates or AI models/outputs), and the goal is to select a committee of $k$ alternatives. One measure of the (in)stability of the outcome is the number of voters who prefer an unchosen alternative to all alternatives in the committee. If this number is less than half the electorate, the committee is a Condorcet winning set, which may not exist if $k \leq 2$. More generally, there exist instances where any committee of size $k$ has at least a $\frac{2}{(k+1)}-\epsilon$ fraction of the electorate preferring another alternative, for arbitrarily small $\epsilon$. While recent work has made remarkable progress narrowing the gap, it is currently unknown whether this lower bound is tight. We develop a mixed-integer linear programming framework that computes exact bounds for fixed parameter values. Our approach depends only on $m$ and $k$; by modeling electorates as distributions over rankings, we eliminate any dependence on $n$. Our programs allow us to rule out counterexamples over arbitrary electorate sizes and obtain tight bounds for fixed $m$ and $k$. Further, our framework provides a pathway for proving general upper bounds. In particular, we show a linear regime, $k \ge \frac{8m}{9}$, in which the conjectured $\frac{2}{(k+1)}$ upper bound indeed holds, providing the first results that match known lower bounds. Beyond stability, our framework can characterize the relationships among other social choice axioms, which we demonstrate by producing minimal incomparability results.
Abstract:Computational social choice studies how conflicting individual preferences are aggregated into a collective decision, with applications to elections, AI evaluation/alignment, and recommendation systems. We focus on settings where $n$ voters (e.g., human evaluators or algorithmic benchmarks) each rank $m$ alternatives (e.g., human candidates or AI models/outputs), and the goal is to select a committee of $k$ alternatives. One measure of the (in)stability of the outcome is the number of voters who prefer an unchosen alternative to all alternatives in the committee. If this number is less than half the electorate, the committee is a Condorcet winning set, which may not exist if $k \leq 2$. More generally, there exist instances where any committee of size $k$ has at least a $\frac{2}{(k+1)}-\epsilon$ fraction of the electorate preferring another alternative, for arbitrarily small $\epsilon$. While recent work has made remarkable progress narrowing the gap, it is currently unknown whether this lower bound is tight. We develop a mixed-integer linear programming framework that computes exact bounds for fixed parameter values. Our approach depends only on $m$ and $k$; by modeling electorates as distributions over rankings, we eliminate any dependence on $n$. Our programs allow us to rule out counterexamples over arbitrary electorate sizes and obtain tight bounds for fixed $m$ and $k$. Further, our framework provides a pathway for proving general upper bounds. In particular, we show a linear regime, $k \ge \frac{8m}{9}$, in which the conjectured $\frac{2}{(k+1)}$ upper bound indeed holds, providing the first results that match known lower bounds. Beyond stability, our framework can characterize the relationships among other social choice axioms, which we demonstrate by producing minimal incomparability results.
An earlier version titled "Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections" appears at the 8th Games, Agents, and Incentives Workshop (GAIW-26), held as part of the Workshops at the 25th International Conference on Autonomous Agents and Multiagent Systems
Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI)
arXiv:2604.19851 [cs.GT]
(or arXiv:2604.19851v2 [cs.GT] for this version)
Text integral sub licența deschisă a publicației · 331 cuvinte
Subiecte conexe
FLARE: Verifying MILP Reformulations with LLM-Based Theorem Proving
arXiv · 27 aug. 2026
Article: The AI Productivity Paradox in Test Automation: Moving beyond Structural Validation to Perception and Intent
InfoQ · 1 iun. 2026
The Machines that Make the Machines
NVIDIA · 7 oct. 2026
Fridays With Bob
IEEE Spectrum · 1 aug. 2026