No Algorithmic Collusion in Two-Player Blindfolded Game with Thompson Sampling
When two players are engaged in a repeated game with unknown payoff matrices, they may be completely unaware of the existence of each other and use multi-armed bandit algorithms to choose the actions, which is referred to as the ``blindfolded game'' in this paper. We show that when the players use Thompson sampling, the game dynamics converges to the Nash equilibrium under a mild assumption on the payoff matrices. Therefore, algorithmic collusion doesn't arise in this case despite the fact that the players do not intentionally deploy competitive strategies. To prove the convergence result, we find that the framework developed in stochastic approximation doesn't apply, because of the sporadic and infrequent updates of the inferior actions and the lack of Lipschitz continuity. We develop a novel sample-path-wise approach to show the convergence.
Code (0)
등록된 구현이 없습니다.
Tasks
Thompson SamplingSimilar Papers 제목 키워드 기반
Tacit algorithmic collusion in deep reinforcement learning guided price competition: A study using EV charge pricing game
Players in pricing games with complex structures are increasingly adopting artificial intelligence (AI) aided learning algorithms to make pricing decisions for maximizing profits. This is raising concern for the antitrus…
Deep Reinforcement LearningCollusion Detection in Team-Based Multiplayer Games
In the context of competitive multiplayer games, collusion happens when two or more teams decide to collaborate towards a common goal, with the intention of gaining an unfair advantage from this cooperation. The task of …
Ex ante coordination and collusion in zero-sum multi-player extensive-form games
Recent milestones in equilibrium computation, such as the success of Libratus, show that it is possible to compute strong solutions to two-player zero-sum games in theory and practice. This is not the case for games with…
FormNaive Algorithmic Collusion: When Do Bandit Learners Cooperate and When Do They Compete?
Algorithmic agents are used in a variety of competitive decision settings, notably in making pricing decisions in contexts that range from online retail to residential home rentals. Business managers, algorithm designers…
Beyond Human Intervention: Algorithmic Collusion through Multi-Agent Learning Strategies
Collusion in market pricing is a concept associated with human actions to raise market prices through artificially limited supply. Recently, the idea of algorithmic collusion was put forward, where the human action in th…