{'fraction_non_alphanumeric': 0.05607422995982399, 'fraction_numerical': 0.013334608762196288, 'mean_word_length': 3.8167158127534093, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal Scoring Rule Design

This paper introduces an optimization problem for proper scoring rule design. Consider a principal who wants to collect an agent's prediction about an unknown state. The agent can either report his prior prediction or access a costly signal and report the posterior prediction. Given a collection of possible distributions containing the agent's posterior prediction distribution, the principal's objective is to design a bounded scoring rule to maximize the agent's worst-case payoff increment between reporting his posterior prediction and reporting his prior prediction. We study two settings of such optimization for proper scoring rules: static and asymptotic settings. In the static setting, where the agent can access one signal, we propose an efficient algorithm to compute an optimal scoring rule when the collection of distributions is finite. The agent can adaptively and indefinitely refine his prediction in the asymptotic setting. We first consider a sequence of collections of posterior distributions with vanishing covariance, which emulates general estimators with large samples, and show the optimality of the quadratic scoring rule. Then, when the agent's posterior distribution is a Beta-Bernoulli process, we find that the log scoring rule is optimal. We also prove the optimality of the log scoring rule over a smaller set of functions for categorical distributions with Dirichlet priors.


Introduction
Proper scoring rules are scoring functions that incentivize truthful information elicitation: an agent who has a subjective belief about an uncertain event maximizes his expected score by making a prediction according to his belief. When the agent can acquire costly information to refine his belief, which proper scoring rules maximally incentivize the agent's information acquisition? We formalize this question and show that popular quadratic and log scoring rules are optimal for information acquisition under different scenarios.
Suppose a principal wants to elicit a probabilistic prediction about an uncertain state W (e.g. the outcome of a future coin flip). An agent can report his prior P (W ) (e.g. uniform on each side). Alternatively, the agent can obtain additional costly information S, say by tossing the coin several times, and then update his prediction to P (W |S = s). Any proper scoring rule can elicit the agent's prediction truthfully once its formed. But not all scoring rules incentivize the agent to gather costly information and improve his posterior prediction. In particular, the information gain -the expected difference of payment on posterior prediction and prior prediction -may be too small for the agent to obtain information. We propose an optimization framework to study the principal's problem of designing a proper scoring rule to incentivize the agent to acquire costly information, subject to a bounded payment constraint. The principal hopes to maximize the agent's information gain, with respect to the chosen scoring rule, for the worst information structure that the agent may have. This worst-case consideration is natural. For example, if the principal wants to design a scoring rule to incentivize her students to grade assignments with effort, the principal needs to ensure her scoring rule can incentivize all students to work hard when students have heterogeneous information structures.
We study two settings of this scoring rule design problem: static and asymptotic settings. In the static setting, the agent can access one signal. The principal's problem (Problem 1) is to design a proper scoring rule that 1) maximizes the information gain of the worst information structure in a known set P that the agent's information structure belongs to, and 2) is subjected to a bounded expected payment constraint. We require the expected score to be always bounded as otherwise, the problem is meaningless because we can always scale the scoring rule. Our setting is similar to that of Hartline et al. [20], but they require the ex-post payment be bounded. See related work for more comparison. We also consider the reverse of Problem 1 (our Problem 2) in the static setting and ask, for any given proper scoring rule, whether there exists a set of information structures that make the scoring rule uniquely optimal for incentivizing information acquisition.
In the asymptotic setting (Problem 3), the agent can adaptively and indefinitely refine his prediction. For instance, suppose we want to design a scoring rule and use it as a market scoring rule in a prediction market to encourage a sequence of forecasters to exert effort and report their posterior prediction. Each forecaster's incentive depends on the previous forecaster's information, and they can adaptively decide whether to spend the effort. Thus we need to design a scoring rule that optimizes for a sequence of collections of information structures where the n-th collection represents all possible information structures of any k-th forecaster with k ≤ n. Another example is the large sample theory in statistics which studies estimators with an indefinitely growing sample size. In this context, Problem 3 asks what the optimal proper scoring rule is when the agent can adaptively get sample points to improve his prediction.

Our Technique and Contributions
Because any proper scoring rule can be specified as a convex function of prediction and its sub-gradient [22,29,18], our design space of the optimization in Problem 1 and 3 can be converted to the set of bounded convex functions, and the information gain becomes the Jensen gap of the associated convex function. This gives us a geometric interpretation of our optimization problem: The information gain amount to how curved (an integral of second derivative) the associated convex function, H, is at the information structure. However, the double iterative integral of the second derivative of H is bounded, since H is bounded.
Section 4 studies the static setting. For Problem 1, we first consider the extreme case when the principal knows the agent's information structure exactly (i.e. P is singleton), and show in Section 4.1 that the optimal convex function is an upside-down pyramid (Fig. 1). Then Section 4.2 considers the case that the collection of information structures is finite: both the number of information structures and the support of any information structure are finite. Theorem 4.4 shows we can solve the optimization problem efficiently and the optimal H is a convex piecewise linear function. Section 4.3 looks at Problem 2: Given any convex H, is there a collection of information structures for which H is (uniquely) optimal? We show a necessary and sufficient condition for a convex piecewise linear function to be uniquely optimal in Theorem 4.6. However, we show quadratic scoring rule cannot be uniquely optimal in Problem 1.
Section 5 considers the asymptotic setting which generalizes the static setting and evaluates a scoring rule relatively against the best scoring rule called the relative information gain (Problem 3). Section 5.1 tries to study general Bayesian estimation with large number of i.i.d. samples. Inspired by (Bayesian) Cramèr-Rao bound [17] which shows the Bayes estimator with n samples has variance of order Θ(1/n), Section 5.1 considers the sequence of collections of information structures with vanishing covariance. Theorem 5.1 shows that the quadratic scoring rule optimizes the relative information gain against any smooth functions. To prove this, we relate the information gain to the strong convexity of our convex function and show that the quadratic scoring rule is the "most strongly convex" function.
Finally, Section 5.2 studies the information structures that are in an exponential family with conjugate prior, Beta-Bernoulli and Dirichlet-categorical information structures, and shows that the log scoring rule is optimal. Specifically, Section 5.2.1 studies a sequence of collections of information structures that converges to the collection of all Beta-Bernoulli distributions and show the relative information gain of the log scoring rule is optimal against all smooth functions. Additionally, through simulation Fig. 3 shows that the optimal scoring rules for Beta-Bernoulli distribution with large enough sample size is close to log scoring rule. Section 5.2.2 extends this result to non-binary settings and show the log scoring rule optimizes the relative information gain against all functions that are smooth up to the boundary. To achieve these results, we first show the limit of information gain is an elliptic differential operator on the convex function. Then we use a maximum principle to show that the log scoring rule maximized the elliptical differential operator's value [11,4].

Related Work
Our problem can be seen as purchasing prediction from strategic people. The work on this topic can be roughly divided into two categories according to whether agents can misreport their signal or prediction. Below we focus on the relationship of our work to the most relevant technical scholarship.
In the first category, to ensure agents reporting their signals or predictions truthfully, there are two settings according to whether money is used for incentive alignment. In the first setting, the analyst uses monetary payments to incentivize agents to reveal their data truthfully. The challenge is to ensure truthtelling gets the highest payments. Existing works verify agents' reports by using either an observable ground truth (proper scoring rules) or peers' reports (peer prediction). For the second setting, individuals' utilities directly depend on an inference or learning outcome (e.g. they want a regression line to be as close to their own data point as possible) and hence they have incentives to manipulate their reported data to influence the outcome. [10,23,27,19,8].
Our setting is inspired by Hartline et al. [20] where there is an observable ground truth to verify an agent's reports and we want to maximize agent's inventive under a budget constraint. However, they consider that the ex-post payment is bounded, while we ask the ex-ante payment be bounded. This different boundedness condition contributes to the distinction between our results and theirs. In particular, ex-post bounded payment excludes the log scoring rule which is arguably one of the most important proper scoring rule. Furthermore, we show the log scoring rule is indeed the optimal when agent's belief is in exponential family with conjugate prior. Additionally, our paper stresses more on unknown information structure, and theirs focuses more on known information structure. They show if the information structure is exactly known the optimal scoring rule has v-shaped in the one-dimensional case which is qualitatively similar to our Corollary 4.2. They also consider general information structures and show that the quadratic scoring rule is optimal up to a constant factor which also holds for any strongly convex function. In contrast, we show the quadratic scoring rule is uniquely optimal.
Neyman et al. [24] also study optimal scoring rule design problem, but is more related to sequential method [16]. Instead of imposing bounded payment conditions, their objective comprises both payment and accuracy. They consider a special case of Beta-Bernoulli information structures where the prior is uninformative and design scoring rule for an agent to sequentially acquire samples from a Bernoulli distribution.

Problem Description
A principal wants to collect high quality prediction of an unknown state of the world W from an agent who can access a costly signal S. The space of the world Ω is finite with |Ω| = d and has a typical realization ω ∈ Ω. The signal space S is a measurable set with a typical realization s ∈ S. We refer to a joint distribution P on Ω × S as an information structure. Because accessing the signal S is costly for the agent, the principal wants to design a scoring rule to incentivize the agent to spend the effort and report the posterior prediction instead of the prior prediction. However, the principal only knows a collection of information structures P ⊆ ∆(Ω × S) that the agent's information structure falls into.
Before stating our objective, we first simplify the notation by calibrating agent's signal. Specifically, let the agent's prediction after observing the signal be a random variable on ∆(Ω), X = X(s) := P (W | S = s) when S = s, and, thus, his prediction without the signal is E X = P (W ). For the principal, the information structures P ∈ P affects only the random variable of prediction X. Hence, we will use P and X exchangeably for information structures in this paper, and let X be the collection of random variables of prediction induced from information structures P in P.
With the above definitions, the principal wants to maximize the difference of expected payment between reporting the prior prediction E X and reporting the posterior prediction X. Because a proper scoring rule P S : Ω × ∆(Ω) → R can be associated with a convex function H : ∆(Ω) → R so that for all x ∈ ∆(Ω) and ω ∈ Ω (See Section 3.1 for more properties of scoring rules), given an information structure X, the value of observing the signal under the proper scoring rule with H is We call J H (X) information gain of X on H which measures the difference of expected scores between agents who exert effort and those who do not. 1 Given Ω and X , the principal chooses a convex function H which maximizes the worst information gain of X which is called the information gain of X on H, We require the scoring rules are bounded so that the ex-ante payment of truth-telling is always in [0, 1]. By a simple calculation, a bounded scoring rule has H in H : Now we are ready to define our max-min optimization problem for the principal. First, Section 4 considers a max-min optimization problem given a collection of information structures.
Problem 1 (static). Given a set of information structures X and Ω, find bounded H which maximizes the information gain of X Obj X (H) = max H∈H Obj X (H).
We further call Opt(X ) := max H∈H Obj X (H). 2 We can also ask the converse of Problem 1: Given any convex H, is there a collection of information structures X for which H is (uniquely) optimal in Problem 1? These problem can provide an incentive understanding why certain proper scoring rules, e.g., log scoring rule and quadratic scoring rule are commonly used.
We say a collection of information structures X settles a convex function H ∈ H if H is optimal for X . Given U ⊆ ∆ d , we say X uniquely settles H on U if for all H ∈ arg maxH Obj X (H), H (x) = H(x) for all x ∈ U , and uniquely settles H when U = ∆ d . Equivalently H is the unique optimal for X , {H} = arg maxH Obj X (H).
Problem 2. Given U ⊆ ∆ d and a convex function H, find a collection of information structure X so that X uniquely settles H, i.e., H is the unique optimal for X .
Note that Problem 2 requires the unique optimality. Otherwise, if a collection of information structures contains a constant information structure X where X = E X, any H has zero information gain of X, and thus is optimal.
The agent may adaptively conduct a sequence of experiments and access a sequence of signals. Hence the principal may want the agent to access as many signals as possible, and needs to ensure the information gain of each additional signal is as large as possible.
Problem 3 (asymptotic). Let X 0 , . . . be a sequence of collections of information structures which does not contain any constant information structure andX n := ∪ k≤n X k for all n. The principal chooses H to maximize the relative information gain of the sequenceX 0 , . . . , As the example in the introduction, to predict an output of a biased coin, the agent can observe any number of samples from the coin. The principal has a sequence of collections of information structures X 0 , X 1 , . . . where each element in X n is a possible information structure of the (n+1)-th sample. Specifically, given an outcome s (≤n) = (s (1) , . . . , s (n) ) ∈ {0, 1} n of the first n signal S (≤n) , let X s (≤n) (s) = P (W | S (≤n) = s (≤n) , S (n+1) = s) be the posterior on W with the (n + 1)-th signal conditional on S (≤n) = s (≤n) or posterior with (n+1)-th signal for short. Then X n = {X s (≤n) , ∀s (≤n) ∈ {0, 1} n }. As the asymptotic theory in statistics studies estimators with indefinitely growing sample size, Problem 3 evaluates proper scoring rules when the agent may collect indefinitely data. The notion of relative information gain is particularly useful when the cost of each signal is small for all, or the number of signal is indefinite.
Equation (3), intuitively, measures the information gain of lim n→∞Xn on H. Indeed Proposition 2.1 shows that Problem 3 contains Problem 1 as a special case when Opt(lim nXn ) > 0. Furthermore, using the ratio of information gains, Eq. (3) is meaningful even when Opt(lim nXn ) = 0. Proposition 2.1. Given an increasing sequence X 1 , . . . with X := lim n→∞ X n , if Opt(X ) > 0, H ∈ H is optimal for X for Problem 1 if and only if H is optimal for the sequence X 1 , . . . for Problem 3.

Preliminary
Here we list some notations. Given positive integer d and n, let We further call all one vector 1 := (1, . . . , 1) ∈ R d and c :

Proper Scoring Rules
A scoring rule for a random variable W ∈ Ω is a function P S : Ω × ∆(Ω) → R where P S(ω,x) is the score assigned to a predictionx ∈ ∆(Ω) when W = ω. The scoring rule is (strict) proper if for all random variable W on Ω with distribution x, settingx = x (uniquely) maximizes the expected score E W ∼x P S(W,x). In other words, if W is distributed according to x, then truthfully reporting x can maximizes the expected score.
Conversely, for every (strictly) convex function H : ∆(Ω) → R, there exists a (strict) proper scoring rule such that the above condition hold.
We list some common proper scoring rules with associated convex functions which are scaled to be in H.
Note that the convex functions Q and H s for quadratic scoring rule and spherical scoring rule respectively are smooth on the closed set ∆ d , but H ln for log scoring rule is only smooth on the open set int(∆ d ).
When the state space Ω is binary, the associated convex function is one-dimensional. For every proper scoring rule P S, there exists a convex function H : [0, 1] → R so that for all x ∈ [0, 1] and binary event ω ∈ {0, 1}

Convex Functions
In Sections 5.1 and 5.2, we will restrict our functions to be smooth and utilize their analytic properties (k-th order derivative). Though the domain of our convex functions is a probability simplex ∆ d , which is a submanifold in R d , we can extend any smooth function h on ∆ d to a smooth function on R d 3 , and use standard notation to discuss the k-th derivative of h, instead of using complex coordinate charts.
We first define the notion of strongly convex on int(∆).
Note that the pair x and y are restricted in int(∆), so the equivalent condition on the Hessian of H is also restricted in the tangent space of ∆. Formally,

PDE and Maximum Principle
We will associate the objective in Problem 3 with elliptic differential operators and exploit the maximum principles of our differential operator.
Definition 3.4 (Evans [11]). Let U ⊂ R d be an open and bounded set. L is a second order differential We say L is elliptic if A(x) = (A ij (x)) is positive definite for all x ∈ U , and uniformly elliptic if there exists ρ > 0 such that A(x) − ρI is still positive definition for all x ∈ U .
The following theorem shows the maximum of a (super-)solution of a second order elliptic differential equation can only have its maximum points on the boundary. We will strengthen this result to functions on a probability simplex (Lemma 5.16).
Theorem 3.5 (maximum principle of elliptic PDE [11]). Suppose that L is uniformly elliptic and Lu ≥ 0 for a function u ∈ C 2 (U ). Then the function u must attain its maximum on the boundary Moreover, if u has an interior maximum, u is a constant.

Singleton Information Structure
As a warm-up, let's consider the principal exactly knows the agent's information structure so that X = {X} is a singleton. We show the optimal H can be an upside down pyramid. (Fig. 1)

Since the information gain
Proof of Theorem 4.1. Let H be the upside down pyramid in Theorem 4.1, and H ∈ H be an arbitrary bounded convex function.
by the Jensen's inequality. Now we consider h 0 < 1. LetH be a convex piecewise linear function whose epigraph has vertices at (E X, h 0 ), and Second, because the epigraphs of H andH are both upside down pyramids, and the vertices are aligned, we can convertH to H through an affine transformation: because 0 ≤ h 0 < 1, and both sides are non-negative. Combining Eqs. (6) and (7), , and complete the proof.
When the state space is binary Ω = {0, 1}, by Eq. (4), the upside down pyramid H is v-shaped, and Theorem 4.1 yields the following corollary.
These results suggest the principal should choose H that is "curved" at the prior in order to incentivize the agent to derive the signal and move away from the prior. This intuition is useful for the later sections.

Finite Information Structures
In this section, we give a polynomial time algorithm that computes an optimal scoring rule when the collection of information structures is finite as defined below.
We call a collection of information structures X finite if |X | is finite and all X ∈ X has a finite support | supp(X)| < ∞.
The notion of finite collection of information structures is natural when there is a finite number of heterogeneous agents with finite set of information.
, and X is finite with |supp(X )| = m, there exists an algorithm that computes an optimal bounded proper scoring rule and the running time is polynomial in d and m.
The main idea is that when X is finite Obj X (H) in Eq. (2) only depends on the evaluations of H in supp(X ). Thus, instead of searching for all possible bounded scoring rules, we can reduce the dimension of Problem 1 and use a linear programming whose variables contain the evaluations of H in supp(X ) and add linear constraints to ensure those evaluation can be extended to a convex function. This observation allows us the solve the problem in weakly polynomial time which is polynomial in d and m but may not be polynomial in the representation size.
Proof of Theorem 4.4. The idea is to construct a linear programming whose variables contain the evaluations of H in supp(X ). To formulate this, we introduce some notations. Given |X | = n, we set To simplify the notations, we assume supp(X ) does not contain any vertex of ∆ d e k for k = 1, . . . , d and for all distinct α, α in A, x α = x α . 4 Note that the objective value only depends on a finite number of values. Specifically, given H(x α ) = h α for any α ∈ A, the objective, Eq. (2), is Thus, we can first decide h α to maximize Eq. (8), and "connect" those points (x α , h α ) to construct a piecewise linear function. To ensure the resulting function is convex, we further require there exists a supporting hyperplane for each ( In summary, we set the convex function to be and the collection of h α and g α is a solution of the following linear programming, The above linear programming has constraints, so we can solve it in polynomial time with respect to m and d. Now we need to show H is 1) convex, 2) bounded in [0, 1], and 3) optimal. It is easy to see for all α ∈Ā, because =h α (by the constraints in Eq. (10)) First because H is the maximum of a collection of linear functions, H is convex. Second, for the lower bound, by the constraints in Eq. (10) and (11). Finally, for any bounded convex functionH ∈ H, we seth α =H( 5 SinceH is convex and in H, the collection ofh α and g α is a feasible solution to Eq. (10), and Obj X (H) ≤ Obj X (H).
Note that if X contains a constant information structure X, the resulting linear programming (10) will output an arbitrary piecewise linear convex function, because the objective value is always zero (Footnote 4).

Unique Optimality of an Convex Function
In this section we ask given any convex H, is there a collection of information structures X that uniquely settles H? (Problem 2) First Proposition 4.5 shows a simple necessary condition of H to be uniquely settled for some X . For convex piecewise linear function, Theorem 4.6 shows such necessary condition is also sufficient, and we can construct a finite collection of information structures (Definition 4.3) to uniquely settle those convex piecewise linear functions. Similarly, Proposition 4.7 shows any convex H satisfying the necessary condition can be uniquely settled on any closed set U that does not contain any minimum or maximum point of H. However, Proposition 4.8 shows no collection of information structures uniquely settles a quadratic function which contrasts the unique optimality of quadratic scoring rules in an asymptotic setting in Section 5.1.
The formal proof is in Appendix B. Intuitively, we can show that if one of the condition does not hold, we can construct an other convex function that has a larger or the same information gain of any information structure.
Convex piecewise linear functions Now, we consider sufficient conditions for piecewise linear functions H. Theorem 4.6 shows the necessary conditions Eq. (12) is also sufficient for any convex piecewise linear functions. Our proof is constructive: Given a point θ ∈ ∆ d , we can create information structures to upper bound and lower bound the evaluation of an optimal convex function. The proofs and details are in Appendix B.
General convex functions We can also use the same idea on a general convex function. Proposition 4.7 shows that we can construct a collection of information structures such that the optimal H agrees with H with all except θ ∈ ∆ d with extreme large or small H(θ). Moreover, for all closed set U ⊂ ∆ d that does not contain any minimum or maximum point of H, there exists X H,U that uniquely settles H on U .
However, Proposition 4.8 shows this limit is inevitable and no collection of information structures uniquely settles a quadratic scoring rule which satisfies Eq. (12). Finally, it's not hard to extend this example to show that no collection of information structures can settle any strictly convex function.
Proposition 4.8. For any collection of information structures X which settles the quadratic scoring rule on binary state space Q 2 (x) = 4(x − 1 2 ) 2 , there exists another optimal H for X but H = Q 2 . Proof of Proposition 4.8. Let δ := Opt(X ). If δ = 0, any convex function is optimal and we are done. If δ > 0, we define x δ :

Asymptotic Setting
Now we study optimal incentive scoring rules for eliciting estimation from Bayesian agents when the number of samples n is large. Because as the number of samples increases, the mean squared error (variance) is vanishing for any consistent estimator, Opt(lim n→∞ X n ) = 0, we use the relative information gain in Problem 3 to evaluate a proper scoring rule. Section 5.1 considers a sequence of collection of information structures with vanishing covariance, and shows the quadratic scoring rule is uniquely optimal. In Section 5.2, the data are generated from exponential families with conjugate prior (Beta-Bernoulli and Dirichlet-Categorical process), and the log-scoring rule is uniquely optimal. Though both Sections 5.1 and 5.2 consider eliciting Bayes estimator with large samples, Section 5.1 models general prior and observation which can be continuous, while the setting in Section 5.2 is more restricted, e.g., observation is in [d].

Vanishing Covariance Information Structures
Consider the agent can access n i.i.d. samples to estimate the distribution of the ground state W . What is a natural sequence of collections of information structures to model this process? By Bayesian Cramér-Rao lower bound [17], the variance (covariance) of the posterior distribution P (W |S (1) , . . . S (n) ) is of order Θ(1/n) for large n. Thus, the variance of the posterior with n-th signal given the first n − 1 samples is of order Θ(1/n 2 ). 6 This motivates us to consider a sequence of collections of information structures where the norm of covariance matrix is bounded below: and X n emulates the set of the posterior with the k-th sample where k ≤ n. Additionally, as n goes to infinity X contains all possible non constant information structure. Finally, the sequence is homogeneous and isotropic: whether an information structure X is in X n is independent of the position and direction so that translation and rotation do not affect the membership.
Our main results in this section show that a quadratic scoring rule is optimal for the sequence X n . The first result (Theorem 5.1) shows that the information gain Eq. (2) is of order 1/n 2 for any convex function, and the constant is maximized if and only if H is the quadratic function Q. Then, we can translate the result into relative information gain, and show the quadratic scoring rule maximizes the relative information gain against all smooth function on int(∆ d ) for (X n ) n∈Z>0 in Corollary 5.2. To prove Theorem 5.1, the main idea is that the information gain J H (X) only depends on the "curvature" of H at E X that is the strongly-convexity of H. (Lemma 5.4) Then, it is sufficient to show that the quadratic function Q has the largest possible curvature in H. (Lemma 5.5) The following lemma show it is sufficient to consider random variable X with Cov(X) 2 = 1/n 2 .

Lemma 5.3 (scaling).
Let H ∈ H and n ∈ Z >0 . For all X ∈ X n , there existsX ∈ X n so that Cov(X) 2 = 1/n 2 and J H (X) ≥ J H (X).
Then we connect information gain of X n to strongly convexity of a function. The proofs of Lemmas 5.3 and 5.4 are in Appendix C.
Lemma 5.4 (strongly convex). If H ∈ H ∩ C ∞ (int(∆ d )), H is α-strongly convex in int(∆) if and only if inf X∈Xn: Cov(X) =1/n 2 J H (X) ≥ α 2n 2 + o 1 n 2 . Finally, we show the most "strongly convex" function in H is the quadratic scoring rule Q. Intuitively, if a function H is more strongly convex than Q, the difference H − Q is a convex function, and H is greater than Q at one of the vertexê k which is a contradiction because Q(ê k ) = 1 for all k ∈ [d]. Proof of Lemma 5.5. If H ∈ H is 2d d−1 -strongly convex, we define the symmetrization of H as where S d is the set of all permutations on [d]. We first prove H(c) = 0 and ∇H(c) = 0.
Since the symmetrization H sym is also 2d d−1 -strongly convex, smooth, and in H, the following function is convex on ∆, K(x) := H sym (x) − H sym (c) − Q(x). Because H sym is convex and symmetric with respect to c, H sym (c) = min x∈∆ H sym (x), and ∇H sym (c) = 0 which proves the second part of Eq. (14). For the first part of Eq. (14), ∇K(c) = ∇H sym (c) − ∇Q(c) = 0, and K(x) ≥ K(c) = 0 for all x ∈ ∆ by Eq. (5). As a result, for any vertexê j , so H sym (c) = 0, and the vertices K(ê j ) = 0 for all j = 1, . . . , d. Because K ≥ 0 is convex and the evaluations at vertices are zero, K(x) = 0 for all x ∈ ∆, so Finally, because H is smooth and 2d d−1 -strongly convex, by Lemma 3.3, for all x ∈ int(∆) and v ∈ R d with 1 However, by Eq. (15),

Exponential Family Information Structures
Now we consider two common families of information structures in Bayesian inference: Beta-Bernoulli and Dirichlet-categorical information structures. Specifically, the principal wants to predict the outcome of a d-sided dice. First, the principal announces her proper scoring rule to encourage the agent to collect signals through rolling the dice once (first setting) or a fixed amount of times (second setting). The agent then reports his prediction. Finally, the dice is rolled and the agent gets his payment according to the outcome and the proper scoring rule.
In Section 5.2.1 we consider d = 2. As an warm-up, we begin with the static settings where the agent can only collect a fixed number of samples and apply Theorem 4.4 to solve the optimal scoring rules. Then we study the asymptotic setting, and show the log scoring rule is optimal. We further extend this result to general d-sided dice in Section 5.2.2.

Beta-Bernoulli Information Structure
Suppose we want to collect predictions on an outcome of a coin. Given p ∈ [0, 1], the outcome W follows the Bernoulli distribution Bern(p) with Pr[W = 1] = p, whereas the true value of p is unknown. We consider the following two cases.
1. Knowing that the agent privately observes N i.i.d samples from the coin, we want to incentivize the agent to make one additional observation.
2. We want to incentivize the agent to collect N +1 samples adaptively. That is for any sequence of n ≤ N samples from the coin, the information gain of the (n + 1)-th sample is large enough to incentivize the agent to observe.
In both cases, the agent starts with an uninformative prior on the parameter of the coin p that is a uniform distribution on [0, 1].

Static Setting
In the first case, if the agent already observes n 1 heads and n − n 1 tails, his prior on W = 1 is θ = n1+1 n+2 , and the posterior predictive distribution is X (n) θ := P (W = 1 | S) that is a Beta-Bernoulli information structure with (θ, n + 2), Note that because the agent starts with the uniform prior, his effective sample size after n observation is m = n + 2. By Eq. (4), the information gain of the (n + 1)-th observation under a convex function H : Thus to elicit the (N + 1)-th observation, the objective value in Eq. (2) is When N ∈ Z ≥0 is finite, the collection of information structures X (N ) θ : θ = 1 N +2 , . . . , N +1 N +2 is finite. Hence, finding an optimal H for Eq. (17) is studied in Section 4.2. For the second case, to incentivize the agent to collect N + 1 costly observation adaptively, we need to ensure for any sequence of n ≤ N samples, the agent's expected information gain of the (n + 1)-th observation is large. Thus, the collection of information which is also finite. Figure 2 shows examples of the optimal scoring rules in the above two cases with a finite effective sample size N . However, as N increases the size of corresponding linear programming becomes larges. For instance, if we want to incentivize the agent to collect N + 1 samples adaptively, the number of variable is Θ(N 2 ) which is the length of Farey sequence of order N + 1. 7 In the next section, we are going to show the optimal scoring rules is the log scoring rule in Eq. (23) when N → ∞.
Asymptotic Setting Instead of the static setting with a fixed number of samples, now we consider the agent can indefinitely get samples, and define a sequence of collections of Beta-Bernoulli information structures as follows,X which is the collection of all Beta-Bernoulli information structures with an effective sample size at most N and δ N < θ < 1 − δ N where δ N ∈ o(1) and δ N ∈ ω(1/N ). Note thatX ≤N Beta is an increasing sequence and lim N →∞X ≤N Beta = X Beta := {X (N ) θ : 0 < θ < 1, N ∈ N} contains all Beta-Bernoulli information structures. Our main result in this section shows that a log scoring rule is optimal for the sequenceX ≤n Beta . Theorem 5.6. Let H ∈ H ∩ C ∞ ((0, 1)) be smooth on (0, 1).

Moreover the equality holds if and only if
We can also rewrite this result in terms of relative information gain, and show the log scoring rule maximizes the following relative information gain on the sequence in Eq. (18) against any function in H ∩ C ∞ ((0, 1)). In contrast to vanishing covariance information structures in Section 5.1, the variance of a Beta-Bernoulli information structure depends on the mean. For example, the posterior X (N ) 0.5 with mean 0.5 changes rapidly, but X (N ) 0.98 with mean 0.98 hardly changes. Additionally, the movement becomes small as the prior mean approaches the vertices 0 or 1, so a good scoring rule should be more curved as well.
The proof structure is similar to Theorem 5.1. We defer the proofs of the following two lemmas to Appendix D.
The next lemma relates the objective value to a second order differential operator D beta for any smooth function h : (0, 1) → R where h is the second derivative of h. Note that for the log scoring rule, D beta H ln (x) = 1 ln 2 for all x ∈ (0, 1). Lemma 5.9. For any smooth convex H ∈ H ∩ C ∞ ((0, 1)), and X ∈X N Beta , when N is large enough. Moreover, ObjX N Beta (H ln ) = 1 2(ln 2)(N +3) 2 + o 1 (N +3) 2 , for log scoring rule. 7 Farey sequence of order m is the sequence of completely reduced fractions between 0 and 1 and the denominators are less than or equal to m.
Informally, the first part of Lemma 5.9 is a "pointwise" characterization where for each θ, X (N ) θ the information gain pointwise converges to D beta H(θ) 2(N +3) 2 , and the moreover part is an "almost uniform" characterization, where the information gain converges to the limit almost uniformly in (0, 1), because (δ N , 1 − δ N ) → (0, 1) as N → ∞.
Finally, we show the log scoring rule with H ln has the largest inf x D beta H(x) for all smooth H ∈ H.
The converse holds by Lemma 5.9 and 5.8.
Note that for any N the setX ≤N Beta does not contain all Beta-Bernoulli information structures with effective sample size at most N , but it additionally requires the mean δ N ≤ θ ≤ 1 − δ N is bounded away from the vertices, 0 and 1. This restriction is due to the log scoring rule's singular behavior around the vertices. In particular, in Lemma 5.9 the information gain J H ln (X (n) θ ) only converges pointwise to D beta H ln (θ) and the constant in the error term increases as θ approaches the vertices. In other words, Theorem 5.6 ensures the log scoring rule is optimal in an almost uniform manner, but Theorem 5.1 shows the quadratic scoring rule is optimal in a uniform manner. In Fig. 3, we numerically show the optimal scoring rules under the first case with finite N converge to the log scoring rule.

Dirichlet-Categorical Information Structure
We will show the log scoring rule is still the optimal scoring rule for the collection of Dirichlet-categorical information structures.
If |Ω| = d, let θ ∈ Θ = ∆(Ω) and m ∈ N >0 . Let Dir(θ, m) be the Dirichlet distribution where the probability density at p ∈ ∆(Ω) is proportional to Π d k=1 p θ k m−1 k . Let θ be the mean and m be the effective sample size. We similarly define Dirichlet-categorical information structure with (θ, m) as follow: p is sampled from Dir(θ, m). The state of the world W and signal S are sampled independently from Cat(p) where the outcome is k with probability p k . Figure 3: We plot the log scoring rules H ln and the optimal scoring rules under the static setting which is the first case with constant N . The rightmost panel shows the difference between those optimal scoring rules and the log scoring rule.
We will generalize Beta-Bernoulli information structures (16) and the log scoring rule Eq. (19) with d = 2 to general d-dimensional cases. When the agent's prior is Dir(θ, n + d), the information structure of the (n + 1)-th sample is X Furthermore, we consider the following sequence of collections of information structures where δ N ∈ ω(1/N ) and δ N ∈ o(1).
Our main results (Theorem 5.11 and Corollary 5.12) show that a log scoring rule is optimal for the sequenceX ≤n dir . However, we only show H ln is optimal against any function that is smooth on the close set ∆ d , instead of the relative interior int(∆ d ). Notice that H ln is smooth on int(∆ d ) but not smooth on ∆ d , but several standard proper scoring rules are smooth on ∆ d , e.g., quadratic, and spherical scoring rule. Therefore, our results still provide relevant comparison among common scoring rules.
We can also rewrite this result in terms of relative information gain as Corollary 5.12. The proof structure is mostly identical to Theorem 5.6. However, the main challenge is Lemma 5.15 which shows the log scoring rule maximizes a differential operator D dir defined in Eq. (24). We prove Lemma 5.15 in Section 5.2.2, and omit rest of the proofs. The next lemma relates the information gain to a second order differential operator D dir , for all smooth h ∈ H and x ∈ ∆(Ω) where (ê k ) d k=1 are the vertices of simplex ∆(Ω). The proof is basic identical to the proof of Lemma 5.9. Lemma 5.14. For any smooth convex H ∈ H∩C ∞ (int(∆ d )), and Dirichlet-Categorical information structure when N is large enough. Moreover, for log scoring rule, Finally, we show the infimum of D dir on H ln is greater than the infimum of D dir on any H ∈ H which is smooth on ∆ d . The idea stems from the maximum principle of elliptic second order differential equations.
Proof of Lemma 5.15 Despite being similar to Lemma 5.5 and 5.10, the proof of Lemma 5.15 is quite challenging. To see this, Lemma 5.10 only needs to handle functions in an one dimensional space and a lower bound of D beta is sufficient to characterize such function fully. In particular, once we know D beta h(x) we can compute the second derivative of h at x. Similarly, Lemma 5.5 handles on functions on d-dimensional space, but the notion of strongly convex is also rich enough to fully determine the function. However, D dir is a differential operator with scalar value, so we cannot reconstruct h from the value of D dir h. To address this, we use the idea of maximum principle (Theorem 3.5) to proof Lemma 5.15. Note that D dir (H ln )(x) = d−1 ln d for all x and H ln ∈ [0, 1]. Suppose there exist a function H = H ln in ln d for all x ∈ int(∆ d ). We will show there exists an extreme point of the simplexê j such that H(ê j ) > H ln (ê j ) = 1, for all x ∈ int(∆ d ). Let θ * ∈ ∆ d be a maximum point of u. Now, we will show max u(x) > 0 andê 1 = θ * is a maximum points which proves Eq. (25) and completes the proof. Because D dir in Eq. (24) is a second order differential operator with where (26) is a partial differential equation on u. Ideally, we want to use the maximum principle (Theorem 3.5) and show that the maximum happens at the vertex so that u(ê k ) > u(c) = 0 which implies Eq. (25) and completes the proof. However, since A dir (x)1 = 0 for all x, D dir is not elliptic, and we cannot use the standard maximum principle. Thus we use a maximum principle which holds under this weaker condition.
Lemma 5.16. Let V ⊂ R d be a linear subspace, and W ⊂ R d be a bounded set where {x − w : ∀x ∈ W } ⊂ V is relative open to V for some w ∈ R d . If a second order differential operator L with A satisfies the following two conditions: 1) L is uniformly elliptic on W which has ρ > 0 so that for all x ∈ W and v ∈ V, v A(x)v ≥ ρ v 2 2 , 2) the image of A is in V, null(A(x)) = V ⊥ for all x ∈ W , then for any super-solution h satisfies Lh ≥ 0 and continuous on cl(W ), Moreover, if h has an interior maximum, h is a constant.
This result can be derived from Theorem 3.5, because we can use d−1 coordinate to encode the space. The first condition says L is uniformly elliptic on the subspace and the second condition ensures the differential operator is well-defined. Alternatively this is also a special case of maximum principle on Riemannian manifolds. [26]. We include a proof in Appendix D for completeness.
Back to our proof of Lemma 5.15, though D dir is not uniformly elliptic on int(∆ d ), D dir is uniformly elliptic on U := {x ∈ ∆ d : x k ≥ , ∀k ∈ [d]} for any > 0. We set V dir = {v ∈ R d : 1 v = 0} and {x − c : ∀x ∈ U } ⊂ V dir , and by Lemma 5.16 the maximum value of u happens at the boundary of U . Suppose that u has an interior maximum θ * . we can set small enough such that θ * ∈ int(U ) which reaches a contradiction. Therefore, θ * can only be in the boundary, and, due to the symmetry of u, we can assume Since u(c) = H(c) − H ln (c) = 0 and u is not constant, u(θ * ) > 0.
Now we want to can the maximum principle recursively such that the maximum can be only atê 1 which completes our proof. Formally, it is sufficient to prove ln d , by direct computation. Therefore, we can apply Lemma 5.16 again and show θ * ∈ ∆ d−2 . By induction, θ * =ê 1 and this completes our proof.

A Details and Proofs in Sections 2 and 3
Proof of Proposition 2.1. First note that the sequence (Obj Xn (H)) n is non-increasing, because X 1 , . . . is non-decreasing, and Obj Xn (H) ≥ 0 for all n by the Jensen's inequality. Thus, lim n→∞ Obj Xn (H) exists. Now we show that lim Because X n ⊆ X for all n, lim n→∞ Obj Xn (H) ≥ Obj X (H). To show lim n→∞ Obj Xn (H) ≤ Obj X (H), given any > 0, there exists X ∈ X such that J H (X) ≤ infX ∈X J H (X) + = Obj X (H) + . Because X ∈ X , there exists N so that for all n ≥ N , X ∈ X n . Hence lim n Obj Xn (H) ≤ J H (X). Combining these two, we have lim n Obj Xn (H) ≤ Obj X (H) + for all which proves Eq. (28). Therefore, if Opt(X ) > 0, we can apply the limit operator separately in Eq. which shows the Problem 1 and 3 are equivalent.
Proof of Lemma 3.3. Suppose H is α-strongly convex in int(∆). Given any x ∈ int(∆) and v ∈ R d with 1 v = 0, we can pick a small t ∈ R >0 such that y := x + tv ∈ int(∆). First by Taylor expansion, there exists some 0 ≤ τ ≤ t such that Then we apply Eq. (5), and have v Conversely, if for all x ∈ int(∆) and v ∈ R d with 1 v = 0, we have v ∇ 2 H(x)v ≥ α v 2 , we want to show Eq. (5) is true. For any x, y ∈ int(∆), we set v = y − x ∈ R d . Again by Taylor's expansion, there exists some z ∈ int(∆) such that H(y) = H(x) + ∇H(x) v + 1 2 v ∇ 2 H(z)v. Finally, because x, y ∈ int(∆) and z ∈ int(∆), v j = 0 and v ∇ 2 H(z)v ≥ α v 2 . Therefore, we complete the proof. For the second condition, suppose there exists j * ∈ [d] such that H(ê j * ) < 1. Becauseê j for j ∈ [d] are all the vertices of ∆ d , any x ∈ ∆ d is a convex combination of those vertices, x = j α jêj where α j ≥ 0 and j α j = 1. With this notion, we define an affine function K(x) = K( j α jêj ) := j α j (1−H(ê j )), and two new bounded convex functions H 1 (x) := H(x) + K(x) and H 2 (x) = 1 1−min H1 (H 1 (x) − 1) + 1 for all x ∈ ∆ d . First, because adding the affine function K does not change the information gain, Obj X H (H 1 ) = Obj X H (H). Additionally, because min H 1 > 0, Obj X H (H 1 ) < Obj X H (H 2 ). Combining these two inequality, we have Obj X H (H) < Obj X H (H 2 ).

B.2 Upper and Lower Bound Evaluations of a Convex Function
We prove this result by constructing a set of information structures to upper bound (Lemma B.1) and lower bound (Lemma B.2) the evaluation of an optimal convex function at a point θ ∈ ∆ d . Lemma B.1 (upper bounds). Let H satisfy Eq. (12) and X be a collection of information structures which settles H and 0 < Opt(X ). For any θ ∈ ∆ d , there exists a constant C θ > 0 so that if Opt(X ) ≤ C θ , there exists an information structure X up θ such that X ∪ {X up θ } settles H and H (θ) ≤ H(θ) for any optimal H for X ∪ {X up θ }. Proof of Lemma B.1. Because ∆ d is a convex hull of (ê j ) j∈[d] , we use α j (x) to denote the weight of vertex e j for the point x such that x = j α j (x)ê j .
Given θ ∈ ∆ d , if H(θ) = 1, we can pick an arbitrary information structure in X , and the two conditions trivially holds. Otherwise, if H(θ) < 1 and Opt(X ) ≤ C θ := 1 − H(θ), we construct X up θ such that First, let's compute the information gain of X up θ on H, If θ * is a minimum point of H, by Lemma B.1, we set X * be the information structure so that H (θ * ) = H(θ * ) = 0 when X * settles H . Lemma B.2 adds X * to lower bound an evaluation of an optimal function. Lemma B.2 (lower bounds). Let H satisfy Eq. (12) with minimum at θ * and X be a collection of information structures which settles H and 0 < Opt(X ). For any θ ∈ ∆ d , there exists a constant D θ > 0 so that if Opt(X ) ≤ D θ , there exist information structures X lo θ and X * such that X ∪ {X lo θ , X * } settles H and H (θ) ≥ H(θ) for any H that is optimal for X ∪ {X lo θ , X * }. Proof of Lemma B.2. Since the convex function H satisfying Eq. (12), there exists θ * ∈ ∆ d such that H(θ * ) = 0. First, if H(θ) = 0, we can pick an arbitrary information structure in X , and the two conditions trivially holds. If H(θ) > 0, θ = θ * and there exists j * ∈ arg max j θ j − θ * j . Hence, we can represent the minimum point θ * as a convex combination of θ andê j with j ∈ [d]\{j * }, θ * = β j * θ + j =j * β jêj . We define an information structure X lo θ such that Pr[X lo H(θ)). For the first condition, by direct computation, Thus, Obj X ∪{X lo θ } (H) = Opt(X ) = Opt(X ∪ {X lo θ }). Finally, by Lemma B.1 we can add X * without changing the optimal value, and ensure H (θ * ) = 0 for any optimal H . When H is optimal for X ∪ {X lo θ }), J X lo θ (H ) ≥ Opt(X ), and β j * H (θ) + 1 − β j * ≥ β j * H(θ) + 1 − β j * which proves the second condition.

B.3 Proof of Theorem 4.6
Now we use these lemmas to prove Theorem 4.6. To illustrate the idea, we first consider H is a v-shaped convex function on [0, 1] with the minimum point at θ * . We pick two points θ 0 and θ 1 with 0 < θ 0 < θ * < θ 1 < 1. First we add an information X * to X H such that Pr[X * = θ * ] = 1 − , Pr[X * = 0] = (1 − θ * ) , and Pr[X * = 1] = θ * . For any > 0, we have if H is optimal for {X * }. If we take small enough, we can apply Lemmas B.1 and B.2 for θ 0 and θ 1 , and add four additional finite information structures to {X * } such that Now we want to show the resulting finite collection of information structures X H ensures H = H when H is optimal for X H . For all 0 < θ < θ 0 , by Eq. (29), H is a convex function below H because the epigraph of H is polytope with vertices at 0, 1 and θ * , so H (θ) ≤ H(θ). On the other hand, because Therefore, H (θ) = H(θ) for all 0 < θ < θ 1 . We can repeat this argument to the other three intervals where H is affine (θ 1 , θ * ), (θ * , θ 1 ), and (θ 1 , 1). The above proof can be easily adapted to any convex piecewise linear function.
Proof of Theorem 4.6. We prove it by constructing a finite collection of information structures X H . Before defining X H , we introduce some notations. Because H satisfies Eq. (12), H(ê j ) = 1 for all j ∈ [d] and there exists θ * ∈ ∆ d with H(θ * ) = 0. Since H : ∆ d → R is a convex piecewise linear function, there exists a finite set of affine functions A : ∆ d → R and A ∈ A, such that Because H is convex and piecewise linear, the epigraph is a polytope. We define F A = {x ∈ ∆ : H(x) = A(x)} which is the set of points x where H is agree with the affine function A. Because F A is also the domain of a face of epigraph of H, F A is a convex of a finite number of vertices v A 1 , . . . v A d A . Finally we additionally pick an interior point u A ∈ F A for each A ∈ A. Now, we are ready to define X H which is similar to the v-shaped case. First, we add X * such that Pr[X * = θ * ] = 1 − , and Pr[X * =ê j ] = (1 − )α j (θ * ) for all j ∈ [d]. For any > 0, we have H (θ * ) = 0 and H (ê j ) = 1 for all j ∈ [d] (31) if H is optimal for {X * }. Because the set of vertices {v A k : A ∈ A, k ≤ d A } and interior points {u A : A ∈ A} are finite, we can pick > 0 small enough, and apply Lemmas B.1 and B.2 adding a finite number of finite information structures to X H such that for all A ∈ A, 1 ≤ k ≤ d A , and if H is optimal for X H . For any A ∈ A and θ ∈ F A , by Eqs. E X * = x * and Cov(X * ) = E[(X * − x * )(X * − x * ) ] = n −2 vv , so Cov(X * ) 2 = 1/n 2 . Thus X * ∈ X n . Second ).
Proof of Lemma 5.8. Given a Beta-Bernoulli information structure X with (θ, n), if X ∈ X ≤N Beta , we have n ≤ N . We want to show another Beta-Bernoulli information structureX ∈ X N Beta with (θ, N ) has a smaller information gain.
Proof of Lemma 5.16. The proof is very similar to Theorem 3.5 in Evans [11]. Informally although the matrix A is only positive definition in a linear subspace, we also only need to ensure the maximum position in the same space. Because v 1 , . . . , v k is an orthonormal basis of V, we can add d − k vectors v k+1 , . . . , v d such that v 1 , . . . , v d is an orthonormal basis for R d . Suppose x * is an interior maximum point of h in W . Since h is smooth, ∇ 2 h(x * ) is symmetric matrix, and v ∇ 2 h(x * )v ≤ 0 for all ∈ [k] by the second derivative test. Therefore, there exists λ 1 , . . . , λ d such that λ 1 , . . . , λ k ≤ 0, and ∇ 2 h(x * ) = λ v v . First we assume u is a strict supersolution such that 0 < Lh(x) for all x ∈ W . For x = x * , we have