Truthful Fair Mechanisms for Allocating Mixed Divisible and Indivisible Goods

1 Introduction

Fair allocation problem considers how to fairly allocate scarce resources among interested agents (see excellent books or surveys by, e.g., [Brams and Taylor, 1995; Robertson and Webb, 1998; Moulin, 2019; Suksompong, 2021; Amanatidis et al., 2022]). This problem has gained substantial attentions in various fields including computer science, mathematics, and economics, due to the ubiquity in numerous real-world scenarios (e.g., school choices [Abdulkadiro˘glu et al., 2005], course allocations [Budish and Cantillon, 2012], and allocating computational resources [Ghodsi et al., 2011]).

The literature of fair allocation problem can be categorized by the type of resources being allocated. The first line of work studies the allocation of divisible goods, where the famous fairness criterion envy-freeness has been extensively studied [Foley, 1967; Aziz and Mackenzie, 2016]. In an envy-free allocation, each agent weakly prefers her own bundle than any other agent's bundle. The second group studies the allocation of indivisible goods, in which an envy-free allocation may fail to exist. A common practice to circumvent the issue is to consider relaxed notions such as envyfreeness up to one good (EF1) in which agent i's envy towards agent j could be eliminated if we (hypothetically) remove a good in agent j's bundle [Lipton et al., 2004; Budish, 2011].

In addition to fairness, truthfulness is an important consideration, given that agents report their private preferences over the resources. Roughly speaking, a mechanism is said to be truthful if each agent cannot benefit by misreporting her preference. The truthfulness aspect of fair allocation has been addressed in a number of recent papers, e.g., [Bogomolnaia and Moulin, 2004; Caragiannis et al., 2009; Mossel and Tamuz, 2010; Maya and Nisan, 2012; Kurokawa et al., 2013; Aziz and Ye, 2014; Brˆanzei and Miltersen, 2015; Li et al., 2015; Amanatidis et al., 2016; Menon and Larson, 2017; Bei et al., 2017; Bei et al., 2020]. When the resource to be allocated is a cake (i.e., a heterogeneous divisible good), the seminal work by [Chen et al., 2013] designed the first truthful envy-free mechanism when each agent's valuation is piecewise-uniform. On the other hand, very recently, [Bu et al., 2023] showed that for piecewise-constant valuations (which is a more general type of valuation functions than piecewise-uniform functions), there does not exist a (deterministic) truthful and envy-free mechanism. For indivisible goods setting, [Amanatidis et al., 2017] provided a characterization of truthful mechanisms for two agents, and further showed that truthfulness and EF1 are incompatible even for two agents and five indivisible goods. This negative result, however, does not hold any more for some restricted cases. With binary valuations, [Halpern et al., 2020] and [Babaioff et al., 2021] independently designed truthful and EF1 mechanisms by using maximum Nash welfare with lexicographic tie-breaking.

The aforementioned results paved the way for understanding the interplay between truthfulness and fairness for the fair allocation problem with either divisible or indivisible goods. However, when the resources contain a mixture of both, the study of designing truthful and fair allocation mechanisms is mostly absent, which is our focus in this paper. The only exception we know of is the work by [Goko et al., 2022]. They concerned indivisible goods allocation and designed a truthful and fair mechanism that achieves envy-freeness by subsidizing each agent with at most 1, the maximum marginal value of each good for each agent.

We adopt a different perspective than that of [Goko et al., 2022]. To be more specific, in our setting, the divisible and indivisible goods to be allocated are both fixed in advance [Bei et al., 2021a; Bei et al., 2021b; Bhaskar et al., 2021; Lu et al., 2023; Nishimura and Sumita, 2023]. In a setting with mixed divisible and indivisible goods (mixed goods for short), [Bei et al., 2021a] proposed a new fairness notion called envy-freeness for mixed goods (EFM) that generalizes both envy-freeness and EF1, and showed constructively that an EFM allocation always exists for any number of agents. Can we go one step further by designing truthful and EFM mechanisms when allocating mixed goods?

1.1 Our Results

We study the problem of designing truthful and EFM mechanisms when allocating mixed divisible and indivisible goods to agents who have additive valuations over the goods. To the best of our knowledge, this is the first work examining the compatibility of truthfulness and EFM. Two variants of EFM are considered in this paper, and we use EFM≥0 and EFM>0 to distinguish them (see Section 2 for their formal definitions). Intuitively speaking, EFM≥0 requires that the envy-free criterion is imposed even if the envied bundle contains a positive amount of divisible goods and the EF1 criterion is used otherwise. Slightly differently, EFM>0 only requires to impose the envy-free criterion if the envied bundle contains divisible goods with positive value. It can be verified that EFM≥0 implies EFM>0. While in the following we mostly present our results regarding to EFM>0, some of the results can be extended to the case of EFM≥0.

We start by giving in Section 3 a strong impossibility result showing that truthfulness and EFM>0 are incompatible even if there are only two agents and there are a single indivisible good and a single divisible good. Since we can normalize the valuations so that agents' valuations on the indivisible good are 0 or 1, as a corollary to the impossibility result, truthfulness and EFM>0 are incompatible for two agents with binary valuations on indivisible goods. Truthfulness and EFM>0, however, are compatible if we further restrict the expressiveness of agents' valuations on the divisible goods.

First, in Section 4, we design a truthful and EFM>0 mechanism when agents have binary valuations over indivisible goods and an identical valuation (not necessarily binary) over a single divisible good. In addition, the allocations output by our mechanism satisfy some nice efficiency properties including leximin and Maximum Nash welfare (MNW). Next, in Section 5, we consider the case where agents have binary valuations over all the goods. Specifically, we design truthful and EFM>0 mechanisms when (i) there are two agents (and an arbitrary number of goods), or (ii) the mixed goods consist of an arbitrary number of indivisible goods and a single divisible good. Technically speaking, in general, our mechanisms first make use of the truthful and EF1 mechanism of [Halpern et al., 2020] to allocate the (binary) indivisible goods, and next design different methods to allocate the divisible good(s) in the three different scenarios described above.

2 Preliminaries

Let [s] := {1, . . . , s}. We use N = [n] to denote the set of n agents. The set of the goods is denoted by (G,D), where G = {g1, . . . , gm} is the set of m indivisible goods and D = {d1, . . . , dm} is the set of m divisible goods. Each divisible good is homogeneous, meaning that an agent's value on each divisible good only depends on the fraction of this divisible good allocated to her. (We will formally define the valuations of the agents later.) Denote by A = (A1, . . . ,An) an allocation, where we assign bundle Ai to agent i. Each Ai is composed by a pair (Gi, xi), where Gi is a subset of the indivisible goods allocated to agent i and xi = (xi1, . . . , xim) specifies how divisible goods are allocated to agent i-specifically, xik denotes the fraction of (homogeneous) divisible good dk allocated to agent i. Naturally, an allocation A = ((G1, x1), . . . , (Gn, xn)) must satisfy that (G1, . . . ,Gn) is a partition of G and that ∑ni=1 xik = 1 for each k = 1, . . . ,m (in particular, we have assumed each divisible good has 1 unit of amount).

We assume that each agent i ∈ N has an additive valuation function vi and call (v1, . . . , vn) a valuation profile. That is, agent i's value on a bundle (Gj, xj) is given by vi(Gj, xj) = ∑gk∈Gj vi(gk) + ∑mk=1 xjk · vi(dk ), where vi(gk) is agent i's value on the indivisible good gk and vi(dk ) is agent i's value on the divisible good dk . We slightly abuse the notation by letting vi(Gj) = ∑gk∈Gj vi(gk) and vi(xj) = ∑mk=1 xjk · vi(dk ). We say that agents' valuations are binary if vi(gk) ∈ {0, 1} and vi(dk ) ∈ {0, 1} for every i, k and k. Correspondingly, we say that agents have binary valuations on indivisible goods if vi(gk) ∈ {0, 1} for every i and k and agents have binary valuations on divisible goods if vi(dk ) ∈ {0, 1} for every i and k.

An allocation is envy-free if each agent believes (based on her own valuation) her allocated bundle is weakly more valuable than that of every other agent's. In our case with mixed goods, this means vi(Gi, xi) ≥ vi(Gj, xj) holds for every agents i and j. An envy-free allocation may not exist even if there are only indivisible goods (i.e., D = ∅). For allocating only indivisible goods, a commonly adopted relaxation of envy-freeness is envy-freeness up to one item (EF1), and it is well-known that an EF1 allocation always exists [Lipton et al., 2004; Budish, 2011].

Definition 2.1 (EF1). For D = ∅, given a valuation profile (v1, . . . , vn), an allocation (G1, . . . ,Gn) is EF1 if for any pair of i, j ∈ N, there exists a good g ∈ Gj such that vi(Gi) ≥ vi(Gj \ {g}).

With mixed goods, we adopt the fairness notion called envy-freeness for mixed goods (EFM) [Bei et al., 2021a]. There are two variants of EFM, and we use EFM≥0 and EFM>0 to distinguish them. As we will see shortly, EFM≥0 implies EFM>0. We start by presenting the intuition of EFM>0: For any pair of agents i, j ∈ N, agent i should not envy agent j, as stated in Point 2 of Definition 2.2 below, with the exception that the divisible part allocated to agent j is worthless to agent i, in which case the EF1 condition holds for the indivisible part (see Point 1 of Definition 2.2).

Definition 2.2 (EFM>0). Given a valuation profile (v1, . . . , vn), an allocation ((G1, x1), . . . , (Gn, xn)) is EFM>0 if the followings hold for any pair of i, j ∈ N.

1. If vi(xj) = 0 and Gj ̸= ∅, then there exists a good g ∈ Gj such that vi(Gi, xi) ≥ vi(Gj \ {g}, xj).
2. Otherwise, vi(Gi, xi) ≥ vi(Gj, xj).

EFM≥0, on the other hand, imposes envy-free condition as long as agent j's bundle has any positive amount of divisible goods, even if agent i values the divisible part at 0:

Definition 2.3 (EFM≥0). Given a valuation profile (v1, . . . , vn), an allocation ((G1, x1), . . . , (Gn, xn)) is EFM≥0 if the followings hold for any pair of i, j ∈ N.

1. If xj = 0 and Gj ̸= ∅, then there exists a good g ∈ Gj such that vi(Gi, xi) ≥ vi(Gj \ {g}, xj).
2. Otherwise, vi(Gi, xi) ≥ vi(Gj, xj).

It is easy to see that EFM≥0 implies EFM>0. It also directly follows from the above definitions that when there are only indivisible goods (i.e., D = ∅), EFM>0 and EFM≥0 reduce to EF1; when there are only divisible goods (i.e., G = ∅), EFM>0 and EFM≥0 reduce to envy-freeness.

A mechanism is a function M that maps the set of n valuation functions (v1, . . . , vn) to an allocation ((G1, x1), . . . , (Gn, xn)). We only consider deterministic mechanisms in this paper. In the game-theoretical setting, each agent i submits a valuation v′i to M which may or may not be her true valuation vi. A mechanism M is EFM>0/EFM≥0 if, upon receiving every input (v′1 , . . . , v′n ), it outputs an allocation that is EFM>0/EFM≥0 w.r.t. (v′1 , . . . , v′n ). A mechanismM is truthful if it is each agent i's dominant strategy to truthfully report her valuation vi. Formally, let vi be the true valuation function of an arbitrary agent i and v′i be an arbitrary valuation function, for any n-1 valuation functions v1, . . . , vi-1, vi+1, . . . , vn of the remaining n-1 agents, we have vi(Gi, xi) ≥ vi(G′i , x′i ), where (Gi, xi) is the bundle allocated to agent i byMwhen receiving the input (v1, . . . , vi-1, vi, vi+1, . . . , vn) and (G′i , x′i ) is the bundle allocated to agent i byMwhen receiving the input (v1, . . . , vi-1, v′i , vi+1, . . . , vn).

We make the standard free-disposal assumption, see, e.g., [Chen et al., 2013; Bei et al., 2017; Halpern et al., 2020], which assumes that a good gk (resp., dk ) is discarded by the mechanism if vi(gk) = 0 (resp., vi(dk ) = 0) for all i ∈ N. Without this assumption, we may run into uninteresting technicality. This discussion along with all ommitted proofs can be found in the full version of our paper [Li et al., 2023].

2.1 MaximumNashWelfare and Leximin

We now proceed to review the concepts and some properties of Maximum Nash Welfare (MNW) allocations and leximin allocations, which will be useful in our paper.

The definitions of MNW and leximin allocations apply to general fair division settings. For each i ∈ [n], if we are only allocating indivisible goods, then Ai = Gi; if we are only allocating divisible goods, then Ai = xi; for mixed indivisible and divisible goods, Ai = (Gi, xi).

Definition 2.4 (MNW). Given a valuation profile (v1, . . . , vn), an allocation (A1, . . . ,An) is a Maximum Nash Welfare (MNW) allocation if it first maximizes the number of the agents receiving positive values, i.e.,

|{i ∈ [n] : vi(Ai) > 0}|, and, subject to this, maximizes the product of the positive utilities, i.e., ∏i:vi(Ai)>0 vi(Ai).

When allocating only divisible goods, an MNW allocation is always envy-free [Varian, 1974]. When allocating only indivisible goods, an MNW allocation is always EF1 [Caragiannis et al., 2019]. However, with mixed goods, an MNW allocation may not be EFM>0 [Bei et al., 2021a].

Definition 2.5 (Leximin). Given two vectors s1, s2 ∈ Rn , let s′1 and s′2 be the vectors obtained by sorting s1 and s2 in ascending order respectively. We say that s1 leximindominates s2 if there exists i ∈ [n] such that s′1 and s′2 are identical for the first i - 1 entries and the i-th entry of s′1 is greater than the i-th entry of s′2 . Given a valuation profile (v1, . . . , vn), an allocation (A1, . . . ,An) is a leximin allocation if (v1(A1), . . . , vn(An)) is maximum in the total order induced by leximin-domination among all allocations.

In other words, a leximin allocation maximizes the minimum among the agents' utilities; among all such allocations, it considers those maximizing the second smallest utility, and so on.

When allocating indivisible goods with binary valuations, [Aziz and Rey, 2020] and [Halpern et al., 2020] showed the equivalence of Maximum Nash Welfare (MNW) allocations and leximin allocations. In addition, [Halpern et al., 2020] showed that the mechanism that outputs the MNW/leximin allocation with a consistent lexicographic tie-breaking rule is truthful. For the purpose of our paper, we state Halpern et al.'s mechanism (referred to as MNWtie ) below.

Theorem 2.6 ([Halpern et al., 2020], MNWtie ). For allocating only indivisible goods with binary valuations, there exists a truthful mechanism that always outputs an allocation that is both MNW and leximin.

3 General Impossibility Results

Unfortunately, truthfulness and EFM>0 are incompatible in general. In this section, we prove that there does not exist a truthful and EFM>0 mechanism even under the very restricted settings where there are only one indivisible good and one divisible good and there are only two agents.

Our impossibility result for mixed divisible and indivisible goods holds for a minimum number of agents (which is 2) and a minimum number of goods (which is 2). This is in contrast with [Amanatidis et al., 2017]'s 2-agent-5-good impossibility result for only indivisible goods.

Theorem 3.1. There does not exist a truthful and EFM>0 (and thus EFM≥0) mechanism even when there are only two agents and the set of goods consists of one indivisible good and one divisible good.

Proof. It suffices to prove the statement for EFM>0. Consider the instance with two agents {1, 2}, one indivisible good and one divisible good. Both agents have value 1 on the indivisible good, and have value a and b on the divisible good, where b > a > 1.

Firstly, we prove that all the EFM>0 allocations must allocate the indivisible good to agent 1. Suppose for the sake of contradiction that the indivisible good is allocated to agent 2.

To guarantee EFM>0, agent 2 must get at least a fraction b-1 2b from the divisible good in order to not envy agent 1, and agent 2 must get at most a fraction of a-1 2a from the divisible good in order to avoid that agent 1 envies agent 2. This is impossible as a-1 2a < b-1 2b .

Therefore, the possible EFM>0 allocations can be described as follows. Agent 1 receives the indivisible good and a fraction x of the divisible good, and agent 2 receives a fraction 1 - x of the divisible good. For the reasons similar as above, we must have a-1 2a ≤ x ≤ b-1 2b to guarantee EFM>0. If the mechanism outputs an allocation with x = a-1 2a , agent 1 can misreport her valuation by increasing a, which increases agent 1's received value as x increases. If the mechanism outputs an allocation with x > a-1 2a , agent 2 can misreport her valuation by decreasing b so that a-1 2a < b-1 2b < x. In this case, x will decrease and agent 2 receives more value.

When there is only one indivisible good and one divisible good, we can assume w.l.o.g. that agents' valuations on the indivisible good are binary (as we did in the proof of Theorem 3.1) or agents' valuations on the divisible good are binary. This is because we can normalize the valuations of the agents. Thus, Theorem 3.1 implies the following corollary.

Corollary 3.2. There does not exist a truthful and EFM>0 (and thus EFM≥0) mechanism even when there are two agents and agents have binary valuations on either the indivisible goods or the divisible goods.

As a remark, although we focus on deterministic mechanisms here, Theorem 3.1 and Corollary 3.2 continue to hold for randomized mechanisms (that are universally EFM>0 and truthful in expectation). 1 The proof is almost the same: We must allocate the indivisible good to agent 1 in order to guarantee universally EFM>0, and x in the proof becomes the expected fraction of the divisible good allocated to agent 1.

The strong impossibility results suggest that truthfulness and EFM>0 may only be compatible in more restrictive settings. We confirm our intuitions in the affirmative in the following sections by considering (1) the setting with a single divisible good of identical value to all agents and multiple indivisible goods on which agents have binary valuations (Section 4), and (2) the setting where agents' valuations are binary for both indivisible and divisible goods (Section 5).

4 Binary Valuations on Indivisible Goods and Identical Valuation on Single Divisible Good

This section considers the setting where agents' valuations on indivisible goods are binary and there is one divisible good on which agents have an identical valuation. This describes the natural scenario where we are allocating a set of indivisible goods and some amount of money. Here, the divisible good is just a sum of money, and an agent's value on each indivisible good is described by the amount of money the agent is willing Mechanism 1 A truthful EFM≥0 mechanism for binary valuations on indivisible good and identical valuation on a single divisible good

1 Loosely speaking, universally EFM>0 mechanisms randomize over deterministic EFM>0 mechanisms. A randomized mechanism is said to be truthful in expectation if misreporting a valuation function cannot increase the expected utility of an agent.

• 1: use MNWtie (Theorem 2.6) to compute an MNW/leximin allocation (G1, . . . , Gn) of G 2: initialize xi ← 0 for each agent i 3: while y := 1 - ∑ni=1 xi > 0: 4: let T1 = argmini∈[n]{vi(Gi, xi)} 5: ∆←∞ 6: if T1 ̸= [n] then 7: let T2 = arg mini∈[n]\T1 {vi(Gi, xi)} 8: ∆← vj(Gj, xj) - vi(Gi, xi) for i ∈ T1, j ∈ T2 9: for each i ∈ T1, xi ← xi +min{ ∆u , y |T1| }
• 10: return allocation ((G1, x1), . . . , (Gn, xn))

to pay for the good. We will see that there exists a truthful and EFM≥0 (and thus EFM>0) mechanism under this setting.

For the ease of notation, we will use x1, . . . , xn to denote the fractions of the (unique) divisible good allocated to the n agents. Thus, each agent's allocated share is denoted by (Gi, xi). We will use u to denote each agent's value on the (unique) divisible good.

Our mechanism is shown in Mechanism 1. The mechanism first allocates the indivisible goods using MNWtie (Theorem 2.6) and then iteratively allocates the divisible good. In each iteration, the mechanism identifies a set T1 of agents who receive minimum values in the current partial allocation. The mechanism then attempts to compensate agents in T1 with some fraction of the unallocated divisible good. This is done by a "water-filling" process: We allocate the divisible good to the agents in T1 at an equal rate, until the divisible good is fully allocated, in which case the mechanism terminates, or until the value received by each agent in T1 reaches the second minimum value received among all agents (i.e., the value received by an agent in T2), in which case the mechanism proceeds to the next iteration.

Theorem 4.1. Mechanism 1 is EFM≥0 and truthful. Moreover, it always outputs allocations that are leximin and MNW.

The following three subsections aim to prove this theorem.

4.1 Mechanism 1 Is EFM≥0

We first present some simple yet important observations.

Proposition 4.2. Let ((G1, x1), . . . , (Gn, xn)) be the allocation output by Mechanism 1. The followings hold.

1. For any agent i, vi(Gi, xi) = |Gi| + u · xi.
2. For any agents i and j, vi(Gi, xi) ≥ vj(Gi, xi).

Proof. Since agents have binary valuations on indivisible goods and the identical valuation u on the unique divisible good, we have vj(Gi, xi) ≤ |Gi| +u · xi for any agents i and j. Therefore, Point 1 implies Point 2, and it remains to show Point 1. To show Point 1, notice that vi(Gi, xi) ̸= |Gi|+u·xi is only possible when there exists g ∈ Gi such that vi(g) = 0. Suppose this is the case for the sake of contradiction. If there exists another agent j with vj(g) = 1, then moving g from i's bundle to j's increases the Nash welfare, which contradicts to that (G1, . . . ,Gn) is an MNW allocation. If the good g is worth 0 to all agents, then g is discarded by the free-disposal assumption, which contradicts to g ∈ G1.

Lemma 4.3. Mechanism 1 always outputs EFM≥0 (and thus EFM>0) allocations.

Proof. We will prove by induction that the partial allocation is EFM≥0 after each while-loop iteration. For the base step, the MNW allocation (G1, . . . ,Gn) for the indivisible goods is EF1 by [Caragiannis et al., 2019], and EFM≥0 is satisfied since the allocation of the divisible good has not been started. For the inductive step, suppose the partial allocation ((G1, x1), . . . , (Gn, xn)) is EFM≥0 before a while-loop iteration. After one while-loop iteration, each agent in T1 receives an extra fraction z := min{ ∆u , y |T1| } of the divisible good. It suffices to show that j does not envy i for any agent i ∈ T1 and any other agent j. We discuss two cases: j ∈ T1

and j /∈ T1.

If j ∈ T1, we have vj(Gj, xj) = vi(Gi, xi) ≥ vj(Gi, xi) before the execution of this while-loop iteration, where the first equality is due to our definition of T1 in Mechanism 1 and the second inequality is due to Point 2 of Proposition 4.2. This implies that agent j does not envy agent i before the while-loop iteration. Agent j will not envy agent i after the while-loop iteration, as both agents receive the same amount z of the divisible good, which is worth the same value u · z to both agents.

If j /∈ T1, we have vj(Gj, xj) ≥ ∆+ vi(Gi, xi) ≥ ∆+ vj(Gi, xi) before the execution of this while-loop iteration, where, again, the first equality is due to our definition of T1 in Mechanism 1 and the second inequality is due to Point 2 of Proposition 4.2. This implies that agent j will not envy agent i after the while-loop iteration if the portion of the divisible goods allocated to agent i is worth at most ∆. This is true as u · z ≤ u · ∆u =∆.

4.2 Mechanism 1 Is Truthful

We first define a type of mechanisms called water-filling mechanisms. A water-filling mechanism starts from an allocation (G1, . . . ,Gn) of the indivisible goods and then proceeds to allocate the unique divisible good by the "waterfilling process" defined by the while-loop in Mechanism 1. Our Mechanism 1 is a particular water-filling mechanism by specifying that the allocation of the indivisible goods (G1, . . . ,Gn) is output by MNWtie .

Definition 4.4. Given a valuation profile (v1, . . . , vn), an allocation ((G1, x1), . . . , (Gn, xn)) satisfies the water-filling property if

1. for any two agents i and j with xi > 0 and xj > 0, we have vi(Gi, xi) = vj(Gj , xj), and
2. for any two agents i and j with xi = 0 and xj > 0, we have vi(Gi, xi) ≥ vj (Gj , xj ).

It is straightforward to check that the allocation output by any water-filling mechanism satisfies the water-filling property. Given a valuation profile v = (v1, . . . , vn) and an allocation A = ((G1, x1), . . . , (Gn, xn)) satisfying the water-filling property, we define the potential φ(A, v) by the "height of the water level": φ(A, v) = vi(Gi, xi), where i is an arbitrary agent with xi > 0. When xi = 0 for all i ∈ [n], φ(A, v) = mini∈[n] vi(Gi).

We will first prove a proposition, Proposition 4.7, which follows from that an MNW allocation of indivisible goods with binary valuations is always Lorenz dominating [Babaioff et al., 2021]. Before stating the proposition, we will first state Babaioff et al.'s result.

Definition 4.5. Given a valuation profile (v1, . . . , vn), an allocation (A1, . . . ,An) is Lorenz dominating if, for any k ∈ [n], the sum of the k smallest values of v1(A1), . . . , vn(An) is weakly larger than the sum of the k smallest values of v1(A′1 ), . . . , vn(A′n ) for any allocation (A′1 , . . . , A′n ).

A Lorenz dominating allocation may not exist. However, if it does, it is easy to see that a Lorenz dominating allocation is always leximin. [Babaioff et al., 2021] (implicitly) proved the following theorem.

Proposition 4.6 ([Babaioff et al., 2021]). Consider the allocation of indivisible goods (i.e., D = ∅). For any binary valuation profile on indivisible goods, an MNW/leximin allocation is Lorenz dominating.

In particular, Halpern et al.'s mechanism MNWtie always outputs Lorenz dominating allocations. We then get the following proposition from the Lorenz domination.

Proposition 4.7. Fix a valuation profile (v1, . . . , vn). Mechanism 1 outputs an allocation A that maximizes the potential φ(A, v) among all allocation satisfying the water-filling property.

Lemma 4.8. Mechanism 1 is truthful.

Proof. Let M be Mechanism 1. Consider a valuation profile v = (v1, . . . , vn) and suppose agent 1 misreports her valuation to v′1 . Let v′ be the valuation profile (v′1 , v2, . . . , vn). Let A = ((G1, x1), . . . , (Gn, xn)) be the allocation output by M when agent 1 reports truthfully, and let A′ = ((G′1 , x′1 ), . . . , (G′n , x′n )) be the allocation output by M when agent 1 reports v′1 . By the truthfulness of MNWtie , we have v1(G1) ≥ v1(G′1 ). Let A† = ((G′1 , x†1 ), . . . , (G′n , x†n )) be the allocation obtained by applying the water-filling process (the while-loop in M) to the start-up allocation (G′1 , . . . ,G′n ) with the true valuation profile v considered. Both A and A† satisfy the water-filling property w.r.t. v, and A′ satsifies the water-filling property w.r.t. v′ .

If x′1 = 0, we have v1(G1, x1) ≥ v1(G1) ≥ v1(G′1 ) = v1(G′1 , x′1 ), and the truthfulness of M holds trivially. Thus, we assume x′1 > 0 from now on.

By Proposition 4.7, φ(A, v) ≥ φ(A† , v). We have v1(G1, x1) ≥ φ(A, v) according to the definition of the potential function φ. To conclude that M is truthful, it suffices to show that φ(A† , v) ≥ v1(G′1 , x′1 ).

Since we have assumed x′1 > 0, v′1 (G′1 , x′1 ) = φ(A′ , v′ ). Let δ = v′1 (G′1 , x′1 ) - v1(G′1 , x′1 ). It then remains to show that φ(A† , v) + δ ≥ φ(A′ , v′ ).

By Point 1 of Proposition 4.2, we have v′1 (g) = 1 for each g ∈ G′1 . Moreover, it is clear that δ equals to the number of goods g in G′1 with v1(g) = 0 and v′1 (g) = 1. In particular, δ ≥ 0. Now, consider the two water-filling processes corresponding to φ(A† , v) and φ(A′ , v′ ). When the "height of the water level" reaches φ(A† , v), the first process terminates, while an additional amount δ of water is yet to be split among one or more agents in the second process. Thus, the "height of the water level" for the second process can be further increased by at most δ. Therefore, φ(A† , v) + δ ≥ φ(A′ , v′ ).

4.3 Leximin andMNW

We show that the allocation output by Mechanism 1 is Lorenz dominating.

Proposition 4.9. Given a valuation profile v = (v1, . . . , vn), the allocation A = ((G1, x1), . . . , (Gn, xn)) output by Mechanism 1 is Lorenz dominating.

Proof. Suppose there is an allocation A′ = ((G′1 , x′1 ), . . . , (G′n , x′n )) such that A does not Lorenz dominate A′ . Let a1, . . . , an and b1, . . . , bn be orderings of the n agents such that va1 (Ga1 , xa1 ) ≤ · · · ≤ van (Gan , xan ) and vb1 (G′b1 , x′b1 ) ≤ · · · ≤ vbn (G′bn , x′bn ), respectively. Let k be the smallest index such that

We can first assume w.l.o.g. that A′ satisfies the waterfilling property. If not, we can adjust A′ by applying the water-filling process to the start up allocation (G′1 , . . . ,G′n ). It is easy to see that the adjusted allocation Lorenz dominates the original allocation.

By Proposition 4.7, we have φ(A, v) ≥ φ(A′ , v). Let ℓ and ℓ′ be the numbers of agents with xi > 0 and x′i > 0, respectively. We must have k > ℓ′ . Otherwise, ∑ki=1 vbi (G′bi , x′bi ) = k · φ(A′ , v) ≤ k · φ(A, v). Since φ(A, v) is a lower bound to each vi(Gi, xi), Equation (1) cannot be true. Since k > ℓ′ , we have

We consider two cases: ℓ ≤ k and ℓ > k. If ℓ ≤ k, we must have ∑ki=1 vai (Gai , xai ) = u + ∑ki=1 vai (Gai ). This, together with Equations (1) and (2), implies ∑ki=1 vai (Gai ) < ∑ki=1 vbi (G′bi ). However, this contradicts to Proposition 4.6. If ℓ > k, we have vai (Gai , xai ) = φ(A, v) = vak (Gak , xak ) < vbk (G′bk , x′bk ) ≤ vbi (G′bi , xb′i ) for each i = k + 1, . . . , ℓ, where the only strict inequality in the middle is due to our assumption that k is the smallest index. This implies Equation (1) continues to hold if we summing over the first ℓ terms instead of the first k terms:

Since ℓ > k > ℓ′ , we have ∑ℓi=1 vai (Gai , xai ) = u + ∑ℓi=1 vai (Gai ) and ∑ℓi=1 vbi (G′bi , x′bi ) = u + ∑ℓi=1 vbi (G′bi ). These, together with Equation (3), give a contradiction to Proposition 4.6 again.

Mechanism 2 A truthful EFM>0 mechanism for binary valuations on both divisible and indivisible goods with two agents

• 1: use MNWtie (Theorem 2.6) to compute an MNW/leximin allocation (G1, G2) of G
• 2: initialize xi ← 0 for each agent i ∈ {1, 2}
• 3: if v1(G1) ̸= v2(G2) then
• 4: let i∗ = argmini∈{1,2}{vi(Gi)}
• 5: if ∃¯ k∗ ∈ [ ¯m] s.t. vi∗(d¯k∗) = 1 then xi∗¯k∗ ← 1
• 6: for each ¯ k = 1 to ¯mwith ¯ k ̸= ¯ k∗ do
• 7: if v1(d¯k) = v2(d¯k) = 1 then x1¯k ← 0.5, x2¯k ← 0.5
• 8: else
• 9: if v1(d¯k) = 1 then x1¯k ← 1
• 10: if v2(d¯k) = 1 then x2¯k ← 1
• 11: return allocation ((G1, x1), (G2, x2))

Lorenz domination leads to the following lemma.

Lemma 4.10. Mechanism 1 always outputs allocations that are both leximin and MNW.

5 Binary Valuations for Both Divisible and Indivisible Goods

In this section, we focus on the setting where agents' valuations on mixed goods are binary. We start from the simplest case where there are only two agents. We first show that no deterministic mechanism can ensure truthfulness and always output an MNW/leximin allocation. We illustrate this by Example 5.1. This is in sharp contrast to Halpern et al.'s mechanism MNWtie and Mechanism 1.

Example 5.1. Consider the instance with 2 agents and an indivisible good g1 and two divisible goods d1 and d2. We have v1(g1) = v2(g1) = 1. For d1, let v1(d1) = 1 and v2(d1) = 0; for d2, let v1(d2) = 0 and v2(d2) = 1.

In the allocation returned by a mechanism that can always output an MNW/leximin allocation, each agent i receives the corresponding divisible good di and one of them also receives the indivisible good g1. Without loss of generality, we assume agent 1 receives g1 and d1. If the actual valuation of agent 1 is positive towards all three goods and she reports her valuation truthfully, she will only receive d1 and a half of d2 to achieve an MNW/leximin allocation. Thus, she has an incentive to misreport the valuation we stated in the table to earn a benefit.

Remark 5.2. Even when allowing randomized mechanisms, we can also show there is no truthful mechanism that always outputs an MNW/leximin allocation with a general number of agents (where the proof can be found in the full version).

Such an example shows that directly returning an MNW allocation cannot work for our setting. Instead, we adopt the mechanism MNWtie (Theorem 2.6) for only indivisible goods and design a truthful mechanism which can always output an EFM>0 allocation when there are only two agents.

Mechanism 2 first allocates indivisible goods according to MNWtie . If the valuations of two agents over their own bundles are different, we can allocate one valuable divisible good to the one with a smaller value to eliminate the possible envy, if such a divisible good exists. Each remaining divisible good Mechanism 3 A truthful EFM>0 mechanism for binary valuations on indivisible goods and a single divisible good

• 1: use MNWtie (Theorem 2.6) to compute an MNW/leximin allocation (G1, . . . , Gn) of G 2: initialize xi ← 0 for each agent i ∈ [n] 3: let T = argmini∈[n]{vi(Gi)} 4: for each i ∈ T do 5: xi1 ← 1 |T | 6: return allocation ((G1, x1), . . . , (Gn, xn))

is allocated evenly to all the agents who value it positively. We have the following result for Mechanism 2:

Theorem 5.3. Mechanism 2 is EFM>0 and truthful.

Proof. We first show the output allocation A = (A1,A2) is EFM>0. Since the allocation (G1,G2) output by MNWtie is EF1, so it is also EFM>0. If v1(G1) = v2(G2), such an allocation is envy-free. If v1(G1) ̸= v2(G2), after Steps 45, either the present allocation is envy-free, or vi∗(D) = 0, which means the output allocation is always EFM>0 for agent vi∗ no matter how divisible goods are allocated. In the remaining steps, each divisible good is allocated evenly to the agents who positively value them, which will not destroy the envy-freeness. Hence the final allocation is EFM>0.

We next show Mechanism 2 is truthful. We assume we receive the allocation A = (A1, A2) given the true valuation profile (v1, v2) and the allocation A′ = (A′1 , A′2 ) when agent 1 misreports her valuation to v′1 .

Since the allocation of divisible goods after Step 6 is to evenly allocate all goods to the agents who value them, misreporting can make no benefit in this part. For Steps 4-5, the decision depends only on the valuations of the indivisible goods, there is also no gain from misreporting the valuations on divisible goods. So the only possible way to benefit is to misreport the valuations on indivisible goods.

As MNWtie is truthful, we get v1(G1) ≥ v1(G′1 ). The first case is when v1(G1) ≥ v1(G′1 ) + 1. By misreporting, the largest benefit is from the change of i∗ from 2 to 1 during Steps 4-5. Such benefit is upper bounded by 2 × 0.5 = 1, since agent 1 will receive half of this good if she values the allocated good positively and such a good is allocated after Step 6. Hence there is no need to misreport in this case.

For the second case where v1(G1) = v1(G′1 ), we first have v′1 (G′1 ) ≥ v1(G′1 ) since the leximin allocation with binary valuations. The benefit of the misreporting is also from the change of i∗ during Steps 4-5. If i∗ is 2 under (v1, v2) and does not exist under (v′1 , v2), then v2(G′2 ) = v′1 (G′1 ) ≥ v1(G′1 ) = v1(G1) > v2(G2), this violates the leximin property of (G1,G2) under (v1, v2). If i∗ is 2 under (v1, v2) and 1 under (v′1 , v2), the leximin property of (G1,G2) under (v1, v2) is also violated from the similar argument. Similar analysis also holds for the case where i∗ does not exist under (v1, v2) and is 1 under (v′1 , v2). Since all three cases which can benefit agent 1 cannot occur, misreporting the valuations has no benefit. Thus, this mechanism is truthful.

If we consider the setting with more than two agents, we can also design an EFM>0 and truthful mechanism for allocating indivisible goods and a single divisible good, which is shown in Mechanism 3. It is worth noting that, in this setting, agents value the divisible good at either 1 or 0, which is different from the setting in Section 4 where all agents have an identical value over the single divisible good. In this mechanism, after allocating all indivisible goods according to MNWtie , we allocate the only divisible good evenly to all agents with the smallest vi(Gi).

Theorem 5.4. Mechanism 3 is EFM≥0 and truthful.

Proof. Since MNWtie returns an EF1 allocation and the remaining of our mechanism is just to allocate the single divisible good evenly to agents with the smallest vi(Gi), no agent in T will envy others in T. Because there is only one divisible good, no agent in [n] \ T will envy the agents in T after allocating this good. Thus, the output allocation is EFM≥0.

We then prove Mechanism 3 is truthful. We assume we get the allocation A = (A1, . . . , An) given the true valuation profile (v1, . . . , vn), and the allocation A′ = (A′1 , . . . ,A′n ) when agent 1 misreports her valuation to v′1 .

From the truthfulness of MNWtie , we have v1(G1) ≥ v1(G′1 ). Since there is only one divisible good, there is no incentive to misreport if v1(G1) ≥ v1(G′1 )+1. We then consider the case where v1(G1) = v1(G′1 ). If agent 1 can benefit from misreporting, this means that after misreporting, agent 1 is in the set T at Step 3, and when agent 1 truthfully reports v1, either she is not in the set T or the size of the set T is larger than that after misreporting.

Since MNWtie is leximin, under binary valuations, we have v′1 (G′1 ) ≥ v1(G′1 ) = v1(G1). Because, after misreporting the valuation, agent 1 is in the set T which contains all agents with the smallest vi(Gi). Both two cases mentioned above violate the leximin property of the allocation (G1, . . . ,Gn) of G under the valuation (v1, . . . , vn). Thus, this mechanism is truthful.

Remark 5.5. This mechanism is no longer EFM≥0 and EFM>0 when there is more than one divisible good, because some envy may occur from the agent outside the set T to the agent in T after allocating multiple divisible goods.

6 Conclusion

In this paper, we have studied truthful and fair (i.e., EFM) mechanisms when allocating mixed divisible and indivisible goods. Our strong impossibility result shows that truthfulness and EFM are incompatible even if there are only two agents and two goods. We then designed truthful and EFM mechanisms in various restricted settings.

In future research, it would be intriguing to completely determine the compatibility between truthfulness and EFM when agents have binary valuations over all goods. Given by our impossibility result, another future direction is to consider weaker notions of truthfulness, e.g., maximin strategyproofness [Brams et al., 2006], not obviously manipulation (NOM) [Troyan and Morrill, 2020; Ortega and Segal-Halevi, 2022], and risk-averse truthfulness [Bu et al., 2023].

Acknowledgments

Shengxin Liu is the corresponding author. The research of Biaoshuai Tao was supported by the National Natural Science Foundation of China (Grant No. 62102252). The research of Shengxin Liu was partially supported by the National Natural Science Foundation of China (Grant No. 62102117), by the Shenzhen Science and Technology Program (Grant No. RCBS20210609103900003), and by the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2023A1515011188), and was partially sponsored by CCF-Huawei Populus Grove Fund (Grant No. CCFHuaweiLK2022005). Xinhang Lu was partially supported by ARC Laureate Project FL200100204 on "Trustworthy AI".