# Fairness in the Multi-Secretary Problem

arXiv: https://arxiv.org/abs/2511.23097 · HTML: https://mlsanity.com/paper/2511.23097/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 48 references that are in the map.
- First posted on arXiv 28 Nov 2025.

## Builds on (most cited first, 30 of 30)

- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Multi-Winner Voting with Approval Preferences](https://mlsanity.com/paper/2007.01795/) (2020)
- [Proportional Participatory Budgeting with Additive Utilities](https://mlsanity.com/paper/2008.13276/) (2020)
- [Proportional Justified Representation](https://mlsanity.com/paper/1611.09928/) (2016)
- [Robust and Verifiable Proportionality Axioms for Multiwinner Voting](https://mlsanity.com/paper/2302.01989/) (2023)
- [Fair Allocation of Indivisible Public Goods](https://mlsanity.com/paper/1805.03164/) (2018)
- [Fair Public Decision Making](https://mlsanity.com/paper/1611.04034/) (2016)
- [Proportionality and the Limits of Welfarism](https://mlsanity.com/paper/1911.11747/) (2019)
- [The Core of the Participatory Budgeting Problem](https://mlsanity.com/paper/1610.03474/) (2016)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Representation with Incomplete Votes](https://mlsanity.com/paper/2211.15608/) (2022)
- [Participatory Budgeting: Data, Tools, and Analysis](https://mlsanity.com/paper/2305.11035/) (2023)
- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Optimized Distortion and Proportional Fairness in Voting](https://mlsanity.com/paper/2205.15760/) (2022)
- [Online Approval Committee Elections](https://mlsanity.com/paper/2202.06830/) (2022)
- [Fair Knapsack](https://mlsanity.com/paper/1711.04520/) (2017)
- [Putting a Compass on the Map of Elections](https://mlsanity.com/paper/2105.07815/) (2021)
- [Approval-Based Committee Voting in Practice: A Case Study of (Over-)Representation in the Polkadot Blockchain](https://mlsanity.com/paper/2312.11408/) (2023)
- [Random-Order Models](https://mlsanity.com/paper/2002.12159/) (2020)
- [Individual Fairness in Prophet Inequalities](https://mlsanity.com/paper/2205.10302/) (2022)
- [Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning](https://mlsanity.com/paper/2205.07831/) (2022)
- [Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting](https://mlsanity.com/paper/2312.08187/) (2023)
- [Properties of the Mallows Model Depending on the Number of Alternatives: A Warning for an Experimentalist](https://mlsanity.com/paper/2401.14562/) (2024)
- [Method of Equal Shares with Bounded Overspending](https://mlsanity.com/paper/2409.15005/) (2024)
- [Fair Secretaries with Unfair Predictions](https://mlsanity.com/paper/2411.09854/) (2024)
- [Approval-Based Voting with Mixed Goods](https://mlsanity.com/paper/2211.12647/) (2022)
- [Participatory Budgeting Design for the Real World](https://mlsanity.com/paper/2302.13316/) (2023)
- [Proportional Selection in Networks](https://mlsanity.com/paper/2502.03545/) (2025)
- [Robust Committee Voting, or The Other Side of Representation](https://mlsanity.com/paper/2506.18643/) (2025)

## Abstract (arXiv)

This paper bridges two perspectives: it studies the multi-secretary problem through the fairness lens of social choice, and examines multi-winner elections from the viewpoint of online decision making. After identifying the limitations of the prominent proportionality notion of Extended Justified Representation (EJR) in the online domain, the work proposes a set of mechanisms that merge techniques from online algorithms with rules from social choice -- such as the Method of Equal Shares and the Nash Rule -- and supports them through both theoretical analysis and extensive experimental evaluation.