In the recent literature on machine learning and decision making, calibration
has emerged as a desirable and widely-studied statistical property of the
outputs of binary prediction models. However, the algorithmic aspects of
measuring model calibration have remained relatively less well-explored.
Motivated by [BGHN23], which proposed a rigorous framework for measuring
distances to calibration, we initiate the algorithmic study of calibration
through the lens of property testing. We define the problem of calibration
testing from samples where given $n$ draws from a distribution $\mathcal{D}$ on
(predictions, binary outcomes), our goal is to distinguish between the case
where $\mathcal{D}$ is perfectly calibrated, and the case where $\mathcal{D}$
is $\varepsilon$-far from calibration.
We design an algorithm based on approximate linear programming, which solves
calibration testing information-theoretically optimally (up to constant
factors) in time $O(n^{1.5} \log(n))$. This improves upon state-of-the-art
black-box linear program solvers requiring $\Omega(n^\omega)$ time, where
$\omega > 2$ is the exponent of matrix multiplication. We also develop
algorithms for tolerant variants of our testing problem, and give sample
complexity lower bounds for alternative calibration distances to the one
considered in this work. Finally, we present preliminary experiments showing
that the testing problem we define faithfully captures standard notions of
calibration, and that our algorithms scale to accommodate moderate sample
sizes.

通过近期关于机器学习和决策的文献，校准已成为二进制预测模型输出的理想和广泛研究的统计特性，本文通过性质测试的角度启动了校准的算法研究，设计了一种基于近似线性规划的算法，解决校准测试问题，同时开发了对该测试问题容差化的算法，并给出了其他校准距离的样本复杂性下界。

在次线性时间内进行校准测试

Testing Calibration in Subquadratic Time

Networked public goods games model scenarios in which self-interested agents
decide whether or how much to invest in an action that benefits not only
themselves, but also their network neighbors. Examples include vaccination,
security investment, and crime reporting. While every agent's utility is
increasing in their neighbors' joint investment, the specific form can vary
widely depending on the scenario. A principal, such as a policymaker, may wish
to induce large investment from the agents. Besides direct incentives, an
important lever here is the network structure itself: by adding and removing
edges, for example, through community meetings, the principal can change the
nature of the utility functions, resulting in different, and perhaps socially
preferable, equilibrium outcomes. We initiate an algorithmic study of targeted
network modifications with the goal of inducing equilibria of a particular
form. We study this question for a variety of equilibrium forms (induce all
agents to invest, at least a given set $S$, exactly a given set $S$, at least
$k$ agents), and for a variety of utility functions. While we show that the
problem is NP-complete for a number of these scenarios, we exhibit a broad
array of scenarios in which the problem can be solved in polynomial time by
non-trivial reductions to (minimum-cost) matching problems.

该研究开展了网络公共品博弈的算法研究，以诱导特定形式的均衡状态，研究了投资、网络结构和均衡状态对博弈结果的影响，并对多种均衡形式和效用函数进行了研究。