Group-Fair Online Allocation in Continuous Time
The theory of discrete-time online learning has been successfully applied in many problems that involve sequential decision-making under uncertainty. However, in many applications including contractual hiring in online freelancing platforms and server allocation in cloud computing systems, the outcome of each action is observed only after a random and action-dependent time. Furthermore, as a consequence of certain ethical and economic concerns, the controller may impose deadlines on the completion of each task, and require fairness across different groups in the allocation of total time budget $B$. In order to address these applications, we consider continuous-time online learning problem with fairness considerations, and present a novel framework based on continuous-time utility maximization. We show that this formulation recovers reward-maximizing, max-min fair and proportionally fair allocation rules across different groups as special cases. We characterize the optimal offline policy, which allocates the total time between different actions in an optimally fair way (as defined by the utility function), and impose deadlines to maximize time-efficiency. In the absence of any statistical knowledge, we propose a novel online learning algorithm based on dual ascent optimization for time averages, and prove that it achieves $\tilde{O}(B^{-1/2})$ regret bound.
Code (0)
등록된 구현이 없습니다.
Tasks
Cloud ComputingDecision MakingDecision Making Under UncertaintyFairnessSequential Decision MakingSimilar Papers 제목 키워드 기반
Almost Group Envy-free Allocation of Indivisible Goods and Chores
We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and…
FairnessGroupwise Maximin Fair Allocation of Indivisible Goods
We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Specifically, maximin sh…
FairnessFair Resource Allocation for Demands with Sharp Lower Tail Inequalities
We consider a fairness problem in resource allocation where multiple groups demand resources from a common source with the total fixed amount. The general model was introduced by Elzayn et al. [FAT*'19]. We follow Donahu…
FairnessActive Learning for Fair and Stable Online Allocations
We explore an active learning approach for dynamic fair resource allocation problems. Unlike previous work that assumes full feedback from all agents on their allocations, we consider feedback from a select subset of age…
Active LearningDecision MakingFairnessParameterized Fair Resource Allocation under Diversity Constraints
Resource allocation across multiple agent groups arises in many applications including e-commerce recommendation systems, housing assignment, and course allocation, and is commonly formulated as an optimization problem w…
Recommendation Systems