论文标题
在奖励季节选择中
On Reward-Penalty-Selection Games
论文作者
论文摘要
奖励 - 季节选择问题（RPSP）可以看作是设定盖问题（SCP）和命中设定问题（HSP）的组合。给定一组元素，一组奖励集和一组罚款集，一个人试图找到一部分元素的子集，使得涵盖了尽可能多的奖励集，即，所有元素都包含在子集中，同时又有很少的罚款集，即受到罚款的相互作用，即与Emptty the Emptty the Enterment the Emptty no-Empterty Is non-Empt-Empt-Empt-Empt-Emptimenty。在本文中，我们根据RPSP定义了合作游戏，其中RPSP的元素是玩家。我们证明了结构性结果，并表明RPS游戏是凸，超级效果且完全平衡的。此外，可以在多项式时间内计算出Shapley值。除此之外，我们还根据基础RPSP的实例提供了网络图中核心元素作为可行流的表征。通过使用此表征，可以有效地计算核心元素。
The Reward-Penalty-Selection Problem (RPSP) can be seen as a combination of the Set Cover Problem (SCP) and the Hitting Set Problem (HSP). Given a set of elements, a set of reward sets, and a set of penalty sets, one tries to find a subset of elements such that as many reward sets as possible are covered, i.e. all elements are contained in the subset, and at the same time as few penalty sets as possible are hit, i.e. the intersection of the subset with the penalty set is non-empty. In this paper we define a cooperative game based on the RPSP where the elements of the RPSP are the players. We prove structural results and show that RPS games are convex, superadditive and totally balanced. Furthermore, the Shapley value can be computed in polynomial time. In addition to that, we provide a characterization of the core elements as a feasible flow in a network graph depending on the instance of the underlying RPSP. By using this characterization, a core element can be computed efficiently.
