{'fraction_non_alphanumeric': 0.02692142550450837, 'fraction_numerical': 0.008930871618720481, 'mean_word_length': 4.8329576759328825, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Winning at Any Cost -- Infringing the Cartel Prohibition With Reinforcement Learning

Pricing decisions are increasingly made by AI. Thanks to their ability to train with live market data while making decisions on the fly, deep reinforcement learning algorithms are especially effective in taking such pricing decisions. In e-commerce scenarios, multiple reinforcement learning agents can set prices based on their competitor's prices. Therefore, research states that agents might end up in a state of collusion in the long run. To further analyze this issue, we build a scenario that is based on a modified version of a prisoner's dilemma where three agents play the game of rock paper scissors. Our results indicate that the action selection can be dissected into specific stages, establishing the possibility to develop collusion prevention systems that are able to recognize situations which might lead to a collusion between competitors. We furthermore provide evidence for a situation where agents are capable of performing a tacit cooperation strategy without being explicitly trained to do so.


Introduction
Dynamic reinforcement learning based pricing strategies supersede static ones in terms of average daily profits [16]. As 27 percent of the respondents of a 2017 study by KPMG identified price or promotion as the factors that are most likely to influence their decision regarding which product or brand to buy online [15], it is to be expected that successful companies (such as Amazon [5]) base their decisions on these algorithms to learn from and react to their competitor's pricing policies as well as to adjust to external factors, such as a transformation of demand or product innovations [12]. Monitoring these AIs is getting increasingly complex as the market is distributed worldwide, the barriers of entry are minimal, and the amount of created pricing data grows quicker by the day.
The work presented in this paper has been conducted in the KarekoKI project, which is funded by the Baden-Württemberg Stiftung in the Responsible Artificial Intelligence program.

arXiv:2107.01856v1 [cs.AI] 5 Jul 2021
Primarily legal scholars have commented on the possibility of self-learning algorithms to quickly learn to achieve a price-setting collaboration especially within oligopolies (e. g., [10,11,12]). With the power of modern hardware, AIs would be able to monitor the market in which they act, resulting in a rapidly arising tacit collusion. Researchers investigated the issue by creating game theory like scenarios with the intention of pushing the agents towards a Nash equilibrium (e. g., [12,23]). In essence, it seems to be "incredibly easy, if not inevitable" to achieve "such a tacitly collusive, profit-maximizing equilibrium" [20]. While collusion has been presumed to appear in enclosed multi agent reinforcement learning scenarios, scholars have neither studied how to spot the origin of collusion nor if competitors can apply tacit collusion by displacing the others.
In an effort to simplify the dynamic pricing data analysis, we aim to train a competitive multi agent reinforcement learning (MARL) game simulation. In this game, the agents play a three-player version of rock paper scissors (RPS). We aim to analyze the effect of the competitive RPS scenario on the agents' learning performances and potential collaboration strategies. In specific, we aspire to analyze whether RL agents are capable of performing a tacit cooperation or communication strategy without being explicitly trained to do so.

Infringing the Cartel Prohibition
In its most recent proposal for an Artificial Intelligence Act, the European Commission emphasises the importance of the safety and lawfulness of AI systems, of legal certainty with regard to AI, the governance and effective enforcement of existing law on fundamental rights and the installation of safety requirements [8]. In line with these goals, AI price policies must oblige to competition law just as prices that are set by humans. Both European and German competition law distinguish three possible conducts of infringing the cartel prohibition, see Article 101 (1) Treaty on the Functioning of the European Union ("TFEU") 3 : (a) agreements between undertakings, (b) decisions by associations of undertakings, and (c) concerted practices. Independent undertakings shall independently decide over their market behavior and must not coordinate it with their competitors ("requirement of independence"). This requirement does strictly preclude any direct or indirect contact by which an undertaking may influence the conduct on the market of its actual or potential competitors or disclose to them its decisions or intentions concerning its own conduct on the market where the object or effect of such contact is to create conditions of competition which do not correspond to the normal conditions of the market [9].
The independently chosen intelligent adaption of an undertaking's market behavior to the observed market behavior of its competitors (generally) is permitted. Drawing a clear line between the adaption of an observed market behavior and a conduct through which competition knowingly is replaced by a practical cooperation and therefore constitutes a concerted practice within the meaning of Article 101 (1) TFEU 4 is often difficult and sometimes even impossible. Especially on transparent markets with few market participants, the market outcome of collusion can often hardly be traced back to be (or not to be) the product of a concerted practice (cf. petrol station market). Although collusion as a market outcome can be detrimental to consumers, innovation and economic growth and is therefore undesirable from a welfare economic point of view, the difficulty from a dogmatic perspective is that legal responsibility cannot be attached to a market outcome as such [24].
Our goal is to disclose whether a certain sequence of actions or a specific pattern can be identified as a situation in which the uncertainty about the competitor's next moves is replaced by a practical cooperation. It is conceivable that such accurate determination might not be possible due to the increased market transparency achieved by the self-learning algorithms: their ability to quickly process large amounts of competition-relevant data and to react to price movements in an almost unlimited frequency might lead to such a high degree of transparency on a market that makes it impossible to determine from its outcome whether or not the result of collusion is due to intelligent market observation and parallel behavior or a concerted practice.

Multi Agent Reinforcement Learning
A tacit collaboration between some reinforcement learning agents can only occur in certain situations. The agents have to interact within a multi agent reinforcement learning (MARL) environment, where competing agents and prices are recognized as a part of such [4]. Due to that, the environment is usually subjective for every agent, resulting in a differing learning performance and a diverse landscape of achieved competencies. It is unclear whether one of these competencies might arise in the skill to communicate with specific other agents to adjust their pricing policies accordingly; resulting in a higher producer's pension and a displacement of a competitor.
Researchers have investigated circumstances which can be juxtaposed with collusion between pricing agents, such as bidding processes [21,7] or economy simulations [25]. However, the authors did not control for or induce communication or collaboration. To combat this shortcoming, scholars within the economics realm created oligopolistic models (particularly Cournot oligopolies) to show collusion between agents. A Cournot oligopoly is characterized by an imperfect competition, where firms individually have some price-setting ability but are constrained by rivals [3]. Izquierdo and Izquierdo [14] show that simple iterative procedures, such as the win-continue, lose-reverse (WCLR) rule are able to achieve collusive outcomes. However, the results are not robust in terms of minor, independent perturbations in the firms' cost or profit functions. Similar results were achieved with basic Q-learning [23]. As a case in point, using a price-setting duopoly model with fixed production, in which two firms follow a Q-learning algorithm, Tesauro and Kephart [22] observed convergence to prices higher than the competitive level. Major takeaways from these studies are, that cooperation is more likely to occur in simplified, static environments with a homogeneous good and that communication is vital to achieve collusive outcomes, particularly when more than two firms operate in a market. Such results suggest that the ability to communicate could also be pivotal for algorithmic collusion to occur [20].

Problem Definition
Oroojlooy and Hajinezhad [19] recommend to model a MARL problem based on (i) centralized or decentralized control, (ii) fully or partially observable environment and (iii) cooperative or competitive environment. Our case demands for a decentralized control, with a partially to fully observable environment, so that every agent is able to make its own decisions based on the information given by the environment. Lastly, we apply a cooperative inside of a competitive environment, so that agents are able to team up against other agents.

Approach
With the intention of simplifying a realistic economy simulation, we choose to build a MARL-game based on a three player version of RPS. Every agent i = {1, ..., 3} represents a player with a set of legal game actions A = {1, ..., 3} comprising the moves of rock, paper and scissors. The agents interact with a stochastic environment E which solely contains the chosen actions of every agent of the current time step t. Hence, a state at t can be described as Following a collective action, every agent receives a reward out of R = {-1, 0, 0.5, 2} mapped to the possible game outcomes presented in table 1, resulting in a direct association between input and output. This formalism gives rise to a finite Markov decision process (MDP) in which every t relates to a distinct state, encouraging an application of standard reinforcement learning methods for MDPs. The goal of the agent is to interact with E by selecting actions in a way that maximises future rewards. As the agents receive a reward at the end of every timestep, we will not apply any discount to future rewards. We define the optimal action-value function Q * (s, a) as the maximum expected return achievable by following any strategy, after seeing some sequence s and then taking some action a, Q * (s, a) = max π E[R t |s t = s, a t = a, π], where π is a policy that maps sequences to actions (or distributions over actions). In an attempt to induce strategic behavior, resulting in a tacit communication within this competitive MARL environment, we utilize a Deep Q-Network (DQN) [18] with an experience replay and a target network [17]. After performing experience replay, the agent selects and executes an action according to an -greedy policy. The agents select the action a t that maximizes the expected value of r + Q * (s , a ), updating the Q-values by: Our main argument for the selection of this specific scenario is the controlled, unambiguous reward allocation in combination with the restricted moveset of the agents. Thus, every step t develops into a zero-sum game (as shown in Table 1). On the one hand, we create an environment, where no agent can earn a profit, if it does not communicate with another agent. On the other hand, we counteract the poor learning performance of MARL [2] (due to the defined equilibrium/ local optimum) as well as increase the comprehensibility of the neural network's predictions. We expect the agents to converge to a collusive state after several episodes, as described by economics and law scholars (e. g., [12,23]).
We also attempt to induce a displacement of one agent due to the actions selected by the other two agents. In our use case, they need to learn a specific policy which would force two colluding agents to not repeat their allied agents' actions. While this would not necessarily result in a better short term step reward for these agents, it would however eliminate the ability to achieve a "big win" (e. g., playing Paper if the opponents play Rock and Rock) for the third, competing agent. Generally speaking, if two agents avoid choosing the same action, the expected reward for the third player is negative. We aim to simulate this circumstance in diverging settings.
In mode 1, collusion is induced by explicit communication as suggested by Schwalbe [20]. More specifically, we designate two 'cheating' agents i c ⊂ i and a 'fair' agent i f ∈ i, i f ∈ i c ahead of a training session. Before its turn, one of the cheating agents transmits his picked action to the other cheating agent. The

Output
(3) Fig. 1. DQN Architecture message will be enclosed to input to the receiver's DQN. 5 In mode 2, instead of making the players communicate explicitly, we provoke tacit communication by adjusting the reward of the cheating agents r t ic to r t ic = −r t f . In other words, they will try to maximize their joint instead of their individual reward, which is equivalent to minimizing i f 's reward. We additionally denoise the rewards; hence, i c will receive 1 for a loss or a tie with i f and -1 for a win of i f . To further stress this issue, we perform control-runs, where i f is replaced with an agent that plays random actions (which is the best strategy in a competitive 3-player version of RPS).

Implementation
The main weakness of RPS in a real world scenario is the unpredictability of an opponent's move. The best player would just play random, however since playing this game is psychologically based on personal human short-term memory behavior, there is a tendency to follow specific patterns, like not repeating moves or trying to play unpredictably [1]. In an artificial MARL-problem, we can model that by not only reacting to an opponent's last move, but learning from a history of its last moves. After testing, we chose to apply a history size of 100 games to accommodate for a stable learning process. Regarding the experience replay, we chose to use the last 3 timesteps as an input for the neural net. The network is made up of four dense layers (input, two hidden layers, output), whose main task is to compress the given information and provide the chosen action. For that matter, we design a DQN with an input layer comprising 8100 neurons (300 steps * 3 one-hot encoded actions * 3 players * 3 time steps), two hidden layers with 2700 and 9 neurons and a dense output with 3 neurons to choose either rock, paper or scissors (cf. figure 1). The neurons required for the number of players will increase by 1 for the cheating player to accommodate for the action received by the messaging agent. We use TensorFlow 2 to build and train the DQNs; the code can be found on Github 6 .

Results
To counter inconsistent MARL outcomes, we chose to train the agents for 10 runs with 100 episodes each (300 steps per episode), comprising three different learning rates (0.001, 0.005, 0.01), resulting in 30 runs with 900.000 games of RPS per scenario. We picked learning rates that are fairly small to counteract quickly developing local optima, causing repetitions of the same action, due to the straightforward connection between action and reward. For every scenario with i c involved, we also performed another 15 runs (5 per learning rate) where i f is replaced with an agent that randomly picks actions in order to further stress the issue by simulating a perfect RPS policy.

Collusion between all agents
In our series of simulations, we were able to achieve collusive results within every of the chosen learning rate scenarios (cf. figure 2). When averaged, the different action sequences can be visually divided into three learning stages. In stage 1 , the agents basically acted random, due to the epsilon-greedy algorithm. After approximately 5 episodes (stage 2 ), one of the agents achieved a better outcome due to a lucky action selection. The agents stuck to their learned strategy while randomly delving into different policies. Upon further examination, we discovered that the strategies usually involve a single action which will be repeated in the next turns, even if this might not be the best action. This sub-optimal behavior stems from the first few episodes being mostly played randomly due to the epsilon-greedy strategy. Thus, the agents were only able to learn from a short history, which taught them to repeat the most successful action, rather than a certain sequence of actions. Stage 3 establishes a collusive sequence of actions from episode 40 onwards with two different scenarios (3a and 3b).
As presented in table 2, the agents try to avoid a negative reward over a long-term, resulting in an average episode profit of zero. However, stages 3a and 3b differ significantly in their way of achieving this. In 3a, one of the players repeated one action (e. g., scissors) and occasionally deviated from that due to the epsilon-greedy strategy, while the others predominantly alternate between two moves that change over time. In stage 3b, the agents played seemingly random. However if examined more closely, specific alternation patterns occured. A specific pattern can be identified, when observing the actions of agent 1 in figure 2. The player oscillated between choosing rock and scissors in the first moves and transitions to scissors and paper towards the end of the episode. The remainder of the agents follow more elaborate patterns, however specific repetitions can be discovered by scanning the history.

Collusion between two agents
Mode 1: Explicit Communication We successfully trained a displacing collusion policy with the help of explicit communication between the cheating agents i c . The results represented in figure 3 indicate that the agents were able to learn the suggested policy of not repeating their collaborator's action after a few episodes. After about 5 episodes, i c achieve a higher reward on average. Thus, for the next 30 Episodes i f is only rarely able to achieve a "big win". However, just like when colluding with all agents, after approximately 45 episodes, they tend to converge to an average game reward of 0. While it would be feasible to prolong this behavior by including variable learning rates or reducing the target update frequency during later episodes, we chose to encourage a longterm formation of a zero-centered equilibrium. Our reasoning behind this is the comparison to a real-world oligopoly, where two market participants could only uphold a displacement by reducing the price up to a certain point, before damaging themselves. In order to further stress the issue, we chose to replace i f with an agent that chooses actions randomly. While i c were able to successfully learn a displacement strategy in every training session, the results within the first 40 episodes were less significant than when i f acted on behalf of the DQN. Nevertheless, we were able to observe slightly better results in the later stages, due to the added randomness.
Mode 2: Implicit Communication The agents i c successfully learned the suggested implicit collusion policy. After about 5 episodes, i c achieve a higher game reward on average. This circumstance is especially prominent in the section between 20 episodes and 40 episodes (cf. the upper right half of figure 4). On average, i f is rarely able to exceed a reward of 0. Again, after about 40 episodes, the agents converge to an average game reward of 0.
We were able to observe a less prevailing, but still effective policy when implementing a randomly acting agent i f . As demonstrated in Figure 7 median of i f 's winrate was still 0 in between episodes 0 to 40, yet the interquartile range is greater than before, indicating a less stable learning due to the added randomness of i f 's action selection. We also experience a few runs, where the agents were able to learn the displacement policy and not unlearn it in later episodes. In those specific runs, agent 1 repeated the same actions from episode 22 onward while agent 0 played the action that would lose against that one in a regular game. Hence, the joined rewards i c turn out greater than those of i f .

Discussion
Our research successfully confirmed the hypothesis from law and economics scholars (e. g., [23] or [14]) about a possible collusion between reinforcement learning based pricing agents in MARL scenarios without being especially trained to do so. We furthermore extended these findings by providing specific learning stages that could be translated into real world scenarios to possibly set a foundation for a system that is capable to detect collusion in early stages. Moreover, we were able to show that with the appropriate reward function, deep reinforcement learning can be used to learn an effective displacement strategy in a MARL environment.
Based on the results of the experiments, we derive several implications. Due to the noticeable segmentation of action selection in different learning stages, one could argue that the transition episodes in between a fair and a collusive state can be seen as a signaling process, where agents agree on specific patterns to increase the joint reward. This proposition is supported by the fact, that a repeating action selection pattern of another agent could be predicted and punished by the DQN due to its experience replay [17]. In a real world scenario, a malicious AI could be trained to repeat patterns, that are less recognizable for humans. We would like to emphasize that within inelastic selling conditions (as they appear in collusive markets), a cooperation between two agents will be facilitated as the existing communication strategy will furthermore ease the displacement of a competitor. From a legal perspective, the question whether the cartel prohibition can be applied to such factual achieved, however nonvolitional, state of collusion, is subject to this project's further legal research.

Limitations and Outlook
As every study, the results are beset with limitations, opening the door for future research. As aforementioned, our experiment is a simplified, gamified version of an economy simulation game. As such, it lacks the data complexity of a real world pricing AI as well as the scaling opportunities. To further develop our research, we intend to apply the gained knowledge to a MARL environment resembling the one of real pricing AIs, where we can further highlight specific moments in which the agent's behavior tips over from independence to collusion. Especially the division into distinct stages should be investigated in a context of realistic pricing agents environments. While we focused on highlighting the possible dangers of pricing AIs in a MARL environment, we opened the opportunity for research explicitly investigating measures to avoid it. As such, law and IT scholars alike could benefit from this research as a foundation for guidelines, law amendments, or specific laws concerning the training and behavior of pricing AIs.