Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6896390 | European Journal of Operational Research | 2015 | 12 Pages |
Abstract
We consider the problem of allocating indivisible goods to agents who have preferences over the goods. In such a setting, a central task is to maximize social welfare. In this paper, we assume the preferences to be additive and measure social welfare by means of the Nash product. We focus on the computational complexity involved in maximizing Nash product social welfare when scores inherent in classical voting procedures such as approval or Borda voting are used to associate utilities with the agents' preferences. In particular, we show that the maximum Nash product social welfare can be computed efficiently when approval scores are used, while for Borda and lexicographic scores the corresponding decision problem becomes NP-complete.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Andreas Darmann, Joachim Schauer,