qhjqhj00 online-matching-fairness-eval
Fairness Maximization among Offline Agents in Online-Matching Markets — Ma et al. (2021) (arXiv:2109.08934, 2021)
What this evaluates
Evaluates online matching algorithms for maximizing individual and group fairness among offline agents, as well as weighted matching performance, under dynamic arrival constraints.
Datasets
- Chicago ride-hailing dataset — total ?; splits: test (-1); repo https://data.cityofchicago.org/Transportation/Transportation-Network-Providers-Trips/m6dm-c72p
- Network Data Repository (socfb-Caltech36, socfb-Reed98, econ-because, econ-mbeaflw) — total ?; splits: test (-1)
- Synthetic bipartite graphs — total ?; splits: test (-1)
Metrics
CR1(primary) — range: [0, 1]- Competitive Ratio 1: min_i E[Z_i] / x_i^, where Z_i is the number of times offline agent i is matched and x_i^ is the optimal offline LP solution.
CR2— range: [0, 1]- Competitive Ratio 2: sum_i w_i * E[Z_i], where w_i is the weight of offline agent i.
group fairness rate— range: [0, 1]- Minimum matching rate of offline agents across all predefined groups (e.g., community areas).
Input / output format
Input: Bipartite graph with offline agents (fixed set) and online agents arriving dynamically. Each online agent reveals its compatible offline neighbors upon arrival.
Output: A matching decision for each arriving online agent, selecting at most one available offline neighbor.
Scoring recipe
def compute_cr1(matches_per_agent, optimal_lp):
ratios = [matches_per_agent[i] / optimal_lp[i] for i in optimal_lp]
return min(ratios)
def compute_cr2(matches_per_agent, weights):
return sum(weights[i] * matches_per_agent[i] for i in weights)
Common pitfalls
- CR1 and CR2 are computed against an optimal offline LP solution (x^*) that must be solved per instance, not a fixed baseline.
- Group fairness is evaluated using geographic community areas as proxies for demographic groups, not direct demographic labels.
- Synthetic datasets assume uniform random weights and fixed average degree delta, which may overestimate performance on sparse real-world graphs.
Evidence (verbatim from paper)
For each algorithm, we compute two kinds of competitive ratio as follows: (1) CR1: min_i E[Z_i]/x_i^. (2) CR2: sum_i w_iE[Z_i]. Recall that our metric of group fairness is defined as the minimum matching rates of offline agents over all groups.
Citation
@misc{ma2021fairness,
title={Fairness Maximization among Offline Agents in Online-Matching Markets},
author={Ma et al. (2021)},
year={2021},
note={arXiv:2109.08934}
}
- arXiv: 2109.08934