ID: Applying Game Theory To The Domain Name Root System

Open Root Server Confederation (ORSC)                           S. Higgs
draft-higgs-dns-game-theory-00.txt             Higgs Communications, LLC
Category: Informational                                       March 2002


            Applying Game Theory To The Domain Name Root System


1. Status of this Memo

This document is an Internet-Draft and is subject to all provisions of
Section 10 of RFC2026 except that the right to produce derivative works is
not granted.

Internet-Drafts are working documents of the Internet Engineering Task Force
(IETF), its areas, and its working groups. Note that other groups may also
distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and
may be updated, replaced, or obsoleted by other documents at any time.  It
is inappropriate to use Internet-Drafts as reference material or to cite
them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html


2. Abstract

This paper applies Game Theory and the Nash Equilibrium to the Domain Name
Root System.


3. Concepts & Definitions

   3.1. Nash Equilibrium
        The Nash Equilibrium is a set of mixed strategies for finite,
        noncooperative games of two or more players in which no player can
        improve his payoff by unilaterally changing strategy.

   3.2. Zero-Sum Game
        A Zero-Sum Game is a game in which players make payments only to each
        other. One player's loss is the other player's gain, so the total
        amount of "money" available remains constant.

   3.3. Dominant Strategy
        Let an individual player in a game evaluate separately each of the
        strategy combinations he may face, and, for each combination, choose
        from his own strategies the one that gives the best payoff. If the
        same strategy is chosen for each of the different combinations of
        strategies the player might face, that strategy is called a "dominant
        strategy" for that player in that game.

   3.4. Dominant Strategy Equilibrium
        If, in a game, each player has a dominant strategy, and each player
        plays the dominant strategy, then that combination of (dominant)
        strategies and the corresponding payoffs are said to constitute the
        dominant strategy equilibrium for that game.

   3.5. The Commons
        The "commons" is any resource which is shared by a group of people.


4. Overview

In Game Theory, a game consists of a set of rules governing a competitive
situation in which from two to "n" individuals or groups of individuals
choose strategies designed to maximize their own winnings or to minimize
their opponent's winnings. The rules specify the possible actions for each
player, the amount of information received by each as play progresses, and
the amounts won or lost in various situations. Early game theory restricted
attention to zero-sum games, that is, to games in which no player can gain
except at another's expense.

This restriction was overcome by the work of John F. Nash during the early
1950s. Nash mathematically clarified the distinction between cooperative and
noncooperative games. In noncooperative games, unlike cooperative ones, no
outside authority assures that players stick to the same predetermined
rules, and binding agreements are not feasible. Further, he recognized that
in noncooperative games there exist sets of optimal strategies (so-called
Nash Equilibrium) used by the players in a game such that no player can
benefit by unilaterally changing his or her strategy if the strategies of
the other players remain unchanged. Because noncooperative games are common
in the real world, the discovery revolutionized game theory. Nash also
recognized that such an equilibrium solution would also be optimal in
cooperative games. He suggested approaching the study of cooperative games
via their reduction to noncooperative form and proposed a methodology,
called the Nash program, for doing so. Nash also introduced the concept of
bargaining, in which two or more players collude to produce a situation
where failure to collude would make each of them worse off.


5. The Tragedy of the Commons

The DNS Root is an example of an instance of "the tragedy of the commons."
The logic of the commons breaks down when resources decline and/or
population grows too large. The DNS Root is a common resource available to
all domain name holders. Within the DNS Root, .COM users make more intensive
use of the common resource that other TLD users, causing the resource to be
degraded (in this instance, a lack of available names). Yet the .COM users
gain a private advantage by choosing more intensive use of the common
resource, at least while the resource is relatively un-degraded. Another
example of the private advantage is the automatic appendage of the .COM
suffix by the popular web browsers in unresolved domain name searches. The
tragedy is that this intensive use leads to the degradation of the resource
to the point that all are worse off. This degradation is also identified by
the number of domain name disputes and by demands from multiple trademark
holders for exclusive use of the same domain name.

In general, "the tragedy of the commons" is that all common property
resources tend to be overexploited and thus degraded, unless their intensive
use is restrained by legal, traditional, or (perhaps) philanthropic
institutions. The classical instance is common pastures, on which, according
to the theory, each farmer will increase his herds until the pasture is
overgrazed and all are impoverished. Thus, we have cases of deliberate
destruction of the commons to not only get the wealth out of it before
someone else does, but also to leave nothing for others. Often, this has
involved the ruin of other commons resources along with the ones sought
after.


6. Game Theory On Competing Roots

In this scenario we have two actors, both of whom applied to the U.S.
Department of Commerce for the role of DNS Root administrator in 1997.  The
Internet Corporation for Assigned Names and Numbers (ICANN) and the Open
Root Server Confederation (ORSC) both started out with identical root zones,
which were based upon the root zone of the prior DNS Root administrator,
the Internet Assigned Numbers Authority (IANA).

                         ORSC

                     New     ORSC
                     TLD     Root
                  -----------------
          New TLD | 20,20 | 0,10  |
ICANN            |-------|-------|
       ICANN Root | 10,0  |  5,5  |
                  -----------------

Figure 1. Game Theory Applied To Root Systems

In Figure 1, incentives for an identical non-expansive root are valued at 5
points. When a new TLD, such as a ccTLD, is added to both root systems,
pressure is lifted from the DNS and this extension to the name space
benefits both root systems, and therefore each receive 20 points. When a TLD
is added to one root system and not another, pressure is reduced from one
root zone only, and this is valued at 10 points. The ideal situation
(20,20), where both organizations win, is for a unified root system in which
both root systems cooperate.


                         ORSC

                .FOO    .BAR    None
              -------------------------
         .FOO | 20,20 | 10,10 | 10,0  |
              |-------|-------|-------|
ICANN   .BAR | 10,10 | 20,20 | 10,0  |
              |-------|-------|-------|
         None |  0,10 |  0,10 |  0,0  |
              -------------------------

Figure 2. Situations With Identical Top Level Domains

In Figure 2, incentives for an identical non-expansive root are valued at 0
points (the degradation of the resource is valued at 0 points). When a new
TLD, such as a ccTLD, is added to both root systems, pressure is lifted from
the DNS and this extension to the name space benefits both root systems, and
therefore each receive 20 points. When a TLD is added to one root system and
not another, pressure is reduced from one root zone only, and this is valued
at 10 points. Again, the ideal situation (20,20), where both organizations
win, is for a unified root system in which both root systems cooperate.


                            ORSC

                 .FOO(1)   .BAR(1)    None
               -------------------------------
       .FOO(2) | -10,-10 |  10,10  |  10,0   |
               |---------|---------|---------|
ICANN .BAR(2) |  10,10  | -10,-10 |  10,0   |
               |---------|---------|---------|
         None  |   0,10  |   0,10  |   0,0   |
               -------------------------------

Figure 3. Situations With Colliding Top Level Domains

In Figure 3, incentives for an identical non-expansive root are valued at 0
points (the degradation of the resource is valued at 0 points). When a TLD
is added to one root system and not another, pressure is reduced from one
root zone only, and this is valued at 10 points. When identical, and
conflicting TLDs are active in both root zones, because of the confusion and
duplication of name space, the value is negative 10 points. In this case,
the ideal situation (10,10), where both organizations win, is for each root
to only introduce non-conflicting TLDs.


7. Conclusion

By applying the Nash Equilibrium to the practical application of the
hierarchy and distribution of the DNS, this paper concludes that the spirit
of RFC1591 is mathematically valid. RFC1591 states:

    "The designated manager must be equitable to all groups in the domain
     that request domain names" and "the principles described here apply
     recursively to all delegations of the Internet DNS name space."

This paper shows that the internet is enhanced by mutual co-ordinated
co-operation. Individually rational actions result in both parties being
made worse off in terms of their own self-interested purposes. Therefore
ICANN cannot be expected to win a zero-sum game.


8. References

Nash, J. F. (1950) , Equilibrium Points in N-Person Games, Proceedings of
the National Academy of Sciences of the United States of America 36, 48-49.

Nash, J. F. (1951), Non-Cooperative Games, Annals of Mathematics 54,
286-295.

Nash, J. F. (1950), The Bargaining Problem, Econometrica 18, 155-162.

Nash, J. F. (1953), Two Person Cooperative Games, Econometrica 21, 128-140.

McCain, R. A. Game Theory: An Introductory Sketch

Postel, J., RFC1591, Domain Name System Structure and Delegation


9. Author

Simon Higgs
Higgs Communications, LLC
P.O. Box XXXX
XXXXXXX
XX XXXXX-XXXX

###