L.A. Math: Romance, Crime, and Mathematics in the City of Angels

by James D. Stein

  Arrow’s Impossibility Theorem

  Example 2, which shows that majority preference is not transitive, is a little unsettling. Nonetheless, it did not dissuade generations of social scientists from seeking a system that would translate the preferences of individuals into preferences for the society.

  Ideally, we would like to take a list of individual preferences and from this arrive at a list of the preferences of society. Example 2 shows that we cannot expect transitivity to hold for society’s preferences, even though it will certainly hold for the preferences of the individual. We would like to construct a “social preference method” derived from a list of individual preferences that enables society to choose between any two alternatives. Here is a list of some properties, each of which is desirable.

  Transitivity: We would like this “social preference method” to be transitive: If society prefers alternative A to alternative B, and it also prefers alternative B to alternative C, then it should also prefer alternative A to alternative C.

  Nondictatoriality: We would like a society that is nondictatorial. In other words, there should be no individual whose preferences are automatically adopted by society. In a dictatorship, the dictator’s preferences are automatically adopted by society; that’s what makes a dictator.

  Preservation of unanimous preferences: If every member of the society prefers alternative A to alternative B, then the society should prefer alternative A to alternative B.

  Independence of irrelevant alternatives: Suppose that the ballot contains at least three alternatives, A, B, and C, and that society prefers alternative A to alternative B. Now suppose that alternative C is eliminated from the ballot. Society should still prefer alternative A to alternative B.

  Like transitivity, this is generally obvious for individuals. Let’s suppose that you are going out for dinner and that steak, fish, chicken, and hamburger are on the menu. You select steak. The waiter comes back and tells you that they ran out of fish. Your reaction would undoubtedly be, “Who cares? Bring me my steak!” The absence of fish is an irrelevant alternative; it would only be relevant if you had actually decided to have fish for dinner.

  Each of these properties is not only desirable but also seems ostensibly reasonable. However, Arrow’s Impossibility Theorem shows that one cannot construct a social preference method with all of the above properties!

  Every time an election involves more than two candidates, there is the possibility that the choice of method may play a critical role in deciding the election, and that the “will of the people” may be inadvertently or unknowingly subverted. Arrow’s Theorem shows that there can be no perfect method.

  Here’s some food for thought: Suppose that the United States had only four states, three of which had twenty-six electoral votes and one of which had twenty-two electoral votes, a total of a hundred electoral votes. Too bad for you if you live in the state with twenty-two electoral votes because this state has absolutely no influence on the outcome of the election! If a candidate wins any two of the twenty-six electoral vote states, that’s fifty-two electoral votes—all they need.

  So is the Electoral College a good idea? As a well-known television network says, we report, you decide—and you may have to, because there are movements afoot to get rid of the Electoral College, which has led to some strange results in presidential elections.

  As Arrow’s Theorem shows, there’s no perfect way to run an election, but social scientists are continually on the lookout for ways that have as few flaws as possible.

  APPENDIX 14

  ALGORITHMS, EFFICIENCY, AND COMPLEXITY IN “THE QUARTERBACK CONTROVERSY”

  THE VALUE OF PLANNING

  Going places and doing things inefficiently wastes precious resources. Some of these resources, such as time and money, can be expressed in terms of numbers—and anything that can be expressed in numbers is fair game for analysis.

  You’re almost certainly familiar with some of the basic principles of operations research, the branch of mathematics concerned with efficient planning, from your everyday life—often, they’re just common sense. For instance, if you need to mail a package at the post office, pick up a book at the library, and leave the car to have the oil changed, and all of these locations are within walking distance of one another, you will find out when the library and post office are open so you can mail the package and pick up the book while the oil is being changed. Also, if you have several different locations to visit, you’ll try to visit them in an order that minimizes the time you spend getting from one place to another.

  In each day, you have only a few things to do and a few places to go. It is therefore fairly easy to plan to do these things with some efficiency because there are only a limited number of ways to do them. However, when there are many things to do and many places to go, the number of possible ways to do them can be astronomically large. For example, in any major construction project, there are a huge number of tasks to be done. A lot of time and money can be wasted if the electricians are sitting around waiting for the wiring conduits to be installed.

  In this chapter, we’ll look at some of the mathematics of going places (routes) and doing it as efficiently as possible.

  GOING PLACES (ROUTES)

  All cities, whether large or small, face two common problems involving routes: garbage collection, and the repair of broken traffic lights. A garbage truck starts out from a central location, picks up the garbage at all the buildings on a number of streets, and returns to its starting point. The route is most efficiently designed if the truck does not have to retrace any of the streets.

  A traffic light repair crew faces a different problem. Broken traffic lights undoubtedly occur at different areas of the city, and the route for repairing them is most efficiently designed if the total distance the repair crew has to travel is kept as small as possible.

  Figure 14.2. A Graph with Five Vertices and Six Edges

  Each of the routing problems can be presented in the simplified form of a graph, as indicated below (yes, the word “graph” has a different meaning when discussing functions, but mathematicians are not the only ones to assign multiple meanings to the same word—look up “spring” in the dictionary!). A graph consists of points, called vertices, connected by lines, called edges.

  The garbage collection problem is to design routes that retrace as few edges as possible. The traffic light repair problem is to minimize the total distance traveled in visiting all the vertices.

  When the Goal Is to Visit All the Vertices

  As you saw in “The Quarterback Controversy,” the problem of visiting all the vertices in a graph while minimizing the total distance traveled is known as the Traveling Salesman Problem, abbreviated TSP.

  If you assume that a salesman (or woman) has to visit n different cities before returning home, he (or she) has a choice of n different cities to visit first. From there, he (or she) could go to any one of the (n − 1) unvisited cities, and from that city to any one of the (n − 2) unvisited cities, etc. By the Chinese Restaurant Principle, there are a total of n × (n − 1) × (n − 2) × … × 1 = n! different routes that he (or she) could take.

  You may recall from the chapter on counting that, even for fairly small values of n, such as 25, n! is an astronomically large number. Even the fastest supercomputer would take billions of years to examine the total distances of each of 25! different routes. As a result, mathematicians have examined two different questions.

  Question 1: Is there an algorithm that enables one to examine only a select handful (this can be defined in mathematical terms, but don’t worry about it) of routes and still come up with the shortest route?

  Question 2: Is there an algorithm that enables one to examine only a select handful of routes and come close to the shortest route?

  (Traveling Salesman Problem continued from p. 125)

  As Pete points out in the story, as far as question 1 is concerned, no one even knows whether such an algorithm exists, although the be
tting in the mathematical community is that it doesn’t. The Traveling Salesman Problem is an example of what mathematicians call an NP-complete problem. There are many extremely important such problems, and they generally involve a factorial number of possibilities.

  Consider, for instance, a scheduling problem that might take place in a typical factory, such as the problem of assembling a car, a TV, or a circuit board. Many different subtasks have to be performed, and although some must clearly follow others, it is often possible to perform many of the subtasks in any order. Here it is necessary to minimize the total time, or possibly the total cost, of performing the entire job, but it is just the TSP in another guise.

  Any problem that involves factorials is troublesome because a problem with “factorially many” computations to make requires far too many computations even for fairly small numbers. A traveling salesman visiting 25 cities is way beyond the power of even the fastest supercomputer to handle, and variations of the TSP often have the equivalent of thousands of cities.

  In 1971, Stephen Cook, a mathematician at the University of Toronto, showed that, if one NP-complete problem could be solved, they could all be solved. A result such as this does not tell how to solve a problem, but it yields a certain amount of insight. Additionally, it shows that (1) if someone can solve just one of these problems, they can all be solved, and (2) if someone can show that just one of these problems cannot be solved, there is no need to “waste time” trying to solve any of the others. To date, no one has solved any NP-complete problem, but no one has shown that they cannot be solved, either.

  More progress has been made in answering question 2. It is fairly easy to describe an algorithm, such as the “nearest neighbor” algorithm that appears in the story, and to execute it. What is substantially more difficult is to figure out how good that algorithm is. Obviously, any TSP has a “best” answer—the number of miles of the shortest route. If one could find an algorithm that guaranteed an answer within, say, 10% of the best answer, this would obviously represent substantial progress. Several algorithms have been devised that give excellent results with problems that occur in the real world, but no algorithm is yet known that guarantees “coming close” in all cases.

  Because of the immense practical value of the TSP and its related NP-complete problems, this is one of the most intensively investigated of all mathematical problems.

  Calculating Task Complexity

  A task that is doable in N2 steps, or N8 steps, or Np steps for any fixed integer p is said to be a polynomially complex task. Polynomially complex tasks have the following property: The price tag for increasing the number N by “just 1 more” gets smaller and smaller as N gets larger and larger.

  Consider a task that is doable in N3 steps. If N = 10, then the task requires 1,000 steps. If N = 11, the task requires 1,331 steps, an increase of about 13.3%. However, if N = 100, the task requires 1,000,000 steps, but if N = 101, the task requires 1,030,301 steps, an increase of only about 3%. This “price tag” gets smaller as N gets larger.

  The next stage of task magnitude is the exponentially complex task, which might require 2N steps to complete. For such a task, the price tag of “just one more” is always the same—the task time doubles. Obviously, any algorithm that can reduce an exponentially complex task to a polynomially complex task represents a tremendous potential savings in time, especially when N is large.

  The ultimate horror show in task complexity is the factorially complex task, such as the TSP. As you have seen, a traveling salesman who must visit N cities has a choice of N! possible routes. The cost of “just one more” for a factorially complex task gets worse and worse as N gets larger and larger. In fact, since (N + 1)!/N! = N + 1, you can see that the cost of going from N to N + 1 increases by an ever-increasing factor of N + 1.

  The “nearest neighbor” algorithm discussed in “The Quarterback Controversy” reduces a factorially complex problem to a polynomially complex one. Applying the “nearest neighbor” algorithm to an N-city TSP requires one simply to look at N numbers for the first intercity trip, then N − 1 numbers for the second intercity trip, N − 2 numbers for the third intercity trip, and so on. This method would give a total of N + (N − 1) + … + 1 computational steps, and we know (from the chapter on patterns) that this total is N × (N + 1)/2, which is less than N2.

  The “nearest neighbor” algorithm is often called a greedy algorithm because it decides at each stage what is best according to a certain rule and then hopes that this step-by-step plan gives the best overall result. This is somewhat akin to an individual who eats the first item of food he (or she) sees whenever he (or she) is hungry and hopes that by so doing his (or her) nutritional needs will be best satisfied. Good luck with that method.

  AN INTRODUCTION TO SPORTS BETTING

  Betting on sports almost certainly started thousands of years ago, when one horse owner said to another, “My horse is faster than yours,” and the second responded, “Oh, yeah? Wanna bet?” Since then, betting on sports has become an avocation of millions of people and is a billion-dollar industry that shares many of the ideas and techniques of two trillion-dollar industries: financial markets and insurance. Different societies have different views on sports betting; it is a respectable national institution in England, but less so in the United States, where the laws governing sports betting vary from state to state. Offshore betting websites proliferate; some abide by federal restrictions, and others don’t. The rule “Buyer beware!” is good advice to anyone interested in patronizing such a website.

  PARI-MUTUEL BETTING

  Legalized horse racing is common throughout the world, and the usual method of wagering is pari-mutuel betting. Bettors place bets on which horse will win; all these bets are placed in a pool. The organization supervising the wagering collects a fraction of the pool and pays the remaining money back to the winners.

  Here’s an easy example. Suppose that there are three horses in a race, and the proprietors supervising the wagering take 20% of the total amount bet (this is a fairly typical percentage in state-run horse racing). The money has been wagered as follows

  Horse

  Amount Bet to Win on That Horse

  Alexander the Great

  $500

  Mike the Mediocre

  $400

  Howard the Horrible

  $100

  The total wagered is $1,000. So 20% of that, or $200, is deducted by the proprietors, leaving $800 to be distributed among the winners. If Alexander the Great wins, each dollar bet on Alexander the Great returns $800/500 = $1.60. In this case, a bettor who bet $1 on Alexander will have paid $1 for a ticket; he or she will then receive $1.60, a profit of $0.60 on his or her bet. If Mike the Mediocre wins, each dollar bet on Mike the Mediocre returns $800/$400 = $2.00; a profit of $1.00. If Howard the Horrible wins, each dollar bet on Howard returns $800/$100 = $8.00; a profit of $7.00.

  LINE BETTING

  Many sports events are a contest between two teams or individuals. As an example, let’s suppose that the Dallas Cowboys are playing the New York Giants at New York. New York is felt by the Las Vegas bookmakers to be a slightly stronger team than Dallas, and the fact that the game is being played at New York gives the Giants a home-field advantage, which is normally felt to be worth three points. That, combined with the fact that the Giants are felt to be a slightly stronger team, leads the Las Vegas bookmakers to estimate that, on average, the Giants should win by five points. The Las Vegas bookmakers therefore set the line at New York minus five. A bettor who bets on the Giants is said to give five points, and the Giants are known as the favorite. A bettor who bets on the Cowboys is said to get five points, and the Cowboys are known as the underdog, commonly referred to as the dog.

  When the game ends, if New York wins by MORE than five points, those people who have bet on New York win the bet, those who have bet on Dallas lose the bet. In this case, the favorite is said to have covered. If New York either loses or wins by LESS than five points, those
people who have bet on Dallas win the bet, and those who have bet on New York lose the bet. If New York wins by EXACTLY five points, the game is said to be a push, and no money changes hands.

  If you bet with a bookmaker, you generally must pay odds of 11 to 10 on a losing bet. For instance, if the line is New York minus five (or Dallas plus five, which is the same thing), and you bet $100, if you win you are paid $100. However, if you lose, you must pay $110. The extra $10 paid on losing bets is known as the vig, which is short for vigorish. The term originated in the twentieth century from the Russian vyigrish (brought over from Russia and incorporated into Yiddish), meaning “gains” or “winnings.”

  NOTES

  CHAPTER 8. NOTHING TO CROW ABOUT

  1. Handicapping is the process of predicting the success of the various entrants in a contest. Political pundits often handicap various elections.

  2. A longshot in an athletic contest is a contestant with little chance to win. In everyday English, it refers to an improbable event.

  3. In poker, a hole card is a card dealt to a player that only that player can see. Cards that can be seen by all players are called up cards; they are dealt face up. The expression ace in the hole means a fact known only to its possessor that can be extremely advantageous. During World War II, the fact that the British had developed radar in secret was an ace in the hole.

  4. In horse racing, the daily double is a bet on which horses will win the first two races. A daily double bet selects one horse in the first race and one horse in the second race, and the bet wins only if both horses win.

  5. In horse racing, to wheel a particular selection means to place bets on that selection and all the other horses in the race. For example, if a bettor is sure that Alexander the Great will win the first race, he or she might buy a number of daily double tickets by wheeling Alexander the Great with every horse in the second race. If Alexander the Great actually wins and a longshot wins the second race, this method can be extremely profitable.