Condorcet winner configurations of linear networks

Abstract

We consider the problem of locating a fixed number of facilities along a line to serve n players. We model this problem as a cooperative game and assume that any locational configuration can be eventually disrupted through a strict majority of players voting for an alternative configuration. A solution of such a voting location problem is called a Condorcet winner configuration. In this article, we state three necessary and one sufficient condition for a configuration to be a Condorcet winner. Consequently, we propose a fast algorithm which enables us to verify whether a given configuration is a Condorcet winner, and can be efficiently used also for computing the (potentially empty) set of all Condorcet winner configurations.

Keywords::

• facility location
• majority voting
• algorithms

AMS Subject Classifications::

• 91B12
• 91B18
• 68Q25

Acknowledgements

This work was supported by the VEGA grant 1/3001/06, VVGS grant 36/2006 and Science and Technology Assistance Agency contract No. APVT-20-004104.