人工智能中的不可分项目分配：寻找合意集合

"不可分项分配问题中的代理人选择" 在不可分项分配问题中，一组代理人需要共同决定如何分配有限的、不可分割的资源。这个问题在人工智能领域有着广泛的研究价值，因为它涉及到资源的效率分配和公平性。传统的资源分配问题通常关注的是如何最大化社会福利或者消除嫉妒，确保每个代理人都对分配的结果感到满意。然而，本文探讨的是一个更特殊的情况，即代理人并非独立行动，而是作为一个集体来接受资源分配。 文章的核心在于寻找一个“合意的”项目子集，这表示这个子集对所有的代理人都至少是可接受的，即使他们可能有各自不同的偏好。对于任意数量的代理人和项目，作者们确定了一个最坏情况下的界限，即最少需要多少个项目才能让所有代理人都能接受。他们提出了一种多项式时间算法，当代理人数量为2或3时，该算法能找到大小匹配这个最坏情况界限的合适子集。 此外，研究还考虑了在只有单一项目偏好信息的情况下找到小规模合意集合的可能性。这里，代理人对项目的偏好可能通过预言机模型或添加剂实用性模型来表达。在这些模型中，他们建立了近似比率的紧界，并提出了能在多项式时间内运行的算法来有效地找到接近最小规模的合意集合。 文章进一步深入，分析了如何在各种偏好表示模型下近似计算出最优解，包括预测模型和加性效用模型。这些问题的解决对于理解在实际应用中如何在有限信息和复杂偏好条件下实现公平且高效的资源分配具有重要意义。 这篇论文在不可分项分配问题上做出了理论贡献，不仅定义了合意集合的概念，还提供了解决方法，特别是在代理人数量相对较小的情况下。它强调了在集体决策中找到共同可接受的解决方案的重要性，为未来在人工智能和资源管理领域的研究提供了理论基础。