Online Fair Division with Additional Information

• URL: http://arxiv.org/abs/2505.24503v1
• Date: Fri, 30 May 2025 12:06:16 GMT
• Title: Online Fair Division with Additional Information
• Authors: Tzeh Yuan Neoh, Jannik Peters, Nicholas Teh,
• Abstract summary: We study the problem of fairly allocating indivisible goods to agents in an online setting.<n>We ask how the availability of information on future goods influences the existence and approximability of fair allocations.<n>We propose an algorithm that achieves stronger fairness guarantees than previously known results.
• Score: 7.435063833417366
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of fairly allocating indivisible goods to agents in an online setting, where goods arrive sequentially and must be allocated irrevocably to agents. Focusing on the popular fairness notions of envy-freeness, proportionality, and maximin share fairness (and their approximate variants), we ask how the availability of information on future goods influences the existence and approximability of fair allocations. In the absence of any such information, we establish strong impossibility results, demonstrating the inherent difficulty of achieving even approximate fairness guarantees. In contrast, we demonstrate that knowledge of additional information -- such as aggregate of each agent's total valuations (equivalently, normalized valuations) or the multiset of future goods values (frequency predictions) -- would enable the design of fairer online algorithms. Given normalization information, we propose an algorithm that achieves stronger fairness guarantees than previously known results. Given frequency predictions, we introduce a meta-algorithm that leverages frequency predictions to match the best-known offline guarantees for a broad class of ''share-based'' fairness notions. Our complementary impossibility results in each setting underscore both the limitations imposed by uncertainty about future goods and the potential of leveraging structured information to achieve fairer outcomes in online fair division.

Related papers

• Targeted Learning for Data Fairness [52.59573714151884]
  We expand fairness inference by evaluating fairness in the data generating process itself.<n>We derive estimators demographic parity, equal opportunity, and conditional mutual information.<n>To validate our approach, we perform several simulations and apply our estimators to real data.
  arXiv  Detail & Related papers  (2025-02-06T18:51:28Z)
• Identifying and Mitigating Social Bias Knowledge in Language Models [52.52955281662332]
  We propose a novel debiasing approach, Fairness Stamp (FAST), which enables fine-grained calibration of individual social biases.<n>FAST surpasses state-of-the-art baselines with superior debiasing performance.<n>This highlights the potential of fine-grained debiasing strategies to achieve fairness in large language models.
  arXiv  Detail & Related papers  (2024-08-07T17:14:58Z)
• Equal Opportunity of Coverage in Fair Regression [50.76908018786335]
  We study fair machine learning (ML) under predictive uncertainty to enable reliable and trustworthy decision-making. We propose Equal Opportunity of Coverage (EOC) that aims to achieve two properties: (1) coverage rates for different groups with similar outcomes are close, and (2) the coverage rate for the entire population remains at a predetermined level.
  arXiv  Detail & Related papers  (2023-11-03T21:19:59Z)
• Learning for Counterfactual Fairness from Observational Data [62.43249746968616]
  Fairness-aware machine learning aims to eliminate biases of learning models against certain subgroups described by certain protected (sensitive) attributes such as race, gender, and age. A prerequisite for existing methods to achieve counterfactual fairness is the prior human knowledge of the causal model for the data. In this work, we address the problem of counterfactually fair prediction from observational data without given causal models by proposing a novel framework CLAIRE.
  arXiv  Detail & Related papers  (2023-07-17T04:08:29Z)
• Sampling Individually-Fair Rankings that are Always Group Fair [9.333939443470944]
  A fair ranking task asks to rank a set of items to maximize utility subject to satisfying group-fairness constraints. Recent works identify uncertainty in the utilities of items as a primary cause of unfairness. We give an efficient algorithm that samples rankings from an individually-fair distribution while ensuring that every output ranking is group fair.
  arXiv  Detail & Related papers  (2023-06-21T01:26:34Z)
• Fairness in Matching under Uncertainty [78.39459690570531]
  algorithmic two-sided marketplaces have drawn attention to the issue of fairness in such settings. We axiomatize a notion of individual fairness in the two-sided marketplace setting which respects the uncertainty in the merits. We design a linear programming framework to find fair utility-maximizing distributions over allocations.
  arXiv  Detail & Related papers  (2023-02-08T00:30:32Z)
• Fair Ranking with Noisy Protected Attributes [25.081136190260015]
  We study the fair-ranking problem under a model where socially-salient attributes of items are randomly and independently perturbed. We present a fair-ranking framework that incorporates group fairness requirements along with probabilistic information about perturbations in socially-salient attributes.
  arXiv  Detail & Related papers  (2022-11-30T15:22:28Z)
• Attainability and Optimality: The Equalized Odds Fairness Revisited [8.44348159032116]
  We consider the attainability of the Equalized Odds notion of fairness. For classification, we prove that compared to enforcing fairness by post-processing, one can always benefit from exploiting all available features. While performance prediction can attain Equalized Odds with theoretical guarantees, we also discuss its limitation and potential negative social impacts.
  arXiv  Detail & Related papers  (2022-02-24T01:30:31Z)
• Fair Normalizing Flows [10.484851004093919]
  We present Fair Normalizing Flows (FNF), a new approach offering more rigorous fairness guarantees for learned representations. The main advantage of FNF is that its exact likelihood computation allows us to obtain guarantees on the maximum unfairness of any potentially adversarial downstream predictor. We experimentally demonstrate the effectiveness of FNF in enforcing various group fairness notions, as well as other attractive properties such as interpretability and transfer learning.
  arXiv  Detail & Related papers  (2021-06-10T17:35:59Z)
• Fair Densities via Boosting the Sufficient Statistics of Exponential Families [72.34223801798422]
  We introduce a boosting algorithm to pre-process data for fairness. Our approach shifts towards better data fitting while still ensuring a minimal fairness guarantee. Empirical results are present to display the quality of result on real-world data.
  arXiv  Detail & Related papers  (2020-12-01T00:49:17Z)
• Fast Fair Regression via Efficient Approximations of Mutual Information [0.0]
  This paper introduces fast approximations of the independence, separation and sufficiency group fairness criteria for regression models. It uses such approximations as regularisers to enforce fairness within a regularised risk minimisation framework. Experiments in real-world datasets indicate that in spite of its superior computational efficiency our algorithm still displays state-of-the-art accuracy/fairness tradeoffs.
  arXiv  Detail & Related papers  (2020-02-14T08:50:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.