From: Wei Dai <weidai@eskimo.com>
Date: Wed, 26 Mar 1997 01:03:34 -0800 (PST)
To: Cypherpunks <cypherpunks@toad.com>
Subject: game theoretic analysis of junk mail
Message-ID: <Pine.SUN.3.96.970326004814.1233A-100000@eskimo.com>
MIME-Version: 1.0
Content-Type: text/plain


The junk mail problem (also known as spam) is well known to just about
everyone who receives e-mail.  There has also been many solutions
proposed.  Noticeably, the idea of having e-mail senders include ecash
payments with their mail has come up several times (I believe as the
result of independent discovery).  In order to evaluate the effectiveness
of this proposal, I will construct a game theoretic model of the
interaction between the sender and the recipient of an e-mail, and compare
the solutions with and without the ecash payment option.

The Model

Players: A - Sender, B - Recipient

      A: Send mail?
        /     \
    no /       \ yes
      /         \
    (0,0)    B: Read mail?
               /   \
           no /     \ yes
             /       \
         (0,0)   B: Accept offer?
                    /  \
                no /    \ yes
                  /      \
               (0,-c)  (s,r-c)

Assumptions: 
- sending the e-mail is costless to the sender
- c (the cost of reading a piece of e-mail) is known to both the sender
and the recipient.  
- s and r (the profit of the proposed deal to sender and receiver,
respectively, both assumed to be non-negative) are distributed according
to the probability density function f(s,r).  The sender knows s and r
before sending the e-mail, but the receiver does not learn s and r until
he reads the e-mail. 

Solution of the game:
To solve this game, we apply the method of backward induction.  In the
last stage of the game, B decides whether to accept A's offer.  Clearly he
always accepts since r-c >= -c.  Therefore, in the next to last stage, B
knows that the expected payoff if he reads the mail is the expected value
of r-c, E(r)-c, so he will read if E(r)-c > 0.  Finally, we come to A's
decision.  If A knows that B will not read, then he is indifferent between
sending and not sending.  However, if we assume that there is a small
probability that B will read and accept irrationally, then we can conclude
that A always sends the mail.

Conclusions

To summerize, if E(r) > c, B always reads the mail and accepts the offer,
otherwise B never reads.  A always sends regardless of the value of the
parameters.  Now we can see the outcome is not socially optimal.  For
example if E(r) < c, both A and B would be better off if A only sends when
r>c.

The above model is not very realistic.  The most unrealistic assumption is
that the sender knows the exactly value of his offer to the recipient.
However I believe the model captures the essence of the junk mail problem.
Next time I will analyze the proposed solution of adding the option of a
pre-payment.  For those who want to try it themselves, I give the game
tree here:

      A: Send mail?
        /     \
    no /       \ yes
      /         \
    (0,0)    A: Decide pre-payment p
                |
                |
                |
             B: Read mail?
               /   \
           no /     \ yes
             /       \
         (-p,p)   B: Accept offer?
                    /  \
                no /    \ yes
                  /      \
               (-p,p-c)  (s,r-c)