PaperlayerView exact revision on arXiv

Source-linked AI summary

Fair and Truthful Mechanisms for Dichotomous Valuations

Moshe Babaioff, Tomer Ezra, Uriel Feige

arXiv:2002.10704v3cs.GT

TL;DR

Allocating indivisible goods without money requires balancing welfare, fairness, and truthfulness. The paper designs truthful mechanisms for dichotomous valuations: deterministic PE for submodular valuations and randomized ML for additive near-dichotomous valuations. PE provides Lorenz-based fairness guarantees, while ML achieves at least a ρ-fraction of maximum welfare.

  • Problem

    Allocating indivisible goods among agents with private preferences requires balancing economic efficiency and fairness when money cannot be used to transfer utility.

    Source: §1 · p. 1

  • Method

    The paper designs deterministic prioritized egalitarian (PE) allocation for submodular dichotomous valuations and randomized ML for additive valuations rounded to dichotomous values, using random priorities and held-out items.

    Source: §1.1 · p. 6

  • Results

    PE is Lorenz-dominating, EFX, and NSW-maximizing, with maximin-share guarantees for additive dichotomous valuations; ML achieves at least a ρ-fraction of maximum welfare.

    Source: §1.1 · pp. 3, 5, §3 · p. 11

  • Takeaways & Limitations

    Random priorities make PE envy-free ex ante while retaining its other guarantees ex post.

    Source: §3.3 · p. 15

    Even for two agents with additive dichotomous valuations, no truthful deterministic mechanism can guarantee welfare maximization and EFX if it must allocate every item, including undesired ones.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. To gauge the robustness of our positive results, we also study $\epsilon$-dichotomous valuations, in which the added value of any item to a set is either non-positive, or in the range $[1, 1 + \epsilon]$. We show several impossibility results in this setting, and also a positive result: for players that have additive $\epsilon$-dichotomous valuations with sufficiently small $\epsilon$, we design a randomized truthful mechanism with strong ex-post guarantees. For $\rho = \frac{1}{1 + \epsilon}$, the allocations that it produces generate at least a $\rho$-fraction of the maximum welfare, and enjoy $\rho$-approximations for various fairness properties, such as being envy-free up to one item (EF1), and giving each player at least her maximin share.

1 Introduction

The paper studies truthful, fair, welfare-efficient allocation of indivisible goods without payments, focusing on dichotomous valuations. It presents its allocation guarantees and situates them alongside prior and concurrent work on dichotomous valuations.

1 Introduction

  • The introduction frames allocation without money as a tradeoff among social welfare, fairness, and truthful reporting, and uses museum-guide shifts as an example of dichotomous preferences.Source: §1 · p. 1, §1.2.1 · p. 6

1.1 Our Contribution and Techniques

  • For submodular dichotomous valuations, the deterministic prioritized egalitarian mechanism is truthful and welfare maximizing, and yields a Lorenz-dominating allocation with EFX and maximum NSW; additive valuations also guarantee each agent her maximin share.The result applies when agents report truthfully.Source: §1.1 · p. 3
  • Randomizing priorities for the prioritized egalitarian mechanism makes it envy-free ex ante and universally truthful, while retaining its other guarantees ex post.Source: §1.1 · p. 4
  • For ǫ-dichotomous valuations, no truthful mechanism can approximate maximum welfare better than 1/2 even for unit-demand agents, and ǫ-leveled valuations rule out truthful welfare maximization.For ǫ-leveled valuations, no deterministic truthful mechanism both allocates all desirable items and guarantees an agent reporting n desirable items at least one of them.Source: §1.1 · p. 5
  • For additive ǫ-leveled valuations, randomized mechanism ML is truthful in expectation and ex-post ǫ-truthful, while guaranteeing ex-post ρ-approximations to welfare, maximin share, and EF1.The expected utility of each truthful agent is also at least a 1/n fraction of her value for the grand bundle.Source: §1.1 · p. 5
  • Mechanism ML rounds reported values down to integers, applies prioritized egalitarian allocation to main items, and uses randomly held-out items with reversed priorities to support truthfulness and fairness.Its truthfulness argument uses PE’s incentive property and the chance of losing a desirable item after misreporting.Source: §1.1 · p. 6

1.2.1 Previous Work

  • Prior work on dichotomous preferences includes randomized fair-in-expectation mechanisms, while this paper broadens the valuation class to submodular preferences and focuses on ex-post fairness.The closely related MAP work uses a fractional Lorenz-dominating solution and restricted truthfulness; its ex-post fairness after rounding is not addressed.Source: §1.2.1 · pp. 6–7
  • Freeman et al. [24] achieve ex-ante envy-freeness with ex-post EF1 for additive valuations, while Aleksandrov et al. [1] study online additive dichotomous allocation with both guarantees.Freeman et al. show that ex-ante EF together with ex-post EF1 and PO is impossible; the paper claims these properties for dichotomous valuations, including submodular valuations, with stronger EFX and Lorenz-domination guarantees than the online work.Source: §1.2.1 · p. 7

1.2.2 Independent and Concurrent Work

  • The deterministic mechanism is truthful, efficient, Lorenz-dominating, and EFX; its randomized variant is universally truthful, stochastically envy-free, efficient, and ex-post EFX for dichotomous submodular valuations.Source: §1.2.2 · p. 8
  • For additive dichotomous valuations, Halpern et al. [28]’s deterministic MNWtie mechanism matches the paper’s PE mechanism and is EF1, PO, and weakly group strategyproof.Their randomized mechanism is ex-ante weakly group strategyproof and ex-post PO and EF1; Aziz [6] proves a similar result using a different rounding procedure. The paper’s best-of-both-worlds result extends to submodular dichotomous valuations and is universally truthful, while the cited concurrent results cover only additive valuations and are not known to be universally truthful.Source: §1.2.2 · p. 8
  • Benabbou et al. [11] give an efficient algorithm for welfare-maximizing EF1 allocations with dichotomous submodular valuations, but do not address incentives.The paper instead designs a computationally efficient truthful mechanism combining fairness and economic efficiency.Source: §1.2.2 · p. 8

2 Model and Preliminaries

The model treats agents as having normalized, non-decreasing valuations over sets of finite, indivisible goods. It formalizes valuation classes, allocation mechanisms, and fairness criteria used in the paper.

2 Model and Preliminaries

  • The setting has a finite set of indivisible, non-identical items and at least two agents with normalized, non-decreasing valuations.An agent's utility is the value of the bundle allocated to that agent.Source: §2 · p. 8

2.1 Valuations

  • Dichotomous valuations have marginal values of 0 or 1; submodular dichotomous valuations are matroid rank functions, while additive 0-leveled valuations are dichotomous additive valuations.The preliminaries also define additive, submodular, matroid rank, and epsilon-dichotomous valuation classes.Source: §2.1 · p. 9

2.2 Allocations

  • An allocation assigns each item to at most one agent and may leave items unallocated; welfare is the sum of agents' allocated-bundle values.A reasonable allocation is non-redundant and has maximal size; with epsilon-dichotomous valuations it achieves at least a 1/(1+epsilon) fraction of maximum welfare.Source: §2.2 · pp. 9–10

2.3 Mechanisms

  • Mechanisms map reported valuation functions to allocations, and truthfulness means truthful reporting is a weakly dominant strategy for each agent.A mechanism has an allocation property when every output allocation has that property for its input valuations.Source: §2.3 · p. 10

2.4 Fairness

  • Fairness criteria include maximin share, EF1, EFX, lex-min utility vectors, Lorenz domination, min-square allocations, and Nash Social Welfare.EFX is stronger than EF1; a Lorenz-dominating allocation, when one exists, is also lex-min.Source: §2.4 · pp. 10–11
  • The preliminaries also define alpha-approximations for maximin share, EF1, and EFX, requiring each agent to receive at least an alpha fraction of the corresponding share.The section notes that an allocation maximizing Nash Social Welfare need not maximize welfare.Source: §2.4 · p. 11

3 Submodular Dichotomous Valuations

For submodular dichotomous valuations, the paper gives a truthful mechanism whose allocations maximize welfare and satisfy strong fairness guarantees. Random priorities extend the result to ex-ante envy-freeness while preserving the deterministic mechanism’s guarantees ex-post.

3 Submodular Dichotomous Valuations

  • For submodular dichotomous valuations, the mechanism is truthful, welfare maximizing, and outputs allocations that are Lorenz dominating, NSW maximizing, and EFX.For additive dichotomous valuations, it also guarantees maximin fairness.Source: §3 · p. 11

3.1 Lorenz Dominating Allocations

  • Lorenz domination implies welfare maximization, lex-min and min-square outcomes, and maximum NSW; for non-redundant MRF allocations it also implies EFX.For additive dichotomous valuations, it further implies maximin fairness.Source: §3.1 · p. 12
  • For general MRF valuations, every Lorenz dominating allocation gives each agent at least half her maximin share, though some such instances admit no maximin-fair Lorenz dominating allocation.Source: §3.1 · p. 12

3.2 The Prioritized Egalitarian (PE) Mechanism

  • The PE mechanism selects a non-redundant Lorenz dominating allocation that favors higher-priority agents as much as possible; this particular selection is truthful.An arbitrary Lorenz dominating allocation need not be truthful.Source: §3 · p. 12, §3.1 · p. 13, §3.2 · p. 15

3.1 Lorenz Dominating Allocations

  • The paper establishes that Lorenz dominating allocations exist for MRF valuations, and removing auxiliary items from an augmented allocation preserves Lorenz domination.Submodular dichotomous valuations are matroid rank functions (MRFs).Source: §3 · p. 11, §3.1 · p. 13

3.2 The Prioritized Egalitarian (PE) Mechanism

  • With succinct MRF representations, the PE mechanism can be implemented in polynomial time.Source: §3.2 · p. 15

3.3 Best-of-Both-Worlds via Random Priorities

  • The RPE mechanism draws priorities uniformly at random before running PE; it is universally truthful and welfare maximizing, with Lorenz domination and fairness guarantees ex-post.It is stochastically envy-free, and therefore ex-ante envy-free and proportional; these guarantees do not require risk neutrality.Source: §3.3 · pp. 15–16

4 ǫ-Leveled Valuations

The paper tests whether the dichotomous-valuation guarantees survive when positive marginal values vary within a narrow range. It identifies limits on truthful, fair mechanisms and gives a randomized approach for additive ε-leveled valuations when ε is sufficiently small.

4 ε-Leveled Valuations

  • For any ε>0, no truthful mechanism, deterministic or randomized, always achieves approximately maximum welfare for submodular unit-demand ε-dichotomous valuations.Source: §4 · p. 17
  • For two agents and three items, no deterministic truthful mechanism guarantees approximate welfare and ensures an agent who desires two items receives at least one.The paper says this rules out mechanisms satisfying stronger fairness properties such as maximin fairness or EF1.Source: §4 · p. 17
  • Rounding each valuation down produces a dichotomous valuation, and for ε-leveled valuations the rounded valuation is additive.Source: §4 · p. 18
  • With two items and two ε-leveled agents, a randomized truthful-in-expectation mechanism must either fail one of five listed fairness properties ex-post, even for floor valuations, or sometimes leave a demanded item unallocated.The listed properties are Lorenz domination, min-square, maximum NSW, lex-min, and EFX.Source: §4 · p. 18

4.1 A Truthful Mechanism for Leveled Valuations

  • For sufficiently small ε, ML is truthful in expectation for ε-leveled valuations; with truthful agents, welfare ex post is at least 1/(1+ε) of maximum welfare, with 1/(1+ε)-maximin-share and 1/(1+ε)-EF1 guarantees.Source: §4.1 · pp. 19–20
  • The positive ML result is for additive ε-dichotomous valuations, called ε-leveled valuations, rather than the broader submodular class used in the impossibility result.Source: §4 · p. 17, §4.1 · p. 19
  • ML combines PE on the remaining items with a mechanism for one or two randomly selected items, using reversed priority order for the latter allocation.The paper says the random-item mechanism creates incentives that make the combination truthful in expectation when ε is sufficiently small.Source: §4.1 · p. 19

B.1 Fairness Properties of Lorenz Dominating Allocations

Lorenz domination entails several welfare and fairness properties, but its maximin-share guarantee depends on the valuation class. For MRFs it guarantees at least half the maximin share, whereas additive dichotomous valuations receive the full share.

B.1 Fairness Properties of Lorenz Dominating Allocations

  • A Lorenz dominating allocation maximizes welfare, is lex-min and min-square, and maximizes NSW; if valuations are MRFs and the allocation is non-redundant, it is also EFX and EF1.For additive dichotomous valuations, Lorenz domination also implies maximin fairness.Source: §B.1 · p. 24
  • With additive dichotomous valuations, every Lorenz dominating allocation is maximin fair.Source: §B.1 · p. 25
  • For MRF valuations, every Lorenz dominating allocation gives each agent at least half her maximin share, but some MRF instances have no Lorenz dominating allocation that is maximin fair.Source: §B.1 · p. 25
  • The appendix illustrates the MRF limitation with an instance where agent 1’s maximin share is 2n−1, but every Lorenz dominating allocation gives each agent n items.Source: §B.1 · p. 25

B.2 Missing proofs from Section 3.1

The proofs establish an exchange lemma for non-redundant allocations and use it to prove the priority-greedy algorithm maximizes welfare. They also show that the resulting welfare function is submodular.

Lemma 17

  • Lemma 17 transfers items along a useful path so a deficient agent gains one item while exactly one agent with a surplus loses one, preserving non-redundancy.For submodular dichotomous valuations, other agents may also need to exchange items; the example shows one agent exchanging both of theirs.Source: §B.2 · pp. 26–27

Lemma 17 intuition

  • Unlike the additive dichotomous case, a transfer under submodular dichotomous valuations may require multiple agents to exchange items, and can change every item’s allocation.The four-agent example has an agent exchange both items, illustrating why the exchange argument is more involved.Source: §B.2 · p. 26

Lemma 18

  • The greedy priority algorithm gives each agent the largest feasible item count while preserving earlier agents’ counts, and maximizes welfare for every prefix of the priority order.The proof uses Lemma 17 to contradict any welfare-maximizing allocation with a lexicographically larger utility vector.Source: §B.2 · p. 27

Lemma 19

  • The welfare function W over agent sets is submodular: adding either of two agents separately yields at least the combined welfare from adding both.The proof runs the greedy algorithm with agents in S first, then u and v, and uses the allocation for S to lower-bound both single-agent extensions.Source: §B.2 · pp. 27–28

B.3 Missing proofs from Section 3.2

These proofs establish faithfulness, monotonicity, and strong faithfulness of the PE mechanism. Together, strong faithfulness and monotonicity also imply a one-item Lipschitz bound on allocated item counts.

Faithfulness

  • The PE mechanism is faithful: when an agent reports her valuation restricted to her allocated bundle, that bundle remains unchanged.The proof uses the fact that restricting a valuation to the current allocation preserves a Lorenz-dominating allocation’s value vector.Source: §B.3 · p. 28

Lemma 21

  • The PE mechanism is monotone: expanding an agent’s reported desired-item set cannot decrease the number of items allocated to that agent.The proof compares reports differing by one item and uses the exchange lemma to rule out a decrease.Source: §B.3 · pp. 28–29

Lemma 22

  • The PE mechanism is strongly faithful: restricting a report to any subset of the agent’s allocated bundle returns that subset as the allocation.The proof first treats a subset missing one item, then extends to smaller subsets by induction.Source: §B.3 · p. 29

Remark 23

  • Together, strong faithfulness and monotonicity imply that adding one desired item increases an agent’s allocation by at most one item.The count also cannot decrease, by monotonicity.Source: §B.3 · p. 29

B.4 Polynomial Time Algorithm for the PE Mechanism

The PE mechanism can be implemented in polynomial time for succinctly represented MRF valuations. The algorithm combines matroid intersection with iterative reductions in a potential function.

Theorem 9

  • For succinctly represented MRF valuations, the PE mechanism can be implemented in polynomial time.The proof reduces finding a Lorenz-dominating allocation to a polynomial sequence of matroid intersection problems.Source: §B.4 · p. 30

Matroid intersection

  • A matroid-intersection instance represents non-redundant allocations as common independent sets, with maximum welfare corresponding to maximum rank.The two matroids enforce each agent’s MRF independence constraint and prevent assigning copies of the same item more than once.Source: §B.4 · p. 30

Potential minimization

  • Starting from a maximum-welfare allocation, the algorithm tests and reduces its potential until it is minimized, yielding a Lorenz-dominating allocation.It tests O(n^2) candidate agent pairs per iteration and finds a minimum-potential allocation after at most O(m^2n^2) iterations.Source: §B.4 · p. 30

C.1 Basic Observations

The basic observations relate ε-dichotomous valuations to dichotomous ones by flooring marginal values. They provide approximation guarantees for transformed mechanisms and reasonable allocations, and identify conditions under which the floor remains additive.

Flooring valuations

  • For ε < 1/m, flooring an ε-dichotomous valuation’s marginals gives a dichotomous valuation; if the original valuation is ε-leveled and additive, the floored valuation is also additive.The proof bounds the sum of the discarded fractional parts by less than one.Source: §C.1 · p. 31

Mechanism transformation

  • Applying a dichotomous-valuation mechanism to the floored reports transfers maximin-fairness, EF1, and EFX guarantees as approximations, while truthfulness becomes ε-truthfulness.The supplied observation states these transferred guarantees, but its approximation factors for fairness are not fully specified in the passages.Source: §C.1 · p. 31

Welfare approximation

  • Every reasonable allocation for ε-dichotomous valuations gives a 1/(1+ε)-approximation to social welfare.The proof compares its welfare with an optimum allocation and uses that the reasonable allocation maximizes welfare for the corresponding dichotomous valuations.Source: §C.1 · p. 32

C.2 Impossibilities for ǫ-Leveled Agents

For ǫ-leveled agents, the section gives impossibility results for combining truthful allocation with welfare and fairness guarantees. These apply to deterministic mechanisms and, for several fairness properties, randomized mechanisms truthful in expectation.

C.2 Impossibilities for ǫ-Leveled Agents

  • No deterministic truthful mechanism for three items and two ǫ-leveled agents can always approximate welfare while ensuring an agent who desires two items gets at least one.The proof uses truthful reporting to force allocations of desired items across profiles, producing a conflict with the two-item guarantee.Source: §C.2 · pp. 32–33
  • For two ǫ-leveled agents and two items, randomized mechanisms truthful in expectation cannot always satisfy the listed fairness properties ex-post while also remaining reasonable.The listed properties are Lorenz domination, min-square, NSW maximization, lex-min, and EFX; the result allows failure either of ex-post fairness or of allocating a demanded item to an agent who demands it.Source: §C.2 · p. 33
  • With identical agents valuing items L and H at 1 and 1+ǫ, respectively, the fairness conditions force each to receive one item when truthful, enabling a profitable misreport in the randomized impossibility argument.If one agent reports value 0 for L, the fairness conditions require that agent to receive H and the other agent L.Source: §C.2 · p. 33

C.3 Proof of the Main Theorem for ǫ-leveled Valuations

This section proves the main theorem for ε-leveled valuations, showing that mechanism ML combines truthfulness with welfare, fairness, and proportional-share guarantees and runs in polynomial time. It also establishes supporting properties of MX for additive dichotomous valuations and uses conditional allocation guarantees to prove each agent’s proportional share.

C.3 Proof of the Main Theorem for ǫ-leveled Valuations

  • For additive dichotomous valuations, MX is reasonable and truthful, guarantees EF1, and an agent never envies an agent with lower priority.Source: §C.3 · p. 33
  • ML is truthful in expectation and ex-post ǫ-truthful.Each agent maximizes expected value by truthfully reporting demanded items, for any reports by the others.Source: §C.3 · p. 34
  • ML achieves at least a 1/(1+ǫ) fraction of maximum welfare ex post when agents are truthful.This follows from ML being reasonable.Source: §C.3 · pp. 34, 36
  • Each truthful agent receives their proportional share in expectation.ML can be implemented in polynomial time in the number of items and agents.Source: §C.3 · pp. 34, 37

Proof of the proportional-share guarantee

  • Combining the conditional allocation bounds with Lemma 33 shows that agent v receives her proportional share.The proof conditions on the size of Rv ∩ X and uses priority-based allocation guarantees for the resulting cases.Source: §C.3 · pp. 38–39

Implementation

  • ML can be implemented in polynomial time in the numbers of items and agents.Agents report only demand sets; MB and MX are polynomial-time, and the remaining random selection steps are efficient given a source of randomness.Source: §C.3 · pp. 39–40

D XOS valuations

The section defines dichotomous XOS valuations and gives limits on extending the submodular results to this broader class. It shows conflicts between truthfulness, welfare or NSW guarantees, and fairness, including large efficiency gaps for EF1 allocations.

D XOS valuations

  • An XOS valuation is the maximum of a set of additive valuations; the section's dichotomous construction takes the maximum intersection size with a family of item sets.For a family F, the construction is fF(S)=max over T in F of |T∩S|.Source: D XOS valuations · p. 40
  • A randomized truthful-in-expectation mechanism cannot always maximize welfare for two dichotomous XOS agents and four items.The same argument also rules out always maximizing NSW with such a mechanism.Source: D XOS valuations · p. 40
  • For dichotomous XOS valuations, maximum welfare can exceed the welfare of every EF1 allocation by a factor approaching 2−1/n for fixed n.The construction gives maximum welfare 2nk+n−k and bounds EF1 welfare by n(k+1); the ratio approaches 2−1/n as k grows.Source: D XOS valuations · p. 41
  • Dichotomous XOS valuations can make maximal NSW at least a factor 2−ǫ above the NSW of every EF1 allocation when n is sufficiently large.The stated bounds are maximal NSW k·(1/4)^(1/n) and EF1 NSW at most k/2+1.Source: D XOS valuations · p. 41
  • For two dichotomous XOS agents, the section rules out truthful deterministic mechanisms that always attain a c-fraction of maximum NSW when c>2−1/3.The theorem specifies the NSW approximation threshold for this two-agent setting.Source: D XOS valuations · p. 42

E Best-of-Both-Worlds via Random Priorities

For submodular dichotomous valuations, the random priority egalitarian mechanism is stochastically envy-free, and therefore ex-ante envy-free and proportional. The section also relates ex-ante fairness to proportionality and distinguishes ex-ante from stochastic envy-freeness.

E Best-of-Both-Worlds via Random Priorities

  • For subadditive valuations, any non-wasteful ex-ante envy-free randomized allocation is also ex-ante proportional.The observation applies to allocations that are not wasteful.Source: E Best-of-Both-Worlds via Random… · p. 42
  • For submodular dichotomous valuations, RPE is stochastically envy-free and therefore also ex-ante envy-free and ex-ante proportional.The proof compares Lorenz-dominating allocations under swapped priority orders, using auxiliary items and a matroid exchange argument.Source: E Best-of-Both-Worlds via Random… · pp. 42–43
  • An allocation can be ex-ante EF and ex-post EFX without being stochastically EF.In the example, agent 1 never receives value above 1, while another agent sometimes receives a bundle worth more than 1 to agent 1.Source: E Best-of-Both-Worlds via Random… · p. 44

F Allocating All Items

Theorem 1’s welfare-maximizing, EFX mechanism leaves undesired items unallocated. Requiring every item to be allocated makes those guarantees incompatible with truthful deterministic allocation, even for two additive dichotomous agents.

F Allocating All Items

  • Theorem 1’s truthful deterministic mechanism is welfare maximizing and EFX, but leaves undesired items unallocated.The impossibility arises when one insists on allocating even undesired items.Source: F Allocating All Items · p. 44
  • For two additive dichotomous agents, no truthful deterministic mechanism can be welfare maximizing, EFX, and always allocate all items.The impossibility holds even with only two agents.Source: F Allocating All Items · p. 45
  • The proof uses reports on triples sharing two items to force a repeated allocation, then derives a contradiction from truthfulness and EFX.For m ≥ 21, a counting argument finds four such triples with the same allocation; changing reports then forces agent 1 to receive at least three items including the shared pair.Source: F Allocating All Items · p. 45

G Group Strategyproofness

The appendix examines group strategyproofness and shows its limits for the paper’s mechanisms. Some guarantees hold in the additive case, but strong group strategyproofness and related ex-ante or randomized properties are not generally achieved.

G Group Strategyproofness

  • Strong group strategyproofness is unavailable alongside Pareto optimality for the submodular dichotomous setting, since it contains unit-demand valuations.The cited prior result rules out strongly group-strategyproof Pareto-optimal deterministic mechanisms for unit-demand dichotomous valuations.Source: G Group Strategyproofness · p. 45
  • No randomized mechanism for submodular dichotomous valuations can be ex-ante strongly group strategyproof, ex-post Pareto optimal, and EF1 simultaneously.The impossibility is established using three agents and four items.Source: G Group Strategyproofness · p. 45
  • For additive dichotomous valuations, PE is weakly group strategyproof, but not strongly group strategyproof.The failure of strong group strategyproofness occurs even with additive dichotomous valuations.Source: G Group Strategyproofness · p. 46
  • RPE is neither ex-ante Lorenz dominating nor weakly group strategyproof, even for additive dichotomous valuations.The examples show an expected-value shortfall from the fractional Lorenz-dominating allocation and a group deviation that benefits its members in expectation.Source: G Group Strategyproofness · p. 46

Related papers

Loading 2002.10704v3…