home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14871 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  2.6 KB
  1. Path: sparky!uunet!destroyer!cs.ubc.ca!unixg.ubc.ca!unixg.ubc.ca!israel
  2. From: israel@unixg.ubc.ca (Robert B. Israel)
  3. Newsgroups: sci.math
  4. Subject: Electoral college (was Re: Bill Clinton and Complex Analysis)
  5. Date: 12 Nov 92 23:18:17 GMT
  6. Organization: The University of British Columbia
  7. Lines: 55
  8. Message-ID: <israel.721610297@unixg.ubc.ca>
  9. NNTP-Posting-Host: unixg.ubc.ca
  10.  
  11. The historical discussion here has been interesting, but my original
  12. post was of a more mathematical nature.  There are two related problems,
  13. which might be interesting for a course on discrete optimization:
  14.  
  15. (A) How many electoral votes could Perot have taken, given the number of
  16. votes he received?  Here I'm allowing votes to be moved around, subject to
  17. keeping fixed the total national votes for each candidate, and the total
  18. number of votes cast in each state. 
  19.  
  20. (B) How many votes must a candidate in a 3-way race receive in order to
  21. get a majority in the electoral college?  Again I'm assuming the total
  22. number of votes cast in each state is fixed.
  23.  
  24. Both of these can be formulated as "knapsack problems".  Written as an
  25. integer linear programming problem, (A) is
  26.  
  27. maximize
  28.    sum_{i=1..51} e_i x_i
  29. subject to
  30.    sum_{i=1..51} v_i x_i <= P
  31.    all x_i in {0,1}
  32.  
  33. Here i ranges over the 50 states plus District of Columbia, e_i is the number
  34. of electoral votes for state i, v_i is the number of votes needed to win state
  35. i (= [(V_i + 4)/3], where V_i is the total number of votes cast in state i,
  36. and [] is the greatest-integer function), and P is the total vote for Perot.
  37. We interpret x_i = 1 as meaning Perot wins state i, 0 that he doesn't.  In
  38. states with x_i = 1, Perot gets v_i votes and the rest are split as evenly
  39. as possible among the other two candidates.  The remaining votes are 
  40. allocated to the other states, arbitrarily except for totals.
  41.  
  42. Similarly, (B) is the problem
  43. minimize
  44.   sum_{i=1..51} v_i x_i
  45. subject to
  46.   sum_{i=1..51} e_i x_i >= 270
  47.   all x_i in {0,1}
  48.  
  49. I used data from the New York Times (not-quite-complete returns, but at least
  50. 99% in almost all states), and solved the problem using LINDO.  Note that
  51. P = 19,237,247, or 19.02% of the votes cast.
  52.  
  53. Results: 
  54. (A) Perot takes 338 electoral votes (62.8% of the total), winning all 
  55. states except Fla, Ill, La, Md, Mass, Mich, Minn, Mo, NJ, Ohio, Pa, Va and Wis.
  56. (B) 14,802,010 votes (14.64% of the total), winning all states except 
  57. Colo, Conn, Fla, Ill, Kans, Mass, Mich, Minn, Mo, NJ, NY, Ohio, Pa, Texas, Va, 
  58. and Wis.
  59.  
  60.  
  61. -- 
  62. Robert Israel                            israel@math.ubc.ca
  63. Department of Mathematics             or israel@unixg.ubc.ca
  64. University of British Columbia
  65. Vancouver, BC, Canada V6T 1Y4
  66.