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


TD3 Game Theory and Multicriteria Decision
June 10, 2021  2:45 PM
3 - TC Koopmans

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.