Fair and Efficient Allocations Without Obvious Manipulations Article Swipe

MAKE IMPACT

Alexandros Psomas , Paritosh Verma · YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2206.11143

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 Troyan and Morrill. 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.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2206.11143

PDF

https://arxiv.org/pdf/2206.11143

OA Status

green

Cited By

7

Related Works

10

OpenAlex ID

https://openalex.org/W4283390104

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4283390104

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2206.11143

Digital Object Identifier

Title

Fair and Efficient Allocations Without Obvious Manipulations

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2022

Year of publication

Publication date

2022-06-22

Full publication date if available

Authors

Alexandros Psomas, Paritosh Verma

List of authors in order

Landing page

https://arxiv.org/abs/2206.11143

Publisher landing page

PDF URL

https://arxiv.org/pdf/2206.11143

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2206.11143

Direct OA link when available

Concepts

Pareto efficiency, Mathematical economics, Valuation (finance), Pareto principle, Relaxation (psychology), Nash equilibrium, Social Welfare, Computer science, Social choice theory, Mathematical optimization, Incentive, Set (abstract data type), Microeconomics, Economics, Mathematics, Finance, Programming language, Law, Political science, Psychology, Social psychology

Top concepts (fields/topics) attached by OpenAlex

Cited by

7

Total citation count in OpenAlex

Citations by year (recent)

2025: 2, 2024: 3, 2023: 2

Per-year citation counts (last 5 years)

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload