Persuasive Calibration
Yiding Feng, Wei Tang
Abstract
We introduce and study the persuasive calibration problem, where a principal aims to provide trustworthy predictions about underlying events to a downstream agent to make desired decisions. We adopt the standard calibration framework that regulates predictions to be unbiased conditional on their own value, and thus, they can reliably be interpreted at the face value by the agent. Allowing a small calibration error budget, we aim to answer the following question: what is and how to compute the optimal predictor under this calibration error budget, especially when there exists incentive misalignment between the principal and the agent? We focus on standard ℓ t \ell_{t} -norm Expected Calibration Error (ECE) metric. We develop a general framework by viewing predictors as post-processed versions of perfectly calibrated predictors. Using this framework, we first characterize the structure of the optimal predictor. Specifically, when the principal’s utility is event-independent and for ℓ 1 \ell_{1} -norm ECE, we show: (1) the optimal predictor is over-(resp. under-) confident for high (resp. low) true expected outcomes, while remaining perfectly calibrated in the middle; (2) the miscalibrated predictions exhibit a collinearity structure with the principal’s utility function. On the algorithmic side, we provide a FPTAS for computing approximately optimal predictor for general principal utility and general ℓ t \ell_{t} -norm ECE. Moreover, for the ℓ 1 \ell_{1} - and ℓ ∞ \ell_{\infty} -norm ECE, we provide polynomial-time algorithms that compute the exact optimal predictor.
1
Introduction
Over the past decade, machine learning models have grown remarkably powerful, with recent large-scale models (like LLMs) often containing billions of parameters and providing good predictions in a wide variety of domains.
Yet these models/algorithms are frequently regarded as black-box systems: their internal mechanisms remain proprietary, or are considered trade secrets and thus, are not observed by outsiders.
Consequently, end users and downstream decision-makers are often left to trust predictions without transparent insight into how those predictions are generated.
A prominent approach to bolstering trust in such predictions is
calibration
(
Dawid 1982
;
Foster and Vohra 1998
;
Hébert-Johnson et al. 2018
)
.
A calibrated predictor, in simple terms, regulates that predicted probabilities align with the true (conditional) probability of the outcome. For example, predictions of “70% likelihood” materialize approximately 70% outcome realizations of the time.
Calibration thus provides a guarantee that predictions are trustworthy and can be reliably taken at face value for use in downstream decision-making.
Indeed, it is well established that agents who
naively
best respond to calibrated predictions (i.e., those with low calibration error – a measure of how far the predictions deviate from the true conditional probability) achieve low regret
(
Foster and Vohra 1998
;
Kleinberg et al. 2023
;
Haghtalab et al. 2023
;
Roth and Shi 2024
;
Hu and Wu 2024
)
, whose rate is even no larger than the inherent calibration error of the predictor.
At the same time, however, the principal – the entity designing or deploying the prediction model – may have incentives that differ from those of the downstream agent who relies on these predictions. For example, the principal might wish to skew predictions ever so slightly to influence the agent’s actions in a beneficial (to the principal) way.
The above tension naturally leads to the following question:
If a small calibration error is permissible,
how might the principal design an optimal predictor that balances the principal’s objectives while preserving the agent’s trust by not miscalibrating so much?
To study this question, in this paper, we formulate and analyze the
persuasive calibration
problem.
Specifically, we introduce a framework in which the principal aims to provide predictions that must remain acceptably calibrated while ensuring that the downstream agent, who only sees the final predictions, would maintain sufficient trust to best-respond to them.
We aim to understand the following two question:
Can we characterize the optimal predictor under a calibration error budget, especially when there exists incentive misalignment between the principal and the agent? In addition, can we compute this optimal predictor or an approximately optimal predictor in polynomial time?
1.1
Our Contributions and Techniques
In this paper, we provide compelling answers to both of these questions. In a nutshell, we introduce the
persuasive calibration
problem which captures the interaction between the principal who decides the predictor and the agent who takes the action based on the prediction. In the first part of the paper, we focus on a canonical setting where the principal’s utility is event-independent and the predictor is evaluated based on the most classic
\ell_{1}
-norm calibration error. For this setting, we provide a comprehensive characterization of the optimal predictor. In the second part of the paper, we move to the more general setting where the principal’s utility can be arbitrary and the predictor can be evaluated by any
\ell_{t}
-norm calibration error. For this rich setting, we develop an FPTAS (fully polynomial-time approximation scheme) algorithm for all instances of our problem, and an optimal polynomial-time algorithm for
\ell_{1}
-norm or
\ell_{\infty}
-norm calibration errors. Below, we discuss our model, results, and techniques in detail.
The Principal-Agent Model (
Section
2
)
The
persuasive calibration
problem models the interaction between a predictor designer (the principal, she) and a downstream decision maker (the agent, he). In this setting, there is an underlying randomized binary outcome, which is unobserved by both players. However, the principal observes a realized
event
(e.g., a feature or context) that is correlated with the outcome and uses this information to generate a prediction. This prediction is a scalar value representing the probability that the binary outcome equals one.
The agent, whose utility depends on both his action and the realized outcome,
trusts
the prediction provided by the principal
and chooses an action which best responses to the provided prediction.
In contrast, the principal’s utility depends not only on the agent’s action but also on the realized event and outcome, and may be misaligned with the agent’s utility. The principal’s goal is to design a predictor that maximizes her own utility, given the agent’s best response.
We adopt the calibration framework to ensure the trustworthiness of the predictors –
that is, conditional on a given prediction, the expected true outcome should be close to the predicted probability. In this work, we focus on the classic
\ell_{t}
-norm expected calibration error (ECE), which quantifies the expected
\ell_{t}
-norm difference between the prediction and the true expected outcome. More formally, the
persuasive calibration
problem seeks the optimal predictor that maximizes the principal’s payoff, subject to an exogenously specified ECE budget.
Result I: Structural Characterization of the Optimal Predictor (
Section
3
)
We begin our exploration of the persuasive calibration problem under the
\ell_{1}
-norm ECE
(also known as the
K_{1}
ECE), which is the most standard calibration error metric.
We focus on a canonical setting where the principal’s
indirect utility
---mapping predictions to her utilities under the assumption that the agent best responds---is event-independent.
1
1
1
This assumption is common in various principal-agent models
(
Dworczak and Martini 2019
;
Lipnowski and Ravid 2020
;
Feng et al. 2022
;
Arieli et al. 2023
;
Corrao and Dai 2023
;
Feng et al. 2024
, e.g.,)
.
The structure results of the optimal predictor.
As the first main result of this paper, we provide a comprehensive characterization of the optimal predictor under any exogenously specified
K_{1}
ECE budget. In
Section
3.1
, we establish two key properties: (1) the
miscalibration structure
where the optimal predictor is over- (resp. under-) confident for high (resp. low) true expected outcomes while remaining perfectly calibrated in the middle; and (2) the
payoff structure
, where the miscalibrated predictions in the optimal predictor exhibit a collinearity pattern with the principal’s indirect utility function.
We illustrate both properties in
Figure
1(a)
. In this figure, the black solid curve represents the principal’s indirect utility, while each blue dot corresponds to a prediction generated by the optimal predictor. Specifically, the x-coordinate of each blue dot indicates the prediction value, and the y-coordinate represents the corresponding payoff for the principal. The brown squares denote the true expected outcomes conditional on the predictions.
Our
miscalibration structure
(in
Theorem
3.1
) suggests that the prediction space
[0,1]
can be partitioned into three sub-intervals:
(1) the
under-confidence interval
[0,p_{\mathsf{L}}]
, where predictions (blue dots) are lower (smaller x-coordinate) than their corresponding true expected outcomes (brown squares);
(2) the
over-confidence interval
[p_{\mathsf{H}},1]
, where predictions (blue dots) are higher (larger x-coordinate) than their corresponding true expected outcomes (brown squares); and
(3) the
perfectly calibrated interval
[p_{\mathsf{L}},p_{\mathsf{H}}]
, where predictions (blue dots) exactly match their corresponding true expected outcomes (brown squares).
We remark that this three-interval miscalibration pattern appears to be a well-observed phenomenon in the machine learning community. For example,
Guo et al. 2017
show that uncalibrated ResNet tends to be overconfident in its predictions, while
Kuleshov et al. 2018
show that neural networks consistently generate both underestimated and overestimated predictions/forecasts at the two extremes of the probability spectrum.
2
2
2
Also see Figure 4 in
Guo et al. 2017
and Figures 2, 3 in
Kuleshov et al. 2018
.
By interpreting the loss function in these machine learning tasks as the principal’s utility, our results provide a theoretical explanation for this practical observation.
Our
payoff structure
(in
Theorem
3.1
and
Proposition
3.2
) suggests that all blue dots (representing predictions and their induced payoffs for the principal) lie on a
symmetric linear-tailed convex function
\Gamma
(blue curve), which is pointwise (weakly) greater than the principal’s indirect utility (black curve). Moreover, all blue dots in the under-confidence interval
[0,p_{\mathsf{L}}]
(resp. over-confidence interval
[p_{\mathsf{H}},1]
) are collinear, with the slopes of these two linear tails having the same absolute value.
Besides the characterization above, we also (i) establish (almost) tight bounds on the number of predictions that can be generated by the optimal predictor – overall, per event, and per true expected outcome (
Proposition
3.3
), and (ii) provide a verification tool (
Proposition
3.9
) that enables us to theoretically verify the optimality of a given predictor.
p_{\mathsf{L}}
p_{\mathsf{H}}
x_{\mathsf{L}}
x_{\mathsf{H}}
(a)
\kappa(p)
p_{\mathsf{L}}
p_{\mathsf{H}}
(b)
Figure 1
:
In both figures, blue dots are the predictions
p
generated from the optimal predictor
\tilde{f}^{*}
,
brown squares are the corresponding true expected outcomes
\kappa(p)
conditional on the prediction
p
,
Figure
1(a)
is an illustration of
Theorem
3.1
– black solid curve is indirect utility
U
and blue curve is the convex function
\Gamma
in
Proposition
3.2
.
Figure
1(b)
is the reliable diagram (a standard visualization of the miscalibration structure) – black solid line is diagonal line.
Two-step framework to generate optimal predictors.
To prove the aforementioned structural results, we develop a two-step framework for the principal to design and analyze the optimal predictor. At a high level, the framework treats the predictor as a post-processed version of a perfectly calibrated predictor (i.e., zero calibration error). Specifically, we introduce the
post-processing plan
, which “miscalibrates” a perfectly calibrated predictor into an imperfectly calibrated one (
Definitions
3.6
and
3.7
and
Proposition
3.4
).
Using this concept, identifying the optimal predictor subject to an ECE budget constraint can be reformulated as optimizing a pair consisting of a perfectly calibrated predictor and an “ECE-budget-feasible” miscalibration plan.
This reformulation allows us to leverage well-established properties of perfectly calibrated predictors in the analysis.
A particularly interesting subclass of post-processing plans is the event-independent ones.
However, not every imperfectly calibrated predictor can be obtained by event-independently post-processing a perfectly calibrated predictor (see
Figure
3
for an illustration and
Example
3.9
for an example).
Perhaps interestingly,
we find that when the principal’s indirect utility is event-independent,
it suffices to consider event-independent post-processing plans to obtain the optimal predictor (
Proposition
3.7
).
Furthermore, optimizing over perfectly calibrated predictors and event-independent miscalibration plans can be characterized as a linear program (see
3.7
).
Primal-dual analysis of
3.7
.
Utilizing the two-step framework, we know that the optimal predictor can be transformed into an optimal solution of
3.7
and vice versa. Therefore, proving the structural results for the optimal predictor is equivalent to proving their analogs for the optimal solution in
3.7
. By developing both primal-based and duality-based arguments, we establish the aforementioned structural results in
Section
3.3
. Notably, the miscalibration structure is primarily proved through a primal-based argument, which leverages the structure (i.e., mean-preserving contraction (MPC)) of perfectly calibrated predictors, while the payoff structure is primarily proved using duality-based arguments. In particular, the symmetric linear-tailed convex function
\Gamma
(see
Figure
1(a)
and
Definition
3.4
) arises as a consequence of the optimal dual solutions. For example, the slope of its linear tail corresponds to the optimal dual variable associated with the ECE budget constraint in
3.7
.
Result II: FPTAS for Computing Approximately Optimal Predictor (
Section
4
)
Moving forward, we explore the algorithmic aspects of the persuasive calibration problem. We consider a more general setting where the principal’s utility can be arbitrary and the calibration metrics can be general
\ell_{t}
-norm ECE with any
t\geq 1
.
As the second main result of this paper, we provide a FPTAS (
Algorithm
1
and
Theorem
4.1
) for computing an approximately optimal predictor subject to any exogenously specified ECE budget.
To obtain a time-efficient algorithm for computing an approximately optimal predictor, a natural approach is to formulate the principal’s problem as a computationally tractable optimization program. However, due to the calibration error constraint defined on the predictor
\tilde{f}
, this approach is not straightforward.
3
3
3
In
Appendix
B
, we explain the failure of two natural optimization program formulations that directly use the predictor as the decision variable and optimize over the entire space of feasible predictors.
Our FPTAS contains two technical ingredients: it combines a generalized two-step framework, which extends the two-step approach (used in our structural characterization) from the event-independent setting to the general setting, with a carefully designed discretization scheme.
Generalized two-step framework.
For the general setting where the principal’s utility can depend on the realized event, our two-step framework with the
event-independent
post-processing plan established for the structural results may not be sufficient. Motivated by this, we introduce a generalized two-step framework in
Section
4.2
. However, if we consider an event-dependent post-processing plan that
fully decouples
the miscalibration across all events, additional non-linear constraints—seemingly intractable—are required. To bypass this issue, we introduce a generalized two-step framework with an
(event-dependent) bi-event post-processing plan
(
Definitions
4.1
and
4.2
), which allows us to formulate an infinite-dimensional (but tractable) linear program
4.3
. Our bi-event post-processing plan is rich enough to ensure that there always exists an optimal predictor that can be generated within our generalized framework (
Proposition
4.3
).
4
4
4
The foundational reason why the bi-event post-processing plan suffices is that our current model assumes a binary outcome. In fact, we believe that our FPTAS admits a relatively straightforward generalization to an extended model with a constant number of outcomes, which we leave for future exploration.
Instance-dependent two-layer discretization & rounding-based analysis.
Equipped with an infinite-dimensional linear program
4.3
, a natural approach is to consider its discretization. However, common discretization schemes, such as uniform discretization, are not directly applicable. Specifically, due to the ECE budget constraint, standard discretization may either render the discretized LP infeasible or significantly degrade the objective value.
To overcome this challenge, in
Section
4.3
, we introduce a carefully designed discretization scheme (
Definition
4.5
) that is instance-dependent and has a two-layer structure. First, given a discretization parameter
\delta>0
, our scheme constructs a non-uniform
\Theta(\delta)
-net, where the discretized points depend on the problem primitives, ensuring feasibility of the discretized program. Then, for each point in this
\Theta(\delta)
-net, we introduce a finer
\Theta(\delta_{0})
-net within a small neighborhood. Here,
\delta_{0}
depends not only on the discretization precision
\delta
but also on the ECE budget
\varepsilon
and the norm exponent parameter
t
. This second layer, which adapts to the ECE budget, allows us to carefully control changes in ECE when transitioning from a solution in the infinite-dimensional LP to one in the discretized LP. Crucially, the second-layer discretized points are introduced only locally, ensuring that the overall discretization set remains of polynomial size.
Finally, we develop a rounding scheme (
Algorithm
2
) to analyze both the feasibility and the objective value of the discretized program
4.6
. We believe that both our discretization scheme and rounding argument might be of independent interest in the algorithmic information design literature.
Result III: Computing Optimal Predictor under
K_{1}
or
K_{\infty}
ECE (
Section
5
)
As the third main result of this paper, we focus on the most standard ECE metrics, namely the
K_{1}
ECE (i.e.,
\ell_{1}
-norm ECE). We present a polynomial-time algorithm (
Algorithm
3
and
Theorem
5.1
) that computes an optimal predictor while adhering to any exogenously specified
K_{1}
ECE budget. Furthermore, we demonstrate that the same algorithm is also applicable to the
K_{\infty}
ECE (i.e.,
\ell_{\infty}
-norm ECE).
For
K_{1}
or
K_{\infty}
ECE, it is not difficult to express the calibration constraint as a linear constraint of the predictor. However, to obtain an optimal algorithm with polynomial running time, we also need to restrict the continuous space of predictions to a discrete polynomial-size set. To bypass this challenge, we build on an idea from the algorithmic information design literature.
Revelation principle and (Bayesian) persuasion with signal-dependent bias.
In the classic Bayesian persuasion problem
(
Kamenica and Gentzkow 2011
)
, the
revelation principle
assures that it is sufficient to consider signaling schemes that recommend an action. Hence, instead of searching over a (possibly) continuous signal space, it suffices to construct a signaling scheme with a signal space equal to the agent’s action space, which is polynomial-sized. However, such an approach seems difficult to apply to our model, as the design space in our model is restricted to predictions rather than arbitrary signals, and the agent in our model follows a much simpler behavior—i.e., always trusting the prediction—rather than engaging in strategic reasoning. Therefore, it is unclear a priori whether a revelation principle can be established.
Although at first glance, our persuasive calibration problem and the classic Bayesian persuasion problem may seem different, we demonstrate that the persuasive calibration problem can also be interpreted as a new variant of the Bayesian persuasion problem, which we refer to as
(Bayesian) persuasion with signal-dependent bias
. In this model, the receiver (equivalent to the agent) (1) has a utility function that depends linearly on the payoff-relevant state, and (2) exhibits a signal-dependent bias when updating their belief, rather than updating their belief in a fully Bayesian manner.
The sender (equivalent to the principal) now determines both the signaling scheme and the bias assignment for the receiver, subject to an exogenously specified constraints (Eqn. (
34
)) on the total bias.
5
5
5
By allowing the sender to design the bias assignment, our persuasion problem with signal-dependent bias shares similarities with the literature on
\varepsilon
-IC mechanism design
(
Balcan et al. 2005
;
Hartline and Lucier 2015
;
Cai et al. 2012
;
Balseiro et al. 2024
)
. Notably, even when selling a single item to a single buyer, the optimal
\varepsilon
-IC mechanism lacks a simple structural characterization
(
Balseiro et al. 2024
)
. In contrast, due to the equivalence between the persuasive calibration and this variant, we obtain a clean structural characterization for this persuasion problem.
In the special case where the total bias is restricted to zero, this variant reduces to the classic Bayesian persuasion problem.
With this equivalent interpretation, it becomes relatively more straightforward for us to identify a suitable revelation principle (
Lemma
5.2
) and formulate the problem of optimizing the pair consisting of the signaling scheme and the bias assignment (equivalent to the predictor) as an action-recommendation program
5.3
(
Proposition
5.3
). Notably, both the equivalence between two models and
5.3
holds for a general
\ell_{t}
-norm ECE budget constraint with any
t\geq 1
. For
K_{1}
and
K_{\infty}
ECE, the corresponding
5.3
becomes a linear program. Since the program has polynomial size and the transformation between the signaling scheme (with the bias assignment) and the predictor is also polynomial-time computable, we obtain
Algorithm
3
, which computes the optimal predictor under the
K_{1}
or
K_{\infty}
ECE budget in polynomial time.
Given the significance of the Bayesian persuasion and information design literature, we believe that our new variant of persuasion problem with signal-dependent bias, together with its results, may be of independent interest.
1.2
Discussions
How to choose ECE budget
\varepsilon
.
In this work, we consider an exogenously given ECE budget
\varepsilon
, under which the agent best responds to predictions as long as they are generated by an
\varepsilon
-calibrated predictor.
A natural question arises: does the agent’s expected utility under the optimal
\varepsilon
-calibrated predictor always weakly decrease as
\varepsilon
increases?
Perhaps a bit surprisingly, the answer is no.
in
Appendix
A
, we provide an example showing that, due to the strategic interaction between the principal and the agent, the agent’s expected utility can increase as the ECE budget
\varepsilon
increases within a certain range.
In fact, the agent’s utility under the optimal
\varepsilon
-calibrated predictor can be strictly higher than under a perfectly calibrated predictor (
\varepsilon=0
).
However, if the ECE budget becomes too large, the agent may begin to doubt the reliability of the predictions and stop treating them as trustworthy predictions.
This introduces a key behavioral dimension to the problem: the appropriate level of calibration error depends not only on optimization or statistical considerations but also on how the agent perceives and responds to prediction quality.
Calibration to achieve weak commitment.
In information design literature, the designer (or sender) can commit ahead of time to a particular signaling or information disclosure policy, and the receiver knows all the details of this information policy and trusts this commitment.
Additionally, agents are assumed to be fully Bayesian and able to perform complex Bayesian reasoning based on any signal they receive.
While elegant in theory, these assumptions are often unrealistic in practice, as they require agents to have perfect knowledge and unlimited computational capacity.
Calibration, by contrast, offers a simpler and more practical alternative.
It can be viewed as a relaxation of both the strong commitment assumption and the demanding cognitive requirements placed on the agent.
Given a pre-specified ECE budget,
the principal does not need to commit to a specific predictor in advance -- she may generate predictions in any manner, as long as the calibration error, evaluated ex ante, remains within the budget.
On the agent’s side, there is no need to know the prior, the predictor details, or to perform Bayesian updates.
The agent simply acts based on the predictions received.
Thus, calibration enables a weaker form of commitment that is more behaviorally and computationally plausible.
6
6
6
Similar discussions between calibration and Bayesian reasoning has also been mentioned in
Collina et al. 2024a
.
As an overarching goal of this work, we seek to establish and encourage future research that bridges the gap between the literature on algorithmic information design and the literature on calibration – two areas that have been extensively studied within the computer science community.
1.3
Open Questions and Future Directions
The persuasive calibration problem studied in this work opens up several interesting directions for future research, some of which we outline below.
Structural characterizations for general utility.
A natural question is whether our structural results characterized in
Section
3
can be (at least partially) extended to more general utility functions.
We conjecture that the miscalibration structure may still hold under broader conditions, although this likely requires a more fine-grained duality-based analysis.
Deterministic predictor.
Throughout the paper, we focus on potentially randomized predictors. While randomization is allowed in our framework,
Proposition
3.3
shows that, conditional on each event, the number of possible predictions is bounded by a constant (at most four).
7
7
7
In fact, we can further strengthen this result: there exists at most one event that can generate four distinct predictions.
These observations suggest that optimal predictors exhibit very limited randomization.
With that being said, it is still interesting to explore the design of the optimal
(\varepsilon,\ell_{t})
-calibrated deterministic predictor, which have been widely adopted in practice.
Extensions with multicalibration, multi-class calibration, and beyond.
Beyond the ECE metric considered in this work, there is a rich body of literature on broader notions of calibration.
We believe that our persuasive calibration framework naturally extends to these settings.
For example, by viewing each event as a data point, and assuming a membership structure among events, multicalibration becomes a more appropriate metric. It would be interesting to extend our results to predictors subject to multicalibration constraints.
In fact, the computational results and the connections to Bayesian persuasion established in
Theorem
5.1
can be extended to the multicalibration setting.
The key difference would be in the receiver’s behavior – defined in
Definition
5.1
– which, under multicalibration, would depend on the group membership of the events.
Moreover, it is also interesting to explore the setting with multi-outcome (i.e., multi-class) calibration. This problem would be particularly technically interesting as predictions must now lie in a high-dimensional simplex.
It closely relates to the high-dimensional information design, a notoriously difficult and unresolved area in the theoretical economics literature.
Lastly, in this work, we focus on a setting where the principal has full knowledge of each event’s true expected outcome. While this is already a foundational setup, a more realistic and practical scenario may involve the principal only observing noisy realizations of outcomes. In such a case, one must design a predictor based on empirical observations, which we leave it as an important direction for future work.
1.4
Additional Related Work
Our work contributes to a growing line of research on calibration in decision-making settings.
Beginning with
Dawid 1982
;
Foster and Vohra 1998
, it is well established that agents who best respond to calibrated predictions (i.e., those with low
K_{1}
ECE) achieve diminishing swap regret.
Recent works have extended this foundation by introducing new decision-theoretic calibration measures that offer finer-grained guarantees on the regret incurred by downstream agents
(
Kleinberg et al. 2023
;
Roth and Shi 2024
;
Hu and Wu 2024
;
Qiao and Zhao 2025
)
.
For example,
Kleinberg et al. 2023
show that
a decision-maker cannot fare worse by trusting well-calibrated predictions – the external regret incurred by best-responding to such predictions is linearly (up to a small factor) bounded by the
K_{1}
ECE.
They introduce “U-Calibration” – a measure bounded by a small constant times the
K_{1}
ECE, and show that sublinear U-Calibration is both
necessary and sufficient for ensuring sublinear regret for all downstream agents.
Roth and Shi 2024
;
Hu and Wu 2024
consider a similar setting but focusing on swap regret.
In particular,
Roth and Shi 2024
show that
by ensuring unbiasedness relative to a carefully chosen collection of events, one can achieve diminishing swap regret for arbitrary downstream agents with an improved rate compared to using calibrated predictions.
Hu and Wu 2024
then introduce “Calibration Decision Loss (CDL)”, defined as the maximum improvement (over all decision tasks) in decision payoff obtainable by recalibrating the predictions.
The show that CDL is upper bounded by twice the
K_{1}
ECE and that a vanishing CDL guarantees vanishing payoff loss from miscalibration across all decision tasks,
which also removes the regret dependence on the number of actions appeared in the results of
Roth and Shi 2024
.
Qiao and Zhao 2025
propose a new calibration measure called “subsampled step calibration”, which has both decision-theoretic implications and a truthfulness property.
Other conceptually related works include
Noarov et al. 2023
;
Haghtalab et al. 2023
who focus on single decision task, and
Camara et al. 2020
;
Collina et al. 2024b
who explore repeated Principal-Agent interactions in a prior-free setting.
Zhao et al. 2021
introduce “decision calibration” that requires the predicted distribution and true distribution to be indistinguishable to a set of downstream decision-makers.
Gopalan et al. 2022
develop an omniprediction framework which aims to design a single predictor that ensures every downstream decision-maker’s loss is no worse than some benchmark family of functions
(
Gopalan et al. 2023
;
Garg et al. 2024
)
.
Guo and Shmaya 2021
analyze a sender-receiver game where the sender, facing miscalibration costs, provides predictions to the receiver; they show that the game’s Nash equilibrium crucially depends on the magnitude of the miscalibration costs.
In contrast to these works, which primarily adopt a worst-case regret minimization framework and aim to achieve robustness against all decision tasks, our work focuses on characterizing the structure and algorithmic properties of the optimal predictor.
In addition, many of the aforementioned works consider a specific principal’s goal – aiming to minimize regret across all downstream agents.
By contrast, our framework accommodates arbitrary misaligned incentives between the principal and the agent.
In this work, we adopt the
\ell_{t}
-norm ECE as a framework to ensure the predictions to be trustworthy to the agents.
This
\ell_{t}
-norm calibration metric is broadly accepted in the forecasting community
Dawid 1982
;
Foster and Vohra 1998
;
Gneiting et al. 2007
;
Ranjan and Gneiting 2010
, within theoretical computer science (see, e.g.,
Qiao and Valiant 2021
;
Dagan et al. 2024
;
Casacuberta et al. 2024
), empirical machine learning community (see, e.g.,
Gneiting and Katzfuss 2014
;
Rahaman et al. 2021
).
Beyond
\ell_{t}
-norm ECE and the above mentioned decision-driven calibration metrics, other calibration measures have been proposed to capture different desired aspects, e.g., the multicalibration
(
Hébert-Johnson et al. 2018
;
Garg et al. 2024
)
, multi-class calibration
(
Gopalan et al. 2024
)
, distance to calibration
(
Błasiok et al. 2023
;
Qiao and Zheng 2024
;
Arunachaleswaran et al. 2025
)
.
2
Preliminaries
In this work, we introduce and study the
“persuasive calibration”
problem between a principal and a downstream decision-maker. Below, we outline the key components of our model.
Environment.
Consider a stochastic environment that randomly generates an
event
from a finite set of
n
events indexed by
[n]\triangleq\{1,2,\dots,n\}
.
8
8
8
Equivalently, event distribution
\lambda
can be viewed as the a continuum population of events.
We denote by
\lambda_{i}\in[0,1]
the probability of event
i
, satisfying
\sum_{i\in[n]}\lambda_{i}=1
. Once an event is realized, it further induces a randomized
binary outcome
. Specifically, for each event
i\in[n]
, the binary outcome
y\in\mathcal{Y}\triangleq\{0,1\}
is drawn from a Bernoulli distribution with mean
\theta_{i}\in[0,1]
. Without loss of generality, we assume that the events are sorted in non-decreasing order of their Bernoulli means:
\theta_{1}\leq\theta_{2}\leq\dots\leq\theta_{n}
.
There is a
principal
(she) and a downstream decision-maker (he), referred to as the
agent
. The principal observes the realized event
i
but not the final binary outcome
y
, while the agent observes neither the event nor the outcome.
We detail the interaction between the principal and the agent below.
Calibrated predictors.
The principal provides predictions of the final binary outcome (which is unknown to both herself and the agent) to the agent, who then makes a decision that affects the payoffs of both the principal and himself. A
prediction
p\in[0,1]
is a scalar indicating the probability that the binary outcome is one. The principal’s predictions are generated by a (possibly randomized)
predictor
\tilde{f}=\{\tilde{f}_{i}\}_{i\in[n]}
, which specifies a profile of
n
conditional distributions.
9
9
9
Since the principal observes the realized event
i
but not the outcome
y
, her predictor is a function of the realized event that does not depend on the outcome.
Specifically, for each event
i
, the conditional predictor
\tilde{f}_{i}
represents the distribution over predictions given that event
i
occurs. We define the conditional prediction space
\mathsf{supp}(\tilde{f}_{i})
as the support of conditional distribution
\tilde{f}_{i}
and (unconditional) prediction space
\mathsf{supp}(\tilde{f})\triangleq\cup_{i\in[n]}\mathsf{supp}(\tilde{f}_{i})
. With slight abuse of notation, we use
\tilde{f}_{i}(p)
to denote the probability mass (or probability density if
\mathsf{supp}(\tilde{f}_{i})
is continuous) of generating prediction
p
when event
i
is realized.
10
10
10
While predictors with continuous prediction space are considered, our results show that there exists optimal predictors with finite prediction space.
We are also interested in the
marginalized predictor
, denoted by
f\in\Delta([0,1])
, which marginalizes the predictor
\tilde{f}
over the events. Specifically, we define
f(p)\triangleq\sum_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)
to represent the marginal probability of generating the prediction
p
.
The predictor provided by the principal is required to be
trustworthy
. In our model, the trustworthiness of predictors follows the calibration framework: given a fixed predictor
\tilde{f}
, for every prediction
p\in\mathsf{supp}(\tilde{f})
, we denote by
\kappa(p)\triangleq\mathbb{E}\!\left[{y\,\mid\,p}\right]
the
true expected outcome
conditional on the realized prediction
p
, where the randomness is taken over event and outcome. Since the outcome is binary, it also represents the true probability that binary outcome is one, conditional on the realized prediction
p
. As a sanity check, if the prediction space
\mathsf{supp}(p)
is discrete, the true expected outcome
\kappa(p)
can be expressed according to Bayes’ rule as
\displaystyle\kappa(p)\triangleq\mathbb{E}\!\left[{y\,\mid\,p}\right]=\frac{\sum_{i\in[n]}\lambda_{i}\cdot\tilde{f}_{i}(p)\cdot\theta_{i}}{\sum_{i\in[n]}\lambda_{i}\cdot\tilde{f}_{i}(p)}
(1)
A predictor
\tilde{g}
is
perfectly calibrated
if, for every prediction
q\in\mathsf{supp}(\tilde{g})
, the true expected outcome
\kappa(q)
equals the prediction itself, i.e.,
\kappa(q)=q
.
11
11
11
Throughout the paper, we use
\tilde{g}
to denote a perfectly calibrated predictor and
\tilde{f}
to denote a general (possibly imperfectly calibrated) predictor. Similarly, we use
q
to denote the prediction generated by perfectly calibrated predictors and
p
to denote the prediction generated by general (possibly imperfectly calibrated) predictors.
For illustration,
Example
2.1
presents two distinct perfectly calibrated predictors.
Example 2.1
(Perfect calibration)
.
Suppose there are
n=2
events with
\lambda_{1}=\lambda_{2}=0.5
and
\theta_{1}=0.3,\theta_{2}=0.9
. Two perfectly calibrated predictors
\tilde{g}^{\dagger}
and
\tilde{g}^{\ddagger}
can be constructed as follows:
•
In the first predictor
\tilde{g}^{\dagger}
, deterministic prediction
q=0.6
is generated regardless of the realized event. Specifically,
\tilde{g}_{i}^{\dagger}(q)\triangleq\mathbf{1}\!\left\{{q=0.6}\right\}
for both
i\in[2]
.
12
12
12
We use
\mathbf{1}\!\left\{{\cdot}\right\}
to denote the indicator function.
Note that the ex ante probability of outcome being one is
0.5\cdot 0.3+0.5\cdot 0.9=0.6
. Hence, the construction ensures that
\kappa(0.6)=0.6
and thus predictor
\tilde{g}^{\dagger}
is perfectly calibrated.
•
In the second predictor
\tilde{g}^{\ddagger}
, prediction
q=\theta_{i}
is generated when event
i
is realized. Specifically,
\tilde{g}_{i}^{\ddagger}(q)\triangleq\mathbf{1}\!\left\{{q=\theta_{i}}\right\}
for both
i\in[2]
. By construction, predictor
\tilde{g}^{\ddagger}
is also perfectly calibrated.
We adopt the standard
\ell_{t}
-norm expected calibration error metric to quantify the deviation of a predictor from being perfectly calibrated.
Definition 2.2
(Expected calibration error)
.
Fix any
t\in[1,\infty)
. The
\ell_{t}
-norm expected calibration error
(
ECE
)
\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]
of predictor
\tilde{f}
is
\displaystyle\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\triangleq\left(\mathbb{E}\!\left[{\left|\kappa(p)-p\right|^{t}}\right]\right)^{\frac{1}{t}}~,
where the expectation is taken over the randomness of both the event and the prediction. Similarly, the
\ell_{\infty}
-norm ECE
of predictor
\tilde{f}
is
{\text{\bf ECE}_{\infty}\!\left[{\tilde{f}}\right]\triangleq\max\nolimits_{p\in\mathsf{supp}(\tilde{f})}~|\kappa(p)-p|}
.
Given any
\varepsilon\geq 0
and
t\geq 1
,
we say a predictor
\tilde{f}
is
(\varepsilon,\ell_{t})
-calibrated
if its
\ell_{t}
-norm ECE is at most
\varepsilon
, i.e.,
\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\leq\varepsilon
. We refer to
\varepsilon
as the
ECE budget
, and denote by
\mathcal{F}_{(\varepsilon,\ell_{t})}\triangleq\{\tilde{f}:\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\leq\varepsilon\}
the space of all
(\varepsilon,\ell_{t})
-calibrated predictors. Note that when the
ECE budget
is set to zero, the
(0,\ell_{t})
-calibration recovers perfect calibration for all
\ell_{t}
norms. Thus, we write
\mathcal{F}_{0}\equiv\mathcal{F}_{(0,\ell_{t})}
.
Among all
\ell_{t}
-norm ECEs, the most classic and important one is the
\ell_{1}
-norm ECE, also known as the
K_{1}
ECE. Additionally, the
\ell_{2}
-norm ECE and
\ell_{\infty}
-norm ECE, referred to as the
K_{2}
and
K_{\infty}
ECEs, respectively, are also standard in the literature and commonly used in practice. While our results apply to general
\ell_{t}
-norm ECEs, more refined and improved results are derived for these classic ECEs, particularly the
K_{1}
ECE.
When
\ell_{t}
norm is clear from the context, we sometimes simplify notations and omit them, e.g., writing
\text{\bf ECE}\!\left[{\tilde{f}}\right]
,
\mathcal{F}_{\varepsilon}
instead of
\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]
,
\mathcal{F}_{(\varepsilon,\ell_{t})}
, and saying
\varepsilon
-calibrated instead of
(\varepsilon,\ell_{t})
-calibrated.
Example 2.3
(
\varepsilon
-calibrated predictor)
.
Consider the same two-event setting as in
Example
2.1
and two predictors,
\tilde{f}^{\dagger}
and
\tilde{f}^{\ddagger}
, constructed as follows:
•
In the first predictor
\tilde{f}^{\dagger}
, the deterministic prediction
p=0.4
is generated regardless of the realized event. Specifically,
\tilde{f}^{\dagger}_{i}(p)=\mathbf{1}\!\left\{{p=0.4}\right\}
for both
i\in[2]
. For all
t\geq 1
, its
\ell_{t}
-norm ECEs are identical and equal to
\text{\bf ECE}_{t}\!\left[{\tilde{f}^{\dagger}}\right]=0.2
.
•
In the second predictor
\tilde{f}^{\dagger}
, predictions
p=0.4
and
p=0.7
are generated under events 1 and 2, respectively. Specifically,
\tilde{f}^{\ddagger}_{1}(p)=\mathbf{1}\!\left\{{p=0.4}\right\}
and
\tilde{f}^{\ddagger}_{2}(p)=\mathbf{1}\!\left\{{p=0.7}\right\}
. For this predictor, the
K_{1}
,
K_{2}
and
K_{\infty}
ECEs are
\text{\bf ECE}_{1}\!\left[{\tilde{f}^{\ddagger}}\right]=0.15
,
\text{\bf ECE}_{2}\!\left[{\tilde{f}^{\ddagger}}\right]=\sqrt{0.025}\approx 0.158
,
\text{\bf ECE}_{\infty}\!\left[{\tilde{f}^{\ddagger}}\right]=0.2
, respectively.
Agent’s problem.
The agent (downstream decision-maker) has a finite set of actions, denoted by
\mathcal{A}
with
m\triangleq|\mathcal{A}|
. His utility function is given by
v(\cdot,\cdot):\mathcal{A}\times\mathcal{Y}\rightarrow\mathbb{R}
, which depends on both the chosen action and the binary outcome of the event.
13
13
13
Notably, the agent’s utility does not depend on the event, while the principal’s utility may depend on the event, besides the agent’s action and the binary outcome.
We use
v(a,y)
to denote the agent’s utility when he takes action
a\in\mathcal{A}
and the outcome
y\in\mathcal{Y}
is realized.
The agent has no knowledge of the environment, the realized outcome, or the details of the predictor. He can only use the realized prediction
p
generated by the principal’s predictor to inform his decision.
Knowing that the predictions are generated by a predictor with small calibration error, the agent
trusts
the principal’s prediction
p
and chooses the action that maximizes his expected utility assuming the outcome is equal to one with probability
p
.
14
14
14
The behavior of agent directly best responding to the provided predictions that are generated from a low-ECE predictor has been widely adopted and considered in calibration literature, see, e.g.,
Haghtalab et al. 2023
;
Garg et al. 2024
;
Kleinberg et al. 2023
;
Hu and Wu 2024
;
Roth and Shi 2024
;
Qiao and Zhao 2025
.
More formally, for any prediction
p
generated by an
\varepsilon
-calibrated predictor
\tilde{f}
, the agent takes the action
a^{*}(p)\in\mathcal{A}
that satisfies
15
15
15
Following the literature, we assume the agent breaks ties in favor of the principal when he faces indifferent actions.
As a result, the principal’s indirect utility function under each event preserves the upper-semi continuity. This property guarantees the principal’s problem always feasible.
\displaystyle a^{*}(p)\in\argmax\nolimits_{a\in\mathcal{A}}~\mathbb{E}_{y\sim\mathsf{Bern}(p)}\!\left[{v(a,y)}\right]=\argmax\nolimits_{a\in\mathcal{A}}~p\cdot v(a,1)+(1-p)\cdot v(a,0)
(2)
Principal’s problem.
The principal’s utility depends on the agent’s action, the realized outcome, and the realized event. Specifically, for each event
i\in[n]
, agent’s action
a\in\mathcal{A}
, and outcome
y\in\mathcal{Y}
, we denote the principal’s utility by
u_{i}(a,y){\in\mathbb{R}^{+}}
.
16
16
16
Throughout the paper, we consider non-negative principal’s utility, and we do not make any other assumptions unless explicitly stated.
To simplify the presentation, we also introduce the
indirect utility function
U_{i}
, which maps a given prediction
p
to the principal’s expected utility when the agent selects his best action
a^{*}(p)
upon the realization of event
i
.
Definition 2.4
(Indirect utility)
.
For each event
i\in[n]
and prediction
p\in\mathsf{supp}(\tilde{f})
, the principal’s
indirect utility
is
U_{i}(p)\triangleq\theta_{i}\cdot u_{i}(a^{*}(p),1)+(1-\theta_{i})\cdot u_{i}(a^{*}(p),0)
, where
a^{*}(p)
is defined in Eqn. (
2
).
17
17
17
Notably, when the principal evaluates her indirect utility
U_{i}(p)
, the outcome follows the Bernoulli distribution with mean
\theta_{i}
instead of prediction
p
.
Given a predictor
\tilde{f}
, the principal’s expected utility is expressed as
18
18
18
When
\tilde{f}_{i}
is continuous, the inner summation in the expression of
\text{\bf Payoff}\!\left[{\tilde{f}}\right]
becomes integral, i.e.,
\int_{0}^{1}\lambda_{i}\cdot\tilde{f}_{i}(p)\cdot U_{i}(p)\,{\mathrm{d}}p
. To avoid redundancy, in the remainder of the paper, we present formulas for either the continuous or discrete distribution, as the analogous version can be easily derived.
\displaystyle\text{\bf Payoff}\!\left[{\tilde{f}}\right]
\displaystyle\triangleq\mathbb{E}_{i\sim\lambda,p\sim\tilde{f}_{i},y\sim\mathsf{Bern}(\theta_{i})}\!\left[{u_{i}(a^{*}(p),y)}\right]=\sum\nolimits_{i\in[n]}\sum\nolimits_{p\in\mathsf{supp}(\tilde{f}_{i})}\lambda_{i}\cdot\tilde{f}_{i}(p)\cdot U_{i}(p)
where the second equality holds due to the definition of the indirect utility.
Fixing an exogenously given
ECE budget
\varepsilon
and
\ell_{t}
-norm calibration error, we say an
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}^{*}
is
optimal
if it maximizes the principal’s expected utility among all
(\varepsilon,\ell_{t})
-calibrated predictors, i.e.,
\displaystyle\tilde{f}^{*}\in\argmax\nolimits_{\tilde{f}\in\mathcal{F}_{(\varepsilon,\ell_{t})}}~\text{\bf Payoff}\!\left[{\tilde{f}}\right]
We use the tuple
(\Theta,\lambda,u,v,\mathcal{A},(\varepsilon,\ell_{t}))
to refer to as a persuasive calibration instance, where
\Theta=\{\theta_{i}\}_{i\in[n]}
represents the profile of expected outcomes for all events.
Timeline.
We formalize the timeline of the model as follows:
1.
The principal designs a
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}
.
19
19
19
Note the ECE of a predictor is evaluated ex ante, thus, it does not matter when the principal determines the predictor details.
2.
A randomized event
i\in[n]
is realized with probability
\lambda_{i}
, and
a (randomized) prediction
p
is sent to the agent according to the conditional distribution
\tilde{f}_{i}(\cdot)
.
3.
The agent selects his best action
a^{*}(p)
as defined in Eqn. (
2
).
4.
The binary outcome
y
is realized from a Bernoulli distribution with mean
\theta_{i}
. The principal and the agent receive utilities
u_{i}(a^{*}(p),y)
and
v(a^{*}(p),y)
, respectively.
3
Structural Characterization for the Event-Independent Setting
In this section, we focus on the
event-independent setting
, where the principal’s indirect utility does not depend on the realized event. Specifically, we assume that
U_{i}(p)\equiv U_{j}(p)
for all events
i,j\in[n]
and predictions
p\in[0,1]
.
20
20
20
Such event-independent indirect utility assumptions are standard and widely studied in the algorithmic game theory and economics literature
(
Dworczak and Martini 2019
;
Lipnowski and Ravid 2020
;
Feng et al. 2022
;
Arieli et al. 2023
;
Corrao and Dai 2023
;
Feng et al. 2024
, e.g.,)
. In our model, it is equivalent to assume the principal’s utility
u
does not depend on the event and outcome.
Within this section, we omit the subscript
i
in the principal’s indirect utility function, i.e., write
U(p)
instead of
U_{i}(p)
.
In
Section
3.1
, we focus on the
\ell_{1}
-norm ECE (a.k.a.,
K_{1}
calibration error) and present the structural characterization of the optimal
\varepsilon
-calibrated predictor.
In
Section
3.2
, we introduce a two-step framework for generating
(\varepsilon,\ell_{t})
-calibrated predictors for general
t\geq 1
.
Our proofs, provided in
Section
3.3
, for the structural characterization of the optimal
\varepsilon
-calibrated predictor heavily relies on the this two-step framework with a dual-based approach.
3.1
Structural Results for Optimal
(\varepsilon,\ell_{1})
-Calibrated Predictor
In this section, we focus on the
\ell_{1}
-norm ECE, which is the most classic and important calibration error definition, and we present the structural characterization of the optimal
(\varepsilon,\ell_{1})
-calibrated predictor. All the proofs are deferred to
Section
3.3
.
Except for the theorem statements, we omit
\ell_{1}
for the presentation simplicity in this subsection.
We first introduce the following concepts of under-confidence and over-confidence, which are introduced and observed in the machine learning literature
(
Guo et al. 2017
;
Kuleshov et al. 2018
;
Fan et al. 2023
, e.g.,)
.
Definition 3.1
(Under-/over-confidence)
.
Fix any predictor
\tilde{f}
. A prediction
p\in\mathsf{supp}(\tilde{f})
is
under-confident
(resp.
over-confident
,
perfectly calibrated
) if
p\leq\kappa(p)
(resp.
p\geq\kappa(p)
,
p=\kappa(p)
), where
\kappa
is the true expected outcome function of predictor
\tilde{f}
defined in Eqn. (
1
).
We now present the main structural characterization of the optimal predictor.
21
21
21
Theorem
3.1
and its analysis also holds when there is continuum population of events.
Theorem 3.1
(Structure of optimal
\varepsilon
-calibrated predictor)
.
For every persuasive calibration instance in the event-independent setting, there exists
0\leq p_{\mathsf{L}}\leq p_{\mathsf{H}}\leq 1
that partitions
the prediction space
[0,1]
into
under-confidence interval
[0,p_{\mathsf{L}}]
,
perfectly calibrated internal
[p_{\mathsf{L}},p_{\mathsf{H}}]
, and
over-confidence
interval
[p_{\mathsf{H}},1]
. Then, there exists an optimal
(\varepsilon,\ell_{1})
-calibrated predictor
\tilde{f}^{*}
that satisfies the following three properties:
(1)
(Miscalibration Structure)
Every prediction
p
in the under-confidence interval (resp. over-confidence interval, perfectly calibrated interval) is under-confident (resp. over-confident, perfectly calibrated), i.e.,
\displaystyle\begin{array}[]{ll}\forall p\in\mathsf{supp}(\tilde{f}^{*})\cap[0,p_{\mathsf{L}}]:&\quad p\leq\kappa(p)\\
\forall p\in\mathsf{supp}(\tilde{f}^{*})\cap[p_{\mathsf{L}},p_{\mathsf{H}}]:&\quad p=\kappa(p)\\
\forall p\in\mathsf{supp}(\tilde{f}^{*})\cap[p_{\mathsf{H}},1]:&\quad p\geq\kappa(p)\end{array}
(2)
(Payoff Structure-I)
There exists a function
\xi:\mathsf{supp}(\tilde{f}^{*})\rightarrow\mathbb{R}
that selects a subgradient at each prediction
p\in\mathsf{supp}(\tilde{f}^{*})
, i.e.,
\xi(p)\in\partial U(p)
, such that function
\xi
is increasing, and it satisfies
\xi(p)\equiv\alpha
for all predictions in over-confidence interval, and
\xi(p)\equiv-\alpha
for all predictions in under-confidence interval for some
\alpha\geq 0
.
(3)
(Payoff Structure-II)
All points
(p,U(p))_{p\in\mathsf{supp}(\tilde{f}^{*})}
form a convex function.
Moreover, points
(p,U(p))
for all predictions in over-confidence interval are collinear (with slope
\alpha
), and points
(p,U(p))
for all predictions in under-confidence interval are collinear (with slope
-\alpha
).
Implications on the miscalibration of neural networks.
Theorem
3.1
sheds light on a well-observed phenomenon in the machine learning community: the miscalibration of modern neural networks.
It is well-known that neural networks have been found to be poorly calibrated.
For example, in the seminal prior work,
Guo et al. 2017
show that uncalibrated ResNet tends to be overconfident in its predictions (see Figure 4 in
Guo et al. 2017
), and
Kuleshov et al. 2018
show that the neural networks consistently generate underestimated and overestimated predictions/forecasts at the two extremes of the probability spectrum (see Figures 2 and 3 in
Kuleshov et al. 2018
).
Our framework provides a theoretical explanation for this behavior.
Specifically, the principal’s problem can be viewed as minimizing a particular loss function.
The miscalibration structure established in
Theorem
3.1
implies that, whenever there exist calibration errors in the output predictions, they must consistently occur in the tails of the prediction spectrum.
That is, there exist
p_{\mathsf{L}}\leq p_{\mathsf{H}}
such that the model underestimates probabilities in the under-confidence interval
[0,p_{\mathsf{L}}]
and overestimates them in the over-confidence interval
[p_{\mathsf{H}},1]
, no matter what the loss function is.
This structural insight aligns closely with empirical observations in machine learning.
Although we acknowledge that here we simplify the principal’s utility function to be event-independent, it may not fully capture all loss functions that are being considered in training neural networks, we conjecture that our findings can be generalized to more complex utility functions (see
Section
1.2
for more detailed discussions).
Interpretation of the payoff structure.
Theorem
3.1
also provides insights into the principal’s indirect utility and its corresponding derivative (or subgradient if the derivative does not exist) for predictions generated by the optimal predictor. Specifically, the “per-unit” indirect utility derived from predictions in the under-confidence interval
[0,p_{\mathsf{L}}]
and over-confidence interval
[p_{\mathsf{H}},1]
is higher than the “per-unit” indirect utility derived from predictions in the perfectly calibrated interval
[p_{\mathsf{L}},p_{\mathsf{H}}]
. This aligns with the intuition that the optimal predictor is willing to incur ECE to generate predictions with higher payoff. Furthermore, our result suggests that the marginal indirect utility is the same for all predictions in the under-confidence interval
[0,p_{\mathsf{L}}]
and the over-confidence interval
[p_{\mathsf{H}},1]
, and is larger than that for predictions in the perfectly calibrated interval
[p_{\mathsf{L}},p_{\mathsf{H}}]
.
We now illustrate
Theorem
3.1
with two examples.
Example
3.2
considers instances where the agent has binary actions.
Example
3.3
considers instances where the principal’s indirect utility function
U
follows an S-shaped curve (i.e., first convex then concave). Both setups are widely studied in the literature
(
Dughmi and Xu 2017
;
Babichenko and Barman 2017
;
Xu 2020
;
Feng et al. 2022
;
Feng et al. 2024
;
Kolotilin et al. 2024
, e.g.,)
.
Example 3.2
(Binary-action setting)
.
Consider a persuasive calibration instance where the agent has binary actions (i.e.,
\mathcal{A}=\{0,1\}
) and the principal has utility function
u_{i}(a,y)\equiv a
(i.e., always preferring the agent taking action 1). Let
p^{\dagger}\in[0,1]
be the prediction such that the agent is indifferent between two actions. Suppose the agent takes action 1, i.e.,
a^{*}(p)=1
, for every prediction
p\geq p^{\dagger}
.
Let
\bar{\theta}\triangleq\mathbb{E}_{i\in\lambda}\!\left[{\theta_{i}}\right]
be the ex ante expected outcome.
The optimal
\varepsilon
-calibrated predictor
\tilde{f}^{*}
satisfying properties in
Theorem
3.1
has the following two cases:
Case 1. Low ECE budget
\varepsilon
i^{\dagger}
, predictor
\tilde{f}^{*}
generates a deterministic but over-confident prediction
p=p^{\dagger}
. Finally, for the threshold event
i^{\dagger}
, predictor
\tilde{f}^{*}
generates an over-confident prediction
p=p^{\dagger}
with probability
{(\varepsilon-\sum_{i\in[i^{\dagger}+1:n]}\lambda_{i}(p^{\dagger}-\theta_{i}))}{(\lambda_{i^{\dagger}}(p^{\dagger}-\theta_{i^{\dagger}}))^{-1}}
and a
perfectly calibrated prediction
p=\theta_{i^{\dagger}}
with the remaining probability. The construction of the threshold event
i^{\dagger}
and its prediction distribution ensures that the predictor
\tilde{f}^{*}
fully exhausts the ECE budget, i.e.,
\text{\bf ECE}\!\left[{\tilde{f}^{*}}\right]=\varepsilon
.
Case 2. High ECE budget
\varepsilon\geq p^{\dagger}-\bar{\theta}
.
In this case, the optimal
\varepsilon
-calibrated predictor generates a deterministic (but possibly over-confident) prediction
p=\max\{\bar{\theta},p^{\dagger}\}
regardless of the realized event. Its induced ECE budget is
\text{\bf ECE}\!\left[{\tilde{f}}\right]=\max\{p^{\dagger}-\bar{\theta},0\}
.
Example 3.3
(S-shaped indirect utility)
.
Consider a persuasive calibration instance where the principal’s has an event-independent S-shaped (i.e., first convex then concave) indirect utility function
U
. For simplicity, we assume function
U
is differentiable with
\partial U(0)=\partial U(1)=0
and
U(0)i^{\dagger}
, predictor
\tilde{f}^{*}
generates a deterministic but over-confident prediction
p=p^{\dagger}
. Finally, for the threshold event
i^{\dagger}
, predictor
\tilde{f}^{*}
generates an over-confident prediction
p=p^{\dagger}
with probability
t
and a
perfectly calibrated prediction
p=\theta_{i^{\dagger}}
with the remaining probability. The construction of the threshold event
i^{\dagger}
and its prediction distribution ensures that the predictor
\tilde{f}^{*}
fully exhausts the ECE budget, i.e.,
\text{\bf ECE}\!\left[{\tilde{f}^{*}}\right]=\varepsilon
. Also see
Figure
2
for an illustration.
Case 2. High ECE budget
\varepsilon\geq 1-\bar{\theta}
.
In this case, the optimal
\varepsilon
-calibrated predictor generates a deterministic (but possibly over-confident) prediction
p=1
regardless of the realized event. Its induced ECE budget is
\text{\bf ECE}\!\left[{\tilde{f}}\right]=1-\bar{\theta}
.
Graphical characterization of the optimal predictor.
Theorem
3.1
and its analysis also admit a graphical interpretation as follows.
Definition 3.4
(Symmetric linear-tailed convex function)
.
A function
\Gamma:[0,1]\rightarrow\mathbb{R}
is symmetric linear-tailed convex if it is convex, and there exists
0\leq x_{\mathsf{L}}\leq x_{\mathsf{H}}\leq 1
such that (i)
\Gamma
is linear on both intervals
[0,x_{\mathsf{L}}]
and
[x_{\mathsf{H}},1]
; and (ii) the absolute values of the slopes of these linear parts are equal.
We refer to the intervals
[0,x_{\mathsf{L}}]
and
[x_{\mathsf{H}},1]
as the
linear tails
of the function
\Gamma
.
Proposition 3.2
.
For every persuasive calibration instance in the event-independent setting,
fix an optimal
(\varepsilon,\ell_{1})
-calibrated predictor
\tilde{f}^{*}
satisfying the properties in
Theorem
3.1
. There exists a symmetric linear-tailed convex function
\Gamma:[0,1]\rightarrow\mathbb{R}
such that
(i)
\Gamma(p)\geq U(p)
for all
p\in[0,1]
;
(ii)
\mathsf{supp}(\tilde{f}^{*})\subseteq\{p\in[0,1]:\Gamma(p)=U(p)\}
;
(iii) it is linear over
[0,p_{\mathsf{L}}]
and
[p_{\mathsf{H}},1]
.
As we will show in
Section
3.3
, the symmetric linear-tailed convex function
\Gamma
and its properties in
Proposition
3.2
are derived from the optimal dual solution of a linear program
3.7
that characterizes the optimal predictor.
In
Figure
1
, we illustrate the optimal predictor characterized in
Theorem
3.1
along with the corresponding symmetric linear-tailed convex function
\Gamma
from
Proposition
3.2
. When the principal’s indirect utility function is general, as shown in
Figure
1
, we observe the (non-degenerate) under-confidence, perfectly calibrated, and over-confidence intervals structure. The symmetric linear-tailed convex function
\Gamma
exhibits linear tails at both ends, covering the under-confidence and over-confidence intervals.
In contrast, as illustrated in
Example
3.3
, when the principal’s indirect utility function follows an S-shaped structure, the optimal predictor only miscalibrates at the highest prediction. Consequently, in
Figure
2
, the under-confidence interval degenerates, and the symmetric linear-tailed convex function
\Gamma
retains only a single linear tail, corresponding to the over-confidence interval.
p_{\mathsf{H}}
x_{\mathsf{H}}
(a)
p_{\mathsf{H}}
\kappa(p)
(b)
Figure 2
:
Illustration of the principal with a S-shaped indirect utility (
Example
3.3
).
In both figures, blue dots are the predictions
p
generated from the optimal predictor
\tilde{f}^{*}
,
brown squares are the corresponding true expected outcomes
\kappa(p)
conditional on the prediction
p
.
Figure
1(a)
is an illustration of
Theorem
3.1
– black solid curve is indirect utility
U
and blue curve is the convex function
\Gamma
in
Proposition
3.2
.
Figure
1(b)
is the reliable diagram – black solid line is diagonal line.
In
Examples
3.2
and
3.3
, we observe that the number of predictions used in the optimal predictor scales linearly with the number of events, while the number of predictions generated for each realized event remains constant. The following proposition formally establishes that both observations hold for all persuasive calibration instances in the event-independent setting.
Proposition 3.3
(How many predictions are necessary?)
.
For every persuasive calibration instance in the event-independent setting,
there exists an optimal
(\varepsilon,\ell_{1})
-calibrated predictor
\tilde{f}^{*}
satisfying all structures in
Theorem
3.1
, such that
(i)
(Total predictions)
The total number of predictions induced by the optimal predictor
\tilde{f}^{*}
is at most
n+2
, i.e.,
|\mathsf{supp}(\tilde{f}^{*})|\leq n+2
, where
n
is the number of events.
(ii)
(Predictions per event)
For each event
i\in[n]
, the number of predictions induced by the optimal predictor
\tilde{f}^{*}
for this event is at most 4, i.e.,
|\mathsf{supp}(\tilde{f}^{*}_{i})|\leq 4
.
(iii)
(Predictions per true expected outcome)
For every true expected outcome
q\in[0,1]
, the number of predictions which are induced by the optimal predictor
\tilde{f}^{*}
and have true expected outcome
q
is at most 2, i.e.,
|\kappa^{-1}(q)|\leq 2
.
24
24
24
Given any predictor
\tilde{f}
, the inverse of true expected outcome function
\kappa^{-1}
is defined as
\kappa^{-1}(q)\triangleq\{p\in\mathsf{supp}(\tilde{f}):\kappa(p)=q\}
.
Moreover, if the equality holds (i.e.,
|\kappa^{-1}(q)|=2
), at least one prediction
p\in\kappa^{-1}(q)
belongs to the under-confidence
[0,p_{\mathsf{L}}]
or over-confidence interval
[p_{\mathsf{H}},1]
of
\tilde{f}^{*}
, i.e.,
p\in[0,p_{\mathsf{L}}]\cup[p_{\mathsf{H}},1]
.
The following example shows that the Statement (i) in above
Proposition
3.3
is indeed tight.
Example 3.5
.
Given an ECE budget
\varepsilon>0
with
\varepsilon<0.05
,
consider a two-event setting where
\theta_{1}=0.1,\theta_{2}=0.9
with
\lambda_{1}=\lambda_{2}=0.5
, and the principal’s indirect utility is
U(p)=\mathbf{1}\!\left\{{p=\theta_{1}-0.5\varepsilon}\right\}+2\cdot\mathbf{1}\!\left\{{p=\theta_{1}-2\varepsilon}\right\}+\mathbf{1}\!\left\{{p=\theta_{2}+0.5\varepsilon}\right\}+2\cdot\mathbf{1}\!\left\{{p=\theta_{2}+2\varepsilon}\right\}
.
The optimal
\varepsilon
-calibrated predictor
\tilde{f}^{*}
is unique and it is
\tilde{f}^{*}_{1}(\theta_{1}-0.5\varepsilon)=\tilde{f}^{*}_{2}(\theta_{2}+0.5\varepsilon)=\frac{2}{3}
and
\tilde{f}^{*}_{1}(\theta_{1}-2\varepsilon)=\tilde{f}^{*}_{2}(\theta_{2}+2\varepsilon)=\frac{1}{3}
.
Namely, we have
\mathsf{supp}(\tilde{f}^{*})=4=n+2
.
25
25
25
For readers who are familiar with information design literature, it is well-known that the number of necessary signals in optimal signaling scheme in Bayesian persuasion is not larger than the number of events. Our example here shows a strict separation between our persuasive calibration problem and the canonical Bayesian persuasion problem.
We conclude this subsection by noting that the proofs of all results are provided in
Section
3.3
. In the next subsection, we introduce a general framework that serves as the foundation for our proofs.
3.2
Two-Step Framework to Generate
\varepsilon
-Calibrated Predictors
In this section, we provide a systematic way for the principal to design and analyze the predictor. At a high level, the process consists of two steps. First, a perfectly calibrated predictor is constructed. Second, we apply a simple transformation from this perfectly calibrated predictor to obtain an
\varepsilon
-calibrated predictor.
26
26
26
All results and discussions in
Section
3.2
apply to all
\ell_{t}
-norm ECEs. Thus, except for the theorem statements, we omit
\ell_{t}
for simplicity in this subsection.
As we will illustrate in later sections, this two-step framework and its generalization play an important role in computing and analyzing the optimal
\varepsilon
-calibrated predictor.
Our two-step framework relies on the
post-processing plan
defined as follow:
Definition 3.6
(Event-independent post-processing plan)
.
An
(event-independent) post-processing plan
\chi
is a joint distribution over
[0,1]\times[0,1]
. We denote by
\chi(q,p)
the probability density (or probability mass for discrete distribution) of
(q,p)\in[0,1]^{2}
.
Fix any perfectly calibrated predictor
\tilde{g}
and any
t\geq 1,\varepsilon\geq 0
. A post-processing plan
\chi
is
feasible
under perfectly calibrated predictor
\tilde{g}
and
\ell_{t}
-norm
ECE budget
\varepsilon
if it satisfies
\displaystyle\left(\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot|q-p|^{t}~{\mathrm{d}}p{\mathrm{d}}q\right)^{\frac{1}{t}}\leq\varepsilon
(
Calibration-Feasibility
)
\displaystyle\forall q\in[0,1]:\quad
\displaystyle\int_{0}^{1}\chi(q,p)~{\mathrm{d}}p=g(q)
(
Supply-Feasibility
)
where
g
is marginalized predictor induced by
\tilde{g}
, defined as
g(q)\triangleq\sum_{i\in[n]}\lambda_{i}\tilde{g}_{i}(q)
for every
q\in\mathsf{supp}(\tilde{g})
.
When
\tilde{g},t,\varepsilon
are clear from the context, we simply refer to
\chi
as a feasible post-processing plan.
Intuitively, one can view the post-processing plan
\chi
as a joint distribution over the prediction
q\in\mathsf{supp}(\tilde{g})
and the prediction
p
that
“miscalibrates”
the true expected outcome
q
to be
p
.
We say that
\chi
is event-independent because this joint distribution does not depend on the realized event. We formalize this intuition through the following concept of a
post-processing procedure
. We also illustrate it using
Example
3.8
.
27
27
27
In fact, due to
Supply-Feasibility
and
Lemma
3.8
, a perfectly calibrated predictor
\tilde{g}
can be determined by a feasible post-processing plan
\chi
. Hence, such a post-processing plan
\chi
is sufficient to generate an imperfectly calibrated predictor via
Definition
3.7
. Nevertheless, we choose to explicitly express the perfectly calibrated predictor
\tilde{g}
(or its marginalized version,
g
), as it reveals useful structural properties–such as the MPC representation in
Definition
3.10
and
Lemma
3.8
–which play an important role in our analysis.
Definition 3.7
(Event-independent post-processing procedure)
.
Fix any perfectly calibrated predictor
\tilde{g}
and any
t\geq 1,\varepsilon\geq 0
. Given any feasible post-processing plan
\chi
, a new (possibly imperfectly calibrated) predictor
\tilde{f}
is
generated
as follows: for every event
i\in[n]
, and prediction
p\in[0,1]
,
\displaystyle\tilde{f}_{i}(p)\triangleq\int_{0}^{1}\frac{\tilde{g}_{i}(q)}{g(q)}\cdot\chi(q,p)\,{\mathrm{d}}q~.
(3)
To simplify the presentation, we also say predictor
\tilde{f}
is
generated by
\tilde{g}
and
\chi
.
Example 3.8
(Predictors generated from post-processing procedure)
.
Consider the same two-event setting and four predictors
\tilde{g}^{\dagger},\tilde{g}^{\ddagger},\tilde{f}^{\dagger},\tilde{f}^{\ddagger}
as in
Examples
2.1
and
2.3
. Predictors
\tilde{f}^{\dagger},\tilde{f}^{\ddagger}
can be generated by the perfect calibrated predictors
\tilde{g}^{\dagger},\tilde{g}^{\ddagger}
via
Definition
3.7
with the following post-processing plans:
•
Construct post-processing plan
\chi^{\dagger}
with
\chi^{\dagger}(q,p)=\mathbf{1}\!\left\{{q=0.6,p=0.4}\right\}
. Then, predictor
\tilde{f}^{\dagger}
is generated by perfectly calibrated predictor
\tilde{g}^{\dagger}
and post-processing plan
\chi^{\dagger}
.
•
Construct post-processing plan
\chi^{\ddagger}
with
\chi^{\ddagger}(q,p)=0.5\cdot\mathbf{1}\!\left\{{\text{$q=\theta_{1},p=0.4$ or $q=\theta_{2},p=0.7$}}\right\}
. Then, predictor
\tilde{f}^{\ddagger}
is generated by perfectly calibrated predictor
\tilde{g}^{\ddagger}
and post-processing plan
\chi^{\ddagger}
.
With
Supply-Feasibility
of the feasible post-processing plan
\chi
, the predictor
\tilde{f}=(\tilde{f}_{i})_{i\in[n]}
generated in Eqn. (
3
) is indeed well-defined as each
\tilde{f}_{i}
is a valid distribution over
[0,1]
. In addition,
Calibration-Feasibility
ensures that predictor
\tilde{f}
is
\varepsilon
-calibrated.
Proposition 3.4
.
Fix any perfectly calibrated predictor
\tilde{g}
, any
t\geq 1,\varepsilon\geq 0
, and any feasible post-processing plan
\chi
. The predictor
\tilde{f}
generated by
\tilde{g}
and
\chi
(in
Definition
3.7
) is well-defined and
(\varepsilon,\ell_{t})
-calibrated, i.e.,
\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\leq\varepsilon
.
Proof.
We first verify that for each event
i\in[n]
,
\tilde{f}_{i}
is a valid distribution on
[0,1]
:
\displaystyle\int_{0}^{1}\tilde{f}_{i}(p)~{\mathrm{d}}p
\displaystyle\overset{(a)}{=}\int_{0}^{1}\int_{0}^{1}\frac{\tilde{g}_{i}(q)}{g(q)}\cdot\chi(q,p)\,{\mathrm{d}}q{\mathrm{d}}p=\int_{0}^{1}\frac{\tilde{g}_{i}(q)}{g(q)}\int_{0}^{1}\chi(q,p)\,{\mathrm{d}}p{\mathrm{d}}q\overset{(b)}{=}\int_{0}^{1}\tilde{g}_{i}(q)\,{\mathrm{d}}q=1
where equality (a) holds due to the construction of predictor
\tilde{f}
in
Definition
3.7
, and equality (b) holds due to
Supply-Feasibility
of post-processing plan
\chi
.
We next bound the
\ell_{t}
-norm ECE of predictor
\tilde{f}
:
\displaystyle\left(\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\right)^{t}
\displaystyle=\mathbb{E}\!\left[{\left|\kappa(p)-p\right|^{t}}\right]
\displaystyle=\int_{0}^{1}\left|\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot(p-\theta_{i})\right|^{t}~{\mathrm{d}}p
\displaystyle\overset{(a)}{=}\int_{0}^{1}\left|\sum\nolimits_{i\in[n]}\lambda_{i}\cdot(p-\theta_{i})\int_{0}^{1}\frac{\tilde{g}_{i}(q)}{g(q)}\cdot\chi(q,p)\,{\mathrm{d}}q\right|^{t}~{\mathrm{d}}p
\displaystyle\overset{(b)}{=}\int_{0}^{1}\left|\int_{0}^{1}p\cdot\chi(q,p)\,{\mathrm{d}}q-\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\theta_{i}\cdot\frac{\tilde{g}_{i}(q)}{g(q)}\cdot\chi(q,p)\,{\mathrm{d}}q\right|^{t}~{\mathrm{d}}p
\displaystyle\overset{(c)}{=}\int_{0}^{1}\left|\int_{0}^{1}p\cdot\chi(q,p)\,{\mathrm{d}}q-\int_{0}^{1}q\cdot\chi(q,p)\,{\mathrm{d}}q\right|^{t}~{\mathrm{d}}p
\displaystyle\overset{(d)}{\leq}\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot\left|p-q\right|^{t}\,{\mathrm{d}}q{\mathrm{d}}p\overset{(e)}{\leq}\varepsilon^{t}~,
where equality (a) holds due to the construction of predictor
\tilde{f}
in
Definition
3.7
,
equality (b) holds due to the definition of marginalized perfectly calibrated predictor
g
,
equality (c) holds due to the fact that perfectly calibrated predictor
\tilde{g}
has zero ECE,
inequality (d) holds due to the Jensen’s inequality and the convexity of
\left|\cdot\right|^{t}
, and
inequality (e) holds due to
Calibration-Feasibility
of post-processing plan
\chi
. This completes the proof of
Proposition
3.4
.
∎
We remark that various post-processing procedures have been introduced in the calibration literature. However, the majority of these methods focus on transforming a miscalibrated predictor into a perfectly calibrated one or reducing its ECE
(
Kim et al. 2019
;
Fan et al. 2023
;
Blasiok et al. 2023
;
Gopalan et al. 2024
, e.g.,)
. That said, as we will demonstrate in
Appendix
A
, when the principal and agent have misaligned incentives, allowing the principal to use a predictor with higher ECE may improve both her and the agent’s utility–creating a “win-win” scenario.
Hence, we believe our post-processing procedure is not only valuable as an analytical tool but may also have practical implications.
Predictor space
\mathcal{F}^{\rm EI}_{\varepsilon}
.
We denote by
\mathcal{F}^{\rm EI}_{\varepsilon}
the space of all predictors generated by perfectly calibrated predictors and feasible miscalibration plans via the event-independent post-processing procedure (
Definition
3.7
).
Proposition
3.4
guarantees that every predictor
\tilde{f}\in\mathcal{F}^{\rm EI}_{\varepsilon}
is
{\varepsilon}
-calibrated, and thus
\displaystyle\mathcal{F}^{\rm EI}_{\varepsilon}\subseteq\mathcal{F}_{\varepsilon}~.
Example
3.9
shows that the inclusion relation between the two spaces is strict, i.e., there exists a predictor
\tilde{f}\in\mathcal{F}_{\varepsilon}
such that
\tilde{f}\not\in\mathcal{F}^{\rm EI}_{\varepsilon}
, showing a strict inclusion relation between the two spaces.
28
28
28
In
Section
4
, we extend the event-independent post-processing procedure to the event-dependent post-processing procedure, which generates every
{\varepsilon}
-calibrated predictors from perfectly calibrated predictor.
(See
Figure
3
for the hierarch illustration.) However, when the principal’s indirect utility is event-independent, we argue that restricting to predictors in
\mathcal{F}^{\rm EI}_{\varepsilon}
is without loss of generality.
Example 3.9
(Strict inclusion relation between
\mathcal{F}^{\rm EI}_{\varepsilon}
and
\mathcal{F}_{\varepsilon}
)
.
There are two events and let
\lambda_{1}=\lambda_{2}=0.5
with
\theta_{1}=\theta_{2}=0.5
. Consider predictor
\tilde{f}
with
\tilde{f}_{1}(0.125)=\tilde{f}_{2}(0.875)=1
.
It can be verified that such predictor
\tilde{f}\in\mathcal{F}_{\varepsilon}\backslash\mathcal{F}^{\rm EI}_{\varepsilon}
for every
\varepsilon\geq 0.375
and
t\geq 1
.
\tilde{g}
\tilde{f}
\tilde{f}^{\dagger}
\mathcal{F}_{\varepsilon}
\mathcal{F}^{\rm EI}_{\varepsilon}
\mathcal{F}_{0}
Figure 3
:
An illustration of hierarchical relation between
\mathcal{F}_{\varepsilon}
,
\mathcal{F}^{\rm EI}_{\varepsilon}
and
\mathcal{F}_{0}
.
The dashed arrow line from predictor
\tilde{f}
to perfectly calibrated predictor
\tilde{g}
is established by
Proposition
3.5
, and the dashed arrow line from
\tilde{g}
to the predictor
\tilde{f}^{\dagger}
is established in
Definition
3.7
and
Proposition
3.4
.
Proposition 3.5
.
For every persuasive calibration instance in the event-independent setting,
for every
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}\in\mathcal{F}_{(\varepsilon,\ell_{t})}
, there exists a pair of perfectly calibrated predictor
\tilde{g}
and feasible miscalibration plan
\chi
that can generate a (possibly different) predictor
\tilde{f}^{\dagger}\in\mathcal{F}^{\rm EI}_{(\varepsilon,\ell_{t})}
with the same expected utility for the principal, i.e.,
\text{\bf Payoff}\!\left[{\tilde{f}^{\dagger}}\right]=\text{\bf Payoff}\!\left[{\tilde{f}}\right]
.
Specifically, such a pair of perfectly calibrated predictor
\tilde{g}
and feasible miscalibration plan
\chi
can be constructed as follows:
for every event
i\in[n]
, and predictions
q,p\in[0,1]
,
\displaystyle\tilde{g}_{i}(q)\triangleq\sum\nolimits_{p\in\mathsf{supp}(\tilde{f}_{i}):\kappa(p)=q}\tilde{f}_{i}(p)\;\;\mbox{and}\;\;\chi(q,p)\triangleq\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\mathbf{1}\!\left\{{\kappa(p)=q}\right\}
(4)
where
\kappa(p)
is the true expected outcome defined in Eqn. (
1
).
Corollary 3.6
.
For every persuasive calibration instance in the event-independent setting, there exists an optimal predictor
\tilde{f}^{*}\in\mathcal{F}^{\rm EI}_{(\varepsilon,\ell_{t})}
, i.e.,
\text{\bf Payoff}\!\left[{\tilde{f}^{*}}\right]\geq\text{\bf Payoff}\!\left[{\tilde{f}}\right]
for every
\tilde{f}\in\mathcal{F}_{(\varepsilon,\ell_{t})}
.
Proof of
Proposition
3.5
.
Fix any
\varepsilon
-calibrated predictor
\tilde{f}\in\mathcal{F}_{\varepsilon}
. Consider predictor
\tilde{g}
and post-processing plan
\chi
constructed as in Eqn. (
4
).
We first verify that the constructed predictor
\tilde{g}
has zero ECE and thus is perfect calibrated. Let
\kappa
and
\kappa^{\dagger}
be the true expected outcome function induced by original predictor
\tilde{f}
and constructed predictor
\tilde{g}
, respectively.
Note that for every prediction
q\in\mathsf{supp}(\tilde{g})
, its true expected outcome
\kappa^{\dagger}
can be computed as
\displaystyle\kappa^{\dagger}(q)=\frac{\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{g}_{i}(q)\cdot\theta_{i}}{\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{g}_{i}(q)}
\displaystyle=\frac{\sum\nolimits_{i\in[n]}\lambda_{i}\sum_{p\in\mathsf{supp}(\tilde{f}_{i}):\kappa(p)=q}\tilde{f}_{i}(p)\cdot\theta_{i}}{\sum\nolimits_{i\in[n]}\lambda_{i}\sum_{p\in\mathsf{supp}(\tilde{f}_{i}):\kappa(p)=q}\tilde{f}_{i}(p)}=q
where the first and third equalities hold due to the definition of true expected outcome function
\kappa^{\dagger}
and
\kappa
, while the second equality holds due to the construction of predictor
\tilde{g}
.
We next verify that the constructed post-processing plan
\chi
is feasible. Note that for each prediction
q\in[0,1]
,
\displaystyle\int_{0}^{1}\chi(q,p)~{\mathrm{d}}p
\displaystyle=\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\mathbf{1}\!\left\{{\kappa(p)=q}\right\}~{\mathrm{d}}p
\displaystyle=\sum\nolimits_{i\in[n]}\lambda_{i}\sum\nolimits_{p\in\mathsf{supp}(\tilde{f}_{i}):\kappa(p)=q}\tilde{f}_{i}(p)\overset{}{=}\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\tilde{g}_{i}(q)~,
where the first and last equalities follow the construction in Eqn. (
4
). Thus, the
Supply-Feasibility
(in
Definition
3.6
) of post-processing plan
\chi
is satisfied. In addition,
\displaystyle\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot|q-p|^{t}~{\mathrm{d}}p{\mathrm{d}}q
\displaystyle=\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\mathbf{1}\!\left\{{\kappa(p)=q}\right\}\cdot\left|q-p\right|^{t}~{\mathrm{d}}p{\mathrm{d}}q
\displaystyle=\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\left|\kappa(p)-p\right|^{t}~{\mathrm{d}}p=\left(\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\right)^{t}\leq\varepsilon^{t}
which implies the
Calibration-Feasibility
of post-processing plan
\chi
. Thus,
\chi
is feasible.
Invoking
Proposition
3.5
, we know predictor
\tilde{f}^{\dagger}
generated by
\tilde{g}
and
\chi
is well-defined and
(\varepsilon,\ell_{t})
-calibrated. Finally, we compute the principal’s expected utility given predictor
\tilde{f}^{\dagger}
,
\displaystyle\text{\bf Payoff}\!\left[{\tilde{f}^{\dagger}}\right]
\displaystyle=\sum\nolimits_{i\in[n]}\int_{0}^{1}\lambda_{i}\tilde{f}^{\dagger}_{i}(p)\cdot U(p)\,{\mathrm{d}}p\overset{(a)}{=}\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\frac{\tilde{g}_{i}(q)}{g(q)}\cdot\chi(q,p)\cdot U(p)\,{\mathrm{d}}q\,{\mathrm{d}}p
\displaystyle=\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot U(p)\,{\mathrm{d}}q\,{\mathrm{d}}p\overset{(b)}{=}\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\mathbf{1}\!\left\{{\kappa(p)=q}\right\}\cdot U\left(p\right)~{\mathrm{d}}p{\mathrm{d}}q
\displaystyle=\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot U\left(p\right)~{\mathrm{d}}p=\text{\bf Payoff}\!\left[{\tilde{f}}\right]
where equality (a) follows by definition of
\tilde{f}^{\dagger}
(as it is constructed according to Eqn. (
3
)),
equality (b) follows by the construction of
\chi
defined in Eqn. (
4
).
This finishes the proof of
Proposition
3.5
.
∎
A two-step framework for the principal.
Proposition
3.5
(along with
Corollary
3.6
) establishes an equivalence between
\varepsilon
-calibrated predictors
\tilde{f}
and pairs consisting of perfectly calibrated predictor
\tilde{g}
and feasible miscalibration plan
\chi
. This equivalence allows us to adopt a conceptually
two-step approach
, where the principal first designs a perfectly calibrated predictor and then selects a feasible miscalibration plan. The following proposition formalizes this idea and shows that the optimal
\varepsilon
-calibrated predictor can be characterized by
3.7
, an infinite-dimensional linear program, which plays a key role for proving all our structure results in
Section
3.1
.
Proposition 3.7
.
For every persuasive calibration instance in the event-independent setting, the principal’s expected utility under the optimal
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}^{*}
is equal to the optimal objective value of the following linear program with variables
\{\chi(q,p),g(q)\}_{q,p\in[0,1]}
:
\displaystyle\begin{array}[]{rlll}\max\limits_{{\chi}\geq 0,{g}}&\displaystyle\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot U\left(p\right)~{\mathrm{d}}p{\mathrm{d}}q&\text{s.t.}&\\
(\textsc{Calibration-Feasibility})&\displaystyle\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot\left|p-q\right|^{t}~{\mathrm{d}}p{\mathrm{d}}q\leq\varepsilon^{t},&\\
(\textsc{Supply-Feasibility})&\displaystyle\int_{0}^{1}\chi(q,p)~{\mathrm{d}}p=g(q),&q\in[0,1]\\
(\textsc{MPC-Feasibility})&g\in\mathsf{MPC}(\lambda)~,&\end{array}
where
g\in\mathsf{MPC}(\lambda)
is the mean-preserving constraint (see
Definition
3.10
).
Moreover, every optimal solution of
3.7
can be converted into an optimal
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}^{*}
(see
Lemma
3.8
and
Proposition
3.4
).
Definition 3.10
(Mean-preserving contraction)
.
Fix any distribution
\lambda
with support
\mathsf{supp}(\lambda)\subseteq[0,1]
. For any distribution
g
with support
\mathsf{supp}(g)\subseteq[0,1]
., we say distribution
g
is a
mean-preserving contraction
of distribution
\lambda
if for all
s\in[0,1]
,
\displaystyle\int_{0}^{s}G(q)\,{\mathrm{d}}q\leq\int_{0}^{s}\Lambda(q)\,{\mathrm{d}}q
with the equality at
s=1
, where
G
and
\Lambda
are the cumulative density function of distributions
g
and
\lambda
, respectively. We define
\mathsf{MPC}(\lambda)
as the set of all distributions that are mean-preserving contractions of the distribution
\lambda
.
Lemma 3.8
.
A distribution
g\in\Delta([0,1])
is a marginalized perfectly calibrated predictor if and only if
g\in\mathsf{MPC}(\lambda)
.
Proof.
Consider any perfectly calibrated predictor
\tilde{g}
and its corresponding marginalized predictor
g
,
we know that for every
p\in\mathsf{supp}(\tilde{g})
, we have
\kappa(p)=p
, which implies that
\displaystyle\frac{\sum_{i\in[n]}\lambda_{i}\cdot\tilde{g}_{i}(p)\cdot\theta_{i}}{\sum_{i\in[n]}\lambda_{i}\cdot\tilde{g}_{i}(p)}=p~.
By viewing the predictor
\tilde{g}
as a Blackwell experiment, we can see that every prediction
p
in the support
\mathsf{supp}(g)
represents the mean of the Bayesian posterior updated from receiving a signal
p
(with the prior
\lambda
).
Thus, the marginalized predictor
g
equivalently represents a distribution of (Bayesian) posterior means.
By
Blackwell 1953
;
Rothschild and Stiglitz 1978
;
Gentzkow and Kamenica 2016
, we know that a distribution
g
is a feasible distribution of posterior means if and only if it is an MPC of its prior probability
\lambda
.
∎
We conclude this subsection by proving
Proposition
3.7
.
Proof of
Proposition
3.7
.
We first prove the direction that
for any
\varepsilon
-calibrated predictor
\tilde{f}
, there exists a pair of perfectly calibrated predictor
\tilde{g}
(let
g
be its corresponding marginalized perfectly calibrated predictor) and a miscalibration plan
\chi
such that
g,\chi
is a feasible solution to
3.7
, and meanwhile its objective in
3.7
exactly equals to
\text{\bf Payoff}\!\left[{\tilde{f}}\right]
.
To see this, given the predictor
\tilde{f}
, we consider the predictor
\tilde{g}
, and the miscalibration plan constructed as in Eqn. (
4
).
Proposition
3.5
shows that the constructed predictor
\tilde{g}
is perfectly calibrated and post-processing plan
\chi
is feasible. Let
g
be the marginalized predictor of
\tilde{g}
.
Invoking
Lemma
3.8
, we know that
g\in\mathsf{MPC}(\lambda)
.
Thus,
(g,\chi)
forms a feasible solution to
3.7
.
Moreover, the objective value of
g,\chi
in
3.7
is
\displaystyle\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot U(p)~{\mathrm{d}}p{\mathrm{d}}q
\displaystyle=\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\mathbf{1}\!\left\{{\kappa(p)=q}\right\}\cdot U\left(p\right)~{\mathrm{d}}p{\mathrm{d}}q
\displaystyle=\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot U\left(p\right)~{\mathrm{d}}p=\text{\bf Payoff}\!\left[{\tilde{f}}\right]~.
We next prove the reverse direction: given any feasible solution
g,\chi
to
3.7
,
there exists an
\varepsilon
-calibrated predictor
\tilde{f}
such that its payoff exactly equals to the objective value of the solution
g,\chi
in
3.7
.
To see this, we note that from
Lemma
3.8
, we know for any
g\in\mathsf{MPC}(\lambda)
, there must exist a perfectly calibrated predictor
\tilde{g}
whose marginalized perfectly calibrated predictor exactly equals to
g
.
Now given such a perfectly calibrated predictor
\tilde{g}
, and together with
\chi
, we consider a predictor
\tilde{f}
generated according to Eqn. (
3
). Invoking
Proposition
3.4
, predictor
\tilde{f}
is well-defined and
\varepsilon
-calibrated. Finally, the principal’s expected utility under predictor
\tilde{f}
is
\displaystyle\text{\bf Payoff}\!\left[{\tilde{f}}\right]
\displaystyle=\sum\nolimits_{i\in[n]}\lambda_{i}\int_{0}^{1}\tilde{f}_{i}(p)\cdot U(p)~{\mathrm{d}}p
\displaystyle\overset{}{=}\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\frac{\tilde{g}_{i}(q)}{g(q)}\cdot\chi(q,p)\cdot U(p)\,{\mathrm{d}}q\,{\mathrm{d}}p=\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot U(p)\,{\mathrm{d}}q\,{\mathrm{d}}p
which exactly equals to the objective value of the solution
g,\chi
in
3.7
.
This finishes the proof of
Proposition
3.7
.
∎
A direct application of our two-step framework is the following verification tool that can be used to verify if a given predictor
\tilde{f}
is indeed an optimal
(\varepsilon,\ell_{1})
-calibrated predictor for
K_{1}
ECE.
Proposition 3.9
(Optimality verification)
.
Fix any
\varepsilon>0
and consider
t=1
.
Given any predictor
\tilde{h}
, consider the predictor
\tilde{f}
generated (according to (
3
)) by the perfectly calibrated predictor
\tilde{g}
and the miscalibration plan
\chi
, which are constructed according to (
4
) with input
\tilde{h}
.
If there exists a symmetric linear-tailed convex function
\Gamma
(defined in
Definition
3.4
) with
\Gamma(x)\geq u(x),\forall x
satisfying
(i)
\alpha\cdot\left(\text{\bf ECE}\!\left[{\tilde{f}}\right]-\varepsilon\right)=0
where
\alpha\triangleq\max_{p}|(\Gamma(p))^{\prime}|
;
(ii)
(ii-a):
\mathsf{supp}(\tilde{f})\subseteq\{p\in[0,1]:\Gamma(p)=u(p)\}
, and
(ii-b): all
p
with
p\neq\kappa(p)
and their true expected outcome
\kappa(p)
must lie in linear tails of function
\Gamma
;
(iii)
consider a marginalized predictor
g
induced from the perfectly calibrated predictor
\tilde{g}
(defined in (
4
)),
then (iii-a):
\mathbb{E}_{q\sim g}\!\left[{\Gamma(q)}\right]=\mathbb{E}_{q\sim\lambda}\!\left[{\Gamma(q)}\right]
, and (iii-b):
g\in\mathsf{MPC}(\lambda)
;
then the predictor
\tilde{h}
is the optimal
(\varepsilon,\ell_{1})
-calibrated predictor.
The proof of above
Proposition
3.9
is provided at the end of subsequent
Section
3.3
.
3.3
Proofs for
Theorem
3.1
,
Propositions
3.2
,
3.3
and
3.9
In this section, we provide the proofs of
Theorem
3.1
,
Propositions
3.2
and
3.3
.
Utilizing the two-step framework, we know that the optimal
\varepsilon
-calibrated predictor can be transformed into an optimal solution of
3.7
and vice versa. Therefore, proving the structural results for the optimal predictor is equivalent to proving their analogs for the optimal solution in
3.7
.
With a slight abuse of notation, we define
\mathsf{supp}(\chi)\triangleq\{p\in[0,1]:\exists q\in[0,1],\chi(q,p)>0\}
.
To prove
Theorem
3.1
, we first show the following equivalent statement for the optimal solution to
3.7
.
Lemma 3.10
(Restatement of
Theorem
3.1
for
(g^{*},\chi^{*})
)
.
In
3.7
with
t=1
, there exists
0\leq p_{\mathsf{L}}\leq p_{\mathsf{H}}\leq 1
and an optimal solution
(g^{*},\chi^{*})
that satisfies the following three properties:
(i)
For every
(q,p)
such that
\chi^{*}(q,p)>0
, if
p\in[0,p_{\mathsf{L}}]
(resp.
p\in[p_{\mathsf{L}},p_{\mathsf{H}}]
,
p\in[p_{\mathsf{H}},1]
), then
p\leq q
(resp.
p=q
,
p\geq q
).
(ii)
There exists a function
\xi:\mathsf{supp}(\chi^{*})\rightarrow\mathbb{R}
that selects a subgradient at each prediction
p\in\mathsf{supp}(\chi^{*})
, i.e.,
\xi(p)\in\partial U(p)
, such that function
\xi
is increasing, and it satisfies
\xi(p)\equiv\alpha
for
p\in[0,p_{\mathsf{L}}]
, and
\xi(p)\equiv-\alpha
for all
p\in[p_{\mathsf{H}},1]
for some
\alpha\geq 0
.
(iii)
All points
(p,U(p))_{p\in\mathsf{supp}(\chi^{*})}
form a convex function.
Moreover, points
(p,U(p))
for all
p
in
[p_{\mathsf{H}},1]
are collinear (with slope
\alpha
), and points
(p,U(p))
for all
p
in
[0,p_{\mathsf{L}}]
are collinear (with slope
-\alpha
).
We now prove
Theorem
3.1
using our two-step framework and
Lemma
3.10
.
Proof of
Theorem
3.1
.
Consider the optimal solution
(g^{*},\chi^{*})
to
3.7
that satisfies all three properties in
Lemma
3.10
. Invoking
Proposition
3.7
, it can be converted in to an optimal
(\varepsilon,\ell_{1})
-calibrated predictor
\tilde{f}^{*}
. Let
\kappa
be the true expected outcome function induced by predictor
\tilde{f}^{*}
. By construction, for every
(q,p)
such that
\chi^{*}(q,p)>0
, we have
\kappa(p)=q
. (This is guaranteed since
g^{*}
is a marginalized perfectly calibrated predictor and
\chi^{*}
is a feasible post-processing plan.) Thus, the “Miscalibration Structure” property in
Theorem
3.1
is implied by the first property in
Lemma
3.10
. Similarly, by the construction of predictor
\tilde{f}^{*}
in
Definition
3.7
,
\mathsf{supp}(\tilde{f}^{*})=\mathsf{supp}(\chi^{*})
. Therefore, the “Payoff Structure-I” and “Payoff Structure-II” properties in
Theorem
3.1
are implied by the second and third properties in
Lemma
3.10
. This finishes the proof of
Theorem
3.1
.
∎
The proof of
Lemma
3.10
.
We below provide the proof of
Lemma
3.10
.
The proof of
Lemma
3.10
will use the following property of marginalized perfectly calibrated predictor.
Fact 3.11
(Contracting predictions)
.
For any marginalized predictor
g\in\mathsf{MPC}(\lambda)
, consider two predictions
p_{1},p_{2}\in\mathsf{supp}(g)
and let
p^{\dagger}\triangleq\frac{g(p_{1})p_{1}+g(p_{2})p_{2}}{g(p_{1})+g(p_{2})}
.
Consider another distribution
g^{\dagger}\in\Delta([0,1])
satisfying
g^{\dagger}(p)=g(p)
for all
p\in[0,1]\setminus\{p_{1},p_{2},p^{\dagger}\}
, and
g^{\dagger}(p^{\dagger})=g(p^{\dagger})+g(p_{1})+g(p_{2})
.
Then
g^{\dagger}
is also marginalized perfectly calibrated predictor, namely,
g^{\dagger}\in\mathsf{MPC}(\lambda)
.
Proof.
This fact immediately follows from the Blackwell informativeness
(
Blackwell 1953
)
as the marginalized predictor
g
is more informative than the predictor
g^{\dagger}
.
∎
The above property of marginalized predictor
g
essentially says that the distribution
g^{\dagger}
obtained by contracting any predictions supported in
g
is also a feasible marginalized prediction – it is in the set
\mathsf{MPC}(\lambda)
.
Proof of Statement (i) in
Lemma
3.10
.
We prove the statement by contradiction.
Suppose that there exists a solution
g,\chi
to
3.7
that satisfies: it exists
q_{1},q_{2}
with
q_{1}0,\chi(q_{2},p_{2})>0
satisfying
p_{1}>q_{1}
but
p_{2}q_{1}
.
Thus, we have shown that
\text{\bf ECE}\!\left[{\chi^{\dagger}}\right]<\text{\bf ECE}\!\left[{\chi}\right]
.
We further notice that, by construction, the solution
g^{\dagger},\chi^{\dagger}
yields the same objective value as the solution
g,\chi
in
3.7
.
•
When
p_{1}0.
Meanwhile, the solution
g^{\dagger},\chi^{\dagger}
yields the same objective value with
g,\chi
.
Putting all pieces together, we can finish the proof.
∎
Proof of Statements (ii) and (iii) in
Lemma
3.10
.
The proof follows by the complementary slackness.
We
consider the following Lagrange for
3.7
with multipliers
\alpha\geq 0
,
\beta_{\chi}(q,p)\geq 0
,
\beta_{\mathsf{supp}}(q)\in\mathbb{R},\beta_{g}(q)\geq 0,\bar{\beta}_{g}\in\mathbb{R},\beta_{\mathsf{MPC}}(t)\geq 0
\displaystyle\mathcal{L}=
\displaystyle\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot U\left(p\right)\,{\mathrm{d}}p{\mathrm{d}}q+\alpha\cdot\left(\varepsilon-\int_{0}^{1}\int_{0}^{1}\chi(q,p)\cdot|q-p|\,{\mathrm{d}}p{\mathrm{d}}q\right)
\displaystyle+\int_{0}^{1}\beta_{\mathsf{supp}}(q)\cdot\left(\int_{0}^{1}\chi(q,p)~{\mathrm{d}}p-g(q)\right)~{\mathrm{d}}q+\int_{0}^{1}\int_{0}^{1}\beta_{\chi}(q,p)\chi(q,p)\,{\mathrm{d}}p{\mathrm{d}}q
\displaystyle+\bar{\beta}_{g}\left(\int_{0}^{1}g(q){\mathrm{d}}q-1\right)+\int_{0}^{1}\beta_{g}(q)g(q)\,{\mathrm{d}}q+\int_{0}^{1}\beta_{\mathsf{MPC}}(t)\left(\int_{0}^{t}\int_{0}^{x}\lambda(q)\,{\mathrm{d}}q{\mathrm{d}}x-\int_{0}^{t}\int_{0}^{x}g(q)\,{\mathrm{d}}q{\mathrm{d}}x\right)\,{\mathrm{d}}t
\displaystyle+\bar{\beta}_{\lambda}\cdot\left(\int_{0}^{1}qg(q)\,{\mathrm{d}}q-\bar{\theta}\right)
By the first-order condition of optimal miscalibration plan
\chi
, we must have
\displaystyle U(p)-\alpha\cdot|q-p|+\beta_{\mathsf{supp}}(q)+\beta_{\chi}(q,p)
\displaystyle=0,\quad
\displaystyle\forall q,p~.
Since
\beta_{\chi}(q,p)\geq 0
for all
q,p
, we have
\displaystyle U(p)-\alpha\cdot|q-p|
\displaystyle=-\beta_{\mathsf{supp}}(q),\quad\forall q,p\text{ with }\chi(q,p)>0
\displaystyle U(p)-\alpha\cdot|q-p|
\displaystyle\leq-\beta_{\mathsf{supp}}(q),\quad\forall q,p
The first-order condition of
g
also implies:
\displaystyle\beta_{g}(q)-\beta_{\mathsf{supp}}(q)-\int_{q}^{1}\int_{x}^{1}\beta_{\mathsf{MPC}}(t)\,{\mathrm{d}}t{\mathrm{d}}x+\bar{\beta}_{g}+q\bar{\beta}_{\lambda}
\displaystyle=0,\quad\forall q~.
Note that
\chi(q,p)>0
must also imply that
g(q)>0
, which implies that
\beta_{\chi}(q,p)=\beta_{g}(q)=0
.
We next define the function
\Gamma(\cdot):[0,1]\rightarrow\mathbb{R}
:
\displaystyle\Gamma(q)\triangleq\int_{q}^{1}\int_{x}^{1}\beta_{\mathsf{MPC}}(t)\,{\mathrm{d}}t{\mathrm{d}}x-\bar{\beta}_{g}-q\bar{\beta}_{\lambda}~.
It is easy to see that function
\Gamma
is convex.
Claim 3.12
.
Function
\Gamma
is a convex function.
With the above definition, we have the following condition for the optimal solution
\chi,g
:
\displaystyle U(p)-\alpha\cdot|q-p|
\displaystyle\leq\Gamma(q)~,\quad\forall q,p~.
(12)
\displaystyle U(p)-\alpha\cdot|q-p|
\displaystyle=\Gamma(q)~,\quad\text{if }\chi(q,p)>0~.
(13)
From the above two conditions, we can deduce the following observation:
Claim 3.13
.
Function
\Gamma(p)\geq U(p)
for all
p\in[0,1]
, and
\Gamma(p)=U(p)
if
\chi(p,p)>0
.
Function
\Gamma(p)\geq U(p)
for all
p\in[0,1]
is due to Eqn. (
12
) w.r.t.
(p,p)
, and
\Gamma(p)=U(p)
if
\chi(p,p)>0
is due to Eqn. (
13
) w.r.t.
\chi(p,p)>0
.
Now let the predictions
p_{\mathsf{H}},p_{\mathsf{L}}
and the sets
\mathcal{S}_{\mathsf{H}},\mathcal{S}_{\mathsf{L}}
be defined as follows:
\displaystyle p_{\mathsf{H}}
\displaystyle\triangleq\inf_{p\in[0,1]}\{p:\chi(q,p)>0\wedge p>q\},\quad\mathcal{S}_{\mathsf{H}}\triangleq\{p\in[p_{\mathsf{H}},1]:\chi(q,p)>0,q\in[0,1]\}~;
\displaystyle p_{\mathsf{L}}
\displaystyle\triangleq\sup_{p\in[0,1]}\{p:\chi(q,p)>0\wedge p0,q\in[0,1]\}~.
Collinearity.
We next argue that all points
(p,U(p))_{p\in\mathcal{S}_{\mathsf{H}}}
are all collinear.
For the above defined
p_{\mathsf{H}}
, let
q_{\mathsf{H}}
be the point that
\chi(q,p_{\mathsf{H}})>0
.
From (
12
) and (
13
), we know
\displaystyle U(p)-\alpha\cdot(p-q_{\mathsf{H}})
\displaystyle\leq\Gamma(q_{\mathsf{H}}),\quad\forall p\geq q_{\mathsf{H}}
\displaystyle U(p_{\mathsf{H}})-\alpha\cdot(p_{\mathsf{H}}-q_{\mathsf{H}})
\displaystyle=\Gamma(q_{\mathsf{H}}),
(
\chi(q_{\mathsf{H}},p_{\mathsf{H}})>0
)
Thus, for any
p\geq p_{\mathsf{H}}
, we have that
\displaystyle U(p)\leq U(p_{\mathsf{H}})+\alpha\cdot(p-p_{\mathsf{H}})~.
(14)
On the other hand, for any
p\in\mathcal{S}_{\mathsf{H}}
with
\chi(q,p)>0
, we know
\displaystyle U(p)-\alpha\cdot(p-q)
\displaystyle=\Gamma(q)
(by (
13
) with
\chi(q,p)>0
)
\displaystyle\geq\Gamma(q_{\mathsf{H}})+\alpha\cdot(q-q_{\mathsf{H}})
(by
3.12
and
3.13
)
\displaystyle\Rightarrow~U(p)
\displaystyle\geq\Gamma(q_{\mathsf{H}})+\alpha\cdot(p-q_{\mathsf{H}})
\displaystyle=U(p_{\mathsf{H}})-\alpha\cdot(p_{\mathsf{H}}-q_{\mathsf{H}})+\alpha\cdot(p-q_{\mathsf{H}})
\displaystyle=U(p_{\mathsf{H}})+\alpha\cdot(p-p_{\mathsf{H}})~.
Thus, for any
p\in\mathcal{S}_{\mathsf{H}}
we must have
\displaystyle U(p)=U(p_{\mathsf{H}})+\alpha\cdot(p-p_{\mathsf{H}})~,
which shows that all points
(p,U(p))_{p\in\mathcal{S}_{\mathsf{H}}}
must be collinear with a slope of
\alpha
.
Similar arguments can be applied for predictions in the set
\mathcal{S}_{\mathsf{L}}
.
Convexity of points
(p,U(p))_{p\in\mathsf{supp}(\chi)}
.
We next argue that all points
(p,U(p))_{p\in\mathsf{supp}(\chi)}
form a convex function.
We define
p_{\mathsf{H}}^{\dagger}\triangleq\sup\{p\in\mathsf{supp}(\chi):p0
, we have
\kappa(p)=q
. (This is guaranteed since
g^{*}
is a marginalized perfectly calibrated predictor and
\chi^{*}
is a feasible post-processing plan.)
Thus, the Statement (i) in
Proposition
3.2
is implied by the Statement (i) in
Lemma
3.10
, Statement (ii) and (iii) in
Proposition
3.2
is also implied accordingly as we have
\mathsf{supp}(\tilde{f}^{*})=\mathsf{supp}(\chi^{*})
.
∎
The proof of
Lemma
3.14
.
We next provide proof for
Lemma
3.14
. Its analysis is similar to the duality argument used in the proof of Statements (ii) and (iii) in
Lemma
3.10
.
Proof of
Lemma
3.14
.
To simplify the presentation, we shorthand the optimal solution
(g^{*},\chi^{*})
as
(g,\chi)
.
Recall the convex function
\Gamma
and the Lagrange multiplier
\alpha
introduced in the proof of
Lemma
3.10
.
Conditions (
12
) and (
13
) are
\displaystyle U(p)-\alpha\cdot|q-p|
\displaystyle\leq\Gamma(q)~,\quad\forall q,p~.
\displaystyle U(p)-\alpha\cdot|q-p|
\displaystyle=\Gamma(q)~,\quad\text{if }\chi(q,p)>0~.
Define
x_{\mathsf{L}}\triangleq q_{\mathsf{L}}
and
x_{\mathsf{H}}\triangleq q_{\mathsf{H}}
where
q_{\mathsf{L}}
(namely it satisfies
\chi(q_{\mathsf{L}},p_{\mathsf{L}})>0
) and
q_{\mathsf{H}}
(namely it satisfies
\chi(q_{\mathsf{H}},p_{\mathsf{H}})>0
) are defined in the proof of
Lemma
3.10
.
Now we construct a symmetric linear-tailed convex function
\Gamma^{\dagger}
satisfying the all properties in
Lemma
3.14
as follows:
\displaystyle\Gamma^{\dagger}(p)\triangleq\left\{\begin{array}[]{ll}\Gamma(x_{\mathsf{L}})+\alpha(x_{\mathsf{L}}-p)&\quad\text{if $p\in[0,p_{\mathsf{L}}]$}\\
\Gamma(p)&\quad\text{if $p\in[p_{\mathsf{L}},p_{\mathsf{H}}]$}\\
\Gamma(x_{\mathsf{H}})+\alpha(p-x_{\mathsf{H}})&\quad\text{if $p\in[p_{\mathsf{H}},1]$}\end{array}\right.
We first verify that the constructed function
\Gamma^{\dagger}
is a symmetric linear-tailed convex function. By construction, function
\Gamma^{\dagger}
has symmetric linear tails and is convex for every
p\in[p_{\mathsf{L}},p_{\mathsf{H}}]
. In addition, due to the definition of
x_{\mathsf{L}},x_{\mathsf{H}}
, the linear slope
\alpha\geq-\Gamma^{\prime}(x_{\mathsf{L}})
and
\alpha\geq\Gamma^{\prime}(x_{\mathsf{H}})
and thus function
\Gamma^{\dagger}
is convex for all
p\in[0,1]
.
We next verify Statement (i). By construction, for every prediction
p\in[p_{\mathsf{L}},p_{\mathsf{H}}]
,
\Gamma^{\dagger}(p)=\Gamma(p)\geq U(p)
due to condition (
12
). For every prediction
p\in[0,p_{\mathsf{L}}]
,
\Gamma^{\dagger}(p)=\Gamma(x_{\mathsf{L}})+\alpha(x_{\mathsf{L}}-p)\geq U(p)
due to condition (
12
) at
x_{\mathsf{L}}
and the collinearity in the third property in
Lemma
3.10
. For every prediction
p\in[p_{\mathsf{H}},1]
, a symmetric argument applies.
We now verify Statement (ii). By construction, for every prediction
p\in[p_{\mathsf{L}},p_{\mathsf{H}}]\cap\mathsf{supp}(\chi)
,
\Gamma^{\dagger}(p)=\Gamma(p)=U(p)
due to the first property in
Lemma
3.10
and condition (
13
). Similarly, for every prediction
p\in[0,p_{\mathsf{L}}]\cap\mathsf{supp}(\chi)
,
\Gamma^{\dagger}(p)=\Gamma(x_{\mathsf{L}})+\alpha(x_{\mathsf{L}}-p)=U(p)
, due to the collinearity in the third property in
Lemma
3.10
and condition (
13
). For every prediction
p\in[p_{\mathsf{H}},1]\cap\mathsf{supp}(\chi)
, a symmetric argument applies.
Finally, Statement (iii) holds due to the definition of
x_{\mathsf{L}},x_{\mathsf{H}}
and the first property in
Lemma
3.10
, which implies
x_{\mathsf{L}}\geq p_{\mathsf{L}}
and
x_{\mathsf{H}}\leq p_{\mathsf{H}}
. This finishes the proof of
Lemma
3.14
.
∎
To prove
Proposition
3.3
, we first show the following equivalent statement for the optimal solution
(g^{*},\chi^{*})
to
3.7
.
Lemma 3.15
(Restatement of
Proposition
3.3
for
(g^{*},\chi^{*})
)
.
In
3.7
with
t=1
, let
(g^{*},\chi^{*})
be the optimal solution to
3.7
that satisfies the properties in
Lemma
3.10
, and in addition,
(i)
we have
|\mathsf{supp}(\chi^{*})|\leq n+2
.
(ii)
for each event
i\in[n]
, we have
|\{p\in[0,1]:\tilde{g}^{*}_{i}(q)>0\text{ and }\chi^{*}(q,p)>0,q\in[0,1]\}|\leq 4
.
(iii)
for each
q\in\mathsf{supp}(g^{*})
, we have
\left|\{p\in[0,1]:\chi^{*}(q,p)>0\}\right|\leq 2
.
Moreover, if the equality holds (i.e.,
\left|\{p\in[0,1]:\chi^{*}(q,p)>0\}\right|=2
), at least one prediction
p
belongs to the under-confidence
[0,p_{\mathsf{L}}]
or over-confidence interval
[p_{\mathsf{H}},1]
, i.e.,
p\in[0,p_{\mathsf{L}}]\cup[p_{\mathsf{H}},1]
.
Proof of
Proposition
3.3
.
Consider the optimal solution
(g^{*},\chi^{*})
to
3.7
that satisfies all properties in
Lemma
3.15
.
Invoking
Proposition
3.7
, it can be converted in to an optimal
(\varepsilon,\ell_{1})
-calibrated predictor
\tilde{f}^{*}
.
Let
\kappa
be the true expected outcome function induced by predictor
\tilde{f}^{*}
.
By construction, for every
(q,p)
such that
\chi^{*}(q,p)>0
, we have
\kappa(p)=q
. (This is guaranteed since
g^{*}
is a marginalized perfectly calibrated predictor and
\chi^{*}
is a feasible post-processing plan.)
Thus, the Statement (i) in
Proposition
3.3
is implied by the first property in
Lemma
3.10
, as we have
\mathsf{supp}(\tilde{f}^{*})=\mathsf{supp}(\chi^{*})
.
Similarly, by the construction of predictor
\tilde{f}^{*}
in
Definition
3.7
, Statements (ii) and (iii) properties in
Proposition
3.3
are implied by the second and third statements in
Lemma
3.10
. This finishes the proof of
Proposition
3.3
.
∎
The proof of
Lemma
3.15
.
We below provide the proof for
Lemma
3.15
.
Before proceeding to the proof, we first prove the following monotonicity property of the prediction
p
w.r.t. its corresponding true expected outcome
q
.
Lemma 3.16
(Monotonicity of the prediction
p
w.r.t. its
q
with
\chi(q,p)>0
)
.
It is without loss to consider a solution
g,\chi
to
3.7
such that for any
q_{1}0\}\leq\min\{p\in[0,1]:\chi(q_{2},p)>0\}
.
Proof of
Lemma
3.16
.
Fix a feasible solution
g,\chi
to
3.7
.
Fix any
q_{1}0\}
and
p_{2}\triangleq\min\{p\in[0,1]:\chi(q_{2},p)>0\}
.
For notation simplicity, we let
m_{1}\triangleq\chi(q_{1},p_{1})
and
m_{2}\triangleq\chi(q_{2},p_{2})
.
Let us suppose
p_{1}>p_{2}
. We construct the following
\chi^{\dagger}
(and its
g^{\dagger}
):
\displaystyle\chi^{\dagger}(q,\cdot)
\displaystyle=\chi(q,\cdot),\quad
\displaystyle q\in\mathsf{supp}(\chi)\setminus\{q_{1},q_{2}\}~;
\displaystyle\chi^{\dagger}(q_{i},p)
\displaystyle=\chi(q_{i},p),\quad
\displaystyle p\in[0,1]\setminus\{p_{1},p_{2}\},i\in[2]~;
\displaystyle\chi^{\dagger}(q_{1},p_{1})
\displaystyle=(m_{1}-m_{2})\mathbf{1}\!\left\{{m_{1}\geq m_{2}}\right\},\quad
\displaystyle\chi^{\dagger}(q_{1},p_{2})=m_{1}+\chi(q_{1},p_{2})-(m_{1}-m_{2})\mathbf{1}\!\left\{{m_{1}\geq m_{2}}\right\};
\displaystyle\chi^{\dagger}(q_{2},p_{2})
\displaystyle=(m_{2}-m_{1})\mathbf{1}\!\left\{{m_{1}0\}\leq\min\{p\in[0,1]:\chi^{\dagger}(q_{2},p)>0\}
.
Moreover, it is easy see that
\displaystyle\chi^{\dagger}(q_{1},p_{1})+\chi^{\dagger}(q_{2},p_{1})
\displaystyle=\chi(q_{1},p_{1})+\chi(q_{2},p_{1})
\displaystyle\chi^{\dagger}(q_{1},p_{2})+\chi^{\dagger}(q_{2},p_{2})
\displaystyle=\chi(q_{1},p_{2})+\chi(q_{2},p_{2})~.
Thus, solution
g^{\dagger},\chi^{\dagger}
yields the same objective value with
g,\chi
,
which finishes the proof.
∎
Proof of Statement (i) in
Lemma
3.15
.
Suppose that there exists an optimal solution
g,\chi
to the program
3.7
such that there exist predictions
q_{1}\leq p_{1}0,\chi(q_{1},p_{2})>0,\chi(q_{2},p_{3})>0
for some
q_{1}p_{2}
.
Let
t_{i}\triangleq p_{i}-q_{1}
for
i\in[3]
.
From the Statement (iii) in
Lemma
3.10
, we have
\displaystyle\frac{U(p_{2})-U(p_{1})}{t_{2}-t_{1}}=\frac{U(p_{3})-U(p_{2})}{t_{3}-t_{2}}~.
(16)
We next construct
g^{\dagger},\chi^{\dagger}
as follows:
\displaystyle\chi^{\dagger}(q,\cdot)
\displaystyle=\chi(q,\cdot),\quad
\displaystyle q\in\mathsf{supp}(g)\setminus\{q_{1},q_{3}\}~;
\displaystyle\chi^{\dagger}(q_{1},p)
\displaystyle=\chi(q_{1},p),\quad
\displaystyle p\in[0,1]\setminus\{p_{1},p_{2}\}~;
\displaystyle\chi^{\dagger}(q_{1},p_{1})
\displaystyle=\chi(q_{1},p_{1})+\chi(q_{1},p_{2})\cdot\frac{t_{3}-t_{2}}{t_{3}-t_{1}}
\displaystyle\chi^{\dagger}(q_{1},p_{3})
\displaystyle=\chi(q_{1},p_{2})\cdot\frac{t_{2}-t_{1}}{t_{3}-t_{1}}
The above construction essentially reallocates the mass
\chi(q_{1},p_{2})
on prediction
p_{2}
to the predictions
p_{1}
and
p_{3}
.
Such reallocation ensures that
\text{\bf ECE}\!\left[{\chi^{\dagger}}\right]=\text{\bf ECE}\!\left[{\chi}\right]
, which can be seen as follows:
\displaystyle\text{\bf ECE}\!\left[{\chi^{\dagger}}\right]-\text{\bf ECE}\!\left[{\chi}\right]
\displaystyle=\left(\chi(q_{1},p_{1})+\chi(q_{1},p_{2})\cdot\frac{t_{3}-t_{2}}{t_{3}-t_{1}}\right)\cdot(p_{1}-q_{1})+\chi(q_{1},p_{2})\cdot\frac{p_{2}-p_{1}}{t_{3}-t_{1}}\cdot t_{3}
\displaystyle\quad-\left(\chi(q_{1},p_{1})\cdot t_{1}+\chi(q_{1},p_{2})\cdot t_{2}\right)
\displaystyle=\chi(q,p_{2})\cdot\left(\frac{t_{3}-t_{2}}{t_{3}-t_{1}}\cdot t_{1}+\frac{t_{2}-t_{1}}{t_{3}-t_{1}}\cdot t_{3}-t_{2}\right)=0~.
Note that the above construction ensures that
g^{\dagger}=g
, and moreover, the objective value difference between the two solutions
g^{\dagger},\chi^{\dagger}
and
g,\chi
can be computed as
\displaystyle\left(\chi(q_{1},p_{1})+\chi(q_{1},p_{2})\cdot\frac{t_{3}-t_{2}}{t_{3}-t_{1}}\right)\cdot U(p_{1})+\chi(q_{1},p_{2})\cdot\frac{t_{2}-t_{1}}{t_{3}-t_{1}}\cdot U(p_{3})
\displaystyle-\left(\chi(q_{1},p_{1})\cdot U(p_{1})+\chi(q_{1},p_{2})\cdot U(p_{2})\right)
\displaystyle=~
\displaystyle\chi(q,p_{2})\left(\frac{t_{3}-t_{2}}{t_{3}-t_{1}}\cdot U(p_{1})+\frac{t_{2}-t_{1}}{t_{3}-t_{1}}\cdot U(p_{3})-U(p_{2})\right)=0~,
where the last inequality is due to (
16
).
Thus, solution
g^{\dagger},\chi^{\dagger}
is also optimal.
Similarly, the analysis for the case can be carried over when there exist predictions
p_{3}0,\chi(q_{1},p_{2})>0,\chi(q_{2},p_{3})>0
.
If we have
p_{1}^{\dagger}0,\chi(q_{1},p_{1}^{\ddagger})>0
, and suppose there exists
q_{2},q_{3}
with
q_{2}0,\chi(q_{3},p_{3})>0
.
Then we argue that there always exists
\chi^{\dagger}
such that it can either reallocates the mass
\chi(q_{1},p_{1}^{\dagger})
to the predictions
p_{1}^{\ddagger},p_{3}
or reallocates the mass
\chi(q_{1},p_{1}^{\ddagger})
to the predictions
p_{1}^{\dagger},p_{2}
, without changing the objective value.
To see this, we first note that from the Statement (iii) in
Lemma
3.10
, we still have
\displaystyle\frac{U(p_{1}^{\dagger})-U(p_{1}^{\ddagger})}{t_{1}^{\dagger}-t_{1}^{\ddagger}}=\frac{U(p_{3})-U(p_{1}^{\ddagger})}{t_{3}-t_{1}^{\ddagger}}=\frac{U(p_{2})-U(p_{1}^{\dagger})}{t_{2}-t_{1}^{\dagger}}~.
where here
t_{1}^{\dagger}\triangleq q_{1}-p_{1}^{\dagger}
,
t_{1}^{\ddagger}\triangleq p_{1}^{\ddagger}-q_{1}
,
t_{3}=p_{3}-q_{1}
, and
t_{2}=q_{1}-p_{2}
.
From
Lemma
3.16
, we can without loss consider
p_{2}\leq p_{1}^{\dagger}
and
p_{1}^{\ddagger}\leq p_{3}
.
When
t_{1}^{\ddagger}\leq t_{1}^{\dagger}
, one can use the same argument above to construct a new feasible
\chi^{\dagger}
such that it reallocates the mass
\chi(q_{1},p_{1}^{\dagger})
to the predictions
p_{1}^{\ddagger}
and
p_{3}
without changing the objective value.
Similarly, when
t_{1}^{\ddagger}>t_{1}^{\dagger}
, one can use the same argument above to construct a new feasible
\chi^{\dagger}
such that it reallocates the mass
\chi(q_{1},p_{1}^{\ddagger})
to the predictions
p_{1}^{\dagger}
and
p_{2}
without changing the objective value.
Putting all pieces together, we show that there exists at most
q_{1},q_{2}\in\mathsf{supp}(g)
, such that each of them may generate two different predictions.
By
Lemma
3.17
, we further know that for each event
i
, we have
|\mathsf{supp}(q_{i})|\leq 2
. Thus, in total, we have at most
n+2
predictions.
∎
We then first prove the third statement in
Lemma
3.15
.
Proof of Statement (iii) in
Lemma
3.15
.
We prove the result by construction.
Let
g,\chi
be an optimal solution to the program
3.7
, and suppose there exists three different predictions
p_{1},p_{2},p_{3}
that have the same true expected outcome, namely,
\kappa(p_{1})=\kappa(p_{2})=\kappa(p_{3})=q
for some
q\in\mathsf{supp}(g)
.
We show that we can construct another feasible solution
g^{\dagger},\chi^{\dagger}
to the program
3.7
that has the same objective value with the solution
g,\chi
.
Let
t_{i}=|p_{i}-q|
for
i\in[3]
.
Without loss of generality, let us assume that
t_{1}\leq t_{2}\leq t_{3}
.
Note that it cannot be the case where
t_{1}=t_{3}
, as this case must imply that either
p_{2}=p_{1}
or
p_{2}=p_{3}
, which violates the assumption that
p_{1}\neq p_{2}\neq p_{3}
.
We next consider the construction of
g^{\dagger},\chi^{\dagger}
as follows:
\displaystyle\chi^{\dagger}(q^{\prime},\cdot)
\displaystyle=\chi(q^{\prime},\cdot),\quad
\displaystyle q^{\prime}\in\mathsf{supp}(g)\setminus\{q\}~;
\displaystyle\chi^{\dagger}(q,p)
\displaystyle=\chi(q,p),\quad
\displaystyle p\in[0,1]\setminus\{p_{1},p_{3}\}~;
\displaystyle\chi^{\dagger}(q,p_{1})
\displaystyle=\chi(q,p_{1})+\chi(q,p_{2})\cdot\frac{t_{3}-t_{2}}{t_{3}-t_{1}},\quad
\displaystyle\chi^{\dagger}(q,p_{3})
\displaystyle=\chi(q,p_{3})+\chi(q,p_{2})\cdot\frac{t_{2}-t_{1}}{t_{3}-t_{1}};
\displaystyle\chi^{\dagger}(q,p_{2})
\displaystyle=0;
The above construction essentially reallocates the mass
\chi(q,p_{2})
on prediction
p_{2}
to the predictions
p_{1}
and
p_{3}
.
Such reallocation ensures that
\text{\bf ECE}\!\left[{\chi^{\dagger}}\right]=\text{\bf ECE}\!\left[{\chi}\right]
, which can be seen as follows:
\displaystyle\text{\bf ECE}\!\left[{\chi^{\dagger}}\right]-\text{\bf ECE}\!\left[{\chi}\right]
\displaystyle=~
\displaystyle\left(\chi(q,p_{1})+\chi(q,p_{2})\cdot\frac{t_{3}-t_{2}}{t_{3}-t_{1}}\right)\cdot t_{1}+\left(\chi(q,p_{3})+\chi(q,p_{2})\cdot\frac{t_{2}-t_{1}}{t_{3}-t_{1}}\right)\cdot t_{3}
\displaystyle-\left(\chi(q,p_{1})\cdot t_{1}+\chi(q,p_{2})\cdot t_{2}+\chi(q,p_{3})\cdot t_{3}\right)
\displaystyle=~
\displaystyle\chi(q,p_{2})\cdot\frac{t_{3}-t_{2}}{t_{3}-t_{1}}\cdot t_{1}+\chi(q,p_{2})\cdot\frac{t_{2}-t_{1}}{t_{3}-t_{1}}\cdot t_{3}-\chi(q,p_{2})\cdot t_{2}=0~.
Note that the above construction ensures that
g^{\dagger}=g
, and moreover, the objective value difference between the two solutions
g^{\dagger},\chi^{\dagger}
and
g,\chi
can be computed as
\displaystyle\left(\chi(q,p_{1})+\chi(q,p_{2})\cdot\frac{t_{3}-t_{2}}{t_{3}-t_{1}}\right)\cdot U(p_{1})+\left(\chi(q,p_{3})+\chi(q,p_{2})\cdot\frac{t_{2}-t_{1}}{t_{3}-t_{1}}\right)\cdot U(p_{3})
\displaystyle-\left(\chi(q,p_{1})\cdot U(p_{1})+\chi(q,p_{2})\cdot U(p_{2})+\chi(q,p_{3})\cdot U(p_{3})\right)
\displaystyle=~
\displaystyle\chi(q,p_{2})\cdot\frac{t_{3}-t_{2}}{t_{3}-t_{1}}\cdot U(p_{1})+\chi(q,p_{2})\cdot\frac{t_{2}-t_{1}}{t_{3}-t_{1}}\cdot U(p_{3})-\chi(q,p_{2})\cdot U(p_{2})=0~,
where the last inequality is due to the Statement (iii) in
Lemma
3.10
, which ensures that for some
\alpha\geq 0
,
\displaystyle U(p_{1})-\alpha\cdot t_{1}=U(p_{2})-\alpha\cdot t_{2}=U(p_{3})-\alpha\cdot t_{3}
Thus, solution
g^{\dagger},\chi^{\dagger}
is also optimal.
We thus finish the proof.
∎
We now prove the second statement in
Lemma
3.15
.
Lemma 3.17
(Bi-pooling structure of optimal
g
, adopted from
Arieli et al. 2023
)
.
There exists an optimal marginalized predictor
g
such that every event induces at most two true expected outcomes, namely, for every
i\in[n]
, we have
\{q:g_{i}(q)>0\}\leq 2
.
Proof of Statement (ii) in
Lemma
3.15
.
Combining Statement (iii) in
Proposition
3.3
and
Lemma
3.17
would finish the proof.
∎
The proof
Proposition
3.9
is based on a primal argument.
It utilizes the equivalence that we established in
Proposition
3.7
and the properties of marginalized perfectly calibrated predictor (see
Definition
3.10
and
Lemma
3.8
).
Proof of
Proposition
3.9
.
Let us fix any predictor
\tilde{h}
, and consider the predictor
\tilde{f}
that is generated, according to (
3
), by the perfectly calibrated predictor
\tilde{g}
and the miscalibration plan
\chi
, which are constructed according to (
4
) with input
\tilde{h}
.
By
Proposition
3.5
, we know that
\text{\bf Payoff}\!\left[{\tilde{h}}\right]=\text{\bf Payoff}\!\left[{\tilde{f}}\right]
.
To show the optimality of
\tilde{h}
, it suffices to show the optimality of predictor
\tilde{f}
.
By
Corollary
3.6
, it suffices to show that for any
\varepsilon
-calibrated predictor
\tilde{f}^{\dagger}\in\mathcal{F}^{\rm EI}_{\varepsilon}
, we have
\displaystyle\text{\bf Payoff}\!\left[{\tilde{f}}\right]-\text{\bf Payoff}\!\left[{\tilde{f}^{\dagger}}\right]=\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)U(p)~{\mathrm{d}}p-\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}^{\dagger}_{i}(p)U(p)~{\mathrm{d}}p\geq 0
(17)
Since we know that
\Gamma(q)\geq U(q)
for all
q\in[0,1]
, and condition
\mathsf{supp}(\tilde{f})\subseteq\{p\in[0,1]:\Gamma(p)=U(p)\}
, we have
\displaystyle 0=\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\left(U(p)-\Gamma(p)\right)~{\mathrm{d}}p\geq\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}^{\dagger}_{i}(p)\cdot\left(U(p)-\Gamma(p)\right)~{\mathrm{d}}p~.
Rearranging the above inequality, we then have
LHS of
(
17
)
\displaystyle\geq\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\Gamma(p)~{\mathrm{d}}p-\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}^{\dagger}_{i}(p)\Gamma(p)~{\mathrm{d}}p~.
(18)
Now it suffices to show that RHS of (
18
) is always non-negative.
To see this, recall that by
Proposition
3.5
, for any
\tilde{f}\in\mathcal{F}^{\rm EI}_{\varepsilon}
, there must exist a pair of perfect calibrated predictor
\tilde{g}
and a feasible miscalibration plan
\chi
such that
\displaystyle\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\overset{(a)}{=}\sum\nolimits_{i\in[n]}\lambda_{i}\int_{0}^{1}\tilde{g}_{i}(q)\cdot\frac{\chi(q,p)}{\sum_{j\in[n]}\lambda_{j}\cdot\tilde{g}_{j}(q)}\,{\mathrm{d}}q=\int_{0}^{1}g(q)\chi(p\mid q)~{\mathrm{d}}q~,
where equality (a) is by Eqn. (
3
), and
\chi(p\mid q)\triangleq\frac{\chi(q,p)}{\sum_{j\in[n]}\lambda_{j}\cdot\tilde{g}_{j}(q)}
for
q,p\in[0,1]
,
and
g
is the marginalized predictor from
\tilde{g}
.
Thus, we can write RHS of (
18
) as follows:
RHS of
(
18
)
\displaystyle=\int_{0}^{1}g(q)\int_{0}^{1}\chi(p\mid q)\Gamma(p)~{\mathrm{d}}p{\mathrm{d}}q-\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}^{\dagger}_{i}(p)\Gamma(p)~{\mathrm{d}}p
\displaystyle\overset{(a)}{=}\int_{0}^{1}g(q)\int_{0}^{1}\chi(p\mid q)\cdot\left(\Gamma(q)+\alpha\cdot|p-q|\right)~{\mathrm{d}}p{\mathrm{d}}q-\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}^{\dagger}_{i}(p)\Gamma(p)~{\mathrm{d}}p~,
(19)
where
\alpha\triangleq\max_{p}|(\Gamma(p))^{\prime}|
, and equality (a) holds by condition (ii-b) where for any
\chi(q,p)>0
(i.e.,
\chi(p\mid q)>0
) with
p\neq q
, we know
q,p
must lie in linear tails of function
\Gamma
, and thus we have
\Gamma(p)=\Gamma(q)+\alpha\cdot|p-q|
.
When
\alpha=0
, we know that function
\Gamma(p)\equiv C
for some constant
C\geq 0
(here
C\geq 0
is due to the fact that
\Gamma(x)\geq U(x)\geq 0
for all
x\in[0,1]
).
Thus,
\text{RHS of }\eqref{ineq:goal 3}=C-C=0
.
When
\alpha>0
, then by condition (i), we must have
\displaystyle\text{\bf ECE}\!\left[{\tilde{f}}\right]=\int_{0}^{1}g(q)\int_{0}^{1}\chi(p\mid q)\cdot|p-q|~{\mathrm{d}}p{\mathrm{d}}q=\varepsilon~.
(20)
Thus,
RHS of
(
19
)
\displaystyle=\int_{0}^{1}g(q)\Gamma(q)~{\mathrm{d}}q+\alpha\varepsilon-\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}^{\dagger}_{i}(p)\Gamma(p)~{\mathrm{d}}p
\displaystyle\overset{(a)}{\geq}\int_{0}^{1}g(q)\Gamma(q)~{\mathrm{d}}q+\alpha\cdot\text{\bf ECE}\!\left[{f^{\dagger}}\right]-\int_{0}^{1}f^{\dagger}(p)\Gamma(p)~{\mathrm{d}}p
\displaystyle=\int_{0}^{1}g(q)\Gamma(q)~{\mathrm{d}}q+\alpha\cdot\int_{0}^{1}g^{\dagger}(q)\int_{0}^{1}\chi^{\dagger}(p\mid q)|p-q|~{\mathrm{d}}p{\mathrm{d}}q-\int_{0}^{1}f^{\dagger}(p)\Gamma(p)~{\mathrm{d}}p
(holds similarly due to (
20
))
\displaystyle=\int_{0}^{1}g(q)\Gamma(q)~{\mathrm{d}}q-\int_{0}^{1}g^{\dagger}(q)\int_{0}^{1}\chi^{\dagger}(p\mid q)\left(\Gamma(p)-\alpha|p-q|\right)~{\mathrm{d}}p{\mathrm{d}}q
\displaystyle\geq\int_{0}^{1}g(q)\Gamma(q)~{\mathrm{d}}q-\int_{0}^{1}g^{\dagger}(q)\int_{0}^{1}\chi^{\dagger}(p\mid q)\Gamma(q)~{\mathrm{d}}p{\mathrm{d}}q
(due to
\Gamma(p)-\alpha\cdot|p-q|\leq\Gamma(q),\forall q,p\in[0,1]
)
\displaystyle=\int_{0}^{1}g(q)\Gamma(q)~{\mathrm{d}}q-\int_{0}^{1}g^{\dagger}(q)\Gamma(q)~{\mathrm{d}}q
\displaystyle=\int_{0}^{1}\lambda(q)\Gamma(q)~{\mathrm{d}}q-\int_{0}^{1}g^{\dagger}(q)\Gamma(q)~{\mathrm{d}}q
(by condition (iii-a))
\displaystyle\geq 0~,
(by
Definition
3.10
and convexity of
\Gamma
)
where inequality (a) holds as
\text{\bf ECE}\!\left[{\tilde{f}^{\dagger}}\right]\leq\varepsilon
, and for the predictor
\tilde{f}^{\dagger}\in\mathcal{F}^{\rm EI}_{\varepsilon}
, we also have
\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}^{\dagger}_{i}(p)=\int_{0}^{1}g^{\dagger}(q)\chi^{\dagger}(p\mid q)~{\mathrm{d}}q
.
∎
4
FPTAS for General Setting
In this section, we study the time complexity of computing an optimal
(\varepsilon,\ell_{t})
-calibrated predictor. As the main result of this section, we present an FPTAS (
Algorithm
1
) that works for the general setting (e.g., the sender’s indirect utility can be event-dependent) and for all
\ell_{t}
-norm ECEs.
Theorem 4.1
(FPTAS for general setting)
.
For every persuasive calibration instance, given any
\delta\in(0,1)
, there exists a linear programming (see
4.6
) based algorithm (
Algorithm
1
) that computes a
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}
achieving a
(1-\delta)
-approximation to the optimal
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}^{*}
, i.e.,
\text{\bf Payoff}\!\left[{\tilde{f}}\right]\geq(1-\delta)\cdot\text{\bf Payoff}\!\left[{\tilde{f}^{*}}\right]
. The running time of the algorithm is
\mathsf{poly}(\nicefrac{{1}}{{\delta}},n,m)
, where
n=|\Theta|,m=|\mathcal{A}|
are the number of events and the number of agent’s actions, respectively.
We remark that the running time of
Algorithm
1
in the above theorem does not depend on the ECE budget
\varepsilon
or the exponent parameter
t
in the ECE metric. In
Section
5
, we also present a polynomial-time algorithm to compute the optimal predictor for
\ell_{1}
-norm ECE and
\ell_{\infty}
-norm ECE. Determining whether a polynomial-time algorithm for computing the optimal predictor exists for
\ell_{t}
-norm ECE with other exponent parameters
t\in(1,\infty)
, or proving a computational hardness result, is left as an interesting future direction.
In
Section
4.1
, we introduce the FPTAS (
Algorithm
1
) and provide an overview of its two main technical ingredients and their analysis. In
Sections
4.2
and
4.3
, we present the full details of these two technical ingredients, respectively.
Finally, we prove
Theorem
4.1
in
Section
4.4
.
4.1
Algorithm Description and Analysis Overview
In this section, we first sketch the main algorithmic ingredients of
Algorithm
1
, along with the intuitions and challenges behind them. We then provide details of each ingredient and their corresponding analysis.
To obtain a time-efficient algorithm for computing an approximately optimal predictor, a natural approach is to formulate the principal’s problem as a computationally tractable optimization program (e.g., a linear or convex program). However, due to the calibration error constraint defined on the predictor
\tilde{f}
, this approach is not straightforward. In
Appendix
B
, we explain the failure of some natural optimization program formulations that directly use the predictor as the decision variable and optimize over the entire feasible predictor space
\mathcal{F}_{(\varepsilon,\ell_{t})}
.
Algorithm 1
The FPTAS for the persuasive calibration with general
t\geq 1
1:
Input:
persuasive calibration instance
(\Theta,\lambda,u,v,\mathcal{A},(\varepsilon,\ell_{t}))
, approximation precision
\delta\in(0,1)
.
2:
Solve
\textsc{LP-DiscTwoStep}^{+}_{(\nicefrac{{\delta}}{{3}})}
and let
\{\chi_{i,j}^{*}\}_{i,j:i\leq j}
be its optimal solution.
3:
Use the optimal solution
\{\chi_{i,j}^{*}\}_{i,j:i\leq j}
to
construct the predictor
\tilde{f}
as follows:
\displaystyle\forall i\in[n],~p\in[0,1]:\quad\tilde{f}_{i}(p)\leftarrow\displaystyle\frac{1}{\lambda_{i}}\cdot\int_{0}^{1}\left(\sum\limits_{k\in[i:n]}\chi^{*}_{i,k}(q,p)\cdot\frac{\theta_{k}-q}{\theta_{k}-\theta_{i}}+\sum\limits_{k\in[i-1]}\chi^{*}_{k,i}(q,p)\cdot\frac{q-\theta_{k}}{\theta_{i}-\theta_{k}}\right)\,{\mathrm{d}}q
4:
Output:
predictor
\tilde{f}
.
We overcome the challenge and develop
Algorithm
1
, which contains two main technical ingredients: it combines a generalized two-step framework, which extends the two-step approach in
Section
3.2
from the event-independent setting to the general setting, with a carefully designed discretization scheme.
Ingredient 1: generalized two-step framework.
For the general setting where the principal’s utility may simultaneously depend on the realized event, the agent’s action, and the realized outcome, the two-step framework with the
event-independent
post-processing plan established in
Section
3.2
may not be sufficient. Motivated by this, we introduce a generalized two-step framework in
Section
4.2
. However, if we consider an event-dependent post-processing plan that
fully decouples
the miscalibration across all events, additional non-linear constraints—seemingly intractable—are required. To bypass this issue, we introduce a generalized two-step framework with an
(event-dependent) bi-event post-processing plan
(
Definitions
4.1
and
4.2
), which allows us to formulate an infinite-dimensional (but tractable) linear program
4.3
. Our bi-event post-processing plan is rich enough to ensure that there always exists an optimal predictor that can be generated within our generalized framework (
Proposition
4.3
).
Ingredient 2: Instance-dependent two-layer discretization & rounding-based analysis.
Our FPTAS (
Algorithm
1
) solves a discretized version of
4.3
. Common discretization schemes, such as uniform discretization, are not directly applicable, as they may render the discretized LP infeasible or significantly degrade the objective value due to the ECE budget constraint. To overcome this challenge, in
Section
4.3
, we introduce an instance-dependent discretization scheme (
Definition
4.5
) with a two-layer structure.
First, our scheme constructs a non-uniform
\Theta(\delta)
-net that includes the expected outcomes
\Theta=\{\theta_{1},\dots,\theta_{n}\}
and the discontinuity points
\mathcal{Z}
of the principal’s indirect utility function. Second, for each point in this
\Theta(\delta)
-net, it introduces a finer
\Theta(\delta_{0})
-net within a small neighborhood, where
\delta_{0}
depends not only on the discretization precision
\delta
but also on the ECE budget
\varepsilon
and the norm exponent parameter
t
.
This two-layer structure of our discretization scheme ensures that the discretized LP
4.6
remains feasible, closely approximates the original objective value, and maintains a polynomial size. Finally, we develop a rounding scheme (
Algorithm
2
) to analyze both the feasibility and the objective value of
4.6
. We believe that both our discretization scheme and our rounding argument are of independent interest in the algorithmic information design literature.
4.2
Generalized Two-step Framework: Bi-Event Post-Processing Plan
In this section, we generalize the two-step framework developed in
Section
3.2
from the event-independent setting to the general setting.
In the event-independent setting, where the principal has an event-independent indirect utility,
Proposition
3.5
shows that it suffices to consider predictors from
\mathcal{F}^{\rm EI}_{(\varepsilon,\ell_{t})}
, which can be implemented via an event-independent post-processing plan (
Definition
3.6
).
However, in the general setting where the principal’s utility depends on the realized event,
this sufficiency is no longer guaranteed.
Perhaps the most natural generalization is to allow event-dependent post-processing, by extending
\chi(q,p)
to
\chi_{i}(q,p)
, which depends on the realized event
i
.
However,
fully decoupling
the post-processing plan across events introduces a significant challenge: it requires us to impose a
non-linear
feasibility constraint that ensures
\kappa(p)=q
after post-processing according to
\{\chi_{i}(q,p)\}_{i\in[n]}
. See
Appendix
B
for further discussion.
To address this challenge, rather than fully decoupling the post-processing plans, we propose a more tractable alternative:
an
(event-dependent) bi-event post-processing plan
, which captures pairwise miscalibration between events.
This formulation offers greater flexibility than the event-independent approach, while avoiding the complexity of full decoupling.
The formal definition is as follows.
Definition 4.1
((Event-dependent) Bi-event post-processing plan)
.
An
(event-dependent) bi-event post-processing plan
\chi
is a joint distribution over
[n]\times[n]\times[0,1]\times[0,1]
. We denote by
\chi_{i,j}(q,p)
the probability density (or probability mass for discrete distribution) of
(q,p)\in[0,1]^{2}
under a pair of events
(i,j)
with
i\leq j
.
Fix any
t\geq 1,\varepsilon\geq 0
. A
bi-event
post-processing plan
\chi
is
feasible
under
\ell_{t}
-norm
ECE budget
\varepsilon
if it satisfies
\displaystyle\left(\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\cdot|q-p|^{t}\,{\mathrm{d}}p{\mathrm{d}}q\right)^{\frac{1}{t}}\leq\varepsilon,
(
BiE-Calibration-Feasibility
)
and for every event
i\in[n]
,
\displaystyle\int_{0}^{1}\int_{0}^{1}\left(\sum\nolimits_{k\in[i:n]}\chi_{i,k}(q,p)\cdot\omega_{i,k}(q)+\sum\nolimits_{k\in[i-1]}\chi_{k,i}(q,p)\cdot(1-\omega_{k,i}(q))\right)\,{\mathrm{d}}p{\mathrm{d}}q=\lambda_{i}
(
BiE-Supply-Feasibility
)
where auxiliary contribution ratio
\omega_{i,j}(q)\triangleq\frac{\theta_{j}-q}{\theta_{j}-\theta_{i}}
for
\theta_{i}<\theta_{j}
, and
\omega_{i,j}(q)\triangleq 1
for
\theta_{i}=\theta_{j}
.
When
(t,\varepsilon)
are clear from the context, we simply refer to
\chi
as a feasible bi-event post-processing plan.
The two feasibility constraints for the
bi-event
post-processing plan in
Definition
4.1
can be viewed as a generalization of the analogous constraints for the event-independent post-processing plan in
Definition
3.6
. Additionally, it bypasses the challenge that arises when fully decoupling the post-processing plan across events (see
Appendix
B
) by introducing auxiliary contribution ratios
\{\omega_{i,j}(q)\}
.
The intuition is as follows: consider any pair of events
(i,j)
and prediction
q
. Events
i
and
j
are combined to form a true expected outcome
q
if and only if
the probability mass contributed by event
i
is proportional to
\omega_{i,j}(q)
, while the contribution from event
j
is proportional to
1-\omega_{i,j}(q)
. We formalize our intuition in
Definition
4.2
and
Proposition
4.2
below. We also illustrate it using
Example
4.3
.
29
29
29
Unlike our (event-independent) post-processing plan, in
Definition
4.1
, we do not explicitly consider the perfectly calibrated predictor, as our current goal is to develop an LP for computation rather than characterizing its structure. See also
Footnote
27
.
Definition 4.2
(Bi-event post-processing procedure)
.
Fix any
t\geq 1,\varepsilon\geq 0
. Given any feasible
bi-event
post-processing plan
\chi
, a new (possibly imperfectly calibrated) predictor
\tilde{f}
is
generated
as follows: for every event
i\in[n]
, and prediction
p\in[0,1]
,
\displaystyle\tilde{f}_{i}(p)\leftarrow\displaystyle\frac{1}{\lambda_{i}}\cdot\int_{0}^{1}\left(\sum\nolimits_{k\in[i:n]}\chi_{i,k}(q,p)\cdot\omega_{i,k}(q)+\sum\nolimits_{k\in[i-1]}\chi_{k,i}(q,p)\cdot(1-\omega_{k,i}(q))\right)\,{\mathrm{d}}q
(21)
To simplify the presentation, we also say predictor
\tilde{f}
is
generated by
bi-event
post-processing plan
\chi
.
Example 4.3
(Predictors generated from
bi-event
post-processing procedure)
.
Consider the same two-event setting and predictor
\tilde{f}
as in
Example
3.9
. Predictor
\tilde{f}
can be generated by the following
bi-event
post-processing plan
\chi
:
\chi_{1,1}(0.5,0.125)=0.5
and
\chi_{2,2}(0.5,0.875)=0.5
. It can be verified that for every
t\geq 1
and
\varepsilon\geq\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]
,
bi-event
post-processing plan
\chi
is feasible under
\ell_{t}
-norm ECE budget
\varepsilon
.
Proposition 4.2
.
Fix any
t\geq 1,\varepsilon\geq 0
, and any feasible
bi-event
post-processing plan
\chi
. The predictor
\tilde{f}
generated by
\chi
(in
Definition
4.2
) is well-defined and
(\varepsilon,\ell_{t})
-calibrated, i.e.,
\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\leq\varepsilon
.
Proof of
Proposition
4.2
.
Fix any feasible
bi-event
post-processing plan
\chi
. Consider predictor
\tilde{f}
generated by
\chi
(according to Eqn. (
21
) in
Definition
4.2
). Note that predictor
p
is well-defined since
\int_{0}^{1}\tilde{f}_{i}(p){\mathrm{d}}p=1
for every event
i\in[n]
, which is implied by
BiE-Supply-Feasibility
(in
Definition
4.1
) of
bi-event
post-processing plan
\chi
.
We next bound the
\ell_{t}
-ECE of predictor
\tilde{f}
. Note that
\displaystyle\tilde{f}(p)=\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)=\int_{0}^{1}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\,{\mathrm{d}}q~.
We next argue that for any prediction
p\in[0,1]
, if
\tilde{f}(p)>0
, we have
\displaystyle\left|p-\kappa(p)\right|^{t}\leq\int_{0}^{1}\frac{1}{\tilde{f}(p)}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\cdot|p-q|^{t}\,{\mathrm{d}}q
(22)
To see the above inequality, we notice that the true expected outcome
\kappa(p)
of prediction
p
under predictor
\tilde{f}
is
\displaystyle\kappa(p)
\displaystyle=\frac{1}{\tilde{f}(p)}\sum\nolimits_{i\in[n]}\theta_{i}\cdot\left(\int_{0}^{1}\sum\nolimits_{k\in[i:n]}\chi_{i,k}(q,p)\omega_{i,k}(q)\,{\mathrm{d}}q+\int_{0}^{1}\sum\nolimits_{k\in[i-1]}\chi_{k,i}(q,p)(1-\omega_{k,i}(q))\,{\mathrm{d}}q\right)
\displaystyle=\frac{1}{\tilde{f}(p)}\sum\nolimits_{(i,j):i\leq j}\int_{0}^{1}\chi_{i,j}(q,p)\cdot(\omega_{i,j}(q)\cdot\theta_{i}+(1-\omega_{i,j}(q))\cdot\theta_{j})\,{\mathrm{d}}q=\frac{1}{\tilde{f}(p)}\sum\nolimits_{(i,j):i\leq j}\int_{0}^{1}\chi_{i,j}(q,p)\cdot q\,{\mathrm{d}}q
Thus, as function
x\mapsto|p-x|^{t}
is convex for
t\geq 1
, the inequality (
22
) holds by Jensen’s inequality.
Consequently, we have
\displaystyle\left(\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\right)^{t}=\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\left|p-\kappa(p)\right|^{t}\,{\mathrm{d}}p\leq\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\cdot|p-q|^{t}\,{\mathrm{d}}q{\mathrm{d}}p\leq\varepsilon^{t}
where the last inequality holds due to
BiE-Calibration-Feasibility
(in
Definition
4.1
) of
bi-event
post-processing plan
\chi
.
This finishes the proof of
Proposition
4.2
.
∎
So far, we have extended the two-step framework from the event-independent setting, which uses the event-independent post-processing plan, to the general setting, which uses the
bi-event
post-processing plan. While the event-independent post-processing plan may not be sufficient to generate the optimal predictor in the general setting, the key question now is whether the more general
bi-event
post-processing plan is sufficient. The following proposition answers this question affirmatively—considering the
bi-event
post-processing plan is indeed sufficient to generate the optimal predictor.
Proposition 4.3
.
For every persuasive calibration instance, the principal’s expected utility under the optimal
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}^{*}
is equal to the optimal objective value of the following linear program with variables
\{\chi_{i,j}(q,p)\}_{i,j\in[n]:i\leq j,q,p\in[0,1]}
:
\displaystyle\begin{array}[]{rlll}\max\limits_{\chi\geq 0}&\displaystyle\sum\limits_{(i,j):i\leq j}\int_{0}^{1}\int_{0}^{1}\chi_{i,j}(q,p)\cdot U_{i,j}(q,p)~{\mathrm{d}}p{\mathrm{d}}q&\text{s.t.}&\\
(\ref{eq:bed feasible miscal cal budget})&\displaystyle\left(\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\cdot|q-p|^{t}\,{\mathrm{d}}p{\mathrm{d}}q\right)^{\frac{1}{t}}\leq\varepsilon,&\\
(\ref{eq:bed feasible miscal supp})&&\\
\lx@intercol\hfil\qquad\displaystyle\int_{0}^{1}\int_{0}^{1}\left(\sum\limits_{k\in[i:n]}\chi_{i,k}(q,p)\cdot\omega_{i,k}(q)+\sum\limits_{k\in[i-1]}\chi_{k,i}(q,p)\cdot(1-\omega_{k,i}(q))\right)\,{\mathrm{d}}p{\mathrm{d}}q=\lambda_{i}\hfil\lx@intercol&i\in[n]\end{array}
where, with a slight abuse of notation, we expand the definition of indirect utility function as: for every pair of events
(i,j)
with
i\leq j
and predictions
q,p\in[0,1]
,
\displaystyle U_{i,j}(q,p)
\displaystyle\triangleq\omega_{i,j}(q)\cdot U_{i}(p)+(1-\omega_{i,j}(q))\cdot U_{j}(p)
Moreover, every optimal solution of
4.3
can be converted into an optimal
\varepsilon
-calibrated predictor
\tilde{f}^{*}
using Eqn. (
21
).
We remark that
4.3
is an infinite-dimensional linear program. In the next subsection, we introduce an instance-dependent discretization scheme for this program, providing a provable guarantee on the discretization error. We conclude this section by proving
Proposition
4.3
.
Proof of
Proposition
4.3
.
We first prove the direction that
given any feasible solution
\chi
to
4.3
,
there exists an
\varepsilon
-calibrated predictor
\tilde{f}
such that the induced expected utility of the principal exactly equals to the objective value of the solution
g,\chi
in
4.3
.
Due to the constraints in
4.3
, the feasible solution
\chi
is also a feasible
bi-event
post-processing plan. Invoking
Proposition
4.2
, the predictor
\tilde{f}
generated by
bi-event
post-processing plan
\chi
(according to Eqn. (
21
)) is well-defined ans
(\varepsilon,\ell_{t})
-calibrated. It suffices to compute the expected utility of the principal from predictor
\tilde{f}
:
\displaystyle\text{\bf Payoff}\!\left[{\tilde{f}}\right]=~
\displaystyle\int_{0}^{1}\sum\limits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)U_{i}(p)\,{\mathrm{d}}p
\displaystyle=~
\displaystyle\int_{0}^{1}\int_{0}^{1}\sum\limits_{i\in[n]}\left(\sum\limits_{k\in[i:n]}\chi_{i,k}(q,p)\cdot\omega_{i,k}(q)+\sum\limits_{k\in[i-1]}\chi_{k,i}(q,p)\cdot\left(1-\omega_{k,i}(q)\right)\right)\cdot U_{i}(p)\,{\mathrm{d}}p{\mathrm{d}}q
\displaystyle=~
\displaystyle\sum\limits_{(i,j):i\leq j}\int_{0}^{1}\int_{0}^{1}\chi_{i,j}(q,p)\cdot U_{i,j}(q,p)~{\mathrm{d}}p{\mathrm{d}}q
where the last term is exactly the objective value of solution
\chi
in
4.3
.
We thus complete the first direction.
We next prove the reverse direction:
for any
\varepsilon
-calibrated predictor
\tilde{f}
, there exists
\chi
that is a feasible solution to
4.3
, and its objective value in
4.3
exactly equals to the payoff (i.e., the expected utility of the principal)
\text{\bf Payoff}\!\left[{\tilde{f}}\right]
under predictor
\tilde{f}
.
For this direction, our analysis uses the following technical lemma developed in
Feng et al. 2022
:
Lemma 4.4
(
Feng et al. 2022
)
.
Let
X
be a random variable
with discrete support
\mathsf{supp}(X)
.
There exists a
positive integer
K
,
a finite set of
K
random variables
\{X_{k}\}_{k\in[K]}
,
and convex combination coefficients
\mathbf{b}\in[0,1]^{K}
with
\sum_{k\in[K]}b_{k}=1
such that:
(i)
Bayesian-plausibility
: for each
k\in[K]
,
\mathbb{E}\!\left[{X_{k}}\right]=\mathbb{E}\!\left[{X}\right]
;
(ii)
Binary-support
:
for each
k\in[K]
, the size of
X_{k}
’s support is at most 2,
i.e.,
|\mathsf{supp}(X_{k})|\leq 2
(iii)
Consistency
:
for each
x\in\mathsf{supp}(X)
,
\mathbb{P}\!\left[{X=x}\right]=\sum_{k\in[K]}b_{k}\cdot\mathbb{P}\!\left[{X_{k}=x}\right]
Given any
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}
, we first construct a (hypothetical) predictor
\tilde{f}^{\dagger}
as follows:
Initialize
\mathsf{supp}(\tilde{f}^{\dagger})\leftarrow\emptyset
.
For each
p\in\mathsf{supp}(\tilde{f})
, we consider a random variable
X
with the following distribution
\displaystyle\mathbb{P}\!\left[{X=\theta_{i}}\right]=\frac{\lambda_{i}\tilde{f}_{i}(p)}{\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)}~,\quad i\in[n]~.
Let integer
K
, random variables
\{X_{k}\}_{k\in[K]}
,
and convex combination coefficients
\mathbf{b}\in[0,1]^{K}
be the elements in
Lemma
4.4
for the aforementioned random variable
X
.
We consider a new predictor
\tilde{f}^{\dagger}
defined as follows:
Add
K
copies
\{p^{(1)},\dots,p^{(K)}\}
of prediction
p
into the support space
\mathsf{supp}(\tilde{f}^{\dagger})
,
i.e.,
\mathsf{supp}(\tilde{f}^{\dagger})\leftarrow\mathsf{supp}(\tilde{f}^{\dagger})\cup\{p^{(1)},\dots,p^{(K)}\}
.
For each
k\in[K]
, set
\tilde{f}^{\dagger}_{i}(p^{(k)})\leftarrow\frac{1}{\lambda_{i}}{b_{k}\cdot\mathbb{P}\!\left[{X_{k}=\theta_{i}}\right]\cdot{(\sum_{j\in[n]}\lambda_{j}\tilde{f}_{j}(p))}}
.
Note that this construction ensures that
\displaystyle\sum_{k\in[K]}\tilde{f}^{\dagger}_{i}(p^{(k)})
\displaystyle=\sum_{k\in[K]}\frac{1}{\lambda_{i}}{b_{k}\cdot\mathbb{P}\!\left[{X_{k}=\theta_{i}}\right]\cdot{\left(\sum_{j\in[n]}\lambda_{j}\tilde{f}_{j}(p)\right)}}\overset{(a)}{=}\frac{1}{\lambda_{i}}\mathbb{P}\!\left[{X=\theta_{i}}\right]\cdot{\left(\sum_{j\in[n]}\lambda_{j}\tilde{f}_{j}(p)\right)}=\tilde{f}_{i}(p)
where equality (a) holds due to the “Consistency” property
in
Lemma
4.4
.
Hence, the constructed predictor
\tilde{f}^{\dagger}
is a valid distribution.
Moreover, it can be verified that
\text{\bf ECE}_{t}\!\left[{\tilde{f}^{\dagger}}\right]=\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]
as
\displaystyle\left(\text{\bf ECE}_{t}\!\left[{\tilde{f}^{\dagger}}\right]\right)^{t}
\displaystyle=\int_{p\in\mathsf{supp}(\tilde{f})}\sum\nolimits_{k\in[K]}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p^{(k)})\cdot\left|p^{(k)}-\kappa(p^{(k)})\right|^{t}\,{\mathrm{d}}p
\displaystyle\overset{(a)}{=}\int_{p\in\mathsf{supp}(\tilde{f})}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\left|p-\kappa(p)\right|^{t}\,{\mathrm{d}}p=\left(\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\right)^{t}~,
where equality (a) holds due to the “Bayesian-plausibility” property in
Lemma
4.4
.
Finally, we also have
\text{\bf Payoff}\!\left[{\tilde{f}^{\dagger}}\right]=\text{\bf Payoff}\!\left[{\tilde{f}}\right]
as
\displaystyle\text{\bf Payoff}\!\left[{\tilde{f}^{\dagger}}\right]=\int_{p\in\mathsf{supp}(\tilde{f})}\sum\nolimits_{k\in[K]}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p^{(k)})\cdot U_{i}(p^{(k)})\,{\mathrm{d}}p=\text{\bf Payoff}\!\left[{\tilde{f}}\right]~,
where we again use the “Bayesian-plausibility” property in
Lemma
4.4
.
By construction, the predictor
\tilde{f}^{\dagger}
has the following property:
|\{i:\tilde{f}^{\dagger}_{i}(p^{(k)})>0\}|\leq 2
due to the “Binary-support” property in
Lemma
4.4
.
Now based on the constructed predictor
\tilde{f}^{\dagger}
, we construct solution
\chi
as follows:
for all
p^{(k)}\in\mathsf{supp}(\tilde{f}^{\dagger})
,
\displaystyle\chi_{i,j}(q,p^{(k)})\triangleq\lambda_{i}\tilde{f}^{\dagger}_{i}(p^{(k)})+\lambda_{j}\tilde{f}^{\dagger}_{j}(p^{(k)})~,\quad\text{if }\{i:\tilde{f}^{\dagger}_{i}(p^{(k)})>0\}=\{i,j\}\text{ and }\kappa(p^{(k)})=q
Moreover, for each
p^{(k)}
, we have
\displaystyle\chi_{i,j}(q,p^{(k)})\cdot\omega_{i,j}(q)
\displaystyle=\left(\lambda_{i}\tilde{f}^{\dagger}_{i}(p^{(k)})+\lambda_{j}\tilde{f}^{\dagger}_{j}(p^{(k)})\right)\cdot\omega_{i,j}(q)
(27)
\displaystyle=\left(\lambda_{i}\tilde{f}^{\dagger}_{i}(p^{(k)})+\lambda_{i}\tilde{f}^{\dagger}_{i}(p^{(k)})\cdot\frac{1-\omega_{i,j}(q)}{\omega_{i,j}(q)}\right)\cdot\omega_{i,j}(q)=\lambda_{i}\tilde{f}^{\dagger}_{i}(p^{(k)})
\displaystyle\chi_{i,j}(q,p^{(k)})\cdot(1-\omega_{i,j}(q))
\displaystyle=\left(\lambda_{j}\tilde{f}^{\dagger}_{j}(p^{(k)})\frac{\omega_{i,j}(q)}{1-\omega_{i,j}(q)}+\lambda_{j}\tilde{f}^{\dagger}_{j}(p^{(k)})\right)\cdot(1-\omega_{i,j}(q))=\lambda_{j}\tilde{f}^{\dagger}_{j}(p^{(k)})
Thus, with above observations, we have, for any
k\in[n]
,
\displaystyle\int_{0}^{1}\int_{0}^{1}\left(\sum\nolimits_{j\in[k,n]}\chi_{k,j}(q,p)\cdot\omega_{k,j}(q)+\sum\nolimits_{i\in[k-1]}\chi_{i,k}(q,p)\cdot(1-\omega_{i,k}(q))\right)\,{\mathrm{d}}q{\mathrm{d}}p
\displaystyle=~
\displaystyle\int_{p\in\mathsf{supp}(\tilde{f})}\sum_{k=1}^{K}\lambda_{k}\tilde{f}^{\dagger}_{k}(p^{(k)})\,{\mathrm{d}}p=\lambda_{k}\int_{p\in\mathsf{supp}(\tilde{f})}\tilde{f}_{k}(p)\,{\mathrm{d}}p=\lambda_{k}~.
Moreover, the first constraint is also satisfied as we have
\displaystyle\int_{0}^{1}\int_{0}^{1}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\cdot|q-p|^{t}\,{\mathrm{d}}q{\mathrm{d}}p
\displaystyle=~
\displaystyle\int_{p\in\mathsf{supp}(\tilde{f})}\int_{0}^{1}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot|q-p|^{t}\,{\mathrm{d}}q{\mathrm{d}}p=\left(\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\right)^{t}\leq\varepsilon^{t}~.
Finally, we compute the objective value of the constructed solution
\chi
,
\displaystyle\sum\nolimits_{(i,j):i\leq j}\int_{0}^{1}\int_{0}^{1}\chi_{i,j}(q,p)\cdot U_{i,j}(q,p)~{\mathrm{d}}p{\mathrm{d}}q\overset{(a)}{=}\text{\bf Payoff}\!\left[{\tilde{f}^{\dagger}}\right]=\text{\bf Payoff}\!\left[{\tilde{f}}\right]~,
where equality (a) holds by definition of
U_{i,j}(q,p)
, and the property of
\chi
established in (
27
).
We thus finish the second direction and conclude the proof of
Proposition
4.3
.
∎
4.3
Instance-Dependent Discretization and Rounding Scheme
In this section, we introduce the second key technical ingredient of
Algorithm
1
: a discretization scheme for the infinite-dimensional linear program
4.3
. Our goal is to develop this scheme with a provable guarantee on the discretization error. To achieve this, an ideal discretization scheme and its induced discretized linear program (LP) should to satisfy the following two properties:
1.
The discretized LP has a feasible solution.
2.
Given an optimal solution to original LP
4.3
, we can identify a feasible solution in the discretized LP whose objective value is close and the ECE is weakly smaller.
Both properties introduce challenges in applying common discretization schemes, such as uniform discretization, to our problem. (See
Example
4.4
where the discretized LP becomes infeasible under uniform discretization.) While similar challenges arising from the first property has been observed in the algorithmic information design literature
(
Agrawal et al. 2023
, e.g.,)
, the second challenge is, to the best of our knowledge, unique due to the ECE budget constraint.
In particular, suppose the discretized LP under uniform discretization with precision
\delta
happens to be feasible. A natural rounding approach would then convert a feasible solution into a discretized feasible solution by rounding each
\chi_{i,j}(q,p)
to
\chi_{i,j}(q^{\prime},p^{\prime})
, where
(q^{\prime},p^{\prime})
is the closest discretized point to
(q,p)
. However, after this naive rounding, the ECE may increase by
\Theta(\delta)
, which could be significantly larger than the ECE budget
\varepsilon
.
To ensure that the ECE increment remains controlled under this rounding procedure, we would need to set the discretization precision as
\delta\leftarrow\Theta(\varepsilon)
, i.e., on the same order as the ECE budget
\varepsilon
. However, with such a discretization precision, the size of the discretized set and the corresponding discretized LP would have a polynomial dependence on
\varepsilon
, which prevents us from obtaining the FPTAS stated in
Theorem
4.1
.
Example 4.4
(The failure of uniform discretization)
.
Consider a three-event setting with
\{\theta_{i}\}_{i\in[3]}
and a zero ECE budget
\varepsilon=0
, i.e., predictor is feasible if and only if it is perfectly calibrated.
Now, consider a uniform-grid-only discretization scheme
\mathcal{S}_{\delta}=\{\delta,2\delta,\ldots\}\cap[0,1]
. Suppose the event distribution
\lambda
assigns negligible probabilities to the first and third events, and the true expected outcome for the second event,
\theta_{2}
, is not in the the discretized set
\mathcal{S}_{\delta}
(i.e.,
\theta_{2}\notin\mathcal{S}_{\delta}
), then it can be verified with
Lemma
3.8
that it is impossible to construct any perfectly calibrated predictor whose support lies entirely on the grid points in
\mathcal{S}_{\delta}
.
Therefore, no feasible predictor exists if we restrict its support to discretized set
\mathcal{S}_{\delta}
.
We overcome the two aforementioned challenges by introducing an instance-dependent two-layer discretization scheme (
Definition
4.5
). Loosely speaking, to ensure that the discretized LP remains feasible, our scheme first constructs a non-uniform
\Theta(\delta)
-net that includes discretized points corresponding to the expected outcomes
\Theta=\{\theta_{1},\dots,\theta_{n}\}
and the discontinuity points
\mathcal{Z}
of the principal’s indirect utility function.
Additionally, for every point in this
\Theta(\delta)
-net, we introduce a finer “multiplicative
\Theta(\delta\varepsilon^{t})
-net” within a tiny neighborhood of length
\Theta(\varepsilon^{t})
(see formal construction in
Definition
4.5
). By analyzing the optimal solution of the original program
4.3
, we argue that locally refining the grid within these small neighborhoods is sufficient to approximately preserve the optimal objective value while keeping ECE variations under control (
Lemmas
4.6
and
4.7
).
With this approach, the size of the discretized set remains polynomial in the problem input and the discretization parameter
\delta
(
4.5
), enabling the construction of an FPTAS.
Definition 4.5
(Instance-dependent two-layer discretization scheme)
.
Given any discretization parameter
\delta\in(0,\nicefrac{{1}}{{3}})
, define
discretized set
\mathcal{S}_{\delta}
of the space
[0,1]
for both true expected outcomes and the predictions as follows:
\displaystyle\mathcal{S}_{\delta}\triangleq\underbrace{\left(\{0,\delta,2\delta,\ldots\}\cap[0,1]\right)\cup\Theta\cup\mathcal{Z}}_{\text{``first global layer''}}\cup\underbrace{\left\{z\pm(\delta_{0}\cdot(1+\delta)^{s})^{\nicefrac{{1}}{{t}}}\right\}_{z\in\mathcal{Z}\cup\Theta,s\in[0:S]}}_{\text{``second local layer''}}
where
\mathcal{Z}
is the set of all discontinuity points of the sender’s indirect utility function
\{U_{i}\}_{i\in[n]}
,
\delta_{0}\triangleq\varepsilon^{t}\cdot\delta
,
and
S\triangleq\lceil\frac{2}{\ln(1+\delta)}\ln\frac{1}{\delta}\rceil
.
Although our discretization scheme above depends on the ECE budget
\varepsilon
and the norm exponent parameter
t
, the number of discretized points in the set only depends on the problem instance and discretization parameter
\delta
.
Claim 4.5
.
Given any discretization parameter
\delta\in(0,\nicefrac{{1}}{{3}})
,
the size of the discretized set
\mathcal{S}_{\delta}
defined in
Definition
4.5
satisfies
|\mathcal{S}_{\delta}|=O(\frac{1}{\delta}+\frac{m+n}{\ln(1+\delta)}\ln\frac{1}{\delta})
,
where
n=|\Theta|,m=|\mathcal{A}|
are the number of events and the number of agent’s actions, respectively.
Proof.
Since the agent has
m
, the discontinuity points of the sender’s indirect utility function
\{U_{i}\}_{i\in[n]}
is at most
m+1
.
Thus, the size of the discretized set
\mathcal{S}_{\delta}
in the statement holds by construction.
∎
Given the discretization scheme, we are ready to present the discretized LP
4.6
and its discretization error guarantee.
Lemma 4.6
(Discretized LP and discretization error guarantee)
.
Given any discretization parameter
\delta\in(0,\nicefrac{{1}}{{3}})
, consider the following discretized version of
4.3
:
\displaystyle\begin{array}[]{rlll}\max\limits_{\chi\geq 0}&\displaystyle\sum\limits_{(i,j):i\leq j}\sum\limits_{p,q\in\mathcal{S}_{\delta}}\chi_{i,j}(q,p)\cdot U_{i,j}(q,p)&\text{s.t.}&\\
&\displaystyle\sum\limits_{p,q\in\mathcal{S}_{\delta}}\sum\limits_{(i,j):i\leq j}\chi_{i,j}(q,p)\cdot|q-p|^{t}\leq\varepsilon^{t},&\\
&\displaystyle\sum\limits_{p,q\in\mathcal{S}_{\delta}}\left(\sum\limits_{k\in[i:n]}\chi_{i,k}(q,p)\cdot\omega_{i,k}(q)+\sum\limits_{k\in[i-1]}\chi_{k,i}(q,p)\cdot(1-\omega_{k,i}(q))\right)\,{\mathrm{d}}p{\mathrm{d}}q=\lambda_{i},&i\in[n]\end{array}
where discretized set
\mathcal{S}_{\delta}
is defined in
Definition
4.5
. Then, the following three properties hold:
(i)
4.6
is a feasible linear program with
\mathsf{poly}(n,m,\nicefrac{{1}}{{\delta}})
size, where
n=|\Theta|,m=|\mathcal{A}|
are the number of events and the number of agent’s actions, respectively.
(ii)
Every feasible solution of
4.6
is also a feasible solution of
4.3
.
(iii)
The optimal objective value of
4.6
is a
(1-3\delta)
-approximation to the optimal objective value of
4.3
, i.e.,
\displaystyle\text{\bf OBJ}\!\left[{\text{\ref{eq:decoupled opt general discre}}}\right]\geq(1-3\delta)\cdot\text{\bf OBJ}\!\left[{\text{\ref{eq:decoupled opt general}}}\right]~.
In
Lemma
4.6
, the second property follows directly from the construction of
4.6
.
In the remainder of this section, we develop a rounding argument to establish feasibility and bound the discretization error of
4.6
.
A rounding scheme for analyzing
4.6
.
To show
Lemma
4.6
, we argue that (1) an optimal solution to
4.3
can, via a rounding scheme (see
Algorithm
2
), be converted to a feasible solution to
4.6
; (2) the converted solution has a close objective value to the original solution.
Before introducing the rounding scheme, we first observe that it is without loss to consider an optimal solution
\chi
to
4.3
such that any generated prediction lies in the set
\mathcal{S}_{\delta}
.
Lemma 4.7
.
In
4.3
, there exists an optimal solution
\chi
such that for any
\chi_{i,j}(q,p)>0
, it satisfies that
p\in\mathcal{Z}\cup\Theta
.
The intuition behind this result is that the principal’s indirect utility function,
U_{i}
, is piecewise constant. Consequently, if the true expected outcome
q
and the prediction
p
fall into different constant segments, it is always possible—without loss—to modify the predictor so that it “miscalibrates” true expected outcome
q
to a discontinuity point. Conversely, if they lie within the same constant segment, we can distribute true expected outcome
q
across a pair of events or discontinuity points and then generate perfectly calibrated predictions for these points.
Proof of
Lemma
4.7
.
Recall that
\mathcal{Z}\triangleq\{z_{k}\}_{k\in[m]}
denotes the set of all discontinuity points in the principal’s indirect utility function.
Fix any feasible solution
\chi
to
4.3
,
for any pair of
(q,p)
with
\chi_{i,j}(q,p)>0
and
p\notin\mathcal{Z}
, we consider two possible cases:
Suppose
p\in(z_{k},z_{k+1})
and
q\in(z_{l},z_{l+1})
where
kl
). Consider a new solution that,
instead of miscalibrating
q
to
p
, it miscalibrates
q
to
z_{k+1}
(or
z_{k}
).
This adjustment weakly decreases the calibration error while weakly improving the expected utility of the principal, due to the upper semi-continuity of the principal’s indirect utility function (see Footnote
15
).
Suppose both
p,q\in(z_{k},z_{k+1})
.
In this case, it is without loss to assume
q=p
, since otherwise the solution incurs additional calibration error without any improvement in expected utility of the principal.
Suppose further that
q\in(\theta_{i},\theta_{j})
.
Define
q_{L}\triangleq\theta_{i}\vee z_{k}
and let
q_{R}\triangleq\theta_{j}\wedge z_{k+1}
.
Now consider a modified solution that, instead of contracting the true expected outcomes
\theta_{i},\theta_{j}
to
q
, it contracts them to
q_{L},q_{R}
.
Notice that this is always feasible as
\theta_{i}\leq q_{L}\leq q_{R}\leq\theta_{j}
.
Now this new solution generates perfectly calibrated predictions from these true expected outcomes
q_{L},q_{R}
.
Since the calibration error does not increase and the expected utility of the principal weakly improves (again due to upper semi-continuity – see Footnote
15
), the modified solution is at least as good as the original.
Combing the two cases, we complete the proof of
Lemma
4.7
.
∎
By
Lemma
4.7
, we only need to round the true expected outcome
q
so that it lies in the set
\mathcal{S}_{\delta}
.
At a high-level, our rounding scheme proceeds in two steps:
Step 1 (Lines
8
-
9
).
In this step, for each
\chi_{i,j}(q,p)>0
, we use
\delta^{\dagger}
fraction of it to generate perfectly calibrated predictions. By doing this, we save some calibration error so that we can have enough buffer for the potential increase of calibration error in the later rounding steps.
Step 2 (Lines
11
-
20
).
In this step, given a pair
(q,p)
with
\chi_{i,j}(q,p)>0
, we round the true expected outcome
q
, using the remaining fraction
1-\delta^{\dagger}
of
\chi_{i,j}(q,p)
, to two grid points
q_{L},q_{R}\in\mathcal{S}_{\delta}
.
We then consider three possible cases, depending on the distance
|q-p|
.
In
Case I and Case II
where the distance
|q-p|
is not too large, we round
q
to
q_{L},q_{R}
and then miscalibrate these points to the prediction
p
as follows:
\displaystyle\begin{split}\chi^{\dagger}_{i,j}(q_{L},p)&\leftarrow\chi^{\dagger}_{i,j}(q_{L},p)+{(1-\delta^{\dagger})}\chi_{i,j}(q,p)\frac{q_{R}-q}{q_{R}-q_{L}}\\
\chi^{\dagger}_{i,j}(q_{R},p)&\leftarrow\chi^{\dagger}_{i,j}(q_{R},p)+{(1-\delta^{\dagger})}\chi_{i,j}(q,p)\left(1-\frac{q_{R}-q}{q_{R}-q_{L}}\right)\end{split}
(31)
where the ratio
\frac{q_{R}-q}{q_{R}-q_{L}}
ensures that, after rounding, the constructed
\chi^{\dagger}
satisfies the second constraint in
4.6
.
We carefully choose the grid points
q_{L},q_{R}\in\mathcal{S}_{\delta}
so that, after rounding, the calibration error does not increase significantly. Note that for these two cases, the expected utility of the principal remains unchanged after rounding.
In
Case III
where the distance
|q-p|
is very large, we use the remaining fraction
1-\delta^{\dagger}
of
\chi_{i,j}(q,p)
to generate perfectly calibrated predictions.
In this case, there is no increase in calibration error. Furthermore, by the condition defining this case, we can also argue that any loss of the expected utility of the principal is upper-bounded by a factor of
\delta(1+\delta)
.
Algorithm 2
Rounding scheme of
\chi
for the discretization error analysis
1:
Input:
a feasible solution
\chi
to
4.3
;
2:
Input:
\delta>0,\mathcal{S}_{\delta}
and
\delta_{0}=\delta\cdot\varepsilon^{t}
, and let
\delta^{\dagger}\leftarrow 1-\frac{1}{1+2\delta}
3:
Output:
a feasible solution
\chi^{\dagger}
to
4.6
.
4:
Initialize:
\chi^{\dagger}_{i,j}(q,p)\leftarrow 0
for all
i,j\in[n]
and all
q,p\in\mathcal{S}_{\delta}
.
5:
for
every
(q,p)\in[0,1]^{2}
with
\chi_{i,j}(q,p)>0
do
/* Without loss consider
p\leq q
*/
6:
/* Without loss consider
p\in\mathcal{Z}\cup\Theta
. */
7:
/* Below we use
\delta^{\dagger}
fraction of
\chi_{i,j}(q,p)
to induce perfectly calibrated predictions. */
8:
\chi^{\dagger}_{i,j}(\theta_{i},\theta_{i})\leftarrow\chi^{\dagger}_{i,j}(\theta_{i},\theta_{i})+{\delta^{\dagger}}\cdot\chi_{i,j}(q,p)\cdot\omega_{i,j}(q)
.
9:
\chi^{\dagger}_{i,j}(\theta_{j},\theta_{j})\leftarrow\chi^{\dagger}_{i,j}(\theta_{j},\theta_{j})+{\delta^{\dagger}}\cdot\chi_{i,j}(q,p)\cdot(1-\omega_{i,j}(q))
.
10:
/* Below we round
q
to be in
\mathcal{S}_{\delta}
. */
11:
if
q-p<\delta_{0}^{\nicefrac{{1}}{{t}}}
then
/* Case I */
12:
Set
q_{L}\leftarrow\theta_{i}\vee p
,
q_{R}\leftarrow(p+\delta_{0}^{\nicefrac{{1}}{{t}}})\wedge\theta_{j}
.
/* When
i=j
, we must have
q_{L}=\theta_{i}=q_{R}
*/
13:
Round
q
to be
q_{L},q_{R}
according to Eqn. (
31
).
/* We set
\frac{0}{0}=1
when
i=j
happens */
14:
else
if
\delta_{0}^{\nicefrac{{1}}{{t}}}\leq q-p\leq(\delta_{0}\cdot(1+\delta)^{S-1})^{\nicefrac{{1}}{{t}}}
then
/* Case II */
15:
Set
q_{L}\leftarrow\theta_{i}\vee p
,
and set
q_{R}
as defined in
4.8
.
16:
Round
q
to be
q_{L},q_{R}
according to Eqn. (
31
).
17:
else
/* Case III */
18:
\chi^{\dagger}_{i,j}(\theta_{i},\theta_{i})\leftarrow\chi^{\dagger}_{i,j}(\theta_{i},\theta_{i})+{(1-\delta^{\dagger})}\cdot\chi_{i,j}(q,p)\cdot\omega_{i,j}(q)
;
19:
\chi^{\dagger}_{i,j}(\theta_{j},\theta_{j})\leftarrow\chi^{\dagger}_{i,j}(\theta_{j},\theta_{j})+{(1-\delta^{\dagger})}\cdot\chi_{i,j}(q,p)\cdot(1-\omega_{i,j}(q))
.
20:
end
if
21:
end
for
With the rounding scheme (
Algorithm
2
), we are now ready to prove
Lemma
4.6
.
Proof of
Lemma
4.6
.
The property (ii) follows directly from the construction of
4.6
.
We next prove the statements (i) and (iii).
For the simplicity of the presentation, we define
\overline{\text{\bf ECE}}_{t}\!\left[{\chi}\right]\triangleq\int_{0}^{1}\int_{0}^{1}\sum_{i,j:i\leq j}\chi_{i,j}(q,p)\cdot|q-p|^{t}\,{\mathrm{d}}q{\mathrm{d}}p
and
\overline{\text{\bf ECE}}_{t}\!\left[{\chi\mid(q,p)}\right]\triangleq\sum_{i,j:i\leq j}\chi_{i,j}(q,p)\cdot|q-p|^{t}
.
By definition, we have
\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}}\right]=\sum_{q,p}\overline{\text{\bf ECE}}_{t}\!\left[{\chi\mid(q,p)}\right]
.
Let us fix a optimal solution
\chi
to
4.3
that satisfying
Lemma
4.7
.
Below we show that the rounding scheme detailed in
Algorithm
2
which takes the solution
\chi
as input can output a feasible solution
\chi^{\dagger}
to
4.6
, namely, we have
\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}}\right]\leq\varepsilon^{t}
, and its support are restricted to be in the set
\mathcal{S}_{\delta}
; and meanwhile, the output
\chi^{\dagger}
has
(1-3\delta)
-approximate expected utility of the principal to the solution
\chi
.
We analyze the incurred calibration error of the constructed
\chi^{\dagger}
step by step:
•
In Step 1, the constructed
\chi^{\dagger}
has
0
calibration error as it always generates perfectly calibrated predictions.
•
In Step 2 with Case I, the calibration error incurred in
\chi^{\dagger}
can be bounded as follows:
\displaystyle\sum\nolimits_{(q_{L},q_{R},p)\text{ in Case I}}\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}\mid(q_{L},p)}\right]+\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}\mid(q_{R},p)}\right]
\displaystyle=~
\displaystyle\sum\nolimits_{(q_{L},q_{R},p)\text{ in Case I}}\sum\nolimits_{(i,j):i\leq j}\left(\chi^{\dagger}_{i,j}(q_{L},p)\cdot|q_{L}-p|^{t}+\chi^{\dagger}_{i,j}(q_{R},p)\cdot|q_{R}-p|^{t}\right)
\displaystyle\leq~
\displaystyle{(1-\delta^{\dagger})\cdot\delta_{0}}\sum\nolimits_{(q,p)\text{ in Case I}}\sum\nolimits_{(i,j):i\leq j}\left(\chi_{i,j}(q,p)\frac{q_{R}-q}{q_{R}-q_{L}}+\chi_{i,j}(q,p)\left(1-\frac{q_{R}-q}{q_{R}-q_{L}}\right)\right)
(as
q_{L}\leq q_{R}\leq p+\delta_{0}^{\nicefrac{{1}}{{t}}}
)
\displaystyle\leq~
\displaystyle{(1-\delta^{\dagger})\cdot\delta_{0}}~.
•
In Step 2 with Case II, we know that, by construction, we have
\displaystyle\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}\mid(q_{L},p)}\right]
\displaystyle=\sum\nolimits_{(i,j):i\leq j}\chi^{\dagger}_{i,j}(q_{L},p)\cdot|q_{L}-p|^{t}
\displaystyle\leq\sum\nolimits_{(i,j):i\leq j}{(1-\delta^{\dagger})}\chi_{i,j}(q,p)\frac{q_{R}-q}{q_{R}-q_{L}}\cdot|q-p|^{t}
(as
p\leq q_{L}\leq q
)
\displaystyle\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}\mid(q_{R},p)}\right]
\displaystyle=\sum\nolimits_{(i,j):i\leq j}\chi^{\dagger}_{i,j}(q_{R},p)\cdot|q_{R}-p|^{t}
\displaystyle={(1-\delta^{\dagger})}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\left(1-\frac{q_{R}-q}{q_{R}-q_{L}}\right)\cdot|q_{R}-p|^{t}
\displaystyle\leq{(1-\delta^{\dagger})}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\left(1-\frac{q_{R}-q}{q_{R}-q_{L}}\right)\cdot|q_{R}^{\prime}-p|^{t}
(as
p\leq q_{R}\leq q_{R}^{\prime}
)
\displaystyle\leq{(1+\delta)(1-\delta^{\dagger})}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\left(1-\frac{q_{R}-q}{q_{R}-q_{L}}\right)\cdot|q-p|^{t}
Thus, the total calibration error of
\chi^{\dagger}
contributed from this case can be upper bounded by
\displaystyle\sum\nolimits_{(q_{L},q_{R},p)\text{ in Case II}}\left(\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}\mid(q_{L},p)}\right]+\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}\mid(q_{R},p)}\right]\right)
\displaystyle\leq~
\displaystyle(1+\delta)(1-\delta^{\dagger})\cdot\sum\nolimits_{(q,p)\text{ in Case II}}\sum\nolimits_{(i,j):i\leq j}\left(\chi_{i,j}(q,p)\cdot|q-p|^{t}+\chi_{i,j}(q,p)\cdot|q-p|^{t}\right)
\displaystyle=~
\displaystyle(1+\delta)(1-\delta^{\dagger})\cdot\sum\nolimits_{(q,p)\text{ in Case II}}\cdot\overline{\text{\bf ECE}}_{t}\!\left[{\chi\mid(q,p)}\right]
\displaystyle\leq~
\displaystyle(1+\delta)(1-\delta^{\dagger})\overline{\text{\bf ECE}}_{t}\!\left[{\chi}\right]\leq(1+\delta)(1-\delta^{\dagger})\cdot\frac{\delta_{0}}{\delta}~.
(by definition
\delta_{0}=\delta\cdot\varepsilon^{t}
,
\overline{\text{\bf ECE}}_{t}\!\left[{\chi}\right]\leq\varepsilon^{t}
)
•
In Step 2 with Case III, notice that in this case, the constructed
\chi^{\dagger}
always generates perfectly calibrated predictions.
Moreover, the total probability mass for this case cannot be large, as
\displaystyle\overline{\text{\bf ECE}}_{t}\!\left[{\chi}\right]
\displaystyle\geq\sum\nolimits_{(q,p)\text{ in Case III }}\overline{\text{\bf ECE}}_{t}\!\left[{\chi\mid(q,p)}\right]
\displaystyle=\sum\nolimits_{(q,p)\text{ in Case III}}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)|q-p|^{t}
\displaystyle\geq\sum\nolimits_{(q,p)\text{ in Case III}}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\delta_{0}(1+\delta)^{S-1}
(by condition of Case III)
\displaystyle\geq\sum\nolimits_{(q,p)\text{ in Case III}}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\cdot\frac{\overline{\text{\bf ECE}}_{t}\!\left[{\chi}\right]}{\delta{(1+\delta)}}~.
(by definition of
S
)
Thus, in Case III, we must have
\sum\nolimits_{(q,p)\text{ in Case III}}\sum\nolimits_{(i,j):i\leq j}\chi_{i,j}(q,p)\leq\delta
.
Consequently, the loss of the expected utility of the principal in constructed
\chi^{\dagger}
at this case is upper bounded by
\delta{(1+\delta)}\cdot\text{\bf OBJ}\!\left[{\text{\ref{eq:decoupled opt general}}\,\mid\,\chi}\right]
.
Putting all pieces together, we have the following guarantee of the ECE of constructed
\chi
:
\displaystyle\overline{\text{\bf ECE}}_{t}\!\left[{\chi}\right]-\overline{\text{\bf ECE}}_{t}\!\left[{\chi^{\dagger}}\right]
\displaystyle\geq\overline{\text{\bf ECE}}_{t}\!\left[{\chi}\right]-\delta_{0}(1-\delta^{\dagger})-(1+\delta)(1-\delta^{\dagger})\cdot\frac{\delta_{0}}{\delta}
\displaystyle=\delta_{0}\left(\frac{1}{\delta}-(1-\delta^{\dagger})-\frac{(1+\delta)(1-\delta^{\dagger})}{\delta}\right)=0
(by the choice of
\delta^{\dagger}
)
In addition, we have the following guarantee of the expected utility of the principal of constructed
\chi
:
\displaystyle\text{\bf OBJ}\!\left[{\text{\ref{eq:decoupled opt general discre}}\,\mid\,\chi^{\dagger}}\right]
\displaystyle\geq~
\displaystyle\text{\bf OBJ}\!\left[{\text{\ref{eq:decoupled opt general}}\,\mid\,\chi}\right]-\underbrace{\delta^{\dagger}\text{\bf OBJ}\!\left[{\text{\ref{eq:decoupled opt general}}\,\mid\,\chi}\right]}_{\text{payoff loss in Step 1}}-\underbrace{\delta{(1+\delta)}\text{\bf OBJ}\!\left[{\text{\ref{eq:decoupled opt general}}\,\mid\,\chi}\right]}_{\text{payoff loss in Step 2 with Case III}}
\displaystyle\geq~
\displaystyle(1-3\delta)\text{\bf OBJ}\!\left[{\text{\ref{eq:decoupled opt general}}\,\mid\,\chi}\right]
(by the choice of
\delta^{\dagger}
)
We thus finish the proof of
Lemma
4.6
as desired.
∎
Finally, we include
4.8
(and its proof) mentioned in our rounding scheme (
Algorithm
2
).
Claim 4.8
.
In Step 2 with Case II of
Algorithm
2
(line 15), we define
q_{R}^{\prime}\leftarrow p+(q-p)(1+\delta)^{\nicefrac{{1}}{{t}}}
.
When
q_{R}^{\prime}\geq\theta_{j}
, set
q_{R}\leftarrow\theta_{j}
.
When
q_{R}^{\prime}<\theta_{j}
,
there must exist
s\in[S]
such that
p+(\delta_{0}(1+\delta)^{s})^{\nicefrac{{1}}{{t}}}\in[q,q_{R}^{\prime}]
, set
q_{R}\leftarrow p+(\delta_{0}(1+\delta)^{s})^{\nicefrac{{1}}{{t}}}
.
Proof of
4.8
.
To show that when
q_{R}^{\prime}<\theta_{j}
,
there must exist
s\in[S]
such that
p+(\delta_{0}(1+\delta)^{s})^{\nicefrac{{1}}{{t}}}\in[q,q_{R}^{\prime}]
, it suffices to show that there exists
s\in[S]
:
\displaystyle q\leq p+(\delta_{0}(1+\delta)^{s})^{\nicefrac{{1}}{{t}}}\leq q_{R}^{\prime}~\Leftrightarrow~\frac{\ln\frac{(q-p)^{t}}{\delta_{0}}}{\ln(1+\delta)}\leq s\leq\frac{\ln\frac{(q_{R}^{\prime}-p)^{t}}{\delta_{0}}}{\ln(1+\delta)}=1+\frac{\ln\frac{(q-p)^{t}}{\delta_{0}}}{\ln(1+\delta)}~.
By the condition
q-p\geq\delta_{0}^{\nicefrac{{1}}{{t}}}
, we observe that
we must have
\frac{\ln\frac{(q-p)^{t}}{\delta_{0}}}{\ln(1+\delta)}\geq 0
.
We next argue that we must have
q_{R}^{\prime}\leq p+(\delta_{0}(1+\delta)^{S})^{\nicefrac{{1}}{{t}}}
. To see this, we observe
\displaystyle p+(\delta_{0}(1+\delta)^{S})^{\nicefrac{{1}}{{t}}}-q_{R}^{\prime}
\displaystyle=(\delta_{0}(1+\delta)^{S})^{\nicefrac{{1}}{{t}}}-(q-p)(1+\delta)^{\nicefrac{{1}}{{t}}}
\displaystyle\geq(\delta_{0}(1+\delta)^{S})^{\nicefrac{{1}}{{t}}}-(\delta_{0}(1+\delta)^{S-1})^{\nicefrac{{1}}{{t}}}(1+\delta)^{\nicefrac{{1}}{{t}}}=0
where the last equality holds due to the condition of Case II.
Thus, there must exist
s\in[S]
such that
p+(\delta_{0}(1+\delta)^{s})^{\nicefrac{{1}}{{t}}}\in[q,q_{R}^{\prime}]
.
This finishes the proof of
4.8
.
∎
4.4
Analysis of
Algorithm
1
We are ready to analyze
Algorithm
1
and prove
Theorem
4.1
.
Proof of
Theorem
4.1
.
In
Algorithm
1
, it first solves
4.6
, which is a linear program with size
\mathsf{poly}(\nicefrac{{1}}{{\delta}},n,m)
, and then constructs the predictor based on the optimal solution of
5.3
. Both steps require
\mathsf{poly}(\nicefrac{{1}}{{\delta}},n,m)
running time and thus the algorithm is polynomial-time. Finally, the approximation of the algorithm follows
Proposition
4.3
and
Lemma
4.6
. This finishes the proof of
Theorem
4.1
.
∎
5
Polytime Algorithm for
\ell_{1}
-Norm ECE and
\ell_{\infty}
-Norm ECE
In this section, we show that for the most standard ECE metrics, the
K_{1}
ECE, and also the
K_{\infty}
ECE, there exists a polynomial-time algorithm that can compute the optimal
(\varepsilon,\ell_{t})
-calibrated predictor with
t\in\{1,\infty\}
.
Theorem 5.1
(Polynomial-time algorithm for
\ell_{1}
-norm and
\ell_{\infty}
-norm ECE)
.
For every persuasive calibration instance with
\ell_{1}
-norm ECE (resp.
\ell_{\infty}
-norm) ECE, there exists a linear programming (see
5.3
) based algorithm (
Algorithm
3
) that computes an optimal
(\varepsilon,\ell_{1})
-calibrated (resp.
(\varepsilon,\ell_{\infty})
-calibrated) predictor. The running time of the algorithm is
\mathsf{poly}(n,m)
, where
n=|\Theta|,m=|\mathcal{A}|
are the number of events and the number of agent’s actions, respectively.
For
\ell_{1}
-norm or
\ell_{\infty}
-norm ECE, it is not difficult to express the
(\varepsilon,\ell_{t})
-calibration as a linear constraint on
\tilde{f}=\{\tilde{f}_{i}(p)\}_{i\in[n],p\in[0,1]}
. However, to obtain an optimal algorithm with polynomial running time, we also need to restrict the continuous space of predictions to a discrete polynomial-size set. To bypass this challenge, we build on an idea from the algorithmic information design literature.
As an example, in the classic Bayesian persuasion problem
(
Kamenica and Gentzkow 2011
)
, the
revelation principle
assures that it is sufficient to consider signaling schemes that recommend an action. Hence, instead of searching over a (possibly) continuous signal space, it suffices to construct a signaling scheme with a signal space equal to the action space, which is polynomial-sized. However, such an approach seems difficult to apply to our model, as the design space in our model is restricted to predictions rather than arbitrary signals, and the agent in our model follows a much simpler behavior—i.e., always trusting the prediction—rather than engaging in strategic reasoning. Therefore, it is unclear a priori whether a revelation principle can be established.
To prove
Theorem
5.1
, we show that the above idea from the algorithmic information design literature indeed applies. To achieve this, we first introduce a new variant of the Bayesian persuasion problem, in which the receiver (in our model): (1) has a utility function that depends linearly on the payoff-relevant state, and (2) instead of updating the belief in a fully Bayesian manner, exhibits a signal-dependent bias when updating the belief.
In
Section
5.1
, we formally define this variant of the Bayesian persuasion problem, establish the revelation principle, and provide a solution for this problem, which will be used to solve our persuasive calibration problem and is of independent interest. In
Section
5.2
, we show the instance equivalence between our problem and this Bayesian persuasion variant (see
Theorem
5.4
), provide
Algorithm
3
, and prove
Theorem
5.1
.
5.1
(Bayesian) Persuasion with Signal-Dependent Bias
Bayesian persuasion
(
Kamenica and Gentzkow 2011
)
is a classic and important model that has been studied extensively in the literature. In this section, we introduce a new variant—
(Bayesian) persuasion with signal-dependent bias
—and provide a characterization of its optimal solution, which serves as a key ingredient for developing
Algorithm
3
and proving
Theorem
5.1
. Additionally, given the significance of the Bayesian persuasion and information design literature, we believe that our new variant and its results may be of independent interest. Below, we first revisit the classic Bayesian persuasion model and then introduce the new variant with signal-dependent bias.
A Bayesian persuasion instance is a game for two players, a sender and a receiver, and it is specified by a tuple
(\Theta^{\mathsf{BP}},\lambda^{\mathsf{BP}},u^{\mathsf{BP}},v^{\mathsf{BP}},\mathcal{A}^{\mathsf{BP}})
:
\Theta^{\mathsf{BP}}\subseteq[0,1]
denotes the payoff-relevant state space;
\lambda^{\mathsf{BP}}\in\Delta(\Theta^{\mathsf{BP}})
represents the common prior for both players, and
\lambda^{\mathsf{BP}}_{\theta}
denotes the prior probability of state
\theta
;
u^{\mathsf{BP}}(\cdot,\cdot):\mathcal{A}^{\mathsf{BP}}\times\Theta\rightarrow\mathbb{R}
(resp.
v^{\mathsf{BP}}(\cdot,\cdot):\mathcal{A}^{\mathsf{BP}}\times\Theta\rightarrow\mathbb{R}
) is the sender’s (resp. receiver’s) utility function that depends on the receiver’s action and the realized state.
The sender observes the realized state, while the receiver cannot.
The sender’s goal is to design a signaling scheme, given by conditional distributions
(\pi_{\theta}(\cdot))_{\theta\in\Theta^{\mathsf{BP}}}
where each
\pi_{\theta}(\cdot)\in\Delta(\Sigma)
specifies a distribution over a measurable signal space
\Sigma
, to maximize her expected payoff.
In classic Bayesian persuasion, upon observing a realized signal, the receiver updates his posterior belief about the underlying state in a
Bayesian
manner
and takes an action that maximizes his expected utility (subject to updated posterior belief).
(Bayesian) persuasion with signal-dependent bias.
In our considered variant, the receiver has a utility function
v(a,\cdot)
that linearly depends on the state.
Thus, only the mean of the belief matters for his optimal action.
In addition, when updating his belief, the receiver exhibits a signal-dependent bias defined as follows:
Definition 5.1
(Signal-dependent bias in belief updates)
.
Upon observing a signal realization
\sigma\sim\pi
, the receiver computes the following mean of the updated belief, denoted by
p(\sigma)
:
\displaystyle p(\sigma)\triangleq\frac{b(\sigma)+\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(\sigma)\cdot\theta}{\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(\sigma)}\in[0,1]
(32)
where
b(\sigma)\in\mathbb{R}
represents receiver’s bias when updating his belief (relative to an exact Bayesian update).
The receiver then takes an action maximizing his expected utility according to the mean
p(\sigma)
of his belief,
\displaystyle a^{*}(\sigma)\triangleq\argmax_{a\in\mathcal{A}^{\mathsf{BP}}}v^{\mathsf{BP}}\left(a,p(\sigma)\right)~.
(33)
Intuitively,
b(\sigma)
captures the receiver’s (possibly) irrational bias when updating their belief.
As a sanity check, when
b(\sigma)\equiv 0
for all
\sigma\in\Sigma
, the receiver’s belief update in Eqn. (
32
) recovers the standard Bayesian posterior mean.
In our variant, such biases are chosen to be favorable to the sender but must satisfy the following
bounded rationality
constraint:
\displaystyle\left(\mathbb{E}_{\sigma\sim\pi}\!\left[{\left|\frac{b(\sigma)}{\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\cdot\pi_{\theta}(\sigma)}\right|^{t}}\right]\right)^{\nicefrac{{1}}{{t}}}\leq\varepsilon~.
(34)
The above constraint essentially regulates that the aggregated biases with being weighted by the subjective belief are upper bounded by a budget
\varepsilon\geq 0
.
As the biases are chosen to be favorable to the sender, the sender can also optimize over the bias assignments subject to the above constraint.
We refer to the pair of signaling scheme
\pi
and a bias assignment
b
as the sender’s strategy.
Our formulation above, in particular the favorable bias assignments, shares similarity to the literature on
\varepsilon
-incentive compatible (IC) mechanism design (see, e.g.,
Balcan et al. 2005
;
Hartline and Lucier 2010
;
Hartline and Lucier 2015
;
Cai et al. 2012
;
Cai et al. 2021
;
Gonczarowski and Weinberg 2021
;
Balseiro et al. 2024
) where the ties are also usually chosen to be favorable to the mechanism designer.
30
30
30
There is also another line of research that studies robust mechanism design when agents select the
\varepsilon
-best response, which minimizes the designer’s utility
(
Gan et al. 2023
;
Chen and Lin 2023
;
Yang and Zhang 2024
, e.g.,)
.
Notably, even when selling a single item to a single buyer, the optimal
\varepsilon
-IC mechanism admits no simple structural characterization
(
Balseiro et al. 2024
)
. In contrast, by using the equivalence between the persuasive calibration and Bayesian persuasion with signal-dependent bias (
Theorem
5.4
), the structural characterizations developed for the former calibration problem in
Section
3
can be translated into structural results for the latter persuasion problem as well.
We also remark that many previous works have explored relaxing the Bayesian rationality assumptions in the classic Bayesian persuasion problem, either from the action-taking perspective (see, e.g.,
Feng et al. 2024
;
Yang and Zhang 2024
) or from the belief-updating perspective (see, e.g.,
Alonso and Câmara 2016
;
Galperti 2019
;
De Clippel and Zhang 2022
).
Our new variant, Bayesian persuasion with signal-dependent bias, falls into the latter category.
In general, the revelation principle – a commonly-used principle to analyze the classic Bayesian persuasion problem – need not hold
when the receiver is subject to biases in probabilistic inference, where the main reason is that
biased beliefs typically break linearity, it is no longer true that the convex combinations of implementable outcomes stay implementable in the same way
(
De Clippel and Zhang 2022
)
.
However, as we show below, the revelation principle still holds in our considered persuasion problem.
Definition 5.2
(Direct and IC strategy)
.
We say a sender’s strategy
(\pi,b)
, i.e., a pair of signaling scheme
\pi
and bias assignment
b
, is direct and incentive compatible (IC), if it satisfies (i) its signal space equals to the receiver’s action space; (ii) upon receiving a recommended action, it is indeed receiver’s best response (defined as in Eqn. (
33
)) to follow this action recommendation.
Lemma 5.2
(Revelation principle)
.
For the persuasion problem with signal-dependent bias, the revelation principle holds: for every sender’s strategy
(\pi,b)
, there exists a direct and IC strategy
(\pi^{\dagger},b^{\dagger})
that achieves the same outcome, i.e., conditional on the same state realization, the distributions of actions selected by the receiver are the same under both the original strategy
(\pi,b)
and the new direct and IC strategy
(\pi^{\dagger},b^{\dagger})
.
Therefore, there always exists a direct and IC sender’s strategy that maximizes the sender’s expected utility.
The intuition behind
Lemma
5.2
is as follows:
for any pair belief means
p(\sigma_{1}),p(\sigma_{2})
induced from two signals
\sigma_{1},\sigma_{2}
, if they lead to a same receiver action, then this action remains optimal for the new belief mean obtained through convex combination of them.
Meanwhile, this convex combination does not increase the aggregated biases.
Proof of
Lemma
5.2
.
Let
\pi,b
satisfy the conditions in Eqn. (
34
).
Suppose under two different signals
\sigma_{1},\sigma_{2}\sim\pi
with mean-belief update biases
b(\sigma_{1}),b(\sigma_{2})
, the receiver takes the same action, namely,
a^{*}(\sigma_{1})=a^{*}(\sigma_{2})\equiv a
.
Consider a new signaling
\pi^{\dagger}
that contracts these two signals
\sigma_{1},\sigma_{2}
into a same signal
\sigma^{\dagger}
, namely,
\pi_{i}^{\dagger}(\sigma^{\dagger})=\pi_{i}(\sigma_{1})+\pi_{i}(\sigma_{2})
for all
i\in[n]
, and a new mean-belief update bias assignment
b^{\dagger}(\sigma^{\dagger})=b(\sigma_{1})+b(\sigma_{2})
.
From Eqn. (
33
), we know that for any action
a^{\prime}\in\mathcal{A}^{\mathsf{BP}}
and signal
\sigma\in\{\sigma_{1},\sigma_{2}\}
, the receiver’s utility satisfies
\displaystyle v^{\mathsf{BP}}(a,p(\sigma))\geq v^{\mathsf{BP}}(a^{\prime},p(\sigma))~,
where
p(\sigma)
is defined in Eqn. (
32
).
By algebra, we have
\displaystyle v^{\mathsf{BP}}(a,p(\sigma_{1}))\cdot\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(\sigma_{1})+v^{\mathsf{BP}}(a,p(\sigma_{2}))\cdot\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(\sigma_{2})
\displaystyle\geq~
\displaystyle v^{\mathsf{BP}}(a^{\prime},p(\sigma_{1}))\cdot\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(\sigma_{1})+v^{\mathsf{BP}}(a^{\prime},p(\sigma_{2}))\cdot\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(\sigma_{2})
Since function
v^{\mathsf{BP}}(a,\theta)
is linear over the states
\theta\in\Theta^{\mathsf{BP}}
, the above inequality implies that for any action
a^{\prime}\in\mathcal{A}^{\mathsf{BP}}
\displaystyle v^{\mathsf{BP}}(a,p(\sigma^{\dagger}))\geq v^{\mathsf{BP}}(a^{\prime},p(\sigma^{\dagger}))~,
Thus, both strategies
(\pi,b)
and
(\pi^{\dagger},b^{\dagger})
induce same distribution for the receiver’s action conditional on each state.
Meanwhile, by Jensen’s inequality, the LHS of condition (
34
) under
(\pi^{\dagger},b^{\dagger})
is weakly smaller than that of
(\pi,b)
.
Thus, if multiple distinct signals lead to a same receiver’s action, one can contract these signals to a direct signal that recommends the receiver to take this action that is always followed by the receiver without violating the condition Eqn. (
34
).
∎
With
Lemma
5.2
, we can formulate the sender’s problem as finding an optimal direct and IC strategy, which can be further characterized by an maximization program with polynomial numbers of constraints and variables.
Proposition 5.3
(Optimization program characterization)
.
For the persuasion problem with signal-dependent bias, the optimal sender’s strategy
(\pi^{*},b^{*})
and her optimal expected utility is the solution of the following maximization program:
\displaystyle\begin{array}[]{llll}\max\limits_{\pi\geq 0;b}&\displaystyle\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\sum\nolimits_{a\in\mathcal{A}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(a)\cdot u^{\mathsf{BP}}(a,\theta)&\text{s.t.}&\\
&\displaystyle\left(\sum\nolimits_{a\in\mathcal{A}^{\mathsf{BP}}}\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(a)\cdot\left|\frac{b(a)}{\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(a)}\right|^{t}\right)^{\frac{1}{t}}\leq\varepsilon&\\
&\displaystyle v^{\mathsf{BP}}\left(a,b(a)+\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(a)\cdot\theta\right)\geq v^{\mathsf{BP}}\left(a^{\prime},b(a)+\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(a)\cdot\theta\right)&a,a^{\prime}\in\mathcal{A}^{\mathsf{BP}}\\
&\displaystyle\sum\nolimits_{a\in\mathcal{A}^{\mathsf{BP}}}\pi_{\theta}(a)=1&\theta\in\Theta^{\mathsf{BP}}\\
&\displaystyle b(a)+\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(a)\cdot\theta\geq 0&a\in\mathcal{A}^{\mathsf{BP}}\\
&\displaystyle b(a)+\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(a)\cdot\theta\leq\sum\nolimits_{\theta\in\Theta^{\mathsf{BP}}}\lambda^{\mathsf{BP}}_{\theta}\pi_{\theta}(a)&a\in\mathcal{A}^{\mathsf{BP}}\end{array}
which has
\mathsf{poly}(|\Theta^{\mathsf{BP}}|,|\mathcal{A}^{\mathsf{BP}}|)
variables,
\{\pi_{\theta}(a),b(a)\}_{\theta\in\Theta^{\mathsf{BP}},a\in\mathcal{A}^{\mathsf{BP}}}
, and
\mathsf{poly}(|\Theta^{\mathsf{BP}}|,|\mathcal{A}^{\mathsf{BP}}|)
constraints. Both the objective function and all constraints, except for the first constraint, are linear.
31
31
31
Recall that function
v^{\mathsf{BP}}(a,\theta)
is linear over the states
\theta\in\Theta^{\mathsf{BP}}
.
In the special case of
t=1
or
t=\infty
, the first constraint in
5.3
is equivalent to
\displaystyle\text{when }t=1:
\displaystyle\quad\sum\nolimits_{a\in\mathcal{A}}\left|b(a)\right|\leq\varepsilon~;
\displaystyle\text{when }t=\infty:
\displaystyle\quad\left|b(a)\right|\leq\varepsilon~,\quad a\in\mathcal{A}~.
which is essentially a linear constraint. Therefore,
5.3
becomes a linear program for
t=1
or
t=\infty
.
As mentioned in
Proposition
5.3
,
5.3
is a polynomial-size linear program when
t\in\{1,\infty\}
and can thus be solved in polynomial time. For other values of
t\in(1,\infty)
, the first constraint in
5.3
becomes non-linear. We leave it as an interesting future direction to explore whether
5.3
can be solved in polynomial time for general
t
, e.g., by constructing a time-efficient separation oracle.
Proof of
Proposition
5.3
.
Invoking
Lemma
5.2
, there exists an optimal strategy
(\pi^{*},b^{*})
for the sender that is direct and IC. We first verify that it is a feasible solution of
5.3
with the same objective value. Since strategy
(\pi^{*},b^{*})
is direct and IC, the expected utility of the sender is equal to the objective value of
(\pi^{*},b^{*})
in
5.3
. The first constraint is satisfied since strategy
(\pi^{*},b^{*})
satisfies the bounded rationality constraint defined in Eqn. (
34
). The second constraint is satisfied since strategy
(\pi^{*},b^{*})
is IC and utility function
v^{\mathsf{BP}}(a,\theta)
is linear over the states
\theta\in\Theta^{\mathsf{BP}}
. The third, fourth and fifth constraints are satisfied due to the feasibility of strategy
(\pi^{*},b^{*})
.
Finally, following the same argument, every feasible solution of
5.3
represents a sender’s strategy that is well-defined, feasible, direct and IC and has the expected utility of the sender equal to the objective of the solution. Therefore, we finish the proof of
Proposition
5.3
as desired.
∎
5.2
Instances Equivalence and Analysis of
Algorithm
3
In this section, we formally establish the equivalence between the persuasive calibration problem and the persuasion problem with signal-dependent bias (
Section
5.1
). We then use the equivalence to develop
Algorithm
3
and prove
Theorem
5.1
.
At first glance, the two problems might seem different, as the agent in the persuasive calibration model always trusts the prediction, while the agent in the persuasion model performs a biased Bayesian update to form their posterior belief. However, the ECE budget constraint in the former and the bounded rationality constraint (Eqn. (
34
)) in the latter model enable us to establish the an equivalence between the two problems. The proof of
Theorem
5.4
is at the end of this section.
Theorem 5.4
(Instance equivalence)
.
Fix any instance of the persuasive calibration problem, specified by a tuple
(\Theta,\lambda,u,v,\mathcal{A},(\varepsilon,\ell_{t}))
.
Consider the following instance
(\Theta,\lambda,u^{\mathsf{BP}},v^{\mathsf{BP}},\mathcal{A},(\varepsilon,\ell_{t}))
of the (Bayesian) persuasion problem with signal-dependent bias:
(i)
the sender’s/receiver’s utility functions are given as:
\displaystyle u^{\mathsf{BP}}(a,\theta_{i})
\displaystyle\leftarrow(1-\theta_{i})\cdot u_{i}(a,y=0)+\theta_{i}\cdot u_{i}(a,y=1),
\displaystyle\quad a\in\mathcal{A},i\in[n]~;
\displaystyle v^{\mathsf{BP}}(a,\theta_{i})
\displaystyle\leftarrow(1-\theta_{i})\cdot v(a,y=0)+\theta_{i}\cdot v(a,y=1),
\displaystyle\quad a\in\mathcal{A},i\in[n]~;
(ii)
the sender’s strategy follows the bounded rationality constraint defined in Eqn. (
34
).
Then an optimal
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}^{*}
in the persuasive calibration instance can be converted as an optimal sender’s strategy
(\pi^{*},b^{*})
in the above defined instance of the (Bayesian) persuasion problem with signal-dependent bias, and vice versa. Specifically, given an optimal sender’s strategy
(\pi^{*},b^{*})
that is direct and IC, an optimal
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}^{*}
can be constructed as
\displaystyle\tilde{f}^{*}_{i}(p)\leftarrow\sum\nolimits_{a\in\mathcal{A}}\pi^{*}_{\theta_{i}}(a)\cdot\mathbf{1}\!\left\{{\frac{\sum\nolimits_{i\in[n]}\lambda_{i}\pi^{*}_{\theta_{i}}(a)\cdot\theta_{i}+b^{*}(a)}{\sum\nolimits_{i\in[n]}\lambda_{i}\pi^{*}_{\theta_{i}}(a)}=p}\right\},\quad i\in[n],~~p\in[0,1]~.
(41)
Given an optimal
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}^{*}
, an optimal sender’s strategy
(\pi^{*},b^{*})
that is direct and IC can be constructed as
\displaystyle\pi^{*}_{\theta_{i}}(a)
\displaystyle\leftarrow\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}^{*}_{i}(p),\quad
\displaystyle a\in\mathcal{A},i\in[n]
\displaystyle b^{*}(a)
\displaystyle\leftarrow\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}^{*}_{i}(p)(p-\theta_{i}),\quad
\displaystyle a\in\mathcal{A}
where
a^{*}(p)
is defined in Eqn. (
2
).
We remark that in the corresponding Bayesian persuasion instance constructed in
Theorem
5.4
, the receiver’s utility
v(a,\theta)
is a linear function over the states
\theta\in\Theta^{\mathsf{BP}}
, while the sender’s utility could be general.
Combining
Theorem
5.4
and
Proposition
5.3
, we are ready to provide
Algorithm
3
and prove
Theorem
5.1
.
Algorithm 3
LP-based polynomial-time algorithm for solving optimal predictor with
t\in\{1,\infty\}
1:
Input:
persuasive calibration instance
(\Theta,\lambda,u,v,\mathcal{A},(\varepsilon,\ell_{t}))
with
t\in\{1,\infty\}
.
2:
Solve linear program
5.3
using the persuasion instance defined in
Theorem
5.4
and let
(\pi^{*},b^{*})
be its solution.
3:
Use the optimal solution
(\pi^{*},b^{*})
to
construct the predictor
\tilde{f}^{*}
based on Eqn. (
41
).
4:
Output:
predictor
\tilde{f}^{*}
.
Proof of
Theorem
5.1
.
In
Algorithm
3
, it first solves
5.3
, which is a linear program with size
\mathsf{poly}(n,m)
, and then constructs the predictor based on the optimal solution of
5.3
. Both steps require
\mathsf{poly}(n,m)
running time and thus the algorithm is polynomial-time. Finally, the correctness of the algorithm follows
Proposition
5.3
and
Theorem
5.4
. This finishes the proof of
Theorem
5.1
.
∎
We conclude this section by presenting the proof for
Theorem
5.4
.
Proof of
Theorem
5.4
.
In this proof, we use
\text{\bf Payoff}\!\left[{\pi,b}\right]
to denote the sender’s payoff from the strategy
(\pi,b)
.
To prove the theorem statement, we show that: (1) every direct and IC strategy
(\pi,b)
that satisfies the condition in Eqn. (
34
) can be converted into an
(\varepsilon,\ell_{t})
-calibrated
\tilde{f}
whose principal’s payoff equals to the original sender’s payoff;
(2)
every
(\varepsilon,\ell_{t})
-calibrated
\tilde{f}
can be converted into a direct and IC sender’s strategy
(\pi,b)
whose sender’s payoff equals to original principal’s payoff from
\tilde{f}
.
Since
\Theta^{\mathsf{BP}}=\Theta
, we will simplify the notation
\pi_{\theta_{i}}=\pi_{i}
for
i\in[n]
.
From sender’s strategy
(\pi,b)
to principal’s predictor
\tilde{f}
.
By
Lemma
5.2
, we consider a direct and IC strategy
(\pi,b)
.
Now given a pair
(\pi,b)
satisfying the condition (
34
), we define a prediction
p(a)
for the action
a\in\mathsf{supp}(\pi)
and construct predictor
\tilde{f}
as follows:
\displaystyle p(a)\triangleq\frac{\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot\theta_{i}+b(a)}{\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)}~;\quad\tilde{f}_{i}(p)\leftarrow\sum\nolimits_{a\in\mathcal{A}}\pi_{i}(a)\cdot\mathbf{1}\!\left\{{p(a)=p}\right\},\quad i\in[n],~~p\in[0,1]
Clearly, by condition (
33
), we know that
p(a)\in[0,1]
for all
a\in\mathcal{A}
.
By construction, it can be verified that
\tilde{f}_{i}(\cdot)
is a valid distribution over
[0,1]
.
We next argue that the constructed
\tilde{f}
is
(\varepsilon,\ell_{t})
-calibrated and it satisfies that
\text{\bf Payoff}\!\left[{\tilde{f}}\right]=\text{\bf Payoff}\!\left[{\pi,b}\right]
.
To see
\tilde{f}
is indeed
(\varepsilon,\ell_{t})
-calibrated, we observe
\displaystyle\left(\text{\bf ECE}_{t}\!\left[{\tilde{f}}\right]\right)^{t}
\displaystyle=\sum\nolimits_{p\in\mathsf{supp}(\tilde{f})}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\cdot\left|p-\frac{\sum\nolimits_{k\in[n]}\lambda_{k}\tilde{f}_{k}(p)\theta_{k}}{\sum\nolimits_{j\in[n]}\lambda_{j}\tilde{f}_{j}(p)}\right|^{t}
\displaystyle=\sum\nolimits_{a\in\mathcal{A}}\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot\left|p(a)-\frac{\sum\nolimits_{k\in[n]}\lambda_{k}\pi_{k}(a)\theta_{k}}{\sum\nolimits_{j\in[n]}\lambda_{j}\pi_{j}(a)}\right|^{t}
\displaystyle=\sum\nolimits_{a\in\mathcal{A}}\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot\left|\frac{b(a)}{\sum\nolimits_{j\in[n]}\lambda_{j}\pi_{j}(a)}\right|^{t}\leq\varepsilon^{t}~.
To see the equal payoff, we first notice that for every event
i\in[n]
,
U_{i}(p(a))=u^{\mathsf{BP}}(a,\theta_{i})
for all
a\in\mathcal{A}
.
This is by the condition (
33
).
Consequently, we have
\displaystyle\text{\bf Payoff}\!\left[{\tilde{f}}\right]=\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\sum\nolimits_{p\in[0,1]}\tilde{f}_{i}(p)U_{i}(p)
\displaystyle=\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\sum\nolimits_{a\in\mathcal{A}}\tilde{f}_{i}(p(a))U_{i}(p(a))
\displaystyle=\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\sum\nolimits_{a\in\mathcal{A}}\sum\nolimits_{a^{\prime}\in\mathcal{A}:p(a^{\prime})=p(a)}\pi_{i}(a)u^{\mathsf{BP}}(a,\theta_{i})
\displaystyle=\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\sum\nolimits_{a\in\mathcal{A}}\pi_{i}(a)u^{\mathsf{BP}}(a,\theta_{i})=\text{\bf Payoff}\!\left[{\pi,b}\right]
From principal’s predictor
\tilde{f}
to sender’s strategy
(\pi,b)
.
Given an
(\varepsilon,\ell_{t})
-calibrated predictor
\tilde{f}
, for any
p\in\mathsf{supp}(\tilde{f})
, we let
a^{*}(p)\in\mathcal{A}
denote the receiver’s optimal action upon receiving a prediction
p
.
We consider a signal space
\Sigma\leftarrow\mathcal{A}
, and define
\pi_{i}(\cdot)\in\Delta(\mathcal{A})
for
i\in[n]
and
b(\cdot):\mathcal{A}\rightarrow\mathbb{R}
as follows
\displaystyle\pi_{i}(a)
\displaystyle\leftarrow\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}_{i}(p),\quad
\displaystyle a\in\mathcal{A},i\in[n]
\displaystyle b(a)
\displaystyle\leftarrow\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)(p-\theta_{i}),\quad
\displaystyle a\in\mathcal{A}
We next show that by construction, the above
\pi,b
satisfy the condition (
34
), and moreover, they yield same payoff.
It is easy to see that, by construction,
\pi_{i}
is a valid distribution over
\Sigma
:
\displaystyle\sum\nolimits_{a\in\mathcal{A}}\pi_{i}(a)=\sum\nolimits_{a\in\mathcal{A}}\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}_{i}(p)=\sum\nolimits_{p\in[0,1]}\tilde{f}_{i}(p)=1,\quad i\in[n]~.
We next argue the Eqn. (
34
) is satisfied for
\pi,b
.
\displaystyle~\sum\nolimits_{a\in\mathcal{A}}\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot\left|\frac{b(a)}{\sum\nolimits_{j\in[n]}\lambda_{j}\pi_{j}(a)}\right|^{t}
\displaystyle=\sum\nolimits_{a\in\mathcal{A}}\tilde{f}(a)\cdot\frac{1}{\tilde{f}(a)^{t}}\left|\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\sum\nolimits_{k\in[n]}\lambda_{k}\tilde{f}_{k}(p)(p-\theta_{k})\right|^{t}
\displaystyle\leq\sum\nolimits_{a\in\mathcal{A}}\tilde{f}(a)\cdot\frac{1}{\tilde{f}(a)^{t}}\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\left|\sum\nolimits_{k\in[n]}\lambda_{k}\tilde{f}_{k}(p)(p-\theta_{k})\right|^{t}
(due to Triangle inequality)
\displaystyle\leq\sum\nolimits_{a\in\mathcal{A}}\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}(p)\cdot\frac{1}{\tilde{f}(p)^{t}}\left|\sum\nolimits_{k\in[n]}\lambda_{k}\tilde{f}_{k}(p)(p-\theta_{k})\right|^{t}
(due to
\tilde{f}(a)\geq\tilde{f}(p)
)
\displaystyle=\sum\nolimits_{p}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\left|p-\frac{\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\theta_{i}}{\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)}\right|^{t}\leq\varepsilon^{t}~.
where
\tilde{f}(a)\triangleq\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\geq\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)\triangleq\tilde{f}(p)
for all
p
with
a^{*}(p)=a
.
To see the mean-belief
p(a)\in[0,1]
,
we note that for any
a\in\mathcal{A}
,
\displaystyle\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot\theta_{i}+b(a)
\displaystyle=~
\displaystyle\sum\nolimits_{i\in[n]}\lambda_{i}\theta_{i}\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}_{i}(p)+\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)(p-\theta_{i})
\displaystyle\overset{(a)}{=}~
\displaystyle\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}_{i}(p)p\overset{(b)}{\leq}\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\pi_{i}(a)~,
where from equality (a), we know that
\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot\theta_{i}+b(a)\geq 0
as we always have
q\geq 0
; and inequality (b) utilizes the fact that
p\in[0,1]
and the definition of
\pi_{i}(a)
.
To see the strategy
(\pi,b)
is IC,
we recall that for any prediction
p\in\{p\in[0,1]:a^{*}(p)=a\}
where the receiver’s optimal decision is taking action
a\in\mathcal{A}
, we must have
\displaystyle p\cdot v(a,y=1)+(1-p)\cdot v(a,y=0)\geq p\cdot v(a^{\prime},y=1)+(1-p)\cdot v(a^{\prime},y=0),\quad\forall a^{\prime}\in\mathcal{A}~.
Rearranging, multiplying on both sides with
\lambda_{i}\tilde{f}_{i}(p)
and taking the summation on both sides over all
i\in[n]
, we then have for any
p\in\{p\in[0,1]:a^{*}(p)=a\}
\displaystyle\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)p\cdot v_{1}(a,a^{\prime})\geq\sum\nolimits_{i\in[n]}\lambda_{i}\tilde{f}_{i}(p)(p-1)\cdot v_{0}(a,a^{\prime}),\quad\forall a^{\prime}\in\mathcal{A}
Taking the summation on both sides over all
p\in\{p\in[0,1]:a^{*}(p)=a\}
, we then have for any
a^{\prime}\in\mathcal{A}
,
\displaystyle\sum\limits_{i\in[n]}\lambda_{i}\sum\limits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}_{i}(p)p\cdot v_{1}(a,a^{\prime})\geq\sum\limits_{i\in[n]}\lambda_{i}\sum\limits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}_{i}(p)(p-1)\cdot v_{0}(a,a^{\prime})~.
(42)
By construction, we have
LHS of
(
42
)
\displaystyle=\left(\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot\theta_{i}+b(a)\right)\cdot v_{1}(a,a^{\prime})
RHS of
(
42
)
\displaystyle=\left(\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot\theta_{i}+b(a)-\sum\nolimits_{i\in[n]}\lambda_{i}\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}_{i}(p)\right)\cdot v_{0}(a,a^{\prime})
\displaystyle=\left(b(a)-\sum\nolimits_{i\in[n]}\lambda_{i}\pi_{i}(a)\cdot(1-\theta_{i})\right)\cdot v_{0}(a,a^{\prime})~,
which implies the condition (
33
) for the receiver receiving a signal
a
.
Moreover, we have
\displaystyle\text{\bf Payoff}\!\left[{\pi,b}\right]
\displaystyle=\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\sum\nolimits_{a\in\mathcal{A}}\pi_{i}(a)u^{\mathsf{BP}}(a,\theta_{i})
\displaystyle=\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\sum\nolimits_{a\in\mathcal{A}}\sum\nolimits_{p\in[0,1]:a^{*}(p)=a}\tilde{f}_{i}(p)u^{\mathsf{BP}}(a,\theta_{i})
\displaystyle=\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\sum\nolimits_{p\in[0,1]}\tilde{f}_{i}(p)U_{i}(p)=\text{\bf Payoff}\!\left[{\tilde{f}}\right]~.
We thus finish the proof of
Theorem
5.4
.
∎
Appendix A
A Win-Win Example
As the ECE budget
\varepsilon
increases, the principal’s expected utility under the optimal
\varepsilon
-calibrated predictor weakly increases, since the space of feasible predictors expands. However, from the agent’s perspective, the prediction becomes less calibrated, which may negatively impact their expected utility. Despite this, due to the strategic interaction between the principal and the agent, the intuition that the agent’s expected utility under the optimal
\varepsilon
-calibrated predictor weakly decreases as
\varepsilon
increases is not necessarily correct. In this section, we present a “win-win” instance of our persuasive calibration problem, where both the principal’s and the agent’s expected utility under the optimal
\varepsilon
-calibrated predictor increase within a certain range of the ECE budget and are strictly higher than their expected utilities when the ECE budget is set to zero. In this section, we focus on
\ell_{1}
-norm ECE.
Example A.1
(Win-win instance)
.
There are
n=3
events, with expected outcomes
\theta_{1}=0.10001
,
\theta_{2}=0.85
,
\theta_{3}=1
, and event prior
\lambda_{1}=0.25
,
\lambda_{2}=0.5
,
\lambda_{3}=0.25
. The agent has
m=4
actions, whose induced utilities
v(a,y)
for each outcome
y\in\mathcal{Y}
satisfy
a=1
a=2
a=3
a=4
y=1
-9.9999
0
0.1
10
y=0
0.0001
0
-0.9
-\infty
Table 1
:
Agent’s utility
v(a,y)
in
Example
A.1
.
The principal’s utility
u_{i}(a,y)
only depends on the agent’s action. We shorthand it using
u(a)
and define it as
a=1
a=2
a=3
a=4
5
0
1
2
Table 2
:
Principal’s event-independent utility
u(a)
in
Example
A.1
.
By construction, the principal’s indirect utility
U(p)
of a given prediction
p
is
0\leq p\leq p^{\dagger}
p^{\dagger}0
, we must have
\kappa(p)=q
.
That is, we must have the following condition: for every
\chi_{i}(q,p)>0
, we have
\displaystyle q=\frac{\sum\nolimits_{i\in[n]}\lambda_{i}\int_{0}^{1}\chi_{i}(q^{\prime},p)\,{\mathrm{d}}q^{\prime}\cdot\theta_{i}}{\sum\nolimits_{i\in[n]}\lambda_{i}\int_{0}^{1}\chi_{i}(q^{\prime},p)\,{\mathrm{d}}q^{\prime}}~.
Equivalently, we can express this condition as follows: for every
q,p\in[0,1]
, we have
\displaystyle\left(q-\frac{\sum\nolimits_{i\in[n]}\lambda_{i}\int_{0}^{1}\chi_{i}(q^{\prime},p)\,{\mathrm{d}}q^{\prime}\cdot\theta_{i}}{\sum\nolimits_{i\in[n]}\lambda_{i}\int_{0}^{1}\chi_{i}(q^{\prime},p)\,{\mathrm{d}}q^{\prime}}\right)\cdot\sum\nolimits_{i\in[n]}\lambda_{i}\chi_{i}(q,p)=0~.
With the above observation, we can generalize
3.7
to the following program that involves with variables
(\chi_{i}(\cdot,\cdot))_{i\in[n]}
:
\displaystyle\begin{array}[]{rlll}\max\limits_{\chi_{i}\geq 0}&\displaystyle\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\int_{0}^{1}\int_{0}^{1}\chi_{i}(q,p)\cdot U_{i}(p)~{\mathrm{d}}p{\mathrm{d}}q&\text{s.t.}&\\
&\displaystyle\sum\nolimits_{i\in[n]}\lambda_{i}\cdot\int_{0}^{1}\int_{0}^{1}\chi_{i}(q,p)\cdot|q-p|^{t}~{\mathrm{d}}p{\mathrm{d}}q\leq\varepsilon^{t}&\\
&\displaystyle\left(q-\frac{\sum\nolimits_{i\in[n]}\lambda_{i}\int_{0}^{1}\chi_{i}(q^{\prime},p)\,{\mathrm{d}}q^{\prime}\cdot\theta_{i}}{\sum\nolimits_{i\in[n]}\lambda_{i}\int_{0}^{1}\chi_{i}(q^{\prime},p)\,{\mathrm{d}}q^{\prime}}\right)\cdot\sum\nolimits_{i\in[n]}\lambda_{i}\chi_{i}(q,p)=0&q,p\in[0,1],\\
&\displaystyle\int_{0}^{1}\int_{0}^{1}\chi_{i}(q,p)~{\mathrm{d}}p{\mathrm{d}}q=1&i\in[n],\end{array}
Clearly, the second constraint here is not a linear constraint, and it remains unclear if there exists an efficient solution to solve the above program.