Normative Utility Models for Pareto Scalar Equilibria in n-Person, Semi-Cooperative Games in Strategic Form ()
*Pareto Scalar Equilibria for n-Person Games.
1. Introduction
Game theory is the study of strategic interactions among n rational decision makers called agents (or players), whose decisions affect each other. Its systematic development began with von Neumann and Morgenstern [1] , who described both non-cooperative and cooperative games. These categories have become one approach for classifying games [2] . Either type involves a solution concept to recommend, predict, or explain player choices. Depending on the use of these solutions, game theory can be also divided into normative, predictive, and descriptive branches. The normative use of game theory is to recommend ideal decisions that the participants should make in a given game. The predictive application is to predict the choices of the participants. On the other hand, descriptive game theory, which involves empirical data, attempts to explain the actual behavior of these decision makers. Of course, both classification schemes are inexact. For example, in the latter taxonomy, the normative, predictive, and descriptive uses are interrelated. Descriptive game theory can lead to better mathematical model that give better recommendations and predictions. However, some decision theorists―including von Neumann [1] , Savage [3] , and Aumann [4] ―believe that the principal use of game theory is normative.
The purpose of this paper is to present normative models for games with both cooperative and noncooperative aspects. In each model, all players are assumed to have the same notion of rationality, which differs among the models. Solutions to each model are obtained by solving a scalar optimization problem to avoid the difficulties associated with the usual game theoretic equilibria. Moreover, these solutions involve only pure strategies. The models developed here could also be used by an arbitrator to prescribe an action profile for the game. In this section, we will first summarize the basic ideas of both non-cooperative and cooperative games. Next, we review the literature on games with both competitive and cooperative aspects, including that on arbitration for such decision problems. Then the restriction of our solutions to pure strategies will be discussed, and finally the notion of a scalar equilibrium will be defined.
Modern game theory as described in Myerson [5] and Maschler et al. [6] is predominantly non-cooperative. A non-cooperative game involves two or more utility-maximizing players. The key feature is that it focuses on the actions of the individual players. Non-cooperative game theory requires the solution concept to be a Nash equilibrium [7] [8] [9] . In other words, rational players are considered selfish. They act in their individual self-interest in the sense that each player’s strategy would maximize his expected payoff for the strategy profile of the other
players. Thus in a Nash equilibrium (NE) no player can improve his expected payoff by unilaterally changing his pure or mixed strategy. A NE always exists in mixed strategies but may not be Pareto optimal. Moreover, there may be multiple pure or mixed NEs in which various refinements such as properness have been proposed to eliminate implausible equilibria.
Social dilemmas [10] [11] [12] illustrate that the selfish behavior manifested in NEs may conflict with group or team interests. In Prisoner’s Dilemma, for example, each player can do better by cooperating. To accommodate these situations, Berge [13] proposed a pure-strategy solution that was formalized by Zhukovskiy [14] . A Berge equilibrium (BE) is a pure strategy profile in which every
players choose strategies that maximize the remaining player’s payoff. For a game with unselfish players invoking this Golden Rule rationale, a BE is thus an equilibrium since no unilateral change of strategy by any player can improve another player’s payoff. Such mutual support has been studied in Colman [15] , Corley and Kwain [16] , Corley [17] , and the references therein. The mixed BE is called a dual equilibrium to the NE in the latter two references because of the duality discussed there. Regardless, with this interpretation a pure or mixed BE can be considered as a mutually cooperative or altruistic solution concept for non-cooperative games when each player’s goal is to help the remaining players as opposed to himself. However, the BE is a solution concept for non-cooperative games since it is each player’s individual choice to be altruistic as above. Moreover, the players are rational in the following sense: a person is rational if the person makes decisions and acts in a manner consistent with his or her stated objective. In the BE model, it is assumed that each player’s objective is to be mutually supportive if possible.
In contrast, cooperative (or coalitional) game theory focuses on groups of the n players, rather than individual players themselves. Players form coalitions in cooperative games so that the members can receive more benefit than they could individually. Cooperative game theory focuses on predicting the coalitions that will form, the joint actions the coalitions will take, the resulting collective payoffs, and the binding agreements the coalitions will make [18] . Given this information, the cooperative model is concerned with identifying a fair allocation of benefits to the n players. Different solution concepts for cooperative games define fairness differently and thus assign different payoffs to the individual players. Common solution concepts include the stable set of von Neumann and Morgenstern [1] , the Shapley value [19] , and the core of Gillies [20] , as well as the kernel of Davis and Maschler [21] and the nucleolus of Schmeidler [22] .
The essential difference between non-cooperative and cooperative game theory is that non-cooperative games focus on what individuals can do acting alone while cooperative games focus on what groups can accomplish if they work together. Contracts must be self-enforcing in non-cooperative games, whereas players can make enforceable contracts in cooperative games. However, the contracts in cooperative games are not enforced internally, but externally by an outside party such as an arbitrator. In this paper a class of hybrid games in strategic form, with aspects of both non-cooperative and cooperative games, are called semi-cooperative. They may involve either negotiation by the players or external arbitration.
An early example of such a game was considered by Nash [23] , who presents a unique solution for a two-person bargaining problem in strategic form with complete information. This solution in mixed strategies involves a competitive component in which neither player will accept less than his status quo payoff, as well as a cooperative component modeled by the Nash product in which the players share in the benefits of cooperation. In [24] Nash extended this work to two-person demand games involving threats. Raiffa [25] defined an arbitration scheme as a mapping from a given generalized two-person game into a unique element of the set of mixed strategies for the game. Different imposed conditions gave different mappings that yield mixed strategies to be used as either a bargaining solution or as strategies imposed by an arbitrator on the players. Rosenthal [26] developed an arbitration model for two-person cooperative games in strategic form for an arbitrator to select a single Pareto-optimal pure strategy reflecting the relative strengths of the players. Kalai and Rosenthal [27] gave schemes for an arbitrator to use under his ignorance and survey the game- theoretical arbitration literature to that point.
More recently treatments of semi-cooperative games includes Baccharch et al. [28] , who consider a team reasoning approach to strategic games in which the players make decisions best for their team of players and not simply themselves. Hart and Mas-Colell [29] studied cooperation in n-person strategic-form games and developed a multistage bargaining procedure based on proposer commitment to obtain a ubgame-perfect equilibria that approaches Pareto efficiency. Diskin et al. [30] extended Raiffa’s arbitration model to an iterative procedure that converges to a Pareto optimum of the bargaining set for n players. Cao [31] modified the Hart-Colell procedure by delaying the realization of all threats to end of the game so that the Hart-Colell procedure would be consistent with the min-max solution in two-person zero-sum games. Finally, for two-person strategic-form games Kalai and Kalai [32] proposed a solution concept for cooperation called the cooperative-competitive (or coco) value. Their approach was developed either as a bargaining solution or for an arbitrator to obtain fair mixed strategies to a two-person in strategic form. This coco value combines the two players’ payoff matrices into a max-max cooperative component as well as a max-min competitive one. An extensive literature survey of semi-cooperative games is also provided.
We next justify seeking only pure strategies here by describing the difficulties with mixed strategies. Historically, according to both von Neumann [1] and later Nash [24] , a randomizing process is an essential ingredient in the concept of a mixed strategy. According to Nash [24] , “the use of mixed strategies involves deliberate decisions to randomize, to decide between alternative possibilities by using a randomizing process involving specified probabilities.” However, Aumann [4] considered the concept of mixed strategies to be “intuitively problematic” since people rarely make decision choices by lottery. Thus randomization lacks behavioral support. This difficulty is compounded, Aumann argued, by the fact that people are usually unable to generate random outcomes without some type of random or pseudo-random number generator.
Rubinstein [33] later described two interpretations of mixed strategies. The first was based on the purification theorem of Harsanyi [34] . The basic idea behind purification is that a mixed strategy merely reflects a player’s lack of knowledge of the other players’ information and decision-making process. In this view, random choices are seen as consequences of non-specified, payoff-irrelevant exogeneous factors, which to Rubenstein was unsatisfactory. Rubenstein’s second interpretation considers the game players standing for a large population of agents with n subpopulations, the members of which habitually choose specific actions, i.e., pure strategies. In other words, the fractions of the whole population choosing different strategies resembles a mixed strategy. But then, Rubenstein argued, no reason is provided for the individual agents’ choices. An alternate interpretation, perhaps the most intuitive, is that the probability of a player choosing a given action in a mixed strategy is the fraction of time that player would choose to it in a long series of repeated games. Unfortunately, games are often not repeated and certainly not enough for a frequentist interpretation of probability. Hence, Aumann and Brandenburger [35] interpret a mixed strategy for player i as an representation of the beliefs of i’s opponents about the action that player i will choose. However, opponents will likely have different beliefs, especially if they have different notions of rationality, so the predictive power of a mixed strategy is limited since a Nash equilibrium becomes an equilibrium in beliefs rather than actions.
Thus the interpretation of mixed strategies is controversial. The principal advantage of mixed strategies seems to be theoretical. They provide NEs when none exist in pure strategies and allow for the development of a rich mathematical theory as opposed to a combinatorial one. Nonetheless, practitioners are frequently ambivalent towards mixed strategies, which are currently difficult (if not impossible) to compute except for a relatively small games. Moreover, practitioners often view the mixed strategy solution concept as incomplete since it does not specify why and how players randomize their decisions.
In view of the above discussion, this paper develops pure-strategy solution concepts for n-person, strategic-form, semi-cooperative games with complete information and no threats. The solutions are normative since that they are suggestions for assigning action profiles to the players, under the assumptions of the models. Each is the pure-strategy solution to a scalar optimization problem. Such a solution is designated as a scalar equilibrium and provides a rational assignment in either a binding agreement among the players or a decision by an arbitrator. However, no negotiations are considered here. If the players cannot reach an agreement, a model of this paper could also be used by arbitrator to yield a fair and rational decision. The latter situation would be similar to two bargaining players having an arbitrator impose either the Nash [23] , Kalai- Smorodinsky [36] , or Kalai [37] bargaining solution. The work here restricts such bargaining problems to pure strategies. If an arbitrator is employed, however, the solutions proposed here are not game-theoretical concepts in a strict sense since the players do not choose their own actions.
For the semi-cooperative games described above, a scalar equilibrium (SE) is defined as an assignment of actions to the players using a decision criterion that maximizes an appropriate utility function of the players’ payoff profiles over the players’ acceptable joint actions. This choice of this utility function would be the result of a binding agreement among the players or an arbitrator’s decision. It is designated an equilibrium only in the sense that no player would change his action because the agreement or the arbitrator. In other words, for an n-person, strategic-form game, the agreed-upon utility function T associates a scalar value to each payoff profile in the payoff matrix. A payoff profile with a maximum utility is considered an optimal action profile. In the case of ties, an action profile would be chosen according to secondary criteria, which are not studied here. As an agreement among the players, an SE could be either externally or internally enforceable. In the case of a treaty, for example, an external enforcement mechanism could be an international court, while an internal enforcement mechanism could be a war or trade sanctions. In an arbitration, the arbitrator would obviously be the enforcement mechanism. An SE need not be a NE or a BE.
A semi-cooperative game as considered here has both competitive and cooperative aspects. It is competitive in the sense that each player wants a good payoff, possibly meaning either a fair one or a large one. It is reasonable to assume that no player would agree to an action profile giving him less than his pure-strategy security level. Nor―as argued by Aumann [38] , Rubinstein [33] , and Bacharach et al. [28] ―would reasonable players accept a payoff profile that was Pareto dominated. Otherwise, there would be an alternate profile for which some players’ payoffs would be improved without diminishing any player’s. On the other hand, the games of this paper are also cooperative in the sense that ideally an agreement among the players is required to select T. The goal here is to reduce such semi-cooperative games to the selection of a reasonable T either by the players or by an arbitrator if the players are unable to reach an agreement. Such a T would then determine the players’ actions, and thus the approach is normative.
In summary, the SE approach extends the classic bargaining results of (23), (36), and (37), for example, to n players and to different decision criteria. It also restricts previous results for semi-cooperative games to the more difficult and practical problem of obtaining pure strategies. In particular, the SE approach addresses four problematic areas of non-cooperative game theory.
1) An SE, which always exists, assigns a specific action to each player, as opposed to a mixed strategy that is difficult to calculate, interpret, and implement.
2) An SE can be obtained quickly as the maximum of a finite number of scalar values, as opposed to the computational effort required to determine mixed strategy NEs. A particular T might yield an approximation to a mixed NE or BE. In the latter case, even a mixed BE may not exist (17). However, approximation is satisfactory since implicit in the equilibrium refinement literature is the idea that a game is not a complete description of a strategic situation but rather an approximation itself.
3) SEs do not require that any particular notion of rationality for the individual players. An assignment is rational if it maximizes the utility function T selected by the players. For example, a “rational” action profile could be one that gives each player a “fair” payoff relative to all the players. Another could model the team concept of Bacharach et al. [28] . T would capture the players’ notions of rationality, which could conceivably differ, though this possibility is not considered in this paper.
4) For games with multiple NEs or BEs, one could also use T to refine these equilibria and choose one with the highest feasible value of T.
The paper is organized as follows. In Section 2 we present preliminary notation, definitions, and results. In Section 3 we develop the greedy SE (GSE), establish that a GSE is Pareto optimal for a semi-cooperative game in strategic form, and present two-person examples including the coordination games Prisoner’s Dilemma, and Chicken games to compare the GSE with other solution concepts. In addition, it is shown that a GSE is computationally tractable. In Section 4 we define a compromise SE and then a satisficing SE in Section 5. Both are again Pareto optimal and computationally tractable, and examples are presented. In Section 6 we state some standard bargaining axioms and note those satisfied by the SEs here. In Section 8 we offer conclusions.
2. Preliminaries
Consider first a standard n-person, non-cooperative game in strategic form for pure strategies. Let
denote such a game, where
is the set of players and
is the finite set of
actions for
player i. For an action profile
,
is the von
Neumann-Morgenstern (VMN) utility of player i, and the payoff matrix consists of the n-tuples
ordered in the usual way. It is well known that VMN utilities are both ordinal and cardinal but that these utilities are usually incomparable between players. In other words, for any strategies
and
,
is not well defined but
is. We assume here that
is a TU game with transferable utilities. This assumption means that the players have a common currency, or numeraire, valued equally by all players and that there is no wealth effect. Thus all players derive the same utility for the same currency level. In such a currency (i.e., dollars), it follows that the players have quasi-linear utility functions in
. Furthermore, we assume that utilities for player
,
, have been standardized by transformations of the form
for scalars
and
, which yield an equivialent game [5] , so that each player’s VNM utility for $C is C utils and that a difference of one util is as significant for any player as any other. We call this Assumption U on the utilities.
The Nash and Berge equilibria are next defined as in (17) for pure strategies to contrast with an SE defined below.
Definition 2.1. The action profile
an NE for
if and only if
Definition 2.2. The action profile
is a BE for
if and only if
Now let the n-person, pure-strategy, strategic-form, semi-cooperative game
corresponding to
be denoted by
, where
are as in
. Only the action profiles
in
are deemed acceptable to the n players, so the feasible set
for
should incorporate the pure-strategy security level. Finally,
is a utility function defined according to the particular situation modeled by a game
.
Definition 2.3. An action profile
is a security profile for
if and only if
For each player
,
is called a security action and
is called the security level.
The value
is the least payoff that player i can be guaranteed to receive from his action in the game, regardless of what the other players’ actions are. It is possible that
since
is not necessarily a worst response to
in a security profile. Regardless, it is reasonable to assume that no player would agree to an action profile in which he received less than
. Define
. It follows that
. Leyton-Brown and Shoham [39] , for example, show that any pure NE of the non-cooperative game
is a member of
.
An SE is an action profile
determined from a decision criterion involving an aggregate utility function
for all players in
that induces a preference relation
on
as described in [40] . In particular, for all
,
i)
if
,
ii)
if
,
iii)
if either
or
.
We next maximize the aggregate utility function
over
according to this preference relation and assign actions profiles to the players based on this decision criterion. Such an approach is consistent in the sense that
is complete and transitive. An SE is now formally defined.
Definition 2.4. Let
be the utility function for a semi-cooperative game
. The joint action profile
is an SE for
if and only if
for all
. Thus
is an SE if and only if
maximizes the aggregate utility function composition
over
.
If
has multiple SEs resulting from ties in the maximization, it is assumed that a negotiation among the players, similar to the one stipulating
and
, will choose a single
. If the game
is arbitrated, the arbitrator will select
, and a single SE. A further significant application of the SE approach is the use as a refinement mechanism for multiple equilibria of
. For example,
could be taken as the set of pure NEs for
, all of which are in
, with
specified either by the players, by an arbitrator, or possibly by the game’s model builder for normative purposes. Then the number of NEs could be reduced to those maximizing
over
.
For a certain class of
, an SE
for
will be Pareto optimal. To establish this fact, the following definitions and results are used.
Definition 2.5. For the game
, the action profile
dominates
if and only if
and
for some
. An action profile
is a Pareto maximum for
if
is not dominated by any
. A Pareto maximum
is said to be Pareto maximal.
Definition 2.6. For the game
, the utility function
is said to be strictly increasing on
if and only if
for any
for which
dominates
.
An immediate consequence of Definitions 2.5 and 2.6 is the next result.
Lemma 2.7. If
is an SE for
and
is strictly increasing on
, then
is Pareto maximal for
.
Proof. Let
be an SE for
. We prove the contrapositive. If
is not a Pareto maximum, there exists
that dominates
. But since
is strictly increasing, it follows from Definition 2.5 that
. Thus
is not an SE for
to establish the result.+
3. Greedy Scalar Equilibrium
It is now assumed that each player is greedy and wants a payoff as high as jointly possible. A greedy semi-cooperative equilibrium (GSE) for
is defined as follows. For
and
, consider the utility function
for which
(1)
Because of Assumption U, the multiplication in (1) defines a reasonable aggregate utility function
on
. The number 1 in the denominators of (1) prevents a division by 0 if any
.
Definition 3.1. The pure strategy profile
is a GSE for
if and only if
maximizes the aggregate utility function
over
.
From Definition 3.1, a GSE always exists even though a pure NE modeling player selfishness may not. Moreover, from (3.1), it follows that
for all
. Maximizing
over
requires that each
be as close to
as jointly possible. This maximization of (3.1) is a discrete version
of maximizing
over the region
. In this continuous version,
, over the feasible region, so the maximum is the point
. We now establish that a GSE is a Pareto maximum.
Result 3.2. If
is a GSE for
, then
is Pareto maximal for
.
Proof. By Lemma 2.7, it suffices to show that
is strictly increasing. Let
be pure strategies such that
dominates
. Thus
and
for some
. Since these fractions are all positive,
, and
is strictly increasing on
.+
A special case of Result 3.2 is the following corollary.
Corollary 3.3. If
is a GSE for
, then
is not dominated by any pure NE of the associated
.
On the other hand, the next example shows that a GSE for
can dominate a pure NE for
. This fact and Corollary 3.3 raise the possibility that a GSE for
models player selfishness better than a pure NE for
.
Example 3.4. Consider the two-person prescriptive game
with the
payoff matrix in Figure 1 below, where for simplicity we write
. In this case, the security levels
and
, so
. Immediately from Figure 1,
and
. We calculate
for each cell of Figure 1 to give the GSE corresponding to the underlined number in the scalar matrix of the
values shown in Figure 2.
From Figure 1 and Figure 2, the unique GSE for
is
with payoff profile
. The two pure NEs for
are
and
with payoff profiles
and
, respectively, while the two BEs are
and
with payoff vectors
and
, respectively. This example illustrates that a GSE for
is not necessarily an NE for
and vice versa. Morever, the GSE
dominates the NE
. There is also a BE that is a
Figure 1. Payoff matrix for Example 3.4.
Figure 1. Payoff matrix for Example 3.4.
Figure 2. Scalar matrix for Example 3.4.
Figure 2. Scalar matrix for Example 3.4.
GSE. Finally, we note that if the payoff for
were changed to
for
and if Figure 2 were recalculated, then the scalar value
,
is not a GSE, and no BE is a GSE and vice versa.
Example 3.5. Consider now the classic two-person Prisoner’s Dilemma (PD) game with the payoff matrix of Figure 3. The associated scalar matrix for
is shown in Figure 4. In this case,
and so
. Thus
, and the symbol ´ denotes that a strategy profile is not in
. From Figure 4,
is the unique GSE, which is not an NE. However, it is the unique BE. Thus in this example,
is both a greedy and mutually supportive action profile. Being mutually supportive in PD is better for each player than being selfish in the sense of an NE.
Example 3.6. For
, Figure 5 is the payoff matrix of a Hawk-Dove game
in which two countries vie for a contested resource. The Hawk pure strategy involves an escalated fight or even war for the resource, while the Dove pure strategy eschews such a fight. When
,
and
, so
. The pure NEs are
and
for
, and the BE is
, which is not feasible. The scalar matrix for
is shown in Figure 6. For
,
and
are GSEs as well as NEs. In this case, the greedy decision criterion has one player fighting and the other not. Such a situation could possibly lead to eventual retaliation by the Dove country and years of turmoil. When
, however, the GSE is
, while
and
are NEs. Hence, the GSE approach recognizes that a larger payoff
would result in a greedy Dove-Dove
Figure 3. Payoff matrix of Example 3.5.
Figure 4. Scalar matrix of Example 3.5.
Figure 5. Payoff matrix of Example 3.6.
Figure 6. Scalar matrix of Example 3.6.
strategy and avoid war, whereas the non-cooperative NE strategy does not.
Computational Procedure 3.7. A general procedure for obtaining the GSEs for
is outlined below.
will be maximized over
and not
. However, for any
such that
, the method will replace
by a very negative number to ensure that an
maximizing
over
also maximizes it over
.
Step 1. Enumerate the
(i.e., the cells of the payoff matrix) as
, and let
be a positive number much larger than any
in the matrix. Read a single player’s payoff at a time from each cell in order the order
. The length of the input is thus
numbers. As these numbers are read, if any
, set
so that
cannot max-
imize
. After all cells have been read and all replacements have been made, every n numbers from the beginning of the input list represents an n-tuple
for some
; and every action profile
. will have at least one
with value
.
Step 2. For
, compute
, which is the maximum of the individual inputs
one or more of which have value at least
.
Step 3. For each of the possible
cells, i.e., joint actions
, compute
.
Step 4. Find the action profiles
that maximize
in Step 3.
The worst-case time complexity of obtaining all GSEs for
is now shown to be linear in the size of the input data. Recall that in the standard Random Access Machine (RAM) model [41] , each addition, subtraction, multiplication, division, replacement, if statement, and call is considered to take one time step.
Result 3.8. The worst-case time complexity for obtaining all GSEs for
is
for
.
Proof. Without loss of generality it may be assumed that all have players have the same number of actions, so let
, in which case
is the size of the input. The maximum possible number of replacements in the Step 1 is
with time complexity
. Finding all the n maxima
in Step 2 has complexity
as established by Blum et al. [42] . With all
computed, finding each term of the product in Step 3 for a given
takes
time steps. But there are
joint actions
and thus
multiplications. Hence, determining the product in Step 3 for each
has complexity
. Next finding the GSEs by taking the maximum in Step 4 over all
has complexity
. It follows that all GSEs can be obtained in time complexity
, which is
to establish the result.+
It is worth noting that the problem of determining if pure NEs exists for a strategic-form game and then finding them is
as shown by Gottlob, et al. [43] . A similar result holds for BEs [44] . However, finding a mixed NE is a PPAD-complete problem [45] , a different type of complexity than NP-comple- teness but still a strong evidence for intractability [46] .
4. Compromise Scalar Equilibrium
Now assume now that each player wants a fair payoff or compromise as compared with the other players. Again, because of Assumption U, a reasonable notion of fairness is proposed as a compromise semi-cooperative equilibrium (CSE) for
, which is defined in a manner similar to Definition 3.1. For
,
, and
, consider the aggregate utility function
for which
(2)
From the definition of
and
it follows that
for all
. The number 1 in the numerators of (4.1) prevents
from being 0 if
for some
, while the number 1 in the denominators prevent a division by 0 if
. Maximizing
over
requires that each
be as close to
as jointly possible. Thus the players with
will receive payoffs in approximately the same percentile of their payoff ranges over the feasible action profiles. Players with
will receive
. For this decision criterion, the outcome can be construed as an equitable compromise between the players’ selfishness and unselfishness. A CE differs substantially from the fairness equilibrium of Rabin [47] for two players and from other notions of fairness in Korth [48] . However,
could be considered as a discrete analog to the Nash product for the two-person bargaining problem [23] . More precisely, maximizing
over
is a discrete version of maximizing
over the region
, in which case
for
, and the maximum is at
. The following definition extends one in Corley et al. [49] .
Definition 4.1. The pure strategy profile
is a CSE for
if and only if
maximizes the aggregate utility function
over
.
is easily shown to be strictly increasing on
, much as in the proof of Result 3.2, so the next result follows directly from Lemma 2.7.
Result 4.2. If
is a CSE for
, then
is Pareto maximal for
.
Obviously a CSE always exists for
. A computational procedure to obtain all CSEs is a simple modification of the Computational Procedure 3.7 in which any
is now replaced by
and
is used instead of
. This procedure again has worst-case time complexity
for
.
Example 4.3. Consider again two-person PD game
of Figure 3 above. The associated scalar matrix for
is shown in Figure 7. Thus
is the unique CSE, which is not an NE but is a BE.
Example 4.4. Consider again the Hawk-Dove of Figure 5 with associated compromise scalar matrix in Figure 8. Now
is the unique CSE for
, which gives a larger range on
for avoiding war by compromise than by greed as in Example 3.6.
5. Satisficing Scalar Equilibrium
Aspiration levels are widely used in decision theory [50] [51] and will be used here in a satisficing scalar equilibrium (SSE) unrelated to the satisficing games of Stirling [52] . The SSE achieves four objectives.
1) An SSE gives each player
at least some targeted payoff level
required for the player to accept a binding agreement gives each player
at least the targeted payoff level
that is required for the player to accept a binding agreement for an action profile
. It is assumed that
, with some
to distinguish the aspiration levels from the security levels, which are always obtainable.
2) The SSE model focuses the players or arbitrator on the parameters
and
. For example, if all
cannot be simultaneously satisfied, they can be modified by negotiation.
Figure 7. Scalar matrix of Example 4.3.
Figure 8. Scalar matrix of Example 4.4.
3) An SSE can give certain players higher relative payoffs than other players. Each each player
will be assigned a weighting factory
. If
, then player
will receive a higher payoff than player
if possible.
4) For any
, an SSE is Pareto optimal over the joint actions achieving the players’ aspiration levels.
Definition 5.1. For any
, where
, let
, where
. Then the action profile
is an SSE for the game
, if and only if
maximizes the aggregate utility function
over
.
Result 5.2. For all
, where
, any
solving
(3)
is an SSE and Pareto maximal for
.
Proof. Let
, and let
be such that
dominates
. Then it immediately follows that
, from which
. Thus
is strictly increasing on
, and the result follows from Lemma 2.7.+
One method of determining feasible aspiration levels
satisfied by at least one
in Definition 5.1 is to select the weights
, and then to
. The aspiration levels
are then feasible. Moreover, this method could be construed as fair if
. The approach suggests the following counterpart to Result 5.2.
Result 5.3. If
is Pareto maximal for
, then for any
,
is an SSE for the aspiration levels
.
Proof. Let
be Pareto maximal for
. Then
is obviously feasible for (3) with
. Now suppose there exist
, for which
does not solve (3). Then for some
satisfying
, it follows that
and hence
. But since
, then
and
for some
. Thus
is not Pareto optimal for
, in contradiction to the assumption. It follows that for any
,
solves (3) and is an SSE for aspiration levels
.■
Example 5.4. Consider now the payoff matrix of Example 3.4 in Figure 1. Note that
yields no feasible action profiles. When
, problem (3) has a solution, and the feasible
are
Figure 9. Scalar matrix for Example 3.4.
Figure 9. Scalar matrix for Example 3.4.
with payoff profile
,
with
, and
with
. Setting
in (3) gives the unique SSE
with payoff profile
. For
and
, however, the scalar matrix of
values for the feasible payoffs is shown in Figure 9, where cells with ´ have infeasible payoffs. The unique SSE is
with payoff profile
. Its scalar value is underlined.
For appropriate aspiration levels, an SSE always exists for
. Computational Procedure 3.7 can again be modified to determine if an SSE exists and then to obtain them all. To do so,
is replaced by
and
by
for a given set of
. Whenever
, the replacement
in the maximization of (3) assures that
will not be an SSE. This modified procedure also has worst-case time complexity
for
.
6. Axiomatic Considerations
A set of standard axioms for bargaining solutions will now be applied to the semi-cooperative models studied here. Nash [23] proposed four axioms stated below as Axioms 1 - 4 for the game
. Axiom 5 was formulated by Kalai [37] . We add Axiom 6, which seems reasonable.
Axiom 1 (Pareto Efficiency). If
is an SE for
, then
is Pareto optimal over
. In other words, no player’s payoff is better for another strategy
without at least one other player’s being worse.
Axiom 2 (Symmetry). If the players are indistinguishable, the solution will not discriminate between them. The names of the players do not matter. In other words, if
is an SE for
with a feasible set
and if the indices
are permuted in
, then the resulting strategy profile is an SE for the permuted game
where the indices are similarly permuted.
Axiom 3 (Invariance to Affine Transformations). If
is an SE for
, then
is an SE for the game
for any real numbers
and
. In other words, an affine transformation
of the utilities and aspiration levels will not change the SEs.
Axiom 4 (Independence of Irrelevant Alternatives). If
is an SE for
with feasible set
and if
, then
is an SE for
with feasible set
.
Axiom 5 (Resource Monotonicity). If
is an SE for
with feasible set
and if
is an SE for a
with feasible set
, then
. In other words, if additional feasible action profiles are considered, a new solution should be at least as good for all agents as the previous solution.
Axiom 6 (Individual Rationality). No player would agree to a payoff lower than his guaranteed security level, nor would a reasonable arbitrator impose such a payoff.
The Nash two-person bargaining solution [23] satisfies the above axioms except for Axiom 5 if the disagreement level is taken as a type of security level. The two-person bargaining solution of Kalai [37] satisfies all the axioms except Axiom 4 under the same assumption. However, the solution of Kalai and Smorodinsky [36] satisfies Axioms 1-3 but not Axioms 4 - 5, again under the same assumption.
The SEs of this paper satisfy Axioms 1, 2, 4, 6 but not Axioms 3, 5. However, an SSE is easily seen to be invariant for affine transformations of the form
, where the same
is applied to
, if the aspiration levels are also transformed. Moreover, a GSE and CSE would be invariant if not for the number 1’s added to prevent a numerator or denominator from having a value 0. It is likely that useful transformations T other than
and
can be formulated to satisfy Axioms 1 - 4. On the other hand, satisfying Axiom 5 presents a difficulty. The aggregation of all individual utilities into some
may not dictate that the monotonicity requirement of Axiom 5 on the individual utilities
will be satisfied.
7. Conclusion
The normative SE approach presented here extends classical bargaining models to semi-cooperative games with alternate decision criteria for the players or an arbitrator. In effect, this paper attempts to reduce the negotiations of semi- cooperative games to the new approach of selecting an appropriate utility function T, of which three were offered. It also restricts previous work to the pure strategies actually required for implementation. In doing so, an SE can be obtained quickly as the maximum of a finite number of scalar values, as opposed to the computational effort required to determine mixed equilibria. Future work should focus on formulating utility functions T that would model decision criteria besides the greedy, compromise, and satisficing ones presented in this paper. The next step would then be to form an aggregate utility function T by combining individual utility functions for players with different notions of rationality.