Getting More by Knowing Less: Bayesian Incentive Compatible Mechanisms for Fair Division

1 Introduction

A central goal within the fair division literature is to design procedures that distribute indivisible or divisible goods among groups of agents. For a resource allocation procedure to reach fair and efficient outcomes, however, it needs to have access to the preferences of the participating agents. Whenever this information is private and each agent can strategically misreport it, the literature is riddled with negative results: eliciting the true preferences of the agents while simultaneously guaranteeing fairness and efficiency is usually impossible. One of the main underlying reasons is that monetary payments are commonly infeasible or undesired in fair division, and designing "truthful" mechanisms in the absence of such payments poses often insurmountable obstacles.

Another factor that contributes to the plethora of impossibility results is that "truthfulness" in this literature has been used as a synonym for "Dominant Strategy Incentive Compatibility" (DSIC). This is a very demanding notion of incentive compatibility which requires that every agent prefers truthtelling to misreporting, no matter what the other agents' reports are. This ensures that no agent will have an incentive to lie, even if they know exactly what every other agent's preferences are. However, in most real-world applications it is unreasonable to assume that the agents know that much about each other, so this notion may be unnecessarily stringent. In fact, if we assume that an agent would strategically misreport their preferences only if they have enough information to suggest that this would be beneficial then, in some sense, the less an agent knows the less likely it is that they would misreport. Rather than going to the other extreme and assume the agents have no information about each other, in this paper we consider the well-established truthfulness notion of "Bayesian Incentive Compatibility" (BIC). This instead assumes that each agent's preference is drawn from a publicly known prior distribution and the requirement is that telling the truth is the optimal strategy for each agent in expectation over the other agents' reports. Simply put, our goal in this paper is to understand what can and what cannot be achieved by BIC mechanisms in the context of fair division, and the extent to which they can outperform DSIC mechanisms.

1.1 Our Contributions

We explore the power and limitations of incentive compatible mechanisms when allocating either indivisible or divisible goods among n strategic agents with additive valuations, i.e., such that an agent's value for a set of goods is equal to the sum of her values for each good separately.

Allocating indivisible goods. It is well-known that the only deterministic DSIC mechanism for allocating indivisible goods among two agents in a Pareto efficient way is the patently unfair "serial dictatorship" mechanism [Klaus and Miyagawa, 2002; Schummer, 1996], where one of the agents is allocated all the goods that they have a positive value for, and the other agent receives the leftovers. Since Pareto efficiency may be a lot to ask for, one could imagine that a more forgiving notion of efficiency based on stochastic dominance (SD) [Bogomolnaia and Moulin, 2001] may allow us to overcome this obstacle. Our main negative result shows that this is not the case: even for the more permissive notion of SD+efficiency (defined in Section 3.1) instead of Pareto efficiency, we prove that the only deterministic DSIC mechanism remains the serial dictatorship, and this holds even if for every agent i, their value for each good j can take one of only three possible values, i.e. vi,j ∈ {0, x, y} (Theorem 3). In fact, we show that our stronger negative result is tight in more than one ways: if we were to further relax SD+efficiency to SD efficiency (also defined in Section 3.1), or to further restrict the number of possible agent values to two instead of three, this would permit more deterministic DSIC mechanisms beyond serial dictatorship.

Surprisingly, it is also known that, even if we were to completely drop any efficiency requirement in order to avoid the extreme unfairness of the serial dictatorship, our ability to provide non-trivial fairness guarantees would still be severely limited. For example, if we wanted the outcome to be envy-free up to one good (EF1), which is a wellstudied relaxation of envy-freeness [Lipton et al., 2004; Budish, 2011], this is known to be impossible to achieve using any deterministic DSIC mechanism, even for instances with just two agents [Amanatidis et al., 2017a]. Our main positive result shows that we can simultaneously overcome all of the aforementioned negative results if instead of DSIC we focus on BIC mechanisms. In fact, we can achieve this using a variation of the very practical Round-Robin procedure (where agents take turns choosing a single good each time). We prove that our variation, RRpass , is BIC for any distribution over agent preferences that is "neutral" [Moulin, 1980], and it returns allocations that always combine fairness (in the form of EF1) with efficiency (in the form of SD+efficiency) (Theorem 4). Apart from providing a separation between BIC and DSIC mechanisms by bypassing both of these negative results, this also exhibits a third way in which our result from Theorem 3 is tight. Our definition of a "neutral" prior is satisfied by the common assumption in the stochastic fair division literature, that vi,js are drawn i.i.d. from an agent-specific distribution Di [Bai and G¨olz, 2021; Manurangsi and Suksompong, 2020; Manurangsi and Suksompong, 2021; Amanatidis et al., 2017b], going beyond, it also allows for certain priors where valuations are neither independently nor identically distributed (see Section 3.2).

Encouraged by our positive result, which exhibits a practical BIC mechanism that combines fairness and SD+efficiency, one may wonder whether BIC mechanisms can even optimize well-motivated welfare functions. For example, a lot of recent work in fair division has focused on maximizing the Nash social welfare (the geometric mean of agents' utilities). Apart from guaranteeing Pareto efficiency, this outcome is also known to be EF1 for agents with additive valuations [Caragiannis et al., 2019], and it is used in Spliddit, a popular platform for allocating indivisible goods [Goldman and Procaccia, 2015; Shah, 2017]. Our findings along this direction are negative: we show that even for a very simple neutral distribution (uniform over normalized valuations), a mechanism that maximizes any welfare function from a large well-studied family that satisfies the Pigou-Dalton principle (which, e.g., includes the Nash social welfare, the egalitarian social welfare, the utilitarian social welfare, and the leximin criterion) is not BIC (Theorem 5). Finally, we prove that if we aim for the strong efficiency guarantee of fractional Pareto optimality (fPO), requiring that the outcome is not Pareto dominated even by randomized allocations, then BIC mechanisms cannot even satisfy fullfillment, which is a fairness notion that is much weaker than EF1 (Theorem 6). Informally, an allocation is fulfilling if, whenever agent i values at least n goods strictly positively, her utility for her bundle is strictly positive.

Allocating divisible goods. Moving beyond indivisible goods, we then consider mechanisms for the fair allocation of continuous, divisible, heterogeneous resources, using the classic cake-cutting model. The cake, which captures a divisible resource, is represented as the interval [0, 1] and it must be distributed among n agents with different valuations on different parts of the interval. Typically, agents' valuation functions are described by probability density functions. Recently, [Tao, 2022] showed that, even for n = 2 agents with piecewise constant valuation functions, there is no deterministic and DSIC cake-cutting mechanism that always outputs a proportional allocation, i.e., one where each agent receives at least a 1/n fraction of their total value. Our main result for this problem circumvents this impossibility for any number of agents by relaxing to BIC mechanisms (Theorem 8). Specifically, we propose a deterministic cake-cutting mechanism that is proportional and BIC for all neutral priors. Our mechanism works over a sequence of n rounds: in round i, agent i arrives and agents 1 through i -1 are asked to cut the pieces allocated to them so far into i equal-sized and equalvalued crumbs. Then, agent i takes one crumb from each of the first i - 1 agents. The fact that this operation can always be performed crucially relies on the result of [Alon, 1987] concerning the existence of a perfect partition. 1 Apart from piecewise constant valuation functions, our mechanism also provides the same guarantees for piecewise linear valuations, which can be succinctly represented, and for which perfect partitions can be computed efficiently.

1.2 RelatedWork

Bayesian incentive compatibility in fair division has been considered in the random assignment problem, with n goods and n agents with ordinal preferences. [Dasgupta and Mishra, 2022] consider ordinal BIC mechanisms (OBIC), and show that the probabilistic serial mechanism, which is ordinally efficient and satisfies equal treatment of equals, is OBIC with respect to the uniform prior. The notion of OBIC of [Dasgupta and Mishra, 2022] has been used in voting theory, dating back to [d'Aspremont and Peleg, 1988], to escape infamous dictatorship results [Gibbard, 1973; Satterthwaite, 1975]. For cardinal valuations, such as ours, [Fujinaka, 2008] studies the case of a single indivisible good that must be allocated to one of n agents whose (private) values for the good are drawn from a known product distribution. When payments are possible, [Fujinaka, 2008] designs an envy-free, budget-balanced and BIC mechanism.

1 Informally, a partition is said to be perfect if the value of every piece is the same for every agent.

Another line of work considers other relaxations of DSIC. For example, in the random assignment problem, [Mennle and Seuken, 2021] introduce the notion of partial strategyproofness, a relaxation of DSIC, which is satisfied if truthful reporting is a dominant strategy for agents who have sufficiently different valuations for different objects, and show that in the context of school choice, this notion gives a separation between the classic and the adaptive Boston mechanism. Starting with [Troyan and Morrill, 2020], a number of recent papers [Ortega and Segal-Halevi, 2022; Aziz and Lam, 2021; Psomas and Verma, 2022] relax the DSIC requirement and explore the design of not obviously manipulable (NOM) mechanisms. Under NOM, an agent reports their true type, unless lying is obviously better, where the definition of "obvious" for a strategy follows recent work in Economics [Li, 2017]. Closer to our interest here, [Psomas and Verma, 2022] study the allocation of indivisible goods among additive agents, and prove that one can simultaneously guarantee EF1, PO, and NOM. [Ortega and Segal-Halevi, 2022] show that, in the context of cake-cutting, NOM is compatible with proportionality: an adaptation of the moving-knife procedure satisfies both properties.

Other ways to escape the aforementioned impossibility results in truthful fair division is restricting agents' valuations, e.g. by focusing on dichotomous [Halpern et al., 2020; Babaioff et al., 2021; Benabbou et al., 2021; Barman and Verma, 2021] or Leontief valuations [Ghodsi et al., 2011; Friedman et al., 2014; Parkes et al., 2015], or by using money-burning (that is, leave resources unallocated) as a substitute for payments, while trying to minimize the inefficiency that these payment substitutes introduce (e.g., [Hartline and Roughgarden, 2008; Cole et al., 2013; Fotakis et al., 2016; Friedman et al., 2019; Abebe et al., 2020]). Finally, a recent research thread suggests the study of mechanisms that produce fair allocations in their equilibria [Amanatidis et al., 2023b; Amanatidis et al., 2023a]. Interestingly, for agents with additive valuations over indivisible goods, it is known that allocations obtained in equilibria of the Round-Robin algorithm are EF1 with respect to the agents' true valuation functions [Amanatidis et al., 2023a].

2 Preliminaries

Allocating indivisible goods. We are given a set M of m indivisible items indexed by [m] := {1, 2, . . . ,m} to be allocated among a set N of n agents indexed by [n]. An allocation x ∈ {0, 1}n×m assigns items to agents such that xi,j = 1 if agent i gets item j and 0 otherwise. We use xi = (xi,1, . . . , xi,m) ∈ {0, 1}m to denote agent i's allocation and Xi = {j : xi,j = 1} to denote agent i's bundle in x. In an allocation, each item j ∈ Mmust be allocated to exactly one agent, i.e., ∑ni=1 xi,j = 1. Each agent i ∈ N has a private type which is a valuation vector vi ∈ Rm≥0 where vi,j is agent i's value for item j ∈ M. Collectively, the valuations of all the agents are represented by a valuation profile v = (v1, . . . , vn). The utility of agent i for a given allocation x, denoted by ui(x), is additive and defined as ui(x) := ∑j∈M vi,jxi,j. We will often overload notations and use ui(Xk) to denote the utility of agent i ∈ N for a specific bundle Xk ∈ M.

An allocation x Pareto dominates another allocation y if for all agents i ∈ N, we have ui(x) ≥ ui(y) and uj(x) > uj(y) for some agent j ∈ N. An allocation x is Pareto efficient (or Pareto optimal) if there is no other allocation x′ that Pareto dominates it.

An allocation x is called envy-free (EF) if for every pair of agents i and j ∈ N, agent i values their allocation at least as much as the allocation of agent j, i.e., ui(xi) ≥ ui(xj). However, for the indivisible item settings, an envy-free allocation is not guaranteed to exist. Therefore, we consider a relaxed notion called envy-free up to one good (EF1). Formally, an allocation x is EF1 if for every pair of agents i and j ∈ N with Xj ̸= ∅, agent i values their allocation at least as much as the allocation of agent j without agent i's favorite item, i.e., ui(Xi) ≥ ui(Xj \ {g}) for some g ∈ Xj .

Allocating divisible goods. We study the cake-cutting problem where the cake is represented by the interval [0, 1] and is to be allocated among the set N of n agents. An allocation x = (X1, . . . ,Xn) is a collection of mutually disjoint subsets of [0, 1] where Xi ⊆ [0, 1] denotes the subset of the cake allocated to agent i ∈ N. Each agent i's private type is a density (valuation) function fi : [0, 1] → R≥0 over the cake, such that ∫ 1 0 fi(x)dx = 1 for all i ∈ N. We use f = (f1, . . . , fn) to denote the collection of density functions of all agents. Given a subset S ⊆ [0, 1], agent i's utility on S is defined as ui(S) = ∫S fi(x)dx.

We primarily focus on two classes of valuation functions, namely piecewise-constant and piecewise-linear valuations. For both families, the interval [0, 1] can be partitioned into finite intervals. For the former class, the value of the function in each interval is a constant; for the latter class it is linear.

An allocation x = (X1, . . . ,Xn) is proportional if each agent receives her average share of the entire cake. Formally, for each agent i ∈ N we have ui(Xi) ≥ 1n · ui([0, 1]) = 1n .

Mechanisms and incentive compatibility. For both indivisible and divisible goods, each agent i has a private type ti: the valuations vi for the first and the functions fi for the second. The agents, being strategic, may choose to misreport it if doing so increases their utility. We use b = (b1, . . . , bn) to represent the reported type bi of all agent i ∈ N. A mechanism is represented by an allocation function x(·), which takes as input reports b = (b1, . . . , bn) and outputs a feasible allocation x(b). For notational simplicity, we often refer to a mechanism directly using its allocation function x(·).

We say a mechanism is incentive compatible if it offers robustness guarantees against strategic behaviors of agents. In this paper, we consider two notions of incentive compatibility. A mechanism is dominant strategy incentive compatible (DSIC) if truthful reporting is a dominant strategy for every agent. Formally, for every agent i ∈ N, every possible report bi, and all possible reports of all other agents b-i, we have

We also study the incentives in the Bayesian setting where agents have some prior knowledge of each other's type. We assume that the type ti of each agent i ∈ N is drawn from some known prior distribution Di. A mechanism is Bayesian incentive compatible (BIC) for priors ×ni=1Di if reporting truthfully is a Bayesian Nash equilibrium, i.e., no agent can increase her expected utility by unilaterally misreporting, the expectation being taken over the types of other agents. We use D-i to denote the prior ×j̸=iDj . Formally, for each agent i ∈ N, and every possible report bi, we have

3 Allocating Indivisible Goods

Previous work on the allocation of indivisible goods has uncovered that DSIC mechanisms cannot be both fair and efficient. A notable example shows that requiring Pareto efficiency from a deterministic DSIC mechanism limits the available options to the patently unfair class of serial dictatorships.

Theorem 1 ([Klaus and Miyagawa, 2002]). For n = 2 agents, a DSIC deterministic mechanism is Pareto efficient if and only if it is a serial dictatorship.

Our first result, Theorem 3 in Section 3.1, strengthens Theorem 1, showing that even if we weaken the efficiency requirement from Pareto efficiency to SD+efficiency, a natural relaxation defined below, the only deterministic DSIC mechanisms that can guarantee SD+efficiency are serial dictatorships. Another notable result shows that no deterministic DSIC mechanism always outputs EF1 allocations.

Theorem 2 ([Amanatidis et al., 2017a]). There is no deterministic DSIC mechanism that outputs EF1 allocations, even for instances involving just n = 2 agents.

Theorem 4 in Section 3.2 shows that if we relax the notion of truthfulness from DSIC to BIC, then neither one of these two negative results holds anymore, i.e., there exists a non-dictatorial deterministic BIC mechanism that guarantees EF1. In Section 3.3 we also uncover the limitations of BIC mechanisms by proving that a wide family social choice functions are incompatible with BIC.

3.1 Strengthening the Characterization of Serial Dictatorships

For a given agent i let pi be a ranking of items j ∈ M in decreasing order of i's value for them, where pi(k) = j if item j is agent i's kth favorite item. 2 For two bundles xi, yi ∈

2 For items with the same value, we break ties lexicographically, i.e., if vi,j = vi,k and j < k, then item j is ranked before k in pi.

{0, 1}m, xi weakly stochastically dominates yi for agent i, or xi ⪰i yi, iff for all ℓ ∈ [m] we have

Additionally, we say that xi (strictly) stochastically dominates yi for agent i, or xi ≻i yi, iff xi ⪰i yi and xi ̸= yi. If xi ≻i yi, then there exists an ℓ ∈ [m] for which Inequality (1) is strict.

To define our refinement of stochastic dominance, for each agent i ∈ N we let M+i denote the set of items that i has a positive value for, i.e., M+i := {j ∈ M : vi,j > 0}. Let mi = |M+i |. For two bundles xi, yi ∈ {0, 1}m, we say that xi weakly stochastically and positively dominates yi, denoted as xi ⪰+i yi, iff Inequality (1) is satisfied for all ℓ ∈ M+i . Thus, partial order ⪰+i is essentially the partial order ⪰ defined over the set of itemsM+i . Similarly, xi ≻+i yi iff xi ⪰+i yi and xi ̸= yi. Akin to the previous definition, if xi ≻+i yi, then there exists an ℓ ∈M+i for which Inequality (1) is strict. Note that, if two bundles satisfy xi ⪰i yi, then by definition, xi ⪰+i yi as well. The following lemma relates the partial orders defined above with utilities; its proof along with other missing proofs from this subsection appear in the full version [Gkatzelis et al., 2023].

Lemma 1. For any agent i ∈ N and any two bundles a, b ∈ {0, 1}m, the following statements hold: (1) If a ⪰+i b, then ui(a) ≥ ui(b), and (2) If a ≻+i b, then ui(a) > ui(b).

We say that an allocation y stochastically dominates x, denoted as y ≻ x iff for all agents i ∈ N we have yi ⪰i xi and for at least one agent j ∈ N we have yj ≻j xj. Similarly, we say that an allocation y stochastically and positively dominates x, denoted as y ≻+ x iff for all agents i ∈ N we have yi ⪰+i xi and for at least one agent j ∈ N we have yj ≻+j xj.

Definition 1. An allocation x is SD efficient iff there is no other allocation y such that y ≻ x.

Definition 2. An allocation x is SD+efficient iff there is no other allocation y such that y ≻+ x.

In the following lemma we show that SD+efficiency is implied by Pareto efficiency and SD+efficiency implies SD efficiency.

Lemma 2. The following two implications hold for any number of items and agents with additive preferences: (1) If an allocation x is Pareto efficient then x is SD+efficient as well; (2) If an allocation x is SD+efficient then x is SD efficient as well. Moreover, there exist allocations that are SD+efficient and not Pareto efficient, and allocations that are SD efficient and not SD+efficient.

Now we state the main result of this subsection.

Theorem3. (Characterization of serial dictatorship) For n = 2 agents, a deterministic DSIC mechanism is SD+efficient if and only if it is a serial dictatorship. This holds even when agents have ternary valuations, i.e., for all agents i and items j, we have vi,j ∈ {0, x, y} for some y > x > 0.

Tightness of the above characterization Theorem 3 is tight in two orthogonal ways. Specifically, if we relax SD+efficiency to the weaker notion of SD efficiency, then serial dictatorship no longer remains the only DSIC mechanism- this is formally stated in Proposition 1. Note that although SD efficiency is widely used in the context of matchings (where all agents receive the same number of items), the notion of SD+efficiency is more appropriate when each agent may receive a different number of items. Specifically, an allocation can only be stochastically dominated by another allocation if all agents receive at least the same number of items; this is not true for stochastic and positive domination.

Proposition 1. For n = 2 agents, there exists a deterministic mechanism other than the serial dictatorship that is DSIC and outputs SD efficient allocations.

Second, the proof of Theorem 3 holds even for ternary preferences i.e., vi,j ∈ {0, x, y} for all i ∈ N and j ∈ M. However, Theorem 3 does not hold if we consider the slightly more restricted class of bivalued preferences, i.e., vi,j ∈ {x, y} for fixed x, y ∈ R≥0; this essentially follows from known results.

Proposition 2. For bivalued additive preferences, there exist DSIC, non-dictatorial mechanisms that output Pareto efficient allocations.

3.2 Round Robin Is BIC

We now show that a variation of Round-Robin, which we call ROUND-ROBIN pass (RRpass ), is BIC for neutral priors. Moreover, RRpass always outputs an SD+efficient and EF1 allocation, 3 bypassing the negative results of Theorems 2 and 3. Missing proofs can be found in [Gkatzelis et al., 2023].

The Bayesian Setting. We assume that the for each agent i ∈ N, there is a neutral prior distribution Di supported over Rm≥0 such that the valuation vector vi = (vi,1, . . . , vi,m) ∼ Di. We say that Di is neutral if for every permutation σ : [m] → [m], we have Prvi∼Di [vi,σ(1) > . . . > vi,σ(m)] = 1m! , and for each j ∈ M, the marginal distribution of Di wrt vij does not have point masses. Intuitively, neutral priors imply that all items are equivalent, in expectation. A natural example of a neutral prior is vi,j ∼ ̂Di where ̂Di is supported on R≥0 and does not have a point mass. This exact prior has been extensively studied in previous works including [Bai and G¨olz, 2021; Manurangsi and Suksompong, 2020; Manurangsi and Suksompong, 2021; Amanatidis et al., 2017b]; a stochastic fair division model based on neutrality is also studied in [Benad`e et al., 2023]. Note that, neutral priors are permissive enough to allow for correlated item values, for e.g., if vi ∼ ∆m-1 where ∼ ∆m-1 denotes a uniform draw from the m- 1-simplex, 4 then the item values are identically distributed but not independent. Additionally, the item values for an agent don't even have to be identically drawn: for two items, the prior vi,1 ∼ U[0, 1] and vi,2 ∼ U[ 1 2 , 34 ] is neutral. 5

3 We note that items which have zero value for all the agents won't be allocated by RRpass . Indeed, this does not affect the fairness and efficiency guarantees of RRpass .

4 Recall that, an m- 1-simplex ∆m-1 = {(x1, x2, . . . , xm) : ∑i xi = 1 and xi ≥ 0 for all i}

5U[a, b] represents a uniform distribution over the interval [a, b].

Our Mechanism. We begin by defining the RRpass mechanism: intuitively, we execute the standard Round-Robin procedure but allow agents to pass their turn if all the remaining items are zero-valued. Formally, given the report bi for each agent i ∈ N, the mechanism first computes a tuple (pi,mi), where pi is the strict preference order of items for agent i (ties are broken lexicographically), and mi = |M+i |, where M+i = {j : bi,j > 0} is the set of items agent i values positively. Then the mechanism constructs the output allocation over rounds. In each round, agents arrive in the fixed order 1, 2, . . . , n, and each agent i ∈ N is allocated the item with the smallest (according to pi) ranking among the set of remaining items; if in agent i's turn all items in M+i have already been allocated, then RRpass skips i's turn. This process is repeated until either all the items are allocated or all remaining items are undesirable for all the agents. In the latter case, the remaining items are allocated deterministically and arbitrarily among the agents, resulting in a complete allocation. RRpass is almost ordinal, i.e., to execute it we need the (strict) preference order pi, but also the number of zerovalued items mi for each i ∈ N (noting that one can construct M+i by looking at the bottom mi elements of pi). Thus, in the subsequent discussion, we often interchange vi with (pi,mi). Our goal is to prove the following theorem.

Theorem 4. The ROUND-ROBIN pass mechanism is Bayesian incentive compatible for neutral priors, and always outputs SD+efficient and EF1 allocations.

First, we prove that RRpass is BIC for neutral priors. The high-level idea of our proof is similar to the arguments of [Dasgupta and Mishra, 2022] for showing that the probabilistic serial mechanism is BIC in a setting with complete ordinal preferences. Unlike the ordinal setting, our cardinal setting allows agents to have undesirable, zero-valued items. As hinted by Theorem 3 and Proposition 1, allowing for zero values makes it harder to establish incentive guarantees. To mitigate this, our mechanism RRpass (contrary to Round-Robin) never allocates an item to an agent that doesn't value it, unless the item is valued at zero by everyone. This special treatment of zero values is required to prove key structural properties about the interim allocation (defined below), which are used throughout our proofs.

For each agent i ∈ N and item j ∈ M we define the interim allocation qi,j(bi) ∈ [0, 1] of a mechanism with allocation function x(·) to be the probability that agent i is allocated item j when she reports bi. Formally, qi,j(bi) = Pv-i∼D-i [xi,j (bi, v-i)].

We show that, for each agent i ∈ N, the interim allocation of the RRpass mechanism, given neutral priors, is very structured. For each agent i ∈ N, there is a (fixed) positional interim allocation qpos i = (qpos i,1 , qpos i,2 , . . . , qpos i,m ) such that, if agent i reports valuation bi to RRpass , then her interim allocation qi,j(bi) is exactly qpos i,k if bi,j > 0 and pi(k) = j; otherwise, qi,j(bi) = 0 if bi,j = 0 (Lemma 3). Intuitively, the interim allocation of a positively valued item depends on only its position in the preference order. Furthermore, the positional interim allocations are monotone: qpos i,1 ≥ . . . ≥ qpos i,m (Lemma 4).

Lemma 3. For each agent i ∈ N, there exists a positional interim allocation qpos i = (qpos i,1 , . . . , qpos i,m ) such that if agent i reports any valuation bi, then her interim allocation qi,j (bi) = qpos i,k if (i) bi,j > 0, and (ii) pi(k) = j; otherwise, qi,j(bi) = 0 if bi,j = 0.

Lemma 4. Positional interim allocations are monotone, i.e., qpos i,1 ≥ qpos i,2 ≥ . . . ≥ qpos i,m for all i ∈ N.

Using these two lemmas we show that RRpass is BIC for neutral priors. The high-level intuition is as follows. If agent i reports valuation bi having a corresponding preference order pi = (j1, j2, . . . , jm), then Lemma 3 implies that the interim allocations qi,j1 (bi), qi,j2 (bi), . . . , qi,jn (bi) will be (a prefix of) the positional interim allocation qpos i , which, as per Lemma 4 is monotone, qpos i,1 ≥ . . . ≥ qpos i,m . That is, the interim allocations are non-increasing in the reported preference order and are always a permutation of qpos i . Note that, the expected utility of agent i as per her true preference vi is ∑mk=1 qi,jk (bi) · vi,jk , which essentially is a vector dot product of the true valuation and the interim allocation. This dot product is maximized when the true valuations and the interim allocations are aligned (i.e., are in the same order). Given that the interim allocation is always a permutation of qpos i , this alignment happens when agent i's reported preference order matches her true preference order, i.e., when agent i reports vi, establishing that RRpass is BIC. This intuition is formalized in the following lemma.

Lemma 5. The ROUND-ROBIN pass mechanism is Bayesian incentive compatible for neutral priors.

The following lemma proves that RRpass also satisfies SD+efficiency and EF1.

Lemma 6. The ROUND-ROBIN pass mechanism outputs SD+efficient and EF1 allocations.

Combined, Lemmas 5 and 6 imply Theorem 4.

3.3 Welfare Functions and BIC

In this section, we prove that a large family of "welfare maximizing" mechanisms is not Bayesian incentive compatible. All proofs of this section appear in [Gkatzelis et al., 2023].

A welfare function f : Rn≥0 → R is a function that, given the utilities of agents u1(x), . . . , un(x) in allocation x, outputs f(u1(x), . . . , un(x)), that represents the collective welfare of all the agents in allocation x. An allocation x is said to maximize f if for all other feasible allocations y we have f(u1(x), . . . , un(x)) ≥ f(u1(y), . . . , un(y)).

Definition 3 (Anonymous). A welfare function f is called anonymous iff f(x1, x2, . . . , xn) = f(xπ1 , xπ2 , . . . , xπn ) for any permutation π : [n] → [n].

Definition 4 (Strictly monotone). A welfare function f is strictly monotone iff f(x1, x2, . . . , xn) > f(y1, y2, . . . , yn) whenever we have xi ≥ yi for all i ∈ [n] and xj > yj for some j ∈ [n].

Definition 5 (The Pigou-Dalton principle). The PigouDalton Principle (PDP) states that a welfare function should weakly prefer a profile that reduces the inequality between two agents, assuming that the utilities of all other agents stay unchanged. Formally, a welfare function f satisfies PDP iff for any two vectors (x1, . . . , xn) and (y1, . . . , yn) such that there are two distinct i, j ∈ [n] satisfying (i) xi + xj = yi + yj, (ii) xi > xj, (iii) xi > yi > xj (equivalently xi > yj > xj), and (iv) xk = yk for all k ∈ [n] \ {i, j}, we have f(x1, x2, . . . , xn) ≤ f(y1, y2, . . . , yn).

Welfare functions satisfying anonymity, strict monotonicity, and the PDP constitute a broad set of functions that include, e.g., the class of all the p-mean welfare functions 6 for p ≤ 1 [Moulin, 2004]. The class of p-mean welfare functions, in turn, includes Nash social welfare, egalitarian social welfare, utilitarian social welfare, and the leximin criterion. In Theorem 5, we show that, for any deterministic (or randomized) mechanism that outputs allocations that (ex-post) maximize such a welfare function, f, is not BIC. We prove this fact for a very simple neutral prior distribution according to which each agent i's values are drawn uniformly from the m- 1-simplex, i.e., vi = (v1, v2, . . . , vm) ∼ ∆m-1 . Notably, Theorem 4 also holds for this neutral prior supported over normalized valuations. 7

Theorem 5. There is no deterministic (or randomized) mechanism that is Bayesian incentive compatible for the uniform prior and which always outputs allocations that ex-post maximize welfare function f, where f is any anonymous, strictly monotone function satisfying the Pigou-Dalton principle.

A slightly modified version of the above proof can be used to show the non-existence of deterministic (or randomized) mechanisms that are Bayesian incentive compatible and output allocations that are ex-post fPO and EF1. In fact, we can rule out BIC mechanisms that output fPO allocations that satisfy a fairness criterion we call fulfillment, that is much weaker than EF1. Specifically, an allocation x is fulfilling iff the following condition is satisfied for all agents i ∈ N: if i has at least n items that she values positively, then agent i gets a bundle of positive utility. It is easy to see that an EF1 allocation must be fulfilling. Formally, this result is stated as Theorem 6.

Theorem 6. There is no deterministic (or randomized) Bayesian incentive compatible mechanism that outputs fPO allocations that are fulfilling.

4 Allocating Divisible Goods: Cake Cutting

Recently, [Tao, 2022] proved a strong incompatibility between fairness and incentives in the cake-cutting problem: no deterministic DSIC cake-cutting mechanism can always output proportional allocations (see Theorem 7), for the case of n = 2 agents and piecewise constant density functions.

6 For a given p ∈ R≥0, the p-mean welfare function is defined as fp(x1, x, . . . , xn) := ( 1n ∑ni=1 xpi )1/p . Notably, fp captures utilitarian welfare if p = 1, Nash welfare if p → 0, and egalitarian welfare if p → -∞.

7 It is necessary to consider normalized valuations when studying welfare objectives that aren't scale-free, for e.g. social welfare. In particular, if the valuations aren't normalized, then agents could (mis)report large values for all the items, thereby forcing the mechanism to allocate all the items to them.

Theorem 7 ([Tao, 2022]). There is no deterministic, DSIC, and proportional cake-cutting mechanism for piecewiseconstant valuations, even for n = 2 agents.

The Bayesian Setting. The private piecewise-constant valuation function f ∗ i of each agent i is drawn from a neutral prior distribution Di. We say a prior distribution D is neutral, iff for all integers k > 1, and disjoint pieces of cake X1,X2, . . . ,Xk satisfying |X1| = |X2| = . . . = |Xk|, we have Pr f ∗∼D[j = argmaxki=1 f ∗ (Xi)] = 1/k. Intuitively, neu-

tral priors represent a distribution of density functions such that the probability of an agent preferring an interval over another same-length interval is the same, i.e., same-length intervals are equivalent in expectation. Towards bypassing Theorem 7, we provide a deterministic mechanism (Mechanism 1), which we refer to as INCREMENTALACCOMMODATION (IA), and we show that IA is Bayesian incentive compatible for neutral priors and it always outputs proportional allocations (Theorem 8). Moreover, IA can be executed in polynomial time for piecewise constant density functions.

Theorem 8. The INCREMENTALACCOMMODATION mechanism is Bayesian incentive compatible for neutral product distributions, and always outputs proportional allocations.

At a high level, given reported preferences f1, f2, . . . , fn, IA operates as follows. Initially, the entire cake [0, 1] is allocated to agent 1. Other agents arrive one-by-one following the order 2, 3, . . . , n. Before the arrival of agent i, the entire cake is always allocated among the agents {1, 2, . . . , i - 1}; this allocation is denoted by X1,X2, . . . ,Xi-1. When agent i arrives, each agent j ∈ {1, 2, . . . , i - 1} cuts their piece of cake, Xj, into i pieces, C 1 j ,C 2 j , . . . ,C i j using the SPLITEQUALoperation (Subroutine ??) described below.

SplitEqual operation. Given a piece of cake X, a function f , and a number k, the SPLITEQUAL operation (see [Gkatzelis et al., 2023]) partitions X into pieces C 1 , C 2 , . . . , C k having equal sizes and equal values, i.e., |C 1 | = |C 2 | = . . . = |C k | and f(C 1 ) = f(C 2 ) = . . . = f(C k ). Note that this operation can always be performed given "any" density function f and k > 1 since the existence of such a split is directly implied by the existence of a perfect partition. 8 Specifically, if we consider k density functions where the first function, y1(X) = |X| while the other k - 1 density functions are f, then a perfect partition C 1 , C 2 , . . . , C i of X -which always exists - will satisfy the two required conditions of equal value (since f(C r ) = f(C s ) for all r, s ∈ [i]) and equal size (since |C r | = y1(C r ) = y1(C s ) = |C s | for all r, s ∈ [k]). The SPLITEQUAL operation can be efficiently performed for piecewise constant valuations by simply dividing each subinterval within X having a constant-value w.r.t. f into k pieces of equal size; the equal value condition will follow from the fact the subinterval being divided has a constant-value. Furthermore, it is known that a perfect partition can be computed efficiently for the significantly more general class of piecewise linear valuations [Chen et al., 2013], allowing for efficient execution of IA for this class of valuations as well.

8 [Alon, 1987] proved that given arbitrary density functions y1, y2, . . . , yn, there always exists a partition X1,X2, . . . ,Xn of [0, 1] such that yi(Xj) = 1/n for all i, j ∈ [n].

After performing the SPLITEQUAL operation, each agent j ∈ {1, . . . , i - 1} offers agent i one piece amongst C 1 j ,C 2 j , . . . ,C i j , and agent i picks the one that maximizes her value, as per the reported density function fi. The resulting allocation, after the arrival of the nth agent, is then returned as the final allocation. In Lemma 8, we show that IA is BIC for neutral priors. In Lemma 9, we show that IA always outputs proportional allocations. The proof of Lemma 9 resembles a proof of [Fink, 1964] wherein proportionality is established for a similar recursive cake-cutting algorithm. All proofs of this section appear in the full version [Gkatzelis et al., 2023].

Mechanism 1: INCREMENTALACCOMMODATION

Lemma 7. Let X′j , Xj be the pieces of cake that agent j is allocated at the beginning and the end of iteration t, respectively, for some 1 ≤ j < t ≤ n. 9 Then, for any valuation function ˆ f, the expected value of ˆ f(Xj) is equal to t-1 t · ˆ f(X′j ), where the expectation is over the randomness of the valuation function of agent t, f ∗ t , drawn from a neutral prior D. Formally, E f ∗ t ∼D[ ˆ f(Xj)] = t-1 t · ˆ f (X′j ).

Now using Lemma 7, we will show that IA is Bayesian incentive compatible for neutral priors.

Lemma 8. The INCREMENTALACCOMMODATION is Bayesian incentive compatible with respect to product distributions that are neutral.

Proof Sketch. At a high level, we show that if agent i has piece Xi i after her arrival, then, eventually, in the final allocation, her utility, as per her true valuation f ∗ i , will be proportional to f ∗ i (Xi i ). Specifically, let Xn i be the piece that agent i has at the end of the mechanism's execution. Through repeated applications of Lemma 7 we prove that f ∗ i (Xn i ) = in ·f ∗ i (Xi i ) for any reported valuation function fi. Therefore, it suffices to prove that truthfully reporting f ∗ i maximizes f ∗ i (Xi i ).

The following lemma proves that IA outputs proportional allocations.

Lemma 9. The INCREMENTALACCOMMODATION mechanism outputs proportional allocations.

Combining Lemmas 8 and 9 implies Theorem 8.

9 Note that Xj is a random variable which depends on the valuation function of agent t, f ∗ t , drawn fromD.

Acknowledgements

Alexandros Psomas and Paritosh Verma are supported in part by the NSF CAREER award CCF-2144208, a Google Research Scholar Award, and a Google AI for Social Good award. Vasilis Gkatzelis and Xizhi Tan are partially supported by the NSF CAREER award CCF-2047907.