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 is developed.
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.
Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study determinist...
A new randomized online algorithm for additive and submodular valuations, called Single-or-Sample, is developed, that achieves a constant-factor approximation to MMS simultaneously for all agents, with constant probability, and establishes a fundamental tradeoff between approximation and success probability.
Shuchi Chawla, Zhi-Yi Huang, Pooja Kulkarni et al.· 1 citation
We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily ac...
This work determines the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively, and improves when fewer agents value the same good, unlike uniform random allocation.
Although deciding whether a TEF1 allocation exists is NP-hard even for goods, this work identifies several tractable settings and gives an exact pseudo-polynomial algorithm for deciding TEF1 existence.
Kui-Wang Choi, Min-Ming Li, Nicholas J. Teh· 10 citations
Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs unde...
Yi-Long Feng, Zhihao Gavin Tang, Kang-Ning Wang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.