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.



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