English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study a dynamic allocation problem in which $T$ sequentially arrivingdivisible resources are to be allocated to a number of agents with linearutilities. The marginal utilities of each resource to the agents are drawnstochastically from a known joint distribution, independently and identicallyacross time, and the central planner makes immediate and irrevocable allocationdecisions. Most works on dynamic resource allocation aim to maximize theutilitarian welfare, i.e., the efficiency of the allocation, which may resultin unfair concentration of resources on certain high-utility agents whileleaving others' demands under-fulfilled. In this paper, aiming at balancingefficiency and fairness, we instead consider a broad collection of welfaremetrics, the H\"older means, which includes the Nash social welfare and theegalitarian welfare. To this end, we first study a fluid-based policy derivedfrom a deterministic surrogate to the underlying problem and show that for allsmooth H\"older mean welfare metrics it attains an $O(1)$ regret over the timehorizon length $T$ against the hindsight optimum, i.e., the optimal welfare ifall utilities were known in advance of deciding on allocations. However, whenevaluated under the non-smooth egalitarian welfare, the fluid-based policyattains a regret of order $\Theta(\sqrt{T})$. We then propose a new policybuilt thereupon, called Backward Infrequent Re-solving with Thresholding($\mathsf{BIRT}$), which consists of re-solving the deterministic surrogateproblem at most $O(\log\log T)$ times. We prove the $\mathsf{BIRT}$ policyattains an $O(1)$ regret against the hindsight optimal egalitarian welfare,independently of the time horizon length $T$. We conclude by presentingnumerical experiments to corroborate our theoretical claims and to illustratethe significant performance improvement against several benchmark policies.

Uniformly Bounded Regret in Dynamic Fair Allocation