Proportional allocation of indivisible resources under ordinal and uncertain preferences.

Zihao Li, Xiaohui Bei, Zhenzhen Yan
Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR 180:1148-1157, 2022.

Abstract

We study a fair resource allocation problem with indivisible items. The agents’ preferences over items are assumed to be ordinal and have uncertainties. We adopt stochastic dominance proportionality as our fairness notion and study a sequence of problems related to finding allocations that are fair with a high probability. We provide complexity analysis for each problem and efficient algorithms for some problems. Finally, we propose several heuristic algorithms to find an allocation that is fair with the highest probability. We thoroughly evaluate the performance of the algorithms on both synthetic and real datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v180-li22d, title = {Proportional allocation of indivisible resources under ordinal and uncertain preferences.}, author = {Li, Zihao and Bei, Xiaohui and Yan, Zhenzhen}, booktitle = {Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence}, pages = {1148--1157}, year = {2022}, editor = {Cussens, James and Zhang, Kun}, volume = {180}, series = {Proceedings of Machine Learning Research}, month = {01--05 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v180/li22d/li22d.pdf}, url = {https://proceedings.mlr.press/v180/li22d.html}, abstract = {We study a fair resource allocation problem with indivisible items. The agents’ preferences over items are assumed to be ordinal and have uncertainties. We adopt stochastic dominance proportionality as our fairness notion and study a sequence of problems related to finding allocations that are fair with a high probability. We provide complexity analysis for each problem and efficient algorithms for some problems. Finally, we propose several heuristic algorithms to find an allocation that is fair with the highest probability. We thoroughly evaluate the performance of the algorithms on both synthetic and real datasets.} }
Endnote
%0 Conference Paper %T Proportional allocation of indivisible resources under ordinal and uncertain preferences. %A Zihao Li %A Xiaohui Bei %A Zhenzhen Yan %B Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2022 %E James Cussens %E Kun Zhang %F pmlr-v180-li22d %I PMLR %P 1148--1157 %U https://proceedings.mlr.press/v180/li22d.html %V 180 %X We study a fair resource allocation problem with indivisible items. The agents’ preferences over items are assumed to be ordinal and have uncertainties. We adopt stochastic dominance proportionality as our fairness notion and study a sequence of problems related to finding allocations that are fair with a high probability. We provide complexity analysis for each problem and efficient algorithms for some problems. Finally, we propose several heuristic algorithms to find an allocation that is fair with the highest probability. We thoroughly evaluate the performance of the algorithms on both synthetic and real datasets.
APA
Li, Z., Bei, X. & Yan, Z.. (2022). Proportional allocation of indivisible resources under ordinal and uncertain preferences.. Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 180:1148-1157 Available from https://proceedings.mlr.press/v180/li22d.html.

Related Material