First Report on a Project Studying the Analysis of

Cooperation in Games Through Modeling in Terms of Formally

Non-Cooperative Action in a Repeated Game Context

A few years ago I gave a talk on the topic of the use of the

"Prisoner's Dilemma" game, in a context of repetition and evolution of

strategies, by theoretical biologists who were interested in studying the

natural evolution of cooperative adaptations. And after giving the talk

I thought more about the concept of studying a game by studying it as a

repeated game and through this viewpoint I got an idea of how to eliminate

all of the "verbal" complications that could become involved in the

consideration of coalitions and coalition formation.

In principle, coalitions, and specifically coalitions as considered by

Von Neumann and Morgenstern in "Theory of Games and Economic Behavior", are

things that could be implemented by contracts, like contracts in roman law.

But of course a contract is quite intrinsically a "verbal" thing because

indeed it could (or should!) be written down in words.

On the other hand, if in Nature a form of cooperation has evolved, like

with a species of insects providing fertilization for a flowering species

of plants, then the cooperation exists and is maintained, not by the

enforcement of a verbal contract but presumably by the action of "natural

selection" affecting the genetics of both species as time passes.

My idea was that in a repeated game context that the players could be

given the right to vote for "agencies" or "agents" among themselves. Thus

at a first step a player, say player A, would have the option to accept

player B as his agent. And the effect of this would be that the coalition

(A,B) would be formed (like a committee with B as chairman) without any

verbal processes occurring between A and B. Furthermore, this process

adapts to successive steps of coalescence since if another step of

elections is held then B, as the "agent" representing the coalition (A,B),

can vote to accept the agency of player C and then C will thus become the

agent representing the coalition (A,B,C).

And in this manner, with generalized "agencies" being electable, the

level of a "grand coalition" can always be reached (for a game of finitely

many players), and as a consequence of that the requisites for "Pareto

efficiency" will be available.

With regard to the actual results which have been obtained and which we

can report on now, they have been calculations of equilibria for models

and specific games where there were two or three players. The models

relate to the representation of the coalescence (or coalition formation)

possibilities in terms of the concept of agencies and the models also

incorporate some form of "reactivity" by which players can react

affirmatively when well treated by others (acting as agents) and

negatively when badly treated by other players. (And of course there is

no bound, a priori, to the complexity of reaction patterns). But it is

somewhat plausible that with a "reasonable" level of refinement in the

modeling of reactive behavior that we can find results, in terms of

calculated equilibria of behavior, that will be plausible in relation to

appraising the bargaining/negotiation "values" for the game and also

compare calculated value vectors for it with other calculable value

vectors such as the Shapley value or the nucleolus. And the interest in

these comparisons is a good reason for studying games given as "CF games"

(which we will discuss further below) so that the Shapley value, the

classic nucleolus and the "Harsanyi nucleolus" can directly be calculated

for these games.

We have seen that there is much to do further, even on the level of

games of merely three players, to refine the modeling. We have worked

with parameters called "epsilons" which enable some smoothness and good

mathematical solutions for equilibria when they are finite and, as they

tend towards zero, limiting results that have Pareto efficiency that

becomes asymptotically perfect as "the epsilons" pass to zero limits.

(What is less clear at this stage of the research, for three players, is

that we can actually evaluate the "division of the profits" as the payoffs

to the players.)

In the continuing text below we will go into specific topics and also

into some details of calculations and of programming developed to achieve

the calculation results.

Agencies

As was mentioned above in the first paragraph, this research was

inspired by some study of the work of theoretical biologists working with

models employing the "Prisoner's Dilemma" game. When I arrived at the

idea of use of "agencies" as the means for the reduction of the potentially

quite "verbal" general concept of a coalition to a concept well suited

for studies based on analysis of the players' motivations from the

non-cooperative viewpoint of separate and independent utility measures

I realized also that there was a connection with the studies on the topic

of "the evolution of cooperation" (Axelrod et al).

Instead of there being unlimited means by which coalitions might

actually be formed or form, dissolve, and reform, we have an election

procedure through which any player may elect to accept any other player as

his agent. And in the context of studying a repeated game we can afford to

prescribe that this election process is such that the agent is entirely

uncommitted and his election is irrevocable for each specific playing of

the game. (Of course election choices are expected to vary as the game is

repeated.)

A set of rules can be devised so that there are election stages in

each of which all of the players remaining independent (not represented by

another player as agent) have, each of them, the option of electing another

player as an accepted agent. It is natural for these rules to require

convergence so that no more than (n-1) stages of election will ever be

needed for a game of n players.

Election rules need to do something to resolve the impasse of a

situation where A votes to accept B as his agent but B simultaneously

also votes similarly for A. It is not exactly clear which rule version

handles these situations in the most preferable fashion, we have worked

with more than one variant.

When we more recently found, in the course of the use of specific model

games for calculations, that it seemed to be desirable to allow elections

to be repeated when an election had failed to result the election of any

agency power, this finding had the effect of suggesting that election

rules which had the effect that at most one agency could be elected at

any stage of the election process would be most convenient.

Concerning the general concept of transforming a cooperative game into

a form where all cooperation must be realized by means of the election of

agencies, we can remark that this is analogous to thinking of committees as

being such that all effective actions of a committee must take the form of

an action by the "chairperson" of the committee.

If one begins with a quite general CF game and then if one introduces

a game formally requiring that all coalition benefits must be attained

through the means of the action of agents who have the authority to

represent all the members of the coalition then the "agencies game"

resulting from this still has the same validly derivable characteristic

function as the original game. In essence the coalitions simply have

the same potentialities as before, but in a formal sense, for these

potentialities to be exploited, the members of a coalition would need

TO CONSPIRE on a practical procedure for electing agents successively and

finally taking the effective action of the coalition as an action of the

agent finally elected to represent all of the members of that coalition.

Remark: The agencies concept inspired the origins of this research

project on which we are reporting. And earlier we considered various

alternative specific schemes of rules for the election of agents and

agencies. Some earlier texts which describe some of these alternative

ideas are available on the author's "web page". In particular the text of

the file "agentt7c.c" gives a good picture of these ideas with alternative

varieties of election rules being considered.

The Currently Applied Election Rules for Agencies

It was initially used just for the purpose of simplifying the

format of model games and simplifying the calculations needed to find the

corresponding equilibria (for the game of the realization of "coalescence"

(and coalition benefits) through the election of agencies). But in the

process we found that a simplifying format of election rules seems to be

adequate and convenient. If in a stage of elections more than one of the

players has voted to give his acceptance to another player to become his

agent (and as if with "power of attorney") then a random process, or

"chance move", determines only one of those votes as effective, and one

of the players has elected one of the other players to be agent for him.

In our latest modeling for 3-person games we introduced the concept of

repeating an election if no player had voted to give acceptance to anyone

as his agent, but this repeated election opportunity was to be given only

with probability of (1-e4) (one minus epsilonsub4). Then we found that we

got good results mathematically by considering the limiting results as e4

(epsilonsub4) tended to the limit of zero.

In general, if there are n players of a game, with this procedure, it

would take n-1 steps of effective election to achieve the final election

of an agency for the "grand coalition" (which is the coalition including

all of the players of the game). And in general, for the realization

of "Pareto Efficiency", it is needful that the grand coalition level

is attained.

CF Games

We want to introduce a concept or terminology applying to games that

are described by a "characteristic function" of the type developed

by Von Neumann and Morgenstern. There has been a tendency in the many

publications on game theory to describe a sample game simply by

specifying its characteristic function. We wish to call such a game,

for which an underlying "normal form game" or "extensive form game" has

not been specified, a "CF game". And an important consideration comes

in here: The characteristic function cannot be considered as fully

enough descriptive of a game so that an "evaluation concept" (or a

concept of determining a "value" for the game) that depends entirely on

the information given by that function would be well based. (This is a

phenomenon that appears initially in the context of 2-person cooperative

games as studied by Nash.)

And of course both the Shapley value and the nucleolus (imputation or

value vector) are defined in relation to a characteristic function that

is presumed given.

A "corrected" characteristic function, consistent with Nash's theory

for 2-person cases was introduced by Harsanyi around 1959 and it was

further studied by Selten in 1964. And either the Shapley Value or the

nucleolus can be alternatively calculated from this sort of a "modified"

or corrected characteristic function.

But there is also a paradox that appears with typical examples: IF a

game has been DEFINED (for purposes of study, perhaps as an example) by

specifying a characteristic function to describe it THEN the characteristic

function is correct! So we feel that this is a useful and convenient

category of example games and wish to have a language that allows for its

convenient use.

Thus we can seek to find, by various means, an "evaluation" of a "CF

game" described by the numbers of a characteristic function of the original

type of Von Neumann and Morgenstern). And we can obtain also, for a CF

game, the modified characteristic of Harsanyi's type. (This process of

going to the Harsanyi "modified characteristic function" can be described

as applying the "Harsanyi transform" to the original characteristic

function.)

Pro-Cooperative Games

There seems to be the possibility that theory for cooperative games,

of the sort that could prescribe evaluation numbers, like the Shapley

value or the nucleolus, may work better for games which tend to strongly

reward cooperation of the players than for those which could be regarded

as tending more towards favoring non-cooperative behavior of the players.

This remark is unfortunately both vague and rather "verbal".

A game of the sort that most simply favors cooperation is a game which

approximates to a maximally simple game of bargaining. If agreement of all

players in a three-person game is necessary for them to receive the main

payoff total and coalitions of merely two of the players could get only

comparatively quite small amounts then the game intrinsically favors the

cooperation needed for the realization of the benefits of the "grand

coalition".

(We have used games of this sort as a start for examples for explicit

calculations in our project of study.)

A contrasting type of game is the example game presented by Alvin Roth

in 1980. His illustrative game led to much discussion and arguments and

counter-arguments. But Harsanyi, whose own theory was considered by Roth

not to give an acceptable evaluation for the example, himself accepted the

critical implications of the example. The thing that can be noted about

Roth's illustrative game is that the grand coalition is totally ineffectual

(as it were) and that all of the possible payoff is realizable by a

coalition of only two of the players. (The context is a little complicated

by the presentation of the game in an NTU form and the need for the value

vector concepts to proceed via reductions to TU form.) (Here TU and NTU are

standard terms for transferable or non-transferable utility.)

So it seems plausible that Roth's example game can be classed,

comparatively, as a game not of "pro-cooperative" type. And what we are

thinking is that the analysis of the process itself of formation of

coalitions, via non-cooperative underlying motivations, can naturally

lead to different results for games which tend to favor or disfavor the

dependence of the players on the achievement of cooperation at the level of

the grand coalition. (We don't know, at this time, what should be a precise

definition of "pro-cooperative game" but we feel that it is likely that

an analysis of negotiation and bargaining, as processes on the roadway

towards the realization of cooperation, could lead to unique solutions

and plausible payoff outcomes for certain types of games while for other

types, perhaps like Roth's example, there could be non-uniqueness or

other deficiencies.)

Cooperation is not always intrinsically favored, in nature, or in human

affairs. Sporting events would become absurd if Sumo wrestlers were to

spend ALL of their time in polite ceremonies and respectful bows. And

Nature allows the evolution of parasitism and predation as well as the

evolution of symbiotic relationships.

A Consistent Value for Games of Three Players

In connection with this project I was thinking about how games might

be most practically described in the process of preparing to study them in

terms of modeling the processes of "bargaining" and/or "negotiation" and

"coalescence". And it became clear that the modeling would be much

simplified if a characteristic function description of the game could be

used. However I also knew that the procedure of definition of the VN&M

characteristic function (as defined in "Theory of Games and Economic

Behavior") could not be viewed as entirely "correct" because of its failure

to properly analyze the "threat" potentials of the various parties in the

game.

So the question arose of whether or not the "modified" characteristic

function defined by Harsanyi (1959, 1962) could be used instead and this

issue was stimulated by conversations with Shapley at Stony Brook 2001

from which I learned that it was viewed as quite appropriate to apply

the Shapley value calculation with any given characteristic function and

particularly that of Harsanyi.

It can be remarked that this use of the "HCF" (or Harsanyi characteristic

function) with the Shapley value formula or with Harsanyi's procedure in

1959 and 1962, for a general 2-person game of TU type (transferable

utility), yields the result of Nash in "Two-Person Cooperative Games" for

such a 2-person game.

And further study of the possibility of using the HCF to describe a game

led to a surprise for me when I realized that the nature of the reduction

of information in moving to that description has the effect, since the

characteristic function is of such a form that it describes effectively a

"constant-sum" game, that for three player games a natural value concept

is definable without making any use of an axiom of linear additivity of

games. In effect, the Shapley value for the HCF-described game emerges

as appropriate without the use of a linearity/additivity hypothesis.

And this is confirmed by the circumstance that for constant-sum games of

three players the nucleolus and the Shapley value coincide (as vectors

of three payoffs assigned to the players or as "imputations" in the

language of VN&M). So the nucleolus, which is not dependent on the linear

additivity axiom, confirms the value concept that is derivable for a game

of three players described by an HCF version of characteristic function.

So these considerations suggest also the idea of "the Harsanyi nucleolus"

which is definable as the result obtained by first finding the HCF

(or Harsanyi characteristic function) of a game (which might have been

originally given as a CF game) and then calculating the nucleolus as

usual except with the HCF used as the characteristic function for the

calculation.

This results, for games of three players, simply in the Shapley value (if

we start with a CF game), but for games of 4 or more it is something else

and a few examples suggested to me that for 4-player games it might tend to

assign more payoff to apparently favored players that the SV does. So the

"Harsanyi nucleolus" looks like an alternative value concept, for games of

4 or more players, that perhaps should be included in studies that compare

alternative ideas for values and arbitration schemes.

Other Workers

The areas of (1): analysis of cooperative games via means of

non-cooperative theory, (2): value theory, for games, in general, and (3):

the study of games by means of direct experimentation are relating areas

that are attracting interest in recent times. We can mention representative

names of persons doing research in these areas. Armando Gomes has studied a

model in which cooperation is achieved through steps that are taken by the

players on a non-cooperative basis. At one stage of his studies the result

for 3-person games was sometimes the nucleolus and sometimes the Shapley

value, and thus it was a quite suggestive result.

And Gianfranco Gambarelli has been studying alternative possibilities

in the area of "value formulae", where it is good to remember that any

accepted value concept can be the basis for an "arbitration scheme".

Gambarelli has been interested in the connections with voting power

issues similar to those which inspired the invention of the Banzhaf index.

And Reinhard Selten in recent times has been a leader in the direct

experimental study of games and how they are actually played if experiments

are done.

Here I can remark that, while my research project does not involve

experiments with human players at all, it is however as if experiments

are being carried out on the behavior of robotic players. And the nature

of the calculations is that one does not know, a priori, after designing

a model of robotically reactive players, what to expect from the results

of calculations based on the model. So the process can be analogous to

experimentation rather than to simply trying to design a (somehow "proper")

arbitration scheme without regard to the natural patterns of behavior of

players (possibly human, possibly corporate) in a naturally arising game

context.

References

The paper in final form will have references to various relevant papers

"in the literature". These are not included in this preliminary text. So

that will be the Bibliography for this paper.

Appendices

We include below, as texts in format, some files for programs that run

under MATHEMATICA to obtain solutions for model games. And also there are

the pages that describe calculation results for specific "cases" in terms

of the specific model most recently studied. Corresponding to these pages

there will also be transparencies that can be displayed at the Princeton

seminar.

And it can be remarked that the paper will need to explain in detail

about the structure of a model of reactive players whereas this issue can

be approached to some extent by talk or blackboard in a seminar.

#################################################################