Regret And Cumulative Unfairness

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

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

@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