Research map / Learning theory and algorithms / Fairness
Promoting External and Internal Equities Under Ex-Ante/Ex-Post Metrics in Online Resource Allocation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies online resource allocation under external equity (heterogeneous demands, ex-post/ex-ante) and internal equity (group fairness with unit demands), proving LP-based 1/2-competitive policies for external equity under ex-ante and optimal policies for internal equity.
Problem
Equitable online allocation of a limited divisible or indivisible resource to sequentially arriving agents, where equity is measured either by demand-proportional fair shares (external) or group-proportional shares (internal), under ex-post or ex-ante metrics, benchmarked against a clairvoyant optim
Approach
Defines external and internal equity models under ex-post and ex-ante metrics; for external equity under ex-ante it builds an LP upper bound and an attenuated randomized policy achieving CR 1/2; for internal equity it characterizes an optimal ex-ante policy via a threshold/randomized-rounding structure for Poisson arrivals.
Key results
- ATT policy for external equity under ex-ante achieves competitive ratio 1/2 relative to benchmark LP (1) with independent demands.
- An unconditional upper bound of 1/(2-2/e) ≈ 0.791 on competitive ratio for external equity under ex-ante is derived.
- Optimal ex-ante policy for internal equity under Poisson arrivals (RD, via dependent rounding) and optimal ex-post policy (Greedy) for internal equity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ATT, an LP-based policy with simulation-based attenuations | EEP under ex-ante with independent demands · EEP, ex-ante, independent demands | competitive ratio vs. benchmark LP: 1/2 | Helped |
| Use double-layer thresholding | EEP under ex-ante with independent demands · EEP, ex-ante, independent demands | competitive ratio vs. benchmark LP: 1/2 | Helped |
| Restrict demands to zero or values of at least one | EEP under ex-ante · EEP, ex-ante, demands of zero or at least one | competitive ratio vs. clairvoyant optimum | Helped |
| Bound every demand by K·ϵ²/ln(1/ϵ) | EEP under ex-post · EEP, ex-post, small demands | competitive ratio vs. clairvoyant optimum: 1−ϵ | Helped |
| Use RD with dependent rounding | IEP under ex-ante · IEP, ex-ante, unimodal arrival-count distribution | optimality among online policies | Helped |
| Use Greedy, serving each arrival while capacity remains | IEP under ex-post · IEP, ex-post | competitive ratio vs. clairvoyant optimum: 1-competitive | Helped |
| Allow correlated demands instead of restricting EEP to independent demands | Online policies for EEP · EEP, ex-post, correlated demands | competitive ratio: O(1/ ln n) | Hurt |
| Allow correlated demands instead of restricting EEP to independent demands | Online policies for EEP · EEP, ex-ante, correlated demands | competitive ratio: O(1/ ln n) | Hurt |
Surprising findings
- Greedy is 1-competitive for internal equity under ex-post, while ex-post and ex-ante optimal policies can differ.
- Under correlated demands, no policy can beat O(1/ln n) competitive ratio for external equity under either metric.
Limitations
- Competitive ratio of 1/2 is only proven relative to benchmark LP (1); unconditional gap to clairvoyant OPT is only bounded by 0.791.
- Ex-post external equity with independent demands is not solved for general demands; only small-demand case (1-epsilon) is handled.
- Internal equity is studied only for individual-level equity, not group-level.
Experimental setup
Metrics: ex-ante equity ex-post equity competitive ratio
Baselines: Greedy clairvoyant optimal (OPT)
Builds on: Manshadi et al. 2021 online fair allocation Papadimitriou et al. 2021 online matching with online optimal benchmark dependent rounding (Gandhi et al. 2006)
Closest papers by meaning
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.85)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.85)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.84)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.84)
- Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty (NeurIPS 2024 · similarity 0.84)
- Evaluating Index-based Treatment Allocation in Underresourced Communities (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.