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…
(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 
décroissante), alors
. Aller au tribunal n’est pas Pareto optimal 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…
. 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,
. Si l’agent a une utilité exponentielle
qui maximise le produit des deux gains d’utilité (cf 
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 
… 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).
Avant hier, j’avais mis en ligne (
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é 
, 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
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
. 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
. 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
