8,39 €
Mehr erfahren.
- Herausgeber: Icon Books
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
- Veröffentlichungsjahr: 2022
Brian Clegg was always fascinated by Isaac Asimov's classic Foundation series of books, in which the future is predicted using sophisticated mathematical modelling of human psychology and behaviour. Only much later did he realise that Asimov's 'psychohistory' had a real-world equivalent: Game Theory. Originating in the study of probabilistic gambling games that depend on a random source - the throw of a dice or the toss of a coin - Game Theory soon came to be applied to human interactions: essentially, what was the best strategy to win, whatever you were doing? Its mathematical techniques have been applied, with varying degrees of wisdom, to fields such as economics, evolution, and questions such as how to win a nuclear war. Clegg delves into Game Theory's colourful history and significant findings, and shows what we can all learn from this oft-misunderstood field of study.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Ähnliche
i
Hot Science is a series exploring the cutting edge of science and technology. With topics from big data to rewilding, dark matter to gene editing, these are books for popular science readers who like to go that little bit deeper …
AVAILABLE NOW AND COMING SOON:
Destination Mars: The Story of Our Quest to Conquer the Red Planet
Big Data: How the Information Revolution is Transforming Our Lives
Gravitational Waves: How Einstein’s Spacetime Ripples Reveal the Secrets of the Universe
The Graphene Revolution: The Weird Science of the Ultrathin
CERN and the Higgs Boson: The Global Quest for the Building Blocks of Reality
Cosmic Impact: Understanding the Threat to Earth from Asteroids and Comets
Artificial Intelligence: Modern Magic or Dangerous Future?
Astrobiology: The Search for Life Elsewhere in the Universeii
Dark Matter & Dark Energy: The Hidden 95% of the Universe
Outbreaks & Epidemics: Battling Infection From Measles to Coronavirus
Rewilding: The Radical New Science of Ecological Recovery
Hacking the Code of Life: How Gene Editing Will Rewrite Our Futures
Origins of the Universe: The Cosmic Microwave Background and the Search for Quantum Gravity
Behavioural Economics: Psychology, Neuroscience, and the Human Side of Economics
Quantum Computing: The Transformative Technology of the Qubit Revolution
The Space Business: From Hotels in Orbit to Mining the Moon – How Private Enterprise is Transforming Space
Game Theory: Understanding the Mathematics of Life
Hothouse Earth: An Inhabitant’s Guide
Hot Science series editor: Brian Clegg
v
GAME THEORY
UNDERSTANDING THE MATHEMATICS OF LIFE
Brian Clegg
vii
For Gillian, Chelsea and Rebecca
viiiixx
CONTENTS
ACKNOWLEDGEMENTS
Thanks to the staff at Icon Books, notably Duncan Heath and Robert Sharman. Many years ago, I took an MA in Operational Research at the University of Lancaster, which introduced me to some of the concepts of game theory. My thanks to the lecturers there, particularly Graham Rand, who is still involved with the university. He edits the operational research magazine Impact, for which I have written many articles, including one that led me to look more into auctions and game theory.xiv
1
GAMES AND THE REAL WORLD
When I first bought a textbook on game theory many years ago, never having come across the term before, I felt cheated. I was expecting something fun that would tell me the optimal strategies for winning at card games, backgammon and Monopoly. I wanted an interesting analysis of how the games worked mathematically under the hood. Ideally there would also be guidance on how to create your own interesting board games. Instead, I found descriptions of a series of ‘games’ that no one had ever played, with tables of outcomes that did not so much give guidance as show just how impossible it often was to come up with a useful outcome. This was interspersed with a hefty load of mathematical equations. And yet, the more I read about game theory, the closer it seemed to one of my favourite classics of science fiction.
For his 1950s Foundation series of books (made into a TV show in 2021), Isaac Asimov came up with the concept of ‘psychohistory’. This is an imaginary mathematical mechanism for predicting the future, based on an understanding of human psychology and the behaviour of masses 2of people. In practice, psychohistory was never going to happen. The repeated failures of pollsters who amass vast amounts of data to predict the outcomes of elections, or decisions such as the UK’s Brexit referendum, make it clear that people form far too complex a system to enable reliable mathematical predictions of outcomes. Yet game theory does achieve some of the promise of psychohistory by resorting to the classic approach used by science, particularly physics: modelling.
The mathematical models used in physics reduce complex systems to simpler combinations of objects and their interactions. Messy aspects of the system are often ignored (it will be noted that this is happening). So, for example, Newton’s familiar laws of motion at first glance don’t appear to describe the real world very well. The first law states that an object in motion will keep moving unless acted on by a force. In everyday experience, such countering forces – like friction and air resistance – are ubiquitous; yet for convenience, models often ignore such things, as they add complexity and can be difficult to account for. This means that the model does not reflect reality – without friction and air resistance, once you gave it a push, a ball on a flat surface would roll on for ever. But simplification makes calculations more manageable and gives an approximation to reality. Similarly, game theory uses mathematical models that simplify human interactions and decisions as much as is possible to help understand those processes.
The theory of games started with the development of the mathematical field of probability to deal with gambling games and other pastimes where the outcome was dependent on a random source, such as the throw of dice or the toss of a coin. However, in the first half of the twentieth century, a 3handful of individuals and a quasi-governmental American institution took some of the basic mathematics of games and began to apply it to decision-making problems, ranging from economics to the best strategy to win a nuclear war.
The field that was developed under the name of game theory became detached from ‘real’ games. It was all about strategy – what was the best approach to win, given a set of choices available to two or more players. Games were transformed from pastimes to something deadly serious. This shift was so strong that often those who deal with game theory totally ignore what the rest of the world calls games. However, I believe that this is a mistake. Real games still form part of the continuum – it is just that many familiar games are not interesting from a game theory perspective, either because they are too dependent on random chance, with no strategy, or because they are too complex for strategies to be developed.
It’s worth spending a moment on the ‘strategy’ word here, as it is often misused, and game theory has its own specialist meaning for the term. A strategy is a plan to achieve a goal. However, as J.D. Williams pointed out in his light-hearted 1960s book The Compleat Strategyst, in game theory, a strategy ‘designates any complete plan’. In general usage, a strategy is usually a best effort to achieve something. But in game theory, a strategy is any complete plan for playing the game, no matter how good or bad. In chess, for example, your strategy could be to always play the piece closest to the bottom left-hand corner of the board that is available to move. Such a strategy would pretty much guarantee losing, but it would nevertheless be a strategy in game theory terms.
Much early game theory was developed to deal with situations where two players went head-to-head in an 4aggressive win-or-lose situation. This was the circumstance, for example, facing American military strategists when applying game theory to nuclear warfare and whether it was better to be reactive or pre-emptive when it came to nuclear strikes (arguably more a lose-lose scenario than win-or-lose). However, the most valuable impact of game theory in recent years has been in the design of specialist mechanisms to deal with spectrum auctions.
Selling a spectrum
The word ‘spectrum’ suggests that these auctions are something to do with selling off an array of colours, but here a different part of the electromagnetic spectrum is under consideration: not visible light, but the segment of radio frequencies available for, usually, mobile phones and wi-fi.
Historically, radio bandwidth was primarily used for broadcast radio and TV, with a relatively small number of transmitters sending signals to many receivers. Because of overlaps between different transmitters and applications, and because of the crude technology originally used, wide swathes of the radio bandwidth were allocated to broadcasters.
The exact definition of radio is a loose one. The electromagnetic spectrum is divided up by frequency or wavelength. Wavelength is the distance between equivalent points in the repeating cycles along the progress of a wave. Frequency is the number of such complete cycles of the wave that take place in a second.
Frequencies on the entire electromagnetic spectrum – which includes radio, microwaves, infrared, visible light, ultraviolet, X-rays and gamma rays – vary from a handful of 5hertz (cycles per second) through to hundreds of exahertz, where an exahertz is a million trillion hertz. The equivalent wavelengths run from hundreds of thousands of kilometres to picometres (trillionths of a metre).
Figure 1.1. Structure of a wave.
Radio comes at the bottom end of the spectrum, with the lowest frequencies and longest wavelengths, at its highest reaching wavelengths of about 1cm and frequencies of hundreds of gigahertz (a gigahertz is a billion hertz), though signals at the top end of the radio range are often referred to as microwaves, first employed for communications and radar, but now also used in the eponymous ovens.
What has transformed the need to squeeze every bit out of the radio spectrum is the growth of two applications – cellular phones and wireless internet. Worldwide cell phone ownership has risen dramatically. In the mid-1990s, around 5 per cent of the world’s population had access to a cell phone. By 2015, the 100 per cent mark had been passed. It might seem that only sportspeople and competitors in TV game shows claim to be able to give more than 100 per cent, 6but this value reflects the fact that in many countries today there are more cellular subscriptions than there are members of the population, both from owners of multiple phones and devices other than phones that use cellular data.
More recently, the use of wi-fi to connect devices to the internet has become ubiquitous, while those multitudinous cell phones continue to eat up more and more bandwidth of the radio spectrum. Bandwidth describes the range of frequencies or wavelengths that a radio broadcast uses. The more data a device needs to access, the greater the bandwidth. As smartphone technology has transformed cell phones from being simple communication devices to powerful pocket computers, they are starting to use the high-bandwidth flows of data needed to stream videos and perform other data-intensive tasks. This requirement has seen a rapid transition through 3G (third generation) and 4G connections, with 5G now becoming available, providing data rates that had previously only been possible through fixed fibre-optic connections.
At the same time, television, one of our biggest historical consumers of radio bandwidth, is undergoing a two-part revolution. The first change was from analogue to digital. Digital channels take up a lot less bandwidth than their analogue equivalents, because the data is compressed before transmitting it, making it possible to free up more frequencies for mobile data access. The other stage of television’s transformation, which is only just starting to have a major effect but will transform TV viewing forever, is the move from broadcasting to streaming. Already, a percentage of the population watch most of their TV over the internet. In time, all TV will be watched this way and the bandwidth occupied by TV will be released.7
Monetising bandwidth
An example of the process of transferring parts of the TV spectrum to mobile usage in America gives a dramatic portrayal of the way that game theory has come to play a major role in what can be a very lucrative process for governments.
In 2017, the US Federal Communications Commission (FCC), which regulates US telecommunications, realised there was an opportunity to reshuffle many TV stations’ frequencies, freeing up bandwidth for mobile data. Specifically, they looked at the top end of the 600 MHz TV band, traditionally known as UHF (ultra-high frequency). This proved a particularly useful segment of bandwidth as it was adjacent in the spectrum to existing mobile phone bands, has good range and is effective at penetrating the walls of buildings, which is something of an essential for mobile signals.
The technical teams responsible for making this happen had two challenges: ensuring that the requirements for TV signals were still covered, though potentially on different frequencies; and getting the most money from the telecoms providers who wanted licences to use more of the available bandwidth for their customers.
The optimisation of the TV channel allocation made use of a sophisticated mathematical algorithm, but from the game theory viewpoint, the interesting part of the process was the mechanism for allocating licences to the mobile phone operators. The FCC would use an ancient mechanism for selling items among multiple competing interested parties, the auction – but with a new twist devised using game theory.
Remember that game theory is about more than playing traditional games – it’s a mechanism for designing strategies 8and for decision-making when taking on opponents. Taking part in an auction is exactly the kind of process that game theory was designed to handle: bidders are competitive ‘players’ in a game where the prizes are (in this case) access to bandwidth. How effective a strategy can be often depends on how much we know about the desires and strategies of our opponents. The degree of information available is crucial to the way the game plays out, and this has become central to the design of sophisticated auctions. Before seeing how this is done, it will be helpful to take a look at an apparently simple game that influenced the development of game theory – poker.
Information and games
If, like me, you aren’t a poker player, you may be surprised at the suggestion that poker is simple, because it can be tricky to remember the priority of the different hands. However, given those rules, the play is very straightforward – a hand with a higher value always wins.
Unlike most card games, poker has many different formats. In some, known as ‘draw poker’, the players’ cards are concealed. The only source of information a player has about the strength of the hands of his or her opponents is the way that the players bet and anything that can be deduced from their speech and body language. However, other formats, such as stud poker (where some of a player’s cards are dealt face up) and Texas hold ’em (where cards displayed on the table are included in every player’s hand), provide players with some information on what is available to their opponents.9
Imagine, though, that all cards in every hand were always visible. It wouldn’t be much of a game, as everyone would have perfect information on what the other players were holding and therefore would know exactly what they were likely to do (unless they were very silly). The level of information available has a strong influence on the ability of the players to develop appropriate strategies.
We tend to think of an auction as a marketplace, but its power is as a mechanism for sharing information. It exposes the preferences of players of the auction game (the bidders), showing how far they are inclined to go to gain a particular outcome. Unless they get carried away and become irrational, players of the game will not bid higher than they consider the item on sale to be worth. And this is crucial information, because initially no one knows what an object is worth. We are used to many things having a list price, but this is an arbitrary convention. In reality, something on sale is worth what someone is prepared to pay for it. With a list price, the vendor can only guess what that amount is and see if anyone will buy. But an auction is a vehicle for establishing what that value is among the community of game players.
In the 2017 US spectrum auction process, the gaming power of the auction would be used doubly, first on the TV companies and then on the mobile phone networks. The first phase was to use auctions to see what value TV companies put on releasing bandwidth. The companies were paid to free up some of their frequencies and move to new ones. This involved a kind of auction known as a reverse auction, where, unlike a conventional auction, there is a single buyer and multiple sellers. Each TV station was offered a tailored starting price. Robert Lees, director of the Smith Institute at Harwell, Oxfordshire, who was involved in the FCC process, 10noted: ‘Initial levels were set taking into account the coverage areas and coverage populations of each TV station. So, stations covering large areas of urban population would see high initial prices in the reverse auction. Another consideration was to set the prices at levels which would be sufficiently attractive to encourage high participation levels from the broadcasters.’
If a station accepted the offer, they stayed in the auction process. If they rejected it, they dropped out and could keep their existing bandwidth but had to move, without compensation, to a new channel (which would cost them money to undertake as they would need to change broadcasting equipment and retune customers’ TVs). In the next round, the prices were lowered and the process repeated. Eventually there would be no new channels left to move to. At this point, the auction stopped and the remaining stations were paid the offer at this level to give up their bandwidth, provided there was sufficient funding available to cover the offers.
When the required amount of bandwidth had been freed up, the second style of auction, a more conventional ‘forward’ auction was started between the FCC and the mobile networks. Sections of the freed-up bandwidth were given a starting price, and anyone prepared to pay the requested amount entered the auction. The amount then went up, with players dropping out as the pricing got too rich, until the bandwidth was allocated to the last player standing.
This wasn’t quite the end of the process, as it was possible that bidding would have dropped off too early to be able to fund the release of the TV channels. If this were the case, the auction would be abandoned and restarted with smaller units of bandwidth until a successful outcome was reached. 11There had been plenty of spectrum auctions before, but what was unique here was the two-way facing auctions. Mobile phone companies were familiar with the auction process, but it was new to the TV companies.
According to Robert Leese, ‘The FCC spent a great deal of time with [the TV companies] to make sure that they understood the process and that all their concerns were addressed. One key feature of the auction design was that participation for the broadcasters should be as easy as possible. They were never asked to select from more than three options at a time. Another key feature was that broadcasters were free to drop out of the process at any time (or not to participate in the first place), safe in the knowledge that they would not end up in a materially worse situation with regard to interference than their situation before the auction.’
Game theory was crucial to devising this auction design, as it is surprisingly easy to get auctions wrong. As we will discover in Chapter 6, by not anticipating the strategies of bidders, some spectrum auctions have been disasters. However, in the case of the 2017 FCC process, the auctions raised over $10 billion to be paid to the TV industry for the released bandwidth, as well as over $7 billion surplus for the government.
We will see how game theory got to this point in history – and how it has moved on thanks to the ability of computers to repeatedly play games – but to get into the basics of game theory, we need to travel back in time to the first mathematical explanations of games of chance.12
