Darmann Andreas, Nicosia Gaia, Pferschy Ulrich, Schauer Joachim
University of Graz, Institute of Public Economics, Universitaetsstr. 15, A-8010 Graz, Austria.
Dipartimento di Ingegneria, Università degli Studi "Roma Tre", via della Vasca Navale 79, 00146 Rome, Italy.
Eur J Oper Res. 2014 Mar 16;233(3):539-549. doi: 10.1016/j.ejor.2013.08.047.
In this work we address a game theoretic variant of the Subset Sum problem, in which two decision makers (agents/players) compete for the usage of a common resource represented by a knapsack capacity. Each agent owns a set of integer weighted items and wants to maximize the total weight of its own items included in the knapsack. The solution is built as follows: Each agent, in turn, selects one of its items (not previously selected) and includes it in the knapsack if there is enough capacity. The process ends when the remaining capacity is too small for including any item left. We look at the problem from a single agent point of view and show that finding an optimal sequence of items to select is an [Formula: see text]-hard problem. Therefore we propose two natural heuristic strategies and analyze their worst-case performance when (1) the opponent is able to play optimally and (2) the opponent adopts a greedy strategy. From a centralized perspective we observe that some known results on the approximation of the classical Subset Sum can be effectively adapted to the multi-agent version of the problem.
在这项工作中，我们研究子集和问题的一种博弈论变体，其中两个决策者（智能体/玩家）争夺由背包容量表示的公共资源的使用权。每个智能体拥有一组整数权重的物品，并希望使其背包中自身物品的总权重最大化。解决方案构建如下：每个智能体依次选择其一个物品（之前未被选中的），如果有足够容量则将其放入背包。当剩余容量过小而无法放入任何剩余物品时，过程结束。我们从单个智能体的角度看待该问题，并表明找到选择物品的最优序列是一个[公式：见正文]难问题。因此，我们提出两种自然的启发式策略，并分析它们在以下两种情况下的最坏情况性能：（1）对手能够最优地行动；（2）对手采用贪婪策略。从集中式角度我们观察到，一些关于经典子集和近似的已知结果可以有效地应用于该问题的多智能体版本。
