## Randomized Strategyproof Mechanisms with Best of Both Worlds Fairness and Efficiency

Ankang Sun ∗

Bo Chen †

## Abstract

We study the problem of mechanism design for allocating a set of indivisible items among agents with private preferences on items. We are interested in such a mechanism that is strategyproof (where agents' best strategy is to report their true preferences) and is expected to ensure fairness and efficiency to a certain degree. We first present an impossibility result that a deterministic mechanism does not exist that is strategyproof, fair and efficient for allocating indivisible chores. We then utilize randomness to overcome the strong impossibility. For allocating indivisible chores, we propose a randomized mechanism that is strategyproof in expectation as well as ex-ante and ex-post (best of both worlds) fair and efficient. For allocating mixed items, where an item can be a good (i.e., with a positive utility) for one agent but a chore (i.e., a with negative utility) for another, we propose a randomized mechanism that is strategyproof in expectation with best of both worlds fairness and efficiency when there are two agents.

Key words: multi-agent systems; resource allocation; mechanism design; strategyproof; randomization

## 1 Introduction

Resource allocation is a fundamental issue that has obtained significant attention in the intersection of operations research, economics and computer science (Brandt et al., 2016, Ibaraki and Katoh, 1988, Moulin, 2003). Among different types of resources, indivisible items stand out as a prominently studied model. This model has drawn substantial interest as it serves as a metaphor of real-world allocation problems, such as outpatient diagnostic tests scheduling (Zaerpour et al., 2017), school choice (Abdulkadiro˘lu and S¨nmez, 2003), order dispatching in ride-hailing platg o form (Qin et al., 2020) and conference paper assignment (Lian et al., 2018).

In most practical allocation problems, individual preferences are private. This necessitates allocation protocols to operate based on announced preferences. When participants are aware that declared preferences determine the outcome of the allocation, strategic behavior often comes into play, leading to misreports of true preferences for more favorable outcomes. False

∗ Department of Computing, Hong Kong Polytechnic University, China; ankang.sun@polyu.edu.hk †

Corresponding author: Warwick Business School, University of Warwick, UK; bo.chen@wbs.ac.uk

preferences significantly undermine outcomes if the allocation protocol is not designed to address such manipulation. Some recent studies have addressed such strategic behavior in supply chain management (Karaenke et al., 2020), production system (Norde et al., 2016) and project management (Chen and Hall, 2021).

To circumvent the challenge of strategic manipulation, an ideal allocation protocol should incentivize truthful reporting, making it the optimal strategy for individuals. Allocation protocols designed with this property are known as strategyproof mechanisms. After the seminal work of Nisan and Ronen (2001), a line of works focus on the model of indivisible items and strategyproof mechanisms (without money payment ) to achieve fair outcomes (Amanatidis et al., 1 2017, 2016, Bez´kov´ and Dani, 2005, Markakis and Psomas, 2011). a a Many argue that, in general, strategyproofness prohibits mechanisms from achieving fair or even approximately fair outcomes. In particular, for indivisible goods, Amanatidis et al. (2017) consider the notion of envy-free up to one item 2 (EF1) and show that EF1 and strategyproofness are incompatible even for two agents and five items when agents' valuations are additive. To escape from the strong impossibility result, follow-up studies have explored restricted preference domains, such as the binary margin where the marginal valuation of an item is either zero or one. These studies demonstrate that strategyproofness, fairness and efficiency can be achieved simultaneously under the setting of binary margin (Babaioff et al., 2021, Barman and Verma, 2022, Halpern et al., 2020).

The aforementioned positive results are mainly established in the context of allocating goods, items with positive utilities. However, in practical scenarios, the items to be allocated extend beyond goods to chores, which impose costs on individuals. The chore allocation scenario includes, but is not limited to, workload assignment in manufacturing industry (Pereira and Ritt, 2023), job scheduling (Etesami, 2022) and household chores division among family members (Igarashi and Yokoyama, 2023). Moreover, whether an item is a good or a chore is not only subjective but also agent dependent. For example, a pesticide may have a positive utility for a farmer who wants to protect his crops from pests, but a negative utility for a beekeeper who loses his bees due to the toxic chemicals. Such a setting is referred to as mixed items . For chores or mixed items, whether strategyproofness, efficiency and fairness can be achieved simultaneously is not well understood. In particular, an approach applied successfully in the setting of goods does not convert to chores (or mixed items) straightforwardly. Halpern et al. (Halpern et al., 2020) propose a fair, efficient and strategyproof mechanism for indivisible goods and additive valuations with a binary margin. The proposed mechanism relies on the allocation that maximizes the product of individuals' utilities, known as Nash welfare. The allocation with the maximum Nash welfare allocation is EF1 and Pareto optimal for goods (Caragiannis et al., 2019), while no (known) equivalent rule with fairness and efficiency guarantees for chores. This leads to our first research question:

1 When money transfer is either infeasible or illegal in practice.

2 No one envies another after hypothetically eliminating one good from the bundle of the latter.

For allocating chores or mixed items, whether strategyproofness, fairness and efficiency are compatible? In general or in a restricted preference domain?

Restricting preference domains is one approach to escape from strong impossibilities. Another potential avenue involves relaxing the requirement of (deterministic) strategyproofness to strategyproofness in expectation through lotteries. Informally, a randomized mechanism is considered strategyproof in expectation if every agent's expected utility is maximized when they truthfully reveal their preferences. For allocating indivisible items, achieving performance guarantees before realization (ex-ante) along with strategyproofness in expectation is not a hard task. For instance, consider a mechanism that selects an agent uniformly at random and assigns all items to that agent. This mechanism is strategyproof in expectation as reported preferences are ignored. In the allocation of such a mechanism, no agent prefers the bundle of another before realization. However, such a mechanism unlikely guarantees fairness or efficiency after realization (ex-post). An ideal randomized mechanism should have both ex-ante and ex-post performance guarantees, also referred to as the 'best of both worlds' (Akrami et al., 2023, Aziz et al., pear, Babaioff et al., 2022, Hylland and Zeckhauser, 1979). This then leads to our second research question:

For allocating chores or mixed items, whether strategyproofness in expectation, best of both worlds fairness and efficiency are compatible? In general or in a restricted preference domain?

## 1.1 Main results

This paper presents results in the realm of fair and efficient allocation mechanisms, particularly focusing on the allocation of (i) indivisible chores , where all items are chores for agents, and (ii) mixed items , where an item can be a good for one agent but a chore for another. In Section 3, we study deterministic mechanisms and present two impossibility results. We first examine the performance of the widely-studied mechanism, known as sequential picking, revealing that this allocation rule does not guarantee Pareto optimality. Then we establish an impossibility result for all deterministic mechanisms, which informally states that deterministic strategyproofness, equitability-based fairness notions and Pareto optimality are incompatible, even for additive valuations with a binary margin. Given this strong impossibility result, we relax deterministic strategyproofness to strategyproofness in expectation and concentrate on randomized mechanisms in the subsequent sections.

In Section 4, we consider randomized mechanisms and are concerned with allocation of indivisible chores. We focus on the k -restricted additive valuations, where a single item has k inherent values and the item's value for an agent is either from the k inherent values or 0. For 1-restricted additive valuations, we propose a randomized mechanism that is groupstrategyproof 3 in expectation and has best of both worlds fairness and efficiency guarantees.

3 No group of agents has an incentive to misreport.

We also show that fairness and efficiency guarantees of the proposed mechanism cannot be achieved simultaneously by any mechanism (without the requirement of strategyproofness) when valuations are k -restricted additive for all k ≥ 2. Moving on to Section 5, we consider the setting of mixed items and propose a randomized mechanism for two agents that is strategyproof in expectation. The proposed mechanism also guarantees best of both worlds fairness and efficiency.

## 1.2 Other related works

The study of strategyproof mechanisms with guaranteed properties dates back to Hylland and Zeckhauser (1979). Then investigating the existence of strategyproof mechanisms with desired properties was a central concern. Gale (1987) raises the question of whether we can find a 'nice' mechanism that satisfies strategyproofness, efficiency, and other distributional properties, simultaneously. A follow-up study Zhou (1990) partially answers Gale's conjecture and proves that in the problem of assigning n items to n agents, no mechanism can be strategyproof, Pareto optimal and symmetric 4 when n ≥ 3. Then P´ apai (2001b) studies the problem of allocating a single indivisible item to several agents without money transfer and examines possible extra properties that a strategyproof mechanism can have. In another study, P´pai (2001a) considers the scenario a where each agent can receive more than one item and presents a characterization of subclass of strategyproof mechanisms. Bez´ akov´ and Dani (2005) consider the problem of allocating a m items to two agents and show that no strategyproof mechanism can maximize the value of the worse agent. Markakis and Psomas (2011) present a lower bound on the values of agents in the worst-case scenario and also show that no deterministic strategyproof mechanism can achieve a (2 / 3)-approximation of the worst-case bound.

As indicated in the aforementioned studies, pursuing an optimal strategyproof mechanism is sometimes impossible. Procaccia and Tennenholtz (2013) start to consider strategyproof mechanisms that achieve an approximation of the optimal objective when the optimal solution is computationally intractable or when no such mechanism exists. Amanatidis et al. (2016) focus on indivisible goods and present a deterministic strategyproof mechanism with O m ( )-approximation on maximin-share fairness. They complement the result by showing that no deterministic strategyproof mechanism can achieve better than (1 / 2)-approximation. For allocating indivisible chores, Aziz et al. (2022b) assume ordinal valuations for agents and present deterministic and randomized mechanisms that return allocations guaranteeing O (log( m/n ))-approximation and O (log( √ n ))-approximation of maximin share, respectively.

There are also some studies concerning strategyproofness along with other fairness criteria such as EF1. Amanatidis et al. (2017) demonstrate that no deterministic strategyproof mechanism guarantees EF1, even there are only two agents with additive valuations. To achieve positive results, subsequent studies focus on domains of restricted agent preferences. Halpern et al.

4 In a symmetric mechanism, agents with the same reported valuations should receive identical (expected) utility.

(2020) focus on additive valuations with a binary margin and indicate that the rule of maximizing Nash welfare with a lexicographic tie-breaking rule is group strategyproof, EF1 and Pareto optimal. Babaioff et al. (2021) consider submodular and monotone valuation functions with a binary margin and show that the Lorenz dominating 5 rule is strategyproof, EF1 and Pareto optimal. A follow-up work (Barman and Verma, 2022) show that the proposed mechanism in Babaioff et al. (2021) is indeed group strategyproof.

## 1.3 Organization of the paper

After introduction of basic definitions in Section 2, we establish our impossibility results in Section 3 for deterministic mechanisms. We then follow up with randomization and present our randomized mechanisms, respectively for allocating chores and mixed items in Sections 4 and 5, together with their nice properties. Proofs of lemmas, propositions and theorems are provided either in the main body of the paper or are relegated to the appendix. We make some concluding remarks in Section 6.

## 2 Preliminaries

/negationslash

/negationslash

Denote by [ k ] = { 1 , . . . , k } for any k ∈ N + . A set E = { e , . . . , e 1 m } of m indivisible items are to be allocated to a set N = { 1 , . . . , n } of n agents. Each agent i is associated with a valuation function v i : 2 E → R . An item e is a good (resp., a chore) for agent i if v i ( e ) ≥ 0 (resp., v i ( e ) ≤ 0). Throughout this paper, we are particularly interested in two settings: (i) chores: all items are chores for all agents, and (ii) mixed items: an item can be a good for agent i but a chore for some agent j = . i Agents are rational and can interact strategically towards making a collective decision. Let A be the set of outcomes or allocations . An allocation A = ( A , . . . , A 1 n ) ∈ A is an n -partition of E , that is, A i ∩ A j = ∅ for any i, j ∈ [ n ] with i = j and ⋃ i ∈ [ n ] A i = E . Given an allocation A = ( A , . . . , A 1 n ), for any i ∈ [ n ], A i represents the set of items or the bundle allocated to agent i . Note that in any allocation, no item is left unallocated.

Throughout the paper, for any i ∈ [ n ], function v i represents the true valuation function of agent i , and following the convention of mechanism design literature, v i is also called the type of agent i . Each agent i privately observes his preferences over outcomes in A , which is defined by that agent i knows his valuation function v i that is not available to others. Denote by V i the set of all possible types of agent i and by V = V 1 ×··· × V n the set of type profiles. A type profile is denoted by v = ( v , . . . , v 1 n ). Additionally, each agent i is associated with a utility function u i : A × V i → R . Given an outcome A and type v i ∈ V i , utility u i ( A , v i ) denotes the value or payoffs of agent i under outcome A when his type is v i . In this paper, we focus

5 For two ascending-ordered vectors a and b , the Lorenz domination partial order is defined as a /follows Lorenz b if for every k , the sum of the first k entries of a is at least as large as that of b . A Lorenz dominating allocation is the allocation whose valuation vector Lorenz dominates the vector of every other allocation.

on the setting where agent i does not care about how bundles are allocated to others, i.e., no externalities . Hence, the utility of agent i with type v i under allocation A = ( A , . . . , A 1 n ) can also be expressed as u i ( A , v i i ), equivalent to v i ( A i ).

The social choice function or mechanism is a mapping M : V 1 ×··· × V n → A that assigns every possible type profile an outcome from set A . We focus on direct mechanisms that elicit type information from agents by asking them to reveal their true valuations. After receiving reported profile ˆ = (ˆ v v , . . . , v 1 ˆ ), mechanism n M outputs an allocation based on ˆ. v Given the combinatorial explosion, it is unrealistic for agents to report their valuations on every subset T ⊆ E . Consequently, we assume that valuation function v i is additive for all i ∈ [ n ], that is, for any T ⊆ E v , i ( T ) = ∑ e ∈ T v i ( { } e ). For simple notations, we use v i ( e ), instead of v i ( { } e ), to denote agent i 's valuation of item e . The set A of outcomes, the set N of agents, the set E of items and the type sets { V i } i ∈ [ n ] are common knowledge, while type v i is private to agent i only.

## 2.1 Fractional and randomized allocations

In this paper, we also write allocations in the form of matrices. With a slight abuse of notation, an allocation or an allocation matrix A = ( a j,i ) j ∈ [ m,i ] ∈ [ n ] is such that a fraction a j,i of item e j allocated to agent i and ∑ i ∈ [ n ] a j,i = 1 for all j ∈ [ m ]. A deterministic allocation requires a j,i ∈ { 0 1 , } for all j, i , while in a fractional allocation A , a j,i can be any real number in interval [0 , 1]. A randomized allocation ˜ A is a probability distribution over deterministic allocations, and moreover, it naturally implements a fractional allocation. More specifically, let the support of ˜ A be A 1 , . . . , A k ∈ { 0 1 , } n and the probability of being A j is p j for all j ∈ [ k ]. Then we say that ˜ A implements fractional allocation ∑ j ∈ [ k ] p j A j . Note that for a given fractional allocation, there can be several randomized allocations that implement it.

Given an arbitrary randomized allocation ˜ A , let us suppose it implements fractional allocation A ′ = ( a ′ j,i ) j ∈ [ m,i ] ∈ [ n ] . The term a ′ j,i can be interpreted as the probability of assigning item e j to agent i . For any i ∈ [ n ], the expected value of agent i under ˜ A is ∑ j ∈ [ m ] a ′ j,i v i ( e j ), which is equivalent to the value of agent i under fractional allocation A ′ .

## 2.2 Strategyproofness

Let us formally define the notions of (group) strategyproofness and strategyproofness in expectation. We first introduce a common notation used in the mechanism design literature. Given the reported profile ˆ and a set of agents v S ⊆ N , denote by ˆ v S the set of reported valuations of agents S and by ˆ v -S the set of reported valuations of agents N \ S , i.e., ˆ v -S = ˆ v N S \ . Similar notations extend to agent type and the set of agent types.

Definition 2.1 (SP) . A deterministic mechanism M is strategyproof if ∀ i ∈ [ n ], ∀ v i ∈ V i , ∀ ˆ v i ∈ V i , ∀ ˆ v -i ∈ V -i , the following holds:

$$u _ { i } ( \mathcal { M } ( v _ { i }, \hat { v } _ { - i } ), v _ { i } ) \geq u _ { i } ( \mathcal { M } ( \hat { v } _ { i }, \hat { v } _ { - i } ), v _ { i } ).$$

In a strategyproof (SP) mechanism, it is always an optimal strategy for an agent i to truthfully report his type, regardless of what is reported by other agents. In other words, no agent can gain additional utility by misreporting compared to the received utility when reporting truthfully. A mechanism is randomized if it returns randomized allocations. Accordingly, we use the notion of strategyproof in expectation (SPIE) for a randomized mechanism under which every agent's expected utility is maximized when reporting truthfully. Formally, we have the following definition.

Definition 2.2 (SPIE) . A randomized mechanism ˜ M is strategyproof in expectation if ∀ i ∈ [ n ], ∀ v i ∈ V i , ∀ ˆ v i ∈ V i , ∀ ˆ v -i ∈ V -i , the following holds,

$$\mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ( v _ { i }, \hat { v } _ { - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] \geq \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ( \hat { v } _ { i }, \hat { v } _ { - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ].$$

SP and SPIE mechanisms can incentivize truthful reporting for individual agents but may not prevent strategic manipulation from a group of agents. To address strategic behavior at the group level there is a need for group-strategyproof (GSP) and group-strategyproof in expectation (GSPIE) mechanisms, in which no group of agents can collude to misreport their valuations in a way that makes at least one member of the group better off without making any of the remaining members worse off.

Definition 2.3 (GSP) . A deterministic mechanism M is group-strategyproof if there does not exist a group of agents S ⊆ N and a reported profile (ˆ v S , v ˆ -S ) such that for any i ∈ S ,

$$u _ { i } ( \mathcal { M } ( \hat { v } _ { S }, \hat { v } _ { - S } ), v _ { i } ) \geq u _ { i } ( \mathcal { M } ( v _ { S }, \hat { v } _ { - S } ), v _ { i } ),$$

and at least one strict inequality holds.

Definition 2.4 (GSPIE) . A randomized mechanism ˜ M is group-strategyproof in expectation if there does not exist a group of agents S ⊆ N and a reported profile (ˆ v S , v ˆ -S ) such that for any i ∈ S ,

$$\mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ( \hat { v } _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] \geq \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ( v _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ],$$

and at least one strict inequality holds.

## 2.3 Efficiency, fairness and other distributional properties

We conclude this section by presenting efficiency measurement and fairness criteria that we are concerned with in this study. We begin with Pareto optimal allocations and social welfare functions.

Definition 2.5 (PO) . An allocation B = ( B , . . . , B 1 n ) Pareto dominates another allocation A = ( A , . . . , A 1 n ) if for any i ∈ [ n ], v i ( B i ) ≥ v i ( A i ) and at least one inequality is strict. An allocation A is Pareto optimal if no allocation Pareto dominates it.

Definition 2.6. Given an allocation A = ( A , . . . , A 1 n ), its utilitarian welfare is UW ( A ) = ∑ i ∈ [ n ] v i ( A i ) and the egalitarian welfare is EW ( A ) = min i ∈ [ n ] v i ( A i ). An allocation A is a utilitarian welfare maximizer (UWM) and an egalitarian welfare maximizer (EWM) if A achieves the maximum utilitarian welfare and egalitarian welfare, respectively.

Definition 2.7 (EF and EF1) . An allocation A = ( A , . . . , A 1 n ) is envy-free (EF) if for any i, j ∈ [ n ], v i ( A i ) ≥ v i ( A j ). An allocation A is envy-free up to one item (EF1) if for any i, j ∈ [ n ], there exists e ∈ A i ∪ A j such that v i ( A i \ { e } ) ≥ v i ( A j \ { e } ).

Informally, for mixed items, an allocation is EF1 if for every agent i , he does not envy agent j after either hypothetically removing a chore (from agent i 's view) in his own bundle or removing a good in agent j 's bundle.

Definition 2.8 (EQ and EQ1) . An allocation A = ( A , . . . , A 1 n ) is equitable (EQ) if for any i, j ∈ [ n ], v i ( A i ) = v j ( A j ). The allocation A is equitable up to one item (EQ1) if for any i, j ∈ [ n ], there exists e ∈ A i ∪ A j such that v i ( A i \ { e } ) ≥ v j ( A j \ { e } ).

The notion of EQ1 requires that the valuation of agent i must be at least that of agent j when either a chore (from agent i 's view) is removed from agent i 's bundle or a good is removed from agent j 's bundle.

Definition 2.9 (PROP and PROP1) . An allocation A = ( A , . . . , A 1 n ) is proportional (PROP) if for any i ∈ [ n ], v i ( A i ) ≥ 1 n v i ( E ). An allocation A is proportional up to one item (PROP1) if for any i ∈ [ n ], v i ( A i ) ≥ 1 n v i ( E ) or v i ( A i ∪{ } e ) ≥ 1 n v i ( E ) for some e ∈ E A \ i or v i ( A i \{ } e ) ≥ 1 n v i ( E ) for some e ∈ A i .

In a PROP allocation, every agent i is guaranteed a value of 1 n v i ( E ), also known as his fair share . In a PROP1 allocation, agent i is guaranteed his fair share after either hypothetically receiving an extra good, not assigned to his yet, or eliminating a chore from his bundle. We remark that in the setting of mixed items, when agents are associated with additive valuations, EF allocations are PROP, and EF1 allocations are also PROP1 (Aziz et al., 2022a).

## 3 Impossibility results of deterministic mechanisms

In this section, we focus on deterministic mechanisms. Consider a class of widely-studied mechanisms, called sequential picking (Kohler and Chandrasekaran, 1971), where agents are ordered in advance and each agent i picks a number t i of items in his turn. The advantage of sequential picking is that once { t i } i ∈ [ n ] are predetermined or unrelated to reported profiles and ∑ i ∈ [ n ] t i = m , the corresponding mechanism is strategyproof and outputs a complete allocation. The sequential picking rule has been employed to design truthful mechanisms with performance guarantees regarding share-based fairness notions (Amanatidis et al., 2016, Aziz et al., 2022b). However, we find that for indivisible chores, no sequential picking mechanism can always return Pareto optimal outcomes, even when the margin of chores is binary, i.e., v i ( e j ) ∈ { 0 , - } 1 for all i and j .

Theorem 3.1. For indivisible chores, no sequential picking mechanism can always return Pareto optimal allocations, even when agents' valuations have a binary margin.

We next present a stronger impossibility result regarding all deterministic mechanisms in the context of allocating indivisible chores.

Theorem 3.2. For indivisible chores, no deterministic mechanism can be SP , PO and EQ1 , simultaneously, even when there are four chores and two agents with binary additive valuations.

Proof. For a contradiction, let M be a deterministic SP, PO and EQ1 mechanism. Consider an instance I with two agents and a set E of four chores e , e 1 2 , e 3 , e 4 . Given the reported profile ˆ v = (ˆ v , v 1 ˆ ) with ˆ ( 2 v i e j ) = -1 for all i, j , mechanism M has to assign each agent two chores so that the outcome can be EQ1 when agents report truthfully. Without loss of generality, we assume M ( ˆ v ) = A with A 1 = { e , e 1 2 } and A 2 = { e , e 3 4 } . We now consider another reported profile ˆ v ′ = (ˆ v , v ′ 1 ˆ ) where ˆ ( ′ 2 v ′ 2 e ) = ˆ ( v 2 e ) for all e and ˆ ( v ′ 1 e 1 ) = ˆ ( v ′ 1 e 2 ) = 0 and ˆ ( v ′ 1 e j ) = -1 for j = 3 4. Suppose , M ( ˆ v ′ ) = A ′ . As M always returns PO allocations, allocation A ′ needs to be PO when ˆ v ′ is true valuations. Thus, e , e 1 2 should be assigned to agent 1 in A ′ . Moreover, by the property of EQ1, each agent i ∈ [2] should be allocated one chore from { e , e 3 4 } under A ′ .

Now suppose for each i ∈ [2], ˆ v ′ i is the type of agent i , i.e., ˆ v ′ i = v i . Then, if both agents report truthfully, M returns allocation A ′ with v 1 ( A ′ 1 ) = -1. However, if agent 1 misreports ˆ , then the outcome becomes v 1 M (ˆ v , v 1 ˆ ) = ′ 2 A , and the value of agent 1 in the allocation A is equal to v 1 ( A 1 ) = 0. Therefore, agent 1 has incentive to behave strategically, contradicting the strategyproofness of M . /square

We remark that the above impossibility result is mainly owing to the fact that deterministic strategyproofness is too strict to be achieved together with Pareto efficiency and fairness. Note that for indivisible chores, EQ1 and PO allocations are guaranteed to exist for additive valuations (Freeman et al., 2020). Given such a strong impossibility result, we relax strategyproofness via randomness.

## 4 A randomized mechanism for indivisible chores

Throughout this section, we focus on the setting of indivisible chores, and assume agents have k -restricted additive valuation functions, that is, every chore e j is associated with k inherent values v 1 ( e j ) , v 2 ( e j ) , . . . , v k ( e j ) with v t ( e j ) &lt; 0 for all t ∈ [ k ], and for any agent i , his value of e j is v i ( e j ) ∈ { 0 , v 1 ( e j ) , v 2 ( e j ) , . . . , v k ( e j ) } . In particular, 1-restricted additive valuation is simply called restricted additive valuation where for simple notations, the inherent value of e j is v e ( j ) &lt; 0. The restricted additive valuation has been studied in the literature on fair division and resulted in significant and challenging research questions (Akrami et al., 2022, Asadpour et al., 2012, Bez´kov´ and Dani, 2005). Note that restricted additive functions a a strictly generalize binary additive functions. Problems that can be solved efficiently in binary additive valuations possibly become computationally intractable under the restrictive additive

domain. For example, in the context of indivisible goods, the egalitarian welfare-maximizing allocation can be computed in polynomial time under binary additive valuations (Barman et al., 2018), while for restricted additive valuations, it is NP-hard to approximate within a factor better than 1 2 (Bez´kov´ and Dani, 2005). / a a As type sets { V i } i ∈ [ n ] are common knowledge, the inherent values { v t ( e j ) } of e j is publicly known, which further constrains every agent i 's reported value on e j to satisfy ˆ ( v i e j ) ∈ { 0 , v 1 ( e j ) , v 2 ( e j ) , . . . , v k ( e j ) } .

Designing SPIE mechanisms with fairness and efficiency guarantee is not a trivial task. Existing randomized mechanism such as Random Priority and Probabilistic Serial (Bogomolnaia and Moulin, 2001) can not guarantee strategyproofness and fairness at the same time when m &gt; n . While some straightforward mechanisms, such as assigning all items to an agent chosen uniformly at random satisfies strategyproofness and fairness before realization, its performance guarantees is poor after realization, with all items allocated to a single agent. Therefore, among randomized mechanisms, we pursue those that can be strategyproof in expectation and have best of both worlds performance guarantees. In the following, we define ex-ante and ex-post fairness/efficiency.

Definition 4.1. Given fairness or efficiency notion P , a randomized allocation ˜ A is ex-ante P if the fractional allocation implemented by ˜ A is P and is ex-post P if every deterministic allocation in its support is P .

Definition 4.2. Given fairness or efficiency notions of P 1 and P 2 , a randomized mechanism ˜ M is ex-ante P 1 and ex-post P 2 if it always returns a randomized allocation that is ex-ante P 1 and ex-post P 2 .

For ex-ante and ex-post efficiency, we have the following implication relation.

Proposition 4.3. An ex-ante UWM randomized allocation ˜ A is also ex-ante PO and ex-post UWM . An ex-ante PO randomized allocation ˜ B is also ex-post PO .

/negationslash

Proof. Suppose that ˜ A has support { A 1 , . . . , A k } with probability p i on deterministic allocation A i for each i ∈ [ k ]. Let A ′ be the fractional allocation implemented by ˜ A . If there exists another fractional allocation ̂ A that Pareto dominates A ′ , then UW ( ̂ A &gt; ) UW ( A ′ ) holds, contradicting the fact that ˜ A is ex-ante UWM. Hence, allocation ˜ A is also ex-ante PO. Next, we prove that ˜ A is also ex-post UWM. For a contradiction, suppose ˜ A is not ex-post UWM, then there must exist a deterministic allocation A k +1 such that UW ( A k +1 ) &gt; UW ( A i ) for some i ∈ [ k ]. Consider the fractional allocation A ′′ = p i A k +1 + ∑ j = i p j A j and it is not hard to verify UW ( A ′′ ) &gt; UW ( A ′ ), contradicting the fact that ˜ A is ex-ante UWM. Therefore, ˜ A is also ex-post UWM.

For an arbitrary ex-ante PO randomized allocation ˜ B , let its support be { B 1 , . . . , B k } with probability p i on deterministic allocation B i for each i ∈ [ k ]. Moreover, let B ′ be the fractional allocation implemented by ˜ B . For a contradiction, assume that there exists another deterministic allocation B k +1 that Pareto dominates B i for some i ∈ [ k ]. Similarly, the fractional

/negationslash

In contract to UWM and PO, not every ex-ante fair solution guarantees ex-post fairness. Let us again consider the mechanism of assigning all items to an agent chosen uniformly at random. It is not hard to verify that the returned allocation is ex-ante EF. However, it provides little fairness guarantee after realization.

allocation B ′′ = p i B k +1 + ∑ j = i p j A j Pareto dominates B ′ , a contradiction. Therefore, allocation ˜ B is ex-post PO. /square

The main result of this section is a GSPIE randomized mechanism (see Algorithm 1) with best of both worlds fairness and efficiency guarantees for n agents with 1-restricted additive valuation functions. Intuitively, the mechanism first collects reported type profile and then partitions [ m ] into Q and ¯ where for any Q e j with j ∈ Q , there exists some agent with reported value zero on e j , while for any e j ′ with j ′ ∈ ¯ , Q every agent i reports ˆ ( v i e j ′ ) = v e ( j ′ ). Then, for every j ∈ Q , RandChore assigns e j to an agent chosen uniformly at random with reported value 0 on e j . Items ⋃ j ∈ ¯ Q e j are then assigned to agents in a round-robin fashion based on a permutation σ of { 1 , . . . , n } generated uniformly at random.

## Algorithm 1 RandChore

- 1: Collects reported profile (ˆ v , . . . , v 1 ˆ ). n
- 2: Let Q = { q ∈ [ m ] | ∃ i such that ˆ ( v i e q ) = 0 } and ¯ = [ Q m ] \ Q .
- 3: For every q ∈ Q , uniformly at random pick an agent reporting zero value on e q and assign e q to that agent.
- 4: Let ¯ = Q { l 1 , l 2 , . . . , l k } with inherent values v e ( l 1 ) ≥ · · · ≥ v e ( l k ).
- 5: Uniformly at random generate a permutation σ of { 1 , . . . , n } . According to σ , assign the chore with the largest inherent value from the remaining items to an agent each time, until all chores are assigned. If there is a tie on the largest value item, pick e l j with the smallest index j .

Theorem 4.4. Mechanism RandChore is GSPIE and satisfies the following:

- · Fairness guarantee: ex-ante EF PROP EQ , , and ex-post EF1 , PROP1 EQ1 , ;
- · Efficiency guarantee: ex-ante PO UWM EWM , , and ex-post PO UWM 2 , , -approximation of EWM .

In the following, we split the proof of Theorem 4.4. We begin with GSPIE and then prove best of both worlds fairness and efficiency. For simplicity, we use notation ˜ M ∗ and RandChore interchangeably in this section.

## Proposition 4.5. Mechanism RandChore is GSPIE .

Before proving Proposition 4.5, we first present several lemmas.

Lemma 4.6. Given the reported profile (ˆ v , . . . , v 1 ˆ ) n and the corresponding Q and ¯ Q , for any agent i ∈ [ n ] , he receives an expected utility 1 n v i ( ⋃ q ∈ ¯ Q e q ) in Step 5.

Proof. Fix index i . Since σ is a uniformly random permutation of { 1 2 , , . . . , n } , the probability of agent i on position σ j ( ) is 1 n for all j ∈ [ n ]. Based on Step 5, if agent i is in position σ j ( ), he receives a utility v i ( e l j ∪ e l n + j ∪ · · · ∪ e l kn + j ), where k = /floorleft ( | ¯ Q | -j ) /n /floorright . Thus, his expected utility derived by the assignment of Step 5 is equal to

$$\sum _ { j = 1 } ^ { n } \frac { 1 } { n } v _ { i } ( \bigcup _ { p = 0 } ^ { k } e _ { l _ { p n + j } } ) = \frac { 1 } { n } v _ { i } ( \bigcup _ { j = 1 } ^ { n } \bigcup _ { p = 0 } ^ { k } e _ { l _ { p n + j } } ) = \frac { 1 } { n } v _ { i } ( \bigcup _ { q \in \bar { Q } } e _ { q } ),$$

where the first equality transition is due to the additivity of v i ( ). · /square

For any group S of agents and any agent i ∈ S , if agent i 's true valuation on e j is v i ( e j ) = 0, then he cannot gain additional expected utility by misreporting ˆ ( v i e j ) = v e ( j ).

/negationslash

Lemma 4.7. Given a subset S ⊆ N and a reported profile (ˆ v S , v ˆ -S ) with ˆ v S = v S , construct another reported profile (ˆ v ′ S , v ˆ -S ) as follows: for any i ∈ S and e j ∈ E , if v i ( e j ) = 0 , then set ˆ ( v ′ i e j ) = 0 ; otherwise, ˆ ( v ′ i e j ) = ˆ ( v i e j ) . Then for any i ∈ S , the expected utility of agent i under reported profile (ˆ v ′ S , v ˆ -S ) is at least that under (ˆ v S , v ˆ -S ) ,

$$\mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { * } ( \hat { v } _ { S } ^ { \prime }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] \geq \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { * } ( \hat { v } _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ].$$

Lemma 4.8. Given a subset S ⊆ N and reported valuations ˆ v -S , the summation of the expected utilities of agents in S is maximized when every agent i ∈ S reports his true valuation.

Proof Sketch. The proof is given by a contradiction argument. If some valuation functions ˆ v S result in the summation of expected utilities of agents in S being larger than that under v S , then according to Lemma 4.7, we can further assume ˆ v S only contains one type of misreporting: some agent j ∈ S reports ˆ ( v j e ) = 0 on chore e while his true valuation is v j ( e ) = v e ( ) &lt; 0. Based on Steps 2 and 5, deviating from v e ( ) to zero can only increase the probability of allocating e to agents in S . Therefore, agents of S have no incentive to manipulate. The formal proof is deferred to Appendix A.2. /square

Now we are ready to prove that RandChore is GSPIE.

Proof of Proposition 4.5. For the sake of a contradiction, assume there exists a group of agents S ⊆ N and a reported profile (ˆ v S , v ˆ -S ) such that for any agent i ∈ S , it holds that

$$\mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { * } ( \hat { v } _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] \geq \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { * } ( v _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ],$$

and at least one strict inequality holds. Accordingly, we have the following inequality,

$$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cd� \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \collections \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \clots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots
\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cl: \\ \sum _ { i \in S } \mathbb { E } _ { \mathbf A } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { I } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { F } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { E } _ { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } ^ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { { \mathbf A } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \nu } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J }_ \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \so \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim \widet } \sim \widetilde { \mathcal { J } _ { \sim \widet } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sigma _ { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { J } _ { \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim } \sim \widetilde { \mathcal { J } _ { \sim }$$

which contradicts Lemma 4.8. /square

After establishing the group strategyproofness, we proceed to prove that RandChore can ensure best of both worlds fairness. Specifically, RandChore always returns solutions with exante exact fairness (EF, PROP and EQ) and ex-post approximate fairness (EF1, PROP1 and EQ1).

Proposition 4.9. Mechanism RandChore is ex-ante EF , EQ and PROP , and ex-post EF1 , EQ1 and PROP1 .

We then show that RandChore also guarantees efficiency from the best of both worlds perspective.

Proposition 4.10. Mechanism RandChore is ex-ante PO UWM , and EWM and ex-post PO , UWM and 2 -approximation of EWM .

Note that the 2-approximation of optimal egalitarian welfare is almost the (ex-post) limitation of RandChore , especially when the number of agents is large.

Proposition 4.11. Mechanism RandChore is not ex-post ( 2 n -1 n -/epsilon1 ) -approximation of EWM for any /epsilon1 &gt; 0 .

As for the running time of the proposed mechanism, although RandChore is a randomized mechanism, randomness here does not affect the running time of execution. Note that the worstcase running time of Step 3 is O m ( ) and of Step 5 is O mn ( ). Thus, the worst-case running time of RandChore is O mn ( ).

We conclude this section by a discussion of possible extension of RandChore . As demonstrated, RandChore can guarantee EF1, EQ1, PO and strategyproofness simultaneously when agents have restricted additive valuation functions. A natural question arises: in a broader preference domain, such as additive valuation functions, can a strategyproof (in expectation) mechanism achieve EF1, EQ1, and PO? Unfortunately, the answer is negative, even without the requirement of strategyproofness. Freeman et al. (2020) have shown that for indivisible chores, EF1, EQ1 and PO are incompatible for four agents with additive valuation functions. For completeness, we also provide the example in Appendix A.2. Note that in the example of Freeman et al. (2020), valuation functions of agents are indeed 2-restricted additive, and consequently, the proposed mechanism RandChore achieves the best that we can hope for in the k -restricted additive preference domain.

## 5 A randomized mechanism for allocating mixed items

In this section, we consider allocation of mixed items to two agents, where an item can be a good for an agent but a chore for another. For valuation functions, agents are assumed to have M-restricted additive valuations, which can be viewed as a generalization of restricted additive functions to the setting of mixed items. Namely, each item e q has two inherent values {-c e ( q ) , v ( e q ) } with c e ( q ) , v ( e q ) &gt; 0 and, if e q is a chore to (resp., a good for) an agent, then his valuation of e q is -c e ( q ) (resp., v e ( q )). Otherwise, his valuation for e q is equal to 0. Note that c e ( q ) and v e ( q ) are not required to be identical. Recall that type sets { V i } i ∈ [ n ] are common knowledge, and hence for any q ∈ [ m ], inherent values -c e ( q ) and v e ( q ) are publicly known so that the reported valuation should be ˆ ( v i e q ) ∈ {-c e ( q ) , 0 , v ( e q ) } for all i ∈ [ n ].

The main result of this section is a randomized SPIE mechanism with best of both worlds fairness and efficiency for two agents. We propose mechanism RandMixed and formally introduce it below (see Algorithm 2). A simple description of RandMixed is as follows. Based on reported profile (ˆ v , v 1 ˆ ), partition [ 2 m ] into four parts { Q ,Q ,Q ,Q 0 1 2 3 } . Assign items in Q 0 one-by-one to one of the two agents uniformly at random. For any i ∈ { 1 2 , } , assign items ⋃ q ∈ Q i e q to agent i and then assign items ⋃ q ∈ Q 3 e q to agents in a round-robin fashion based on a permutation σ generated uniformly at random.

## Algorithm 2 RandMixed

- 1: Collect reported profile (ˆ v , v 1 ˆ ). 2
- 2: Partition [ m ] = Q 0 ∪ Q 1 ∪ Q 2 ∪ Q 3 where Q 0 = { q ∈ [ m ] | ˆ ( v 1 e q ) = ˆ ( v 2 e q ) = 0 , } Q 1 = { q ∈ [ m ] | ˆ ( v 1 e q ) &gt; v ˆ ( 2 e q ) } , Q 2 = { q ∈ [ m ] | ˆ ( v 1 e q ) &lt; v ˆ ( 2 e q ) } and Q 3 = { q ∈ [ m ] | ˆ ( v 1 e ) = ˆ ( v 2 e ) = 0 } .

/negationslash

- 4: For i = 1 2, assign items , ⋃ q ∈ Q i e q to agent i .
- 3: For each e q with q ∈ Q 0 , uniformly at random pick an agent and assign e q to that agent.
- 5: Let σ be a permutation of { 1 2 , } generated at random uniformly. Among unassigned items, assign the one with the largest inherent value to the two agents in a round-robin fashion based on permutation σ .

Theorem 5.1. Mechanism RandMixed is SPIE , ex-ante PO UWM EF PROP , , , and ex-post PO UWM EF1 , , and PROP1 .

In what follows, we split the proof of Theorem 5.1, and for simplicity, we use ˜ M 2 and RandMixed interchangeably in this section.

Proposition 5.2. Given reported profile (ˆ v , v 1 ˆ ) 2 and the corresponding partition { Q i } 3 i =0 , any agent i ∈ { 1 2 , } receives an expected utility 1 2 v i ( ⋃ q ∈ Q 0 ∪ Q 3 e q ) + v i ( ⋃ q ∈ Q i e q ) .

Proof. Fix i ∈ { 1 2 , } . As items ⋃ q ∈ Q 3 -i e q are allocated to agent 3 -i , the utility of agent i indeed comes from the assignment of ⋃ q ∈ Q 0 ∪ Q i ∪ Q 3 e q . Note that e q with q ∈ Q 0 is assigned to agent i with probability 1 2 , and e q with q ∈ Q i is assigned to agent i with probability 1. As for items ⋃ q ∈ Q 3 e q , similar to the analysis in the proof of Lemma 4.6, this part results in an expected utility 1 2 v i ( ⋃ q ∈ Q 3 e q ) for agent i . Therefore, agent i 's expected utility derived from the assignment is 1 2 v i ( ⋃ q ∈ Q 0 ∪ Q 3 e q ) + v i ( ⋃ q ∈ Q i e q ). /square

/negationslash

/negationslash

Lemma 5.3. Given agent i and reported profile (ˆ v k i , v ˆ 3 -i ) with ˆ ( v k i e k ) = v i ( e k ) for some k ∈ [ m ] , construct another reported profile (ˆ v , v i ˆ 3 -i ) where ˆ ( v i e k ) = v i ( e k ) and ˆ ( v i e ) = ˆ ( ) v k i e for all e = e k . Then, the expected utility of agent i under reported profile (ˆ v , v i ˆ 3 -i ) is at least that under (ˆ v k i , v ˆ 3 -i ) .

Intuitively, Lemma 5.3 states that from any non-truthful reported profile, correcting the reported value of a single item of agent i does not decrease the expected utility of agent i .

/negationslash

Then, for any reported valuation ˆ v i = v i , one can start from ˆ v i and reach v i by a sequence of corrections of the reported values for a single item, without decreasing the expected utility.

## Proposition 5.4. Mechanism RandMixed is SPIE .

Proof. Fix i ∈ { 1 2 , } and ˆ v 3 -i . Let ˆ v i be arbitrary reported valuations that differ from the true valuations v i on a set { e p 1 , . . . , e p r } of r ∈ N + items. First let ˆ v 0 i = ˆ v i and then for every l ∈ [ r ], construct valuation function ˆ v l i as follows:

$$\ u n c o n \, \upsilon _ { i } \, \infty \, \text{rows}. \\ \hat { v } _ { i } ^ { l } \, ( e ) = \begin{cases} v _ { i } ( e _ { p _ { l } } ) & \text{if $e=e_{p_{l}}$,} \\ \hat { v } _ { i } ^ { l - 1 } ( e ) & \text{otherwise.} \end{cases} \\ \text{hat valuation functions } \hat { v } _ { i } ^ { r } \, \text{ is identical } t$$

It is not hard to verify that valuation functions ˆ v r i is identical to v i . Then, according to Lemma 5.3, we have

$$\mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { 2 } ( \hat { v } _ { i } ^ { r }, \hat { v } _ { 3 - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] \geq \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { 2 } ( \hat { v } _ { i } ^ { r - 1 }, \hat { v } _ { 3 - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] \geq \cdots \geq \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { 2 } ( \hat { v } _ { i } ^ { 0 }, \hat { v } _ { 3 - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ].$$

Since ˆ v r i = v i and ˆ v 0 i = ˆ , the above inequalities become v i

$$\mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { 2 } ( v _ { i }, \hat { v } _ { 3 - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] \geq \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { 2 } ( \hat { v } _ { i }, \hat { v } _ { 3 - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ],$$

which completes the proof. /square

In the following, we show that RandMixed outputs allocations that guarantee ex-ante and ex-post fairness and efficiency.

Proposition 5.5. Mechanism RandMixed is ex-ante EF , PROP and ex-post EF1 , PROP1 .

Proposition 5.6. Mechanism RandMixed is ex-ante and ex-post PO and UWM .

Since randomness does not affect the running time of execution, the worst-case running time of RandMixed is O m ( ). One may observe that mechanism RandMixed does not provide good performance guarantee regarding the notion of equitability. We remark that this is due to the fact that (relaxed) equitability and PO is incompatible in the mixed items setting even without the requirement of strategyproofness. For example, consider the following instance of two agents and two mixed items, in which Agent 1 values each item at 1 and agent 2 values each item at -1. The PO allocation assigns both items to agent 1, violating EQ and EQ1.

## 6 Conclusions

In this paper, we have studied allocation of indivisible items from the mechanism design perspective. We have focused on the settings where (i) all items are chores and (ii) an item can be a good for one agent and a chore for another. If randomization is not allowed, we have showed that strategyproofness, fairness and efficiency are incompatible, and in particular, no deterministic mechanism can be SP, PO and EQ1 simultaneously, even when agents' valuations

are binary additive. On the other hand, if randomization is allowed, we have proposed a GSPIE mechanism that guarantees ex-ante EF, EQ and ex-post EF1, EQ1 and ex-ante UWM and EWM, when all items are chores and agents' valuations are 1-restricted additive. We have also studied the model of mixed items and designed a randomized SPIE mechanism with best of both worlds fairness and efficiency for two agents with M-restricted additive valuations.

Our findings have significant implications for both the theoretical understanding and practical implementation of fair and efficient allocation mechanisms. Our constructive proofs and analyses provide a solid foundation for designing strategyproof mechanisms in complex allocation settings, offering insights into the mechanisms' ability to align agents' incentives with truthful reporting. Moreover, the proposed mechanisms offer a novel approach to overcoming the inherent challenges of strategyproof mechanism design in the context of indivisible items allocation, showcasing the potential of randomised mechanisms in achieving strategyproofness, fairness and efficiency simultaneously. In practice, our proposed mechanisms can be implemented easily and efficiently in various real-world scenarios where agents' preferences are private but fair and efficient resource allocation is crucial.

Looking forward, there are several interesting open questions that deserve investigation. Firstly, it remains to be seen whether the idea of RandMixed can be generalized to accommodate three or more agents for mixed items. The second open question is if it is possible to achieve strategyproofness in expectation and best of both worlds fairness and efficiency guarantees for goods. Additionally, note that while Theorem 3.2 indicates an impossibility result regarding the notion of EQ1, it remains unknown whether deterministic mechanisms can achieve strategyproofness, Pareto optimality, and other fairness criteria such as EF1 or PROP1.

## References

Abdulkadiro˘lu, A. and S¨nmez, T. (2003). School choice: A mechanism design approach. g o Am. Econ. Rev. , 93(3):729-747.

Akrami, H., Mehlhorn, K., Seddighin, M., and Shahkarami, G. (2023). Randomized and deterministic maximin-share approximations for fractionally subadditive valuations. In Thirtyseventh Conference on Neural Information Processing Systems .

Akrami, H., Rezvan, R., and Seddighin, M. (2022). An EF2X allocation protocol for restricted additive valuations. In Raedt, L. D., editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022 , pages 17-23. ijcai.org.

Amanatidis, G., Birmpas, G., Christodoulou, G., and Markakis, E. (2017). Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness. In Proceedings of the 2017 ACM Conference on Economics and Computation , EC '17, pages 545-562, New York, NY, USA. ACM.

Amanatidis, G., Birmpas, G., and Markakis, E. (2016). On Truthful Mechanisms for Maximin Share Allocations. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence , IJCAI'16, pages 31-37. AAAI Press.

Asadpour, A., Feige, U., and Saberi, A. (2012). Santa Claus Meets Hypergraph Matchings. ACM Trans. Algorithms , 8(3):24:1-24:9.

Aziz, H., Caragiannis, I., Igarashi, A., and Walsh, T. (2022a). Fair allocation of indivisible goods and chores. Auton. Agents Multi Agent Syst. , 36(1):3.

Aziz, H., Freeman, R., Shah, N., and Vaish, R. (To appear). Best of both worlds: Ex ante and ex post fairness in resource allocation. Oper. Res.

Aziz, H., Li, B., and Wu, X. (2022b). Approximate and strategyproof maximin share allocation of chores with ordinal preferences. Math. Program.

Babaioff, M., Ezra, T., and Feige, U. (2021). Fair and truthful mechanisms for dichotomous valuations. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021 , pages 5119-5126. AAAI Press.

Babaioff, M., Ezra, T., and Feige, U. (2022). On best-of-both-worlds fair-share allocations. In Hansen, K. A., Liu, T. X., and Malekian, A., editors, Web and Internet Economics - 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings , volume 13778 of Lecture Notes in Computer Science , pages 237-255. Springer.

Barman, S., Krishnamurthy, S. K., and Vaish, R. (2018). Greedy algorithms for maximizing nash social welfare. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems , AAMAS '18, page 7-13, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.

Barman, S. and Verma, P. (2022). Truthful and fair mechanisms for matroid-rank valuations. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022 , pages 4801-4808. AAAI Press.

Bez´ akov´, I. and Dani, V. (2005). a Allocating Indivisible Goods. SIGecom Exch. , 5(3):11-18.

Bogomolnaia, A. and Moulin, H. (2001). A New Solution to the Random Assignment Problem. J. Econ. Theory , 100(2):295-328.

Brandt, F., Conitzer, V., Endriss, U., Lang, J., and Procaccia, A. D., editors (2016). Handbook of Computational Social Choice . Cambridge University Press.

| Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., and Wang, J. (2019). The Unreasonable Fairness of Maximum Nash Welfare. ACM Trans. Econ. and Comput. , 7(3):1-32.                                                                                                                              |
|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Chen, B. and Hall, N. G. (2021). Incentive schemes for resolving parkinson's law in project management. Eur. J. Oper. Res. , 288(2):666-681.                                                                                                                                                                          |
| Etesami, S. R. (2022). An optimal control framework for online job scheduling with general cost functions. Oper. Res. , 70(5):2674-2701.                                                                                                                                                                              |
| Freeman, R., Sikdar, S., Vaish, R., and Xia, L. (2020). Equitable Allocations of Indivisible Chores. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems , AAMAS '20, pages 384-392, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems. |
| Gale, D. (1987). College course assignments and optimal lotteries. University of California at Berkely .                                                                                                                                                                                                              |
| Halpern, D., Procaccia, A. D., Psomas, A., and Shah, N. (2020). Fair Division with Binary Valuations: One Rule to Rule Them All. In Chen, X., Gravin, N., Hoefer, M., and Mehta, R., editors, Web and Internet Economics , Lecture Notes in Computer Science, pages 370-383, Cham. Springer International Publishing. |
| Hylland, A. and Zeckhauser, R. (1979). The Efficient Allocation of Individuals to Positions. J. Pol. Econ. , 87(2):293-314.                                                                                                                                                                                           |
| Ibaraki, T. and Katoh, N. (1988). Resource allocation problems: algorithmic approaches . MIT Press, Cambridge, MA, USA.                                                                                                                                                                                               |
| Igarashi, A. and Yokoyama, T. (2023). Kajibuntan: A house chore division app. Proceedings of the AAAI Conference on Artificial Intelligence , 37(13):16449-16451.                                                                                                                                                     |
| Karaenke, P., Bichler, M., Merting, S., and Minner, S. (2020). Non-monetary coordination mechanisms for time slot allocation in warehouse delivery. Eur. J. Oper. Res. , 286(3):897- 907.                                                                                                                             |
| Kohler, D. A. and Chandrasekaran, R. (1971). A Class of Sequential Games. Oper. Res. , 19(2):270-277.                                                                                                                                                                                                                 |
| Lian, J. W., Mattei, N., Noble, R., and Walsh, T. (2018). The conference paper assignment problem: Using order weighted averages to assign indivisible goods. Proceedings of the AAAI Conference on Artificial Intelligence , 32(1).                                                                                  |
| Markakis, E. and Psomas, C. (2011). On worst-case allocations in the presence of indivisible goods. In Chen, N., Elkind, E., and Koutsoupias, E., editors, Internet and Network Economics                                                                                                                             |

- -7th International Workshop, WINE 2011, Singapore, December 11-14, 2011. Proceedings , volume 7090 of Lecture Notes in Computer Science , pages 278-289. Springer.

Moulin, H. (2003). Fair Division and Collective Welfare . The MIT Press.

Nisan, N. and Ronen, A. (2001). Algorithmic mechanism design. Games Econ. Behav. , 35(1):166-196.

Norde, H., Ozen, U., and Slikker, M. (2016). ¨ Setting the right incentives for global planning and operations. Eur. J. Oper. Res. , 253(2):441-455.

P´ apai, S. (2001a). Strategyproof and Nonbossy Multiple Assignments. J. Public Econ , 3(3):257271.

P´ apai, S. (2001b). Strategyproof single unit award rules. Soc. Choice Welf. , 18(4):785-798.

Pereira, J. and Ritt, M. (2023). Exact and heuristic methods for a workload allocation problem with chain precedence constraints. Eur. J. Oper. Res. , 309(1):387-398.

Procaccia, A. D. and Tennenholtz, M. (2013). Approximate Mechanism Design Without Money. ACM Trans. Econ. Comput. , 1(4):18:1-18:26.

Qin, Z. T., Tang, X., Jiao, Y., Zhang, F., Xu, Z., Zhu, H., and Ye, J. (2020). Ride-hailing order dispatching at didi via reinforcement learning. INFORMS J. Appl. Anal. , 50(5):272-286.

Zaerpour, F., Bischak, D. P., and Menezes, M. B. (2017). Coordinated lab-clinics: A tactical assignment problem in healthcare. Eur. J. Oper. Res. , 263(1):283-294.

Zhou, L. (1990). On a conjecture by gale about one-sided matching problems. J. Econ. Theory , 52(1):123-135.

## Appendix

## A.1 For Section 3

## A.1.1 Proof of Theorem 3.1

Without loss of generality, we assume agents are ordered 1 , . . . , n and hence agent 1 is the first to pick. Every sequential picking mechanism can be characterized by a sequence of number t 1 , . . . , t n with ∑ i ∈ [ n ] t i = m . Moreover, such a sequence is predetermined and is not affected by reported profiles. Fix a sequence { t i } n i =1 . If t 1 &lt; m , then consider an instance I 1 where the type of agent 1 is v 1 ( e ) = 0 for all e ∈ E and the type of agent i ≥ 2 is v i ( e ) = -1 for all e ∈ E . Instance I 1 admits an allocation in which all agents have a value zero. However, in the allocation returned by a sequential picking algorithm with t 1 &lt; m , there exists at least one agent receiving negative value, and consequently, the returned allocation is not Pareto optimal. Note that Pareto optimality requires t 1 = m , while any sequential picking algorithm with t 1 = m cannot output Pareto optimal allocation for another instance I 2 where the type of agent 1 is v 1 ( e ) = -1 for all e ∈ E and the type of agent i ≥ 2 is v i ( e ) = 0 for all e ∈ E . Therefore, no sequential picking mechanism can always return PO allocations for both I 1 and I 2 .

## A.2 For Section 4

## A.2.1 Proof of Lemma 4.7

/negationslash

Let Q,Q ¯ and Q , Q ′ ¯ ′ be the corresponding index sets constructed in Step 2 of Algorithm 1 with reported profiles (ˆ v S , v ˆ -S ) and (ˆ v ′ S , v ˆ -S ), respectively. For every i ∈ S , define P i = { e ∈ E | ˆ ( v i e ) = 0 } and P ′ i = { e ∈ E | ˆ ( v ′ i e ) = 0 } . Then, for any i ∈ S and e ∈ P i , if v i ( e ) = 0, by the construction of ˆ , we have ˆ ( v ′ i v ′ i e ) = 0, implying e ∈ P ′ i . If v i ( e ) = 0, again from the definition of ˆ , we have ˆ ( v ′ i v ′ i e ) = ˆ ( v i e ) = 0, implying e ∈ P ′ i . Thus, for any i ∈ S and e ∈ P i , item e ∈ P ′ i always holds, i.e., P i ⊆ P ′ i for all i ∈ S . Note that reported valuations of agents N \ S are identical in these two profiles, then we can claim that Q ⊆ Q ′ , and equivalently, ¯ Q ′ ⊆ ¯ . Q

/negationslash

/negationslash

/negationslash

We now analyze the expected utility of agent i ∈ S caused by the assignment of Steps 3 and 5. For Step 3, note that for any e ∈ C i ∩ P i , it never happens that ˆ ( ) = 0 but ˆ ( v j e v ′ j e ) = v e ( ) for some agent j ∈ N . Then, the number of agents reporting zero on e under (ˆ v ′ S , v ˆ -S ) is at least that under (ˆ v S , v ˆ -S ). Since RandChore uniformly at random assigns e to an agent

The expected utility of an agent indeed comes from two parts, the assignment of Step 3 and of Step 5. For any i ∈ S , let C i = { e ∈ E | v i ( e ) = 0 } be the set of items of which the valuation is non-zero for agent i . If C i ∩ P i = ∅ (resp., C i ∩ P ′ i = ∅ ) for some i , then agent i would receive a negative expected utility from the assignment of C i ∩ P i (resp., C i ∩ P ′ i ) under the reported profile (ˆ v S , v ˆ -S ) (resp., (ˆ v ′ S , v ˆ -S )). Recall that for any i ∈ S , P i ⊆ P ′ i holds, and thus, C i ∩ P i ⊆ C i ∩ P ′ i . For any i ∈ S and e ∈ C i ∩ P ′ i , we have ˆ ( v ′ i e ) = 0, and moreover, by the construction of ˆ , it holds that ˆ ( v ′ i v i e ) = 0, implying e ∈ C i ∩ P i . Accordingly, C i ∩ P ′ i ⊆ C i ∩ P i holds for all i ∈ S , and thus, C i ∩ P i = C i ∩ P ′ i .

whose reported valuation is zero, the probability of assigning e to agent i under reported profile (ˆ v ′ S , v ˆ -S ) is no greater than that under (ˆ v S , v ˆ -S ). Hence, the expected utility of agent i caused by the assignment of Step 3 does not decrease when agents S deviate their reporting from ˆ v S to ˆ v ′ S . As for Step 5, by Lemma 4.6, the expected utility here of agent i ∈ S under reported profiles (ˆ v ′ S , v ˆ -S ) and (ˆ v S , v ˆ -S ) is equal to 1 n v i ( ∪ q ∈ ¯ Q ′ e q ) and 1 n v i ( ∪ q ∈ ¯ Q q e ), respectively. Recall that ¯ Q ′ ⊆ ¯ , Q we have 1 n v i ( ⋃ q ∈ ¯ Q ′ e q ) ≥ 1 n v i ( ⋃ q ∈ ¯ Q e q ) as chores yield non-positive valuations. Therefore, for any agent i ∈ S , the expected utility of his under (ˆ v ′ S , v ˆ -S ) is at least that under (ˆ v S , v ˆ -S ).

## A.2.2 Proof of Lemma 4.8

For the sake of a contradiction, assume that there exist valuation functions ˆ v S = v S such that

$$\sum _ { i \in S } \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { * } ( \hat { v } _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] > \sum _ { i \in S } \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { * } ( v _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ].$$

/negationslash

Then we consider valuation functions ˆ v ′ S constructed as follows; for any i ∈ S and e ∈ E , if v i ( e ) = 0, then set ˆ ( v ′ i e ) = 0; otherwise, ˆ ( v ′ i e ) = ˆ ( ). v i e By Lemma 4.7, we know E A ∼ ˜ M ∗ (ˆ v ′ S ,v ˆ -S ) [ u i ( A , v i )] ≥ E A ∼ ˜ M ∗ (ˆ v S ,v ˆ -S ) [ u i ( A , v i )] for all i ∈ S . As a consequence, we can without loss of generality assume that for every agent i ∈ S , if v i ( e ) = 0, then ˆ ( v i e ) = 0. In other words, reported valuation functions ˆ v S only contain one type of misreporting; that is, some agent j ∈ S reports ˆ ( v j e ) = 0 on chore e while his true valuation is v j ( e ) = v e ( ) &lt; 0.

If ¯ Q b = ¯ , then we have Q

Let Q,Q ¯ and Q , Q b ¯ b be the corresponding index sets constructed in Step 2 of Algorithm 1 under reported profiles ( v S , v ˆ -S ) and (ˆ v S , v ˆ -S ), respectively. For every i ∈ S , define P i = { e ∈ E | v i ( e ) = 0 } and P b i = { e ∈ E | ˆ ( v i e ) = 0 } . Based on the aforementioned assumption, for any i ∈ S and e ∈ P i , it holds that e ∈ P b i . As reported valuations of agents N \ S are consistent, we have Q ⊆ Q b , equivalent to ¯ Q b ⊆ ¯ . Q

$$\Phi _ { \aleph } \, - \aleph, \, \text{var} \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m n } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \, \mathbb { m m } \\ \geq & \sum _ { i \in S } \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } ^ { * } ( \hat { \mathbf v } _ { S }, \hat { \mathbf v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ], \\ \dots$$

where the first equality transition is because the assignment of ⋃ q ∈ Q e q results in expected utility zero for every agent i ∈ S under the reported profile ( v S , v ˆ -S ) and the inequality transition is due to that chores allocated in Step 3 yields non-positive expected utility. The above inequality contradicts the construction of ˆ v S .

If ¯ Q b /subsetnoteql ¯ , Q as agents N \ S consistently report ˆ v -S , every item e q with q ∈ ¯ Q \ ¯ Q b must be allocated with probability one to one or a subset of agents in S under reported profile (ˆ v S , v ˆ -S ). As the set of indices ¯ corresponds to reported profile ( Q v S , v ˆ -S ), then for every chore e q with q ∈ ¯ , Q it holds that v i ( e q ) = v e ( q ) for all i ∈ S ; note that if v i ( e q ) = 0, then q ∈ Q . Hence, under ( v S , v ˆ -S ), the expected utility of agents S caused by assignment of Step 3 is equal to

zero, and we have the following:

$$\text{ero, and we have the following: } \\ \sum _ { i \in S } \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { * } ( v _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] & = \sum _ { i \in S } \frac { 1 } { n } v _ { i } ( \bigcup _ { q \in \tilde { Q } ^ { b } } e _ { q } ) + \sum _ { i \in S } \frac { 1 } { n } v _ { i } ( \bigcup _ { q \in \tilde { Q } \langle \tilde { Q } ^ { b } } e _ { q } ) \\ & = \sum _ { i \in S } \frac { 1 } { n } v _ { i } ( \bigcup _ { q \in \tilde { Q } ^ { b } } e _ { q } ) + \sum _ { i \in S } \frac { 1 } { n } v _ { i } ( \bigcup _ { q \in \tilde { Q } \langle \tilde { Q } ^ { b } } e _ { q } ) \\ & \geq \sum _ { i \in S } \frac { 1 } { n } v _ { i } ( \bigcup _ { q \in \tilde { Q } ^ { b } } e _ { q } ) + \sum _ { q \in \tilde { Q } \langle \tilde { Q } ^ { b } } v _ { i } ( e _ { q } ) \\ & \geq \sum _ { i \in S } \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { * } ( \hat { v } _ { S }, \hat { v } _ { - S } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ], \\ \text{there the second equality transition is due to } v _ { i } ( e _ { q } ) = v _ { i } ( e _ { q } ) \text{ for all } i \in S \text{ and } q \in \tilde { Q } ; \text{ the first}$$

where the second equality transition is due to v i ( e q ) = v e ( q ) for all i ∈ S and q ∈ ¯ ; Q the first inequality transition is due to | S | ≤ n and chores yielding non-positive valuation; the second inequality is owing to the fact that every item e q with q ∈ ¯ Q \ ¯ Q b is allocated with probability one to one or a group of agents in S under reported profile (ˆ v S , v ˆ -S ). The above inequality leads to a contradiction, completing the proof.

## A.2.3 Proof of Proposition 4.9

Let Q,Q ¯ be the sets of indices constructed in Step 2 under profile v = ( v , . . . , v 1 n ) and let A = ( A , . . . , A 1 n ) be the returned randomized allocation. Suppose A ′ = ( A , . . . , A ′ 1 ′ n ) = ( a ′ j,i ) j ∈ [ m,i ] ∈ [ n ] be the corresponding fractional allocation (matrix) implemented by A . As the assignment of Step 3 yields an expected utility zero for all agents, we the focus on the utility driven by the allocation of Step 5. Since permutation σ is generated uniformly at random, for any agent i and any item e q with q ∈ ¯ , Q the probability of assigning e q with agent i is equal to 1 n , and accordingly, a ′ q,i = 1 n for all q ∈ ¯ Q and i ∈ [ n ]. Then, agents' valuation in A ′ is v i ( A ′ i ) = v i ( A ′ j ) = 1 n · ∑ q ∈ ¯ Q v e ( q ) = v j ( A ′ j ) holds for all i, j ∈ [ n ] since v l ( e q ) = v e ( q ) for all q ∈ ¯ Q and all l ∈ [ n ]. Thus, fractional allocation A ′ is EF (and hence PROP) and EQ, and therefore, randomized allocation A is ex-ante EF (and hence PROP) and EQ.

For the ex-post fairness guarantee, let A ∗ = ( A , . . . , A ∗ 1 ∗ n ) be an arbitrary deterministic allocation in the support of A . We first show that A ∗ is EQ1. Note that v i ( e q ) = 0 holds for all i ∈ [ n ] and q ∈ Q , then the assignment of ⋃ q ∈ Q e q in Step 3 does not affect agents' value. Thus, when proving EQ1, it suffices to consider only the reduced instance with set of items E = ⋃ q ∈ ¯ Q e q and valuation functions v i ( e ) = v e ( ) &lt; 0 for every i ∈ [ n ] and e ∈ E . Let σ ∗ be the permutation in Step 5 corresponding the deterministic allocation A ∗ . Let the number of items be m = kn + d with k, d ∈ N and 0 &lt; d ≤ n , and hence, the assignment in Step 5 has k +1 rounds. Given two agents i, j ∈ [ n ], without loss of generality, we assume σ ∗ ( ) i &lt; σ ∗ ( j ). If agents i, j receive same number of items in A ∗ , then in every single round, agent i receives value no less than that of agent j , implying v i ( A ∗ i ) ≥ v j ( A ∗ j ). As for agent j , her value in every round l ≤ k -1 is at least the value received by agent i in round l +1. So by eliminating the last chore received by agent j , the value of agent j is at least that of agent i . Thus, for this

case, allocation A ∗ is EQ1. For the situation where agent i receives one more item, similarly the value received by agent j in every round l ≤ k is at least the value received by agent i in round l +1, implying v j ( A ∗ j ) ≥ v i ( A ∗ i ), i.e., agent j satisfies the property of EQ1. As for agent i , if the last item she receives is removed, she would have a value at least that of agent j . Therefore, allocation A ∗ is EQ1.

We next prove that A ∗ is also EF1. For any pair of agents i, j ∈ [ n ], we have

$$v _ { i } ( A _ { j } ^ { * } ) = v _ { i } ( A _ { j } ^ { * } \cap \bigcup _ { q \in \bar { Q } } e _ { q } ) + v _ { i } ( A _ { j } ^ { * } \cap \bigcup _ { q \in Q } e _ { q } ) = v ( A _ { j } ^ { * } \cap \bigcup _ { q \in \bar { Q } } e _ { q } ) = v _ { j } ( A _ { j } ^ { * } ),$$

where the second and the third equality transitions are due to the fact that for any agent l and any e q with q ∈ ¯ , Q v l ( e q ) = v e ( q ) holds. As A ∗ is EQ1, the following holds,

$$\max _ { e \in A _ { i } ^ { * } } v _ { i } ( A _ { i } \, \searrow \{ e \} ) \geq v _ { j } ( A _ { j } ^ { * } ) = v _ { i } ( A _ { j } ^ { * } ).$$

Therefore, allocation A ∗ is also EF1 (and hence PROP1).

## A.2.4 Proof of Proposition 4.10

Let Q,Q ¯ be the sets of indices constructed by Step 2 under profile v = ( v , . . . , v 1 n ) and let A = ( A , . . . , A 1 n ) be the returned randomized allocation, which implements fractional allocation (matrix) A ′ = ( A , . . . , A ′ 1 ′ n ) = ( a ′ j,i ) j ∈ [ m,i ] ∈ [ n ] . According to the proof of Proposition 4.9, for any agent i , his valuation in A ′ is v i ( A ′ i ) = 1 n ∑ q ∈ ¯ Q v e ( q ), which implies the utilitarian welfare UW ( A ′ ) = ∑ q ∈ ¯ Q v e ( q ) and egalitarian welfare EW ( A ′ ) = 1 n ∑ q ∈ ¯ Q v e ( q ). For an arbitrary fractional allocation B = ( B , . . . , B 1 n ), it holds that UW ( B ) ≤ ∑ q ∈ ¯ Q v e ( q ) as v i ( e q ) = v e ( q ) for all i ∈ [ n ] and all q ∈ ¯ . Q Moreover, by the pigeonhole principle, EW ( B ) ≤ 1 n ∑ q ∈ ¯ Q v e ( q ) holds. Therefore, we can claim that randomized allocation A is ex-ante UWM and EWM. By Proposition 4.3, allocation A is also ex-ante PO and ex-post UWM and PO.

It remains to show the ex-post guarantee regarding EWM. Let A ∗ = ( A , . . . , A ∗ 1 ∗ n ) be an arbitrary deterministic allocation in the support of A and σ ∗ be the permutation in Step 5 corresponding A ∗ . Without loss of generality, assume σ ∗ ( ) = i i for all i ∈ [ n ]. Similar to the proof of Proposition 4.9, we can further assume E = ⋃ q ∈ ¯ Q e q ; note that agents indeed have identical valuation functions over items ⋃ q ∈ ¯ Q e q . Let | E | = kn + d with k, d ∈ N and 0 &lt; d ≤ n , then each agent i ∈ [ d ] receives k +1 items and each agent i ≥ d +1 receives k items. Moreover, agent d receives the last item in Step 5. We now show v d ( A ∗ d ) ≤ v i ( A ∗ i ) for all i ∈ [ n ]. For i &lt; d , both agents d and i receive k +1 items and in each round, the value of agent i is at least the value of agent d , which implies v d ( A ∗ d ) ≤ v i ( A ∗ i ). For i &gt; d , agent i receives an item in rounds 1 , . . . , k and moreover for any l ∈ [ k ], the value of agent i in every round l is at least the value of agent d in round l + 1. Therefore, it holds that v d ( A ∗ d ) ≤ v i ( A ∗ i ) for all i ∈ [ n ] and thus EW ( A ∗ ) = v d ( A ∗ d ).

Denote by OPT E and by OPT U respectively the optimal utilitarian and egalitarian welfare among all deterministic allocations. We then show v d ( A ∗ d \ { e ′ } ) ≥ OPT E where e ′ is the last

item received by agent d . For a contradiction, assume v d ( A ∗ d \ { e ′ } ) &lt; OPT E . By Proposition 4.9, allocation A ∗ is EQ1, and thus for any i ∈ [ n ], v i ( A ∗ i ) ≤ max e ∈ A ∗ d v d ( A ∗ d \{ } e ) = v d ( A ∗ d \{ e ′ } ) holds where the equality transition is due to the allocation rule of Step 5. Accordingly, we have an upper bound of the optimal utilitarian welfare as follows,

$$\text{OPT} _ { U } = \text{UW} ( \text{A} ^ { * } ) = \sum _ { i \in [ n ] } v _ { i } ( A _ { i } ^ { * } ) \leq n \cdot v _ { d } ( A _ { d } ^ { * } \, \langle \, e ^ { \prime } \, \} ) + v _ { d } ( e ^ { \prime } ) < n \cdot \text{OPT} _ { E },$$

where the first equality transition is because A ∗ is ex-post UWM and the last inequality is due to our assumption v d ( A ∗ d \ { e ′ } ) &lt; OPT E and v d ( e ′ ) ≤ 0. However, since agents have identical valuations over ⋃ q ∈ ¯ Q e q , it must hold that OPT U ≥ n OPT E , contradicting the above inequality. Therefore, the claim v d ( A ∗ d \ { e ′ } ) ≥ OPT E is proved. Additionally, it is not hard to verify v i ( e ′ ) ≥ OPT E for all i ∈ [ n ] as agents have identical valuations over ⋃ q ∈ ¯ Q e q . Then, the following holds,

$$\text{EW} ( \mathbf A ^ { * } ) = v _ { d } ( A _ { d } ^ { * } ) = v _ { d } ( A _ { d } ^ { * } \, \sum \{ e ^ { \prime } \} ) + v _ { d } ( e ^ { \prime } ) \geq 2 \cdot \text{OPT} _ { E },$$

which completes the proof.

## A.2.5 Proof of Proposition 4.11

Let us consider the instance with n agents and a set E = { e , . . . , e 1 ( n -1) n +1 } of ( n -1) n + 1 chores. Agents have identical valuation functions: v i ( e j ) = v e ( j ) for all i, j , and inherent values are v e ( j ) = -1 for all j ≤ ( n -1) n and v e ( n n ( -1)+1 ) = -n . For any item e , we say e a β -chore if v e ( ) = -β for β ∈ { 1 , n } . Thus, there are n n ( -1) 1-chore and one n -chore. Denote by OPT E the optimal egalitarian welfare among all deterministic allocations, and naturally, OPT E ≤ -n as there must be an agent receiving the n -chore. Consider an allocation B in which every agent i ∈ [ n -1] receives a number n of 1-chore and agent n receives the unique n -chore. One can verify that min i ∈ [ n ] v i ( B i ) = -n and thus OPT E = -n .

Let σ ∗ with σ ∗ ( ) i = i for all i ∈ [ n ] be a deterministic permutation in Step 5 and A ∗ = ( A , . . . , A ∗ 1 ∗ n ) be the deterministic allocation returned by RandChore with respect to σ ∗ . Accordingly, A ∗ is a deterministic allocation in the support of ˜ M ∗ ( v ). By the allocation rule of Step 5, for any 2 ≤ i ≤ n , agent i receives a number n -1 of 1-chore and agent 1 receives a number n -1 of 1-chore and the unique n -chore. Thus, it holds that EW ( A ∗ ) = v 1 ( A ∗ 1 ) = -2 n +1 and therefore, the approximation of A ∗ towards the optimal egalitarian welfare is at least 2 -1 n , approaching 2 as n → + ∞ .

## A.2.6 Example in Freeman et al.

Consider an indivisible chores instance with four agents and eight chores. Agents have 2restricted additive valuations as shown in the following table.

For a contradiction, these exists an allocation A that is EQ1, EF1 and PO. Then, one can verify that both agents 1 and 2 get exactly one chore in A . Then a total of six chores are

|           | e 1   | e 2   | e 3   | e 4   | e 5   | e 6   | e 7   | e 8   |
|-----------|-------|-------|-------|-------|-------|-------|-------|-------|
| v 1 ( · ) | - 10  | - 10  | - 10  | - 10  | - 10  | - 10  | - 10  | - 10  |
| v 2 ( · ) | - 10  | - 10  | - 10  | - 10  | - 10  | - 10  | - 10  | - 10  |
| v 3 ( · ) | - 73  | - 1   | - 1   | - 1   | - 1   | - 1   | - 1   | - 1   |
| v 4 ( )   | 73    | 1     | 1     | 1     | 1     | 1     | 1     | 1     |

·

-

-

-

-

-

-

-

-

assigned between agents 3 and 4. Assume agent 3 gets at least three chores. Note that at least one of agents 1 and 2 does not receive e 1 in A , and therefore, agent 3 violates EF1 when comparing to that agent. For the detailed proof, we refer readers to (Freeman et al., 2020).

## A.3 For Section 5

## A.3.1 Proof of Lemma 5.3

Denote by { Q i } 3 i =0 and { Q k i } 3 i =0 , respectively, the corresponding indices sets constructed in Step 2 under reported profiles (ˆ v , v i ˆ 3 -i ) and (ˆ v k i , v ˆ 3 -i ). Let ∆ be the difference between expected utility of agent i under reported profile (ˆ v , v i ˆ 3 -i ) and that under (ˆ v k i , v ˆ 3 -i ), i.e.,

$$\Delta = \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { 2 } ( \hat { v } _ { i }, \hat { v } _ { 3 - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ] - \mathbb { E } _ { \mathbf A \sim \widetilde { \mathcal { M } } ^ { 2 } ( \hat { v } _ { i } ^ { k }, \hat { v } _ { 3 - i } ) } [ u _ { i } ( \mathbf A, v _ { i } ) ].$$

In what follows, we prove ∆ ≥ 0 by carefully checking possible combinations of ˆ ( v i e k ), ˆ v k i ( e k ) and ˆ v 3 -i .

## Case 1 : ˆ ( v i e k ) = v i ( e k ) = v e ( k ).

Subcase 1.1: ˆ ( v k i e k ) = 0 and ˆ v 3 -i ( e k ) = v e ( k ). Under these reported valuations, it holds that Q 0 = Q k 0 , Q i = Q k i , Q 3 -i = Q k 3 -i \ { e k } and Q 3 = Q k 3 ∪ { e k } . Then, by Proposition 5.2, we have ∆ = 1 2 v i ( e k ) = 1 2 v e ( k ) &gt; 0.

Subcase 1.2: ˆ ( v k i e k ) = 0 and ˆ v 3 -i ( e k ) = 0. Under these reported valuations, it holds that Q 0 = Q k 0 \ { e k } , Q i = Q k i ∪ { e k } , Q 3 -i = Q k 3 -i and Q 3 = Q k 3 . Similarly, by Proposition 5.2, we have ∆ = 1 2 v i ( e k ) = 1 2 v e ( k ) &gt; 0.

Subcase 1.3: ˆ ( v k i e k ) = 0 and ˆ v 3 -i ( e k ) = -c e ( k ). Under these reported valuations, the set of indices Q t is identical to Q k t for all t = 0 1 2 3, and therefore, ∆ = 0. , , ,

Subcase 1.4: ˆ ( v k i e k ) = -c e ( k ) and ˆ v 3 -i ( e k ) = v e ( k ). Under these reported valuations, the composition of { Q k t } 3 t =0 and of { Q t } 3 t =0 are identical to that of subcase 1.1, and accordingly, we also have ∆ = 1 2 v e ( k ) &gt; 0.

Subcase 1.5: ˆ ( v k i e k ) = -c e ( k ) and ˆ v 3 -i ( e k ) = 0. Under these reported valuations, it holds that Q 0 = Q k 0 , Q i = Q k i ∪ { e k } , Q 3 -i = Q k 3 -i \ { e k } and Q 3 = Q k 3 . Again, by Proposition 5.2, we have ∆ = v i ( e k ) = v e ( k ) &gt; 0.

Subcase 1.6: ˆ ( v k i e k ) = -c e ( k ) and ˆ v 3 -i ( e k ) = -c e ( k ). Under these reported valuations, it holds that Q 0 = Q k 0 , Q i = Q k i ∪ { e k } , Q 3 -i = Q k 3 -i and Q 3 = Q k 3 \ { e k } . According to Proposition 5.2, we have ∆ = 1 2 v i ( e k ) = 1 2 v e ( k ) &gt; 0.

Case 2 : ˆ ( v i e k ) = v i ( e k ) = 0. Note that reported valuations ˆ v i and ˆ v k i only differ on e k . According to RandMixed , deviating from (ˆ v , v i ˆ 3 -i ) to (ˆ v k i , v ˆ 3 -i ) only affects indices sets Q t 's and Q k t 's on whether includes e k or not. As the utility of e k of agent i is zero, one can verify that for Case 2, ∆ = 0 holds.

## Case 3 : ˆ ( v i e k ) = v i ( e k ) = -c e ( k ).

Subcase 3.2: ˆ ( v k i e k ) = v e ( k ) and ˆ v 3 -i ( e k ) = 0. Under these reported valuations, it holds that Q 0 = Q k 0 , Q i = Q k i \ { e k } , Q 3 -i = Q k i ∪{ e k } and Q 3 = Q k 3 . Then according to Proposition 5.2, we have ∆ = -v i ( e k ) = c e ( k ) &gt; 0.

Subcase 3.1: ˆ ( v k i e k ) = v e ( k ) and ˆ v 3 -i ( e k ) = v e ( k ). Under these reported valuations, it holds that Q 0 = Q k 0 , Q i = Q k i , Q 3 -i = Q k 3 -i ∪{ e k } and Q 3 = Q k 3 \ { e k } . By Proposition 5.2, we have ∆ = -1 2 v i ( e k ) = 1 2 c e ( k ) &gt; 0.

Subcase 3.3: ˆ ( v k i e k ) = v e ( k ) and ˆ v 3 -i ( e k ) = -c e ( k ). Under these reported valuations, it holds that Q 0 = Q k 0 , Q i = Q k i \ { e k } , Q 3 -i = Q k 3 -i and Q 3 = Q k 3 ∪ { e k } . Similarly, by Proposition 5.2, we have ∆ = -1 2 v i ( e k ) = 1 2 c e ( k ) &gt; 0.

Subcase 3.4: ˆ ( v k i e k ) = 0 and ˆ v 3 -i ( e k ) = v e ( k ). Under these reported valuations, we have Q k t = Q t for all t = 0 1 2 3, and accordingly, ∆ = 0 holds. , , ,

Subcase 3.5: ˆ ( v k i e k ) = 0 and ˆ v 3 -i ( e k ) = 0. Under these reported valuations, it holds that Q 0 = Q k 0 \ { e k } , Q i = Q k i , Q 3 -i = Q k 3 -i ∪ { e k } and Q 3 = Q k 3 . According to Proposition 5.2, we have ∆ = -1 2 v i ( e k ) = 1 2 c e ( k ) &gt; 0.

Subcase 3.6: ˆ ( v k i e k ) = 0 and ˆ v 3 -i ( e k ) = -c e ( k ). Under these reported valuations, it holds that Q 0 = Q k 0 , Q i = Q k i \ { e k } , Q 3 -i = Q k 3 -i and Q 3 = Q k 3 ∪ { e k } . Again, by Proposition 5.2, we have ∆ = -1 2 v i ( e k ) = 1 2 c e ( k ) &gt; 0.

## A.3.2 Proof of Proposition 5.5

Denote by { Q t } 3 t =0 the set of indices constructed in Step 2 under profile v = ( v , v 1 2 ) and by A = ( A , A 1 2 ) the returned randomized allocation. Suppose A ′ = ( A , A ′ 1 ′ 2 ) be the corresponding fractional allocation (matrix) implemented by A . According to Proposition 5.2, for any agent i ∈ [2], he receives a value v i ( A ′ i ) = 1 2 v i ( ⋃ q ∈ Q 0 ∪ Q 3 e q ) + v i ( ⋃ q ∈ Q i e q ) in fractional allocation A ′ . Moreover by arguments similar to that in the proof of Proposition 5.2, agent i 's value of A ′ 3 -i is equal to v i ( A ′ 3 -i ) = 1 2 v i ( ⋃ q ∈ Q 0 ∪ Q 3 e q ) + v i ( ⋃ q ∈ Q 3 -i e q ). Based on the definitions of Q i and Q 3 -i , for any i ∈ [2] and q ∈ Q i (resp., q ∈ Q 3 -i ), we have v i ( e q ) ≥ 0 (resp., v i ( e q ) ≤ 0). Accordingly, it holds that v i ( ⋃ q ∈ Q i e q ) ≥ v i ( ⋃ q ∈ Q 3 -i e q ), implying v i ( A ′ i ) ≥ v i ( A ′ 3 -i ). Thus, fractional allocation A ′ is EF (and hence PROP), and therefore, randomized allocation A is ex-ante EF (and hence PROP).

For the ex-post fairness guarantee, let A ∗ = ( A , A ∗ 1 ∗ 2 ) be an arbitrary deterministic allocation in the support of A . Fix an agent i . As v i ( e q ) = 0 for all q ∈ Q 0 , we have v i ( A ∗ i ) = v i ( A ∗ i ∩ ⋃ q ∈ Q i e q )+ v i ( A ∗ i ∩ ⋃ q ∈ Q 3 e q ) and v i ( A ∗ 3 -i ) = v i ( A ∗ 3 -i ∩ ⋃ q ∈ Q 3 -i e q )+ v i ( A ∗ 3 -i ∩ ⋃ q ∈ Q 3 e q ). By the definitions of Q i and Q 3 -i , we have v i ( A ∗ i ∩ ⋃ q ∈ Q i e q ) ≥ v i ( A ∗ 3 -i ∩ ⋃ q ∈ Q 3 -i e q ). As a consequence, it suffices to show that the partial allocation of items ⋃ q ∈ Q 3 e q satisfies EF1. Then by arguments

similar to that in the proof of Proposition 4.9, it is not hard to verify that the partial allocation upon ⋃ q ∈ Q 3 e q is EF1, and therefore allocation A is ex-post EF1 and PROP1.

## A.3.3 Proof of Proposition 5.6

According to Proposition 4.3, it suffices to prove only ex-ante UWM. Let { Q t } 3 t =0 be the set of indices constructed in Step 2 under profile v = ( v , v 1 2 ). Denote by A = ( A , A 1 2 ) the returned randomized allocation and by A ′ = ( A , A ′ 1 ′ 2 ) the corresponding fractional allocation implemented by A . It suffices to show that allocation A ′ achieves the maximum utilitarian welfare among all fractional allocations. As two agents have identical valuations on items ⋃ q ∈ Q 0 ∪ Q 3 e q , the utilitarian welfare derived from the assignment of ⋃ q ∈ Q 0 ∪ Q 3 e q must be identical among all (fractional) allocations. For every item e q with q ∈ Q 1 ∪ Q 2 , it is allocated to the agent with a larger value in allocation A ′ , and therefore, we can claim that no fractional allocation can achieve a utilitarian welfare larger than UW ( A ′ ).
Ankang Sun Bo Chen
Randomized Strategyproof Mechanisms with Best of Both Worlds Fairness and Efficiency
We study the problem of mechanism design for allocating a set of indivisible
items among agents with private preferences on items. We are interested in such
a mechanism that is strategyproof (where agents' best strategy is to report
their true preferences) and is expected to ensure fairness and efficiency to a
certain degree. We first present an impossibility result that a deterministic
mechanism does not exist that is strategyproof, fair and efficient for
allocating indivisible chores. We then utilize randomness to overcome the
strong impossibility. For allocating indivisible chores, we propose a
randomized mechanism that is strategyproof in expectation as well as ex-ante
and ex-post (best of both worlds) fair and efficient. For allocating mixed
items, where an item can be a good (i.e., with a positive utility) for one
agent but a chore (i.e., a with negative utility) for another, we propose a
randomized mechanism that is strategyproof in expectation with best of both
worlds fairness and efficiency when there are two agents.