论文标题
关于在K-Coalitional Hedonic游戏中最大化平等价值
On Maximizing Egalitarian Value in K-coalitional Hedonic Games
论文作者
论文摘要
本文考虑了将代理之间分配给联盟的问题。我们专注于可分离的享乐游戏（ASHG），其中每个代理商对其他每个代理商都有非负值，而她的效用是她分配给联盟成员的价值观的总和。与以前的工作不同，我们分析了必须恰好成立$ k $联盟的模型，目标是最大程度地利用最糟糕的代理商的效用，即平等主义的社会福利。我们表明，即使应在联盟之间平均分配代理人的数量，这个问题也很困难。因此，我们提出了一种启发式，以最大化平等主义的社会福利，并最大化每个代理人作为次要目标的平均效用。使用广泛的模拟，无论是在合成和真实数据上，我们都证明了方法的有效性。具体来说，我们的启发式方法提供的解决方案比最大化平均社会福利的解决方案要公平得多，同时仍提供相对较高的平均社会福利。
This paper considers the problem of dividing agents among coalitions. We concentrate on Additively Separable Hedonic Games (ASHG's), in which each agent has a non-negative value for every other agent and her utility is the sum of the values she assigns to the members of her coalition. Unlike previous work, we analyze a model where exactly $k$ coalitions must be formed, and the goal is to maximize the utility of the agent which is worst off, i.e., the egalitarian social welfare. We show that this problem is hard, even when the number of agents should be equally divided among the coalitions. We thus propose a heuristic that maximizes the egalitarian social welfare and maximizes the average utility of each agent as a secondary goal. Using extensive simulations, both on synthetic and real data, we demonstrate the effectiveness of our approach. Specifically, our heuristic provides solutions that are much fairer than the solutions that maximize the average social welfare, while still providing a relatively high average social welfare.
