Skip to yearly menu bar Skip to main content


Poster

Promoting External and Internal Equities Under Ex-Ante/Ex-Post Metrics in Online Resource Allocation

Karthik Abinav Sankararaman · Aravind Srinivasan · Pan Xu


Abstract: This paper proposes two different models for equitable resource allocation in online settings. The first one is called *external* equity promotion, where sequentially arriving agents are heterogeneous in their external attributes, namely how many resources they demand, which is drawn from a probability distribution (accessible to the algorithm). The focus is then to devise an allocation policy such that every requester can get a fair share of resources *proportional to their demands,* regardless of their arrival time. Motivating examples include allocating food donations to different agencies. The second is called *internal* equity promotion, where arriving requesters can be treated homogeneously in external attributes (demands) but are heterogeneous in internal traits such as demographics. In particular, each requester can be identified as belonging to one or several groups, and an allocation of resources is regarded as equitable when every group of requesters can receive a fair share of resources proportional to the percentage of that group in the whole population. An inspiring instance is rationing (limited) COVID-19 vaccines during the early stage of the pandemic.For both models above, we consider as the benchmark a clairvoyant optimal solution that has the privilege to access all random demand realizations in advance. We aim to design efficiently-computable policies whose performance is as close as possible to that of a clairvoyant optimal, where the largest possible ratio of the former to the latter over all possible instances is measured as competitive ratio (CR). We consider two equity metrics, namely *ex-post and ex-ante,* and discuss the challenges under the two metrics in detail. Specifically, we present two linear program (LP)-based policies for external equity promotion under ex-ante with independent demands, each achieving an *optimal* CR of $1/2$ with respect to the benchmark LP. For internal equity promotion, we present optimal policies under both ex-ante and ex-post metrics.

Live content is unavailable. Log in and register to view live content