Science Talk January 17, 2007 -- Improved Methodologies for Cake Cutting; and Relative Competitiveness of Professional Team Sports and Devising More Efficient Schedules

Welcome to the Science Talk, the weekly podcast of Scientific American for the seven days starting January 17th. I am Steve Mirsky. This week on the podcast, the Los Alamos National Laboratory's Eli Ben-Naim discusses competitiveness in sports leagues and the optimal ways to make sure the best teams really win; and Montclair State University's Michael Jones talks about better ways to cut a cake. Shh….. Don't tell anybody for all of this material is really math. It’s disguised as fun stuff like cake cutting and baseball schedules. Plus we will test your knowledge about some recent science in the news. First up, mathematician Michael Jones on cake cutting. I called him at his office at Montclair State University in New Jersey.

Steve: Professor Jones—thanks for talking to us today.

Jones: Good talking to you.

Steve: And you have got this paper, "Better Ways to Cut a Cake", which does not sound like your typical math paper.

Jones: It isn't a typical math paper. It's written with a couple of colleagues—an economist, and a protocol scientist—and then I am the mathematician. So we use cake as really a metaphor for dividing a heterogeneous, divisible good and items that people may have different preferences over the items.

Steve: Well, let's talk about the traditional kind of cake cutting situation where there are two people and you have the cake, and what that methodology is and what it represents in the real world.

Jones: Well, I guess in the simplest case, it could represent two kids who are dividing an actual cake or a candy bar or something like that; but it's also a cake [that] in that type of scenario could represent land that's being divided between two countries after some sort of dispute. Cake itself represents being a heterogeneous divisible good—it's just something that more than one person could have the rights to.

Steve: The simpler situation, one person makes the cut and the other person gets to choose.

Jones: Sure, I cut you choose; goes back, boy, even to the time of the Bible. But the problem with "I cut you choose"—although being very simple—is that the person who does the cutting is limited to just 50 percent of the cake if that person, you know, cuts it in such a way that he or she is indifferent between the two pieces—and that's the way that that person can guarantee getting 50 percent of the cake. Then you look at that as disadvantage if you are the person doing the cutting. You would rather be the chooser. This idea of eliminating being at that disadvantage is at the heart of our paper "Better Ways to Cut a Cake". We were looking for a way so that both players could get more than 50 percent. There are a number of properties that are desirable in cake cutting and one of them is that it's sufficient—meaning that there is no other allocation that is better for one of the players than[that isn't] at least as good for the other person. The key one[concept] in cake cutting is called "envy freeness". In any type of division or any type of exchange, you don't want to end up feeling like you were taken advantage of; and that you desire what the other person received and you have a certain amount of envy for their piece of cake. So, there is a third property, and the third property is arguably the lesser of the three; but it is the one that sort of motivated us because we know that we can get efficiency in envy freeness. "I cut, you choose" has those two properties, but the third property is what's called "equitability" and equitability is almost like a second-order envy—not only do I not want your piece, but I want both of us to have the same satisfaction for the pieces that we get.

Steve: And this is key because before you said it—maybe less than as you are thinking, this guy is a mathematician?—you just say[id] we can have more than a 100 percent, but this is the key to how you can have more than a 100 percent, right?

Jones: That's right. That's exactly the case. It's because the players are the people who are dividing the object—the cake, as it is. They value the pieces differently. So, for example, if a cake consists of half chocolate and half vanilla, and one person likes chocolate a lot and can tolerate vanilla, and the other person is indifferent between the two, will[we'll] then await[want] to have both people receiving in their opinion more than half of the cake—that is to give the person who values chocolate more, given[ing] them more chocolate; and if they get a lot of the chocolate, they are going to happier. And you offset that by giving more of the total cake—which would include all the vanilla—to the other person; and in that case, then both of the people to get more than what they perceive to be half of the cake.

Steve: And a lot of your paper consists of the equations that talk about how to optimize that particular cake-cutting scenario.

Jones: Right, well the important thing—and I [al]so had mentioned this concept of equitability—is there is actually a way to cut the cake so that both people can receive what they believe is the same amount of cake. So, it satisfies this equitability; but here is the riddle—the riddle is that there is no procedure possible that can induce people to truthfully reveal their preferences of the cake so that we can cut the cake there. So, although this point—this sort of mythical perfect cut—exists for the two people, the problem is that there is no way for me to have the people communicate truthfully their preferences of the cake to [so I can] cut the cake there. There is always a way for them to uniformly lie and do better. And as someone who wants to design a procedure or implement a procedure, I want my procedure to induce the players to be honest about their preferences. And so this sort of perfect cut or mythical outcome in some sense doesn't pass that test. And what we show in the paper is, we come up with a different type of procedure that is strategy-proof and induces players to be truthful about revealing their preferences. It doesn't return equitability, but it does something: It returns a different type of equitability, what we call proportional equitability. And in proportional equitability, the two players sort of are quibbling over a surplus. We guarantee that both of them would get 50 percent of the cake and then what remains is a surplus and proportional equitability cuts the cake at a point that the players receive pieces in proportion to the value that they have for the surplus. The procedure makes it so that there is no way for one of the players to lie and guarantee that they can do better; and that ends up being important really in some sense of fair division in the areas of mathematics. Or if you think of fair division [a]s an area of mathematics, designing a procedure is what we would call creating a mechanism. And so it becomes a mechanism-design problem, and that's really a subset of game theory. We are trying to design a procedure so that players will tell the truth and let the procedure do what it's supposed to do. And the last thing you want if you are dividing , say, a piece of land from an inheritant, it’s a[is to] feel like you are [being] tak[en]ing advantage of by the other person that you are dividing with.

Steve: Right. And that gets to the real world applications of this, where you actually do have a limited resource that you are dividing up among maybe more than two people.

Jones: Yep, that's right.

Steve: Your work is kind of distantly related—is this right?—to, you know, the work that a lot of people are maybe familiar with from the movie A Beautiful Mind or prisoner's dilemma, the spanish prisoner—that kind of thing.

Jones: Well, as I said before, a mechanism design can be considered an area related to game theory. It sort of changes the story. In game theory, the structure of the game is given and we are trying to then determine equilibrium strategies. In mechanism design, we are coming up with the rules of the game so that the equilibrium strategies have nice properties that—in this case[s] like what I was describing—induces the players to be honest about the preferences.

Steve: Right. So now is this the kind of thing that would actually find use in—for example, the United Nation sends in a team of arbitrators to try to solve a dispute. Well, would this kind of analysis actually come into play?

Jones: This area of fair division, most certainly. There are different types of fair divisions dealing with either two or more players, and arbitration is an example of fair division.

Steve: And it is possible for both parties to feel like they got more than half of the deal.

Jones: Yes. My colleague, Steven Brams—[who] is one of the coauthors of the paper—has a book called A Win-Win Solution. The win-win solution[book] is paying homage exactly to that:Two players in a negotiation can both do better than 50 percent.

Steve: Dr. Jones, thanks very much.

Jones: Thanks for having me.

Steve: For more on the mathematics of cake cutting—and a little on pie cutting too—see my column called "The Kindest Cut" in the February issue of Scientific American. It's also available free at the Web site—www.sciam.com. Jones' paper appeared in the December issue of the Notices of the American Mathematical Society.

Now it’s time to play TOTALL.......Y BOGUS. Here are four science stories; only three are true. See if you know which story is TOTALL.......Y BOGUS.

Story number 1: The world's tallest man was enlisted to reach deep into a couple of dolphins to pull plastic out of their stomachs.

Story number 2: Some snowflakes may actually be identical.

Story number 3: A gluten-free pancake can fool the palate if it's made with rice and sweet potatoes.

Story number 4: Fossil remains of a giant sabertooth cat that would have weighed in at about two-and-a-half tons have been found in Wyoming.

We will be back with the answer. But first—does the underdog win more often in baseball than in hockey, and how many games does it take to ensure that the best team really finished first?. Eli Ben-Naim wondered about these questions and others—and as the group leader for complex systems analysis in the theoretical division in [the] Center for Nonlinear Studies at the Los Alamos National Laboratory, Eli Ben-Naim could actually answer those questions. To find out what he found out, I called him at his home in Los Alamos.

Steve: Dr. Ben-Naim, thanks for talking to us.

Ben-Naim: Hi Steve, how are you?

Steve: You study the relative competitiveness of various sports—the big four American team sports, as well as soccer—and can you briefly discuss what you found by studying that?

Ben-Naim: Well, we asked a very simple question. How many games do we have an upset? Where by "upset", we mean a weak team—a team that we perceive to be weak—beating a stronger team; and we saw that this number is surprisingly large in many of the sports we looked [at]. And in baseball, it's about 44 percent over a century with a few hundred thousand games. Next comes hockey; it's about 40 percent. And tied for last are basketball—[the] NBA—and American football—the NFL. It's about 33 percent or something like that.

Steve: So, it ranges from about 44 percent—where the underdog wins in baseball—down to 33 percent, where the underdog wins in football or soccer.

Ben-Naim: Yeah, it's quite a big spread.

Steve: Now, this is interesting because, for example, American football has a salary cap that is supposed to guarantee parity throughout the league, whereas baseball doesn't; and yet you are saying that baseball is actually more competitive than football.

Ben-Naim: Currently, it is, but the numbers that I just quoted are over a century. If you look over the last decade, American football has almost narrowed the gap with baseball and soccer—which are in the top—and they have done it precisely the way you are suggesting—salary cap and the draft and having a variable schedule where strong teams play a stronger schedule [and] weak teams play a weaker schedule. So, the NFL actually—from our data—has made a tremendous job of improving the parity clarity in its league. It is rather astounding how much improvement there is in [the] NFL in the past 40 years since the merger with [the] AFL.

Steve: I see. So by instituting the salary cap, you are actually doing what they hope that would do, and that's to increase the parity.

Ben-Naim: Precisely. Interestingly, we did not find its effect in the NBA, where the parity seems to be roughly constant over the past 30 to 40 years.

Steve: Despite a salar[y]ies cap!

Ben-Naim: Despite—I think—attempts by the league, yeah.

Steve: Any explanations you can come up with for that?

Ben-Naim: I could not make head or tail of the basketball data. I mean the NFL had the very clear trend, and baseball had a very slow trend of improvement over 100 years; but it was really hard to understand the NBA data. It was sort of going up and down without any particular pattern.

Steve: Interesting. One of the great things about sports for a statistician is that your database is so huge.

Ben-Naim: Indeed. And it's not only that, it's accurate. There is no doubt who won a game and who lost the game, and it's documented and all the games are available. There are no errors, you know, unlike in biology or in other fields, [like] physiology. So, that's one of the things that attracted us to look at sports [w]as the availability of the data, and the fact that it's free and accurate and it's trustable. This randomness is inherent in sports, and that has really very profound consequences. It tells us that we know—of a champion of the entire league or season or tournament—basically, there is a lot of luck involved. And that's really a profound fact in sports.

Steve: Well, that kind of takes us into this new paper that you have that's yet to be published that's called "How to Choose a Champion". There is a lot of mathematics in the paper, but basically I've read the abstract and what you are talking about is the inefficiency of a regular season schedule that involves all the teams for the whole year. Is that right?

Ben-Naim: Yeah, it tells you that, roughly speaking, in a league with 16 teams, [where] every team play[s] every other team once or twice, so they play at home and away series—such a format will reproduce one of the top four teams of [with] a good chance of winning the championship. Of course, the best team probably is more likely to win it, but it's not a big surprise if the four teams would win it. However, what such a format does is that this chance—of say, of the tenth team out of 16 to win—is really small, and the last team has practically no chance of winning a championship. So, this is what we call a league format. And the mathematics tells us something that we probably kind of anticipate, [which] is that leagues are very good in, you know, eliminating the bottom team, but they are not so efficient at picking the absolutely best team at the end of the season. And we see that if you look at the 2005 baseball season: The Yankees and the Red Sox were tied for first and there are many other cases where teams are trading places for first and second and third up to the last game of the season.

Steve: Let's say you have 10 teams in your league. Now, according to your paper, in order to establish a champion—that is, actually the best team—with a high certainty, you would have to play—if you have 10 teams in the league and each team is playing all the other teams the same number of times—you would have to play the cube of the number of teams; so the total number of games you would have to play to ensure that the best team wins would be a 1,000 games in a regular season.

Ben-Naim: Exactly. Every team would have to play every other team 10 times rather than once or twice, and that would guarantee that the best team wins—that the best team is the champion. And that sort of surprises, because you know the natural outcomes in it—yeah and n squared, every team plays each other once and that really produces the champion. So, what we celebrate is not necessarily be the best team. I mean, that's also what makes sports interesting.

Steve: Okay now, but then you talk about the fact that if you have rounds in which you eliminate the lower rated teams, you can pretty much ensure that your best team comes out at the end of the season as your league champion far more efficiently—with fewer games.

Ben-Naim: Yeah. You can pretty much do this with very, very [a lot] less than a [thousand]games; and all you need is a few games initially to sort of sort the teams out and figure out which team has no chance of winning at the end of the day; and you throw away most of the teams and keep a few that goes to the playoff—and we call that the championship round—and that reduces the [number of] game[s needed] by a huge factor.

Steve: So this paper is called "How to Choose a Champion", and you have just submitted it to what journal?

Ben-Naim: Physical Review E.

Steve: Tell us how all this relates to your actual work at Los Alamos.

Ben-Naim: So, much of my work is to do with studying random processes, and my traditional work has been on granular materials. I have been studying how random motion of grains of sand evolve and trying to model that. But I have recently gotten interested in trying to understand social dynamics and how people interact and how social structure[s] emerge—how do you have a middle class and an upper class? Then we came up with a colleague with a model that tells you that competition actually plays a big role. You can think about in economics—companies compete and they compete for market share, and if one company gains that necessarily means another company loses. And using a very simple model of competition that basically shows that, you know, if two companies compete, I would say two-thirds of the time the stronger one wins and one-third of the time the weaker one wins. You can really understand the emergent[ing] of social structures and hierarchies of companies or sports need more people; and the way we were drawn into the sports is really the model had lots of numerical quantitative prediction that we wanted to verify or falsify and see whether this model has anything to do with reality. And after thinking about it long and hard, we realized that sports is a really the ideal laboratory for testing our predictions; and the more we looked at into it, the more we realized that we can explain competition in tournaments and in leagues very, very well—w[c]ould match many observed data substantiating, what’s the probability that, you know, the 11th-seeded team in the NCA[A] tournament wins the whole thing. We looked at that as well, and it was pretty much a very simple model that explained many of the observed results in sports competition and championships and leagues and tournaments in a consistent way.

Steve: Interesting stuff Dr. Ben-Naim. Thanks so much for your time.

Ben-Naim: Thank you so much.

For more on the mathematics of competitiveness and scheduling, just Google Eli Ben-Naim.

Now, it's time to see which story was TOTALL.......Y BOGUS. Let's review the four stories.

Story number 1: Tallest man tackles dolphin digestive detritus.

Story number 2: Two snowflakes might indeed be identical.

Story number 3: Pancakes from rice and sweet potatoes taste like the real deal.

Story number 4: Giant cat fossil found in Wyoming.

Time’s up.

Story number 1 is true. Back in December, the world's tallest man saved a couple of dolphins by reaching way down with his extra-long arms into the dolphins' stomachs and pulling out pieces of plastic they had accidentally ingested. This all happened in China, home of 7-feet, 9-inch tall Bao Xishun.

Story number 2 is true. You probably can find identical snowflakes. The American Chemical Society reports that snowflake researcher, John Nelson says that big snowflakes are indeed probably unique, but some smaller snowflakes, which would still have a simple crystal structure compared with the bigger ones could probably be twins.

Story number 3 is true. Sweet potatoes and rice can make a good wheat-free pancake substitute for people with celiac issues who still want their stack of silver dollars. That's according to a study in the current issue of the Journal of Food Quality; full flapjacks need to be between 20 percent and 40 percent sweet potato flour to achieve the proper pancake hardness, cohesiveness, springiness and chewiness.

All of which means that story number 4 about the 5,000-pound sabertooth cat fossil is totally bogus. Because a new theoretical study has found that a terrestrial carnivorous mammal could probably never weigh more than about 2,200 pounds. They could never catch enough prey to support the energy requirements of their body, which would include the efforts involved in catching the prey they could never get enough of. For more on the size limits for carnivorous land mammals, listen to the January 16th edition of the daily Scientific American podcast, 60-Second Science.

Well that's it for this edition of the weekly Scientific American podcast. You can write to us at podcast@sciam.com. Check out news articles at our Web site, www.sciam.com, and the daily Scientific American podcast 60-Second Science is at the Web site and at iTunes. For Science Talk, the weekly podcast of Scientific American, I am Steve Mirsky. Thanks for clicking on us.

Web sites mentioned on this episode include www.sciam.com/podcast; http://cnls.lanl.gov/~ebn; http://www.ams.org/notices/200611/fea-brams.pdf; https://www.scientificamerican.com/article.cfm?chanID=sa006&colI D=15&articleID=1373A988-E7F2-99DF-3DF48A64628C76E9