Abstract
The main goal of the model of cooperative games is to determine in a rational way each player s payoff based on the worth of cooperation. The worth is determined by values assigned to each subset of players, so called coalitions.
These values, encoded into a characteristic function constitute the cooperative game. The main disadvantage of this approach is due to the huge number of such values (exponential in the number of players).
In many real world applications, it is either impossible or costly to collect all information representing the values. The model of incomplete cooperative games deals with these problems by setting values of certain coalitions to be unknown.
Based on the partial information, the goal remains the same - to determine each player's payoff. Different ways to determine the payoff lead to different solution concepts.
A fundamental tool for the analysis of incomplete games are the so called extensions. Those are complete games, which coincide with the incomplete game on the known values of coalitions.
Thus, an extension may be viewed as an approximation of the underlying complete cooperative game. Moreover, if we known the underlying game satisfies further properties, we can restrict to extensions with those properties, thus refine the approximation.
Based on values of coalitions of all such extensions, we can define solution concepts of incomplete games. The goals of our research are twofold.
First, we study different sets of extensions together with their solution concepts. The analysis yields different results for different structures of coalitions with known values.
More specificaly, we investigate 1-convex, convex and positive extensions of incomplete games, generalizations of standard solution concepts such as the Shapley value, nucleolus, the core or the tau-value. We also introduce the average value, a solution concept constructed specifically for incomplete games.
Second, we approach the question of optimizing the set of coalitions with known values. Imagine we want to compute the payoff distribution based on the values of coalitions and information about each value can be purchused.
In this scenario, we want to balance the precision of the computation of the solution concept and the costs we pay to acquire the knowledge about the game. In our research, we formalize several distinct ways to formalize these questions, derive their properties as well as provide discussion about their advantages and disadvantages.