Strategyproof and Approximately Maxmin Fair Share Allocation of Chores

1 Introduction

Multi-agent resource allocation is one of the major research topics in artificial intelligence [Bouveret et al., 2016]. We consider fair allocation algorithms of indivisible chores when agents have additive utilities. The fairness concept we use in this paper is the intensively studied and well-established maxmin share fairness. The maxmin fair share of an agent is the best she can guarantee for herself if she is allowed to partition the items but then receives the least preferred bundle.

In this paper we take a mechanism design perspective to the problem of fair allocation. We impose the constraint that the algorithm should be strategyproof, i.e., no agent should have an incentive for report untruthfully for profile of valuations. The research question we explore is the following one. When allocating indivisible chores, what approximation guarantee of maxmin share fairness can be achieved by strategyproof algorithms? This approach falls under the umbrella of approximation mechanism design without money that has been popularized by [Procaccia and Tennenholtz, 2013].

Maxmin share fairness was proposed by [Budish, 2011] as a fairness concept for allocation of indivisible items. The concept coincides with the standard proportionality fairness concept if the items to be allocated are divisible. There have been several works on algorithms that find an approximate MMS allocation [Procaccia and Wang, 2014; Amanatidis et al., 2015; Barman and Murthy, 2017; Ghodsi et al., 2018; Aziz et al., 2017]. None of these works took a mechanism design perspective to the problem of computing approximately MMS allocation. [Amanatidis et al., 2016] were the first to embark on a study of strategyproof and approximately MMS fair algorithms. Their work only focussed on the case of goods. There are many settings in which agents may have negative utilities such as when chores or tasks are allocated. In this paper, we revisit strategyproof fair allocation by considering the case of chores.

∗The authors are ordered alphabetically. This work is partially supported by NSF CAREER Award No. 1553385. The full version of the paper can be found at: https://arxiv.org/abs/1905.08925

1.1 Our results

We initiate the study of maxmin share (MMS) allocations of m indivisible chores among n strategic agents. It is assumed that all agents have underlying cardinal additive utilities over the chores. We consider three preference models in this work.

• Cardinal model: agents are asked to report their cardinal utilities over the items.
• Ordinal model: agents are only allowed or asked to express their ordinal rankings over the items.
• Public ranking model: all agents' rankings are public information and the agents are asked to report their utilities that are consistent the known ordinal rankings.

First, for cardinal and ordinal models, we design a deterministic sequential picking algorithm SequPick, which is strategyproof and unexpectedly achieves an approximation of O(log mn )1 . Roughly speaking, given an order of the agents, a sequential picking algorithm lets each agent i pick ai items and leave. [Amanatidis et al., 2016] proved that when the items are goods, the best a sequential picking algorithm can guarantee is an approximation of ⌊(m-n+2)/2⌋, and such an approximation can be easily achieved by letting each of the first n-1 agents select one item and allocating all the remaining items to the last agent. Compared to their result, we show that by carefully selecting the ai's, when items are chores, we are able to significantly improve the bound to O(log mn ).

Next, we further improve the approximation ratio for cardinal and ordinal models by randomized algorithms. Particularly, we show that by randomly allocating each item but allowing each agent to recognize a set of "bad" items and to be able to decline each allocated "bad" item once, the resulting algorithm is strategyproof and achieves an approximation ratio of O(√log n) in expectation.

1 In this paper we use log() to denote log2 ().

We complement these upper bound results with lower bound results by showing that for cardinal and ordinal models, no deterministic strategyproof algorithm has a better than 43 approximation. For the ordinal model, we prove that the lower bound of 43 cannot be improved by non-strategyproof algorithms. For randomized non-strategyproof algorithms, this bound cannot be improved to be better than 65 .

Finally, for the public ranking model, we show that the greedy round-robin algorithm is strategyproof and achieves 2-approximation. This is also surprising as when the items are goods, the best known approximation is O(n) by [Amanatidis et al., 2016]. When n ≤ 3, we give a strategyproof divide-and-choose algorithm that further improves this ratio to 3 2 . We complement these upper bound results by a lower bound of 65 for any deterministic strategyproof algorithms.

Our results as well as previous results for the case of goods are summarized in Table 1.

1.2 RelatedWork

MMS fairness is weaker than the proportionality fairness concept that requires that each agent gets at least 1/n of the total utility she has for the set of all items [Bouveret and Lemaˆıtre, 2016]. However for indivisible items, there may not exist an allocation that guarantees any approximation for the proportionality requirement.

Most of the work on fair allocation of items is for the case of goods although recently, fair allocation of chores [Aziz et al., 2017] or combinations of goods and chores [Aziz et al., 2018] has received attention as well. [Aziz et al., 2017] proved that MMS allocations do not always exist but can be 2-approximated by a simple algorithm. [Aziz et al., 2017] also presented a PTAS for relaxation of MMS called optimal MMS. [Barman and Murthy, 2017] presented an improved approximation algorithm for MMS allocation of chores.

Strategyproofness is a challenging property to satisfy for fair division algorithms. [Amanatidis et al., 2016] initiated the work on strategyproof goods allocation with respect to MMS fairness. In particular they proved the results covered in the goods part of Table 1. There is also work on the approximation of welfare that can be achieved by strategyproof algorithms for allocation of divisible items [Aziz et al., 2016].

2 Models and Preliminaries

For the fair allocation problem, N is a set of n agents, and M is a set of m indivisible items. The goal of the problem is to fairly distribute all the items to these agents. Different agents may have different preferences for these items and these preferences are generally captured by utility or valuation functions: each agent i is associated with a function vi : 2M →R that valuates any set of items.

MMS Fairness

Imagine that agent i gets the opportunity to partition all the items into n bundles, but she is the last to choose a bundle. Then her best strategy is to partition the items such that the smallest value of a bundle is maximized. Let Π(M) denote the set of all possible n-partitionings of M. Then the maxmin share (MMS) of agent i is defined as

If agent i finally receives a bundle of items with value at least MMSi, she is happy with the final allocation.

In this work, it is assumed that items are chores: vi({j}) ≤ 0 for all i ∈ N and j ∈ M. Then each agent actually wants to receive as few items as possible. For ease of analysis, we ascribe a disutility or cost function ci = -vi for each agent i. In this paper, we assume that the cost function of each agent i is additive. We represent each cost function ci by a vector (ci1, · · · , cim) where cij = ci({j}) is the cost of agent i for item j. Then for any S ⊆ M we have ci(S) = ∑j∈S cij. Agent i's maxmin share can be equivalently defined as

Note that the maxmin threshold defined in Equation 2 is positive which is the opposite number of the threshold defined in Equation 1. Throughout the rest of our paper, we choose to use the second definition. For each agent i, we use a permutation over M, σi : M → [m], to denote agent i's ranking on the items: ciσi(1) ≥ · · · ≥ ciσi(m). In other words, itemσi(1) is the least preferred item and σi(m) is the most preferred.

Let x = (xi)i∈N be an allocation, where xi = (xij)j∈M and xij ∈ {0, 1} indicates whether agent i gets item j under allocation x. A feasible allocation guarantees a partition of M, i.e., ∑i∈N xij = 1 for any j ∈ M. We somewhat abuse the definition and let Xi = {j ∈ M|xij = 1} and ci(x) = ci(xi) = ci(Xi). An allocation x is called an MMS allocation if ci(xi) ≤ MMSi for every agent i and α-MMS allocation if ci(xi) ≤ αMMSi for all agents i.

We first state the following simple properties of MMS (with proof deferred to the full version). Lemma 2.1 implies if an agent receives k items, then its cost is at most k ·MMSi.

Lemma 2.1 For any agent i and any cost function ci,

• MMSi ≥ 1n ci(M);
• MMSi ≥ cij for any j ∈M.

By Lemma 2.1, it is easy to see that if m ≤ n, any allocation that allocates at most one item to each agent is an MMS allocation. Thus throughout this paper, we assume m > n.

Models

In the cardinal model, the agents are asked to express their cardinal costs over M. A deterministic cardinal algorithm is denoted by a functionM : (Rm)n → Π(M). If an algorithm is restricted to only use the resulting rankings of the reported cardinal cost functions to allocate the items, we call it an ordinal algorithm and the corresponding problem is called the ordinal model. If the algorithm has the information of all agents' rankings by default, and every agent has to report her cost function with respect to the known ranking, the algorithm is called a public ranking algorithm and the corresponding problem is called the public ranking model. A deterministic algorithmM is called (α-approximate) MMS if for any cost functions, it always outputs an (α-) MMS allocation. A randomized algorithm M returns a distribution over Π(M) and is called α-approximate MMS if for any cost functions c1, · · · , cn, Ex∼M(c1,··· ,cn)[maxi∈N ci(x) MMSi ] ≤ α. 2

In this work, we study the situation when the costs are private information of the agents. Each agent may withhold her true cost function in order to minimize her own cost for the allocation. We call an algorithm strategyproof (SP) if no agent can unilaterally misreport her cost function to reduce her cost.

Formally, a deterministic algorithmM is called SP if for every agent i, cost function ci and the cost functions c-i of other agents, ci(M(ci, c-i)) ≥ ci(M(c′i , c-i)) holds for all c′i . We call a randomized algorithm M SP in expectation if for every i, ci and c-i, Ex∼M(ci,c-i)ci(x) ≥ Ex∼M(c′i ,c-i)ci(x) holds for all c′i .

Example 2.2 Suppose the cost function of an agent on four items is c1 = (1, 2, 3, 4). In an SP cardinal algorithm, reporting c1 minimizes her cost (in expectation, for randomized algorithm and the same for the following cases); In an SP ordinal algorithm, reporting c14 ≥ c13 ≥ c12 ≥ c11 minimizes her cost; In an SP public ranking algorithm, the algorithm knows c14 ≥ c13 ≥ c12 ≥ c11 by default, and the agent minimizes her cost by reporting c1.

2 Note that if the α-approximation is defined as for every agent i, Ex∼M(c1,··· ,cn)ci(x) ≤ αMMSi, the problem becomes trivial as uniform-randomly allocating all items optimizes α to be 1.

By the above definition, we have the following lemma immediately (with proof provided in the full version).

Lemma 2.3 An SP α-approximation algorithm for the ordinal model is also SP α-approximate for the cardinal model. An SP α-approximation algorithm for the cardinal model is also SP α-approximate for the public ranking model.

We end this section by providing a necessary condition of all SP algorithms for cardinal and public ranking models, which is mainly used to prove our hardness results. We prove Lemma 2.5 in the full version.

Definition 2.4 An allocation algorithmMis monotone if for any cost functions c1, · · · , cn and x = M(c1, · · · , cn), increasing cij for some xij = 0, or decreasing cij for some xij = 1 does not change xi.

Lemma 2.5 All SP algorithms are monotone.

3 Ordinal Model: Deterministic Algorithms

Before we present our algorithm for the ordinal model, we first discuss the limitation of deterministic ordinal algorithms.

Lemma 3.1 No deterministic ordinal algorithm (even nonSP) has an approximation ratio smaller than 4 3 , even for 2 agents and 4 items.

Proof: Consider the instance with 2 agents, whose ranking on the m = 4 items are identical. Without loss of generality, assume the item with maximum cost is given to the first agent, i.e. x11 = 1. If the first agent is allocated only one item, then for the case when c2 = (1, 1, 1, 1), the approximation ratio is 3 2 : the second agent has total cost 3 while MMS2 = 2. Otherwise for the case when c1 = (3, 1, 1, 1), the approximation ratio is at least 43 , as the first agent has total cost at least 3 + 1 = 4 while MMS1 = 3.

Next we present a deterministic sequential picking algorithm that is O(log mn )-approximate and SP. [Amanatidis et al., 2016] gave a deterministic SP ordinal algorithm which is O(m-n)-approximate when the items are goods. In the following, we show that if all the items are chores, it is possible to improve the bound to O(log mn ). Without loss of generality, we assume that n and mn are at least some sufficiently large constant. As otherwise it is trivial to obtain an O(1)- approximation by assigning mn arbitrary items to each agents.

Theorem 3.2 There exists a deterministic SP ordinal algorithm with approximation ratio O(log mn ).

SequPick. Fix a sequence of integers a1, . . . , an such that ∑i≤n ai = m. Order the agents arbitrarily. For i = n, n - 1, . . . , 1, let agent i pick ai items from the remaining items.

We note that as long as ai's do not depend on the valuations of agents, the rule discussed above is the serial dictatorship rule for multi-unit demands. When it is agent i's turn to pick items, it is easy to see that her optimal strategy is to pick the top-ai items with smallest cost, among the remaining items. Hence immediately we have the following lemma.

Lemma 3.3 For any {ai}i≤n, SequPick is SP.

It remains to prove the approximation ratio.

Lemma 3.4 There exists a sequence {ai}i≤n such that the approximation ratio of SequPick is O(log mn ).

Proof: We first establish a lower bound on the approximation ratio in terms of {ai}i≤n. Then we show how to fix the numbers appropriately to get a small ratio. Let r be the approximation ratio of the algorithm.

Consider the moment when agent i needs to pick ai items. Recall that at this moment, there are ∑j≤i aj items, and the ai ones with smallest cost will be chosen by agent i. Let c be the average cost of items agent i picks, i.e., ci(x) = c · ai. On the other hand, each of the ∑j≤i-1 aj items left has cost at

least c. Thus we have MMSi ≥ c · ⌈ a1+...+ai-1 n ⌉ and

It suffices to compute a sequence of a1, . . . , an that sum to m and minimizes this ratio. Fix K = 2 log mn . Let

Note that the first term of the min is to guarantee we leave enough items for the remaining agents. Moreover, truncating ai is only helpful for minimizing the approximation ratio and thus we only need to consider the case when ai equals the second term of the min. In the following, we show that

1. all items are picked: ∑i∈N ai =m;

Note that for i ≤ n2 , since agent i receives 2 items, the approximation ratio is trivially guaranteed.

The first statement holds because

and ai's will be truncated when their sum exceeds m.

For i > n2 , observe that (let l = i - n2 - 1)

We conclude the section by showing that our approximation ratio is asymptotically tight for SequPick.

Lemma 3.5 (Limits of SequPick) The SequPick algorithm (with any {ai}i∈N) has approximation ratio Ω(log mn ).

Proof: Fix K = 14 log mn . Suppose there exists a sequence of {ai}i∈N such that the algorithm is K-approximate.

Then the last agent to act must receive at most K items, i.e., a1 ≤ K. Next we show by induction on i = 2, 3, . . . , n that ai ≤ K(1 + 2K n )i-1 for all i ∈ N.

Suppose the statement is true for a1, . . . , ai. Then if ai+1 > K(1 + 2K n )i , we have

Thus we have ∑ni=1 ai ≤ n · ((1+ 2K n )n -1) ≤ n · (e2K - 1) < m, which is a contradiction, since not all items are allocated.

4 Ordinal Model: Randomized Algorithms

We have shown a logarithmic approximation algorithm SequPick for the problem. However, the algorithm may still have poor performance when the number of items is much larger than the number of agents, e.g., m = 2n . In this section we present a randomized O(√log n)-approximation ordinal algorithm, which is SP in expectation.

Again, before we show our algorithm, let us first see a limitation of the randomized ordinal algorithms.

Lemma 4.1 No randomized ordinal algorithm (even non-SP) has approximation ratio smaller than 6 5 , even for 2 agents and 4 items.

Proof: Consider the instance with 2 agents, whose ranking on the m = 4 items are identical. Let p be the probability that the algorithm assigns 2 items to both agents.

If p ≤ 3 5 , consider the instance with evaluation (1, 1, 1, 1), for which MMS1 = MMS2 = 2. Then with probability 1-p, the agent receiving at least 3 items has cost at least 32 times its maxmin share, which implies that the expected approximation ratio is at least p+ (1 -p) · 32 = 3 2 - p2 ≥ 6 5 .

If p > 35 , then consider the instance with evaluation (3, 1, 1, 1), for which MMS1 = MMS2 = 3. Then with probability p, the agent receiving the item with cost 3 has cost at least 43 times its maxmin share, which implies an expected approximation ratio at least p · 43 + (1 - p) = 1 + p3 ≥ 65 .

Basically, if we randomly allocate all the items, one is able to show that the algorithm achieves an approximation of O(logn). The drawback of this na¨ıve randomized algorithm is that it totally ignores the rankings of agents. In the following, we show that if the agents have opportunities to decline some "bad" items, the performance of this randomized algorithm improves to O(√logn). Note that since we already have an O(log mn )-approximate deterministic algorithm for the ordinal model, it suffices to consider the case when m ≥ n log n.

RandDecl. Let K = ⌊n√logn⌋. Based on the ordering of items submitted by agents, for each agent i, label the K items with largest cost as "large", and the remaining to be "small". It can be also regarded as each agent reports a set Mi of large items with |Mi| = K. The algorithm operates in two phases.

• Phase 1: every item is allocated to a uniformly-atrandom chosen agent, independently. After all allocations, gather all the large items assigned to every agent into set Mb. Note that Mb is also a random set.
• Phase 2: Redistribute the items in Mb evenly to all agents: every agent gets |Mb| n random items.

Theorem 4.2 There exists a randomized SP ordinal algorithm with approximation ratio O(√log n).

We prove Theorem 4.2 in the following two lemmas.

Lemma 4.3 In expectation, the approximation ratio of Algorithm RandDecl is O(√logn).

Proof: We show that with probability at least 1 - 2n , every agent i receives a collection of items of cost at most O(√logn) · MMSi. Fix any agent i. Without loss of generality, we order the items according to agent i's ranking, i.e., σi(j) = j for any j ∈ M and ci1 ≥ · · · ≥ cim.

For ease of analysis, we rescale the costs such that

Note that after the scaling, agent i's maxmin share is MMSi ≥ √logn. Let xij denote the random variable indicating that the contribution of item j to the cost of agent i in phase 1. Then for j > K, we have xij = cij with probability 1n , and xij = 0 otherwise. For j ≤ K, xij = 0 with probability 1. Note that

Moreover, we have cij ≤ 1 for j > K, as otherwise we have the contradiction that ∑Kj=1 cij > K. Note that {xij}j≤m are independent random variables taking value in [0, 1]. Hence by Chernoff bound we have

Then by union bound over the n agents, we conclude that with probability at least 1- 1n , every agent i receives a bundle of items of cost at most O(√log n) · MMSi in phase 1.

Now we consider the items received by an agent in the second phase. Recall that the items Mb will be reallocated evenly. By the second argument of Lemma 2.1, to show that every agent i receives a bundle of items of cost O(√logn) · MMSi in the second phase, it suffices to prove that |Mb| = O(n√log n) (with probability at least 1 - 1n ).

Let yj ∈ {0, 1} be the random variable indicating whether item j is contained in Mb. For every item j, let bj = |{k : j ∈ Mk}| be the number of agents that label item j as "large". Then we have yj = 1 with probability bj n . Since every agent labels exactly n√log n items, we have

Applying Chernoff bound we have

Thus, with probability at least 1- 2n , every agent i receives a bundle of items with cost O(√logn · MMSi) in the two phases combined. Since in the worse case, i receives a total cost of at most n · MMSi, in expectation, the approximation ratio is (1 - 2n ) · O(√log n) + 2n · n = O(√log n).

Lemma 4.4 RandDecl is SP in expectation.

Proof: To prove that the algorithm is SP in expectation, it suffices to show that for every agent, the expected cost it is assigned is minimized when being truthful. Let K = n√log n and fix any agent i. Suppose ci1, . . . , ciK are the costs of items labelled "large" by the agent; and ci,K+1, . . . , cim are the remaining items. Then the expected cost assigned to the agent in the first phase is given by 1n ∑mj=K+1 cij, as every item is assigned to the agent with probability 1n . Now we consider the cost the agent is assigned in the second phase.

Recall that the expected total cost of items to be reallocated in the second phase is E[∑j∈Mb cij] = ∑mj=1 cij · bj n , where bj is the number of agents that label item j "large". Let E be this expectation when agent i does not label any item "large".

By labelling ci1, . . . , ciK "large", agent i increases the probability of each item j ≤ K being included in Mb by 1n . Thus it contributes an 1n ∑Kj=1 cij increase to the expectation

of total cost of Mb. In other words, we have

Since a random subset of |Mb| n items fromMb will be assigned to agent i, the expected total value of items assigned to the agent in the two phases is given by

Obviously, the expression is minimized when ci1 + . . . + ciK is maximized. Hence every agent minimizes its expected cost by telling the true ranking over the items.

5 Cardinal Model

First, we present a lower bound on the approximation ratio for the all deterministic SP cardinal algorithms.

Lemma 5.1 No deterministic cardinal SP algorithm has approximation ratio smaller than 43 , even for 2 agents and 4 items.

Proof: First, consider c1 = c2 = (3, 1, 1, 1), for which MMS1 = MMS2 = 3. To obtain an approximation smaller than 43 , the only possible allocation is to assign the first item to some agent, and the remaining items to the other. Without loss of generality, suppose agent 1 receives the first item.

By monotonicity of SP algorithms (Lemma 2.5), for the case when c1 = (1, 3, 1, 1) and c2 = (3, 1, 1, 1). The assignment remains unchanged. Now we consider the profile when c1 = (1, 3, 1, 1) and c2 = (2, 2, 1, 1).

Note that we also have MMS1 = MMS2 = 3, and thus (to guarantee the approximation ratio) agent 2 cannot receive the last three items. Moreover, to guarantee SPness, agent 2 cannot receive a proper subset of the last three items, as otherwise agent 2 will misreport (2, 2, 1, 1) when its true value is (3, 1, 1, 1). Thus the first item must be assigned to agent 2, and consequently the second item must be assigned to agent 1. To guarantee the approximation ratio, agent 1 should not receive any other item, which means that agent 2 must receive the last two items, which violates the better-than- 43 approximation ratio.

For positive results, by Lemma 2.3, both algorithms in Sections 3 and 4 apply to the cardinal model. Thus we immediately have the following.

Corollary 5.1 For the cardinal model, there exists a deterministic SP algorithm with approximation ratio O(log mn ); and a randomized SP-in-expectation algorithm with approximation ratio O(√log n).

6 Public RankingModel

[Amanatidis et al., 2016] provided a deterministic SP public ranking algorithm which is O(n)-approximate if the items are goods. In this section, we show that if the items are chores, we can do much better.

6.1 Strategyproof Algorithms

We first give a simple SP algorithm with an approximation ratio of at most 2 and its proof is deferred to the full version.

RounRobi. For an arbitrary order of the agents, let the agents pick items in the round-robin manner.

Theorem 6.1 For the public ranking model, RounRobi is SP and has an approximation ratio of 2 - 1n .

By Theorem 6.1, when n = 2 and 3, the algorithm gives a 3 2 and 53 approximations, respectively. Indeed, for n = 3, we show a divide-and-choose algorithm which is SP and still guarantees 3 2 -approximation ratio.

Theorem 6.2 For the public ranking model, there exist an SP 1.5-approximation algorithm when n = 3.

Proof: Without loss of generality, we order the items according to agent 1's ranking, i.e., σ1(j) = j for any j ∈ M and c11 ≥ · · · ≥ c1m. The algorithm runs as follows:

• Let S1 = {1}, S2 = {j ∈ M|j mod 2 = 0} and S3 = {j ∈ M|j > 1 and j mod 2 = 1}. Note that (S1, S2, S3) is a partition of all the items.
• Let agent 2 select her favourite bundle from S1, S2, S3.
• Let agent 3 select her favourite one from the two bundles left in Step 2, and assign the last bundle to agent 1.

It is easy to see that the above algorithm is SP as the algorithm does not use any information reported by agent 1 and both of agent 2 and agent 3's best strategy is to report the costs such that the bundle with smallest cost is selected. We are left to prove the approximation ratio.

For agent 1, note that c1(S1 ∪ S3) ≥ c1(S2) ≥ c1(S3). By the first argument of Lemma 2.1, c1(S3) ≤ c1(S2) ≤ 1 2 c1(M) ≤ 3 2 ·MMS1. By the second argument of Lemma 2.1, c1(S1) ≤ MMS1. That is, no matter which bundle is left, the cost of this bundle is at most 3 2 · MMS1 to agent 1.

As agent 2 gets her best bundle, her cost is at most MMS2. For agent 3, since she is still able to select one from two bundles, her cost for the better bundle is at most 12 · c3(M) which is at most 3 2 · MMS3 by Lemma 2.1.

In conclusion, the algorithm is a 32 -approximation.

6.2 Limitation of Strategyproof Algorithms

Next, we complement the upper bound results with a lower bound result for the the public ranking model.

Lemma 6.3 For the public ranking model, no deterministic SP algorithm has an approximation ratio smaller than 65 , even for 2 agents.

Proof: Let n = 2 and m = 6. Assume for contradiction that there exists some SP algorithm with approximation ratio less than 65 . Suppose c1 = (1, 1, 1, 1, 1, 1) and c2 = (1, 1, 1, 1, 1, 1), then we have MMS1 = MMS2 = 3. The algorithm must assign every agent exactly 3 items, as otherwise the cost for one of them is 4 ≥ 65 · 3. Without loss of generality, assume that A1 = {1, 2, 3} and A2 = {4, 5, 6}.

By Lemma 2.5, when c1 = (1, 1, 1, 1, 1, 5) and c2 = (1, 1, 1, 1, 1, 1), the assignments remain unchanged, i.e., A1 = {1, 2, 3}. If we further increase c26 to 5, we have MMS1 = MMS2 = 5. If {6} ⊆ A2, we should have A2 = {6} to guarantee an approximation ratio less than 65 . Then we know that agent 2 has incentive to lie when its true cost is c2 = (1, 1, 1, 1, 1, 1). Hence we have {6} ⊆ A1, which implies A1 = {6} and A2 = {1, 2, 3, 4, 5}. Again, by Lemma 2.5, for c1 = (1, 1, 1, 1, 1, 3) and c2 = (1, 1, 1, 1, 1, 5), the assignment remains unchanged.

Applying a similar argument, for c1 = (1, 1, 1, 1, 1, 3) and c2 = (1, 1, 1, 1, 1, 1), we have A1 = {1, 2, 3}. Then for c1 = (1, 1, 1, 1, 1, 3) and c2 = (1, 1, 1, 1, 1, 3), we have {6} ⊆ A1, |A1| ≤ 2, and c2(A2) = 4 to guarantee an approximation ratio less than 65 . Thus by Lemma 2.5, for c1 = (1, 1, 1, 1, 1, 3) and c2 = (1, 1, 1, 1, 1, 5), the assignment does not change, i.e., |A2| = 4, which contradicts the conclusion we draw in the previous paragraph.

7 Conclusion

In this paper, we initiated the study of strategyproof and approximately maxmin fair algorithms for chore allocation. Our study leads to several new questions. The most obvious research question is to close the gaps between the lower and upper approximation bounds for SP algorithms and to study the lower bound of randomized SP cardinal algorithms.

At present we have two parallel lines of research for goods and chores. It is interesting to consider similar questions for combinations of goods and chores [Aziz et al., 2018]. Another interesting direction is to study the strategyproof fair allocation algorithms for the case of asymmetric agents [Aziz et al., 2019; Farhadi et al., 2019].