Eliciting information about uncertain events is crucial for informed decision making. Information is often acquired by individual agents. To achieve collective intelligence, the key problems are to elicit and aggregate timely and truthful information from dispersed agents.
Prediction markets (PMs) allow agents to bet on the occurrence of future events: the outcome of a presidential election, the winner of a football game, etc. Market prices reflect society's aggregated estimate of the outcome. However, prediction markets tend to only pay the first agent bringing information to the market. For example, in the market of a tennis match, if one player wins a set, likely the price of the market will shift dramatically. Because sportscasts are usually delayed by a few seconds, agents with real-time information (say with a confederate attending the match) reap the rewards by trading just seconds before others. This provides little to no societal value as the price would be updated seconds later anyhow. This practice is widespread. People, called "courtsiders", are paid to attend sports events and send back real-time information [10,13]. The US Open ejected 20 spectators for courtsiding and banned them from future events [24]. While this information is useful to those profiting from it, it is hardly more than a waste of money and time for our society.
The importance of speed in trading on information is underscored by the infamous $300 million, 827 mile fiber optic cable from New York City to Chicago. The cable reduced the round-trip latency to 13.1 milliseconds [1] by offering a more direct route, bypassing Philadelphia, than the previous 1000 mile cable took with round trip latency 14.5 milliseconds.
We want to design systems that work well for society rather than promoting speed that is not needed but is merely a byproduct of the market design. Increasingly, businesses are seen not merely as profit-maximizing, but as responsible and responsive to their various stakeholders [25].
Maximizing welfare rather than profit has various economic motivations as well. To gain market share and maximize long-term revenue, a company may also want to benefit other companies that it makes deals with. For example, many sponsored search auctions maximize welfare instead of revenue [22]. Since profit is a lower bound of social welfare (when agents' utility is non-negative), higher welfare potentially leads to high profit. Welfare-maximizing auctions and profit-maximizing auctions are shown to be very close in terms of both welfare and efficiency [2,7]. In our settings, though our mechanism maximizes social welfare, its profit is still high, illustrated in Figure 7.
Apart from social welfare concerns, another potential challenge with prediction markets is that agents may want to delay reporting their information to increase their rewards [4,9,20]. We show that in the settings we study, this is still a problem for traditional prediction markets, and we resolve this problem in our mechanisms.
Motivated by the above concerns, we answer the following question: How to aggregate timely and truthful information to maximize social welfare?
We formulate the process as a principal-agent problem. The principal first suggests a contract which maps agents' reports to rewards. Then each agent decides his hidden actions (how much effort and how to report) strategically to maximize his utility. The principal knows neither agents' actions nor the relation between agents' actions and quality of information. This makes our problem different from those in standard contract theory. To resolve this, we design two new markets to maximize social welfare under the following two settings.
In the single batch setting, a principal needs to decide by a particular deadline. To maximize social welfare, the principal needs to incentivize agents to invest the correct cost. Agents' costs are hidden, and they can misreport. For this setting, we propose the Fair Prediction Market (FPM, Mechanism 1), in which the expected reward for every truthful agent is the same.
In the sequential setting, the value of information decreases as time passes. Besides dealing with agents' hidden costs and misreporting behaviors, the principal also needs to encourage timely reports. We propose the Marginal Value Prediction (MVP) Market (Mechanism 2), in which every agent is paid by his contribution to the value of information.
Compared to the traditional prediction market, our mechanisms have more desirable properties, as shown in Table 1.
One line of works studies when agents should report their signals in prediction markets [4,9,15,20]. They find that whether information will be aggregated quickly depends on agents' information structure. Agents will delay reporting if their information is "complementary", and rush to report if it is "substitutional". Earlier in the finance literature, [14,19,21] analyze how private information is disseminated into real financial markets using different models.
The market behavior depends on the numbers of insiders, noise traders, and market makers. Chakraborty and Das [8] find that when agents are risk-averse, the market scoring rule acts as an opinion pool. Agents' risk aversion avoids the issue that agents will always pull the market price toward their own belief without ever reaching a consensus. We do not have this issue because, in our model, agents believe that the signals of each other are useful and are willing to do Bayesian updates.
For costly information, if the effort level is binary, it's wellknown that we can scale the reward to compensate for the cost of effort. This approach encourages agents to invest effort and increases the liquidity of the prediction [23]. In our paper, we consider a more complicated setting: The effort level is continuous, and the relation between agents' actions and the quality of information is unknown. Azar and Micali [3] uses contract theory to delegate computation where acquiring data is costly, but assume the principal has some ability to verify the data. Moreover, our goal is to maximize social welfare, not just collect accurate decisions.
Budish et al. [6] investigate the continuous limit order book market and the high-frequency trading arms race. They show examples that such arms races induce rents that harm the liquidity of the market. They propose a frequent batch market which discretizes the time to mitigate the necessity to be first, and show that the above-mentioned example does not hold in their new markets.
In Section 2, we provide some basic notations, assumptions, and definitions; frame the problem we want to solve; and describe how prediction markets work. In Section 3, we show how prediction markets may fail to collect timely reports. In Section 4, we propose Mechanism 1 for the single-batch setting and show that it is truthful and maximizes the social welfare. In Section 5, we propose Mechanism 2 for the sequential setting and show that it is truthful, timely and maximizes social welfare. At last, we present some concrete examples to compare our mechanism to prediction markets in Section 6.
There is a principal and a set of agents N = {1, . . . , 𝑛}. 1 Let Y be the outcome space, 𝑦 ∈ Y be the true outcome, and 𝑌 be the random variable for the outcome. For each agent 𝑖 ∈ N , let 𝑋 𝑖 be the private information of agent 𝑖, and X 𝑖 be the set of possible values of 𝑋 𝑖 where X 𝑖 is finite. The principal wants to collect information from agents to better predict 𝑦, and her utility depends on the value of information. Example 2.1. Consider a binary outcome space Y = {0, 1}, and binary signal spaces X 𝑖 = {0, 1} for all 𝑖 ∈ N . The prior of the outcome is given by Pr[𝑌 = 1] = 𝛼. There is a noise level 𝛽 ∈ [0, 1/2) such that each signal is an independent noisy observation of the outcome Pr[𝑋 𝑖 = 𝑌 ] = 1 -𝛽 for all 𝑖 ∈ N and 𝑦 ∈ {0, 1}. Suppose the principal wants to predict 𝑌 and her utility is 1 (-1) if correct (incorrect). Let 𝛼 = 1/2. If she only knows the prior of the outcome, her expected utility is 0. However, if all agents collectively provide their prediction Pr[𝑌 | 𝑋 1 , . . . , 𝑋 𝑛 ], the principal's utility is greater than 0. For example, if 𝑛 = 1, her expected utility is 1 -2𝛽 > 0.
Acquiring signals is costly for agents. Hence, agents may not bother to invest effort and may misreport their information. The principal needs to incentivize agents to invest some effort to acquire their signals, without observing how much effort they actually invest. Formally, the mechanism has three stages:
(1) The principal publishes a contract which maps reports and the outcome to payments. Agents accept (or refuse).
(2) Each agent chooses a hidden effort level and submits a report to the principal. (3) The true outcome (that agents are guessing at) is revealed.
The principal rewards each agent according to the contract. Each agent's utility is his reward from the principal minus his effort level. Agents are rational and maximize their expected utility based on their beliefs over future events. The principal's utility is the value of information minus the rewards given to the agents. The social welfare is the total utility of all agents and the principal.
We want to design mechanisms whose resulting social welfare equals that in the centralized setting, where every agent's action is controlled by the principal. In particular, we hope that the agents invest the same amount of effort and report just the same as in the centralized setting.
Throughout the paper, we are only looking for symmetric equilibrium. This is reasonable since agents' signals are i.i.d. and they have no a priori means to coordinate. However, it is important to know that a non-symmetric strategy profile can be better than a symmetric one in terms of social welfare. For instance, as shown in Figure 1, social welfare may decrease as the number of agents increases, a phenomenon shared across a wide range of economic models: the tragedy of commons, the game of chicken, etc. In such cases, if we break the symmetry and only allow a restricted number of agents to participate, the social welfare will increase.
At each time during the whole process, for each agent, given the information he has and the strategies of other agents, he has a belief over all uncertainty -including the randomness of the world and other agents' private information. His immediate strategy should maximize his expected utility given his current information. If a strategy profile satisfies the above property, it is called a perfect Bayesian equilibrium. 3 We say a mechanism is individually rational if every agent has non-negative expected utility in every Nash equilibrium.
Scoring rules have a very long history [5,12,16,17]. Market scoring rules were introduced by Hanson [18] to study prediction markets. A scoring rule for an outcome 𝑦 is a function 𝑆 : Δ Y × Y → R, 4 so that 𝑆 (𝑝, 𝑦) is the score assigned to a prediction 𝑝 when the true outcome realized is 𝑌 = 𝑦. Formally,
A proper scoring rule is strict if the equality holds only if 𝑏 = 𝑝. In other words, reporting one's belief results in a higher score than reporting other distributions. Such a report is said to be truthful. 3 Here is a more rigorous definition. In an extensive-form game, for each game state ℎ, let 𝜋 𝜎 (ℎ) denote its reach probability according to strategy profile 𝜎. We simply use 𝜋 (ℎ) if 𝜎 is clear from the context. For each information set 𝐼 , let 𝜋 (𝐼 ) = ℎ∈𝐼 𝜋 (ℎ). Let 𝑢 𝜎 (ℎ) denote ℎ's expected utility according to 𝜎. For each information set 𝐼 with 𝜋 (𝐼 ) > 0, let 𝑢 (𝐼 ) = E ℎ∈𝐼 [𝑢 (ℎ) ] = ℎ∈𝐼 𝑢 (ℎ)𝜋 (ℎ)/𝜋 (𝐼 ). For a strategy profile 𝜎, let 𝜎 𝐼 →𝑠 denote the same strategy profile except the strategy at information set 𝐼 is changed to 𝑠. A strategy profile 𝜎 = (𝜎 1 , . . . , 𝜎 𝑛 ) is a perfect Bayesian equilibrium if for every information set 𝐼 with 𝜋 (𝐼 ) > 0, for every strategy 𝑠 at 𝐼 , 𝑢 𝜎 (𝐼 ) ≥ 𝑢 𝜎 𝐼 →𝑠 (𝐼 ). 4 Δ Y is the set of all probability distributions over Y.
Prediction markets with a scoring rule proceed as follows: A public belief 𝑝 ∈ Δ Y is maintained in the market. Initially, 𝑝 = 𝑝 0 . Agents can change the market belief arbitrarily, resulting in a belief sequence 𝑝 0 , 𝑝 1 , 𝑝 2 , . . . . After the outcome is revealed, for every 𝑘 ≥ 1, the agent who changes 𝑝 𝑘-1 to 𝑝 𝑘 is rewarded (or charged, if negative) by 𝑆 (𝑝 𝑘 , 𝑦) -𝑆 (𝑝 𝑘-1 , 𝑦), where 𝑆 is a proper scoring rule.
In prediction markets, if each agent is only allowed to report once (and they believe other agents are rational), then the reports will be truthful. In particular, each agent will report his posterior distribution using the market information as the prior and his private information as the evidence.
Proposition 2.3. If signals are independent conditioned on the outcome, then agents can perform a Bayesian update knowing only the current market belief (and the likelihood of their own signals). In particular, they need not know the history of updates.
In this section, we show by examples how the original form of prediction markets may perform undesirably: agents may 1) invest too much effort, which decreases the social welfare, and 2) intentionally delay their reports.
Current theories of prediction markets do not consider agents' effort to discover signals: How much effort should an agent invest? For some easy, accurate information, it would be a waste of resources if everyone invests a lot.
We model the cost of information by an access function 𝐹 : R ≥0 → [0, 1] that maps from an effort level (the cost that an agent spends) to the probability of getting signals. Each agent 𝑖 decides his effort level 𝑐 𝑖 and then obtains his signal 𝑋 𝑖 with probability 𝐹 (𝑐 𝑖 ). We assume the access function is the same for every agent as common knowledge but unknown to the principal.
Suppose agents' signals are structured as in Example 2.1 with 𝛼 = 1/2 and 𝛽 = 0, i.e., all 𝑋 𝑖 's are identical to the outcome and are exact substitutes to each other. Also, only the first agent who changes the belief will get one unit of reward, and others will get zero. In this case, every agent wants to be the first. If multiple agents get signals, we assume each of them receives the reward with equal probability since they are symmetric.
Suppose the principal's value of information is described by a proper scoring rule 𝑆. She needs to choose a proper scoring rule S for the prediction market. Unfortunately, she is unable to maximize the social welfare because she doesn't know the access function 𝐹 and the information structure Pr[𝑋 | 𝑌 ] (characterized by 𝛽 in this case). We will see in this section that, if she chooses S = 𝑆 for prediction markets, the social welfare could be very poor. This is in stark contrast to the mechanisms we propose later in this paper, where the social welfare is maximized when S = 𝑆, without the need to know anything about 𝐹 or Pr[𝑋 | 𝑌 ]. Our results are summarized in Figure 1.
We consider two examples of access functions and compute the social welfare of the market as the number of agents increases. When every agent's effort is 𝑐, social welfare is the total value minus with 𝑐 ≥ 0. In both (linear and exponential) cases, the total costs (right column) are high in the strategic setting. In the linear case, agents spend all potential social value and have zero social welfare. In the exponential case, the total cost increases as the number of agents increases.
cost. The value is 1 when at least one agent derives his signal, and the total cost is 𝑐𝑛, so in expectation,
Proposition 3.1 (Linear Access). Given 𝑛 ≥ 2, 𝜆 > 1 and a linear access function is 𝐹 (𝑐) = 𝜆𝑐 for 𝑐 ∈ [0, 1/𝜆], the optimal social welfare with 𝑛 agents is 𝑊 (𝑛) (𝑐 opt ) = 1 -𝜆 -𝑛/(𝑛-1) -𝑛 𝜆 -1 -𝜆 -𝑛/(𝑛-1) > 0 in the centralized setting, but the social welfare 𝑊 (𝑛) (𝑐 self ) is zero in the strategic setting. Proposition 3.2 (Exponential Access). Given 𝑛 ≥ 2, 𝜆 > 1 and an exponential access function 𝐹 (𝑐) = 1 -𝑒 -𝜆𝑐 for 𝑐 ≥ 0. As 𝑛 → ∞, the optimal social welfare with 𝑛 agents is 𝑊 (𝑛) (𝑐 opt ) = 1 -(1 + ln 𝜆)/𝜆 > 0, but the social welfare in the strategic setting is
Unfortunately, prediction markets do not guarantee timely reports, i.e., one may wait for others to report. This is undesirable when the value of information decays quickly. Suppose agents' signals are structured as in Example 2.1 with 𝛼 = 0.02, 𝛽 = 0.2. Consider the quadratic scoring rule, where we let 𝐺 (𝑝) = ∥𝑝 ∥ 2 2 and 𝑆 (𝑝, 𝑦) = 𝐺 (𝑝) + ∇𝐺 (𝑝), 𝛿 𝑦 -𝑝 = 2𝑝 (𝑦) -∥𝑝 ∥ 2 2 . Contrary to the intuition, the marginal value of a report does not monotonically decrease. As shown in Figure 2, the largest increase in the scoring rule is due to the third report, not the first or the second. Thus, an agent who believes he is likely to be the first will wait before reporting.
We want to design new mechanisms to deal with the above issues. In particular, we assume the market belief is used by someone whose utility is the "quality" of the market belief minus the rewards she gives to the agents. Then, we maximize social welfare and encourage truthful and timely reports. We first ignore the time factor and consider a simple case, where each agent 𝑖:
(1) chooses to invest 𝑐 𝑖 ∈ R much effort, (2) gets a signal 𝑋 𝑖 with probability 𝐹 (𝑐 𝑖 ), and reports 𝑏 𝑖 to the mechanism, (3) receives some reward 𝑟 𝑖 from the mechanism. We want to design a reward function (contract) from agents' reports to rewards in order to maximize the social welfare. If 𝑝 is the aggregated belief from agents' reports, the value of information is represented as a (strictly) proper scoring rule 𝑆 (𝑝, 𝑦), where 𝑦 is the outcome. The principal's utility 𝑈 , each agent 𝑖's utility 𝑢 𝑖 , and the social welfare 𝑊 , are given by: 𝑈
Here the expectation is taken over all randomness (ex-ante), i.e., agents compute it based on the information in Stage 1. Note that given the information valuation 𝑆 and the information structure, assuming agents are truthful, the ex-ante social welfare only depends on the agents' effort 𝒄 = (𝑐 1 , . . . , 𝑐 𝑛 ). We call 𝒄 * an optimal effort profile if
where 𝑝 is the Bayesian posterior of the outcome given all signals.
To incentivize agents to invest the optimal effort, we want to design a mechanism that, given agents' reports, outputs an aggregated belief 𝑝 ∈ Δ Y and a reward for each agent. This task is challenging for two reasons: A report is said to be truthful if it results in a Bayesian update on the market belief, where the prior is the previous market belief, the posterior is the new market belief, and the evidence is the reporter's signal. We pay each agent by his improvement on the market belief as if he were the last one to update. This mechanism is "fair" in the sense that if everyone is truthful then everyone receives the same expected reward. Note that if 𝑝 𝑘,𝑦 is known for |Y| -1 different 𝑦's, then the last one follows directly since their sum is 1, so each agent needs to report only |Y| -1 values, the same number as in the original prediction market, where each agent reports a probability distribution. d𝑐 2 < 0. 5 Mechanism 1 is individually rational, and there exists a strict perfect Bayesian equilibrium 𝝈 in which the expected social welfare is maximized (over all symmetric strategy profiles), and 𝝈 satisfies the following properties:
Effort Optimality The effort profile 𝒄 is optimal (as in (2)).
Truthfulness Each agent makes a Bayesian update on the market belief.
In order to proof Theorem 4.2, we first show some lemmas.
Every report 𝑏 𝑘 will be truthful, assuming other reports are truthful. Any deviation will result in a strictly worse expected reward. Proof of Theorem 4.2. Each agent 𝑖 makes two decisions, and his strategy can be written as 𝜎 𝑖 = (𝑐 𝑖 , 𝑏 𝑖 ), where 𝑐 𝑖 is the effort he invests at the beginning and 𝑏 𝑖 is his report. By Lemma 4.4, he will not deviate from 𝑐 𝑖 . By Lemma 4.3, he will not deviate from 𝑏 𝑖 .
The proof for individual rationality is simple: If in a Nash equilibrium, agent 𝑖 gets negative expected utility, then he can deviate to 𝑐 𝑖 = 0 and get zero utility. This means he is not in a Nash equilibrium. Thus in every Nash equilibrium, every agent has non-negative expected utility. □
Below is the proofs of the lemmas. Lemma 4.4 is perhaps the most interesting among the three. The expected social welfare is given by:
Setting the derivative to be zero, we have
5 decreasing marginal benefit, a very common assumption in economics.
-
On the other hand, the expected utility of agent 𝑖 is
where 𝑐 is the amount of effort invested by other agents. Because 𝐹 (𝑐 𝑖 ) is concave in 𝑐 𝑖 , 𝑢 𝑖 is also concave in 𝑐 𝑖 . We also know that 𝐹 (𝑐 𝑖 ) is upper bounded (by 1), so lim 𝑐 𝑖 →∞ d𝐹 (𝑐 𝑖 )/d𝑐 𝑖 = 0 and thus lim 𝑐 𝑖 →∞ d𝑢 𝑖 /d𝑐 𝑖 = -1. Therefore, there is a unique 𝑐 𝑖 that maximizes the utility, which is either (a) 𝑐 𝑖 = 0 or (b) the point with zero derivative. In case (b), we have
(5) Equation ( 5) describes how an agent's decision 𝑐 𝑖 should best response to those of others 𝑐. In a symmetric equilibrium, 𝑐 𝑖 = 𝑐. Then, surprisingly, Equation (5) becomes equivalent to Equation (4). In case (a), both individually optimal and socially optimal solutions are 𝑐 𝑖 = 0. In other words, the distributed maximization of each agent's utility can result in the maximization of social welfare. □ Proof of Lemma 4.5. Since signals are identically distributed and the effort function is the same for every agent, an agent is indistinguishable from another. The lemma simply follows. □
In this section, we consider a setting that involves time. Its difference from the setting of the previous section is that signals are not received by agents immediately but will be eventually. Formally, before receiving signal 𝑋 𝑖 , each agent 𝑖 suffers from a latency 𝑇 𝑖 , which is a random variable with c.d.f. 𝐹 𝑐 (𝑡). For instance, 𝐹 𝑐 (𝑡) = 1 -𝑒 -𝜆𝑐𝑡 means 𝑇 𝑖 ∼ Exp(𝜆𝑐 𝑖 ). Here, 𝐹 𝑐 (𝑡) -a generalization of the access function 𝐹 (𝑐) used in the previous section -depends on time. In summary, each agent 𝑖 ∈ N :
(1) chooses to invest 𝑐 𝑖 ∈ R effort, (2) obtains a signal 𝑋 𝑖 at time 𝑇 𝑖 ≥ 0 generated from c.d.f 𝐹 𝑐 𝑖 (•), decides a time 𝑠 𝑖 ≥ 0 and a report 𝑏 𝑖 to send to the mechanism at time 𝑠 𝑖 , (3) receives some reward 𝑟 𝑖 from the mechanism.
We assume that as long as the agents invest non-zero effort, they always obtain their signals before the true outcome being revealed because this is far in the future. The value of the information (market belief) evolves over time. Let 𝑝 (𝑡) ∈ Δ Y denote the market belief at time 𝑡. The value of a belief history {𝑝 (𝑡)} 𝑡 >0 is defined as: 𝑉 = ∫ 𝑡 >0 𝑆 (𝑝 (𝑡), 𝑦)ℎ(𝑡)d𝑡, where 𝑦 is the outcome, 𝑆 is a strictly proper scoring rule characterizing the quality of the market belief, and time value function ℎ is a function characterizing how the value of information diminishes through time. For instance, ℎ(𝑡) = 𝜂𝑒 -𝜂𝑡 means that the value of information decays exponentially. This would be appropriate if the principal needs to make decision at a random time 𝜏 ≥ 0 generated from an exponential distribution with parameter 𝜂.
We want to design a mechanism that takes agents' online reports as inputs, maintains a real-time market belief, and finally outputs the reward given to each agent. We also want this mechanism to be truthful, timely, and social-welfare-maximizing. We say a mechanism is timely if every agent reports immediately after he gets a signal. The principal's utility 𝑈 , each agent 𝑖's utility 𝑢 𝑖 , and the social welfare 𝑊 , are given by: 𝑈
Given proper scoring rule 𝑆 and the information structure, assuming the agents aggregate their information in a truthful and timely manner, the expected social welfare only depends on the agents' effort 𝒄 = (𝑐 1 , . . . , 𝑐 𝑛 ). In this section, we call 𝒄 * an optimal effort profile if
Besides the challenges involved in Section 4 -including the hidden effort, the unknown information structure and effort function, and the potential manipulation of agents' reports -we also need to deal with another complexity: An agent can choose any time to report, not necessarily just at the time he receives his signal, and even before it (i.e., 𝑠 𝑖 < 𝑡 𝑖 ). We restrict our focus to mechanisms where each agent can report only once. Note that this assumption exists in the previous literature, e.g., in the traditional prediction market, there would be no truthfulness guarantee without this assumption. For this sequential setting, we propose Mechanism 2, which updates a market belief using agents' reports one by one. Agents report their information in the same structure as in Section 4.
The mechanism also computes counterfactual market beliefs with one of the reports skipped. In particular, the counterfactual belief for agent 𝑖's absence is what the market belief would be if agent 𝑖 does not report. The reward for each agent depends on both the actual and counterfactual market beliefs.
Theorem 5.1. Assume ℎ(𝑡) > 0 for all 𝑡 > 0,
< 0, 6 and 𝐹 𝑐 (𝑡) is the c.d.f. of a non-negative random variable for 𝑐 ≥ 0. Mechanism 2 is individually rational, and there exists a strict perfect Bayesian equilibrium that is socially optimal (over all symmetric strategy profiles) and satisfies the following properties:
Effort Optimality Every agent invests the "right" amount of effort as (6). Truthfulness Each agent makes a Bayesian update on the market belief. Timeliness For all 𝑖 ∈ N , 𝑠 𝑖 = 𝑡 𝑖 .
Our core idea is to pay each agent by the actual value of information minus the counterfactual value of information as if he had not updated the market belief. Let Ṽ 𝑖 be the counterfactual value w.r.t. agent 𝑖. The reward (in Line 19 of Mechanism 2) is given by
where p𝑖 (𝑡) is what the market belief would be at time 𝑡 if agent 𝑖 had not changed anything in the market. Figure 3 gives an intuition for E 𝑉 -Ṽ 𝑖 . Note that we are not talking about a counterfactual value for the case as if an agent had not participated the game. The number of agents is still 𝑛, and other agents do the same. Lemma 5.2 (Effort Optimality). Agents are incentivized to invest the "right" amount of effort that maximizes the expected social welfare, assuming all updates are timely and truthful. Lemma 5.4 (Timeliness). Every agent is incentivized to update the market belief as soon as he gets his signal, assuming all updates are truthful.
Proof of Theorem 5.1. Each agent 𝑖 decides how much effort to make at the beginning. By Lemma 5.2, he will not deviate at this decision. Then, at each time, he decides whether to report and if so, what to report. By Lemma 5.4, he will report if he has a signal. By Lemma 5.3, he will report truthfully. □
The proofs of the lemmas are similar to those in Section 4 and are postponed to the supplementary materials.
There are both similarities and differences between our mechanisms and the VCG mechanism. They are similar because both of them have a payoff function that can be interpreted as an actual term minus a counterfactual term. Also, in our mechanisms, the utility function of an agent is -to some extent -aligned with the social welfare as a function of his action, as in VCG.
However, a straightforward application of VCG fails. In VCG, we need to compute the utility of each agent, which is impossible here, because the amount of effort each agent invests is never revealed. In our mechanisms, the alignment of the agent's utility and social welfare is achieved implicitly without the principal computing them. In addition, VCG deals with a single-stage game, while our mechanisms deal with multi-stage games. This is to say that the signals must be discovered before they can be (truthfully) revealed. Finally, VCG guarantees the DSIC (dominant-strategy incentivecompatible) property, which is not the case in our setting, where agents respond to others when choosing the effort level.
The equilibrium depends on a variety of parameters. In this section, we analyze how it is affected by ease, noise, and substitutability of the information. We compare our socially optimal mechanism (Mechanism 2) with the traditional prediction market. 7 We assume the value of information decays exponentially: ℎ(𝑡) = 𝜂𝑒 -𝜂𝑡 with parameter 𝜂 = 1. The latency of signal discovery is also exponentially distributed: 𝐹 𝑐 (𝑡) = 1-𝑒 -𝜆𝑐𝑡 . Here, 𝜆 can be viewed as the ease of collecting the information, as the larger 𝜆 is, the shorter latency the agent suffers. There are 𝑛 = 2 agents unless otherwise stated.
Let 𝑣 1 = 2 and 𝑣 2 = 3, defined above. In our mechanism, the amount of effort in equilibrium automatically adapts to the ease of collecting information, even though the mechanism does not know anything about the parameters! Figure 4 is a visualization. In prediction markets, agents invest too much for very easy (𝜆 → ∞) information, thus making the updates unnecessarily quick. For information that takes a long time to discover, agents still invest equally much effort in prediction markets, while in our mechanism, they do not invest anything because we have the 𝜂𝑒 -𝜂𝑡 term in the value of information -the information value decays so quickly that the gain in information value is overwhelmed by the amount of effort invested.
Consider the scenario described in Section 3.2, with 𝛼 = 0.1. Recall that 𝛽 = Pr[𝑋 ≠ 𝑌 ] is the probability each signal differs from the true outcome. It can also be regarded as the noise of information. It turns out that in prediction markets, agents invest too much not only for very easy information but also for very accurate (𝛽 → 0) information, as shown in Figure 5. When the signals become weak enough, agents no longer invest anything in either prediction markets (because a late reporting is encouraged) or our mechanism (because the gain in value is too little).
Recall that 𝑣 𝑘 is the expected increase of the score due to the first 𝑘 updates. We fix 𝑣 2 = 2, and see what happens when 𝑣 1 changes.
Here, 𝑣 1 /𝑣 2 can be considered as the substitutability of information.
7 Following Section 3.1, we study the case where S = 𝑆. As shown in Figure 6, in prediction markets, when value is more concentrated in the first report (higher substitutability), agents invest more effort to get a signal quickly. Surprisingly, this is not always the case in our mechanism. When signals are very easy (quick to obtain), agents tend to invest less when value is more concentrated in the first signal. This is because even though the first report brings high value, after the second report, the marginal value of the first report (against other signals) becomes much less. Moreover, the easier to obtain a signal, the stronger this effect.
As we argue that agents invest too much effort for easy and accurate information in the traditional prediction market, one may wonder how bad the effect of such behavior could be on social welfare. We find that the social welfare approaches to 0 as the number of agents grows large, while in our proposed mechanism, both social welfare and the principal's utility are high, as shown in Figure 7.
In this example, we assume 𝑣 0 = 0 and 𝑣 𝑘 = 1 for each 𝑘 ≥ 1 (or equivalently, 𝛽 = 0). This is similar to what we show in Section 3.1.
Throughout the paper, we use 'she' and 'he' for the principal and agents respectively.
In reality, it could be other people who value the information in the market, use it to do something outside the market, and then get utility based on the quality of the information. Without loss of generality, we simply aggregate all such utility into that of the principal.[11,16]
decreasing marginal benefit