EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

Allocation of Indivisible Items With a Common Preference Graph: Minimizing Total Dissatisfaction

Nina Chiarelli, Clément Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Peter Muršič, Ulrich Pferschy

Networks · 15.05.2026

DOI: 10.1002/net.70040 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Networks, online erschienen am 15.05.2026. Verfasst von Nina Chiarelli und 6 weiteren Autor:innen. Die Arbeit nennt 42 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0). Gefördert von: OeAD-GmbH, Javna Agencija za Raziskovalno Dejavnost RS.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Allocating indivisible items among a set of agents is a frequently studied discrete optimization problem. In the setting considered in this work, the agents' preferences over the items are assumed to be identical. We consider a very recent measure for the overall quality of an allocation which does not rely on numerical valuations of the items. Instead, it captures the agents' opinion by a directed acyclic preference graph with vertices representing items. An arc in such a graph means that the agents prefer item over item . For a given allocation of items the dissatisfaction of an agent is defined as the number of items which the agent does not receive and for which no more preferred item is given to the agent. Our goal is to find an efficient allocation of the items to the agents such that the total dissatisfaction over all agents is minimized. We explore the dichotomy between NP ‐hard and polynomially solvable instances, depending on properties of the underlying preference graph. While the problem is NP ‐hard for three agents even on very restricted graph classes, it is polynomially solvable for two agents on general preference graphs. For an arbitrary number of agents, we derive polynomial‐time algorithms for relevant restrictions of the underlying undirected graph. These are trees and, among the graphs of treewidth two, series–parallel graphs and cactus graphs.

Förderung

  • OeAD-GmbH
  • Javna Agencija za Raziskovalno Dejavnost RS

Zitieren

APA

Chiarelli, N., Dallard, C., Darmann, A., Lendl, S., Milanič, M., Muršič, P., & Pferschy, U. (2026). Allocation of Indivisible Items With a Common Preference Graph: Minimizing Total Dissatisfaction. Networks. https://doi.org/10.1002/net.70040

Vancouver

Chiarelli N, Dallard C, Darmann A, Lendl S, Milanič M, Muršič P, et al. Allocation of Indivisible Items With a Common Preference Graph: Minimizing Total Dissatisfaction. Networks. 2026. doi:10.1002/net.70040

BibTeX
@article{Chiarelli2026,
  author = {Chiarelli, Nina and Dallard, Clément and Darmann, Andreas and Lendl, Stefan and Milanič, Martin and Muršič, Peter and Pferschy, Ulrich},
  title = {Allocation of Indivisible Items With a Common Preference Graph: Minimizing Total Dissatisfaction},
  journal = {Networks},
  year = {2026},
  doi = {10.1002/net.70040}
}
Kostenlos starten →