Guided Practice 2.2: The Prisoner's Dilemma

Two men are arrested, but the police do not possess enough information for a conviction. The police separate the two men and offer each the same deal- if one testifies against his partner (betrays), and the other stays quiet (doesn't betray), the betrayer goes free and the non-betrayer receives the full one-year sentence. If both remain silent, both are sentenced to only one month in jail for a minor charge. If each 'rats out' the other, each receives a three-month sentence. Each prisoner must choose to either betray or remain silent; the decision of each is kept quiet. What should they do?

The outcomes for player 1 are:

                           Player 2 move: 
                         Betray    Don't Betray
 Player 1 move:
 Betray              |    -3        0
 Don't Betray        |   -12       -1       

Observe that for both player 1 and player 2, the "right" thing to do is to betray, since that avoids the possibility of -12. But of course if nobody betrays, they both wind up with only a month in jail-- a better outcome!

This problem has been the subject of much discussion and research. Let's take a look at a small piece of the problem.


;; A Move is one of 
;; -- "betray"
;; -- "don't betray"

;; move-fn : Move -> ???
;; (define (move-fn m)
;;   (cond
;;     [(string=? m "betray") ...]
;;     [(string=? m "don't betray") ...]))

Here's the task:

;;; outcome : Move Move -> Number
;;; GIVEN: the moves of player 1 and player 2
;;; RETURNS: the outcome for player 1
;;; EXAMPLES: (outcome "betray" "don't betray") = 0.
;;; see table above.

Here's how NOT to do it:

(define (outcome move1 move2)
    [(string=? move1 "betray")
       [(string=? move2 "betray") -3]
       [(string=? move2 "don't betray") 0])]
    [(string=? move1 "don't betray")
       [(string=? move2 "betray") -12]
       [(string=? move2 "don't betray") -1])]))

  (check-equal? (outcome "betray" "betray") -3)
  (check-equal? (outcome "betray" "don't betray") 0)
  (check-equal? (outcome "don't betray" "betray") -12)
  (check-equal? (outcome "don't betray" "don't betray") -1))

This code does NOT follow the template for structural decomposition. It starts out doing structural decomposition on move1, but in structural decomposition, the right-hand side of each cond can only be function composition, and here the code has inserted a second structural decomposition (on move2).

Rewrite this code to follow the template by splitting each of the right-hand sides into a separate help function. Be sure to use good function names for your help functions.


Last modified: Sun Sep 14 12:11:23 Eastern Daylight Time 2014