T. Heller, S. O. Krumke
The Set Cover Problem (SCP) is a well-known combinatorial problem and is strongly related to the Hitting Set Problem (HSP). We study a combination of both problems, the Reward-Penalty-Selection Problem (RPSP) in a game theoretic setting. Given a set of elements, a set of reward sets, and a set of penalty sets, we try to find a subset of elements such that as many reward sets as possible are covered and at the same time as few penalty sets as possible are hit. Given instances of the SCP and HSP, an instance of the RPSP can be constructed by taking the sets from SCP as reward sets, the elements from the HSP as penalty sets and the elements from the SCP and from the HSP as elements. Given the RPSP, we define a combinatorial cooperative game, where the participants are given by the elements of the RPSP. We prove that RPS games are convex, totally balanced and superadditive. The Shapley value can be computed in polynomial time. In addition to that, we provide a characterization of the core elements as a maximum flow in a network graph depending on the instance of the underlying RPSP. By using this characterization, a core element can be computed in polynomial time.
Keywords: Game Theory, Combinatorial Optimization, Cooperative Games, Core Elements
Scheduled
TD3 Game Theory and Multicriteria Decision
June 10, 2021 2:45 PM
3 - TC Koopmans
