Generalized binary utility functions and fair allocations

Franklin Camacho, Rigoberto Fonseca-Delgado, Ramón Pino Pérez and Guido Tapia

Mathematical Social Sciences, 2023, vol. 121, issue C, 50-60

Abstract: The problem of finding envy-free allocations of indivisible goods cannot always be solved; therefore, it is common to study some relaxations such as envy-free up to one good (EF1) and envy-free up to any positively valued good (EFX). Another property of interest for the efficiency of an allocation is the Pareto Optimality (PO). Under additive utility functions for goods, it is possible to find EF1 and PO allocations using the Nash social welfare. However, finding an allocation that maximizes the Nash social welfare is a computationally costly problem. Maximizing the utilitarian social welfare subject to EF1 constraints is an NP-complete problem for the case where three or more agents participate. In this work, we propose a restricted case of additive utility functions called generalized binary utility functions. The proposed utilities are a generalization of binary and identical utilities simultaneously. In this scenario, we present a polynomial-time algorithm that maximizes the utilitarian social welfare and, at the same time, produces an EF1 and PO allocation for goods as well as for chores. Moreover, a slight modification of our algorithm gives a better allocation: one which is EFX.

Keywords: Allocation of indivisible goods/chores; Envy-free up to one good/chore; Efficiency; Additive utility function (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489622000798
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:121:y:2023:i:c:p:50-60

DOI: 10.1016/j.mathsocsci.2022.10.003

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().