CS200: Computer Science, Spring 2004

Problem Set 2:
Procedurally Predicting Presidential PrimariesOut: 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 dtb9c@virginia.edu
Dan Nguyen dvn4n@virginia.eduRedcliff Chen rc5p@virginia.edu
Steven Jo smj9d@virginia.eduChelsea Coleman cmc6d@virginia.edu
TJ Ensele tje6n@virginia.eduAlexander Liu acl5f@virginia.edu
Michael Owen Manning mom5v@virginia.eduHenry Cook hmc3z@virginia.edu
Stephen Sojka sps3b@virginia.eduMarija Cvijetic mc6sb@virginia.edu
Preston Joseph Gisch pjg2m@virginia.eduHaben Ghermazien htg2j@virginia.edu
William Ingram wai9z@virginia.eduErin Paige Hallissy eph7y@virginia.edu
Mee Kyung Hwang mkh7b@virginia.eduR. Lincoln Hamilton rlh3x@virginia.edu
Lauren Walker lew3p@virginia.eduSeth Kendler shk3m@virginia.edu
Erika Vogel ekv2j@virginia.eduSusan R. Lindsay srl5u@virginia.edu
Leah Nylen lan4d@virginia.eduJonathan Carter jlc8eg@virginia.edu
Kristina Hereford kah3j@virginia.edu
Raquel Johnathan rdj2f@virginia.eduKathryn Morandi krm7d@virginia.edu
Cristina Rabaglia cdr2m@virginia.eduEvong Nham en9j@virginia.edu
Debora Wesner dtw4e@virginia.eduNicole Numbers numbers@virginia.edu
Benjamin Franklin Walter bfw6a@virginia.eduPurpose
 Become comfortable with procedures as parameters and results.
 Learn to define recursive procedures.
 Provide pragmatic policy pronouncements for presidential primary pretenders.
Background
Always vote for principle, though you may vote alone,
and you may cherish the sweetest reflection that your vote is never lost.
John Qunicy AdamsAlthough 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?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 singledimension 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 rationallybehaving voters along a onedimensional 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: ps2.zip Create a folder called ps2 and unzip the contents into that folder. It contains four files:
You should enter your answers in ps2.ss. Remember to click Save frequently to save your work (note that Execute does not save your definitions).
 ps2.ss — a template for your answers. This is the only file you should need to edit.
 graphics.ss — procedures for drawing.
 election.ss — partial code for the election game.
 listprocs.ss — 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)
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 makepoint, xofpoint and yofpoint such that:
> (xofpoint (makepoint 0.2 0.4)) 0.2 > (yofpoint (makepoint 0.2 0.4)) 0.4Here's one way:(define (makepoint x y) (lambda (selector) (if selector x y))) (define (xofpoint point) (point #t)) (define (yofpoint point) (point #f))The procedure makepoint 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 curve.ss:
 (windowdrawpoint point) — Draw a black dot on the window at the point point. For example, (windowdrawpoint (makepoint 0.5 0.5)) will place a black dot in the center of the window. (The point is only one pixel, so it is hard to see.)
 (windowdrawline point0 point1) — Draw a black line from point0 to point1. For example, (windowdrawline (makepoint 0.0 0.0) (makepoint 1.0 1.0)) will draw a diagonal line from the bottom left corner to the top right corner.
Question 0: Define a procedure that uses makepoint, windowdrawpoint and windowdrawline 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.)
Curves
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 (midline t) (makepoint t 0.5))defines a curve that is a horizontal line across the middle of the window. If we apply midline to a value x, we get the point (x, 0.5). Hence, if we apply midline to all values between 0.0 and 1.0, we get a horizontal line.Predict what (xofpoint (midline 0.7)) and (yofpoint (midline 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 (drawcurveworker curve t step) (if (<= t 1.0) (begin (windowdrawpoint (curve t)) (drawcurveworker curve (+ t step) step)))) (define (drawcurvepoints curve n) (drawcurveworker curve 0.0 (/ 1 n)))The procedure drawcurvepoints takes a procedure representing a curve, and n, the number of points to draw. It calls the drawcurveworker procedure. The drawcurveworker procedure takes three parameters: a curve, the current time step values, and the difference between time step values. Hence, to start drawing the curve, drawcurvepoints evaluates drawcurveworked with parameters curve (to pass the same curve that was passed to drawcurvepoints), 0.0 (to start at the first t value), and (/ 1 n) (to divide the time values into n steps).The drawcurveworker procedure is defined recursively: if t is less than or equal to 1.0, we draw the current point using (windowdrawpoint (curve t)) and draw the rest of the points by evaluating (drawcurveworker curve (+ t step) step)).
The drawcurveworker code uses the special form begin. The evaluation rule for begin is:
Evaluation Rule 4  begin. To evaluate (begin Expression_{1} Expression_{2} ... Expression_{k}), evaluate each subexpression in order from left to right. The value of the begin expression is the value of Expression_{k}.We stop once t is greater than 1.0, since we defined the curve over the interval [0.0, 1.0].
Question 1:
 Define a procedure, verticalmidline that can be passed to drawcurvepoints so that (drawcurvepoints verticalmidline 1000) produces a vertical line in the middle of the window.
 Define a procedure, verticalline that takes one parameter and produces a procedure that produces a vertical line at that horizontal location. For example, (drawcurvepoints (verticalline 0.5) 1000) should produce a vertical line in the middle of the window and (drawcurvepoints (verticalline 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 flatelectorate as an electorate that is divided evenly through the political spectrum:
(define flatelectorate (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 (electoratecurve electorate) (lambda (t) (makepoint t (electorate t))))And then draw the electorate using, (drawcurvepoints (electoratecurve <electorate>) 1000).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 electoratesteps 1000) ;; number of samples through the electorate ;;; electoratevoters evaluates to the number of voters in electorate between ;;; startposition and endposition (define (electoratevoters electorate startposition endposition) (electoratevotersworker electorate startposition endposition (/ 1 electoratesteps)))The electoratevotersworker procedure should evaluate to the sum of the values of evaluating the electorate procedure at each step between startposition and endposition.
Question 3: Define the electoratevotersworker procedure used by electoratevoters. If your definition is correct, you should get results similar to these:
> (electoratevoters flatelectorate 0.0 0.5)
250.0
> (electoratevoters flatelectorate 0.0 1.0)
500.0
;;; iowaelectorate is defined in election.ss
> (electoratevoters iowaelectorate 0.0 0.2)
119.90000000000003
> (electoratevoters iowaelectorate 0.2 0.4)
159.90000000000012
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 iowacaucus (makerace iowaelectorate (list (makecandidate "Kucinich" 0.05 staticcandidate) (makecandidate "Gephardt" 0.1 moveawayfromothers) (makecandidate "Dean" 0.2 moveawayfromothers) (makecandidate "Edwards" 0.6 movetowardsvoters) (makecandidate "Kerry" 0.8 moveawayfromothers))))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 "flipflopper", 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 (staticcandidate candidate poll) 0.0)Of course, principled candidates are unlikely to win, so we have defined two other candidate strategies in election.ss: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.
 movetowardsvoters moves the candidate in the direction towards the most voters.
 moveawayfromothers moves the candidate away from the other candidates.
We have defined the (runoneday race) procedure that models one day of a race. The actual code in election.ss is quite complicated to deal with displaying results and illegal candidate moves, but here is the basic idea:
(define (runoneday race) (let ((pollresults (conductpoll race))) (makerace (raceelectorate race) ;; the electorate doesn't change (map (lambda (candidate) (candidatesetposition candidate (+ (candidateposition candidate) ((candidaterepositionprocedure candidate) candidate race pollresults)))) (racecandidates 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 runoneday, 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 runtwodays (twice runoneday))
to define a procedure runtwodays 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 ntimes that takes a procedure and number n, and composes the procedure with itself n times. Think about a recursive definition of ntimes: 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 (ntimes f n) (if (= n 0) (lambda (x) x) ; No procedure applications, return the identity procedure (compose <fill this in> (ntimes f <fill this in>))))We have defined a procedure runelection that uses the ntimes procedure you have defined to run an election:
(define (runelection race numberofdays) (let ((final ((ntimes runoneday numberofdays) race))) (let ((finalvotes (conductpoll final))) (displaypollresults final finalvotes) (displaywinner final finalvotes))))The important part is the application of ntimes (in bold). The rest of the procedure is used to record the final race, and then display the results.When you evaluate (runelection iowacaucus 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:
(Please recall that any resemblence to real elections is purely coincidental.)======================
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
For the final question, your task is to define a candidate repositioning procedure that will help you win the CS200 primary:
(define cs200primary (makerace flatelectorate (list (makecandidate "Alyssa P. Hacker" 0.4 staticcandidate) (makecandidate "Ben Bitdiddle" 0.1 moveawayfromothers) (makecandidate "Cy D. Fect" 0.9 moveawayfromothers) ; add your candidate: (makecandidate "YOUR NAME" yourpositionvalue yourrepositioningprocedure) )))
Question 6: Define a winning candidate repositioning procedure that can win the election
(runelection cs200primary 20).Competition
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.Discussion
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.
cs200staff@cs.virginia.edu Using these Materials 