Online Fair Revenue Maximizing Cake Division with Non-Contiguous Pieces in Adversarial Bandits
This work addresses fair resource allocation in adversarial online settings, representing an incremental advance by applying existing bandit algorithms to a non-contiguous cake-cutting variant.
The paper tackles the problem of online fair revenue maximization in cake division with non-contiguous pieces, using adversarial multi-armed bandits to achieve sub-linear fairness and revenue regret simultaneously.
The classic cake-cutting problem provides a model for addressing the fair and efficient allocation of a divisible, heterogeneous resource among agents with distinct preferences. Focusing on a standard formulation of cake cutting, in which each agent must receive a contiguous piece of the cake in an offline setting, this work instead focuses on online allocating non-contiguous pieces of cake among agents and establishes algorithmic results for fairness measures. In this regard, we made use of classic adversarial multi-armed bandits to achieve sub-linear Fairness and Revenue Regret at the same time. Adversarial bandits are powerful tools to model the adversarial reinforcement learning environments, that provide strong upper-bounds for regret of learning with just observing one action's reward in each step by applying smart trade-off between exploration and exploitation. This work studies the power of the famous EXP_3 algorithm that is based on exponential wight{-}importance updating probability distribution through time horizon.