Evelyn Lamb: Hello, and welcome to my favorite theorem, a math podcast where we asked mathematicians to tell us about their favorite theorems. I'm one of your hosts, Evelyn Lamb. I'm a freelance math and science writer in Salt Lake City, Utah. And this is your other host,
Kevin Knudson: Hi, I'm Kevin Knudson, professor of mathematics at the University of Florida. How you doing, Evelyn?
EL: I’m all right. I had a really weird dream last night where I couldn't read numbers. And I was like, trying to find the page numbers in this book. And I kept having to ask someone, "Oh, is this 370?" Because it looked like 311 to me. For some reason those are two of the numbers that like somehow, yeah, those numbers don't look the same. But yeah, it was so weird. I woke up, and I opened a book. And I was like, "Okay, good. I can read numbers. Life is ok." But yeah, it was a bit disorienting.
KK: That's weird. I’ve never had anything like that.
EL: So how about you?
KK: Well, I don't know. I was in California earlier this week, so I'm trying to readjust to Florida after what was really nice in California. It’s just gruesomely hot here and gross. But anyway, enough about that. Yeah.
EL: Yeah. So today, we're very happy to have Anil Venkatesh joining us. Hi, Anil, can you tell us a little bit about yourself?
Anil Venkatesh: Hi, Evelyn. Hi, Kevin. Yes, I am an applied mathematician. I teach at a school called Ferris State University in Michigan. And I am also a musician, I play soccer, and I’m the lead Content Developer for a commercial video game.
EL: Oh, wow. And I how I ran across your name is through the music connection. Because you sometimes give talks at the Joint Math Meetings and things like that. And I think I remember seeing one of your talks there. But I didn't know about the game developing. What game is that?
AV: It's called Star Sonata. And I'll plug it maybe at the end of the episode. But it actually relates because the theorem I'm going to talk about, well, I ran across it in my development work, actually.
EL: Oh, cool. So let's get right to it.
AV: Okay. Well, I'm going to talk about the Shapley value, which is due to Lloyd Shapley. The paper came out in 1953, and there's a theorem in that paper. It did not come to be known as the Shapley theorem, because that's a different theorem. But it's an amazing theorem, and I think the reason theorem didn't gain that much recognition is that the value that it kind of proved something about is what really took off.
So should I tell you a little bit about what the Shapley value is, and why it's cool?
KK: Yeah, let’s have it.
AV: Well, so actually, I picked up this book that came out in ’88, so quite a long time after the Shapley value was originally introduced. And this book is amazing. It's got like 15 chapters. And each chapter is a paper by some mathematician or economist talking about how they use the Shapley value. So it's just this thing that really caught on in a bunch of different disciplines. But it is an econ result, which is why I took a while to actually track it down once I came up with the math behind it.
EL: RIght.
AV: So putting this into context, in 1953 people were thinking a lot about diplomacy, they were thinking about the Cold War, or ensuing Cold War. And so here's a great application of the Shapley value. So you have the United Nations. It’s got in the Security Council, five permanent members who can veto resolutions and then 10 rotating members. So for a resolution to pass, I don't know if this is exactly how it works now, but at least when the paper was written, you needed nine out of 15 to vote in favor.
KK: That’s still correct.
AV: And of those nine, you needed all five of the permanent members. So you couldn’t have any of those vetoes. So you might ask, How powerful is it to have the veto? Can we quantify the negotiating strength of possessing a veto in this committee?
KK: Okay.
EL: Okay.
AV: Okay. And yes, you can with the Shapley value, and it comes down to, well, do you want to hazard a guess? Like, how many times better is it to have a veto?
KK: Like a million.
AV: It's a lot better. You know, I didn't really have a frame of reference for guessing. It's about 100.
EL: Yeah, I don't know… Oh, how much?
AV: A hundred.
KK: I was only off by four orders of magnitude! That’s pretty good.
AV: Yeah.
EL: Yeah, not bad.
AV: So the way the Shapley value carries this out is you imagine out of 100 percent, let's apportion pieces of that to each of the 15 members according to how much power they have in the committee.
KK: Okay.
AV: And so if it was 20% to each of the permanent members, there wouldn't be any left for the remaining 10 voting, right? In actuality, it's 19.6% to each of the five permanent members.
KK: Okay.
EL: Wow.
AV: And then that last sliver gets apportioned 10 ways to the rotating members. And that's how we come up with roughly 100 times more powerful with the veto.
EL: Okay.
AV: I will tell you how this value is computed, and I'll tell you about the theorem. But I'll give you one more example, which I thought was pretty neat and timely. So in the US, laws get made when the House of Representatives and the Senate both vote with the majority in favor of the bill, and then the President does not veto that bill.
KK: Yes.
AV: Or if the president vetoes, then we need a two-thirds majority in both houses to override that veto. So you could ask, well, if you think of it just as the House, the Senate and the President, how much of the negotiating power gets apportioned to each of those three bodies when it comes to finally creating a law? And if you apply the Shapley value, you get ratios of 5:5:2, which means the president alone has a one-sixth say in the creation of a law.
EL: Okay. Yeah, I was when you said that I was thinking, I mean, if you do the Security Council one, the people with vetoes had almost one fifth each, so I was thinking maybe like being one third of the things that could veto, it would be about a third for the president, but that seemed too high.
AV: Yes. So if the if the it was not possible to override the veto, then it would be a little bigger, right?
EL: Right, right. Okay.
AV: Yes. Now, if you actually break this down on the individual basis, so you might think, okay, well, the house gets 5 out of 12 of the power, but there are so many people in the house, so each individual person in the house doesn't have as much power, right?
KK: Yes
AV: When it breaks down that way, so going individual representative, individual senator and President, the ratio goes like 2 to 9 to 350.
EL: Okay.
AV: So the President actually has way more power than any one individual lawmaker.
KK: Well, that makes sense, right?
AV: Yes, it does. And so, yeah. The great thing about the Shapley value is that it's not telling you things you don't know exactly, but it's quantifying things. So we know precisely what the balance of power is. Of course, you've got to ask, “Okay, so this sounds like a like a fun trick. But how is it done anyway?”
EL: Yeah.
AV: The the principle behind the Shapley value is just, it’s beautiful in its simplicity. The theory is this—and actually when I tell you this, it's going to remind you of a lemma that's already been on this podcast.
EL: Okay.
AV: More than one actually, this just a very standard kind of technique. So imagine all the possible orderings of voters. So suppose they come in one at a time and cast their vote. Under how many of these arrangements is a particular person casting the pivotal vote? The more more frequently the more arrangements in which Person A casts the typical vote, the more power Person A is allotted.
EL: Okay.
AV: That's it. So we actually just take an average overall possible orderings of votes and basically count up however many of those orderings involve a particular person casting the pivotal vote, and that's how we that's how we derive this breakdown of power.
EL: So this is a lot like having everyone at a vertex and looking at symmetries of this object, which is kind of reminding me of Mohammed Omar's episode about Burnside’s lemma. I assume so that's the one that you were thinking about.
AV: Yes, that’s the one I was thinking about.
EL: But you said another one as well.
AV: The other one hasn’t actually been on this podcast yet. And I could have talked about this one instead. But the Cohen-Lenstra heuristics for the frequency of ideal class groups of imaginary quadratic extensions also involves an idea, now this one gets a little deeper. but essentially, if you dig into the Shapley value, you notice that the bigger the group is, the less power each person has in it. And yeah, so there are various other twists you can ask using the Shapley value. So in the Cohen-Lenstra heuristics, you essentially divide by the automorphisms of a group, you weight things inversely by the number of automorphisms they have. Anyway, that one also evoked because you take sort of an average across all the groups of the same size. So, I'm not claiming that there's some kind of categorical equivalence between the Cohen-Lenstra heuristics and the Shapley value, but this idea of averaging over an entire space comes up in a bunch of different branches of mathematics.
KK: Sure.
EL: Yeah. Very cool. So, we've got the Shapley value now, and what is the theorem?
AV: The theorem, and this is what makes it all really pop, the theorem is why people, why the Shapley value is so ubiquitous. There is no other logical apportionment of 100 percent than the Shapley value’s algorithm.
EL: Okay.
AV: There is no other sensible way to quantify the power of a person in the committee.
EL: Interesting.
KK: What’s the definition of sensible?
AV: I’ll give it to you, and and when you hear—this is how weak the the assumptions are that already gave you this theorem, and that's why it's amazing.
KK: Sure.
AV: Efficiency: you must apportion all hundred percent
KK: Okay.
AV: Of course. Symmetry: if you rename the people but you don't change their voting rules, the Shapley value is not affected by that kind of game.
KK: Sure.
AV: Null player: if a person has no voting power at all, they get zero percent.
KK: All right.
AV: Obviously. And finally, additivity. That one takes a little bit more thinking about, but it's nothing crazy. It's just saying, like, if there are two different votes happening, then your power in the total situation is the sum of your power in the one vote and your power on the other vote. If there's more than one game being played, basically, the Shapley value is additive over those games.
KK: That's the weirdest one, but yeah, okay.
AV: Yeah, I looked at it. I thought a little bit about what to say. And then honestly, if you dig into it, you realize it's just, like, not saying anything amazing. You have to think about this: the Sheppey value, it's a function, right? So we're working in the space of functions, and weird things can happen there. So this is just asserting you don't have any really wild and woolly functions. We're not considering that.
EL: Okay.
AV: So you just have these assumptions. And then there's only one. And the way they prove it is by construction. They basically write down a basis of functions, and they write down a formula using that basis, and there can only be one because it's from a basis, and then they prove that formula has the properties desired. It’s a really short paper, it's like a 10 page paper with four references. It's amazing.
EL: You said this is the 1953 paper by Shapley?
AV: Yes, by Shapley.
EL: Yeah, was there another author too, or just?
AV: No, Shapley collaborated with many people on related projects, but the original paper was just by him.
EL: Yeah. So I assume people have maybe looked at Shapley values of individual voters, like in the US or in an individual state or local election. We're recording this in election season, a little bit before the midterm elections.
KK: Yeah, can’t end soon enough here.
EL: Yeah, I guess. Oh, I guess actually, that wouldn't be that interesting, because it would just be, I mean, within a state or something. But I guess, the Shapley value of someone in one state versus another state might be a fairly interesting question.
AV: Oh, yes. But even the Shapley value for one person in a certain district or another district, this gets into gerrymandering, for sure.
KK: Right.
AV: I don't know to what extent people have thought about the Shapley value applied in this way. I imagine they have, although I haven't personally seen it mentioned, or anything that looks like it in the gerrymandering math groups that have been doing the work.
KK: No, I mean, I've been working with them a little bit, too. I mean, not really. And yeah, of course, it sort of gets to things like, you know, the Senate is sort of fundamentally undemocratic.
EL: Right.
KK: I mean, the individual senators kind of have a lot power. But you know, the voters in Wyoming have a lot more, you know, their vote counts more than than a voter and say, Florida.
EL: Right? Or the voter in Utah versus the voter in Florida.
AV: I'm thinking about within a specific state, if you look at the different districts. I mean, I read a little bit about this. And I see that they're, they're trying to resolve kind of the tension between the ability to cast a pivotal vote and the ability to be grouped with people who are like-minded. I don't know, it seems like, I wonder whether there's some extent to which they're reinventing the wheel, and we already have a way to quantify the ability to cast a pivotal vote. There's only one way to do it.
EL: Interesting.
AV: I don't know. Yeah, I'm not super informed on that. But it feels like it would apply.
KK: Yeah. So what drew you to this through this? I mean, okay. So fun fact: Anil and I actually had the same PhD advisor, albeit a couple of decades apart, and neither of us works in this area, really. So what drew you to this?
AV: Well, that's why I mentioned my game development background. So this game, Star Sonata, is one of those massively multiplayer online role-playing games. It actually was created back in 2004, when World of Warcraft had just started. And basically the genre of game had just been created. So that's why the game started the way it did. But it's kind of just an indie game that stuck around and had its loyal followers since then.
And I also played the game myself, but several years ago, I just kind of got involved in the development side. I think initially, they wanted—Well, I was kind of upset as a player, I felt they’d put some stuff in the game that didn't work that well. So I said, “Listen, why don't you just bring me on as a volunteer, and I'll do quality assurance for you.” But after some time, I started finding a niche for myself in the development team, because I have these quantitative skills that no one else on the team really had that background in. So a little later, I also noticed that I actually had pretty decent managing skills. So here I am, I'm now basically managing the developers of the game.
And one of my colleagues there asked me an interesting question. And he was kind of wrestling with it in a spreadsheet, and he didn't know how to do it. So the question is this, suppose you're going to let the player have like, six pieces of equipment, and each piece of equipment, let's say it increases their power in the game by a percent. Power could be like, you know, your ability to kill monsters or something.
EL: Yeah.
AV: So the thing is, each piece of equipment multiplicatively increases your power. So your overall power is given by some product, let's say (1+a)(1+b)(1+c), and so on. One letter for each piece of equipment. So you write down this product, you have to use the distributed property to work out the the final answer. And it looks like 1 plus the sum of those letters plus a bunch of cross-terms.
KK: So symmetric functions, right?
AV: Yes, exactly. So what his question was, “Okay, now that we're carrying all six of these pieces of equipment, how much of that total power is due to each piece of equipment?”
EL: Okay.
AV: How much did each item contribute to the overall power of the player? The reason we want to know this is if we create a new piece of equipment the player can obtain, and we put that in, and then suddenly we discover that everyone in the game is just using that, that's not good game design. It's boring, right? We want there to be some variety. So we need to know a way to quantify ahead of time whether that will happen, whether a new a new thing in the game is going to just become the only thing anyone cares about. And they'll eschew all alternatives. So he asked me, basically, how can I quantify whether this will happen? And I thought about it. And as you can tell, what this is asking about is the Shapley value in a special case where all the actors contribute multiplicatively to the to the total. And I didn't know that at the time because I'd never learned about the Shapley value. I didn't really learn much econ.
KK: Sure.
AV: So I just derived it, as it turns out, independently, in this in this special case. And it works out in a very beautiful formula involving essentially the harmonic means of all those letters. So reciprocals of sums of reciprocals. The idea there—and I mean, I can give a real simple example—Like, suppose you have two items. One of them increases your power by 20%, and one increases by 30%. So your overall power is 1.2 times 1.3. So what does that get to? 1.56 So of that of that 56% increase, 20% goes to the one item, 30 goes to the other, but 6% is left over. And how should that be aportioned?
EL: Right.
AV: Well, if you think about it, you might think, “Well, okay, the 30 percent should get the lion's share.” And maybe so, maybe so. But then there's a competing idea: because that 30% was pretty big, the 20 percent’s effect is amplified, right? So it's not, there's not an immediately obvious way to split it. But you can kind of do it in a principled fashion. So once I wrote this down, you know, I gave it to my colleague, he implemented it, it improved our ability to make the game fun. But then I also started wondering, like, look, this is, this is nice and all, but someone must have thought of this before, you know? So I don't actually remember now, how I came across it, whether I just found it or somebody sent it to me. But one way or another, I found the Shapley value on Wikipedia. I read about it, and I immediately recognized it as the generalization of what I'd done. So, yeah.
EL: Oh, yeah. Well, and this seems like the kind of thing that would come up in a lot of different settings, too. A friend of mine one time was talking about a problem where, you know, they had sold more units and also increased price, or something. And, you know, how do you allocate the value of the increased unit sales versus the increase price or something, which might might be a slightly different, the Shapley value might not apply completely there.
AV: No, it does.
EL: Okay.
AV: Yes, that’s called the Aumann-Shapley pricing rule.
EL: Okay, yeah.
AV: Yeah. So, questions of fair division and cost allocation are definitely applications of the Shapley value. So, yeah.
EL: Neat. Thanks.
KK: Very cool. The other fun part of this podcast is that we ask our guests to pair their theorem is something What have you chosen to pair this with?
AV: Well, like many your guests, I really struggled with this question.
KK: Good.
AV: And the first thing I thought of, which won't be my choice, was a pie because you have to, you know, fairly divide the pie. I told this to one of my friends, and I explained what the Shapley value was, and she was like, “No, that's, that's a terrible idea, because you want to divide the pie equally.” But the Shapley value is this prescription for dividing unequally but according some other principle. So it won't be a pie. So I actually decided this morning, it's going I'm going to pair it with a nice restaurant you go to with your friends, but then they don't let you split the bill.
KK: Ah.
EL: Okay. Yeah, so you have to figure out what numbers to write on the back of the receipt for them read your credit cards. Or for the added challenge, you could decide, like, given the available cash in each person's wallet? Can you do that?
AV: Oh, don't even get me started.
KK: This is the problem, right? Nobody has cash. So when you're trying to figure out how to how to split the bill…People think that mathematicians are really good at this kind of thing, and in my experience, when you go to a seminar dinner or whatever, nobody can figure out how to split the bill.
AV: If I'm out with a bunch of people, and we have to split a bill, let it not be mathematicians, that’s what I say. Let it be anyone else.
KK: Yeah, because some people want to be completely exact and each person ordered a certain thing and it cost as much and you pay that, then you divide the tip proportionally, all this stuff. Whereas I'm more, you know, especially the older I get, the less I care about five or $10 one or the other.
AV: Yeah, well, I find it's good if I go out with a bunch of people who are kind of scared of math, because then they just let me do it. You know, I become the benevolent dictator of the situation
KK: That’s happened to me too, yeah.
EL: So, I don't remember where what city Ferris State is in.
AV: Well, it's in a town of Big Rapids, which is a little the Grand Rapids, which is a little bit more well-known
EL: Slightly grander. So, yeah, you're the slightly lesser rapids?
AV: So, there are at least five rapids in Michigan, like five different places named something rapids.
KK: Sure.
EL: So do you have a Big Rapids restaurant in mind for this pairing?
AV: You know, they're all really nice about splitting the bills there. So I was thinking something maybe in New York City or Boston.
KK: College towns are pretty good about this. In fact, they'll let you hand them five cards, and they'll just deal with it.
AV: Yeah, totally.
KK: Yeah, yeah, very nice. So your rapids are big but Grand Rapids’ rapids are grander.
AV: They’re much grander. Don’t get me started about Elk Rapids. I don't know how to compare that to the other two.
KK: Elk Rapids?
EL: Yeah, Big, Elk, and Grand, not clear what order those go in. [I guess Iowa’s got the Cedar Rapids.]
AV: Yes. I don't remember the other two rapids, but I know identified them at some point.
EL: Well thank you so much for joining us
AV: Thanks for inviting me. It was great.
EL: Yeah, I learned something new today for sure.
KK: Math and a civics lesson, right?
EL: Yes. Everybody go vote. Although this episode will already be out. [Ed. note: Evelyn said this backwards. Voting occurred before the episode, not vice versa.] But get ready to vote in the next election!
KK: Yeah, well, it's never ending right? I mean, as soon as one elections over, they start talking about the next one. Thanks, Anil.
EL: All right, bye.
AV: Thank you.
[outro]
