Research map / Learning theory and algorithms / Fairness
Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions
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 matching under known stationary Poisson arrivals where the objective is maximizing the minimum long-run matching rate across online types, proposing an LP-based sampling algorithm SAMP with competitiveness at least 1-1/e and hardness bounds.
Problem
Online bipartite matching under known stationary arrivals maximizing long-run individual fairness (minimum matching rate across online types), where standard total-matches objectives ignore fairness across types.
Approach
An LP benchmark whose optimal scale s* both upper-bounds the clairvoyant and drives an LP-based sampling policy (SAMP) that samples an eligible offline agent proportional to LP values and rejects if it is full; competitiveness is parameter-dependent and approaches one in several regimes. Also shows FCFS is optimal with a single offline agent.
Key results
- SAMP is at least (1-1/e)-competitive for OM-LF and approaches 1 when minimum offline capacity b grows large, when s* goes to 0 or infinity.
- FCFS is 1-competitive for long-run individual fairness with a single offline agent.
- Any non-rejecting policy is no more than 1/2-competitive, and any randomized policy is no more than (sqrt(3)-1)-competitive on the constructed bad example.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FCFS rather than an alternative online policy | OM-LF with one offline agent · OM-LF, single offline agent | competitive ratio: 1-competitive | Helped |
| Use SAMP for online matching | OM-LF with multiple offline agents · OM-LF, general case | competitive ratio: at least 1 − 1/e | Helped |
| Use SAMP when minimum offline capacity or demand regime grows | OM-LF · OM-LF, asymptotic regimes | competitive ratio: approaches 1 | Helped |
| Require a policy to serve every feasible arrival instead of rejecting selectively | Online matching policies · OM-LF, bad example | competitive ratio: no more than 1/2 | Hurt |
| Use any randomized online policy instead of a clairvoyant policy | OM-LF · OM-LF, bad example | competitive ratio: no more than (√3 − 1) | Hurt |
| Apply SAMP on the tightness instance | SAMP · OM-LF, bad example | competitive ratio: no more than (1 − 1/e) | Hurt |
| Use SAMP-G for group-level fairness | Group-level long-run fairness · Group-level long-run fairness | competitive ratio: at least 1 − e−bbb/b! | Helped |
| Use RESERVE for group-level fairness | Group-level long-run fairness · Group-level long-run fairness | competitive ratio: at least 1 − e−λλλ/λ! | Helped |
| Use FCFS for short-run fairness when λ ≤ 1 | Short-run fairness with one offline agent · Short-run fairness, single offline agent, λ ≤ 1 | competitive ratio: 0.863-competitive | Helped |
| Use Prob-Rej at high total arrival rates | Short-run fairness with one offline agent · Short-run fairness, single offline agent, λ → ∞ | competitive ratio: at least 1 − o(1) | Helped |
| Prioritize the rare type in the clairvoyant bad-example policy | OM-LF · OM-LF, bad example | long-run fairness: 1 − O(1/n) | Helped |
| Reject common-type arrivals with probability 1 − α | Rej(α) · OM-LF, bad example, rare types | long-run fairness: 1 − α/2 + o(1) | Mixed |
Surprising findings
- FCFS is zero-competitive for group-level long-run fairness with overlapping groups, even with a single offline agent.
- Optimal clairvoyant policy may need randomization over online types even on a fixed arrival realization, so per-realization max-min is insufficient.
Limitations
- Short-run fairness is only analyzed for a single offline agent; no general LP benchmark found.
- SAMP's analysis is tight at 1-1/e in the worst case, so competitiveness is not improved in general regimes.
- Theoretical paper with no empirical experiments reported.
Experimental setup
Metrics: long-run fairness competitive ratio
Baselines: FCFS non-rejecting policies SAMP-G RESERVE
Builds on: known identical independent distributions (KIID) online matching Ma et al. 2022 fairness among offline agents dependent rounding
Closest papers by meaning
- Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.89)
- Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations (ICML 2024 · similarity 0.89)
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.88)
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.88)
- Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty (NeurIPS 2024 · similarity 0.87)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.86)
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.