Dynamic Fair Division with Partial Information

Gerdus Benadè (), Daniel Halpern () and Alexandros Psomas ()
Additional contact information
Gerdus Benadè: Boston University, Boston, Massachusetts 02215
Daniel Halpern: Harvard University, Cambridge, Massachusetts 02139
Alexandros Psomas: Purdue University, West Lafayette, Indiana 47907

Operations Research, 2025, vol. 73, issue 4, 1876-1896

Abstract: We consider the fundamental problem of fairly and efficiently allocating T indivisible items among n agents with additive preferences. Items become available over a sequence of rounds, and every item must be allocated immediately and irrevocably before the next one arrives. Previous work shows that when the agents’ valuations for the items are drawn from known distributions, it is possible (under mild assumptions) to find allocations that are envy-free with high probability and Pareto efficient ex post. However, this requires that agents accurately report their values to the algorithm, which rarely happens in practice. We study a partial-information setting, where true item values are hidden from the algorithm and it is only possible to elicit ordinal information in the form of a ranking or pairwise comparison relative to prior items. When values are drawn from i.i.d. distributions, or correlated distributions consisting of a shared common value for each item with i.i.d. noise, we give an algorithm that is envy-free and ( 1 − ϵ ) -welfare-maximizing with high probability. We provide similar guarantees (envy-freeness and a constant approximation to welfare with high probability) even with minimally expressive queries that ask for a comparison with a single previous item. For independent but nonidentical agents, we obtain envy-freeness and a constant approximation to Pareto efficiency with high probability. Our results are asymptotically tight. A computational study shows that envy-freeness and efficiency can be achieved on practical time-horizons.

Keywords: Market; Analytics; and; Revenue; Management; online allocation; fairness; online learning (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0608 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:4:p:1876-1896

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().