Fair and Efficient Allocations Without Obvious Manipulations
Authors: Alexandros Psomas
Paritosh Verma
Venue: NeurIPS 2022 Accept (2022)
Keywords: mechanism design
fair division

Abstract: We consider the fundamental problem of allocating a set of indivisible goods among strategic agents with additive valuation functions. It is well known that, in the absence of monetary transfers, Pareto efficient and truthful rules are dictatorial, while there is no deterministic truthful mechanism that allocates all items and achieves envy-freeness up to one item (EF1), even for the case of two agents. In this paper, we investigate the interplay of fairness and efficiency under a relaxation of truthfulness called non-obvious manipulability (NOM), recently proposed by~\citep{troyan2020obvious}. We show that this relaxation allows us to bypass the aforementioned negative results in a very strong sense. Specifically, we prove that there are deterministic and EF1 algorithms that are not obviously manipulable, and the algorithm that maximizes utilitarian social welfare (the sum of agents' utilities), which is Pareto efficient but not dictatorial, is not obviously manipulable for $n \geq 3$ agents (but obviously manipulable for $n=2$ agents). At the same time, maximizing the egalitarian social welfare (the minimum of agents' utilities) or the Nash social welfare (the product of agents' utilities) is obviously manipulable for any number of agents and items. Our main result is an approximation preserving black-box reduction from the problem of designing EF1 and NOM mechanisms to the problem of designing EF1 algorithms. En route, we prove an interesting structural result about EF1 allocations, as well as new ``best-of-both-worlds'' results (for the problem without incentives), that might be of independent interest.

Fair and Efficient Allocations Without Obvious Manipulations
Alexandros Psomas Purdue University apsomas@cs, purdue. edu
Paritosh Verma Purdue University verma1360purdue edu
Abstract
We consider the fundamental problem of allocating of indivisible goods among strategic agents with additive valuation functions. It is well known that, in the ab- sence of monetary transfers, Pareto efficient and truthful rules dictatorial, while there no deterministic truthful mechanism that allocates all items and achieves envy-freeness up to one item (EF1), even for the case of two agents, In this paper, we investigate the interplay of fairness and efficiency under relaxation of truthful- ness called non-obvious manipulability (NOM), recently proposed by [TM20]. We show that this relaxation allows us to bypass the aforementioned negative results in a very strong sense. Specifically, we prove that there are deterministic and EF1 algorithms that are not obviously manipulable, and the algorithm that maximizes utilitarian social welfare (the sum of agents' utilities), which is Pareto efficient but not dictatorial, is not obviously manipulable for n 2 3 agents (but obviously manipulable for n agents). At the same time, maximizing the egalitarian social welfare (the minimum of agents' utilities) or the Nash social welfare (the product of agents' utilitics) is obviously manipulable for any number of agents and items. Our main result is approximation preserving black-box reduction from the problem designing EFI and NOM mechanisms to the problem of designing EFI algorithms. En route,
prove interesting structural result about EFI allocations, as well as new "fest-of-both-woolde results (for the problem without incentives), that might be of independent interest.
Introduction
We consider the fundamental problem of allocating set of indivisible items among strategic agents with additive preferences. is well-understood that, in the absence of monetary transfers, fairness, effi- ciency and truthfulness cannot be reconciled, in very strong sense. For example, serial dictatorship (arguably the most unfair rule) is the unique truthful and Pareto efficient mechanism [KM02, EK03], even for the of two agents and randomized mechanisms (or, equivalently, divisible items) [Sch96]. At the same time, achieving envy-freeness up to one item (EF1) [Bud] I], a popular fairness notion for indivisible goods that compatible with Pareto efficiency [CKM 19], impossible for truthful and deterministic mechanisms to achieve, even for two additive agents [ABCM17].
The standard abstraction for strategic agent assumes that, when presented with algorithm, the agent will perfectly understand it and optimally respond to it. Therefore, a truthful mechanism should protect against all deviating strategies. This modeling is overly pessimistic since, for example, in practice agents do not have exact knowledge about others' preferences. Since truthfulness rules out reasonable solutions, previous work typically ignores strategic issues altogether. In this paper aim to escape the aforementioned impossibility results by relaxing truthfulness: our goal is to design mechanisms that protect only against obviously dominanl deviating strategies.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Informally, a strategy is obviously dominant if it guarantees an outcome better than any outcome of every other strategy [Li17]. Designing obviously truthful mechanisms, those where honest reporting is obviously dominant, is problem that has attracted significant attention in recent years [AG18, KV19, FV19, AMN20J. Since dishonesty also a strategy, a deviation can be profitable but not obviously profitable. A manipulation is obvious if it yields higher utility than truth-telling in either the best or worst-case scenarios. Seminal work of [TM20] defines this notion, and shows that relaxing truthfulness to non-obvious manipulability can strictly improve the designer's objective in a number of domains (e.g. two-sided matching). In this paper we aim to provide a comprehensive study of what can and what cannot be achieved by non-obviously manipulable mechanisms in the fundamental domain of fair and efficient allocation of indivisible goods.
Our Contribution. We first consider the problem of designing a non-obviously manipulable mechanism (NOM) which always outputs allocations that are envy-free up to one item (EF1), a task that is impossible for truthful mechanisms to achieve [ABCM17]. We prove that the Round- Robin procedure (agents choose items one at a time, following a fixed order) which is known to always output EFI allocations, is also not obviously manipulable (Theorem 1), giving separation between truthfulness and non-obviously manipulability for our problem. In fact, we show that NOM is compatible with even stronger notions of fairness. Specifically, randomized algorithm can be ex-post EFI (i.e. the output allocation is always EFI), and simultaneously be envy-free in expectation (ex ante EF). There are known algorithms that satisfy this "best-of- se--bohhhwwllee guarantee (FSV20, Azi20b]; we show that the PS-Lottery algorithm of [Azi20b] is not-obviously manipulable. This result uses connection between ex-ante proportionality and not obvious manipulability; we later exploit this connection to establish new negative -fosh-o--bothwwordds results.
We proceed to study efficient algorithms. We focus on the three most prominent notions of efficiency: utilitarian social welfare (the sum of agents' utilities), egalitarian social welfare (the minimum of agents' utilities), and Nash social welfare (the geometric mean of agents' utilities). For the case of n = 2 agents all three notions are incompatible with non obvious manipulability, i.e. every (deterministic or randomized) algorithm that always outputs an integral solution that is optimal with respect to any of these objectives is obviously manipulable (Theorem 2). This is also true for the case of more than three agents for egalitarian and Nash social welfare (Theorems 8 and 4). The high level intuition for these impossibilities is as follows. There are instances where a specific agent' gets only her least favorite item, in the worst-case. However, maximizing egalitarian Nash social welfare ensures that the number of agents that get non-zero utility are maximized. Therefore, by reporting that she only values single item (her favorite item) to the mechanism, this agent can force the mechanism to give her this item (or increase the probability that she gets it) in the worst-case. Note that lack of agents' knowledge about each others' preferences is used as a justification for why manipulations might not be first-order concern in our domain [CKM* 19]; the fact that maximizing Nash social welfare is manipulable even when agents know nothing about each other further highlights the need for more nuanced formal models between "agents are always honest" and "agents are perfectly rational and all- kn-winnwing expected utility maximizers." " Surprisingly, the same not true for utilitarian social welfare: there is a NOM mechanism that always outputs an allocation that maximizes utilitarian social welfare for the case of n 2 3 agents (Theorem 3). This gives an efficient and not obviously manipulable mechanism that is not dictatorial.
Since maximizing Nash social welfare, an objective that simultaneously achieves Pareto efficiency and EFI, is obviously manipulable, the next natural question is whether there are any other Pareto efficient and EFI algorithms that satisfy NOM. Our main result answers this question in the affirmative. In fact, we prove that the problem of designing a Pareto efficient, EFI and NOM mechanism is exactly as hard as designing a Pareto efficient and EFI algorithm. We give black-box reduction, that preserves Pareto efficiency guarantees, which given an algorithm that always outputs (clean and wastefll) EFI allocations, outputs a mechanism that is not obviously manipulable and always outputs EFI allocations. There are two crucial steps in our reduction. Given the valuation function V; of agent i, let EF v;) be the set of allocations that are clean, non- non-wasteful and EF1 for agent First, our reduction ensures that, when agent i reports her valuation to be b, every single allocation in EF b,) is possible, i.e. for every allocation A E EFI(i, by) there are reports for the other agents such that A is the output of the mechanism. Second, we prove the following intuitive structural result, that might be of independent interest. For an agent i having valuation function v., the worst-case allocation in EF1(i, v.) is better than the worst-case allocation in EF1(i. b.) (Lemma 4). These facts
Informally, the agent that the tie- brebkink rule favors.

---

Table 1: Existence of NOM mechanisms for various fairness and efficiency notions.
Fairness & Efficiency Notions
Existence of NOM Mechanism
EFI
[Theorem 1]
Ex-ante EF & Ex- EFI
[Theorem 7]
Utilitarian Social Welfare
n = 2 agents
[Theorem 2]
/ n 2 3 agents
[Theorem 3]
Egalitarian Social Welfare
X [Theorem 8]
Nash Social Welfare
[Theormm 4]
fPO EFI
/ [Theorem 5]
Ex-ante EF & Ex-posI IPO EFI
X
[FSV20]
combined establish the "worst-case" part from the definition of NOM, which is the most challenging step. As a direct application of our reduction, by giving as input the algorithmic results [GM21], get fractionally Pareto efficient, EFI and NOM mechanism for additive agents; this last result cannot be improved by adding ex ex-ante fairness guarantees (due to a theorem of [FSV20]. Finally, despite the aforementioned technical subtleties, the "code" of our reduction is fairly simple: it checks whether some allocations are EF1, and if not it calls the black-box algorithm. This simplicity is a feature, with concrete practical implications: by adding few lines of code to the implementation of any EFI and Pareto efficient algorithm (e.g. the algorithm that maximizes Nash social welfare, which is used by the popular website Spliddit [GP15]) one can maintain these guarantees, while provably protecting against certain types of manipulations.
Our results show a connection between certain notions of fairness and not obvious manipulability: positive algorithmic results for EF1 and "best-of-both-wee worlddd guarantees can be used to get positive results for not obviously manipulable mechanisms. In Appendix E cxploit this connection in the other direction, and show how negative results for not obviously manipulable mechanisms can be used to prove impossible to achieve ex-ante proportionality, ex-post Pareto efficiency while ex- ex-post maximizing the number of agents with positive utility. As direct corollaries recover known result of [FSV20] that ex-ante proportional and ex ex-post MNW allocations do not exist, as well as new results: is impossible to achieve ex-ante proportionality by randomizing over allocations that are (1) ex-post Pareto efficient and ex-post egalitarian, or (2) ex-post leximin.
negative results for
algorithms. Specifically, we prove that it
Related work. [TM20] define the notion of not obvious manipulability. They show that number of known mechanisms that are not truthful satisfy not obviously manipulability, c.g. stable mechanisms in the context of two-sided matching are not obviously manipulable (in direct contrast to [Rot82], who shows that there exists no mechanism that is both stable and truthful). At the same time, many known mechanisms that not truthful are obviously manipulable, e.g. the first-price auction, and more generally the pay-as-bil bid auction.
The notion of non obvious manipulability has been explored in some very recent works [OSH19, AL21J. [OSH19] study cake-cutting and show that, as opposed to truthfulness, NOM is compati- ble with proportionality: an adaptation of the well-known moving knife procedure satisfies both properties. They also observe that every proportional (direct revelation) rule satisfics the worst-case guarantee required for NOM (we show similar statement in Lemma 5), while every Pareto efficient (direct revelation) rule satisfies the best-case guarantee required for NOM. [AL21] 1] explore obvious manipulations in voting theory. They give sufficient conditions for voting rules to be not obviously manipulable, and show that a number of voting rules escape the pessimistic conclusions of the Sebbard-Satterther
theorem, e.g., the Borda rule is not obviously manipulable.
Other than relaxing the notion of incentive compatibility, one can escape the aforementioned im- possibility results by restricting agents' valuations, e.g. focus on dichotomous [HPPS20, BEF21, BCIZ21, BV21] or Leontief valuations [GZH+11, FGP14, PPS15], or by using money-burning (wasting resources) substitute for payments [HR08, CGG13, FTTZ16, 1GPS19, ACGH20).
3

---

2 Preliminaries
We consider the problem of allocating set M of m items among a set N of agents with additive utilities. We use [k] to denote the set 21,2,... }} for any positive integer k E E4. Proofs pertaining to randomized mechanisms are deferred to the appendix; see Appendix A for the corresponding preliminaries on randomized allocations/meccanisns.
Allocations. A frrctionaal allocation A E [0, 1 is n matrix that defines for each agent E N and item j E M the fraction A of the item j that the agent receives. We represent a fractional allocation as A = (A1...., AA) where A; = .i.......,,,,... E [0, 1|TT denotes the fractions of all items allocated to agent i. A feasible allocation satisfies Vien Ai, S 1, for all j E M. A fractional allocation A is integral if A; E {0, 1 for all agents i E N. An integral allocation can be equivalently defined as n disjoint subsets of the set of items M. this representation is often convenient. Let (M) = {(S S,) - S C M and Vi * j. S S = o} denote the set of all n integral allocation A = (A1,...
ordered disjoint subsets of the set of items M. Given Ai,, as subsets of items A; == {j E M A =1]. This allows us to view integral allocation A as ordered disjoint subsets of items, ie., A II, (M). An integral allocation A is complete if Uن= A; = M and partial if A C M. Unless stated otherwise, we will use the term allocation refer to complete allocations. We will use the term bundle to refer to any subset of items.
An), we
can interpret the binary vectors A, = (A
Each agent i E N has private valuation function v:(.) that outputs the utility that agent i derives from given set (or fractions) of items. We use the notation (X,) (resp. (A.)) to denote the utility that agent i gets from the items allocated to her in fractional allocation X (resp. integral allocation A). We consider agents with additive utilities. An additive agent E N has non-negative valuation Usyy for receiving the entirety of item j: her utility for an allocation X is (X,) = EjEM 2i.5 for an integral allocation A, the utility is simply v,,), = Σjen, Vz.j-
Preferences.
Mechanisms. A mechanism M clicits "bids" (i.e. reported valuations) b = (bi,..., br) from every agent i E N, and outputs a feasible allocation. We write (b) for the fraction of item j allocated to agent when each agent j E N reports a valuation by. We use the notation b (and b,) to refer to the input mechanism, and v (and v,) to refer to the true valuations of agents. A mechanism M is deterministic if for every reported valuations b it deterministically outputs an integral allocation. We will use M(b) (Mi (b), M2(b), ... M,, M..(b) (b)) to denote the integral allocation that mechanism M outputs given reported valuations b- = (b)..... : b,,) as input, here M,(b) S M represents the bundle of items that agent i receives in the allocation M(b. For a deterministic mechanism M, the value v. (b)) denotes the utility of agent for the allocation output by M on input b.
Notions of incentive compatibility. A mechanism M is truthful if agents cannot strictly improve their utility by misreporting their valuation, i.e. for all i E N, valuations vi, b, and reports of the other agents V-i, (V,,,,, v-))) 2 (b,,, v)). Our work focuses
notion of incentive compatibility that is a relaxation of truthfulness called not obvious manipulability.
Definition (Not Obviously Manipulable [TM20J). A mechanism M is not obviously manipulable (NOM) if for every agent E N with valuation function v,, and every possible report b, of agent i, the following two inequalities hold:
min (M, v))) 2 min v. (M, v.))..
(2) max ( V-1
max (M. V-1
Intuitively, if a mechanism is NOM then an agent cannot increase her worst-case utility or her best-case utility (computed with respect to the true valuation) by misreporting her valuation. If either the worst-case or the best-case utility can be improved then the mechanism is obviously manipulable.
Notions of efficiency. An integral allocation A= (Ai,..., An) is Pareto efficient (or PO) iff there is no integral allocation A' (A/, [A',.... A(,) such that for all agents i N, (AA) 2 (A,), and for at least one agent this inequality is strict. An (integral or fractional) allocation X = (X,...., X,, is fructionally Pareto efficient (or fPO) iff there is no fractional allocation X' = (Xi:..., X²) such that for all agents i E N. v; (X() 2 vx().), and for at least one agent this inequality is strict. Note that fractional Pareto efficiency a strictly stronger notion than Pareto efficiency. An (integral or fractional) allocation X is a-approximately (resp. fractionally) Pareto efficient if there is no integral

---

allocation (resp. fractional allocation) X' = (X, .x, such that a vX( 2 (X,),, with at least one of these inequalities strict [RF90, ILWM17, FGPS19, ZP20]. Notice that for a = 1 we exactly recover Pareto efficiency (resp. fractional Pareto efficiency).
A (partial) allocation A (A1, A2..... An) is non-wastefuu iff for each E N, Vi.j = 0 for every unallocated item j E M \ UKEN AR A bundle 5 M is clean for wrt valuation v; if the items comprising S have positive value, ie., vi(g) > 0 for all g E S. Further, a (partial) allocation A (Ai, (A1,A2,-.. ..,..., A,) is clean if for each i E N the bundle A, is clean wrt valuation V,.
Often, we are interested computing or approximating specific points (i.e., allocations) present on the Pareto frontier that have additional desirable properties. The utilitarian social welfare of an allocation X, denoted by (X),., is defined as the sum of utilities that each agent gets in the Cien V. (X.). The Nash social welfare of an (integral or fractional) allocation X, denoted by NSW (X), is defined as the geometric mean of the utilities of agents in the allocation X, i.e., (XW = (eT v; (x+))) An inlegral allocation that maximizes the Nash social welfare, among all integral allocations, is called a Nash social welfare maximizing (or MNW) allocation. There are instances where every integral allocation A is such that NSW (A) 0, i.e., there is always an agent having zero utility. To cover such an edge case, integral MNW allocations are defined follows [CKM+ + 19J. An integral allocation MNW iff (i) it maximizes, among the set of all integral allocations, the number of agents having positive utility and (ii) for any such maximal set of agents S, it maximizes the geometric mean of the utilities of agents in S.
allocation X, i... SW (WX)
Notions of fairness. An (integral or fractional) allocation X is called eny--rre (EF) for every pair of agents j,j E N, agent i values her allocation at least as much as the allocation of agent j. i... vx)) Achieving envy-freeness is impossible for integral allocations (consider the case )) 2 (x,)
of single item and two agents that both want it), so relaxation of envy-freeness are considered. An integral allocation A is envy-free up to one item (EF1) if for every pair of agents i, E N, where A₁ + 0, agent i values her allocation at least much the allocation of agent j, subject to the removal of one item from agent j's bundle, i.e., (A.) 2 (; \ {a}) for some item g E Aj.
Finally, we are often interested in, so called, best-of-both-woot or efficiency notion for integral allocations and Q be a fairness or efficiency notion for fractional allocations. A randomized allocation R (see Appendix A for definition), which outputs an integral allocation A with probability p², satisfies the notion P ex-post if each integral allocation A in the support of R satisfies P. Additionally, the randomized allocation R satisfies the notion Q ex-ante if the expected fractional allocation Y = E p² Aa corresponding to R. satisfies the notion Q.
guarantees. Let P be fairness
3 Fair Mechanisms
In this section we study whether non obvious manipulability is compatible with EFI. For deterministic mechanisms, is known that no truthful mechanism can always outputs an EFI allocation, even for the case of two agents [ABCM17]. In sharp contrast, we show that Round- arguably the simplest EFI algorithm, is not obviously manipulable. Recall that the Round-Rod -obnd algorithm allocates items agents over sequence of rounds. In each round. the agents choose one item each (a highest- value remaining item, as per their valuation") following a fixed, arbitrary order.
Theorem 1. Round- Robin is not obviously manipulable.
Proof. We prove that the two inequalities in Definition 1 hold for Round-Robin, Let i E N be the i-th agent in the Round-Robin order, and let v, her valuation vector. Assume without loss of generality that Va.j 2 Vi.++1 for all = 0, ...
1. Let é be the number of items agent i receives (either _ or 2 + 1, depending on i, n and m), and notice that E does not depend on her report.
We first prove inequality (1) from the definition of NOM, i.c. the worst-case guarantee. The k-th time agent gets pick an item, there is an un-allocated item that she values least (k since only (k- - 1)n + i items have been allocated at that point. Therefore, the worst-case for agent i under honest reporting is realized when all other agents rank the items in the same order as her, and her utility is exactly Ebm (1,i+(k-1)n Now consider the case when all agents other than i
2 Note that, every Pareto efficient (fractionally Pareto efficient) integral allocation is non-wastefull
'Ties can be broken in arbitrary manner.
5

---

rank items in the same order as i (i.e. v 2 J+1+1 for i' E N). and reports some vector b; Let Ji.....3. de be the items she receives, in the order she picked them. First, without loss of generality, picks these items in decreasing order with respect to her true valuation, i.e. viji 2 Vi.jo+1' picks an item k at round I, and a later round 1' she could pick an item k' with ui,." > Vi,k, then by the choice of valuation for agents other than i, picking k' in round and k in round E' is also possible.
1 if she
Second, Vi.jk I (k-1)()) when picks an item for the k-th time, (i - 1) + (k - 1)(n 1) of her top i (k- 1)n items have been picked by other agents, and k 1 of her top i+ (Is - 1)n items have been picked by herself (since items are picked in decreasing order with respect to the true valuation).
Therefore (k-i+((-1))e 1)n is the largest value U..j. can have; i's utility is at most Σ (k- Thus, the worst-case utility is maximized under truthful reporting.
Next, we prove inequality (2) (the best-case guarantee). Since agent gets exactly E items, her utility is at most Σi=1 U.k. This utility is realized when she reports v,, and everyone else ranks the items in the opposite order, i.e. y < 04 1 for all i', and it cannot be improved upon.
In fact, we can strengthen this result to give a "best-of-both-weee wooldd- NOM mechanism. Specifically, we prove that the PS-Lottery algorithm of [Azi20b], which outputs randomized allocations that are ex-ante EF and ex-post EF1, is NOM in expectation; proof has been deferred to Appendix B.
4 Efficient Mechanisms
In this section we study whether natural efficiency notions are compatible with NOM. We consider the three most popular notions of efficiency: utilitarian social welfare, Nash social welfare and egalitarian social welfare (see Appendix C). Under truthfulness, the only Pareto efficient and truthful algorithm is a dictatorship, which immediately implies that one cannot truthfully achieve any non-trin non-trivial approximations with respect to any of these notions. Omitted proofs can be found in Appendix C.
Utilitarian Social Welfare. We start by considering the utilitarian social welfare maximizing algorithm, i.e. the algorithm which allocates each item to the agent that values it the most. When the winner for an item is not unique the algorithm needs to break ties; the choice of the tie-breaking rule will be crucial for our positive result in this section. In the context of fair division it standard to assume that agents' values are normalized when analyzing utilitarian social welfare. Specifically, the most common assumption is that the agents' values add up to 1; see [Azi20a] for a number of justifications for this assumption. For the remainder of this section we also assume that ΣjEM Vt,5 = for all agents i.4 We note that without this assumption, the utilitarian social welfare maximizing algorithm is NOM, since no matter what an agent reports, the best case for her is that she wins all items she values positively, and the worst case is that she loses all items, misreport can help increase either the worst-case or best-case utility.
Theorem 2.
Every (randomized or deterministic) mechanism for n = agents that always oulputs utilitarian social welfare maximizing allocations is obviously manipulable.
Surprisingly, this impossibility result does not hold for more than two agents.
Theorem 3. The utilitarian social welfare maximizing algorithm, coupled with an appropriate tie-breaking rule, is not obviously manipulable for n 2 3 agents.
Proof. First, we describe our algorithm. The algorithm, given reports bj...., b allocates each item to an agent with the largest reported value. In case of a tie, the item is allocated the agent with the smallest index (i.e. 1 > 2 > .) except if the tie is exactly between agents and n, in which case the item goes to agent n. Consider an arbitrary agent í with true valuation V,.
Towards proving inequality (1), we have that if bi, < for all j E M, there exists a choice for v such that agent i does not have the highest value for any item (e.g., some agent & could have a value of 1 for i's favorite item, and a different agent k' can out-bid i in all remaining items). If bi. = 1 for some j E M, then, again, can again end up with no items, since by the choice of our tie-breaking rule, all agents can lose in the bre-brea (agents other than 1 lose to some smaller index agent,
'Fquivalently, we can define the utilitarian social welfare maximizing algorithm to the aforementioned 21,3 for all E N.
algorithm executed on transformed valuations where 0z = Eyex "t,

---

while agent loses to agent n). Therefore, no matter what agent i reports, in the worst-cass she gets a utillity of zero. Next we prove inequality (2), the best-case guarantee. By the normalization assumption and tie-breaking rule, any agent i (except agent 1) cannot out-bid every other agent on every single item, no matter what b, and v-; are. Therefore, the best-case outcome for agent is that she is allocated all items except her least favorite one. Additionally, note that this outcome can be realized when agent reports honestly and v-, is such that uy = 1, for all i' of i, where j is the item that i values the least (i.e. j E ar argminseM { ()),))). Finally, if agent 1 reports her true valuation, the best-case happens when all other agents also report agent I's true valuation - in which case, as per the tie- tie-breaking rule, she gets all the items; this outcome also cannot be improved upon. [
Nash Social Welfare. The next natural maximization objective, and arguably the most popular one in the context of fair division, is the Nash social welfare. Here, we show that unlike utilitarian social welfare maximization - there does not exist a NOM mechanism that always outputs allocations that maximize the Nash social welfare, for any number of agents. The case of Theorem 10 (Appendix E) that details our "best-of- brest-of-both-wee both-worlds" results. In the following theorem (proof deferred to Appendix C), we show that the impossibility extends n 3 agents.
agents follows from
Theorem 4. Every (randomized or deterministic) mechanism that always outputs an allocation that maximizes the Nash social welfare is obviously manipulable, even additive agents and 4 items.
Fair and Efficient Mechanisms
Maximizing the Nash social welfare results in allocations that are fair in addition to being economi- cally efficient [CKM+19) 19]. However, as we established Theorem 4, mechanisms that output MNW allocations are obviously manipulable for any number of agents.
In this section we state our main result, where we show that there is a deterministic NOM mechanism that is fair and economically efficient for additive valuations. This result is established by showing a black-box reduction from the problem of designing NOM mechanisms that output EF1 allocations to the problem of designing algorithms that output EF1 allocations. Additionally, this black-box reduction preserves Pareto efficiency guarantees. Missing proofs can be found in Appendix D.
The following theorem formally states our main result.
Theorem 5. For additive valuations, there exists Mack-box reduction, which preserves Pareto efficiency guarantees, from the problem of designing NOM and EFI mechanism, to designing an algorithm that computes clean, nos-wasteful and EFI allocations.
By combining Theorem 5 with known algorithmic results can get NOM mechanisms, with the same fairness and efficiency guarantees. Specifically, [GM21] give a pseudo-polynome time algorithm that computes fractionally Pareto efficient and EF1 allocations. Fractional Pareto efficiency implies non- won-aaatefulness, and without loss of generality we can assume that this algorithm outputs clean allocations. 5 Hence, by applying Theorem 5 we get the following application.
Corollary 1. (via [GM21J). For agents with additive valuations, there exists fractionally Pareto efficient, EF1, and NOM mechanism, that runs in poauddo-poynomiill time.
The Reduction. Our reduction, Mechanism 1, takes as input reported valuations b = (bj.... b... and black-box access a deterministic algorithm M Our reduction requires the algorithm M to always output non- wastefll, clean EF1 allocations for every possible input valuation functions.
The reduction is based on two key ideas, first, through careful construction of cases ensure that if an agent E N reports valuation b, then the set of allocations that can be returned by our reduction, Mechanism 1, for every possible b can be precisely characterized (Lemma 3). Second, prove structural result (Lemma 4) concerning this set of possible output allocation. This structural result plays central role in establishing that Mechanism is not obviously manipulable. Further, we show that, by construction, our reduction always outputs IPO + EFI allocations.
We begin by defining some notation. For each agent i N. let D, be the set of goods that have strictly positive value for i i.e. D, {g M bigg 0]. Let D. == \ U/ be the goods
$ Starting from an fPO and EF1 allocation A, making each hundle A, clean preserves hoth properties. Algorittm MM' could possibly be computationally inefficient.
7

---

remaining after removing all goods desired by agents other than i. Let R, for each agent i E N, be the indicator for the event that the subsets Je \ {D;} are pairwise disjoint, i.e. R, = 1 iff ((P))eN)) (D;) are pairwise disjoint, and R2 = 0 otherwise.
Mechanism 1 sequentially considers four cases based the sets {D and the values {Rz) to find a temporary allocation A". See Appendix D.2 for the pseudo-code.
Case I: The sets {D,}i_1 are pairwise disjoint (equivalently, R₁ = 1 for all i N). In this case, A allocates the bundle Dj to agent j for each agent E N.
Case II: R = 1 for exactly one agent: E N. This can occur if D; intersects two or more Djs (and these are the only intersections among pairs of subsets in { (D&)==) If allocating the bundle D. to agent i, and the bundle D2 to each agent j E N, for each j * v results an EF1 allocation, then A" is set to this allocation. Otherwise, if this allocation is not FF A is the allocation returned by M
Case III: There are exactly two agents j E N such that R2 = R3 = 1. The only way this is possible is if De. Dj intersect each other and any other pair of subsets De. Dt where {ki, o {i,
are disjoint. In this case, Mechanism 1 considers whether the set of goods D; n Dj are valued more by agent i or agent j: each of these two subcases are similar to Case II (see Lines 12-21).
Case IV: None of the previous cases holds (equivalently, R2 = 0 for all i E N). In this case, A is simply the allocation returned by M
The last step of Mechanism (Line 24) is to make the bundle allocated to each agent i in the temporary allocation clean, i.c. remove items from her bundle that she does not value. This is necessary for one of our technical lemmas (specifically, for characterizing the set of all allocations that are possible outputs of our mechanism). Note that this step does not affect efficiency or envy-freeness up to one item (i.e. if the allocation satisfied any of these notions before this step, it continues to do so).
For the case of two agents, our reduction is especially simple: give each agent all items she has a positive value and the other agent has a zero value, and give all items that both agents want (if any) to the agent with the largest value for them; if this is not EFI, run the black-box mechanism.
The case of strictly positive valuations. It is interesting to notice that when valuations are strictly positive, i.c. V.j 0 for all i.j. Mechanism simply outputs the allocation of MM (Case IV). However, this does not imply that every PO and EFI algorithm is NOM: in calculating worst-case outcomes, agents consider the possibility that others have zero valuations. This fact is critical in our proof of correctness (see the proof of Lemma 3).
Establishing the main result. Towards establishing Theorem 5, we begin by proving the following supporting lemmas. We show that Mechanism 1 preserves the efficiency and EFI guarantees of M*
Lemma If M is a-Pareto efficient (resp. a-fractionally Pareto efficient) then Mechanism I always outputs an a-Pareto efficient (resp. o-fractionally Pareto efficient) partial allocation.
Lemma If M outputs non-wasteful, clean, and EF1 allocations then Mechanism always outputs non-wasteful, clean, and EF1 partial allocations.
The following lemma characterizes the set of allocations that Mechanism I could possibly return given the reported valuation of a particular agent. Specifically, we will show that every clean, non- wasteful and EFI allocation, that is consistent with the reported valuation, a possible output of Mechanism 1. Before stating the lemma, we define some useful notations. For any agent é E N and valuation function v,, let EF, vs) be the set of (partial) allocations A (AI...., An) that are clean, non- wosteall and ffre- up to one item with respect to agent when her valuation function Vi, i.e., EF v.) = (A E II, (M) Vg E A; Us.g > O, and Vj E with A, + 0, (A.)) Z VA, \ (g)) for some g E Aj; and v:(M / URENAA) 0}.
Lemma 3. Given any agent i E N and valuation function for every allocation A E EFI(i, v:) there exists set of valuations - such that Mechanism I on inpul (V V-s) outputs allocation A.
Lemma establishes that all partial allocations in EF1 v:) can possibly be returned by the mechanism if agent reports v, Therefore, the problem of whether Mechanism is obviously manipulable (partially) reduces to whether some set (f. v`) has a better worst-case outcome than EF vs), with respect to the valuation vector V.. Before describing the subsequent lemma which develops this idea, we define some relevant notations. Given any set of (partial) allocations S C II, (M), an agent E N and valuation vector define l(i, v, S) minAeS v(A.).
8

---

Lemma 4. For any valuations v, v' and any agent i E N, l(i, vi v)) 2 v, EFI v\).
Proof. Let E EFI(i, v) be an allocation such v(A;) = lúi v. EF v)). ic. A is worst-case outcome for agent i when her valuation is v. We can assume, without loss of generality, that A" is complete allocation because if we assign the unallocated items, M \ UKEN AA. to agents other than agent i arbitrarily then still the resultant allocation would continue to belong in EF v). This follows from the fact that A is non-wasteful, vM \\ UREN 0.
If A (i, v'), the lemma immediately follows, since the minimum v (B.). over all allocations B E (i, v'), is at most v vA,). Otherwise, A" $ EF, v'). Since A is complete, and thereby non-wasteful, this is possible if either bundle A; is not clean wrt valuation v' or agent envies some other agent even after removal of one good. Denote by A the allocation obtained by cleaning the bundle A wrt valuation v', all other bundles remain as it is, i.c., Aj A3 for all j # i. Now if allocation A E EFi v'), the lemma follows, because v(Ai) 2 v(A.) and E(i, v, EF1(F, v')) is at most v(A.. In the rest of the proof we will handle the case when A & EFI(i.
Towards this we will construct an allocation A' with the following properties: (i) v(A)) S v(A)), and (ii) A' E FFI v'). These two properties together establish the desired inequality, since E(1, V, EFI(1, (1, v)) = v(4)) 2 v(A,) (0) v(4) (0)) E(i, v, EFI v))).
St = U-ENN A, + 0] be the subset of agents with non-empty bundles in A. Define agent j' == arg maxkes- minge A, v' \ {gg)), to be the agent in S whose allocation "up to one item" has maximum value with respect to v', and let n² arg min gEA,- A'A,, {9)) be the favourite
good with respect to v' that j has. A' is defined as follows. A A, \ [g A/. A, U (g'), and for all agents & E N \ fi.j"} } we have A/. Ag. It remains to show that A'' satisfies (t) and (ii).
Towards proving (i) we have v(A.) = v(Aj- \ {) S <v(,), where the last inequality follows from the fact that A E FT v). For (ii), note that N (i) can be written the union of three disjoint sets S1, S2 and S3. where S = (5 (i)), S2 = (S* \ {j*}), and S3 = {("). We will envy, up to one item, any of the
show that in allocation A' agent i with valuation vector v', does agents in Sj. S2. or S3: this establishes that A' E EFI(i, v'). First, for every agent & E S we have that A/e Aş- 0, by the definition of S*, agent i cannot envy any such agent. Second, given the definition of agent j", we know that for each agent k in S2 = S* {(j") }. we have
min v'k {o}) 9EAG
min v' (A \ {g)) gEAr
(A₁ A& for all agents except and j*)
I min v(A,- (9)) SEAg-
(by the definition of j*)
<AAA \g')))
(g* Aj-) (9*1)
v(A)).
Therefore, agent with valuation v' does not envy up to item (and, in fact, up any item) any agent in S2. Third, recall that A & EF v'). By definition, agent j has the bundle that v' likes the most "up to one item", and g" is that most valuable (in terms of marginal value) item in 's bundle, so v'A))) < ('A \ (g0))) Therefore, we have
(AA)) "(AAMo' > v(A))
(4) = A
(4 $ EF1(i, v))
= -o'd = =V'A'' 1)
-
That is, agent with valuation v' does not envy, up to one item, any agent in S₂ = (i*). Note that, allocation A' is non-wastefin wrt agent i. Furthermore, the bundle A' can be cleaned maintaining the fact that A' is EFI wrt agent i. This establishes that A' E EFI v") and concludes the proof.
Given the previous lemmas, we can show our main theorem with respect to NOM.
Theorem 6. !f agents' valuation functions are additive and M outputs EF1, non-wasteful and clean allocations, then Mechanism I is not obviously manipulable.

---

Proof. We first show that agents cannot improve their worst-case utilities by misreporting.
Let E N be an agent whose true valuation v, and let her misreport be b;. By Lemma for every reported valuation vector b of agent i, and for every allocation A E EF b), there exists valuation profile V-i such that A is the output of Mechanism 1. On the other hand, by Lemma 2, Mechanism I always outputs allocations A that are EFI, clean, and non-wasteful. There- fore, every output allocation of Mechanism is in EFI(ii, b). Therefore, if agent reports v; (respectively b,), then the set of all possible allocations of Mechanism I is exactly EFI(i, v:) (respectively EF, by)). Overloading notation, let A, (V,, v-i) be the allocation of agent in Mech- anism 1, on input (V: V V-i). For the worst-case utility of agent we have min v2 (V, v-1))
min AEEF)(
v2(A,) = ((, vi, EF v.)) 2 Lem. fii, V1, (i, = min v. v. (45(b; (b,, v-:)).
This establishes Inequality (1) from the definition of NOM. To conclude the proof, it remains to show that the best-case utility of an agent is also not improved by misreporting. Note that the best case for agent E N occurs when all other agents have value for the items, i.c. Dj 0 for all N {d}. Hence the sets {Dx ke xs are pairwise-disjoint and Mechanism (via Case 1) allocates the entirety of D; to agent which is impossible to improve upon.
The proof the above theorem along with the supporting lemmas establishes Theorem We note that that it is not possible to improve upon this result by adding ex-ante fairness guarantees; see Appendix D.3 for details.
Acknowledgements
The authors are supported in part by an NSF CAREER award CCF-2144208, a Google Research Scholar Award, and by the Algorand Centres of Excellence program managed by Algorand Foun- dation. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of Algorand Foundation.
References
[ABCM17] Georgios Amanatidis, Georgios Birmpas, George Christodoulou, and Evangelos Markakis. Truthful allocation mechanisms without payments: Characterization and implications fairnsss. In Proceedings of the 2017 ACM Conference Economics and Computation, pages 545-562, 2017.
[ACGH20] Redict Abebe, Richard Cole, Vasilis Gkatzelis, and Jason D Hartline. A truthful cardinal mechanism for one-sided matching. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms,, pages 2096-2113. STAM, 2020.
[AFRC* 16] Haris Aziz, Aris Filos- Rattskass,,,s, Jiashu Chen, Simon Mackenzie, and Nicholas Mattei. Egalitarianism of random assignment mechanisms. In Proceedings the 2016 Inter- national Conference on Autonomous Agents & Multiagent Systems, pages 1267-1268, 2016.
[AG18] Itai Ashlagi and Yannai A Gonczarowski. Stable matching mechanisms are not obvi- ously strategy-proof. Journal of Economic Theory, 177:405 425, 2018.
[AL21] Haris Aziz and Alexander Lam. Obvious manipulability of voting rules. In International Conference on Algorithmic Decision Theory, pages 179-193. Springer, 2021.
[AMN20] R Pablo Arribillaga, Jordi Massó, and Alejandro Neme. On obvious trategy-proofine and single peakedess,, Journal of Economic Theory, 186: 2020.
[Azi20a] Haris Aziz. Justifications of welfare guarantees under normalized utilities. ACM SIGecom Exchanges, 17(2):71-75, 2020.
[Azi20b] Haris Aziz. Simultaneously achieving ex-ante and ex-post fairness. In International Conference on Web and Internet Economics, pages 341-355. Springer, 2020.
10

---

[BCIZ21] Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding fair and efficient allocations for matroid rank valuations. ACM Transactions on Economics and Computation, 9(4): 2021.
[BEF21] Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for di- chotomous valuations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5119-5126, 2021.
[Bud[]] Eric Budish. The combinatorial assignment problem: Approximate competitive equilib- rium from equal incomes. Journal of Political Economy, 11966;1061-1103: 2011.
[BV21] Siddharth Barman and Paritosh Verma. Truthful and fair mechanisms for matroid-rank valuations. arXiv preprint 1rXiv:2109.058/000 2021.
[CGG13] Richard Cole, Vasilis Gkatzelis, and Gagan Goel. Mechanism design for fair division: allocating divisible items without payments. In Proceedings of the fourteenth ACM conference Electronic commerce, pages 251-268, 2013.
[CKM+ 19] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 133):1-32 2019.
[EK03] Lars Ehlers and Bettina Klaus. Coalitional strategy-proof and resource-monntonic solutions for multiple assignment problems. Social Choice and Welfare, 21(2)2255-280, 2003.
[FGP14] Eric Friedman, Ali Ghodsi, and Christos-Alexandros Psomas. Strategyproof allocation of discrete jobs on multiple machines. In Proceedings of the fifteenth ACM conference Economics and computation, pages 529-546, 2014.
[FGPS19] Eric J Friedman, Vasilis Gkatzelis, Fair and efficient memory sharing: Confronting free riders. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1965-1972, 2019.
Psomas, and Scott Shenker.
[FSV20] Rupert Freeman, Nisarg Shah, and Rohit Vaish. Best of both worlds: Ex-ante and ex-post fairness in resource allocation. Proceedings of the 21st ACM Conference on Economics and Computation, pages 21-22, 2020.
[[TTZ16] Dimitris Fotakis, Dimitris Tsipras, Christos Tzamos, and Emmanouil Zampetakis. Efficient money burning in general domains. Theory of Computing Systems, (9)4)619 640, 2016.
[FV19] Diodato Ferraioli and Carmine Ventre. Obvious strategyproofness, bounded rationality and approximation. In International Symposium on Algorithmic Game Theory, pages 77-91. Springer, 2019.
[GM21] Jugal Garg and Aniket Murhekar. On fair and efficient allocations of indivisible goods.
In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[GP15] Jonathan Goldman and Ariel D Procaccia. Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges, 13(2):41-46 2015.
[GZH 11] Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types, In Nsdi, volume 11, pages 24-24, 2011.
[HPPS20] Daniel Halpern, Ariel Procaccia, Alexandros Psomas, and Nisarg Shah. Fair division with binary valuations: One rule to rule them all. In International Conference Web and Internet Economics, pages 370-383. Springer, 2020.
[HR08] Jason D Hartline and Tim Roughgarden. Optimal mechanism design and money burning. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 75-84, 2008
11

---

[ILM11]] Nicole Immorlica, Brendan Lucier, Glen Weyl, and Joshua Mollner. Approximate efficiency in matching markets. In International Conference on Web and Internet Economics, pages 252-265. Springer, 2017.
[KM02] Bettina Klaus and Eiichi Miyagawa. prootggs,, solidarity, and consistency for multiple assignment problems. International Journal of Game Theory, 30(3):421-435 2002.
[KV19] Maria Kyropoulou and Carmine Ventre. Obviously strategyproof mechanisms with- out money for scheduling. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 1574-1581, 2019.
[Li17] Shengwu Li. Obviously strategy-pree proof mechanisms. American Economic Review, 107(11))3257--7,2211 2017.
[OSH19] Josué Ortega and Erel Segal-Halevi. Obvious manipulations in cake-cutting, arXiv preprint arXiv: (rXv02990.002988, 2019.
[PPS15] David C Parkes, Ariel D Procaccia, and Nisarg Shah. Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. ACM Transactions on Economics and Computation (TEAC), 3(1):1-22, 2015.
[RF90] Günther Ruhe and Bernd Fruhwirth. E-optimality for bicriteria programs and its application to minimum cost flows. Computing, 44(1):21-34, 1990.
[Rot82] Alvin E Roth. The economics of matching: Stability and incentives. Mathematics of operations research, 7(4):617-628, 1982.
[Sch96] James Schummer. Strategy-proofneet versus efficiency on restricted domains of ex- change economies. Social Choice and Welfare, 14(1):47-56, 1996.
[TM20] Peter Troyan and Thayer Morrill. Obvious manipulations. Journal of Economic Theory, 185: 185:104970, 2020.
[ZP20] David Zeng and Alexandros Psomas. Faimnes--effiienncy tradeoffs in dynamic fair division. Proceedings of the 2 ACM Conference on Economics and Computation, pages 911 911-912, 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See "Our contribution" in intro.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2.
(b) Did you include complete proofs of all theoretical results? [Yes] All our theorems and lemmas have proofs, either in the first pages, in the supplementary material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
12

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "zubo2tQnpqG", "reviewer": "Reviewer_iRAr", "summary": "This paper studies the problem of non-monetary resource allocation when agents have additive valuation functions over indivisible goods. Since there exist strong impossibility results in this setting if one also imposes truthfulness, the authors consider the relaxed incentive guarantee known as non-obvious manipulability (NOM). The main result is that any algorithm that satisfies envy-freeness up to one good (EF1) can be transformed into a not-obviously manipulable and EF1 algorithm (subject to mild conditions). This main result is complemented by some other results regarding NOM in the domain of non-monetary resource allocation: the round robin and utilitarian social welfare-maximizing algorithms are NOM, but Nash and egalitarian social welfare-maximizing algorithms are not.", "questions": "1) Lines 249-250 grabbed my attention, since my intuition is that manipulating the utilitarian SW-maximizing mechanism is (intuitively) \"obvious\" when valuations are not required to be normalized: I should report huge valuations for all goods. Is there intuition for why we shouldn't think of this as an \"obvious\" manipulation? It would also help me if you could lay out the formal relationship between NOM and obvious strategyproofness of Li17, if there exists one. Lines 38-40 hint at such a relationship but leave it ambiguous.\n\n2) Can you write down the mechanism that is obtained from applying the reduction (Mechanism 1) to MNW? Even just for 3 agents and 4 items?", "limitations": "Adequately addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The idea of the paper is novel and the idea is very interesting. Escaping and refining classic impossibilities in this space is an important problem, in my opinion. The results that are obtained, especially the main result (Theorem 5), are strong and surprising.\n\nWeaknesses: I am not convinced that NOM is a good relaxation of truthfulness (for this problem, at least). See my question below.\n\nMinor:\n\nLine 99: \"efficiency\" -> \"efficient\"\nLine 184: \"an\" -> \"a\"\nLine 191: \"agent\" -> \"agents\"\nCould lines 197-202 go to the appendix?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "u9xZs5YDhA", "reviewer": "Reviewer_uv2Y", "summary": "This work considers the tools available to a central designer needing to allocate goods fairly and efficiently to agents with additive valuation functions and no monetary transfers. There are no general envy-free and deterministic truthful mechanisms to do so. Recent other work in loosening truthfulness has explored what types of manipulations are likely to be taken advantage of. This work takes one such notion, “non-obvious manipulability” and asks what additional strength does relaxing truthfulness to NOM give to the central designer - notably, can she achieve a mechanism that  is deterministic and envy-free up to one item? More generally, how do her options change when she relaxes truthfulness to NOM?\n\nThe paper answers in the affirmative, and in fact gives a black box reduction from designing an EF1+NOM mechanism to that of designing an EF1 algorithm. \n\nThis black box reduction hinges on handling the special cases where the demanded items are fully disjoint sets (1), fully disjoint except for the goods desired by one person (case 2), fully disjoint except the goods desired by two people (case 3), and if none of those apply, applying the algorithm directly (case 4).\n\n\n", "questions": "Can you comment on the jump from 2 to 3 agents in both Theorems 2&3 and in the core reduction and result? Does NOS retain relevance with three agents having overlapping preferences or is this a case where it is capturing ", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper comprehensively addresses the impact that relaxing truthfulness to non-obviously manipulability gives to a designer. This makes for a helpful and interesting contribution to the literature surrounding relaxed notions of truthfulness.\n\nThe nature of the black box reduction - special cases for when two or fewer agents have overlapping demand sets raises a small question of whether or not there is a more fundamental core regarding three agents that can be embedded to simplify the reduction. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "t6QsAxE3RCK", "reviewer": "Reviewer_Hf6D", "summary": "Truthfulness is an important issue in the field of indivisible resource allocation. However, it is widely known that fairness and efficiency are usually not compatible with truthfulness. In this work, the authors studied a relaxed notion of truthfulness, namely, non-obvious manipulability (NOM). Fortunately, under the relaxed notion, the negative results do not hold anymore. \n\nOriginally, truthfulness means it is each agent’s dominant strategy to report the true values no matter what values will be reported by the others. The related notion NOM only requires that reporting the true values yields a (weakly) higher utility than lying in either the best and worst-case scenarios. \n\nThe fairness notion concerned in this work is EF1 (envy-free up to one good), a popular relaxation of EF (envy-freeness). The efficiency notions concerned include utilitarian welfare maximization, egalitarian welfare maximization, and Nash welfare maximization. \n\nFor fairness, under the new notion, the authors first show that the Round-Robin is actually NOM, which significantly separates truthfulness and NOM. Therefore, NOM and EF1 are compatible. Actually, using the algorithm by Aziz, WINE 2020, we can have a stronger result by achieving ex ante EF, ex post EF1 and NOM simultaneously. \n\nFor efficiency, (a little bit unexpected to me since the requirement of NOM is weak to me), the authors proved that for any number of agents, both egalitarian and Nash welfare maximizations are not compatible with NOM. For utilitarian welfare maximization, however, although it is still not compatible with NOM with two agents, they are compatible with more than two agents. \n\nFinally, the authors investigated the compatibility among NOM, EF1, and Pareto efficiency. To answer this question, the authors provided a black box reduction from any algorithm that outputs (clean and non-wasteful) EF1 allocations to a new mechanism that not only ensures EF1 but is also NOM. Moreover, the reduction preserves the property of Pareto efficiency, which implies that NOM, EF1, and Pareto efficiency can be satisfied together, via existing results in the literature.\n", "questions": "For the reduction part, if all the valuations are strictly positive, the reduction actually does not need to do any change. I am not sure if this can be a good warm-up to show at the start of this section so that the readers can understand why we need to design the reduction like this.\n\nThe word “truthfulness” is used throughout the paper except related work, in which strategyproofness is sometimes used. I guess the authors want to be consistent with the referred papers, but I am not sure if the readers will get confused. \n\nHave you ever defined what “PO” is short for?\n", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nI agree with the authors that NOM might be a better notion for non-manipulability since truthfulness is hard to achieve together with fairness and efficiency. Thus, I think this work may be a good initiating work. \n\nThe authors also provide a relatively complete picture for NOM. \n\n\nWeaknesses\nThe requirement of NOM is still a bit weak to me (although it is still not compatible with some efficiency criteria). It will be better if the authors can justify why only the best and the worst cases are particularly interesting. \n\nThe proofs are not technically hard.\n\nThe writing in general is good but can be further improved. \n\n\nTypos:\n\nLine 130 M should be non-italic in \\Pi_n(M).\nLine 214 l does not dependent of her report\nLine 273 argmin should be a function\nLine 274 also report her\nLine 275 she get\nLine 277 I do not see why Nash social welfare maximization is the most popular objective. \nLine 329 each of these two subsets are \nLine 351 some useful notation\nLine 417 establish Theorem 5\nLine 418 that that\n“with respect to” is sometimes abbreviated and sometimes not; better to be consistent\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jzTRXWlKSS", "reviewer": "Reviewer_FBTg", "summary": "This paper reconsiders the classic problem of allocating indivisible goods through the lens of non-obvious manipulability (NOM).  The results show that this can bypass known impossibility results for the stronger and more standard requirement of truthfulness.  In particular is possible to achieve deterministic+EF1+NOM and that this can be combined with (fractional) Pareto efficiency among other positive results.  Negative results show that Nash and egalitarian welfare maximization both fail to satisfy NOM.", "questions": "Can you make a case that the stronger theoretical properties yielded by the reduction lead to meaningfully better results in practice.", "limitations": "NOM is a relatively recent approach.  Given that the interest of the results hinges on the reasonableness of relaxing truthfulness to NOM, I was surprised there does not appear to be discussion of whether the guarantee provided by NOM and the incentives of them mechanisms that satisfy it are reasonable in this setting.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "On the positive side, the paper is clear and does a nice job revisiting a classic problem and gaining new insights about both classic mechanisms and new designs.  The black-box-reduction seems technically non-trivial and from a theoretical perspective the combination of properties it achieves is an improvement over prior work.\n\nOn the negative side, the arguments in Sections 3 and 4 largely seem straightforward, so the contribution here seems somewhat limited.  For Section 5, which has more of a technical contribution, it is unclear to me how important this is for practice.  Other than identifying that it has stronger theoretical properties, there isn’t any evidence presented that the results of the reduction are noticeably better than Round-Robin or PS-Lottery.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept