# Online Matching Fairness Eval

> Evaluates online matching algorithms for maximizing individual and group fairness among offline agents, as well as weighted matching performance, under dynamic arrival constraints. Use when the user wants to benchmark on Chicago ride-hailing dataset, Network Data Repository (socfb-Caltech36, socfb-Reed98, econ-because, econ-mbeaflw), Synthetic bipartite graphs, or asks about evaluating this task. Reports CR1.

- Skill: `qhjqhj00/online-matching-fairness-eval` (Agent Skill)
- Install (CLI): `npx skillmds add qhjqhj00/online-matching-fairness-eval`
- Raw SKILL.md: https://api.skillmd.com/api/skills/qhjqhj00/online-matching-fairness-eval/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: AI & ML
- Author: qhjqhj00 (https://skillmd.com/u/qhjqhj00)
- Updated: 2026-09-08
- Page: https://skillmd.com/skills/qhjqhj00/online-matching-fairness-eval

---


# 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

```python
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_i*E[Z_i]. Recall that our metric of group fairness is defined as the minimum matching rates of offline agents over all groups.

## Citation

```bibtex
@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