A note on maximizing the minimum voter satisfaction on spanning trees

Andreas Darmann, Christian Klamler and Ulrich Pferschy

Mathematical Social Sciences, 2010, vol. 60, issue 1, 82-85

Abstract: A fair spanning tree of a graph maximizes the minimum satisfaction among individuals given their preferences over the edges of the graph. In this note we answer an open question about the computational complexity of determining fair spanning trees raised in Darmann et al. (2009). It is shown that the maximin voter satisfaction problem under choose-t elections is -complete for each fixed t>=2.

Keywords: Minimal; spanning; tree; Social; choice; Fairness (search for similar items in EconPapers)
Date: 2010
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/S0165-4896(10)00036-3
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:60:y:2010:i:1:p:82-85

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 ().