When agents choose bundles autonomously: guarantees beyond discrepancy
Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi
Abstract
We consider the fair division of indivisible items among agents with additive non-negative normalized valuations, with the goal of obtaining high value guarantees, that is, close to the proportional share for each agent. We prove that partitions where \emph{every} part yields high value for each agent are asymptotically limited by a discrepancy barrier of . Guided by this, our main objective is to overcome this barrier and achieve stronger individual guarantees for each agent in polynomial time. Towards this, we are able to exhibit an exponential improvement over the discrepancy barrier. In particular, we can create partitions on-the-go such that when agents arrive sequentially (representing a previously-agreed priority order) and pick a part autonomously and rationally (i.e., one of highest value), then each is guaranteed a part of value at least . Moreover, we show even better guarantees for three restricted valuation classes such as those defined by: a common ordering on items, a bound on the multiplicity of values, and a hypergraph with a bound on the \emph{influence} of any agent. Specifically, we study instances where: (1) the agents are ``close'' to unanimity in their relative valuation of the items -- a generalization of the ordered additive setting; (2) the valuation functions do not assign the same positive value to more than items; and (3) the valuation functions respect a hypergraph, a setting introduced by Christodoulou et al. [EC'23], where agents are vertices and items are hyperedges. While the sizes of the hyperedges and neighborhoods can be arbitrary, the influence of any agent , defined as the number of its neighbors who value at least one item positively that also values positively, is bounded.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper addresses fair division of indivisible items among *n* agents with additive valuations, introducing a sequential autonomous choice model where agents arrive in order and rationally pick their most-valued remaining bundle from a partition. The central contribution is threefold:
1. An impossibility result (Theorem 1.1): Any partition must have some part valued at PROP_a − Ω(√n) for some agent *a*, establishing that universal guarantees (where every part is good for every agent) are fundamentally limited by a Θ(√n) discrepancy barrier.
2. An exponential improvement via dynamic partitioning: By allowing the mechanism to rebundle items between agent arrivals, the paper achieves guarantees of PROP_i − O(log n) for each agent — an exponential improvement over the √n barrier. This is the paper's most significant result.
3. Specialized guarantees for restricted valuation classes: ordered-additive-like instances (with various swap metrics), bounded influence in hypergraph settings, and bounded indifference valuations, each yielding tighter bounds.
The key insight is distinguishing between *universal* guarantees (every part good for everyone) and *individual* guarantees (each agent gets a good part when choosing rationally). The "power of autonomy" combined with adaptive rebundling overcomes a barrier that seemed fundamental from the discrepancy-theoretic perspective.
Methodological Rigor
The paper is technically substantial and well-structured. The proofs are carefully organized with clear separation between cases:
One minor concern: the gap between the O(log n) upper bound and the Ω(√n) impossibility for universal guarantees leaves open whether the individual guarantee can be improved to O(1) or if there's a matching lower bound for the autonomous choice model. The authors acknowledge this explicitly.
Potential Impact
Within fair division: This paper opens a new model — autonomous sequential bundle selection with dynamic rebundling — that sits between fully centralized allocation and fully decentralized mechanisms. This model is practically relevant for settings where agents cannot be forced to accept specific bundles but can be presented with structured menus (e.g., course allocation, resource distribution in organizations).
Connection to discrepancy theory: The clean separation between universal and individual guarantees, and the demonstration that autonomy can exponentially bypass discrepancy barriers, provides a conceptual contribution that could influence how researchers think about fairness guarantees more broadly.
Hypergraph fair division: The bounded influence results contribute to the growing literature on graphical/hypergraph fair division initiated by Christodoulou et al. [EC'23], providing a new angle (proportionality via autonomous choice) complementing the EFX-focused work in this area.
Practical relevance: The sequential model with known arrival order is applicable to priority-based allocation systems (e.g., school choice, housing allocation). The "fair arrival order" computation (Theorem 1.8) adds a mechanism design dimension.
Timeliness & Relevance
The paper addresses a current bottleneck in fair division: bridging the gap between theoretical fairness guarantees and practical allocation mechanisms where agents have agency. The graphical/hypergraph fair division setting is a hot topic with numerous 2024-2025 publications cited. The connection to discrepancy theory, particularly building on the recent tight lower bound by Manurangsi and Meka [2026], makes this timely.
Strengths
Limitations
Generated Apr 19, 2026
Comparison History (80)
Paper 2 bridges deep reinforcement learning, game theory, and economics by enabling model-free learning in Dynamic Population Games. Its application to 'Karma economies' offers highly practical, real-world utility for non-monetary resource allocation. The combination of theoretical suboptimality bounds and empirical RL results provides a broader cross-disciplinary impact compared to the strictly theoretical improvements in fair division presented in Paper 1.
Paper 2 makes a stronger theoretical contribution to the well-established fair division problem, proving fundamental barriers (discrepancy bound of Θ(√n)) and then achieving an exponential improvement (O(log n)) over this barrier. The results are technically deep, addressing multiple valuation classes with clear algorithmic guarantees. Paper 1 addresses an interesting and timely question about LLM interaction design, but its stylized model and framework are more incremental. Paper 2's contributions to algorithmic game theory and combinatorics have broader mathematical impact and are likely to generate significant follow-up work.
Paper 2 introduces a novel framework with direct, high-stakes applications in security and defense. By providing an efficient linear programming solution to compute the Perfect Bayesian Nash Equilibrium in a game of deception, it overcomes significant computational hurdles. This methodological advance, combined with its clear real-world applicability and relevance to cybersecurity and strategic resource allocation, gives it broader and more immediate scientific impact than the theoretical fair division improvements in Paper 1.
Paper 2 presents a significant theoretical breakthrough by exponentially improving upon the known Theta(sqrt(n)) discrepancy barrier in fair division to achieve O(log n) guarantees. This mathematical leap in a fundamental problem (fair division of indivisible items) is likely to have a broader algorithmic impact and spur more follow-up work than Paper 1's auction theory refinements, despite Paper 1's strong contributions to information structure in mechanism design.
Paper 1 introduces a novel framework (explanation systems and price systems) for a well-studied problem in computational social choice, combining axiomatic foundations with algorithmic results and experiments. It opens a new research direction—explainability in multiwinner voting—that has broad implications for democratic decision-making and AI transparency. Paper 2 makes strong technical contributions to fair division with improved guarantees beyond discrepancy barriers, but addresses a more specific technical question. Paper 1's novelty in bridging explainability with voting theory, its practical relevance, and its potential to spawn follow-up work give it higher impact.
Paper 1 addresses a fundamental problem in fair division theory with strong theoretical contributions—proving a discrepancy barrier and then exponentially overcoming it with O(log n) guarantees. The results are mathematically rigorous, broadly applicable across combinatorial optimization and algorithmic game theory, and advance a well-studied area with clear improvements. Paper 2 is interesting but narrower in scope, targeting a specific application (AML compliance) with a mechanism design framework whose broader theoretical contributions are less clear. Paper 1's results are more likely to influence multiple research directions in theoretical computer science and economics.
Paper 2 has higher potential impact due to its direct real-world applicability (AML and inter-bank risk sharing), policy relevance (mandates can backfire), and cross-field reach (mechanism design, industrial organization/competition, compliance, and cybersecurity-style adversarial adaptation). It proposes a concrete incentive mechanism (TVA) with equilibrium guarantees and evaluates it in simulation, improving timeliness and translational potential. Paper 1 is technically strong and novel in fair division theory, but its applications are more indirect and likely narrower outside theoretical CS/econ.
Paper 1 addresses a fundamental problem in fair division with a novel exponential improvement over a discrepancy barrier, providing guarantees of PROP - O(log n) versus the Θ(√n) barrier. The result is technically deep, covering multiple valuation classes with broad applicability in algorithmic game theory and resource allocation. Paper 2 provides solid but more incremental results on PoA bounds for proportional mechanisms in auto-bidding, improving from 2 to 1+O(1/(n-1)). While relevant, Paper 1's breakthrough past a fundamental barrier and broader theoretical implications suggest higher scientific impact.
Paper 1 addresses the highly timely and commercially relevant problem of advertising within LLMs, bridging game theory and machine learning. Its focus on a novel, rapidly growing real-world application gives it a significant edge in potential broad scientific and economic impact compared to Paper 2, which focuses on a classical theoretical fair division problem with narrower appeal.
Paper 2 addresses offline learning in zero-sum games, a highly active area in AI and reinforcement learning. By achieving a fast O(1/n) sample complexity rate without relying on traditional pessimistic value estimation, it provides a significant methodological breakthrough. This advancement has broad implications for offline RL applications, which are currently critical in AI alignment and decision-making systems, giving it a higher potential for widespread scientific and practical impact compared to the algorithmic fair division improvements in Paper 1.