Online Fair Allocation with Demand-Side Time-Dependent Weight

Minming Li, Youzhi Zhang, Shangkun Zheng
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:3668-3684, 2026.

Abstract

We study the problem of allocating indivisible items to a group of agents as these items arrive over time. Our focus is on scenarios where the utility of the items is weighted based on the waiting time since the last item was received, which is a demand-side time-dependent utility model. To ensure fairness, we concentrate on two criteria: temporal envy-freeness (TEF) and temporal proportionality (TProp). These criteria require that the allocation remains fair after each item is allocated. When there are two agents, we demonstrate the sufficient and necessary conditions of the weight function that ensure the existence of a TEF1 or TProp1 allocation. Additionally, we provide two polynomial-time algorithms that output a TEF2 or TProp2 allocation, with some restrictions on the weight function. When there are more than two agents, we show the hardness of determining the existence of TEF1 allocations. We also provide polynomial algorithms returning TEF1/TProp1 allocations with some specific valuation profiles. When there are multiple items per round, we also provide a polynomial algorithm returning TEF1/TProp1 allocations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-li26f, title = {Online Fair Allocation with Demand-Side Time-Dependent Weight}, author = {Li, Minming and Zhang, Youzhi and Zheng, Shangkun}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {3668--3684}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/li26f/li26f.pdf}, url = {https://proceedings.mlr.press/v337/li26f.html}, abstract = {We study the problem of allocating indivisible items to a group of agents as these items arrive over time. Our focus is on scenarios where the utility of the items is weighted based on the waiting time since the last item was received, which is a demand-side time-dependent utility model. To ensure fairness, we concentrate on two criteria: temporal envy-freeness (TEF) and temporal proportionality (TProp). These criteria require that the allocation remains fair after each item is allocated. When there are two agents, we demonstrate the sufficient and necessary conditions of the weight function that ensure the existence of a TEF1 or TProp1 allocation. Additionally, we provide two polynomial-time algorithms that output a TEF2 or TProp2 allocation, with some restrictions on the weight function. When there are more than two agents, we show the hardness of determining the existence of TEF1 allocations. We also provide polynomial algorithms returning TEF1/TProp1 allocations with some specific valuation profiles. When there are multiple items per round, we also provide a polynomial algorithm returning TEF1/TProp1 allocations.} }
Endnote
%0 Conference Paper %T Online Fair Allocation with Demand-Side Time-Dependent Weight %A Minming Li %A Youzhi Zhang %A Shangkun Zheng %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-li26f %I PMLR %P 3668--3684 %U https://proceedings.mlr.press/v337/li26f.html %V 337 %X We study the problem of allocating indivisible items to a group of agents as these items arrive over time. Our focus is on scenarios where the utility of the items is weighted based on the waiting time since the last item was received, which is a demand-side time-dependent utility model. To ensure fairness, we concentrate on two criteria: temporal envy-freeness (TEF) and temporal proportionality (TProp). These criteria require that the allocation remains fair after each item is allocated. When there are two agents, we demonstrate the sufficient and necessary conditions of the weight function that ensure the existence of a TEF1 or TProp1 allocation. Additionally, we provide two polynomial-time algorithms that output a TEF2 or TProp2 allocation, with some restrictions on the weight function. When there are more than two agents, we show the hardness of determining the existence of TEF1 allocations. We also provide polynomial algorithms returning TEF1/TProp1 allocations with some specific valuation profiles. When there are multiple items per round, we also provide a polynomial algorithm returning TEF1/TProp1 allocations.
APA
Li, M., Zhang, Y. & Zheng, S.. (2026). Online Fair Allocation with Demand-Side Time-Dependent Weight. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:3668-3684 Available from https://proceedings.mlr.press/v337/li26f.html.

Related Material