A note on maximizing the minimum voter satisfaction on spanning trees
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.
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Brams, Steven J., 1994.
Handbook of Game Theory with Economic Applications,
in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 2, chapter 30, pages 1055-1089
- Dutta, Bhaskar & Kar, Anirban, 2002.
"Cost Monotonicity, Consistency And Minimum Cost Spanning Tree Games,"
The Warwick Economics Research Paper Series (TWERPS)
629, University of Warwick, Department of Economics.
- Dutta, Bhaskar & Kar, Anirban, 2004. "Cost monotonicity, consistency and minimum cost spanning tree games," Games and Economic Behavior, Elsevier, vol. 48(2), pages 223-248, August.
- Bhaskar Dutta & Anirban Kar, 2002. "Cost monotonicity, consistency and minimum cost spanning tree games," Indian Statistical Institute, Planning Unit, New Delhi Discussion Papers 02-04, Indian Statistical Institute, New Delhi, India.
- Darmann, Andreas & Klamler, Christian & Pferschy, Ulrich, 2009. "Maximizing the minimum voter satisfaction on spanning trees," Mathematical Social Sciences, Elsevier, vol. 58(2), pages 238-250, September.
When requesting a correction, please mention this item's handle: RePEc:eee:matsoc:v:60:y:2010:i:1:p:82-85. See general information about how to correct material in RePEc.
If references are entirely missing, you can add them using this form.