University of Virginia, Department of Computer Science
CS200: Computer Science, Spring 2004

Problem Set 2:
Procedurally Predicting Presidential Primaries
Out: 21 January 2004
Due: Monday, 2 February 2003, beginning of class

Collaboration Policy - Read Carefully For this problem set, you are required to work with your assigned partner listed below. Partners were assigned (roughly) based on your answers to question 11 on the registration survey.

You and your partner should work together and turn in one assignment with both of your names on it. You should read the whole problem set yourself and think about the questions before beginning to work on them with your partner.

In addition to your partner, you may discuss this assignment with other students in the class and ask and provide help in useful ways. You may consult any outside resources you wish including books, papers, web sites and people except for materials from last year's CS200 course. If you use resources other than the class materials, indicate what you used along with your answer.

Darryl Tyger Blackstock
Dan Nguyen
Redcliff Chen
Steven Jo
Chelsea Coleman
TJ Ensele
Alexander Liu
Michael Owen Manning
Henry Cook
Stephen Sojka
Marija Cvijetic
Preston Joseph Gisch
Haben Ghermazien
William Ingram
Erin Paige Hallissy
Mee Kyung Hwang
R. Lincoln Hamilton
Lauren Walker
Seth Kendler
Erika Vogel
Susan R. Lindsay
Leah Nylen
Jonathan Carter
Kristina Hereford
Raquel Johnathan
Kathryn Morandi
Cristina Rabaglia
Evong Nham
Debora Wesner
Nicole Numbers
Benjamin Franklin Walter



Always vote for principle, though you may vote alone,
and you may cherish the sweetest reflection that your vote is never lost.

John Qunicy Adams

Although politicians in Adams' day may have always acted on principle, modern politicians tend to be more sophisticated, and modern voters more cynical. In this problem set we will look at the relatively new academic study of public choice economics. In economics, every individual or entity participating in a market (a place where products are bought and sold) looks to maximize its own utility (benefit derived from selling or purchasing a product). In a traditional market, consumers maximize their utility by maximizing the benefits gained from purchasing products, and producers maximize their utility by maximizing profits. In a political market, candidates for office serve as producers by formulating policy as their product, and voters serve as consumers by purchasing policy, which they do by voting for the candidate that formulated it.

Game theory attempts to explain how participants (or players) in a given market (or game) behave in order to maximize their own individual payoffs. Games are interesting because they analyze how players behave based on the actions of other players. While there are many types of games, we will start by looking at a very simple game based on the model of spatial competition:

Suppose there is a mile long boardwalk with patrons distributed equally and evenly across it. In addition suppose that all of these patrons are hungry and want to eat hot dogs. Two hot dog vendors, A and B, have decided to take advantage of this market by setting up mobile hot dog carts on the boardwalk. Their products are the same in every possible way, and the only way to differentiate between vendor A's product and vendor B's product is by looking at their position on the boardwalk. We assume that a patron will purchase a hot dog from the vendor that is nearest because the location of a vendor is the only way for a patron to decide to buy from one over the other. If vendor A and B are in competition with each other and they each want to maximize their individual revenue, where should A and B setup shop?
hotdog game

Since A wants to maximize the number of peope that will buy from her, and B wants to maximize the number of people that will buy from him, A and B each setup shop at the 1/4 and 3/4 marks, respectively, in order to split the market evenly. Interestingly enough, this initial setup is actually the most beneficial to the patrons as well. In a short matter of time, however, A will realize that she can get more customers by moving toward the 1/2 mark, since the patrons to the left of him must still go to him to buy a hot dog. In response to this, B will be forced to follow suit in order to keep up with A. Eventually, both A and B will find themselves in the center with the person at the 1/2 mark left to decide who gets the most business. This final setup is known as a Nash Equilibrium for this game, since no player can benefit anymore if the other player's position remains the same. (The Nash Equilibrium concept was discovered by John Nash, subject of A Beautiful Mind (winner of the 2002 best picture Academy Award), and winner of the 1994 Nobel Prize in Economics.)

In 1957, Anthony Downs popularized the single-dimension policy space, or political spectrum, in his book An Economic Theory of Democracy. This spectrum, illustrated below, puts liberal policies on the left and conservative policies on the right. Downs also proposed a view of American voting procedures known as the Median Voter Theorem, that is similar to the hot dog game. It states that the median voter will decide an election between two candidates given a symmetric distribution of rationally-behaving voters along a one-dimensional political spectrum. As a consequence, candidates should move toward the center of the spectrum in an attempt to get the median voter's vote and win the election.


Reading: Before going further, you should have finished reading all of SICP, Chapter 1 and GEB, Chapter 5.

Downloads: Download this file to your machine:

Create a folder called ps2 and unzip the contents into that folder. It contains four files:

  • — a template for your answers. This is the only file you should need to edit.
  • — procedures for drawing.
  • — partial code for the election game.
  • — useful procedures for manipulating lists (we will cover lists soon; for now, you are not expected to look at or understand the code in this file)
You should enter your answers in Remember to click Save frequently to save your work (note that Execute does not save your definitions).

Remember to make sure the Language is set to Full Scheme by selecting Language | Choose Language from the DrScheme menu. A dialog box will appear. Select Full Scheme in the Language choice menu and Pretty Big (MrEd and Advanced) in the right radio box.

Drawing Points

We will find it useful to be able to draw a "game board" that will serve as the political spectrum. To start, we will learn how to draw points, then we will move onto curves. This will give us all we need to draw the game board.

A curve is a (possibly infinite) set of points. We can draw a curve by mapping points on the curve to pixels on the screen.

For this assignment, we will use a coordinate system from (0, 0) to (1, 1):

(0.0, 1.0) (1.0, 1.0)
(0.0, 0.0) (1.0, 0.0)

Points have x and y coordinates. To represent points we would like to define procedures make-point, x-of-point and y-of-point such that:

> (x-of-point (make-point 0.2 0.4)) 

> (y-of-point (make-point 0.2 0.4)) 
Here's one way:
   (define (make-point x y)
      (lambda (selector) (if selector x y)))

   (define (x-of-point point) (point #t))
   (define (y-of-point point) (point #f))
The procedure make-point takes two parameters and returns a procedure. The returned procedure is a procedure of one parameter, selector. If the parameter is false (#f), it returns the y parameter; otherwise it returns the x parameter.

We have provided some procedures for drawing on the window in

Question 0: Define a procedure that uses make-point, window-draw-point and window-draw-line to draw a simple picture of a house. There is no need to make it as fancy as the White House. The point of this question is to get you acquainted with drawing objects on the screen. (You do not need to turn in anything for this question, but do not attempt the next question until you can do this.)


Building upon points, we can make curves and lines (straight lines are just a special kind of curve). We can think of curves as procedures from values to points. One way to represent a curve is as a procedure that evaluates to a point for every value between 0.0 and 1.0. For instance,
   (define (mid-line t)
      (make-point t 0.5))
defines a curve that is a horizontal line across the middle of the window. If we apply mid-line to a value x, we get the point (x, 0.5). Hence, if we apply mid-line to all values between 0.0 and 1.0, we get a horizontal line.

Predict what (x-of-point (mid-line 0.7)) and (y-of-point (mid-line 0.7)) evaluate to. Try them in your Interactions window.

Of course, there are infinitely many values between 0.0 and 1.0, so we can't apply it to all of them. Instead, we select enough values to show the curve well. To draw a curve, we need to apply the curve procedure to many values in the range from 0.0 to 1.0 and draw each point it evaluates to. Here's a procedure that does that:

  (define (draw-curve-worker curve t step)
    (if (<= t 1.0)
          (window-draw-point (curve t))
          (draw-curve-worker curve (+ t step) step))))

  (define (draw-curve-points curve n)
     (draw-curve-worker curve 0.0 (/ 1 n)))
The procedure draw-curve-points takes a procedure representing a curve, and n, the number of points to draw. It calls the draw-curve-worker procedure. The draw-curve-worker procedure takes three parameters: a curve, the current time step values, and the difference between time step values. Hence, to start drawing the curve, draw-curve-points evaluates draw-curve-worked with parameters curve (to pass the same curve that was passed to draw-curve-points), 0.0 (to start at the first t value), and (/ 1 n) (to divide the time values into n steps).

The draw-curve-worker procedure is defined recursively: if t is less than or equal to 1.0, we draw the current point using (window-draw-point (curve t)) and draw the rest of the points by evaluating (draw-curve-worker curve (+ t step) step)).

The draw-curve-worker code uses the special form begin. The evaluation rule for begin is:

Evaluation Rule 4 - begin. To evaluate (begin Expression1 Expression2 ... Expressionk), evaluate each sub-expression in order from left to right. The value of the begin expression is the value of Expressionk.
We stop once t is greater than 1.0, since we defined the curve over the interval [0.0, 1.0].

Question 1:
  1. Define a procedure, vertical-mid-line that can be passed to draw-curve-points so that (draw-curve-points vertical-mid-line 1000) produces a vertical line in the middle of the window.

  2. Define a procedure, vertical-line that takes one parameter and produces a procedure that produces a vertical line at that horizontal location. For example, (draw-curve-points (vertical-line 0.5) 1000) should produce a vertical line in the middle of the window and (draw-curve-points (vertical-line 0.2) 1000) should produce a vertical line near the left side of the window.

The Election Game

Our game will simulate an election for President of the United States. Each turn, all candidates will receive polling data and be able to adjust their positions on the political spectrum. Although our game is certainly not a perfect model of electoral politics, its better than Howard Dean's Dean for America game.

For our game, we will need to represent a race consisting of an electorate and a set of candidates.

Modelling Electorates

The electorate models the views of the voters. Similar to a curve, an electorate is a procedure that takes a parameter representing a point on the political spectrum and evaluates to the number of voters at that point in the political spectrum. For our purposes, we don't need to worry about the total number of voters, it is sufficient to have an electorate that gives the relative distribution of voters. To make graphing easier, we will keep the actual value between 0.0 and 1.0.

This defines flat-electorate as an electorate that is divided evenly through the political spectrum:

(define flat-electorate 
  (lambda (pos) 0.5))
We can turn an electorate into a curve by using the t parameter as the position and drawing the curve points as (t, (electorate t)):
(define (electorate-curve electorate)
   (lambda (t) (make-point t (electorate t))))
And then draw the electorate using, (draw-curve-points (electorate-curve <electorate>) 1000).

Question 2:
a. Define virginia-electorate as an electorate that looks like this:

b. Define charlottesville-electorate as an electorate that looks like this:

Your electorates do not need to match exactly, but they should look similar to the ones shown.

In order for a candidate to make decisions about where to position herself, it will be useful to know properties of the electorate like how many voters there are between two positions. To estimate the number of voters, we will step through the electorate in a way similar to the way we step through a curve:

(define electorate-steps 1000) ;; number of samples through the electorate

;;; electorate-voters evaluates to the number of voters in electorate between
;;; start-position and end-position
(define (electorate-voters electorate start-position end-position)
  (electorate-voters-worker electorate start-position end-position (/ 1 electorate-steps)))
The electorate-voters-worker procedure should evaluate to the sum of the values of evaluating the electorate procedure at each step between start-position and end-position.

Question 3: Define the electorate-voters-worker procedure used by electorate-voters.
If your definition is correct, you should get results similar to these:

> (electorate-voters flat-electorate 0.0 0.5)


> (electorate-voters flat-electorate 0.0 1.0)


;;; iowa-electorate is defined in

> (electorate-voters iowa-electorate 0.0 0.2)


> (electorate-voters iowa-electorate 0.2 0.4)


Races and Candidates

A race is defined by an electorate and a list of candidate. For example, we can create a race to model a fictional election below (any resemblance to real elections or candidates is purely coincidendal):
(define iowa-caucus
     (make-candidate "Kucinich" 0.05 static-candidate)
     (make-candidate "Gephardt" 0.1 move-away-from-others)
     (make-candidate "Dean" 0.2 move-away-from-others)
     (make-candidate "Edwards" 0.6 move-towards-voters)
     (make-candidate "Kerry" 0.8 move-away-from-others))))
Each candidate has a name, and current position (between 0.0 and 1.0), and a reposition procedure that adjusts the candidate's position based on polling data. The reposition procedure is a procedure that takes two parameters: a candidate and polling data. The reposition procedure should evaluate to a value that indicates how the candidate is moving (negative values move the candidate to the left, 0 stays at the current position, and positive values move to the right). Note that a candidate who attempts to move too far on a single day (that is, if a candidate procedure evaluates to a value that is not in the range [-0.1, 0.1]) will be perceived as a "flip-flopper", and will be eliminated from the race.

A simple candidate repositioning procedure represents a principled candidate (whose position is not swayed at all by polling data).

   (define (static-candidate candidate poll) 0.0)
Of course, principled candidates are unlikely to win, so we have defined two other candidate strategies in Each day before the election, a poll is conducted. Each candidate's reposition procedure is evaluated with the candidate's own current position and the latest polling data passed in as parameters to determine the candidate's position for the next day.

We have defined the (run-one-day race) procedure that models one day of a race. The actual code in is quite complicated to deal with displaying results and illegal candidate moves, but here is the basic idea:

(define (run-one-day race)
  (let ((poll-results (conduct-poll race)))
     (race-electorate race) ;; the electorate doesn't change
     (map (lambda (candidate)
	    (candidate-set-position candidate 
				    (+ (candidate-position candidate) 
				       ((candidate-reposition-procedure candidate)
	  (race-candidates race)))))
It takes a race as a parameter, and evaluates to a new race. It conducts a poll for the current candidate positions, and then evaluates the candidate reposition procedure for each candidate. Don't worry if you don't understand everything in run-one-day, although you should recognize the map procedure from Problem Set 1. In a few classes, you will understand how to define procedures like map that work on lists.

Since there may be any number of days before the election, we will need a procedure that can evaluate a procedure an arbitrary number of times.

Question 4: Define a procedure twice that composes a procedure with itself. You should be able to use twice like this:
      (define run-two-days (twice run-one-day))
to define a procedure run-two-days that simulates two days of a campaign.

Hint: Recall in Lecture 3 you saw the compose procedure that can be used to compose two functions that take one parameter:

   (define (compose f g)
      (lambda (x) (f (g x))))

Question 5: Define a procedure n-times that takes a procedure and number n, and composes the procedure with itself n times. Think about a recursive definition of n-times: to apply a procedure 1 time, just apply the procedure; to apply the procedure n times, compose the procedure with the result of applying the procedure n - 1 times. (See the hint below for help.)

Hint: Your procedure will look like this (the parts in < ... > brackets are what you need to fill in):

   (define (n-times f n)
      (if (= n 0)
          (lambda (x) x)  ; No procedure applications, return the identity procedure
          (compose <fill this in>
              (n-times f <fill this in>))))

We have defined a procedure run-election that uses the n-times procedure you have defined to run an election:

(define (run-election race number-of-days)
  (let ((final ((n-times run-one-day number-of-days) race)))
    (let ((final-votes (conduct-poll final)))
      (display-poll-results final final-votes)
      (display-winner final final-votes))))
The important part is the application of n-times (in bold). The rest of the procedure is used to record the final race, and then display the results.

When you evaluate (run-election iowa-caucus 20) you will be able to see the candidates move around on the display and the polling results in the interactions window. The blue line across the display shows the electorate, and the vertical line for each candidate shows their latest polling results. At the end of the execution, you should see:

Final Election Results
Candidate Kucinich at 0.05: 0.08132666666666673
Candidate Gephardt at 0.17000000000000007: 0.11200000000000003
Candidate Dean at 0.3000000000000001: 0.17974000000000004
Candidate Edwards at 0.49999999999999994: 0.19163333333333343
Candidate Kerry at 0.5999999999999999: 0.4352999999999997
The winner is: Kerry

(Please recall that any resemblence to real elections is purely coincidental.)

For the final question, your task is to define a candidate repositioning procedure that will help you win the CS200 primary:

(define cs200-primary
     (make-candidate "Alyssa P. Hacker" 0.4 static-candidate)
     (make-candidate "Ben Bitdiddle" 0.1 move-away-from-others)
     (make-candidate "Cy D. Fect" 0.9 move-away-from-others)
     ; add your candidate: (make-candidate "YOUR NAME" your-position-value your-repositioning-procedure)
Question 6: Define a winning candidate repositioning procedure that can win the election
   (run-election cs200-primary 20).


You can each a "Gold Star" on this assignment without going any further. More ambitious students will want to develop a candidate procedure that can compete with other student's candidate procedures to win an election. We will provide more details on the competition next week. Submit your candidate using the Candidate Submission Page.


The Downsian Model helps explain why third parties have a difficult time getting traction in US politics — a third party candidate draws votes away from the major party candidate whose views are most similar to the third party candidate's. Hence, the result of a strong third party candidate is to ensure that the major party candidate furthest from the third party candidate will win, therefore discouraging future support for third party candidates.

The Virginia Democratic Primary is February 10. Since Virginia is an open primary state, you may vote in the primary regardless of your political affiliation. Strategic voters who prioritize the general election result will vote positionally for the candidate that they think candidate they will have the best chance to win the general election (or to lose the general election if you want the Republicans to win the general election). Ironically, the Downsian model would suggest that liberals should vote for the most conservative candidate (who would have the best chance to defeat Bush in the general election), and conservatives should vote for the most liberal candidate (who would have the worst chance to defeat Bush in the general election). Of course, if you follow Adams' advice and vote on principle, you won't need to worry so much about modelling the general electorate.

If you are from Arizona, you might want to vote for Oksana Komarnyckyj, who's campaign is managed (and website developed) by a CS200 graduate and former assistant coach.

Credits: This problem set was developed for UVA CS200 Spring 2004 by Andrew Connors with help from Sarah Bergkuist, David Evans and Katie Winstanley.
Using these Materials