2024 Optimization Days, (algorithmic) collusions in games

Tomorrow, I will attend the 2024 Optimization Days, in Montréal. I will present some work we did last Fall with Philipp Ratz and Suzie Grondin, on (algorithmic) collusions in games, “Market Pricing with Reinforcement Learning” (the paper will be available soon)

Several recent articles have attempted to gain a better understanding of algorithmic collusion (Calvano et al. (2020), Klein (2021), Banchio & Mantegazza (2022) Rocher et al. (2023)). For example, in Calvano et al. (2020), a simulation study showed that for a simplified market environment, basic Q-Learning Agents can learn to collude tacitly, in order to propose higher prices and increase their combined profit. Inspired by some Iterated Prisoners Dilemma, we derive some reinforcement learning algorithm to investigate and discuss several recent results and their robustness, and explain how reinforcement learning differs from simpler strategies and which conditions lead to unfavorable outcomes from a consumer perspective. In particular, we first describe the reinforcement learning problem in a more general manner and investigate the influence of the hyper-parameters. We then consider two situations separately. One, similar in spirit to Rocher et al. (2023), assumes that the market is in equilibrium and that a general agent tries to exploit a pricing strategy of an incumbent agent. The second, more general, approach consists of an agent continuously updating their own policy.

The starting point was Calvano et al. (2020),

For classical games, the mathematical framework is the following

for example, with the prisoner’s dilemma

Then, consider repeated games, and possible collusion

The next step is to include randomness, with (dynamic) stochastic games

and standard equations

(I describe quickly the different concepts). Finally, we can move from here to reinforcement learning, and Q-learning

The idea will be to play (or to interact) to learn that matrix

with the following interpretations, for the different parameters

Then, we will play a little bit, on the framework introduced to present the prisoner’s dilemma, for instance to understand the importance of $\beta$, using in the $\epsilon$-greedy approach, with $\epsilon_t=\exp(-\beta t)$

That is our first approach to the concept of collusion : agents don’t need to “cooperate” to have collusion

Then, we will use the experiment of Calvano et al. (2020) to get more complex discussions…

Promesse et rationalité économique (à court terme)

Non, je vais pas faire une analyse des promesses en cette année électorale (bien que le sujet pourrait être amusant, on peut penser aux propos du candidat Newt Gingrich qui veut que la lune devienne un état américain, ici ou ). Non, en fait je voulais faire un billet sur le sujet les assureurs sont-ils vraiment des voleurs ? En effet, lorsqu’en classe on présente le fonctionnement d’un contrat d’assurance – en particulier lorsque l’on parle de tarification et de l’inversion du cycle de production, ou du provisionnement – on explique que l’assuré achète une promesse: celle de se faire indemniser les sinistres survenus pendant la période dite de couverture. Car formellement, c’est bien de cela qu’il s’agit. Sauf qu’il y a toujours quelqu’un pour faire noter que ce n’est peut-être pas aussi simple et que l’assureur, souvent, rechigne à payer.

En fait, il est parfaitement rationnel – d’un point de vue économique (on s’entend) – que l’assureur négocie. En tous les cas si l’assureur a une vision à très court terme… Et c’est ce que justifient Briegleb & Lemaire (1982), sur l’analyse du marchandage ou Lemaire (1982) (dont sera très largement inspiré ce billet).
Considérons un cas très simple: un assuré a subit une perte (connue, de l’assuré comme de l’assureur). Mais l’assureur refuse de payer. Et l’assuré envisage d’aller au tribunal. Afin de voir s’il s’agit d’une décision rationnelle, on suppose que l’assuré () avait une richesse  avant que le sinistre ne survienne, qu’aller en justice lui coûte , et qu’il estime que sa probabilité de gagner le procès est . De son coté, la compagnie () d’assurance a une richesse , qu’aller en justice lui coute , et que la probabilité que la compagnie perde le procès est – selon la compagnie – (les sont alors les probabilités que l’assuré gagne son procès, mais vu des deux cotés). Au tribunal, on suppose que le juge rend un verdict du genre tout ou rien (on n’autorise pas ici de compensation plus importantes que le cout réel du sinistre, et on ne parle pas non plus de remboursement des frais d’avocat en cas de victoire du procès).
L’espérance d’utilité de l’assuré est

alors que pour la compagnie d’assurance, son espérance d’utilité est

La situation est Pareto optimale si

Si on suppose que les agents sont risquophobe (i.e. décroissante), alors

alors que

Aussi, une condition nécessaire pour que la situation soit Pareto-optimale est que

i.e. . Aller au tribunal n’est pas Pareto optimal si croit plus en ses raisons de gagner que . Si , il peut alors être optimal de ne pas aller au tribunal…. On ne dit pas ici qu’il faut que la compagnie indemnise (intégralement) l’assuré, mais que l’assureur et l’assuré peuvent avoir intérêt a trouver une solution amiable…
Si , il peut être intéressant d’aller au tribunal… mais pas forcément… Du point de vue de l’assureur, on peut supposer que sa richesse lui permet de ne pas être risquophobe, ou au moins d’être risque neutre (face a cette assuré au moins). Elle est donc indifférente entre aller au tribunal (et avoir un rendement incertain) et verser un règlement amiable si le versement correspond à son espérance de perte si elle va au procès. Autrement dit . L’assuré acceptera cette somme si l’utilité qu’il en tire est plus grande que l’espérance d’utilité qu’il aura en allant au tribunal,

La différence entre le terme de gauche et le terme de droite est une fonction . Si l’agent a une utilité exponentielle

alors

doit être une fonction positive. Un calcul rapide de dérivées montre que cette fonction est convexe, avec un minimum atteint en

Moralité ?

• pour les petits et pour les gros sinistres, il est normal que l’assureur et l’assuré cherchent une solution amiable (transaction)
• en revanche, pour les sinistres de cout intermédiaire, il peut être légitime d’aller au tribunal (procès).

Maintenant, si on a les grandes directions… peut-être peut-on essayer de mieux comprendre quelle serait le montant de la transaction dans le cas ou une solution amiable est envisagée. Nash (1950) a envisagé un jeu non-coopératif afin de décrire le marchandage. La transaction optimale est la quantité qui maximise le produit des deux gains d’utilité (cf Nash (1950) ou Roth (1979))

La condition du premier ordre donne l’équation suivante

Si on fait un peu de calcul numérique, on note que la solution est décroissante en : plus l’assuré est risquophobe, plus faible sera la montant de la transaction…. Ce qui n’est pas surprenant, on retrouve ici un résultat noté dans Peeters (1981), Roth (1982) ou ecnore Osbourne (1985). Maintenant, sur le modèle théorique on pourrait bien entendu argumenter que le tribunal fonctionne selon une règle trop simple du tout ou rien, et qu’un procès peut couter beaucoup cher que le simple remboursement du cout du sinistre. Ou qu’il pourrait créer une jurisprudence. On pourrait aussi regarder économétriquement le lien entre le cout des sinistres et les montants des ententes amiables (c’est ce que fait Ayusoa, Bermúdezb & Santolinoc (2012)) mais c’est une autre histoire…. ou ça pourrait être le sujet pour une autre histoire… à suivre donc.

Natural Catastrophe Insurance: How Should the Government Intervene?

An updated version of the joint paper with Benoit Le Maux is online on http://papers.ssrn.com/.

The present paper develops a new theoretical framework for analyzing the decision to provide or buy insurance against the risk of natural catastrophes. In contrast with conventional models of insurance, the insurer has a non-zero probability of insolvency that depends on the distribution of the risks, the premium rate, and the amount of capital in the company. Among several results, we show that risk-averse policyholders will accept to pay higher rates for a government-provided insurance with unlimited guarantee. However, depending on the correlation between and within the regional risks, a government program can be more attractive to high-correlation than to low correlation areas, which may lead to inefficiencies if the insurance ratings are not appropriately chosen.

Non, les probabilités ne sont pas nos amies…

… et non, nous ne vivons pas le monde merveilleux des Bisounours: la vie n’est pas toujours juste. Les probabilités sont un objet assez curieux à manipuler, pas forcément très intuitif. J’avais évoqué ici et enfin  la notion d’espace probabilisé … En fait, généralement, les calculs de probabilités sont assez troublants et paradoxaux. On va considérer ici des gens devant prendre des situations en présence d’incertitude, et plus particulièrement deux situations: la difficulté de prendre en compte de l’information (et donc de calculer des probabilités conditionnelles) et le cas où les gens doivent agir en prenant des décisions de manière aléatoire (et donc fixent en même les probabilités).

• Les probabilités conditionnelles

Avant hier, j’avais mis en ligne (ici) un billet sur le paradoxe dit de Monty Hall, où le candidat à un jeu télévisé doit choisir une porte parmi trois (afin de gagner une voiture), une fois son choix effectué, le présentateur ouvre une des deux autres portes (une qui n’a pas de lot derrière) et demande au candidat s’il souhaite revenir sur son choix. Et la réponse est qu’effectivement, le candidat a intérêt à ouvrir la porte qui est restée ouverte (et que l’animateur n’a pas choisie). L’idée du raisonnement est de formaliser proprement cette information à l’aide de lois conditionnelles.

Cette importance de l’information se retrouve par exemple dans l’histoire des cocus de Bagdad ou des yeux bleus (ici). Sinon, sur les paradoxes de probabilité, je peux aussi renvoyer vers des histoires de des lancers de pièces (ici), mais aussi sur le paradoxe des enveloppes () qui pourrait faire penser à l’histoire de Monty Hall. Mais mon préféré sur les lois conditionnelles reste le paradoxe de Simpson (ici, repris sous une forme plus géométrique )…

• Les probabilités comme paramètres de décision

Dans tous ces exemples, les probabilités sont connues, et il s’agit simplement d’une mise à jour afin de prendre en compte une nouvelle information. Mais il existe des cas encore plus vicieux, où les probabilités ne peuvent pas être considérées comme exogènes, ou objectives, car elles sont déterminées par les joueurs. Considérons une jeu simple, un peu dans l’esprit du pierre-feuille-ciseau (que j’avais déjà évoqué ici, en rappelant qu’il était fondamental de prendre des décisions de manière aléatoire). Dans le jeu d’aujourd’hui, on a toujours deux joueurs, disons moi (P) et ma fille (F). On cache nos mains dans le dos, et on les sort au même moment, en montant un ou deux doigts,

• si le nombre de doigts sortis est identique (paires (1,1) ou (2,2)), alors je gagne le nombre de doigts sortis, i.e. 2 ou 4
• si le nombre de doigts sortis est différent (paires (1,2) ou (2,1)), alors ma fille gagne le nombre de doigts sortis, i.e. 3

La matrice des paiements est alors la suivante

 P\F 1 2 1 2 -3 2 -3 4

Si on suppose que l’on a une chance sur 4 pour chacune des paires, le jeu est alors a somme nulle, puisque

Sauf que les probabilités sont fixées par les joueurs, en l’occurrence moi et ma fille. Supposons que je sorte 1 doigt avec probabilité , et 2 avec probabilité (avec ). Ma fille sort 1 doigt avec probabilité , et 2 avec probabilité (avec ). La valeur espérée du jeu (de mon point de vue) est

Ma fille cherche  qui va minimiser cette valeur, alors que moi, je cherche  qui la maximise. Bref, un problème classique de problème minmax de théorie des jeu. L’équilibre (s’il existe) sera  où et  solution de

A p donné, ma fille cherche à trouver

soit

soit encore

en notant que , on peut réécrire . Autrement dit, si , ma fille a toujours intérêt à sortir un doigt (car ) et ce n’est pas un équilibre… pareillement, si , ma fille a toujours intérêt à sortir deux doigts, et là encore ce n’est pas un équilibre. Autrement dit, le seul équilibre possible est obtenu lorsque , i.e l’équilibre correspond à . De manière dual, pour ma part, je cherchais à trouver

i.e.

soit

qui conduit à un équilibre seulement si . Autrement dit, afin que le jeu soit à l’équilibre, il faut que nous jouions la stratégie suivante: sortir un doigt avec probabilité  (et pas ) et deux avec probabilité . Et la valeur espérée du jeu est alors

Moralité, ma fille tu as intérêt à travailler tes maths si tu veux battre un jour ton père ce n’est pas vraiment un jeu “juste“… à condition bien sûr que moi et ma fille soyons ensuite capable de mettre en œuvre cette stratégie… Car si je regarde avec mes yeux de statisticiens, je pense qu’il est assez dur de faire la différence entre  et  … La preuve sur cette petite simulation,

> N=100; pv=rep(NA,100000)
> for(s in 1:100000){
+ X=sample(1:2,size=N,prob=c(5/12,7/12),replace=TRUE)
+ P=prop.test(table(X)[1],n=N,p=1/2)
+ pv[s]=P\$p.value}
> mean(pv>0.05)
[1] 0.66776

autrement dit, en supposant que ma fille et moi arrivions a jouer 100 fois à ce jeu, dans 2/3 des cas je n’arrive pas à faire la différence entre une probabilité valant  et une probabilité valant .

Jeux noncoopératifs et assurance des catastrophes

Présentation d’un papier (pas encore complètement fini) lors de la réunion AST&Risk à Grenoble1, sur l’assurance des catastrophes naturelles. Les slides seront mis en ligne dès lors que le papier sera finalisé (encore quelques jours)…

En théorie de la décision, les agents prennent des décisions en fonction de leurs croyances, et de leur utilité. Un jeu est un cadre (formel) où les décisions des agents sont interdépendantes: la décision que je prends dépend de ce que font les autres. On parle alors de stratégie.
La notion d’équilibre dans les jeux à somme nulle découle du théorème minimax de John von Neumann (en 1926). Mais c’est John Nash qui a proposé la notion la plus générale en 1950 (je l’avais mentionné ici). Ce résultat est fondamentalement un théorème de point fixe.  Pour comprendre la notion d’équilibre de Nash, prenons l’exemple suivant (que j’ai trouvé ici): considérons un jeu avec deux joueurs (A et B) qui doivent choisir entre deux stratégies S1 et S2. Les gains des 2 joueurs (connus) sont représentés dans le tableau suivant sous la forme (Gain de A ; Gain de B).

On se demande simplement comment les agents doivent prendre une décision. Pour résoudre ce problème, on étudie toutes les stratégies possibles

1. est-ce que (S1 ; S1) est une situation stable ? Non, car le joueur A aura plutôt intérêt à choisir S2 (afin d’augmenter son gain de 3 à 4), tandis que le joueur B voudra dévier en S2 (pour avoir un gain de 4 plutôt que de 3). Bref, les deux joueurs chercheront à dévier: ce n’est pas un équilibre.
2. en (S1 ; S2), A aura intérêt à choisir la stratégie S2 afin de faire passer son gain de 0 à 1. B n’a pas intérêt à dévier dans cette situation. Si l’un des agents a intérêt à dévier, on se doute qu’on ne restera pas sur cette stratégie: ce n’est pas un équilibre.
3. en (S2 ; S1), A n’a pas intérêt à dévier, mais B va préférer la stratégie S2 qui lui donne un gain de 2 plutôt que de 1.
4. en (S2 ; S2), aucun des joueurs n’a intérêt à dévier, il s’agit d’un Équilibre de Nash. Aucun des joueurs ne peut faire mieux en modifiant unilatéralement sa stratégie.

On parle de jeux non-coopératif car les décisions sont prises unilatéralement. On peut alors schématiquement représenter ces déviations sur le schéma suivant

Notons également que l’on a un équilibre de Nash, mais aucunement une situation optimale: les joueurs gagnent respectivement 1 et 2, alors qu’ils pourraient gagner 3 (tous les deux) avec la stratégie (S1 ; S1)

1 Le groupe organise d’ailleurs un workshop Modélisation spatiale et temporelle de la dépendance & Applications au risque, qui se tiendra à Luminy du 26 au 30 avril 2010, ici.