Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information

Ameet Gadekar, Aristides Gionis, Suhas Thejaswi, Sijing Tu · 2025

Read Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information by Ameet Gadekar, Aristides Gionis, Suhas Thejaswi, Sijing Tu (2025) 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-2512-24934.txt.

Introduction

Ameet Gadekar, Aristides Gionis, and Suhas Thejaswi study fair committee selection when voters give rankings but only limited numerical information. Agents are split into groups, and a committee of fixed size must guarantee minimum representation from each group while minimizing the worst cost any agent bears. They model the task as an ordinal fair k-center problem in an unknown metric space.

Rankings are assumed consistent with the hidden distances, which is all the algorithm may use. Social choice and algorithms readers get a fairness formulation balancing representation quotas with egalitarian cost. Committees, hiring panels, and representative bodies all face versions of this trade-off.

Catalog record

CREATORAmeet Gadekar, Aristides Gionis, Suhas Thejaswi, Sijing Tu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-24934

Browse the full library · About the Tower of Babel

Full text

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

Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information Ameet Gadekar, Aristides Gionis, Suhas Thejaswi, Sijing Tu Abstract We study the problem of fair k k -committee selection under an egalitarian objective. Given n n agents partitioned into m m groups ( e.g. , demographic quotas), the goal is to aggregate their preferences to form a committee of size k k that guarantees minimum representation from each group while minimizing the maximum cost incurred by any agent. We model this setting as the ordinal fair k k -center problem, where agents are embedded in an unknown metric space, and each agent reports a complete preference ranking ( i.e. , ordinal information) over all agents, consistent with the underlying distance metric ( i.e. , cardinal information). The cost incurred by an agent with respect to a committee is defined as its distance to the closest committee member. The quality of an algorithm is evaluated using the notion of distortion, which measures the worst-case ratio between the the cost of the committee produced by the algorithm and the cost of an optimal committee, when given complete access to the underlying metric space. When cardinal information is not available, no constant distortion is possible for the ordinal k k -center problem, even without fairness constraints, when k ≥ 3 k\geq 3 [Burkhardt et.al., AAAI’24]. To overcome this hardness, we allow limited access to cardinal information by querying the metric space. In this setting, our main contribution is a factor- 5 5 distortion algorithm that requires only 𝒪 ⁡ ( k ​ log 2 ​ k ) \mathcal{O}(k\log^{2}k) queries. Along the way, we present an improved factor- 3 3 distortion algorithm using 𝒪 ⁡ ( k 2 ) \mathcal{O}(k^{2}) queries. * * footnotetext: Authors are listed in alphabetical order. During this work, Suhas Thejaswi was employed at the Max Planck Institute for Software Systems, Germany, and part of this research was done while Suhas Thejaswi and Ameet Gadekar were visiting KTH Royal Institute of Technology, Sweden. 1 Introduction In many collective decision-making tasks, a group of agents ( e.g. , voters) needs to select a subset of alternatives ( e.g. , candidates) that provides equitable outcomes for each agent while respecting additional demographic fairness constraints. We consider this problem in the context of committee selection, which generalizes the single-winner selection problem to selecting multiple representatives. Specifically, we assume that agents and alternatives are embedded in a metric space, where the distance between an agent and an alternative represents the cost (or dissatisfaction) that the agent experiences when that alternative is selected. Each agent can provide a complete ranking over the alternatives that is consistent with these underlying distances: if an agent ranks alternative a above alternative b , then the distance from the agent to a is no greater than the distance from the agent to b . The computational social choice literature refers to these preference rankings as ordinal information, as opposed to the explicit distance values, which are referred to as cardinal information. The goal is to select a committee (subset of alternatives) that minimizes the social cost, defined as a function of the distances of agents to their closest member in the selected committee. While ordinal rankings are readily available, the exact distance values are typically unknown to the algorithm. A common way to evaluate the performance of a social choice algorithm that uses only ordinal information is through the notion of distortion , first introduced by Procaccia and Rosenschein 2006 . This concept was later extended to metric preferences by [ 3 ] , which measures the quality of the solution produced by the algorithm, defined as the worst-case ratio between the social cost of the algorithm’s solution and the social cost of the optimal solution that has full access to all pairwise distances. In recent years, metric distortion has been a central tool for evaluating the performance of social choice algorithms in the single-winner setting [ 3 , 29 , 19 , 25 , 26 , 10 , 15 , 11 ] , i.e. , when the committee consists of a single member. Recently, Pulyassary and Swamy 2025 and Burkhardt et al. 2024 extend the metric distortion framework from single-winner selection to k -committee selection, for arbitrary k . Their works consider both the utilitarian objective, which minimizes the sum of distances of each agent to its nearest committee member (which corresponds to the k -median or k -means objective), and the egalitarian objective, which minimizes the maximum distance of an agent to its nearest committee member (which corresponds to the k -center objective). Burkhardt et al. 2024 show that for k\geq 3 , no algorithm can achieve a constant distortion for the ordinal k -committee selection problem with the egalitarian objective (i..e, when cardinal information is not available). In light of this hardness result, both works additionally allow limited access to cardinal information through distance queries in order to obtain constant-factor distortion guarantees. In this paper, we continue this line of work by studying a fair version of k -committee selection. Specifically, we study the problem of ordinal fair k -committee selection with an emphasis on both equity and fairness . The equity principle ensures that no agent is unduly disadvantaged by the collective outcome; we encode this through the egalitarian objective, which minimizes the maximum distance from any agent to its nearest committee member. To enforce fairness in the committee, we assume that the alternatives are partitioned according to an underlying demographic profile. The goal is to guarantee minimum representation from each demographic group in the selected committee. Numerous studies in social welfare highlight that such minimum representation can promote equity, inclusion, and informed policy decisions. For instance, quotas have been widely considered as mechanisms to secure diverse representation and balance opportunities across groups [ 5 , 14 ] . Our fairness constraints are designed to align with this notion of demographic fairness. Additionally, similar to [ 6 , 8 ] , we focus on the setting where alternatives and agents coincide. Informally, the ordinal fair k -committee selection problem is defined as follows. We are given a set of agents embedded in an unknown metric space, partitioned into demographic groups. Each agent provides a complete ranking over all other agents that is consistent with the underlying distances in the metric space. The goal is to select a committee of size k using only a limited number of distance queries, subject to fairness constraints that ensure minimum representation from each group, while minimizing the maximum distance from any agent to its nearest committee member (the egalitarian objective). The key difference between our work and Pulyassary and Swamy 2025 and Burkhardt et al. 2024 is that we incorporate fairness constraints on minimum representation requirements for each demographic group. When full cardinal information is available, the ordinal fair k -committee selection problem is equivalent to the fair k -center problem [ 27 ] . To develop algorithmic solutions for the ordinal fair k -committee selection problem, we build on techniques from the fair k -center problem. For consistency with existing literature, we formulate our problem as the ordinal fair k -center problem with limited cardinal information, providing a

Read the complete text