Learning Fair Division from Bandit Feedback
Hakuei Yamada Junpei Komiyama Kenshi Abe Atsushi Iwasaki
This work addresses learning online fair division under uncertainty, where a
central planner sequentially allocates items without precise knowledge of
agents' values or utilities. Departing from conventional online algorithm, the
planner here relies on noisy, estimated values obtained after allocating items.
We introduce wrapper algorithms utilizing \textit{dual averaging}, enabling
gradual learning of both the type distribution of arriving items and agents'
values through bandit feedback. This approach enables the algorithms to
asymptotically achieve optimal Nash social welfare in linear Fisher markets
with agents having additive utilities. We establish regret bounds in Nash
social welfare and empirically validate the superior performance of our
proposed algorithms across synthetic and empirical datasets.