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 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.

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