STRUCTURES OF VALUES FOR SET GAMES RESTRICTED BY PARTITION SYSTEM

§1IntroductionA cooperative game with transferable utility(TU)is a pair(N,v),where N is anonempty,finite set and v∶2N→R is a characteristic function defined on the power set ofN satisfying v()∶=0.LetCGdenote the set of all cooperative TU-games with anarbitrary player set.An element of N(notation:i∈N)and a nonempty subset S of N(notation:S N or S∈2Nwith S≠)are called a player and coalition respectively,andthe associated real number v(S)is called the worth of coalition S to be in…     

The Myerson Value and Superfluous Supports in Union Stable Systems

In this paper, the set of feasible coalitions in a cooperative game is given by a union stable system. Well-known examples of such systems are communication situations and permission structures. Two games associated with a game on a union stable system are the restricted game (on the set of players in the game) and the conference game (on the set of supports of the system). We define two types of superfluous support property through these two games and provide new characterizations for the Myerson value. Finally, we analyze inheritance of properties between the restricted game and the conference game.     

Games induced by the partitioning of a graph

The paper aims at generalizing the notion of restricted game on a communication graph, introduced by Myerson. We consider communication graphs with weighted edges, and we define arbitrary ways of partitioning any subset of a graph, which we call correspondences. A particularly useful way to partition a graph is obtained by computing the strength of the graph. The strength of a graph is a measure introduced in graph theory to evaluate the resistance of networks under attacks, and it provides a natural partition of the graph (called the Gusfield correspondence) into resistant components. We perform a general study of the inheritance of superadditivity and convexity for the restricted game associated with a given correspondence. Our main result is to give for cycle-free graphs necessary and sufficient conditions for the inheritance of convexity of the restricted game associated with the Gusfield correspondence.     

Values and potential of games with cooperation structure

Games with cooperation structure are cooperative games with a family offeasible coalitions, that describes which coalitions can negotiate in the game. We study a model ofcooperation structure and the corresponding restricted game, in which the feasible coalitions are those belonging to apartition system. First, we study a recursive procedure for computing the Hart and Mas-Colell potential of these games and we develop the relation between the dividends of Harsanyi in the restricted game and the worths in the original game. The properties ofpartition convex geometries are used to obtain formulas for theShapley andBanzhaf values of the players in the restricted game in terms of the original gamev. Finally, we consider the Owen multilinear extension for the restricted game.The author is grateful to Paul Edelman, Ulrich Faigle and the referees for their comments and suggestions. The proof of Theorem 1 was proposed by the associate editor's referee.     

The modified stochastic game

We present a new tool for the study of multiplayer stochastic games, namely the modified game, which is a normal-form game that depends on the discount factor, the initial state, and for every player a partition of the set of states and a vector that assigns a real number to each element of the partition. We study properties of the modified game, like its equilibria, min–max value, and max–min value. We then show how this tool can be used to prove the existence of a uniform equilibrium in a certain class of multiplayer stochastic games.     

On-line Chain Partitions of Up-growing Semi-orders

On-line chain partition is a two-player game between Spoiler and Algorithm. Spoiler presents a partially ordered set, point by point. Algorithm assigns incoming points (immediately and irrevocably) to the chains which constitute a chain partition of the order. The value of the game for orders of width w is a minimum number val(w) such that Algorithm has a strategy using at most val(w) chains on orders of width at most w. We analyze the chain partition game for up-growing semi-orders. Surprisingly, the golden ratio comes into play and the value of the game is $\big\lfloor\frac{1+\sqrt{5}}{2}\; w \big\rfloor$ .     

On the determination of the worst sampling error in a communication system for pulse-amplitude-modulated signals. I: The general model

We present a mathematical model of a communication system perturbed by statistical sampling errors (timing jitter). The aim is to find an ‘optimal’ impulse response for the system, the optimization problem actually being a minimax problem. that is we put the model into a game-theoretical framework. The basic game turns out to be a statistical game similar to those arising from estimation problems in statistics. Earlier results concerning least-favourable sampling error distributions published by Krabs and Vogel are supplemented by estimations of the number of support points of the least-favourable distribution. Furthermore, we state the existence of the saddle points of our game, which formerly has only been proved for some special cases. In the first part we treat the general situation, where one strategy set for the game—the set of all feasible impulse responses—forms a vector space with infinite dimension. In the second part we discuss the problem in the case that the impulse responses are restricted to a finite-dimensional subspace of the whole infinite-dimensional subspace.     

The cohesiveness of subgroups in social networks: A view from game theory

A family of cohesiveness measures, based on game theoretical concepts, is proposed for subgroups in social networks. Given a communication situation, consisting of a coalitional game and a graph, both defined on the same set of players-nodes, cohesiveness of a subset is defined as the proportion of their worth that the players in subset retain, when the originally deterministic (restricted) graph becomes a probabilistic one (in a specific manner). Conditions on the game are given to reach some desirable properties.     

Construction of a maximal stable bridge in games with simple motions on the plane

It is known that the solvability set (the maximal stable bridge) in a zero-sum differential game with simple motions, fixed terminal time, geometric constraints on the controls of the first and second players, and convex terminal set can be constructed by means of a program absorption operator. In this case, a backward procedure for the construction of t-sections of the solvability set does not need any additional partition times. We establish the same property for a game with simple motions, polygonal terminal set (which is generally nonconvex), and polygonal constraints on the players’ controls on the plane. In the particular case of a convex terminal set, the operator used in the paper coincides with the program absorption operator.     

Weighted multiple majority games with unions: Generating functions and applications to the European Union

An a priori system of unions or coalition structure is a partition of a finite set of players into disjoint coalitions which have made a prior commitment to cooperate in playing a game. This paper provides “ready-to-apply” procedures based on generating functions that are easily implementable to compute coalitional power indices in weighted multiple majority games. As an application of the proposed procedures, we calculate and compare coalitional power indices under the decision rules prescribed by the Treaty of Nice and the new rules proposed by the Council of the European Union.