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.
References listed on IDEAS
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.:
- 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.
- 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.
- Brams, Steven J. & Fishburn, Peter C., 2002.
Handbook of Social Choice and Welfare,
in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 4, pages 173-236
- Brams, Steven J., 1994. "Voting procedures," 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 Elsevier.
- 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.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.