Did you pick up on those poker champions beaten hands-down by an artificial intelligence program? That was in early 2017, and behind that accomplishment lies a little-known (to the general public, at least) field of mathematics called game theory. Contrary to what the name implies, game theory impinges on a wide range of fields, from computing to biology and the economy. Mikael Touati, an Orange research engineer in economic modelling and agent plays, gives us some pointers.
What is game theory?
It’s a field of mathematics that has been growing since the 1950s. What we call a “game” is an interaction situation where participants take decisions that impact others. Depending on the context, and on whether participants are acting simultaneously or sequentially, and according to the possibilities offered to them or what they know or don’t know about the situation or the other participants, they will make different choices. By taking all those parameters into account, the theory seeks to understand what will influence those decisions, and what results they may lead to. We try to understand the mechanisms of a given situation, just as we would try to understand the mechanisms of a game.
Could you describe an example of a game for us?
The stable marriage problem is a classic theoretical problem that was solved back in 1962 and gave rise to a great many research projects. It asks the following question: if you take a group of individuals, is it possible to marry the men and women in it so that nobody will want to divorce? We look for a stable manner of linking them up according to their expectations so that each woman and each man will prefer to stick by their present spouse rather than being single or with someone else. We are talking here about men and women, but in practical cases, these “couples” correspond to individuals belonging to two distinct groups, for example students and universities, doctors and hospitals, and even mobile phones and radio masts.
What are some of the real-world applications of game theory?
For the stable marriage example, we can talk about admission systems in some colleges and universities in the United States: the students express several choices, ranked by order of preference, when submitting their applications to the schools. On the basis of their records and interviews, the schools also have their own preferences. Finally, a matching mechanism is used to enable the recruitment. But a difficulty was flagged up in the 1980-1990s in that some participants could manipulate the results by selecting choices different from their real preferences in order to boost their chances of being admitted to their preferred school. Others began to circumvent the system and to finalise recruitments between themselves! The marriage game made it possible to re-think the mechanism to avoid this type of problem. But that’s only one example among many others, because game theory covers an incredible number of subjects and fields of application. It is widely used in economics but also touches on biology in the field of evolutionary theory, computing, and political science.
Why is a group like Orange interested in game theory?
In the field of economics, game theory is a way of studying competition mechanisms between different players, such as competing carriers. Orange is also interested in the emergence of marketplaces. These are places where people exchange goods and services among themselves: you have interaction and decision-taking, but these are very different when it comes to a service like Airbnb or an auction site like eBay. So you have to decide how the interactions organise themselves – who gets what, who pays for the service – in short, on what mechanism will you base your decision to create the platform?
Game theory is even used in network design, to overcome congestion problems, for example: when several people want to connect to a site, there must be sufficient resources available, otherwise users will suffer slowdowns. The people are not interacting among themselves, they don’t know who is on the network at the same time as them, and yet the quality of their connection depends on the choices made by others.
Is artificial intelligence opening up new vistas for game theory?
Deep learning is a field where game theory is destined for a brilliant future. Today, machines learn from past occurrences, draw conclusions and replay the situation, see what could have been different, and take their decisions on the basis of future potential. In some cases, they also interact with and influence each other. To imagine and understand these situations, you need to combine deep learning and game theory. Game theory is a powerful tool. That said, we must not use it naively or abusively. The solution may be complex and while we can programme machines to ensure they adopt selected behaviours, humans and reality are still difficult to model.