# an_equivalence_between_wagering_and_fairdivision_mechanisms__212559cd.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

An Equivalence between Wagering and Fair-Division Mechanisms

Rupert Freeman Microsoft Research rupert.freeman@microsoft.com

David M. Pennock Microsoft Research dpennock@microsoft.com

Jennifer Wortman Vaughan Microsoft Research jenn@microsoft.com

We draw a surprising and direct mathematical equivalence between the class of allocation mechanisms for divisible goods studied in the context of fair division and the class of weakly budget-balanced wagering mechanisms designed for eliciting probabilities. The equivalence rests on the intuition that wagering is an allocation of ﬁnancial securities among bettors, with a bettor s value for each security proportional to her belief about the likelihood of a future event. The equivalence leads to theoretical advances and new practical approaches for both fair division and wagering. Known wagering mechanisms based on proper scoring rules yield fair allocation mechanisms with desirable properties, including the ﬁrst strictly incentive compatible fair-division mechanism. At the same time, allocation mechanisms make for novel wagering rules, including one that requires only ordinal uncertainty judgments and one that outperforms existing rules in a range of simulations.

1 Introduction

Consider the following two scenarios. In the ﬁrst, an information-seeking principal would like to elicit credible probabilistic forecasts from a group of agents. She does so by collecting wagers from the agents along with their predictions, and redistributing these wagers in such a way that agents with more accurate predictions are more highly rewarded, potentially keeping a cut for herself. In the second, a neutral mediator needs to allocate a set of divisible goods or resources, such as plots of land or compute cycles, to a group of agents who all have different preferences over the goods and potentially different entitlements. His top priority is ensuring that each agent walks away with her fair share. On the surface, these scenarios appear quite distinct. Central to wagering is the idea of money changing hands, with each agent s rewards contingent on an uncertain future state of the world. In contrast, the fair division of goods or resources typically involves no exchange of money and no inherent uncertainty. Despite these apparent differences, we show that these scenarios are two sides of the same coin. In particular, we show that there is a one-to-one correspondence between the

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

class of weakly budget-balanced wagering mechanisms those for which the principal is guaranteed no loss and the class of allocation mechanisms for divisible goods under additive valuations. Furthermore, we show that commonly studied properties of wagering mechanisms correspond precisely to commonly studied properties of fair division. Individual rationality, which ensures that risk-neutral agents beneﬁt in expectation from participation in a wagering mechanism, corresponds to the notion of proportionality in fair division, which, loosely speaking, guarantees each agent at least a minimal share of allocated goods. And properties common to the literature in both settings, including incentive compatibility and Pareto optimality, carry over immediately, with minor caveats. This correspondence has implications for both fair division and wagering. For example, weighted score wagering mechanisms (Lambert et al. 2008; 2015), which build on the machinery of proper scoring rules (Gneiting and Raftery 2007), can be imported into the fair division setting to yield allocation mechanisms that are proportional, envyfree, and strictly incentive compatible to the best of our knowledge, the ﬁrst strictly incentive compatible allocation mechanisms. On the ﬂip side, the strong demand matching allocation mechanism (Cole, Gkatzelis, and Goel 2013) can be imported into the wagering setting to produce a mechanism that, in our simulations, outperforms standard wagering mechanisms in terms of amount of trade facilitated and agent utility. As another example, since the constrained serial dictatorship (Aziz and Ye 2014) allocation mechanism requires only ordinal agent preferences, the correspondence yields the ﬁrst wagering mechanism that allows agents to report ordinal beliefs. The correspondence we show builds on an earlier observation that the output of a wagering mechanism can be interpreted as a sale of Arrow-Debreu securities to bettors (Freeman, Pennock, and Vaughan 2017). Once all wagers have been collected, a wagering mechanism can be viewed as allocating a ﬁxed number of securities of different types among the bettors (possibly with some leftover for the principal), with a bettor s value for each security proportional to her belief about the likelihood of a future event. Under this interpretation, it is natural to consider the use of an allocation mechanism to allocate the securities. Perhaps more surprisingly, our correspondence shows that the class of weakly

budget-balanced wagering mechanisms is general enough to capture the entire space of allocation mechanisms for divisible goods under additive valuations, so any wagering mechanism can be used for allocation of general goods with no exchange of money.

2 Preliminaries and Background

To set the stage for our main results, we begin with a review of the formal models of both fair division and wagering, and deﬁne the properties most commonly sought out in allocation and wagering mechanisms. Throughout the paper, we use the notation [n] to denote the set {1, . . . , n} and the notation x i to denote all components of the vector x except the ith.

2.1 Fair Division

The study of fair division dates back to the 1940s (Steinhaus 1948) and many variants of the problem have been examined. In this paper, we focus on the problem of allocating divisible goods to agents with additive values, a special case of the cake-cutting problem (Robertson and Webb 1998; Procaccia 2013). Formally, consider a set of n agents indexed {1, . . . , n} and a set of m divisible goods indexed {1, . . . , m}. Each agent i has a private set of values vi,j 0 for each good j. As is standard in the cake-cutting literature, we assume that values are normalized so that Pm j=1 vi,j = 1. Let z denote a bundle of goods, with each component zj [0, 1] specifying a fractional piece of good j. Agent i s value for z is then vi(z) = Pm j=1 vi,jzj. Each agent also has a ﬁxed weight ei > 0, capturing the agent s entitlement or priority. Let E = Pn i=1 ei. An allocation consists of a bundle of goods ai assigned to each agent i. It is permitted to allocate goods incompletely, resulting in waste. A feasible allocation is therefore any allocation for which Pn i=1 ai,j 1 for all j, and ai,j 0 for all i and j. An allocation mechanism A takes as input a vector of reported values ˆvi and weights ei for each agent i and outputs a feasible allocation. We use Ai,j(ˆv, e) to denote the fraction of good j allocated to agent i by the allocation mechanism A with input ˆv and e, and Ai(ˆv, e) for i s full allocation. We note that some of the allocation mechanisms we discuss are either ill-deﬁned or lose some of their fairness properties when weights are unequal. As long as weights are rational, these mechanisms can be extended to the weighted setting by creating multiple copies of each agent i such that the number of copies of i is proportional to ei without sacriﬁcing any of the properties described below (Brams and Taylor 1996, page 152). However, this method can result in an exponential increase in time and space requirements, making some unweighted mechanisms infeasible to run in the weighted setting. Several notions of fairness have been proposed in the fair division literature. Proportionality (Steinhaus 1948) requires that each agent get an ei/E share of her total (reported) value for the set of all goods.

Deﬁnition 1. An allocation mechanism A is proportional if, for all ˆv and e, and for all i [n], ˆvi(Ai(ˆv, e)) ei/E.

Envy-freeness (Foley 1967) requires that no agent can ever prefer another agent s allocation to her own, after accounting for differences in weights.

Deﬁnition 2. An allocation mechanism A is envy-free if, for all ˆv and e, and for all i, i [n], (1/ei)ˆvi(Ai(ˆv, e)) (1/ei )ˆvi(Ai (ˆv, e)).

Note that a trivial envy-free and proportional allocation always exists; simply allocate each agent i an ei/E fraction of each good. Pareto optimality is a basic notion of economic efﬁciency. It says that a mechanism should not output allocations for which it is possible to make some agent better off without making any other agent worse off.

Deﬁnition 3. An allocation mechanism A is Pareto optimal if for all ˆv and e, and all alternative allocations {a 1, . . . , a n}, if ˆvi(a i) > ˆvi(Ai(ˆv, e)) for some i, there exists a j with ˆvj(a j) < ˆvj(Aj(ˆv, e)).

Finally, we might desire mechanisms that do not incentivize agents to misreport their (private) values.

Deﬁnition 4. An allocation mechanism A is weakly incentive compatible if, for every agent i with values vi, and all reports ˆv and weights e, vi(Ai((vi, ˆv i), e)) vi(Ai(ˆv, e)). A is strictly incentive compatible if this inequality is strict whenever vi = ˆvi.

In fair division, fairness is typically emphasized over incentive compatibility, and weak incentive compatibility (or equivalently, dominant strategy truthfulness) is often considered sufﬁcient (e.g., Cole, Gkatzelis, and Goel 2013).

2.2 Wagering While the study of wagering mechanisms also has a long history (Eisenberg and Gale 1959), the model we study here was formalized by Lambert et al. (2008), building on ideas from Kilgour and Gerchak (2004). Consider a random variable X that takes a value in {1, . . . , m}. There is a set of n agents (or bettors) indexed {1, . . . , n}. Each agent i has private, subjective, immutable beliefs pi, where pi,j is the probability i assigns to the event X = j, and a budget or wager wi > 0, the maximum amount of money i is prepared to lose. A wagering mechanism Π is used to elicit beliefs from the agents. Each agent reports beliefs ˆpi along with her wager wi. The wagering mechanism deﬁnes a net payoff Πi(ˆp, w, x) to each agent that depends on the full set of agent reports ˆp, the vector w of agent wagers, and x, the observed value of X. To be a valid wagering mechanism, it must be the case that no agent loses more than her wager (i.e., Πi(ˆp, w, x) wi for all ˆp, w, and x). Let W = Pn i=1 wi. In prior work, we observed that the output of a wagering mechanism can be interpreted as an allocation of securities with payoffs that depend on the realization of X (Freeman, Pennock, and Vaughan 2017). For any j [m], we deﬁne a type-j security to be a contract that pays off $1 in the event

that X = j and $0 otherwise. If i is risk neutral, she should be willing to buy a type-j security at any price up to pi,j. To deﬁne the output of a wagering mechanism in terms of securities, we can think of each agent i paying a price of wi up front in exchange for bi,j securities of each type j, where bi,j = wi + Πi(ˆp, w, j) 0. In the event that X = j, agent i receives net payoff bi,j wi = Πi(ˆp, w, j). Therefore, the output of a wagering mechanism can be completely speciﬁed by an allocation of securities to agents. We take this interpretation of wagering mechanisms throughout the remainder of the paper. To emphasize the distinction, we talk about wagering mechanisms B, letting Bi,j(ˆp, w) denote the number of type-j securities allocated to agent i by the mechanism B on input ˆp and w. We note that this interpretation differs slightly from the one used in Freeman, Pennock, and Vaughan (2017), in which complete sets of securities were transformed into cash and bettors payments were explicitly calculated. The two interpretations are mathematically equivalent, but the one used here makes the correspondence with fair division more direct by removing any need to reason about payments. Lambert et al. (2008) introduced a set of properties desirable for wagering mechanisms, which we translate into our security-based notation here. Individual rationality says that, under the assumption that agents are risk neutral and have immutable beliefs, agents don t lose money in expectation and therefore would willingly participate in the mechanism.

Deﬁnition 5. A wagering mechanism B is individually rational if, for any agent i with beliefs pi, there exists a report ˆpi such that for all ˆp i and w, Pm j=1 pi,j Bi,j(ˆp, w) wi.

Strict budget balance guarantees that the principal never makes or loses money. Weak budget balance allows the principal to proﬁt, but never record a loss.

Deﬁnition 6. A wagering mechanism B is weakly budget balanced if, for all ˆp and w, and for all j [m], Pn i=1 Bi,j(ˆp, w) W. A wagering mechanism is strictly budget balanced if the inequality holds with equality for every j [m].

Incentive compatibility says that agents should have incentive to truthfully report their beliefs.

Deﬁnition 7. A wagering mechanism B is weakly incentive compatible if, for every agent i with beliefs pi, and all reports ˆp and wagers w, Pm j=1 pi,j Bi,j((pi, ˆp i), w) Pm j=1 pi,j Bi,j(ˆp, w). A wagering mechanism is strictly incentive compatible if the inequality is strict whenever pi = ˆpi.

Efﬁciency is also a concern for wagering mechanisms. A speciﬁc notion of Pareto optimality, which we term side-bet Pareto optimality to distinguish it from the corresponding fair division notion, was deﬁned in Freeman, Pennock, and Vaughan (2017). It says that the wagering mechanism should facilitate all available trade. To formally deﬁne this, we ﬁrst need the notion of a proﬁtable side bet.

Deﬁnition 8. Given reports ˆp and allocations bi,j of type-j securities to each agent i, we say that b is a proﬁtable side bet if the following conditions hold:

1. For all j [m], Pn i=1 bi,j = 0. 2. For all i [n], minj [m](bi,j + bi,j) 0. 3. For all i [n], Pm j=1 ˆpi,j bi,j 0, with strict inequality for at least one i.

Deﬁnition 9. A wagering mechanism B is side-bet Pareto optimal if, for all reports ˆp and wagers w, the allocation B(ˆp, w) does not permit a proﬁtable side bet.

Finally, we note that envy-freeness has been deﬁned in the context of wagering (Freeman and Pennock 2018), but in such a way that an agent i by deﬁnition cannot envy another agent j if j s maximum loss is greater than i s wager. While this deﬁnition makes sense for wagering, it does not lend itself to a natural interpretation for allocation.

3 The Correspondence In this section, we show that there is a one-to-one correspondence between weakly budget-balanced wagering mechanisms and allocation mechanisms for divisible goods. This correspondence builds on the intuition that the output of a wagering mechanism is a division of m goods among the agents, where each good represents a security that pays off W = Pn i=1 wi if a particular outcome occurs. A bettor s value for the type-j security is proportional to her estimate of the probability that event j will occur, and wagers can be viewed as analogs of the priority weights used for allocations.

Deﬁnition 10 (Corresponding mechanisms). We say that an allocation mechanism A and wagering mechanism B are corresponding mechanisms if for all ˆp, w, i [n], and j [m], Bi,j(ˆp, w) = WAi,j(ˆp, w),

or equivalently, if for all ˆv, e, i [n], and j [m],

Ai,j(ˆv, e) = Bi,j(ˆv, e)

If A is a valid allocation mechanism, then its corresponding wagering mechanism satisﬁes Bi,j(ˆp, w) 0 and for all ˆp, w, and j [m],

i=1 Bi,j(ˆp, w) =

i=1 WAi,j(ˆp, w) W.

It is therefore a well-deﬁned, weakly budget-balanced wagering mechanism. Similarly, if B is a valid weakly budget-balanced wagering mechanism, then the corresponding allocation mechanism is valid since it satisﬁes Ai,j(ˆv, e) 0 and for all ˆv, e, and j [m],

i=1 Ai,j(ˆv, e) =

Bi,j(ˆv, e)

This correspondence highlights the parallels between properties traditionally studied in the context of wagering and properties more often studied in the context of fair division, as we explore next.

3.1 Corresponding Properties We ﬁrst show an equivalence between incentive compatibility in both settings. A misreport that produces a more preferred allocation of goods also produces a more preferred allocation of securities. All omitted proofs are included in the full version of the paper.1

Theorem 1. A random assignment mechanism A is (weakly, strictly) incentive compatible if and only if the corresponding wagering mechanism B is (weakly, strictly) incentive compatible.

We next show an equivalence between individual rationality and proportionality. Though it is not typically described this way, the equivalence highlights that individual rationality can be viewed as guaranteeing an agent her fair share of the collected wagers. The restriction to incentive compatible mechanisms stems from a minor difference between the most common variants of the deﬁnitions in the two settings: proportionality is deﬁned with respect to reported values, whereas individual rationality is deﬁned with respect to true (not reported) beliefs.

Theorem 2. A (weakly) incentive compatible random assignment mechanism A is proportional if and only if the corresponding (weakly) incentive compatible wagering mechanism B is individually rational.

Pareto optimality in the wagering setting what we term side-bet Pareto optimality does not always imply Pareto optimality in the fair division setting. This is because sidebet Pareto optimality does not require the principal to allocate the maximum number of securities possible. The principal may instead keep a proﬁt for himself. In the fair division setting, this maps to a wasteful allocation that leaves some (fractional) goods unallocated, which is not permitted under Pareto optimality. To obtain the same guarantee in the wagering setting, we must require the mechanism to be strictly budget-balanced, precluding any proﬁt for the principal.

Theorem 3. A random assignment mechanism A is Pareto optimal if and only if the corresponding wagering mechanism B is both side-bet Pareto optimal and strictly budget balanced.

4 A Comparison of Mechanisms The correspondence described in the previous section implies that any wagering mechanism can be viewed as an allocation mechanism and vice versa. In this section, we explore several immediate implications of this equivalence. In particular, we describe a variety of mechanisms that have been proposed in each setting and examine their potential in the other. Table 1 summarizes the properties of these mechanisms. We start by pointing out a pair of equivalent mechanisms that have been explored in both settings.

Market Equilibrium (ME). In the context of allocation, the market equilibrium solution endows each agent i with ei units of currency and simulates a competitive equilibrium

1The full version is available on the authors websites.

in which each good has a price and all agents spend their entire budget on goods that maximize their utility:price ratio (Walras 2013). In the wagering context, this is equivalent to the parimutuel consensus mechanism of Eisenberg and Gale (1959). In the allocation setting, the market equilibrium solution is envy-free, proportional, and Pareto optimal, but not incentive compatible. In the wagering setting, the parimutuel consensus mechanism is individually rational, strictly budget balanced, and side-bet Pareto optimal, but of course still fails to be incentive compatible.

4.1 Wagering Mechanisms We next explore the implications of exporting existing wagering mechanisms into the fair division setting.

Weighted Score Wagering Mechanisms (WSWM). The class of weighted score wagering mechanisms (Lambert et al. 2008; 2015), are built on proper scoring rules, payment functions that elicit truthful predictions from individual agents (Savage 1971; Gneiting and Raftery 2007). A scoring rule s maps a prediction p [0, 1]m and an outcome j [m] to a score in R { }. We say s is proper if for all p, q [0, 1]m, Pm j=1 pjs(p, j) Pm j=1 pjs(q, j), and strictly proper if this inequality is strict for p = q. Fixing any strictly proper scoring rule s bounded in [0, 1], the net payoff of a weighted score wagering mechanism is deﬁned as

Πi(ˆp, w, j) = wi

s(ˆpi, j) Pn i =1 s(ˆpi , j)wi

Weighted score wagering mechanisms are individually rational, strictly incentive compatible, and strictly budget balanced, but not side-bet Pareto optimal. Theorem 4. An allocation mechanism corresponding to a weighted score wagering mechanism is proportional, strictly incentive compatible, and envy-free, but not Pareto optimal. Proportionality, strict incentive compatibility, and the absence of Pareto optimality follow from the correspondence. Envy-freeness holds because each agent s expected utility is an afﬁne transformation of her expected score according to s (and each agent s score undergoes the same transformation). By properness of s, every agent believes her own score to be highest in expectation, so does not envy any other agent s allocation. To our knowledge, allocation mechanisms in this class are the ﬁrst strictly incentive compatible allocation mechanisms, and the ﬁrst non-trivial allocation mechanisms that are proportional, incentive compatible, and envy-free.

No-Arbitrage Wagering Mechanisms (NAWM). Noarbitrage wagering mechanisms (Chen et al. 2014) are deﬁned as follows. Let s be a strictly proper scoring rule bounded in [0, 1], and let p : [0, 1]m (n 1) Rn 1 [0, 1]m be a function that maps reports and wagers of n 1 agents to an average prediction. A no-arbitrage wagering mechanism deﬁnes net payoffs

Πi(ˆp, w, j) = wi W i

W [s(ˆpi, j) s( p(ˆp i, w i), j)].

Allocation Both Wagering

Envy-Free Pareto Opt.

Proportional/ Ind. Rational

Incentive Compatible

General e / w

Budget Balanced

Side-bet Pareto Opt. ME Yes Yes Yes No Yes Yes Strict Yes WSWM Yes No Yes Strict Yes Yes Strict No NAWM No No Yes Strict Yes Yes Weak No DCA Eq. weights No Yes Weak No Yes Weak No CSD No No Yes Weak Yes No Strict No PA Eq. weights No No Weak Yes Yes Weak Yes SDM Yes No No Weak Yes No Weak Yes

Table 1: Comparison of properties satisﬁed by market equilibrium (ME), weighted score wagering mechanisms (WSWM), noarbitrage wagering mechanisms (NAWM), the double clinching auction (DCA), constrained serial dictatorship (CSD), partial allocation (PA), and strong demand matching (SDM).

For certain choices of p, such mechanisms are weakly budget balanced, individually rational, and strictly incentive compatible, but not side-bet Pareto optimal.

Theorem 5. An allocation mechanism corresponding to a no-arbitrage wagering mechanism is proportional and strictly incentive compatible, but not envy-free or Pareto optimal.

Again, proportionality, incentive compatibility, and lack of Pareto optimality follow immediately from the properties of the corresponding wagering mechanism. In the full version, we present an example of an instance on which envyfreeness is violated.

The Double Clinching Auction (DCA). The double clinching auction (Freeman, Pennock, and Vaughan 2017) carefully selects a number of securities to allocate and then allocates them via an adaptive clinching auction (Dobzinski, Lavi, and Nisan 2008). We refer the reader to Freeman, Pennock, and Vaughan (2017) for additional details, but note that the double clinching auction is only deﬁned for the case of m = 2. The double clinching auction is individually rational, weakly budget balanced, and weakly incentive compatible, but not side-bet Pareto optimal.

Theorem 6. The allocation mechanism corresponding to the double clinching auction is proportional and weakly incentive compatible, but not envy-free or Pareto optimal.

In the full version, we present an example on which the double clinching auction violates envy-freeness.

4.2 Allocation Mechanisms We next consider exporting existing allocation mechanisms into the wagering setting.

Constrained Serial Dictatorship (CSD). Constrained serial dictatorship (Aziz and Ye 2014) is deﬁned only for equal weights (ei = 1 for all i). Imagine ﬁxing a particular ordering of the agents, allocating to each agent in order her most preferred m/n of the remaining goods (allowing partial goods to be chosen). The output of constrained serial dictatorship is the expected allocation that would arise from this process from an ordering chosen uniformly at random.

Constrained serial dictatorship is weakly incentive compatible and proportional, but not envy-free or Pareto optimal. There is no known natural extension for unequal weights, so agent duplication must be employed.

Theorem 7. The wagering mechanism corresponding to constrained serial dictatorship is strictly budget balanced, individually rational, and weakly incentive compatible. It is not side-bet Pareto optimal.

Strict budget balance holds because the allocation mechanism always allocates goods completely. Interestingly, the constrained serial dictatorship allocation depends only on ordinal, not cardinal, preferences. Thus it yields a wagering mechanism that can be used for agents who report only ordinal beliefs (outcome j is more likely than outcome j ). Computing the constrained serial dictatorship allocation is #P-complete (Aziz, Brandt, and Brill 2013; Aziz et al. 2015), but a standard Chernoff and union bound argument shows that an arbitrary additive approximation can be found via sampling. We adopt this approach in our simulations.

Partial Allocation (PA). The partial allocation mechanism (Cole, Gkatzelis, and Goel 2013) is designed to approximate market equilibrium, providing each agent at least a 1/e fraction of the utility she would receive in the market equilibrium allocation. Each agent i is allocated some fi 1 fraction of her market equilibrium allocation, where fi is determined according to how costly agent i s presence is to the other agents. See Cole, Gkatzelis, and Goel (2013) for further details. Partial allocation is known to be weakly incentive compatible and envy-free when the weights of all agents are equal. However, it is not envy-free when weights are unequal, and it is not proportional or Pareto optimal.

Theorem 8. The wagering mechanism corresponding to the partial allocation mechanism is weakly incentive compatible, weakly budget balanced, and side-bet Pareto optimal. It is not individually rational.

Strong Demand Matching (SDM). Strong demand matching (Cole, Gkatzelis, and Goel 2013) is also designed to approximate market equilibrium. Its approximation factor is particularly good when all items are highly demanded, for

instance, when there are many more agents than goods and no good is uniformly disliked. It works by computing minimal prices at which each agent s complete demand (when she has a single unit of currency to spend) can be met by a single good. Again, we refer the reader to Cole, Gkatzelis, and Goel (2013) for further details. Strong demand matching is envy-free and weakly incentive-compatible, but not proportional or Pareto optimal. There is no known, natural way to extend the mechanism to unequal weights that retains the desirable properties, other than the agent-duplication method.

Theorem 9. The wagering mechanism corresponding to strong demand matching is weakly budget balanced, weakly incentive compatible, and side-bet Pareto optimal. It is not individually rational.

5 Simulations

We next compare the performance of these mechanisms in practice. Our test data comes from a binary outcome (m = 2) wagering setting, but the equivalence allows us to make observations about allocation-speciﬁc properties like envyfreeness too. In the full version of the paper, we additionally report results from simulations with larger outcome spaces using synthetic data. We restrict attention to incentive compatible mechanisms, excluding market equilibrium. We use reports gathered from an online prediction contest called Probability Sports (Galebach 2017). 2 The dataset consists of probabilistic predictions about the outcomes of 1643 U.S. National Football League matches between 2000 and 2004. For each match, between 64 and 1574 people reported their subjective probability of the home team winning the game and earned points according to a Brier scoring rule. Probability Sports participants did not submit wagers. For our simulations, we follow previous work (Freeman, Pennock, and Vaughan 2017) and generate wagers in two ways. First, we consider uniform wagers, modeling the scenario in which agents are required to risk the same amount. Second, for smaller instances on which it is tractable to employ the agent duplication method for unequal weights, we generate wagers according to a Pareto distribution with shape parameter 1.16 and scale parameter 1. Since agent duplication requires rational wagers, we scale the generated wagers to lie in [0, 50], and then take the ceiling of each, yielding integral wagers between 1 and 50. Table 2 summarizes the results of our ﬁrst simulation, in which the mechanisms were run on the complete Probability Sports dataset with uniform wagers. Weighted score and no-arbitrage wagering mechanisms utilized the Brier score (Brier 1950). We report four statistics, all averaged over the 1643 matches considered. Value ratio is the sum over all agents of the expected value of their allocated securities (with respect to their own subjective beliefs) normalized by the total amount wagered, or 1 W Pn i=1 Pm j=1 ˆpi,j Bi,j(ˆp, w). In the allocation setting, the value ratio is simply the (normalized) social welfare, a natural measure of efﬁciency. In the wagering setting, a high

2We thank Brian Galebach for providing us with this data.

value ratio can be seen as encouraging participation, since forecasters will be more likely to participate when they expect to make a higher proﬁt. High participation is crucial to harnessing the wisdom-of-crowds principle and constructing a good aggregate forecast. Fraction of securities allocated is the quantity 1 m W Pn i=1 Pm j=1 Bi,j(ˆp, w). In the allocation setting, this is a measure of waste, with lower values implying higher waste, while in the wagering setting any wasted securities become mechanism proﬁt when the corresponding outcome occurs. Fraction of agents with an IR violation is the fraction of agents for whom the expected value of their security allocation is less than the value of their wager. The ﬁnal column is similar to value ratio, but calculated only over agents with an individual rationality violation, giving a sense of the magnitude of the violations. Judging by these metrics, the double clinching auction (DCA) and strong demand matching (SDM) show the strongest performance, with comparably high value ratios, negligible waste, and negligible violations of individual rationality (none in the case of DCA). Despite their strong theoretical guarantees but in line with previous observations (Freeman, Pennock, and Vaughan 2017), weighted score (WSWM) and no-arbitrage (NAWM) wagering do not facilitate much trade, creating little value for the agents. At the other end of the spectrum, partial allocation (PA) suffers poor performance across the board, violating individual rationality for almost all agents, and often substantially so. We note that the small number of individual rationality violations observed for constrained serial dictatorship (CSD) stem from the fact that CSD allocations can only be computed approximately. To understand how performance scales with the size of the instance, we next subsampled n agent reports and generated wagers for each n {5, 10, . . . , 50}. Figure 1 shows a selection of the results for agents with Pareto distribution wagers. More are included in the full version of the paper. Results for uniform wagers were similar, though the double clinching auction and partial allocation exhibit no envy in those cases. We see similar trends in value ratios (left plot), but with strong demand matching exhibiting a clear advantage over the double clinching auction. The center plot shows the fraction of instances for which at least one agent envies another, limited to those mechanisms that are not guaranteed to be envy-free. In all cases, envy almost always exists. For a pair of agents (i, j), deﬁne the envy ratio as the expected utility that i would receive if she were allocated j s securities, divided by the expected utility she receives from her own allocation, and scaled to adjust for wagers. The right plot shows the maximum envy ratio on instances for which at least one agent envies another. We see that partial allocation often leads to signiﬁcant amounts of envy.

6 Discussion

While we have focused on the positive implications of the equivalence between wagering and fair division mechanisms, we note that it immediately implies new impossibility results as well. For instance, a classical result of Schum-

Value Ratio Fraction of Securities Allocated Fraction of Agents with an IR Violation Value Ratio for Agents with an IR Violation WSWM 1.092 1.000 0 n/a NAWM 1.046 0.954 0 n/a DCA 1.326 0.997 0 n/a CSD 1.168 1.000 0.004 0.997 PA 0.490 0.369 0.995 0.487 SDM 1.329 0.999 0.042 0.999

Table 2: Comparison of mechanisms on the full Probability Sports dataset with uniform wagers.

Figure 1: Value ratio (left), fraction of instances with envy (center), and average maximum envy across all instances with envy (right) on a subsample of the Probability Sports data with Pareto distribution wagers.

mer (1996) in the allocation setting says that the only incentive compatible and Pareto optimal mechanisms are dictatorial. This result carries over to the wagering setting, and complements the impossibility result of Freeman, Pennock, and Vaughan (2017) that no weakly budget-balanced wagering mechanism can simultaneously satisfy incentive compatibility, side-bet Pareto optimality, and individual rationality. As another example, Han et al. (2011) showed that, for large enough n, no incentive compatible allocation mechanism can achieve better than a 1/m approximation to the optimal social welfare. This result also carries over to wagering. Despite the equivalence, we expect there to be continued value in studying the two problems in isolation. Different design criteria have traditionally been emphasized for the two most notably, strict incentive compatibility (drawing heavily on the scoring rule literature) for wagering and envyfreeness for fair division and different mechanisms may be more appropriate in one setting than the other. However, the connection we revealed opens up the possibility of applying any new results developed in one setting to the other, an approach we expect to be fruitful as both ﬁelds develop.

Acknowledgments

We thank Haris Aziz for pointing us to some helpful literature on fair division.

Aziz, H., and Ye, C. 2014. Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In Conference on Web and Internet Economics. Aziz, H.; Brandt, F.; Brill, M.; and Mestre, J. 2015. Com-

putational aspects of random serial dictatorship. ACM SIGecom Exchanges 13(2):26 30. Aziz, H.; Brandt, F.; and Brill, M. 2013. The computational complexity of random serial dictatorship. Economics Letters 121(3):341 345. Brams, S. J., and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Brier, G. W. 1950. Veriﬁcation of forecasts expressed in terms of probability. Monthly Weather Review 78(1):1 3. Chen, Y.; Devanur, N. R.; Pennock, D. M.; and Vaughan, J. W. 2014. Removing arbitrage from wagering mechanisms. In ACM Conference on Economics and Computation. Cole, R.; Gkatzelis, V.; and Goel, G. 2013. Mechanism design for fair division: Allocating divisible items without payments. In ACM Conference on Electronic Commerce. Dobzinski, S.; Lavi, R.; and Nisan, N. 2008. Multi-unit auctions with budget limits. In IEEE Symposium on Foundations of Computer Science. Eisenberg, E., and Gale, D. 1959. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics 30(1):165 168. Foley, D. 1967. Resource allocation and the public sector. Yale Economics Essays 7:45 98. Freeman, R., and Pennock, D. M. 2018. An axiomatic view of the parimutuel consensus mechanism. In International Joint Conference on Artiﬁcial Intelligence. Freeman, R.; Pennock, D. M.; and Vaughan, J. W. 2017. The double clinching auction for wagering. In ACM Conference on Economics and Computation.

Galebach, B. 2018. Probability Sports. http:// probabilitysports.com/. Gneiting, T., and Raftery, A. E. 2007. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association 102(477):359 378. Han, L.; Su, C.; Tang, L.; and Zhang, H. 2011. On strategyproof allocation without payments or priors. In Conference on Web and Internet Economics, 182 193. Kilgour, D. M., and Gerchak, Y. 2004. Elicitation of probabilities using competitive scoring rules. Decision Analysis 1(2):108 113. Lambert, N. S.; Langford, J.; Wortman, J.; Chen, Y.; Reeves, D. M.; Shoham, Y.; and Pennock, D. M. 2008. Self-ﬁnanced wagering mechanisms for forecasting. In ACM Conference on Electronic Commerce. Lambert, N. S.; Langford, J.; Vaughan, J. W.; Chen, Y.; Reeves, D.; Shoham, Y.; and Pennock, D. M. 2015. An axiomatic characterization of wagering mechanisms. Journal of Economic Theory 156:389 416. Procaccia, A. D. 2013. Cake cutting: Not just child s play. Communications of the ACM 56(7):78 87. Robertson, J. M., and Webb, W. A. 1998. Cake Cutting Algorithms: Be Fair If You Can. AK Peters/CRC Press. Savage, L. J. 1971. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association 66(336):783 801. Schummer, J. 1996. Strategy-proofness versus efﬁciency on restricted domains of exchange economies. Social Choice and Welfare 14(1):47 56. Steinhaus, H. 1948. The problem of fair division. Econometrica 16:101 104. Walras, L. 2013. Elements of pure economics. Routledge.