The Maths of Game Theory

- Today, I'm going to tell you about The Mathematics of Game Theory. When we buy and sell, barter, bid at auctions, and compete for resources more widely, we want to make sure that we're using the best strategy that will get us the best deal, and mathematics can help us with this. In particular, the field of mathematics known as game theory. And in fact the Nobel Prize for Economics has been won several times by mathematicians who were using game theory to analyze economic questions. So we're going to talk through some of those, so is questions today. On the way, we're going to learn how much to charge for a cup of coffee, the best way to fight a duel, and when you should buy a house. So I'm going to begin just by giving a couple of examples of the sorts of questions that mathematics can help us with. So you've got three things there. On the top left, you've got price war. So imagine you've got something to sell, you've got a crowded market that you're competing for market share in. One possibility is that you could lower your prices to try and increase your market share, your profit per item will go down but hopefully you sell more items. What should you do? How do you set your prices? Below that, a sort of slightly similar thing is the problem of the world's best coffee. Now as you know, whenever you travel anywhere and you see some cafes and all of them claim that they sell the world's best coffee. So if you're a tourist, you don't know which cafe to go in, you just sort of pick randomly, and so you are not very price sensitive there and the cafe owners perhaps know that. So they also have to bear in mind, if you are setting the price of your coffee that the locals get disgruntled if you massively, you know, charge make pounds for a cappuccino. So there the question is, how much is the price sensitivity in that market comparing with what tourists will sort of end up grudgingly paying versus the locals that you need to keep on side. Again, mathematical models and ideas can help us make those sorts of decisions. And the other picture got up there is clearly some very, very educated, knowledgeable art buyers at an auction. This is a fun old cartoon, modern connoisseurs it's called, so the picture's upside down there when you are. When you're bidding for things and it need not be at a Christie's or Sotheby's, but on eBay or any other sort of place where you're offering a price, what's your best strategy? And from the other side, if you are an auctioneer, what kind of auction structure should you use? Well, a lecture with the word game theory in the title, that's two words, with the phrase game theory in the title almost legally has to mention one very, very famous game or situation where you are trying to think of a strategy. So I thought, I should mention this, even though probably a few of you in the audience will have heard of this before, but let's talk about it, the prisoner's dilemma. And this is a famous example of where you can use a bit of reasoning to decide there's sort of a dilemma that happens in a situation. And the situation is this, you and your criminal accomplice have been caught by the police and you're suspected of some crime, maybe it's burglary or something. Now they take you off to separate places and they question you. If both of you don't say anything, then they haven't got enough evidence to charge you with the big thing, so maybe they can get you on a lesser charge. So you would each serve one year in prison because they can't get you for the big crime. But if one of you talks and you can implicate your accomplice, frowned upon in some circles, but, you know, let's... It's a theoretical game. You implicate your accomplice. If they don't talk, then there's not enough evidence against you, so you get to go free because you've helped the police and you can't yourself be convicted and then you are unfortunate acquaintance will get the full sentence. If both of you talk, and we can put this in a table of outcomes. If both of you talk then you've cooperated, but you're both implicated so maybe you get three years in prison each. So you can write down all of the outcomes in a little table like this. And the question is, what strategy should I, if I'm prison A, let's say, what should I do? First of all, let's think, if we're acting purely out of self-interest and let's say there's no repercussions, which may not be very realistic. But if you are prisoner A, what do you do? You don't know what the other person is going to do. They're over there, they've separated you, you don't know, are they going to talk, are they not going to talk? So you have to plan for both possible outcomes for what they will do, you don't know. So what we can see is that that the column there that has prisoner B talks, those are the outcomes if prisoner B talks depending on whether you talk or not. So you can see if you talk, in that column, prisoner B, you as prisoner A will either get three years or five years in prison. And of course, you want the least of time possible. So the best thing for you to do, if prisoner B is going to talk, the best thing for you to do is also talk, right? So that's that. What about if prisoner B doesn't talk, they stay silent? Well, that's the column on the right, second column there. But again look, for you, your outcomes, depending on your decision, you either get no years, you go free or you get one year. So again, in that case, it's better for you to talk. So this is sort of a bit of paradox because if you're just acting purely from self-interest, this kind of decision making would say you should always talk, because whatever B does, the least worst outcome for you comes from talking. The problem is prisoner B is making exactly that calculation, so they're going to talk as well. So you'll be in the situation where you both talk and you both get three years. However, if you had both stayed silent, it would be a better outcome. But the problem with this better outcome is you can improve it if you unilaterally decide, actually I'm going to talk. So it's not a kind of stable equilibrium, the one where you get one year each. But colluding in this case or agreeing to cooperate and both not saying anything would get you a total of two prison years, but it's unfortunately changing and betraying your friend, you may be able to go free. So that's a sort of a moral thing mixed in with the mathematical thing. But this idea that you can make a kind of table of outcomes and look at the payoffs for each strategy and make decisions based on those numbers is where we start to do some mathematics. So our first putative financial situation, price war, is exactly the prisoner's dilemma just in disguise. So here I've got two companies, Acme Widgets and BestCo who also make widgets and they are competing for the market share of widgets, which I still don't really know what a widget is, but all the examples always use widgets. Whatever they are, they're both selling them, and there's a total market for let's say a hundred widgets. If they both charge the same price for each widget, then they will get equal market share, 50 each. But if one price is lower, then there's a bit of laziness about swapping over to a different company. But let's say that 80% of people will then switch to the lower priced provider, and so the lower price will get an 80-20 market split. And so they'll sell 80 widgets rather than... The more expensive one will only sell 20. So you could, you know, put in some numbers in and see what will happen. So let's say, if you charge a higher price, you make five pounds profit on every widget that you sell, and at lower price, you'll make four pounds profit and you could construct a table of all the outcomes. And so this is now Acme versus BestCo. So A for Acme, of course. So here you've got in the first row there, what happens if A cuts their price and you can work out what profit will happen for each scenario. So in the top they've got, if A and B both cut their prices, then their price will end up being the same, and so they'll both make the same profit which is four pounds each for every 50, and you sell 50 widgets, so 200 pounds. If A cuts the price but B doesn't. So we are starting off here, they're both charging this higher price and they're making five pound profits each. So we're start off in the bottom right hand corner where they're selling 50 widgets for five pounds profit, they make 250 pounds profit. So what's the incentive here for company A or Acme, they, if they cut their price, which would be the top entry here, if they cut their price and B doesn't, their profit shoots up'cause they suddenly now sell 80 widgets for four pounds profit, 320 pounds profit. But poor old B, BestCo, they are only selling 20 widgets now. So even though they're making five pounds on each, their profit has gone right down. So if A cuts their price, they increase their profit at the expense of company B, and now BestCo, what's it going to do? Well, it's got to cut it's prices as well now, otherwise it's really in a bad place. So maybe it does that. And now you're in this position in the top left where they've both cut their prices, there's a new position where they both have equal market share again, but their profits are lower. And again, now whats to stop company A cutting its prices again, and increasing its profits temporarily until the other one cuts the price. So this is why governments have to legislate against collusion because, of course, what you'd really like to do if you are these companies, we should want to keep our profits high and that means we have to know what the other guy, we have to agree between us to have a higher price. But if one cuts, then they all have to cut. And so governments have to legislate against these kind of, let's all agree to inflate our prices and keep them high because it's a tempting strategy, but it's just the prison's dilemma in disguise. Now there's a game theorist called David Blackwell who had an interesting comment about the prisoner's dilemma. Here he is. He was working in the 40s and 50s on game theory, and we'll talk about one of the things he did in a moment. And he said, you know, a lot of these perhaps toy problems, there are real world applications in economics, but also this time it was at the height of the Cold War, and there are lots of scenarios in that that mimic situations like the prisoner's dilemma. So he remarked about this that it was a bit similar to the Cold War situation with sort of America or the West and the Soviet Union and they kept sort of escalating how many weapons they have. And, of course, the best thing really is for everyone to disarm and get rid of all their weapons. But then you worry that your opponent is not doing that and then they keep their weapons. So unilateral disarmament was felt to be like too risky of a strategy because then you are sort of at a disadvantage. So it's a bit like the prisoner's dilemma where actually it would be nice if you would cooperate and disarm, but that was too risky because what if the other person doesn't do that, and then they've got all the weapons and you haven't got any, was the thinking. So again, it's the prisoner's dilemma in another guise. So David Blackwell, I mean, what a guy, we don't hear enough about him actually. He was a real trailblazer. When he went to Princeton University, the Institute of Advanced Study at Princeton, he was not only the first black faculty member there, but it was at a time when they'd never even had a black student. So like real, real trailblazer. I think he was only the seventh African-American to get a PhD, and he was absolutely top of his field, was the Head of Department of Statistics, I think, at Berkeley for 30 years and some amazing work in game theory, which I will just give you a little idea of. And it's about duels and you could see as a kind of cold war aspect if you think. So, yes. This is the picture, Pistols At Dawn, but there are more real world scenarios where you might be in a situation like this. For example, in a warfare type situation or some kinds of auction as well. And the question here is if you are fighting a duel, so I really like these, these are the petticoat duelists, which is an old picture from 1792. So if you're fighting a duel kind of in the traditional setting, what you do is, I know, you meet up at dawn and then you walk away from each other, you turn around to face each other, pistols raised, and then you start walking towards each other and at some point you fire, you have one bullet, you could fire your bullet and if you hit the other person then you know you've won, and if you miss, then they can come up and let's say finish things off and then they've won. So the question here is when should you shoot? When should you fire your pistol? If you think this is too frivolous, you could imagine two nuclear submarines deciding whether or when to fire their missiles if the stakes aren't high enough. When should you fire? And there's a interplay between two things. If you fire very early, then you're really far away from your opponent and so your chance of actually hitting them is lower. But if you wait until you're very close then there's a risk that they already fired first, and so you are in no position to fire. So the question is what's the right place? What's the sweet spot? When should you fire? And you can model this mathematically. So you can decide what rules would work best for you, you can vary these settings, you can explore all of this, and I encourage you to do that 'cause playing is fun and that's what we like doing. Don't re-enact it in real life though, health and safety. So let's say, we'll make some rules of engagement. So you're going to have one chance each to fire. You initially are standing 20 paces apart and then you start walking towards each other, and so after you've walked 10 paces, if you get to that point, you'll be right next to each other. We'll assume that the opponent's equally skilled so they have an equal chance at any particular stage of successfully hitting another person. And that the probability of hitting your opponent after p paces, and I'll assume you have a whole number of paces if you want to do this, you know, do it kind of continuous. You can have a continuous idea of this, instead of this, which is discrete a whole number of paces. The probability is we're going to say is p over 10. After 10 paces, when you're right next to each other, that'll be a 10 out of 10, a hundred percent probability of actually successfully hitting them. But if you fire after zero paces, you're so far away, you're not going to hit them, and then it's one in 10 probability for one pace and so on. So how do we decide the outcome? Well, if I fire first and I hit you, then I've won. And if I fire and I miss, then that's bad for me because you, wherever you were planning to fire from, you can then just actually walk up to me and take your time and be guaranteed to win. So if I fire first and hit you, I win. If I fire first and miss you, I lose. If we both fire at the same time, and both hit or both miss, then it's a draw. So that's the kind of what the idea is. Now how are we going to put some numbers to this? It's not about profits or time in prison or whatever, well, it might be depending on the outcome. It's not about those things, so what we can do is just assign a value to winning. And the simplest one is... So the two people fighting are going to be called Colin and Rose. And it's 'cause I've got a table, and Colin is going to have the columns, and Rose is going to have the rows. (laughs) So if you like that humor, watch my other Gresham lectures. So the outcome is going to be, Rose gets kind of plus one for a win, if she wins, she gets zero if it's a draw, and minus one if she loses. And this type of game is what we call a zero sum game because Colin, if Rose gets plus one, then, of course, that means Colin's lost and will get minus one. So the sum of the outcomes is zero always. So actually when we do this little table, there's no point including the outcomes for Colin from his point of view because we can just deduce them, it's minus whatever the outcome was for Rose. So that simplifies things a bit in the zero sum game. So how do we actually work out what the payoff is for a particular strategy? Well, you can work out the probabilities and then do the calculation with these outcomes. I'll show you. Example, Rose decides she's going to fire after four paces and Colin decides he will fire after six if he gets the chance. So obviously they don't know what the other one's doing. So after four paces, that means Rose will fire first, fires after four paces, she has a four in 10 'cause that was our little rule, a four in 10 chance of successfully hitting Colin and therefore winning. So with a four in 10 chance she'll have plus one value, but six times out of 10 she'll miss and that means Colin will win. So then the outcome will be minus one for Rose. So you can just work, you know, add up those probabilities and find the expected outcome, the expected value of this strategy and you get minus 0.2. So that's a negative number. So it looks like it's perhaps, you know, zero would be kind of neutral for Rose and anything negative means it's likely that Rose is going to come off worse with this strategy. Okay, so you can do some other ones. If Rose says I'll fire after four paces but Colin is firing after two, then Colin will fire first, so Rose will lose with the probability of two in 10'cause two tenths of the time Colin hits, and she'll win with the probability of eight in 10. So you can add those up and you get plus 0.6, so that strategy looks pretty good for Rose. And if they fire at the same time, both after four paces, then if they both hit or they both miss, it's a draw. So we don't need to worry about those'cause that'll be multiplying by zero at some point it won't affect the outcome. So the only thing we have to account is Rose could win by, she hits with a probability for four in 10 and Colin misses with a probability six in 10, so that would give her a plus one. And then a kind of symmetrical calculation for Rose missing, which she does six tenths of a time, and Colin hitting, which he does four tenths of a time will give you a minus one, a loss for Rose. So you just sort of average these out to get the expected value and actually it's zero, they cancel each other out which makes sense because these are equally matched opponents firing at the same moment. So you would hope that this would be... That they'd have the same chance with that particular strategy. So okay, you can do all these individual calculations. I'm going to put a big table of numbers up, don't worry, don't expect to read every one of them, I just want to show you it. You can do these calculations for all the possibilities. So Rose gets the rows and Colin gets the columns. So you can see like that R4, for example, in the fourth row down, that is what happens when Rose fires after four paces. And you can see that, so in the first column it's Colin firing after one pace that's good for Rose, it's an expected value of plus 0.8. So you get all these numbers, okay. How does that help? How are we going to decide what the best strategy is? So one that you could various ways of attacking this, you don't know, if you are Rose, you don't know what Colin's going to do, and you don't know kind of the probability of which strategy Colin might pick. So you probably don't want to just add up all these numbers in each row and say which one's the best. So one strategy you could use or one decision making process for what's the best strategy is to do with this column on the far right hand side. What you think is, in this method, you say, okay, if I fire after four paces I'm going to be pessimistic and think, well, Colin, obviously, Colin's my opponent, Colin wants to do the best for Colin, not for me. So I'm going to be pessimistic and say what's the worst case scenario here? And after four paces, the worst case scenario is that Colin decides to fire after five or more paces because then the expected kind of payoff for Rose is this minus 0.2. So for Rose, kind of the worst case scenario, the minimum expected outcome is this minus 0.2. So you can put that on the right hand side, this is what this column is measuring, the sort of the worst case in each row for Rose. And so you could then perhaps judge the strategies by saying, all right, I want to kind of have the least worst outcome so I'm going to maximize this minimum thing. You can call it a maximin strategy. So she looks down all of these things, says, well, I definitely don't want to fire after one pace'cause then worst case scenario is a minus 0.8, that's awfully close to Colin being guaranteed to win. It looks like the middle two firing after five or six paces give you the least worst outcome here of zero. And so, Rose will probably pick one of those. Meanwhile, Colin, all of these values are giving Rose's pay off but remember Colin's are just minus that. So Colin here will, instead of wanting to maximize the minimum values, he'll want to minimize the maximum values'cause the maximum values are when Rose does really well. And so Colin will also end up thinking, well, I'll go in the middle somewhere, five or six paces. And if you compare rows five and six, six appears to be sort of a dominant strategy you call it because they're the same except in some places the six row numbers are higher. So if I were Rose, I would fire after six paces, and Colin probably will as well. And actually that outcome means, since they're fairly matched this makes sense that there's basically an even chance of each of them winning. So it's basically going to be a draw probably. Of course, it's all probability, so you don't know what's definitely going to happen but this is about choosing a strategy. So okay, now you know how to fight a duel. Can we extend these sorts of ideas? And in particular this idea of minimizing our worst case scenario and choosing it through that way. Well, I want to tell you about one of the first bits of mathematic around game theory, and to do that, I want to give you a slightly smaller example than this giant one. But also, duel's are pretty much, you know, one off things probably, you're not going to repeatedly fight duels, I hope. Whereas you might repeatedly take penalties in a football game, or at least over your footballing career. I'm aware there's maybe some sort of competition in football going on at the moment. So maybe this will be useful to the players, I don't know. The question is here, and this is an example of what we're going to see. Can you find some sort of equilibrium point where both of you have got strategies that are optimal in the sense that deviating unilaterally from that strategy makes your predicted outcome worse. I suppose you call it a local maximum where you've got something that you both have developed and if you change what you do, it can't improve your your situation. So the game here I'm talking about, for our American friends, soccer, for everybody else, football. It's when you have a penalty. And this is where, so you've got a striker who's trying to kick the ball into the goal, and you've got the keeper who's trying to stop the ball going into the goal. So this is a zero sum game because either a goal is scored or it isn't, and the one is a good outcome for the striker, and the other one is a good outcome for the keeper. So it's a two player zero sum game like the dueling problem. And in this example, picking a single strategy is a terrible idea. So that's called a pure strategy. For instance, if you said, well, I'm actually, you know, I'm right footed so I'm always going to aim to the right. That might work first time, but if you always aim to the right, then, of course, the keeper will know that and then they'll always move to the right, your right, your right, and so then that's going to lessen your chances of actually scoring. So you can draw up a sort of... You know, you can watch lots of penalties being taken and you can see what the odds are of different... What proportion of penalties will go in under different circumstances. So I've basically simplified it to say, you know, you either, you go right, you stay where you are, or you go left, that's essentially your choice as both striker and keeper. So here, I've exclusively talked about you're the striker, I'm the keeper, I've talked about the striker's right. So in that top left hand, that 50% thing, that's what happens if both of you go in the same direction to the striker's right then about 50% of the goals will go in'cause you might not get there in time or, you know, something like this. If the striker is going to the right and you stay in the center, 80% will go in. So some, you know, will be the striker is wide or goes over the goal post or something, and some you might just get there in time. Even if you stay there, you might just get to with fingers on it. And then the right hand side is where the striker is kicking to the right but the keeper moves left and then you can imagine 90% of those are going to go in, it'll be the striker's error if they don't. So you can look at these statistics and you can say, you know, you could say, well, I should always go right then or always go left. But if you always do that then people will get wise to the strategy. So a pure strategy like that is not going to work, you're going to need a mixed strategy where you just mix it up a bit enough to create uncertainty so that they are not going to, you know, always go to the right or left. For example, if both players adopted a strategy of going just randomly one third of the time going right, left, or staying in the middle, then you could work out the expected payoff of that and it would be so, you know, if they're doing this randomly, there'll be one ninth of the time for each of those nine boxes in the table. So you can just add all of those up, so 50%, that's a probability of 0.5, for instance, add all 'em up, divide by nine and the outcome would be 0.7. Otherwise 70% of the time there's a goal. But actually I looked it up, in international competition, many, many penalties have been taken over the years, about 75% of penalties result in a goal, are converted. And so this is less than what we know the actual outcome is. Can you improve this? Maybe you can tweak it a bit, maybe you can go right a little bit more than you go to the middle. And the question is, is there ever an equilibrium point? Is there a time when you've refined your strategy, you've got the percentages just right so that if you were to change that you can't improve what your outcome is? And here's where John von Neumann comes in, and he proves something called the Minimax Theorem which says in a two player zero sum game, there is always going to be an equilibrium strategy that's minimax one player and maximin for the other. In other words, you're getting the best of the worst case scenarios if you're one player, and the reverse of that if you're the other player. Part of the reason for this is, this is zero sum game, so this concept of minimax and maximin can relate to each other. So he proved that, and you'll want to know what the footballers should do. So there's a paper by, I put a link in the transcript, Ferenc Forgó, which solves this for the football example using something called linear programming. And actually both players should go to the right 42% of the time, to the left 42% of the time, and in the center 16% of the time. If you never go in the center, then, of course, people will learn, go to the center. So that's the equilibrium for this particular example. Now, I'm aging myself now, but when I was young in the olden days, there was an advert for a trainer company, let's say a sports sort of brand, which I won't name, and it said 1966 was a good year for English football. If anyone remembers that campaign, of course, in 1966, England won the World Cup. But also that the pure point of this advert was that also in 1966, a footballer called Eric Cantona was born and he played for Manchester United and he was a good footballer. So he was sort of playing within England. So they sort of steered you in the wrong way. So I will now say, 1928 was a good year for game theory because John Nash was born, and John Nash, perhaps the most famous game theorist because there was a film called "A Beautiful Mind" about him. This is what he looked like in I guess the early 90s. If you watch the film, he's played by Russell Crowe, which is perhaps not an absolutely accurate depiction, but anyway, it doesn't matter. (audience laughing) It's a great film, it's a great film, and it's based on the equally great book by Sylvia Nasar,"A Beautiful Mind." And he struggled with mental illness through his life and the film, you know, addresses and discusses those challenges. But he managed to extend the idea of an equilibrium so that it would hold not just in two player zero some games, but in multiplayer non-zero sum games. So the prison's dilemma is a non-zero sum game because the sum of the outcomes is not always zero and it varies according to the strategies. And he showed that there's always something which is been come to be known as the Nash equilibrium. There's always an equilibrium position where no one player can improve the outcome by unilaterally changing strategy. If a whole bunch of people change their strategy, maybe you can, but nobody can unilaterally change their strategy and improve what their outcome will be. So that's a really huge generalization and a really important result in game theory. So this now brings us to our second little puzzle of the best coffee in town. And again, you have to put some numbers into these things, but suppose you have. In this little town, there are two coffee shops that both sell the best coffee in town, and there are 400 locals who will go in and who will know what price is being charged and will remember, and if someone's charging too much, they'll go to the other cafe. But there are also 200 tourists who, you know, they visit once, they pick at random to have the best coffee in town here or here. And so they're not going to be... You know, they might grumble if it's a high price, but they'll have the coffee, but then you'll never see 'em again. So those, that you can perhaps weather a higher price for those people but not for the locals. And you can work out a table, just like for the prisoner's dilemma, only this time it's coffee. So here I've got, you know, cafe A is charging... Could they charge three pounds or four pounds? Cafe B, same thing. So that decision making process, I'm not going into the details, but, you know, all of the locals will go, if somebody's cheaper, the locals will gravitate there. So if they're both charging the same price, three pounds, then there are 600 people, they've got 300 each, so they each make 900 pounds. If they both charge four pounds, again, captive audience, they're both going to make four lots of 300, so 1200. But if they've got this higher price and if somebody lowers their price, then suddenly they get, all the locals will switch to them so their profit will go up. So you can think about, you know, the various examples, you could have multiple different prices, many cafes. But this example here is not a zero sum game because the total amount made is not a constant thing. But there is an equilibrium here and the equilibrium is that... It's this top left. So because in this situation, if A for instance changes their strategy, so they move to this, the higher price, their profit goes down to 400 and profit for B goes up and the same for B. So neither of them can raise their prices unilaterally without having a worse outcome. But if they both were to do it, then they both improve their outcome. So again, cooperation, collusion to think about. So this work was so influential, the work of Nash and others who have extended his work, was so influential that three game theorists shared the Nobel Prize, including Nash in 1994. And there have been other Nobel prizes for economics that have been won by game theorists. And in particular, in 2020, very recently the prize was shared by two game theorists who worked on auctions. So I want to talk about auctions now. And auctions, the first thing to say is there are lots of different kinds of auction, and the one we perhaps have in our mind with a, you know, a very expensive painting being sold, that's called an English open auction. So this style of auction is called English. So it's an open auction, so everyone's there, they know what the bids are and it's ascending, the prices are going up and they go up and up and up until all the other bidders drop out and there's just one person left, and then that person will win the auction, they'll get the item. There's another kind of open auction which is often called a Dutch auction. It's because it's often used Dutch flower selling auctions, hence the tulips, and that one, the price is set at the beginning extremely high, higher than anyone would ever pay. A million pounds, whatever. And then it comes down incrementally until somebody bites and says, I'll have that thing. So that's a descending open auction. Now these envelopes here are representing sealed bid auctions. So these happen, for instance, quite often in Scotland, houses are sold this way, a sealed bid. So everyone puts in their bid for what they think they will pay for this house, and then, you know, when that process finishes, all the envelopes are opened and whatever the highest offer is, they get the house and they pay that amount that they've bid. There is a variant of a sealed bid auction which is called a second price sealed bid auction. It feels counterintuitive that this is a good idea, but I think it is. In this type of auction, it's a sealed bid, nobody knows what anyone else is bidding. You'll put your bids in, and the item goes to the highest bidder, but the price they pay for it is the amount of the second highest bid. So that feels odd. (chuckles) We'll discuss about why that might be a good thing, you know, in a little bit. So there are loads of applications of the mathematics of game theory to this kind of situation, loads of strategies you might want to know about. What should I bid? How should I design my auction to sell my thing for the highest price? If I want to get an item in an auction, what should my bidding strategy be? So just, I'll give you a couple of examples of these, and the first one is setting a reserve price. So in, say, an English auction that the typical one that we sort of feel that we know. Sometimes there'll be a reserve price, and that's where the person selling the object says, okay, I'm not going to sell it if I don't make at least this much money. So, you know, I've got this thing and I think it's worth a million pounds but I won't sell for under half a million pounds. So if the bidding does not get that high, then the item is not sold, and that's the end of it. And this is to prevent a situation where maybe there's very few bidders on the day and so, you know, worst case maybe you just have one bidder and then they could buy it for a pound and you don't want to do that. So it's quite often there'll be a reserve price. So what we want to know is what should we set that price at? What's the best reserve price in order to maximize the revenue that you are going to get from selling your thing? So to analyze this problem, the first step is to say, actually we can reduce this to assuming there's just a single bidder, which, again, why would that be okay? Intuitively the reason is that you can kind of coalesce all the bidders into one and really the thing you care about is the highest bid amongst that collection of people that would be made,'cause that's the thing that ultimately is going to govern what happens. So we'll say, we'll just pretend we have a single bidder that's really like, you know, an amalgamated collection of bidders. So now we'll say we have a single bidder and we don't know what they've got in their mind as the maximum price that they will be prepared to bid. Let's say, we've sort of understood previous auctions and we think that the highest price you could get for something like this is a hundred pounds, whatever this object is. So we are going to say that their maximum bid is going to be somewhere in the range zero to a hundred. Now have to think about what money are we actually going to get, what's our revenue going to be? Well, they're not going to pay more than they have to pay. So if their maximum bid is a hundred pounds, but your reserve price is 10 pounds, they're not going to bid a hundred pounds, they're going to bid 10 pounds. They'll get it for the smallest amount they can. So if that x, which we don't know, is equal or higher than the reserve price that you have set, then you will sell your item for the reserve price'cause they're not going to go above that unnecessarily. If this maximum bid is lower than your reserve price, then your revenue is zero'cause you're not going to sell the thing. So you can work out, again, it's sort of probabilistic, but you are expected revenue based on this, and, you know, a very simple graph there. It's bidding on the x-axis, your bid is x, and the revenue that the seller will make is on the y-axis. So if the maximum bid anyone's prepared to make is less than the reserve, your revenue is zero, if it's bigger than the reserve, then your revenue will be R, the reserve price. And to work out the expected revenue then, basically you want to average all of the revenues you get for these different values over a hundred, which is a hundred, you know, you're going from zero to a hundred. How do you do this? Well, it's basically going to be the area under the graph here divided by a hundred. So what is the area? Well, you've got this rectangle, and the width of the rectangle is a hundred minus R and the height is R. So your expected revenue, your sort of on average revenue will be this amount, it's R times a hundred minus R, which is the area of that rectangle, and then you're averaging out so over a hundred. So that's the expected revenue for that particular reserve price. And what we want to know is, what should I set that reserve price to be at to maximize this number? So there are various ways to attack this and depending on kind of what stage you are at, so you can do it with calculus, you can, you know, you can differentiate respect to R, if that means anything to you, then good do that, if that doesn't, then there are other ways of doing it. You can complete the square or you can draw a picture. So here's a picture, in this plotting, the value of R, the revenue, against the expected, sorry, the value of the reserve, both things begin with R that's very annoying. The value of the reserve R and then against the expected revenue. And you can see very clearly that, I mean, this is an upturn parabola and the highest value is attained when the reserve price is 50. So that's what mathematics tells you, you should do, you should set the reserve price to be half the maximum possible value you might get. So that's one example. From the other viewpoint, if we are bidding at an auction, we can ask what's the best bid? Oh, I've said that there. What's the best bid? And there have been different types of auctions, there'll be a different calculation to do. I won't go into the details, but the mathematics around the best bid for a first price sealed bid auction, you all put in a bid secretly and the highest one wins it and pays out whatever they bid. A similar kind of calculation like the reserve price says, what you should do is bid half what your maximum value that you think that the object has. But there's a risk with these kinds of auctions, with the first price auction, and it's to do with how we value things. Now some things, everyone could legitimately have a different feeling of what it's worth. If you are a collector of something, and I don't know, there are 200 different types of, I don't know, this stamp or whatever, and you've got 199 of them and there's the 200th, you will put a very high value on that. Your own private valuation of that will be very high, much higher than someone who's just started collecting stamps, doesn't sort of care, they just want a stamp. They're not going to value that particular one very high. So in that case, people might legitimately bid very different amounts and still be very happy to win the auction if it comes in at something that's like the value they put on it. Another kind of item or something that can be auctioned will have a value that everyone will agree in common. But we don't necessarily know what that value is, a common value, but we don't know what it is. For example, drilling rights or something like this, you know, rights to drill on a particular oil field, everyone will have a... There will be a value for that depending on how much oil is there, and you can try and estimate that with geological surveys or something like this and everyone will do their own survey and you're all making an estimate. There's uncertainty about what the true value is, but there is a true value. And the problem there is that you are at the risk of the winner's curse, which is if you win against 50 other people and you're like,"Oh, all their valuations must have come in less than mine. So, you know, I must have overbid, my valuation must have been wrong." So even if you win, you then doubt yourself and perhaps aren't happy. So in this situation, it's really tricky, like if you win, there's always that risk of not being happy. If everyone has a private value, then you don't know what others are valuing something at. So example, suppose you are a furniture dealer, you see there's a broken lamp, you know that you can fix it'cause you've got the skills to do it and then you'd be able to sell it for a hundred pounds. So your private value would be a hundred pounds for that thing. What should you bid? You shouldn't bid a hundred pounds because then you make no profit on it. But what should you bid? And the same sort of mathematics as we just used for the reserve price tells you that actually you should bid 50 pounds and that balances out, I won't go into the details, but it's a very similar calculation, it balances out the kind of the risk between if you bid too low, you're unlikely to actually get it, if you bid too high, you don't get very much profit. So in that scenario you should bid half what you actually value the thing at. And sometimes you won't get it, but at least you won't lose out. Now the other kind of auction, the sealed bid auction, which is sometimes called Vickrey auctions because the economist, William Vickrey, studied them and wrote about them. In this case, your winning bid gets you the item, but the price you pay is whatever the second highest bidder contributed. Now these feel a bit odd, but they are actually pretty close to what would happen in an open auction because in an open auction, if you think we get down to a point where there's two bidders left, and at some point, you know, one of them said, okay, I'm not going any higher. If we're at that point, then you can just add like one penny to their maximum bid and win the item. So what you end up paying there is not your maximum bid, but their maximum bid plus a tiny teeny bit. So that's exactly what's mimicked really in this second price seal bid. You can put your true valuation, in that case, that's actually the best strategy. You should bid your valuation because the amount you end up actually paying will be the second bidders maximum, so you're not sort of going to pay more than you need to in that situation. And in this case then you should bid your valuation because yes, if you bid more than your valuation, there's a risk, someone comes in just like less than that, then you have to pay that amount, which is more than you think. So you'd be annoyed, you've overpaid. If you bid less than your valuation, maybe bid 90 pounds, then there's a risk someone comes in and bids 95 pounds, then you don't get the item and you wish you had. So you should bid your exact valuation, but the amount you are going to pay, if you think we don't know what any of these other people... We have no idea what the other people are bidding, it's a silent sealed bid auction, so without any further information, you know, the other person, if your valuation is a hundred pounds, the expected value that you would have to put on that is kind of a randomly chosen number between zero and a hundred, and so the expected value of that number is 50, and so they would, kind of on average. So what you actually end up paying, the expected amount would be 50 pounds. So actually in both of these cases you ended up paying 50 pounds, you got to it from a different route. And it's actually a curious fact of auction theory that we have the revenue equivalence theorem that says, the theoretical expected revenue, so not the maximum bid, but the actual amount paid, is the same in all of these auction types. Theoretical is an important word there. It turns out to be half the highest valuation which we've seen in those two examples. Of course, real life has complications. For example, the biggest one is people tend to have budgets. So even if I think this thing is worth a million pounds, I may not have a million pounds to pay. So that will obviously affect strategies. But in principle these are the same kind of thing. Now designing auctions and the right strategies has been very, very fruitful for governments that have asked mathematicians and game theorists for help with this. And there's just one example. So I put this very old phone to illustrate the fact that this happened in the year 2000 when phones barely existed. So at this point, so we're on 5G now, but at this point it was 3G was the exciting new thing, and the government, the UK government was auctioning off 3G airspace. I guess, for want a better word. And they've had five licenses for it, and they wanted to have five different people having each license. So they did this auction with series of bids and the first round everyone could make a bid on exactly one license. And then they looked at which ones were the top bids, and for those five companies could not then make another bid in the second round, they had to just stick with that. Everyone else could choose either to drop out or to increase exactly one of those top bids and then repeat. You know, people would drop out and you carry on until you have exactly five people left, five bidders left, and by construction they currently hold the top bids on five different licenses. So this was designed very carefully, they had did a lot of mathematical modeling on the possible things, and it raised gigantically more than any other telecom's auction before it. It raised 22 and a half billion pounds, which you know, is good for the ex-checker, and this is kind of the power of using mathematics to design your auctions. So in the few minutes we have remaining, I want to talk about a final question and it's about houses. Well, it's sort of, it could be about houses. This is one of the scenarios in which what I'm about to say can be relevant. So if you're thinking about in various times in our life, maybe one day we are lucky enough to be able to buy a house. But actually a situation that's upmost in my mind is, for example, if you're a student, you go to university and you have to rent accommodation, you have to rent a house with some of your friends. The market for that is very rapidly moving. You go round, you look at places, everyone else is also going around and looking at places. So if you see a place and you like it, but you don't make a decision quickly, the thing is, if you go back next day and say, well, actually I did like that, it'll already be gone. So in that kind of market, and renting houses is this one example. Really, you see something and you have to decide yes or no to it, kind of there and then, and you can't go back and change your mind subsequently. And so you can think, what's my strategy here? I'll see some houses and at some point I have to say, okay, this one is okay, I'm going to choose this one. Even though you haven't seen all the possible houses because, you know, there's more that you could see. So you think about, okay, maybe I'm going to see, you know, three houses every day for up to a week, that's how long I've got to find this house to rent. So maybe I'm going to be able to see up to, let's say, 20 houses, I'll see some and then I'm going to have to make a decision, and when should I do that? So the idea is if you don't see any at all and then just take the first house, that's unlikely, you're not going to know what's out there. So a good strategy will be to view some houses, a sample, let's say, s houses, out of the potential, we said 20, but let's say n, you know, we're mathematicians. And then, so you're looking at some just to gauge what's out there, you're not going to take any of them. And then after that point, after your initial sample, you are then going to take the next house that's the best so far, if that happens. I mean, there's a chance you'll already have seen the best house, it was your first house, then this strategy won't work. But that's what the strategy's going to be. So you view some sample number of houses, then beyond that point, if the house you're looking at right now is the best one so far, you take it, that's the strategy, at least for that point, you are happy that you've got the best one so far. If you took while, and take the second best, you're always a bit sad, you dunno what's out there left. So it's a tricky challenge. So let's try this out with a very small total number of houses. Now you've only got one day, you can only see three houses. So what sample size should you have? How many should you view and reject automatically before you start really making a decision? So we'll have three houses. So you could have a sample size of zero or you're not looking at any, and then you start doing the strategy, which is, for any house, we're going to take it if it's the best we've seen so far. Well, if you don't look at any, then the first house is going to be the best you've seen so far, so you'll take it. But I mean, I guess we assume that these houses, these n houses do have... We could all put them in an order best to worst and that they're randomly seen in random order. So you don't know that any one house has a kind of one in n or one in three chance of being the best one. If you didn't have any in your sample size, you're going to choose the first house, success rate one in three, 33% chance of being the actually best house. If you have a sample size of one that means you view the first house, reject it automatically. And then you look at house number two, is it better than house number one? If so, I take it, if not, reject it, move on to house three. Now, each possible way in which the houses could be arranged and we'll have to look at each one, if we're just assuming it's all random, has a one in six chance of occurring each ordering. So if house one is the best, it could go one, two, three, or one, three, two, if house one is the best, that's bad news for us cause we reject it automatically. So our strategy fails in that case to choose the best house for us. If house two is the best, that's great. We've rejected house one automatically, house two is the next one we see, it's definitely better than house one and it's the best overall. So we choose it and it's the best, success. House three, if house three is the best, then if the ordering goes like this, best is three, worst is two, then that's good because we see house one reject it, house two is worse than house one, we reject it as well, and then we see house three and it's the best so we pick it, success. But if house two is better than house one, then we would take it, we'd sort of peak too soon, we wouldn't even look at house three. So that would be a failure. So of those six possibilities, three of them result in success. So it's a 50% success rate. So a sample size of one is looking better than a sample size of zero, and a sample size of two adds too many'cause you reject house one and two automatically. And then you move on to house three, you're only going to be able to choose it if it's better than both of those things where there's a one in three chance of that. So in this case, with just three houses, the best strategy is to sample a third of them, one house, and then you choose after that point, the best one so far, if that happens. So you can try this for bigger numbers. So if you have five houses, it turns out the best sample size is two, which is 40% of the sample. If there are eight houses, you move up to looking at three houses. You can just do all these calculations, and that's 37.5% of sample size. I mean, these numbers are sort of moving up and down a bit, these are small numbers. As you increase the total number of houses, the best sample size as a percentage seems to settle on a particular number. And so, I've done this for a large number, here's another graph. So this is if we have a thousand houses to look at, hopefully that would never happen, and the sample size is on the x-axis going from zero to a thousand, and then the likelihood of success is on the y-axis. And you can see that there's a maximum and it's about sort of 370 houses somewhere around that point. And this is sort of generally it's tending to some, converging on some number, and that number is viewing 36.79% of the total number of objects. Now, what on earth, that's not a very nice number, 36.79. If I express it in a slightly different way, you can look at the fraction. So the best sample fraction of these three things, little low numbers, one in three, one in 2.5, one in 2.7, for large n, one in 2.718. Now there may be, I think that's... Again, depending on what stage of your mathematical knowledge you're at, you might recognize 2.718. It's an approximation to the very, very important mathematical constant called E, which you will encounter at some point in your mathematical career if you haven't already. The best sample size turns out to be one over E of the total. Now this is a nice little fact, it's a lovely fact. Also, this sort of idea is not just for house buying, you can also use it for love. Think about your dating strategy, I'm sure you will have one. You might think, okay, I'm going to want to settle down at some point, you might work out how many people you might potentially date in a life of dating. Well, if I want to be settled down by the age of 30, let's say, and maybe I'll have 10 years of dating and maybe I'll have, I don't know, two people I might date in a year or something like this. So maybe you have up to 20 candidates for the one during a potential dating life, just to pick some random numbers. And so, now you know what you should do, is you should date seven people with absolutely no intention of settling down with them just to see what the market's like. And then after that point, you should settle down with the best ones so far. Okay, so dating advice from your Gresham professor. So lots of these things can appear in lots of different situations. I hope you've enjoyed a little mathematical tour of the mathematics of games, and you could see these ideas can be relevant in many, many places. I will just flag up my next lecture which is on the 31st of January, lottery winning mathematics. So I hope to see you all there, but for the moment, thank you very much.(audience applauding)- Thank you so much, Professor Hart. We don't have a lot of time for questions, so can we start with one online and then take one in the room? We've got a question here about your auction slides from earlier. And he says, this might be answered in due course, but would second bid plus one or some value between the top two be better? Surely, yes, for the seller, and not so bad for the buyer?- Well, yes. So this kind of thing where I said it's quite like the open auction because you can bid a tiny little bit more than the second person who drops out at the last minute. So potentially you could tweak that and say, yeah, actually we'll take the average or something like this. But that, yeah, I don't think it would make the underlying mathematics very different. It might be like, well, you know, maybe 1% or something 10% of the value would please the seller and not be so bad for the buyer. Yeah.- [Audience Member] Is the calculation for the Colin and Rose example suitable for large number of outcomes? Or is it limited to only the three outcomes of win, draw, or lose? And does the zero sum game only include numbers one, plus one, or minus one, or is there ever a plus two, minus two? Or if there were separate outcomes, do they count within the total possibility of plus one and minus one?- So you could have more complicated setups, you could have a range of different outcomes. And in fact, yeah, the goal scoring was kind of really plus one and zero, you could argue. As long as it adds up to zero or even if it adds up to a constant amount, then that's okay. So you could have plus two, minus two, as long as if I get plus two you get minus two. So as long as it, you know, the sum is zero still, then it still can be amenable to that kind of analysis. But yeah, there are much more complicated examples you could use. But I didn't want to put a hundred by hundred diagram on a slide. So yes, yeah, you can extend these in many ways, yeah.- Thanks so much.(audience applauding)