Randomized Strategyproof Mechanisms
with Best of Both Worlds Fairness and Efficiency

Resource allocation is a fundamental issue that has obtained significant attention in the intersection of operations research, economics and computer science (Ibaraki and Katoh, 1988, Brandt et al., 2016, 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 platform (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 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¹¹1When money transfer is either infeasible or illegal in practice.) to achieve fair outcomes (Bezáková and Dani, 2005, Markakis and Psomas, 2011, Amanatidis et al., 2016, 2017). 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²²2No one envies another after hypothetically eliminating one good from the bundle of the latter. (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:

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” (Hylland and Zeckhauser, 1979, Babaioff et al., 2022, Aziz et al., pear, Akrami et al., 2023). 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?

Denote by $[k]=\{1,\ldots,k\}$ for any $k\in\mathbb{N}^{+}$. A set $E=\{e_{1},\ldots,e_{m}\}$ of $m$ indivisible items are to be allocated to a set $N=\{1,\ldots,n\}$ of $n$ agents. Each agent $i$ is associated with a valuation function $v_{i}:2^{E}\rightarrow\mathbb{R}$. An item $e$ is a good (resp., a chore) for agent $i$ if $v_{i}(e)\geq 0$ (resp., $v_{i}(e)\leq 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\neq i$. Agents are rational and can interact strategically towards making a collective decision. Let $\mathbb{A}$ be the set of outcomes or allocations. An allocation $\mathbf{A}=(A_{1},\ldots,A_{n})\in\mathbb{A}$ is an $n$-partition of $E$, that is, $A_{i}\cap A_{j}=\emptyset$ for any $i,j\in[n]$ with $i\neq j$ and $\bigcup_{i\in[n]}A_{i}=E$. Given an allocation $\mathbf{A}=(A_{1},\ldots,A_{n})$, for any $i\in[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\in[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 $\mathbb{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 $\mathcal{V}=V_{1}\times\cdots\times V_{n}$ the set of type profiles. A type profile is denoted by $\mathbf{v}=(v_{1},\ldots,v_{n})$. Additionally, each agent $i$ is associated with a utility function $u_{i}:\mathbb{A}\times V_{i}\rightarrow\mathbb{R}$. Given an outcome $\mathbf{A}$ and type $v_{i}\in V_{i}$, utility $u_{i}(\mathbf{A},v_{i})$ denotes the value or payoffs of agent $i$ under outcome $\mathbf{A}$ when his type is $v_{i}$. In this paper, we focus 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 $\mathbf{A}=(A_{1},\ldots,A_{n})$ can also be expressed as $u_{i}(A_{i},v_{i})$, equivalent to $v_{i}(A_{i})$.

The social choice function or mechanism is a mapping $\mathcal{M}:V_{1}\times\cdots\times V_{n}\rightarrow\mathbb{A}$ that assigns every possible type profile an outcome from set $\mathbb{A}$. We focus on direct mechanisms that elicit type information from agents by asking them to reveal their true valuations. After receiving reported profile $\hat{\mathbf{v}}=(\hat{v}_{1},\ldots,\hat{v}_{n})$, mechanism $\mathcal{M}$ outputs an allocation based on $\hat{\mathbf{v}}$. Given the combinatorial explosion, it is unrealistic for agents to report their valuations on every subset $T\subseteq E$. Consequently, we assume that valuation function $v_{i}$ is additive for all $i\in[n]$, that is, for any $T\subseteq E$, $v_{i}(T)=\sum_{e\in T}v_{i}(\left\{e\right\})$. For simple notations, we use $v_{i}(e)$, instead of $v_{i}(\{e\})$, to denote agent $i$’s valuation of item $e$. The set $\mathbb{A}$ of outcomes, the set $N$ of agents, the set $E$ of items and the type sets $\{V_{i}\}_{i\in[n]}$ are common knowledge, while type $v_{i}$ is private to agent $i$ only.

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\in[n]}$ are predetermined or unrelated to reported profiles and $\sum_{i\in[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})\in\{0,-1\}$ for all $i$ and $j$.

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

Now suppose for each $i\in[2]$, $\hat{v}^{\prime}_{i}$ is the type of agent $i$, i.e., $\hat{v}^{\prime}_{i}=v_{i}$. Then, if both agents report truthfully, $\mathcal{M}$ returns allocation $\mathbf{A}^{\prime}$ with $v_{1}({A}_{1}^{\prime})=-1$. However, if agent 1 misreports $\hat{v}_{1}$, then the outcome becomes $\mathcal{M}(\hat{v}_{1},\hat{v}^{\prime}_{2})=\mathbf{A}$, and the value of agent 1 in the allocation $\mathbf{A}$ is equal to $v_{1}(A_{1})=0$. Therefore, agent 1 has incentive to behave strategically, contradicting the strategyproofness of $\mathcal{M}$.  $\Box$

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.

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}),\ldots,v^{k}(e_{j})$ with $v^{t}(e_{j})<0$ for all $t\in[k]$, and for any agent $i$, his value of $e_{j}$ is $v_{i}(e_{j})\in\{0,v^{1}(e_{j}),v^{2}(e_{j}),\ldots,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})<0$. The restricted additive valuation has been studied in the literature on fair division and resulted in significant and challenging research questions (Bezáková and Dani, 2005, Asadpour et al., 2012, Akrami et al., 2022). Note that restricted additive functions 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). As type sets $\{V_{i}\}_{i\in[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 $\hat{v}_{i}(e_{j})\in\{0,v^{1}(e_{j}),v^{2}(e_{j}),\ldots,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>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.

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

For an arbitrary ex-ante PO randomized allocation $\widetilde{\mathbf{B}}$, let its support be $\{\mathbf{B}^{1},\ldots,\mathbf{B}^{k}\}$ with probability $p_{i}$ on deterministic allocation $\mathbf{B}^{i}$ for each $i\in[k]$. Moreover, let $\mathbf{B}^{\prime}$ be the fractional allocation implemented by $\widetilde{\mathbf{B}}$. For a contradiction, assume that there exists another deterministic allocation $\mathbf{B}^{k+1}$ that Pareto dominates $\mathbf{B}^{i}$ for some $i\in[k]$. Similarly, the fractional allocation $\mathbf{B}^{\prime\prime}=p_{i}\mathbf{B}^{k+1}+\sum_{j\neq i}p_{j}\mathbf{A}^{j}$ Pareto dominates $\mathbf{B}^{\prime}$, a contradiction. Therefore, allocation $\widetilde{\mathbf{B}}$ is ex-post PO.  $\Box$

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.

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 $\bar{Q}$ where for any $e_{j}$ with $j\in Q$, there exists some agent with reported value zero on $e_{j}$, while for any $e_{j^{\prime}}$ with $j^{\prime}\in\bar{Q}$, every agent $i$ reports $\hat{v}_{i}(e_{j^{\prime}})=v(e_{j^{\prime}})$. Then, for every $j\in Q$, $\mathsf{RandChore}$ assigns $e_{j}$ to an agent chosen uniformly at random with reported value $0$ on $e_{j}$. Items $\bigcup_{j\in\bar{Q}}e_{j}$ are then assigned to agents in a round-robin fashion based on a permutation $\sigma$ of $\{1,\ldots,n\}$ generated uniformly at random.

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 $\widetilde{\mathcal{M}}^{*}$ and $\mathsf{RandChore}$ interchangeably in this section.

Before proving Proposition 4.5, we first present several lemmas.

For any group $S$ of agents and any agent $i\in 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 $\hat{v}_{i}(e_{j})=v(e_{j})$.

Now we are ready to prove that $\mathsf{RandChore}$ is GSPIE.

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

We then show that $\mathsf{RandChore}$ also guarantees efficiency from the best of both worlds perspective.

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

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

We conclude this section by a discussion of possible extension of $\mathsf{RandChore}$. As demonstrated, $\mathsf{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 $\mathsf{RandChore}$ achieves the best that we can hope for in the $k$-restricted additive preference domain.

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})>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\in[n]}$ are common knowledge, and hence for any $q\in[m]$, inherent values $-c(e_{q})$ and $v(e_{q})$ are publicly known so that the reported valuation should be $\hat{v}_{i}(e_{q})\in\{-c(e_{q}),0,v(e_{q})\}$ for all $i\in[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 $\mathsf{RandMixed}$ and formally introduce it below (see Algorithm 2). A simple description of $\mathsf{RandMixed}$ is as follows. Based on reported profile $(\hat{v}_{1},\hat{v}_{2})$, partition $[m]$ into four parts $\{Q_{0},Q_{1},Q_{2},Q_{3}\}$. Assign items in $Q_{0}$ one-by-one to one of the two agents uniformly at random. For any $i\in\{1,2\}$, assign items $\bigcup_{q\in Q_{i}}e_{q}$ to agent $i$ and then assign items $\bigcup_{q\in Q_{3}}e_{q}$ to agents in a round-robin fashion based on a permutation $\sigma$ generated uniformly at random.

In what follows, we split the proof of Theorem 5.1, and for simplicity, we use $\widetilde{\mathcal{M}}^{2}$ and $\mathsf{RandMixed}$ interchangeably in this section.

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$. Then, for any reported valuation $\hat{v}_{i}\neq v_{i}$, one can start from $\hat{v}_{i}$ and reach $v_{i}$ by a sequence of corrections of the reported values for a single item, without decreasing the expected utility.

In the following, we show that $\mathsf{RandMixed}$ outputs allocations that guarantee ex-ante and ex-post fairness and efficiency.

Since randomness does not affect the running time of execution, the worst-case running time of $\mathsf{RandMixed}$ is $O(m)$. One may observe that mechanism $\mathsf{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.

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 $\mathsf{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.