We study variants of the committee selection problem (or, equivalently, a version of the metric facility location problem) in which we must choose a committee of size k to serve a group of voters \(\mathcal {C}\) , under the spatial voting setting where candidates and voters are located in some metric space. We consider four different objectives, where each voter \(i\in \mathcal {C}\) attempts to minimize either the sum or the maximum of its distance to the chosen committee members, and where the overall objective either considers the sum or the maximum of the individual voter costs. Rather than optimizing a single objective at a time, we study how compatible these objectives are with each other, and show the existence of solutions which are simultaneously close-to-optimum for any pair of the above objectives. Our results show that when choosing a representative committee or a set of facilities, it is often possible to form a solution which is good for several objectives at the same time, instead of sacrificing one desideratum to achieve another.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Compatibility of Max and Sum Objectives for Committee Selection and k-Facility Location

  • Yue Han,
  • Elliot Anshelevich

摘要

We study variants of the committee selection problem (or, equivalently, a version of the metric facility location problem) in which we must choose a committee of size k to serve a group of voters \(\mathcal {C}\) , under the spatial voting setting where candidates and voters are located in some metric space. We consider four different objectives, where each voter \(i\in \mathcal {C}\) attempts to minimize either the sum or the maximum of its distance to the chosen committee members, and where the overall objective either considers the sum or the maximum of the individual voter costs. Rather than optimizing a single objective at a time, we study how compatible these objectives are with each other, and show the existence of solutions which are simultaneously close-to-optimum for any pair of the above objectives. Our results show that when choosing a representative committee or a set of facilities, it is often possible to form a solution which is good for several objectives at the same time, instead of sacrificing one desideratum to achieve another.