Complexity of the Object Allocation Problem with Minimum Number of Changes

Umutcan Salman ()
Additional contact information
Umutcan Salman: University of Padova

No 323, "Marco Fanno" Working Papers from Dipartimento di Scienze Economiche "Marco Fanno"

Abstract: This paper studies the problem of reallocating objects to agents while taking into account agents’ endowments, object capacities and agents’ preferences. The goal is to find a Pareto efficient and individually rational allocation that minimizes the number of individuals who need to change from their initial allocation to the final one. We call this problem as MINDIST. We establish NP-completeness result for MINDIST. We also show that MINDIST remains NP-complete when we restrict individual preferences to be binary, meaning that each individual can rank at most two objects in the preferences. Finally, we present an integer programming formulation to solve small to moderately sized instances of the NP-hard problems.

Keywords: : Object allocation; Pareto-efficiency; Individual Rationality; Computational complexity; Minimum changes (search for similar items in EconPapers)
Pages: 25 pages
References: Add references at CitEc
Citations:

Downloads: (external link)
https://economia.unipd.it/sites/economia.unipd.it/files/20250323.pdf (application/pdf)

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:pad:wpaper:0323

Access Statistics for this paper

More papers in "Marco Fanno" Working Papers from Dipartimento di Scienze Economiche "Marco Fanno" Contact information at EDIRC.
Bibliographic data for series maintained by Raffaele Dei Campielisi ().