Regret And Cumulative Unfairness

---
name: regret_and_cumulative_unfairness
description: Evaluates online resource allocation algorithms by measuring their cumulative regret and cumulative unfairness across simulated environments with varying resource binding and degeneracy conditions. Use when the user has predictions and gold and needs to compute cumulative_unfairness.
metadata:
  skill_kind: metric
  source_arxiv: 2110.14621
  bibtex_key: chen2021fairerlp
  confidence: high
---

# regret_and_cumulative_unfairness

> Fairer LP-based Online Allocation via Analytic Center — Chen et al. (2021) (arXiv:2110.14621, 2021)

## What this evaluates

Evaluates online resource allocation algorithms by measuring their cumulative regret and cumulative unfairness across simulated environments with varying resource binding and degeneracy conditions.

## Datasets

- **Synthetic LP Environments** — total ?; splits: (unstated)

## Metrics

- `regret` — range: [0, infinity)
  - The difference between the optimal offline fluid LP objective and the expected cumulative reward achieved by the online algorithm over T time steps.
- `cumulative_unfairness` **(primary)** — range: [0, infinity)
  - The cumulative deviation of individual agent treatment or resource allocation from a fairness benchmark (analytic center of the optimal solution set) over T time steps.

## Input / output format

**Input**: Parameters defining the online LP: reward vector p, demand distribution mu, resource consumption matrix C, and initial resource supply b.

**Output**: Sequence of allocation decisions y_t for each arriving request, aggregated into regret and cumulative unfairness metrics.

## Scoring recipe

```python
def compute_metrics(optimal_lp_val, cumulative_reward, allocation_seq, benchmark):
    regret = optimal_lp_val - cumulative_reward
    cumulative_unfairness = sum(dist(a_t, benchmark) for a_t in allocation_seq)
    return regret, cumulative_unfairness
```

## Common pitfalls

- Regret measures efficiency/revenue loss, while cumulative unfairness measures deviation from a fairness benchmark; they are distinct objectives.
- Degeneracy in non-binding resources specifically drives linear vs logarithmic unfairness growth, not regret.
- Simulated environments are hand-crafted with specific binding/non-binding conditions rather than drawn from a standard dataset.

## Evidence (verbatim from paper)

> As expected, from Figure 5 we find that all the adaptive algorithms have $O(1)$ regret. We also notice similar behavior as in Section 3.3 that the Adaptive Interior (Algorithm 1) has a linear growth of cumulative unfairness while the Adaptive Fair (Algorithm 2) has an logarithmic order.

## Citation

```bibtex
@misc{chen2021fairerlp,
  title={Fairer LP-based Online Allocation via Analytic Center},
  author={Chen et al. (2021)},
  year={2021},
  note={arXiv:2110.14621}
}
```

- arXiv: 2110.14621