Promoting External and Internal Equities Under Ex-Ante/Ex-Post Metrics in Online Resource Allocation
Authors: Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 are 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. 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. 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 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. |
| Researcher Affiliation | Collaboration | 1Meta AI, Menlo Park, USA 2Department of Computer Science, University of Maryland, College Park, USA 3Department of Computer Science, New Jersey Institute of Technology, Newark, USA. |
| Pseudocode | Yes | Algorithm 1 An LP-based policy for external equity promotion under ex-ante (ATT). Algorithm 2 An optimal Randomized-Rounding-based policy for IEP under ex-ante (RD). Algorithm 3 A double-thresholding LP-based policy for EEP under ex-ante (DTH). Algorithm 4 An optimal LP-based policy for EEP under ex-ante with the large-demand assumption (ATT-L). |
| Open Source Code | No | The paper does not contain any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper describes theoretical models and algorithms; it does not utilize or refer to specific datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs rather than empirical experimental setups with hyperparameters or training details. |