Maximizing Nash product social welfare in allocating indivisible goods

摘要

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. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.