- 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)
