Alliances, partnerships and the Banzhaf semivalue

The coordination of strategies in a cooperative game, when some players decide to act together, is the basis of the partnership notion. Nevertheless, in some situations, it may be more convenient to form an effective coalition or alliance. In this work, we consider the Banzhaf semivalue and use it to discuss the convenience to form either partnerships or alliances, especially in simple games. Throughout the paper, some mathematical properties of the Banzhaf semivalue, in relation with the partnership formation, are derived.     

On cooperative games,inseparable by semivalues

Semivalues like the Shapley value and the Banzhaf value may assign the same payoff vector to different games. It is even possible that two games attain the same outcome for all semivalues. Due to the linearity of the semivalues, this exactly occurs in case the difference of the two games is an element of the kernel of each semivalue. The intersection of these kernels is called the shared kernel, and its game theoretic importance is that two games can be evaluated differently by semivalues if and only if their difference is not a shared kernel element. The shared kernel is a linear subspace of games. The corresponding linear equality system is provided so that one is able to check membership. The shared kernel is spanned by specific {–1,0,1}-valued games, referred to as shuffle games. We provide a basis with shuffle games, based on an a-priori given ordering of the players.     

A general procedure to compute mixed modified semivalues for cooperative games with structure of coalition blocks

Semivalues are solution concepts for cooperative games that assign to each player a weighted sum of his/her marginal contributions to the coalitions, where the weights only depend on the coalition size. The Shapley value and the Banzhaf value are semivalues. Mixed modified semivalues are solutions for cooperative games when we consider a priori coalition blocks in the player set. For all these solutions, a computational procedure is offered in this paper.     

Partnership formation with age-dependent preferences

We analyze a model of partnership formation in which players’ preferences are based on the age of a prospective partner. There are two classes of individuals, called for convenience here male and female. Males and females are fertile for the same length of time, normalized to one unit. A male enters the mating pool at age 0 and meets prospective partners according to a Poisson process. At equilibrium, he accepts a female if the utility from mating exceeds the expected utility from future search, which depends on the acceptance strategies of all males and females and the corresponding steady-state distribution of age in the pool of unmated individuals. Females face an analogous problem. Mating pairs are only formed by mutual consent and individuals leave the pool of unmated individuals on finding a mating partner or reaching the age of 1. A policy iteration algorithm is used to determine the equilibrium acceptance strategies and the corresponding steady-state distribution of the age of individuals in the mating pool. Two examples are presented.     

Partnership formation based on multiple traits

A model of partnership formation based on two traits, called beauty and character, is presented. There are two classes of individual and partners must be of different classes. Individuals prefer prospective partners with a high beauty measure and of a similar character. This problem may be interpreted as e.g. a job search problem in which the classes are employer and employee, or a mate choice problem in which the classes are male and female. Beauty can be observed instantly. However, a costly date (or interview) is required to observe the character of a prospective partner. On observing the beauty of a prospective partner, an individual decides whether he/she wishes to date. During a date, the participants observe each other’s character and then decide whether to form a pair. Mutual acceptance is required both for a date to occur and pair formation. On finding a partner, an individual stops searching. Beauty has a continuous distribution on a finite interval, while character ‘forms a circle’ and has a uniform distribution. Criteria based on the concept of a subgame perfect Nash equilibrium are used to define a symmetric equilibrium of this game. It is argued that this equilibrium is unique. When dating costs are high, this equilibrium is a block separating equilibrium as in more classical formulations of two-sided job search problems. However, for sufficiently small dating costs the form of this equilibrium is essentially different.     

Values of games with graph restricted communication and a priori unions

Two new values for transferable utility games with graph restricted communication and a priori unions are introduced and characterized. Moreover, a comparison between these and the Owen graph value is provided. These values are used to analyze the distribution of power in the Basque Parliament emerging from elections in April 2005.     

ON ASPIRATION SOLUTIONS IN PREDICTING COALITION FORMATION IN COOPERATIVE GAMES

This paper consists of two parts. The first part introduces the strict aspiration as a new aspiration solution concept, which is proved to be existent for any cooperative game. The second part deals with the unsolved problem put forward by Bennett [1] by showing that there is at least one payoff which is balanced, partnered and equal gains aspiration. The proof is algebraic and constructive, thus providing an algorithm for finding such aspirations.     

Two hardness results for core stability in hedonic coalition formation games

We establish NP-completeness of two problems on core stable coalitions in hedonic games. In the first problem every player has only two acceptable coalitions in his preference list, and in the second problem the preference structures arise from the distances in an underlying metric space.     

On binomial thinning and mixing

In this paper we consider the notions of binomial thinning, binomial mixing, their generalizations, certain interplay between them, associated limit theorems and provide various examples.     

Bargaining set theory and stability in coalition governments

Various bargaining set theories are compared as predictors of coalition government portfolio distribution. While the kernel and B₁-bargaining set are known to exist in voting games with side payments, it is argued that the kernel, and thus B₁, are poor predictors. The B₂-bargaining set, a subset of B₁, when it exists is shown to be a good payoff predictor in a fractionalized and depolarized parliamentary situation (Finland: 1945ndash;1971). Moreover this predictor provides some explanation for the formation of surplus (winning but not minimal) coalitions.     

A binomial sum related to Wolstenholme's theorem

A certain alternating sum u(n) of n+1 products of two binomial coefficients has a property similar to Wolstenholme's theorem, namely for all primes p?5. However, this congruence also holds for certain composite integers p which appear to always have exactly two prime divisors, one of which is always 2 or 5. This phenomenon will be partly explained and the composites in question will be characterized. We also study the sequence u(n) in greater detail, especially its growth and its sign distribution.     

Seven equivalent binomial sums

Seven binomial sums including four of Ruehr (1980) are shown to be equipollent by means of the Lambert series on binomial coefficients.     

Bell polynomials and binomial type sequences

This paper concerns the study of the Bell polynomials and the binomial type sequences. We mainly establish some relations tied to these important concepts. Furthermore, these obtained results are exploited to deduce some interesting relations concerning the Bell polynomials which enable us to obtain some new identities for the Bell polynomials. Our results are illustrated by some comprehensive examples.     

Stationary perfect equilibria of an n-person noncooperative bargaining game and cooperative solution concepts

This paper characterizes the stationary (subgame) perfect equilibria of an n-person noncooperative bargaining model with characteristic functions, and provides strategic foundations of some cooperative solution concepts such as the core, the bargaining set and the kernel. The contribution of this paper is twofold. First, we show that a linear programming formulation successfully characterizes the stationary (subgame) perfect equilibria of our bargaining game. We suggest a linear programming formulation as an algorithm for the stationary (subgame) perfect equilibria of a class of n-person noncooperative games. Second, utilizing the linear programming formulation, we show that stationary (subgame) perfect equilibria of n-person noncooperative games provide strategic foundations for the bargaining set and the kernel.     

Negation of binomial coefficients

We extend the concept of a binomial coefficient to all integer values of its parameters. Our approach is purely algebraic, but we show that it is equivalent to the evaluation of binomial coefficients by means of the Γ-function. In particular, we prove that the traditional rule of “negation” is wrong and should be substituted by a slightly more complex rule. We also show that the “cross product” rule remains valid for the extended definition.     

On recurrences for sums of powers of binomial coefficients

The recurrence for sums of powers of binomial coefficients is considered and a lower bound for the minimal length of the recurrence is obtained by using the properties of congruence.

Video abstract

For a video summary of this paper, please visit http://www.youtube.com/watch?v=jwy6B4aYR-Q.     

p-Catalan numbers and squarefree binomial coefficients

In this paper, we consider the generalized Catalan numbers , which we call s-Catalan numbers. For p prime, we find all positive integers n such that p^q divides F(p^q,n), and also determine all distinct residues of , q?1. As a byproduct we settle a question of Hough and the late Simion on the divisibility of the 4-Catalan numbers by 4. In the second part of the paper we prove that if pq?99999, then is not squarefree for n?τ₁(p^q) sufficiently large (τ₁(p^q) computable). Moreover, using the results of the first part, we find n<τ₁(p^q) (in base p), for which may be squarefree. As consequences, we obtain that is squarefree only for n=1,3,45, and is squarefree only for n=1,4,10.     

On some questions of Razpet regarding binomial coefficients

We answer two questions of Razpet (Discrete Math. 135 (1994) 377) regarding finite submatrices of the Pascal triangle. One of these has been solved independently in another way by Bayat and Teimoori (Linear Algebra Appl. 308 (2000) 65).