Online Fair Division with Budget Constraints

• URL: http://arxiv.org/abs/2607.23310v1
• Date: Sat, 25 Jul 2026 17:53:10 GMT
• Title: Online Fair Division with Budget Constraints
• Abstract summary: We study an online variant of discrete fair division under generalized assignment budget constraints.<n>We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness.<n>We then identify bounded density spread as a structural condition that restores meaningful guarantees.
• Score: 20.176419497210585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.

Related papers

• The Limits of AI-Driven Allocation: Optimal Screening under Aleatoric Uncertainty [16.186900569675114]
  We show how screening and algorithmic targeting should be optimally combined in a two-stage allocation framework.<n>We show that the optimal strategy screens units at the margin of algorithmic allocation, while directly targeting the highest-risk units.<n>We illustrate our framework with applications in income-based social protection programs and humanitarian demining in Colombia.
  arXiv  Detail & Related papers  (2026-05-08T16:38:58Z)
• Robust and Consistent Ski Rental with Distributional Advice [13.811651343801579]
  The ski rental problem is a canonical model for online decision-making under uncertainty.<n>We propose a framework that integrates distributional advice of unknown quality into both deterministic and randomized algorithms.<n>We show that our framework improves consistency significantly over existing point-prediction baselines while maintaining comparable robustness.
  arXiv  Detail & Related papers  (2026-03-31T04:04:21Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Online Fair Division with Additional Information [7.435063833417366]
  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.
  arXiv  Detail & Related papers  (2025-05-30T12:06:16Z)
• SConU: Selective Conformal Uncertainty in Large Language Models [59.25881667640868]
  We propose a novel approach termed Selective Conformal Uncertainty (SConU)<n>We develop two conformal p-values that are instrumental in determining whether a given sample deviates from the uncertainty distribution of the calibration set at a specific manageable risk level.<n>Our approach not only facilitates rigorous management of miscoverage rates across both single-domain and interdisciplinary contexts, but also enhances the efficiency of predictions.
  arXiv  Detail & Related papers  (2025-04-19T03:01:45Z)
• End-to-End Conformal Calibration for Optimization Under Uncertainty [32.844953018302874]
  This paper develops an end-to-end framework to learn the uncertainty estimates for conditional optimization. In addition, we propose to represent arbitrary convex uncertainty sets with partially convex neural networks. Our approach consistently improves upon two-stage-then-optimize.
  arXiv  Detail & Related papers  (2024-09-30T17:38:27Z)
• Calibrated Probabilistic Forecasts for Arbitrary Sequences [58.54729945445505]
  Real-world data streams can change unpredictably due to distribution shifts, feedback loops and adversarial actors.<n>We present a forecasting framework ensuring valid uncertainty estimates regardless of how data evolves.
  arXiv  Detail & Related papers  (2024-09-27T21:46:42Z)
• Adjusting Regression Models for Conditional Uncertainty Calibration [46.69079637538012]
  We propose a novel algorithm to train a regression function to improve the conditional coverage after applying the split conformal prediction procedure. We establish an upper bound for the miscoverage gap between the conditional coverage and the nominal coverage rate and propose an end-to-end algorithm to control this upper bound.
  arXiv  Detail & Related papers  (2024-09-26T01:55:45Z)
• Probabilistic Conformal Prediction with Approximate Conditional Validity [81.30551968980143]
  We develop a new method for generating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution. Our method consistently outperforms existing approaches in terms of conditional coverage.
  arXiv  Detail & Related papers  (2024-07-01T20:44:48Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server. $alpha$-fraction of agents are adversarial and can report arbitrary fake information. We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
  arXiv  Detail & Related papers  (2022-06-01T00:44:53Z)
• Fair Classification with Adversarial Perturbations [35.030329189029246]
  We study fair classification in the presence of an omniscient adversary that, given an $eta$, is allowed to choose an arbitrary $eta$-fraction of the training samples and arbitrarily perturb their protected attributes. Our main contribution is an optimization framework to learn fair classifiers in this adversarial setting that comes with provable guarantees on accuracy and fairness. We prove near-tightness of our framework's guarantees for natural hypothesis classes: no algorithm can have significantly better accuracy and any algorithm with better fairness must have lower accuracy.
  arXiv  Detail & Related papers  (2021-06-10T17:56:59Z)

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.