We identify a novel connection between the recent literature on multi-group fairness for prediction algorithms and well-established notions of graph regularity from extremal graph theory. We frame our investigation using new, statistical distance-based variants of multi-calibration that are closely related to the concept of outcome indistinguishability. Adopting this perspective leads us naturally not only to our graph theoretic results, but also to new multi-calibration algorithms with improved complexity in certain parameter regimes, and to a generalization of a state-of-the-art result on omniprediction. Along the way, we also unify several prior algorithms for achieving multi-group fairness, as well as their analyses, through the lens of no-regret learning.

翻译：我们发现最近关于多组公平预测算法的文献与从极端图学理论中确立的图表规律概念之间的新联系。 我们使用与结果不可分概念密切相关的新的统计远程多校准变量来构建我们的调查。 采用这一视角自然不仅导致我们的图表理论结果,而且导致新的多校准算法,在某些参数系统中,这种算法的复杂程度有所提高,并导致对无孔不入的最先进的结果的概括化。 同时,我们还通过无孔不入的学习,统一了实现多组公平的若干先前的算法及其分析。