Ordinal Lindahl Equilibrium for Voting Conference: ; ;

Haoyu Song, Thanh Nguyen · 2026

Read Ordinal Lindahl Equilibrium for Voting Conference: ; ; by Haoyu Song, Thanh Nguyen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-04312.txt.

Introduction

Song and Nguyen extend Lindahl equilibrium to voting with ordinal preferences. The core blocks coalitions from backing pricier alternatives than their electorate share allows. LEO builds randomized outcomes meeting approximate core constraints, with each voter likely represented. A deterministic guarantee with factor 6.24 beats the old bound of 32, and structured cases compute fast. The result grounds fair representation and voting algorithms.

Catalog record

CREATORHaoyu Song, Thanh Nguyen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88962
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.04312

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ordinal Lindahl Equilibrium for Voting Conference: ; ; Haoyu Song, Thanh Nguyen Abstract . The core is a central concept in multi-winner social choice, ensuring that no coalition of voters can support an alternative outcome whose size or cost exceeds the group’s share of the electorate. This idea originates from the Lindahl equilibrium in classical public goods theory. Yet Lindahl equilibria may fail to exist when voters have ordinal preferences over a finite set of outcomes and monetary transfers are not allowed. We introduce Lindahl Equilibrium with Ordinal Preferences (LEO) , extending the equilibrium framework to discrete collective choice. Using LEO, we construct randomized outcomes that satisfy (approximate) core constraints for a probabilistic set of voters, while ensuring that each voter is represented with high probability. We also provide a deterministic approximate core guarantee with a factor of 6.24, improving on the previous bound of 32. In structured environments, these outcomes can be computed efficiently. Overall, our results extend classical equilibrium concepts, providing a normative foundation for proportional representation and practical algorithms for applications in voting and fair machine learning. 1. Introduction Multiwinner selection is a voting problem in which a group of agents report their preferences over alternatives, and the goal is to select a collective outcome that represents these agents fairly. Two prominent examples are committee selection and participatory budgeting (PB). In PB, each project has a cost, and voters express ordinal preferences over combinations of projects; the selected subset must fit within the budget while respecting voter preferences. Committee selection is a special case where all projects have equal cost (typically normalized to 1) and the budget corresponds to the size of the committee. Informally, proportional representation requires that no group of voters can support an alternative outcome whose size (or cost) exceeds their share of the electorate. This principle is captured by the proportional core ( EJR2017 ; 12 ) , which is motivated by the Lindahl equilibrium and the core of economies with divisible public goods. The traditional Lindahl equilibrium provides a canonical benchmark for public good provision by replacing a uniform price with personalized prices tailored to individual participants. At a Lindahl equilibrium, each agent chooses their preferred level of the public good given their personalized price and income, and equilibrium requires that all agents demand the same outcome. This coincidence of demand is coordinated by a fictitious central agent that selects the outcome to maximize total revenue—the sum of payments collected from all agents—relative to the cost of provision. By aligning payments with individual valuations, the Lindahl framework offers an appealing model of efficient and equitable public good provision. In particular, 15 shows that Lindahl equilibria lie in the core. Despite its conceptual appeal, neither Lindahl equilibria nor the proportional core generally exist in voting environments. The difficulty stems from the inherently non-convex nature of these settings: feasible outcomes are discrete, and voters typically have ordinal preferences over alternatives or subsets of alternatives. As a result, the Lindahl framework does not directly extend to many collective decision-making problems of practical interest. Prior work has therefore primarily focused on computationally tractable rules and on establishing fairness guarantees within this class. Such approaches often relax proportional-core requirements, restrict the domain of voter preferences, or combine both strategies. This bottom-up perspective prioritizes implementable rules and tailors fairness notions to the practical constraints of these mechanisms. In contrast, we adopt a top-down approach. Rather than being constrained by computational considerations, we take the equilibrium solution as the normative benchmark. We then extend it to ordinal preference settings to construct outcomes that approximately satisfy core constraints. This approach provides an economic framework for achieving fair and proportional outcomes, even in discrete combinatorial settings. Specifically, we consider a general model of social choice, which we call budgeted social choice , in which each outcome has an associated cost. The goal is to select an outcome whose cost does not exceed a given budget parameter and that (approximately) satisfies the core constraint. We assume a subadditive merge operation that combines two outcomes into a new, improved outcome with subadditive cost. This framework generalizes both committee selection and participatory budgeting, where outcomes are subsets of candidates or projects and the merge operation corresponds to set union. It also captures emerging settings such as generative social choice ( 14 ) , motivated by AI and large language models (LLMs), in which outcomes are textual statements, the cost reflects their length (or complexity), and merging corresponds to combining or refining statements. We make four main contributions. First, we introduce the Lindahl Equilibrium with Ordinal Preferences (LEO) , a modification of the classical Lindahl framework designed for environments with ordinal preferences. The modification has two components. Voters’ incomes are drawn from continuous random distributions, which smooths aggregate demand. In addition, the standard requirement that individual demands exactly coincide with the central allocation is relaxed: agreement is enforced only for components with strictly positive prices. These changes allow us to establish existence using a fixed-point argument while retaining the efficiency and fairness properties associated with Lindahl equilibria. Our first result shows that a LEO exists whenever the income distribution has a continuous cumulative distribution function. Second, we introduce the notion of a randomized core outcome , parameterized by two quantities. A (\lambda,\gamma) -randomized core is a lottery over outcomes in which, for each realization, only a subset of voters is represented. The \gamma -core constraint requires that no group within this subset can deviate to an alternative outcome whose cost is less than \gamma times their share of the electorate. Across the lottery, each voter belongs to a represented group with probability at least \lambda . In this sense, \gamma measures the strength of the core constraint for included voters, while \lambda measures the overall coverage across the electorate. Using LEO, we show that for every \alpha\geq 0 , there exists a (1-e^{-\alpha},\alpha+1) -randomized core solution, making explicit the tradeoff between coverage (the probability that a voter is represented) and the strength of the core constraint. It is known that a deterministic 2 - \epsilon -approximate core cannot be guaranteed for all voters ( 19 ) . As an implication, setting \alpha=1 yields a single outcome that satisfies the 2-approximate core for at least 63% of voters. While this is already notable, such a deterministic outcome may leave the remaining 37% of voters unrepresented. For \alpha=3 , coverage improves further: each voter is represented with probability at least 1-1/e^{3}\approx 95\% , while the outcome satisfies a 4-approximate core constraint. But importantly, randomization strengthens the guarantee for all voters: by constructing a lottery over outcomes, every voter is represented with probability at least 63%, avoiding systematic exclusion. In this way, the randomized core provides proportional representation across the entire electorate that no single deterministic outcome can achieve. Third, we show how to convert the randomized core into a deterministic core solution , which includes all voters. The resulting outcome achieves a 6.24 -approximation, a substantial improvement over the previous 32 -approximation in ( 19 ) . Lastly, regarding computation, our approach can be adapted for algorithmic purposes in certain scenarios. The key observation is that the equilibrium conditions underlying the construction of a randomized core can

Read the complete text