Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn convexity and solution concepts in cooperative interval games
119
0
0.0
(
0
)
Added by
Jan Bok
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Jan Bok
Ask ChatGPT about the research
No Arabic abstract
Cooperative interval game is a cooperative game in which every coalition gets assigned some closed real interval. This models uncertainty about how much the members of a coalition get for cooperating together. In this paper we study convexity, core and the Shapley value of games with interval uncertainty. Our motivation to do so is twofold. First, we want to capture which properties are preserved when we generalize concepts from classical cooperative game theory to interval games. Second, since these generalizations can be done in different ways, mainly with regard to the resulting level of uncertainty, we try to compare them and show their relation to each other.
rate research
Read More
Partially defined cooperative games are a generalisation of classical cooperative games in which payoffs for some of the coalitions are not known. In this paper we perform a systematic study of partially defined games, focusing on two important classes of cooperative games: convex games and positive games. In the first part, we focus on convexity and give a polynomially decidable condition for extendability and a full description of the set of symmetric convex extensions. The extreme games of this set, together with the lower game and the upper game, are also described. In the second part, we study positivity. We characterise the non-extendability to a positive game by existence of a certificate and provide a characterisation for the extreme games of the set of positive extensions. We use both characterisations to describe the positive extensions of several classes of incomplete games with special structures. Our results complement and extend the existing theory of partially defined cooperative games. We provide context to the problem of completing partial functions and, finally, we outline an entirely new perspective on a connection between partially defined cooperative games and cooperative interval games.
In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and study the structural and equilibrium properties of this new class of games. Intuitively, the potential component of a game captures interactions that can equivalently be represented as a common interest game, while the harmonic part represents the conflicts between the interests of the players. We make this intuition precise, by studying the properties of these two classes, and show that indeed they have quite distinct and remarkable characteristics. For instance, while finite potential games always have pure Nash equilibria, harmonic games generically never do. Moreover, we show that the nonstrategic component does not affect the equilibria of a game, but plays a fundamental role in their efficiency properties, thus decoupling the location of equilibria and their payoff-related properties. Exploiting the properties of the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the properties of potential and harmonic games to nearby games. We exemplify this point by showing that the set of approximate equilibria of an arbitrary game can be characterized through the equilibria of its projection onto the set of potential games.
Stochastic games, introduced by Shapley, model adversarial interactions in stochastic environments where two players choose their moves to optimize a discounted-sum of rewards. In the traditional discounted reward semantics, long-term weights are geometrically attenuated based on the delay in their occurrence. We propose a temporally dual notion -- called past-discounting -- where agents have geometrically decaying memory of the rewards encountered during a play of the game. We study past-discounted weight sequences as rewards on stochastic game arenas and examine the corresponding stochastic games with discounted and mean payoff objectives. We dub these games forgetful discounted games and forgetful mean payoff games, respectively. We establish positional determinacy of these games and recover classical complexity results and a Tauberian theorem in the context of past discounted reward sequences.
We analyze in this paper finite horizon hierarchical signaling games between (information provider) senders and (decision maker) receivers in a dynamic environment. The underlying information evolves in time while sender and receiver interact repeatedly. Different from the classical communication (control) models, however, the sender (sensor) and the receiver (controller) have different objectives and there is a hierarchy between the players such that the sender leads the game by announcing his policies beforehand. He needs to anticipate the reaction of the receiver and the impact of the actions on the horizon while controlling the transparency of the disclosed information at each interaction. With quadratic cost functions and multivariate Gaussian processes, evolving according to first order auto-regressive models, we show that memoryless linear sender signaling rules are optimal (in the sense of game-theoretic hierarchical equilibrium) within the general class of measurable policies in the noncooperative communication context. In the noncooperative control context, we also analyze the hierarchical equilibrium for linear signaling rules and provide an algorithm to compute the optimal linear signaling rules numerically with global optimality guarantees.
We consider the question of whether, and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. In the first setting, we consider games where each players weight is small. We prove that when the number of players goes to infinity and their weights to zero, the random flows in all (mixed) Nash equilibria for the finite games converge in distribution to the set of Wardrop equilibria of the corresponding nonatomic limit game. In the second setting, we consider an increasing number of players with a unit weight that participate in the game with a decreasingly small probability. In this case, the Nash equilibrium flows converge in total variation towards Poisson random variables whose expected values are Wardrop equilibria of a different nonatomic game with suitably-defined costs. The latter can be viewed as symmetric equilibria in a Poisson game in the sense of Myerson, establishing a plausible connection between the Wardrop model for routing games and the stochastic fluctuations observed in real traffic. In both settings we provide explicit approximation bounds, and we study the convergence of the price of anarchy. Beyond the case of congestion games, we prove a general result on the convergence of large games with random players towards Poisson games.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
