Power and welfare in bargaining for coalition structure formation

We investigate a noncooperative bargaining game for partitioning n agents into non-overlapping coalitions. The game has n time periods during which the players are called according to an exogenous agenda to propose offers. With probability \(\delta \), the game ends during any time period \(t<n\). If it does, the first t players on the agenda get a chance to propose but the others do not. Thus, \(\delta \) is a measure of the degree of democracy within the game (ranging from democracy for \(\delta =0\), through increasing levels of authoritarianism as \(\delta \) approaches 1, to dictatorship for \(\delta =1\)). We determine the subgame perfect equilibrium (SPE) and study how a player’s position on the agenda affects his bargaining power. We analyze the relation between the distribution of power of individual players, the level of democracy, and the welfare efficiency of the game. We find that purely democratic games are welfare inefficient and that introducing a degree of authoritarianism into the game makes the distribution of power more equitable and also maximizes welfare. These results remain invariant under two types of player preferences: one where each player’s preference is a total order on the space of possible coalition structures and the other where each player either likes or dislikes a coalition structure. Finally, we show that the SPE partition may or may not be core stable.     

Chain equilibria in secure strategies

In this paper we introduce a modification of the concept of Equilibrium in Secure Strategies (EinSS), which takes into account the non-uniform attitudes of players to security in non-cooperative games. In particular, we examine an asymmetric attitude of players to mutual threats in the simplest case, when all players are strictly ordered by their relation to security. Namely, we assume that the players can be reindexed so that each player i in his behavior takes into account the threats posed by players j > i but ignores the threats of players j < i provided that these threats are effectively contained by some counterthreats. A corresponding equilibrium will be called a Chain EinSS. The conceptual meaning of this equilibrium is illustrated by two continuous games that have no pure Nash equilibrium or (conventional) EinSS. The Colonel Blotto two-player game (Borel 1953; Owen 1968) for two battlefields with different price always admits a Chain EinSS with intuitive interpretation. The product competition of many players on a segment (Eaton, Lipsey 1975; Shaked 1975) with the linear distribution of consumer preferences always admits a unique Chain EinSS solution (up to a permutation of players). Finally, we compare Chain EinSS with Stackelberg equilibrium.     

When Can Limited Randomness Be Used in Repeated Games?

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist.     

Altruistic behavior in a nonantagonistic positional differential game

We consider a two-person nonantagonistic positional differential game (NPDG) whose dynamics is described by an ordinary nonlinear vector differential equation. Constraints on values of players’ controls are geometric. Final time of the game is fixed. Payoff functionals of both players are terminal. The formalization of positional strategies in an NPDG is based on the formalization and results of the general theory of antagonistic positional differential games (APDGs) (see monographs by N.N. Krasovskii and A.I. Subbotin [3, 4]). Additionally, in the present paper we assume that each player, together with the usual, normal (nor), type of behavior aimed at maximizing his own functional, can use other behavior types introduced in [2, 5]. In particular, these may be altruistic (alt), aggressive (agg), and paradoxical (par) types. It is assumed that in the course of the game players can switch their behavior from one type to another. Using the possibility of such switches in a repeated bimatrix 2 × 2 game in [5, 6] allowed to obtain new solutions of this game. In the present paper, extension of this approach to NPDGs leads to a new formulation of the problem. In particular, of interest is the question of how players’ outcomes at Nash solutions are transformed. An urgent problem is minimizing the time of “abnormal” behavior while achieving a good result. The paper proposes a formalization of an NPDG with behavior types (NPDGwBT). It is assumed that in an NPDGwBT each player, simultaneously with choosing a positional strategy, chooses also his own indicator function defined on the whole game horizon and taking values in the set {normal, altruistic, aggressive, paradoxical}. The indicator function of a player shows the dynamics of changes in the behavior type demonstrated by the player. Thus, in this NPDGwBT each player controls the choice of a pair {positional strategy, indicator function}. We define the notion of a BT-solution of such a game. It is expected that using behavior types in the NPDGwBT which differ from the normal one (so-called abnormal types) in some cases may lead to more favorable outcomes for the players than in the NPDG. We consider two examples of an NPDGwBT with simple dynamics in the plane in each of which one player keeps to altruistic behavior type over some time period. It is shown that in the first example payoffs of both players increase on a BT-solution as compared to the game with the normal behavior type, and in the second example, the sum of players’ payoffs is increased.     

Differential games of <Emphasis Type="Italic">N</Emphasis> players in stochastic systems with controlled diffusion terms

Differential Games of N players defined by stochastic systems with controlled diffusion terms are considered. Necessary conditions of equilibrium strategy are obtained. These conditions are specified for the linear quadratic differential game of N players in terms of differential Riccati equation for program and positional equilibrium situations.     

Stochastic coalitional better-response dynamics and stable equilibrium

We consider coalition formation among players in an n-player finite strategic game over infinite horizon. At each time a randomly formed coalition makes a joint deviation from a current action profile such that at new action profile all the players from the coalition are strictly benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a K-stable equilibrium or becomes stuck in a closed cycle. We also assume that at each time a selected coalition makes mistake in deviation with small probability that add mutations (perturbations) into CBR dynamics. We prove that all K-stable equilibria and all action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Similar statement holds for strict K-stable equilibrium. We apply the CBR dynamics to study the dynamic formation of the networks in the presence of mutations. Under the CBR dynamics all strongly stable networks and closed cycles of networks are stochastically stable.     

Characterizing the Nash equilibria of a three-player Bayesian quantum game

Quantum games with incomplete information can be studied within a Bayesian framework. We consider a version of prisoner’s dilemma (PD) in this framework with three players and characterize the Nash equilibria. A variation of the standard PD game is set up with two types of the second prisoner and the first prisoner plays with them with probability p and \(1-p\), respectively. The Bayesian nature of the game manifests in the uncertainty that the first prisoner faces about his opponent’s type which is encoded either in a classical probability or in the amplitudes of a wave function. Here, we consider scenarios with asymmetric payoffs between the first and second prisoner for different values of the probability, p, and the entanglement. Our results indicate a class of Nash equilibria (NE) with rich structures, characterized by a phase relationship on the strategies of the players. The rich structure can be exploited by the referee to set up rules of the game to push the players toward a specific class of NE. These results provide a deeper insight into the quantum advantages of Bayesian games over their classical counterpart.     

On an approach to constructing a characteristic function in cooperative differential games

We propose a novel approach to constructing characteristic functions in cooperative differential games. A characteristic function of a coalition S is computed in two stages: first, optimal control strategies maximizing the total payoff of the players are found, and next, these strategies are used by the players from the coalition S, while the other players, those from N S, use strategies minimizing the total payoff of the players from S. The characteristic function obtained in this way is superadditive. In addition, it possesses a number of other useful properties. As an example, we compute values of a characteristic function for a specific differential game of pollution control.     

Quantum secure two-party computation for set intersection with rational players

Recently, Shi et al. (Phys Rev A 92:022309, 2015) proposed quantum oblivious set member decision protocol where two legitimate parties, namely Alice and Bob, play a game. Alice has a secret k, and Bob has a set \(\{k_1,k_2,\ldots k_n\}\). The game is designed towards testing if the secret k is a member of the set possessed by Bob without revealing the identity of k. The output of the game will be either “Yes” (bit 1) or “No” (bit 0) and is generated at Bob’s place. Bob does not know the identity of k, and Alice does not know any element of the set. In a subsequent work (Shi et al in Quant Inf Process 15:363–371, 2016), the authors proposed a quantum scheme for private set intersection (PSI) where the client (Alice) gets the intersected elements with the help of a server (Bob) and the server knows nothing. In the present draft, we extended the game to compute the intersection of two computationally indistinguishable sets X and Y possessed by Alice and Bob, respectively. We consider Alice and Bob as rational players, i.e. they are neither “good” nor “bad”. They participate in the game towards maximizing their utilities. We prove that in this rational setting, the strategy profile ((cooperate, abort), (cooperate, abort)) is a strict Nash equilibrium. If ((cooperate, abort), (cooperate, abort)) is strict Nash, then fairness and correctness of the protocol are guaranteed.     

A model of best choice under incomplete information

This paper suggests two approaches to the construction of a two-player game of best choice under incomplete information with the choice priority of one player and the equal weights of both players. We consider a sequence of independent identically distributed random variables (x _i , y _i ), i = 1..., n, which represent the quality of incoming objects. The first component is announced to the players and the second component is hidden. Each player chooses an object based on the information available. The winner is the player whose object has a greater sum of the quality components than the opponent’s object. We derive the optimal threshold strategies and compare them for both approaches.     

Voting in collective best-choice problem with complete information

This paper considers a noncooperative m-player best-choice game with complete information about the quality parameters of incoming candidates. Collective decision-making is based on voting. The optimal threshold strategies and payoffs of the players are found depending on the voting threshold. The results of numerical simulation are presented.     

<Emphasis Type="Italic">N</Emphasis>-person credibilistic strategic game

This paper enlarges the scope of fuzzy-payoff game to n-person form from the previous two-person form. Based on credibility theory, three credibilistic approaches are introduced to model the behaviors of players in different decision situations. Accordingly, three new definitions of Nash equilibrium are proposed for n-person credibilistic strategic game. Moreover, existence theorems are proved for further research into credibilistic equilibrium strategies. Finally, two numerical examples are given to illustrate the significance of credibilistic equilibria in practical strategic games.     

A game-theoretic model of TV show “The Voice”

This paper proposes a game-theoretic model of the two-player best-choice problem with incomplete information. The players (experts) choose between objects by observing their quality in the form of two components forming a sequence of random variables (x_i, y_i), i = 1,..., n. By assumption, the first quality component x_i is known to the players and the second one y_i is hidden. A player accepts or declines an object based on the first quality component only. A player with the maximal sum of the components becomes the winner in the game. The optimal strategies are derived in the cases of independent and correlated quality components.     

Optimal arrivals in a two-server random access system with loss

This paper considers a two-server random access system with loss that receives requests on a time interval [0, T]. The users (players) send their requests to the system, and then the system provides a random access to one of its two servers with some known probabilities. We study the following non-cooperative game for this service system. As his strategy, each player chooses the time to send his request to the system, trying to maximize the probability of servicing. The symmetric Nash equilibrium acts as the optimality criterion. Two models are considered for this game. In the first model the number of players is deterministic, while in the second it obeys the Poisson distribution. We demonstrate that there exists a unique symmetric equilibrium for both models. Finally, some numerical experiments are performed to compare the equilibria under different values of the model parameters.     

The bounded core for games with restricted cooperation

A game with restricted (incomplete) cooperation is a triple (N, v, Ω), where N represents a finite set of players, Ω ? 2^N is a set of feasible coalitions such that N ∈ Ω, and v: Ω → R denotes a characteristic function. Unlike the classical TU games, the core of a game with restricted cooperation can be unbounded. Recently Grabisch and Sudhölter [9] proposed a new solution concept—the bounded core—that associates a game (N, v,Ω) with the union of all bounded faces of the core. The bounded core can be empty even if the core is nonempty. This paper gives two axiomatizations of the bounded core. The first axiomatization characterizes the bounded core for the class G^r of all games with restricted cooperation, whereas the second one for the subclass G_bc^r ? G^r of the games with nonempty bounded cores.     

Mean field games based on stable-like processes

We investigate the mean field games of N agents based on the nonlinear stable-like processes. The main result of the paper is that any solution of the limiting mean field consistency equation generates a 1/N-Nash equilibrium for the approximating game of N agents.     

Lion and Man Game and Fixed Point-Free Maps

This paper is dedicated to the pursuit-evasion game in which both players (Lion and Man) move in a metric space, have equal maximum speeds and complete information about the location of each other. We assume that evasion is successful if, for some initial positions of players, there exists a positive number p and an evader’s non-anticipative strategy guaranteeing that the distance between the players is always greater than p. We consider connection between successful evasion and such properties of the phase space as geodesics behavior and the existence of non-expanding fixed point-free self-maps.     

Validating gameplay activity inventory (GAIN) for modeling player profiles

In the present study, we validated Gameplay Activity Inventory (GAIN), a short and psychometrically sound instrument for measuring players’ gameplay preferences and modeling player profiles. In Study 1, participants in Finland (\(N=879\)) responded to a 52-item version of GAIN. An exploratory factor analysis was used to identify five latent factors of gameplay activity appreciation: Aggression, Management, Exploration, Coordination, and Caretaking. In Study 2, respondents in Canada (\(N=1322\)) and Japan (\(N=1178\)) responded to GAIN, and the factor structure of a 15-item version was examined using a Confirmatory Factor Analysis. The results showed that the short version of GAIN has good construct validity, convergent validity, and discriminant validity in Japan and in Canada. We demonstrated the usefulness of GAIN by conducting a cluster analysis to identify player types that differ in both demographics and game choice. GAIN can be used in research as a tool for investigating player profiles. Game companies, publishers and analysts can utilize GAIN in player-centric game development and targeted marketing and in generating personalized game recommendations.     

Guaranteed approach with the farthest of the runaways

Games of the family {Λ _N } _N?2 are formulated and studied with the application of generalized Isaacs’s approach. The game Λ _N is a simplest model of the counteraction of one persecutor P and coalition N of E ^N runaways for the case when the payoff is the distance up to the coalition of E ^N equal to the Euclidean distance between P and the farthest from the runaways; P is in command of the termination moment. Moreover, an approach within the limits of which in games with a smooth terminal payoff are generated strategies prescribing players’ motions in the directions of local gradients of the payoff is described. The approach is used for constructing pursuit strategies in games in which smooth approximations of the maximum of Euclidean distances up to the runaways are in place of payoffs. Pursuit strategies prescribing the motion in the direction of the farthest of the runaways are studied. A numerical simulation of the development of the games Λ₂ and Λ₃ is conducted in using different strategies by the players.     

Network Formation for Asymmetric Players and Bilateral Contracting

We study a network formation game where players wish to send traffic to other players. Players can be seen as nodes of an undirected graph whose edges are defined by contracts between the corresponding players. Each player can contract bilaterally with others to form bidirectional links or break unilaterally contracts to eliminate the corresponding links. Our model is an extension of the traffic routing model considered in Arcaute, E., Johari, R., Mannor, S., (IEEE Trans. Automat. Contr. 54(8), 1765–1778 2009) in which we do not require the traffic to be uniform and all-to-all. Player i specifies the amount of traffic t_ij ≥ 0 that wants to send to player j. Our notion of stability is the network pairwise Nash stability, when no node wishes to deviate unilaterally and no pair of nodes can obtain benefit from deviating bilaterally. We show a characterization of the topologies that are pairwise Nash stable for a given traffic matrix. We prove that the best response problem is NP-hard and devise a myopic dynamics so that the deviation of the active node can be computed in polynomial time. We show the convergence of the dynamics to pairwise Nash configurations, when the contracting functions are anti-symmetric and affine, and that the expected convergence time is polynomial in the number of nodes when the node activation process is uniform.