My favorite game theoric concepts and impossibility theorems

Game theory is the name given to the methodology of using mathematical tools to model and analyze situations of interactive decision making. It is thus an incredible powerful tool to (i) predict the behavior of several decision makers and (ii) provide decision makers with suggestions regarding ways in which they can achieve their goals. Starting with this basic definition, the reader probably has his head in a twist now as the number of possible applications of this incredible tool are numerous, not to say infinite.

In this blog post, I give my favorite game theoric concepts and resulting impossibility theorems that are particularly mind-blowing. As a consequent game theorist, I classify my concepts because having a ranking of one’s preferences is always necessary to build your utility function, super useful in everyday life I swear! Anyway let’s dive in !

1st place: social choice theory

Definitions

Social choice theory is the study of the question of how to aggregate the preferences of a group of individuals into a single ‘social preference’.

It is arguably a kind of branch of game theory that adopts in my view the most interesting methodology: the axiomatic approach. It is an inevitably normative approach. Typically social choice studies situations where one is confronted with a social problem (eg sharing a resource/common good/cost due to the use of a common good). The modeller attempts to design a collection of logically independent properties (called axioms) that are considered desirable (in an ethical sense). The modeller then finds a solution to the problem (e.g. an allocation rule), which must satisfy the above properties, and characterises the set of solutions satisfying these properties. This is precisely what makes social choice absolutely incredible: one cannot escape a political reflection on the type of social choice criteria to adopt.

The funny thing about the axiomatic approach is that it can be understood from both a consequentialist and deontological point of view! Indeed, the modeller seeks to ensure that his solution satisfies certain desirable properties and is therefore directly interested in the consequences that his solution will have from a collective point of view. The axiomatic method can also be understood from a deontological perspective since the modeller is quite free to choose a certain combination of axioms that he or she deems morally good (or not, for that matter) from a very arbitrary point of view without any necessary consequentialist consideration as long as a solution can satisfy all these different axioms at once.

To construct a choice function that associates every strict preference profile of individual preference relations with a social preference relation, we asked what properties such a function should satisfy. Surprisingly, this led game theorists to conclude that if there are at least three alternatives, seemingly natural and reasonable properties cannot hold unless the choice function is dictatorial! Social choice is the branch par excellence of game theory that formulates super badass impossibility theorems.

Main results and figures

Arrow’s impossibility theorem <3
Gibbart-Satterthwaite’s impossibility theorem
Condorcet’s paradox
Other interesting stuff in voting theory (e.g. aproval voting)

2nd place: decision theory

Definitions

Decision theory is a field who analyzes the reasons and how individuals make their choice. A lot of people seem to confuse this concept with basically game theory more broadly so let me be more precise here:
DT: involves a single decision maker, and for which the single decision is the only focus.
GT: try to predict the behavior of individuals who are involved in a situation together.

The basis of decision theory is to define what economists call a preference relation. As I had already briefly explained in my blog post on rationality in economics, a preference relation must satisfy certain intuituve mathematical axioms to be called rational. We can then construct a utility function representation of preference relations over certain outcomes. It was named after the founding work of von Neumann and Morgenstern. One key feature of this utility function is that it is linear in the probabilities of the outcomes, meaning that the decision maker evaluates an uncertain outcome by its expected utility. To have the honour that your preference relation can be represented by a utility function in the sense of von Neumann Morgenstern, the latter must however satisfy certain mathematical properties (be rationnal and satisfies the von-Neumann Morgenstern axioms).

Suggestions and extensions

However as I previously discussed in my previous blog post, the completeness axiom is a strong assumption because it means that you are always able to classify with 100% certainty any alternative between them. Agents that are not completely sure of the right thing to do/choose between two or several alternatives - which I believe is an accurate summary of the state of knowledge about ethics, both because of normative impossibility theorems (e.g the repugnant conclusion), and the practical difficulty of predicting the consequences of actions – are thus a bit stuck. To better take into account this (moral) uncertainty, one could imagine that preferences are partially ordered (rather than totally ordered in the mathematical sense of it) or are represented by probability distributions over total orders !

What is fun about decision theory is that most EAs heard about decision theory trough Newcomb’s paradox whereas it is not discuss at all in any decision theory course at the university. It is because decision theory is often the first thing to look at and then move on to game theory, which makes full use of this concept of utility function and maximising expected utility since the rational decision in economic theory is always to maximise one’s expected utility, whereas one could very well imagine that a rational decision can be defined in another way (cf. EDT vs CDT theory, timeless decision theory etc.).

3rd place: mechanism design

Well it is great if everyone is super nice and have a rationnal preference relation but what if you’re super smart and realise that you can fool the other ones about your preferences in order to reach your goals more easily ? Mechanism design assumes that agents want to maximize their individual preferences and therefore can have an incentive to misrepresent preferences. A key question in mechanism design is whether an economic mechanisms can implement a social choice function under some game-theoretical solution concept if agents are self-interested, their preferences are private information, and they want to maximize their payoff. The informed reader will easily recognise that mechanism design problems can therefore be modelled using Bayesian games (from the basis of non-cooperative game theory, which is easily accessible).

4th place : network games

One of the assumptions underlying all the situations we have discussed so far is that all players know each other from the start and are likely to interact with each other according to rules that we have mostly assumed to be common knowledge. What happens if we now remove this assumption? What if, for example, entering into relationships with others can be beneficial to everyone but also comes at a ‘cost’? To ask this question is to enter the world of strategic network formation and graph theory. Graph theory is a super fun mathematical concept we do not study that much in an economics degree ! That’s a pitty. Anyway physicists are here to save the honnor (I refer here to the following book).

References

The best game theory textbook for me is “Game Theory” by M. Mashler, E. Solan and S. Zamir (second edition). It is a rather academic book but the exercises are varied to understand and have the basics of both cooperative and non-cooperative game theory. I’ve seen too few game theory textbooks that fully integrate the cooperative part and this one is one of them (7 chapters dedicated exclusively to that!) so go for it! The only thing missing is a chapter on mechanism design… Otherwise for another textbook I also recommend “Strategy: An Introduction to Game Theory” by Watson.
For a chill Sunday read I highly recommend to my French readers “La théorie des jeux” by Gael Giraud which gives very concrete examples, is very pleasant to read and is not extremely formalized mathematically for those who like it.
Concerning ytb videos :

• the beautiful playlist « La démocratie vue sous l’angle de la théorie des jeux » from Science4All
• youtube channel of Selcuk Ozyurt and William Spaniel

If you want to buy me a gift:

• Set functions, Games and capacities in decision making (Michel Grabish, 2016)
• Econophysics and Economics of Games, Social Choices and Quantitative Techniques (Banasri Basu, 2009)
• The Complex Networks of Economic Interactions : Essays in Agent-Based Economics and Econophysics (Akira Namatame, Taisei Kaizouji, Yuuji Aruka, 2005)
• Flowers and chocolates work as well