Coalition Structure Generation Utilizing Compact Characteristic Function Representations
Coalition Structure Generation Utilizing Compact Characteristic Function Representations
复制标题
DOI：
10.1007/978-3-642-04244-7_49
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
Naoki Ohta;Vincent Conitzer;Ryo Ichimura;Y. Sakurai;Atsushi Iwasaki;M. Yokoo
中科院分区：
文献类型：
--
作者：
Naoki Ohta;Vincent Conitzer;Ryo Ichimura;Y. Sakurai;Atsushi Iwasaki;M. Yokoo
提出了一种新的联盟结构生成问题（CSG）的形式化方法，以便将约束优化技术应用于CSG。CSG涉及将一组代理划分为联盟，以便最大化社会盈余。传统上，CSG问题的输入是一个称为特征函数的黑盒函数，它将联盟作为输入并返回联盟的值。因此，将约束优化技术应用于该问题是不可行的。然而，在实践中经常出现的特征函数可以用一组规则来简洁地表示，而不是单个黑盒函数。然后，我们可以更有效地解决CSG问题的约束优化技术的紧凑表示直接。我们提出了新的形式化的CSG问题，利用最近开发的紧凑表示方案的特征功能。我们首先描述的复杂性的CSG下，这些表示方案。在这种情况下，复杂性更多地由规则的数量而不是代理的数量驱动。此外，作为开发用于解决CSG问题的有效约束优化算法的第一步，我们开发了混合整数规划公式，并表明现成的优化包可以执行得相当好，即，它可以用几百个代理解决实例，而最先进的算法（不使用紧凑表示）可以用多达27个代理解决实例。
This paper presents a new way of formalizing the Coalition Structure Generation problem (CSG), so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG involves partitioning a set of agents into coalitions so that social surplus is maximized. Traditionally, the input of the CSG problem is a black-box function called acharacteristic function, which takes a coalition as an input and returns the value of the coalition. As a result, applying constraint optimization techniques to this problem has been infeasible. However, characteristic functions that appear in practice often can be represented concisely by a set of rules, rather than a single black-box function. Then, we can solve the CSG problem more efficiently by applying constraint optimization techniques to the compact representation directly.We present new formalizations of the CSG problem by utilizing recently developed compact representation schemes for characteristic functions. We first characterize the complexity of the CSG under these representation schemes. In this context, the complexity is driven more by the number of rules rather than by the number of agents. Furthermore, as an initial step towards developing efficient constraint optimization algorithms for solving the CSG problem, we develop mixed integer programming formulations and show that an off-the-shelf optimization package can perform reasonably well, i.e., it can solve instances with a few hundred agents, while the state-of-the-art algorithm (which does not make use of compact representations) can solve instances with up to 27 agents.