Positional scoring-based allocation of indivisible goods
Positional scoring-based allocation of indivisible goods
复制标题
DOI：
10.1007/s10458-016-9340-x
复制
发表时间：
2016-08
影响因子：
1.9
通讯作者：
Dorothea Baumeister;S. Bouveret;J. Lang;Nhan-Tam Nguyen;T. Nguyen;J. Rothe;Abdallah Saffidine
中科院分区：
文献类型：
--
作者：
Dorothea Baumeister;S. Bouveret;J. Lang;Nhan-Tam Nguyen;T. Nguyen;J. Rothe;Abdallah Saffidine
我们定义了一个家庭的规则dividingmindivisible商品代理，参数化的评分向量和社会福利聚合函数。我们假设代理人对商品的偏好是可加的，但输入是有序的：每个代理人通过对单个商品进行排名来报告她的偏好。类似于投票中的位置评分规则，评分向量由m个非递增的非负权重组成，其中是分配给代理的商品评分，代理将其排名为位置i。分配给一个代理人的全局分数是分配给她的商品的分数之和。分配的社会福利是所有代理人的分数的总和，对于某些聚合函数，例如，通常，或。与sandmap关联的规则将配置文件映射到最大化社会福利的分配（之一）。在定义了这一系列的规则，并专注于一些关键的例子，我们调查的一些社会选择理论的性质，这一系列的规则，如各种单调性，可分性。最后，我们专注于计算获胜的分配，并对他们的近似：我们表明，常用的评分向量和聚合功能，这个问题是NP难的，我们展示了一些易于处理的特殊情况。
We define a family of rules for dividingmindivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents’ preferences over sets of goods are additive, but that the input is ordinal: each agent reports her preferences simply by ranking single goods. Similarly to positional scoring rules in voting, a scoring vectorconsists ofmnonincreasing, nonnegative weights, whereis the score of a good assigned to an agent who ranks it in positioni. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation functionsuch as, typically,or. The rule associated withsandmaps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation: we show that for commonly used scoring vectors and aggregation functions this problem is NP-hard and we exhibit some tractable particular cases.