Data‐driven collusion and competition in a pricing duopoly with multinomial logit demand

Abstract

We consider dynamic pricing and demand learning in a duopoly with multinomial logit demand, both from the perspective where firms compete against each other and from the perspective where firms aim to collude to increase revenues. We show that joint‐revenue maximization is not always beneficial to both firms compared to the Nash equilibrium, and show that several other axiomatic notions of collusion can be constructed that are always beneficial to both firms and a threat to consumer welfare. Next, we construct a price algorithm and prove that it learns to charge supra‐competitive prices if deployed by both firms, and learns to respond optimally against a class of competitive algorithms. Our algorithm includes a mechanism to infer demand observations from the competitor's price path, so that our algorithm can operate in a setting where prices are public but demand is private information. Our work contributes to the understanding of well‐performing price policies in a competitive multi‐agent setting, and shows that collusion by algorithms is possible and deserves the attention of lawmakers and competition policy regulators.

INTRODUCTION

Background and motivation

The mathematical analysis of dynamic price algorithms in the presence of demand learning is at the forefront of contemporary research, undoubtedly inspired by the significant potential for implementation in practice. A vast and rapidly increasing stream of literature analyzes such price algorithms (see the references discussed in Subsection 1.3). Most of these settings are monopolistic, and do not take the intricacies of pricing and learning in the presence of competitors into account. This motivates the current work, in which we study pricing and learning in a duopoly.

An important aspect of duopoly pricing is the absence of an unequivocal notion of what it means to price optimally. In most monopolistic models, there exists a unique optimal price if model parameters remain fixed throughout the time horizon. For duopolies, however, there exists a spectrum of equilibria, with Nash equilibria on one side and supra‐competitive equilibria on the other side. In this paper, we consider price policies for both sides of the spectrum.

The potential convergence of price algorithms to supra‐competitive equilibria has recently drawn the attention of competition regulators worldwide (Hoffman, 2018; OECD, 2017b; Spiridonova & Juchnevicius, 2020). In particular, the question has emerged whether price algorithms are capable of learning supra‐competitive prices from data (specifically in the scenario where multiple firms in a market use the same price algorithm), within the boundaries of existing competition law. Among other things, this means that the algorithms cannot make use of illicit forms of signaling or communication. Some argue that algorithmic collusion poses a fundamental threat to consumer welfare (Ezrachi & Stucke, 2016, 2017a, 2017b, 2017c, 2020), whereas others believe that algorithmic collusion belongs to the realm of “science fiction” (Kühn & Tadelis, 2017; Schrepel, 2017; Schwalbe, 2018; Veljanovski, 2020). If algorithmic collusion is possible, then the existing legal framework of competition law might need substantial revision or re‐interpretation (Ezrachi & Stucke, 2016, 2017a, 2017b, 2017c, 2020; Gal, 2019; Harrington, 2018; OECD, 2017b).

A challenge in achieving algorithmic collusion is the fact that, without communication, there might be ambiguity in the firms' understanding of what it means to collude. But as shown by Meylahn and den Boer (2022), a definition of collusion can be built into the algorithm; an “algorithmic agreement,” as it were (cf. Gal, 2019, p. 78). This is a powerful tool for creating stable cartels under mutual use of the algorithm, as it prevents bargaining and deviation issues that often result in the collapse of collusion (Bos & Harrington, 2010, pp. 107–108).

A second challenge is the fact that collusive prices usually depend on parameters that are unknown and thus have to be learned from sales data. This task is further complicated by the fact that prices are often publicly observable, but sales transactions are not: firms typically do not have access to the sales data of their competitor (see Meylahn and den Boer (2022) for exceptions). This hinders estimation of the notion of collusion implemented in the algorithm. It is therefore necessary to study if and how algorithms can overcome the challenge of private demand observations.

A third challenge that arises when hard‐coding a notion of collusion into a price algorithm is defining an appropriate collusive solution. Collusion is often associated with joint‐revenue maximization (Gal, 2019; OECD, 2017b; Schwalbe, 2018), but this notion may not perform well for individual firms in asymmetric settings without side payments (Fischer & Normann, 2019). In such cases, algorithmic collusion requires a notion of collusion that is always beneficial to all firms.

The purpose of this paper is to address these three challenges in the context of a pricing duopoly. We show that several axiomatic notions of collusion can be constructed that are beneficial to both firms and detrimental to consumer welfare. Next, we construct an algorithm that learns the collusive price when deployed by both players in the market and learns to respond optimally against a class of competitive algorithms. We furthermore propose a mechanism to overcome the challenge of private demand observations by exploiting the information that is conveyed by the algorithm's price decisions. This algorithm can generate supra‐competitive prices without breaking existing competition law, and therefore shows that the concerns of competition regulators are justified.

Legal environment

We consider a duopoly where both firms independently adopt the same price algorithm. In the absence of communication, the firms should not be in violation of the law even if mutual adoption of the algorithm leads to supra‐competitive outcomes. This is in accordance with findings of the OECD (2017a, p. 10): “Absent concerted action, independent adoption of the same or similar pricing algorithms is unlikely to lead to antitrust liability even if it makes interdependent pricing more likely.” Ezrachi and Stucke (2020, p. 220) derive similar conclusions. Along these lines, Harrington (2018, pp. 339–340) makes a very clear distinction between collusion as an outcome and the means by which the outcome is achieved: “Supracompetitive prices are legal. Collusion is legal. It is the process by which firms achieve collusion that is illegal, rather than the state of collusion itself. […] At a minimum, there must be evidence of communication to allow a court to conclude that firms have not acted independently. Though all forms of collusion are harmful, some forms are legal because of the inability to effectively distinguish collusive conduct from competitive conduct”.

If competing firms purchase the algorithm from the same software supplier who boasts the collusive capabilities of the algorithm, then the supplier runs the risk of being seen as a “middle man” who facilitates collusion and could potentially be held liable. The OECD (2019) has collected many real‐life cases of this type of collusion, so‐called hub‐and‐spoke collusion, where coordination does not occur through direct exchanges between the horizontal competitors (the “spokes”), but through exchanges via a vertically related supplier or retailer (the “hub”). Of particular interest is the case of Partneo (see, e.g., Mandrescu, 2018): between 2008 and 2013 five carmakers colluded by using the same car part pricing software, Partneo, from the company Accenture. They boosted their revenues by more than 1 billion dollars thanks to using Partneo, and yet “no formal findings […] have been found against the carmakers or Accenture” (Ezrachi & Stucke, 2020, p. 220). The OECD (2019, p. 2) states that “[t]he main challenge for enforcement agencies is to identify when inherently legitimate exchanges between suppliers and retailers turn into a prohibited horizontal co‐ordination, without direct proof of collusion. Enforcement and jurisprudence in particular in the United States, but also in Europe, […] require proof of a horizontal connection between the spokes, a rim, and an awareness of all actors involved”. In the scenario that we consider in this paper, there are no exchanges between the competitors via the software supplier. This means that a “rim” (a connection between competitors) can only be established by the workings of the algorithm itself. In Section EC.3 of the Supporting Information, we explain that it is inevitable that prices generated by an algorithm contain and transfer information. This information transfer is an “accidental” and unavoidable by‐product of the generated price decisions that have legitimate alternative justifications. This further suggests that users (and possibly distributors) of the algorithm do not violate competition laws.

Although it is not settled whether a software supplier can sell the same algorithm to competing firms without violating laws, this problem does not arise in other scenarios. Consider the situation of multiple third‐party sellers who sell their products on an online platform. Suppose, in addition, that the computer code of a collusive algorithm has been made available on an online software repository. The collusive capabilities of the algorithm are not mentioned; all that gradually becomes known through word‐of‐mouth rumors is that the algorithm appears to increase profits substantially. It is conceivable that in this situation multiple sellers start using the algorithm, without engaging in illicit communication with each other or with a “middle man.” This scenario becomes increasingly likely due to the rising popularity of platforms that connect third‐party sellers to consumers, and of open‐source software repositories. There are many software suppliers who offer repricing algorithms to third‐party sellers on various platforms, and generally charge a fee that increases with the number of listings. There could thus be much interest in free‐to‐download pricing software.

We emphasize that we do not and cannot claim with certainty that the algorithm proposed in this paper (or the distribution thereof) is legal, because that can only be decided in court. For the same reason it is also not clear that the algorithm is illegal. Regulators are well‐aware that algorithms can facilitate tacit collusion by reducing or eliminating the need for human communication (OECD, 2017b, p. 7), and that signaling between algorithms can occur through prices: “For instance, firms may program snapshot price changes during the middle of the night, which won't have any impact on sales but may be identified as a signal by rivals' algorithms. Or, alternatively, companies may use algorithms to publicly disclose a lot of detailed data that is used as a code to propose and negotiate price increases, as it was observed in the US case on Airline Tariff Publishing Company” (OECD, 2017b, p. 30). An important insight of this paper is that information can be transferred between algorithms in much subtler ways. Indeed, we concretely show that prices generated by algorithms reveal information that can be used to achieve supra‐competitive outcomes, not because extraneous information is explicitly encoded in the prices, but because legitimate price decisions inevitably allow decoding of information by a copy of the same algorithm. This creates a challenge for lawmakers: information transfer through prices is inevitable, but it is far from trivial to determine where to draw the line.

Related literature

Recently, a large number of studies have appeared on dynamic pricing with demand learning (Besbes & Zeevi, 2009, 2015; Broder & Rusmevichientong, 2012; Chen et al., 2019, 2021; Cheung et al., 2017; den Boer & Zwart, 2014, 2015; Hansen et al., 2021; Harrison et al., 2012; Keskin & Zeevi, 2014; Wang et al., 2014, 2021). We refer to den Boer (2015) for a recent survey. Although these papers consider an impressive number of models and settings, the formal analysis of price algorithms with demand learning in the presence of competitors has received relatively little attention in this stream of literature. Exceptions include Bertsimas and Perakis (2006), who formulate an optimal pricing problem with incomplete information in a dynamic programming framework and propose tractable approximations; Cooper et al. (2015), who study the limit behavior of prices in a duopoly where both players use a mis‐specified passive learning policy; and Yang et al. (2020), who study convergence to equilibrium prices under the assumption that all players in the market use the same algorithm. Our paper contributes to this stream of literature by proposing price policies and formally proving regret bounds in a duopoly, both in a competitive and in a collusive setting.

Our work contributes to the nascent field of algorithmic collusion. A key question in this field is up to what extent algorithms are capable of learning supra‐competitive prices under self‐play while simultaneously learning to price competitively against reasonable alternative algorithms. Recent contributions include Calvano et al. (2020), Cooper et al. (2015), and Klein (2021), where we remark that the focus of the second paper is not algorithmic collusion per se but rather the interplay of learning and model mis‐specification. These studies show by means of simulations that particular price policies, when playing against copies of itself, can lead to supra‐competitive limit prices and revenues with positive probability. However, as illustrated by figures 6 and 7 of Cooper et al. (2015), sub‐competitive prices and revenues are also possible outcomes. In addition, these papers do not provide performance guarantees in case these policies do not play against a copy of itself but against a “reasonable” alternative strategy. These two observations diminish the likelihood of such algorithms being implemented in practice (den Boer et al., 2022).

Two examples where the notion of collusion is explicitly programmed in the algorithm are Meylahn and den Boer (2022) and Aouad and den Boer (2021). Meylahn and den Boer (2022) explain that pre‐programmed collusion does not make an algorithm illegal. The authors consider a pricing duopoly, define collusion as maximizing the joint‐revenue function, and construct a policy that learns this collusive price provided this is mutually beneficial to the firms and both firms use the algorithm. In addition, it is shown that prices converge to a best response in case the opponent prices according to a reaction function. Aouad and den Boer (2021) consider similar questions in an assortment‐optimization duopoly with multinomial logit demand.

A limitation of Meylahn and den Boer (2022) is that collusion is only guaranteed if the joint‐revenue‐maximizing prices are mutually beneficial compared to pricing under the Nash equilibrium. In practice this is often not the case if the firms are not symmetric (Bos & Harrington, 2010; Fischer & Normann, 2019). A second limitation is that demand observations are assumed to be public information. These limitations might give lawmakers the wrong impression that algorithmic collusion is only possible in markets where these two limitations do not apply. In contrast, in this work we show and explicitly construct notions of collusion that firms can adopt that are always mutually beneficial. Hard‐coding these cartel prices in algorithms enables collusion in many more markets than only (near‐)symmetric ones. In addition, we show how the challenge of private demand information can be overcome by inferring demand data from public price data.

This paper also contributes to the axiomatic bargaining literature by elaborating how firms can collude on price in a pricing duopoly with multinomial logit demand. To the best of our knowledge, there appears to be no existing work that conducts this analysis. We take an axiomatic approach in the spirit of Roth (1979). Fischer and Normann (2019) study similar concepts for Cournot games.

Contributions and insights

The technical contributions of this paper are threefold. First, we analyze in detail three notions of collusion in a pricing duopoly with multinomial logit demand functions, based on different sets of axioms such as Pareto optimality and equal relative/absolute gains. We prove existence and uniqueness under different combinations of axioms, and show how these collusive prices can be computed up to arbitrary precision. We show that these collusive prices reduce consumer welfare and increase prices and revenues of both firms compared to the Nash equilibrium. Simulation results with parameter values based on empirical data show that these effects can be substantial.

Second, we construct a price algorithm and prove that prices converge to the implemented collusive solution if the algorithm is used by both players. Importantly, the players do not have to start the algorithm at the same moment, demand observations are allowed to be private information, and the players do not have to know that the opponent is using the same algorithm. If the algorithm plays against a competitive price rule, we prove that prices converge to a best response and provide asymptotically optimal regret bounds.

Third, we show how a competitor's private demand realizations can be inferred from public prices. This facilitates consistent estimation of the unknown model parameters and has the additional benefit that the players, under mutual use of our proposed algorithm, always base their decisions on the same sales data set. This enables players to immediately detect when the other firm deviates from the algorithm's price suggestions, strengthening the stability of the cartel.

Our technical results have several implications for competition regulation professionals. First, we show that two major challenges of firms to achieve algorithmic collusion can be overcome when they use the same algorithm. Hard‐coding a notion of collusion in an algorithm removes the need to communicate and agree on what it means to collude, which, according to Bos and Harrington (2010), is a critically difficult step in the formation of cartels. Furthermore, using the same algorithm enables the firms to “understand” each other's price decisions, so that, for example, price experiments aimed at guaranteeing learning the model parameters will not mistakenly be interpreted as “cheating” the cartel. In fact, deviation from the prices prescribed by the algorithm will immediately be detected by the competing firm, which strengthens the stability of the cartel.

Second, our examples of collusive solutions demonstrate that firms can be creative in what they mean by collusion, and can adopt definitions that are not necessarily on the radar of a regulator. Competition regulators should therefore not blindly focus on one particular notion of collusion (e.g., joint‐revenue maximization) but be on the lookout for any sustainable price pair that reduces consumer welfare and is beneficial for the firms.

Third, our mechanism to infer sales data from price paths reveals an important point related to communication: price paths contain and transfer information. Illicit communication between firms to establish collusion is forbidden by law (Harrington, 2018), but the fact that prices may signal information about, for example, a seller's parameter estimates or beliefs cannot always be avoided, and therefore does not constitute illegal communication per se. In our algorithm, information transfer is an “accidental” by‐product of the generated price decisions, which is used to overcome the challenge of private sales data and to learn the collusive price. Competition regulators may wish to reflect on whether this information transfer is a desirable property of prices generated by algorithms.

Organization of the paper

The rest of this paper is organized as follows. Subsection 2.1 describes the static pricing game under consideration. In Subsection 2.2, we consider several axiomatic notions of collusion, and prove results on existence and uniqueness. Subsection 2.3 provides comparisons with Nash prices, revenues, and consumer welfare. Subsection 3.1 extends the static game to a dynamic setting in which the demand functions are unknown upfront, and defines the concept of a price policy. Subsection 3.2 describes the algorithm that we propose. In Section 4, we analyze its performance against different types of competitors. Subsection 4.1 establishes that prices converge to the built‐in collusive solution when the algorithm is used by both firms in the duopoly, and provides a bound for the corresponding regret. In Subsection 4.2, we study the performance of our algorithm when pricing against a “true” competitor, and prove an asymptotically optimal regret bound. Subsection 4.3 provides numerical illustrations. A discussion and directions for future research are contained in Section 5. All mathematical proofs are collected in the Supporting Information, where we also discuss legal aspects of the proposed algorithm (Section EC.3 in the Supporting Information), consider the performance of alternative price rules against our policy (Section EC.4 in the Supporting Information), and explain that cheating the algorithm is difficult (Section EC.5 in the Supporting Information).

COLLUSION IN A STATIC PRICING DUOPOLY

In this section, we describe different definitions of collusion that firms could devise and implement in a price algorithm. Subsection 2.1 describes the static pricing game under consideration. Subsection 2.2 establishes that joint‐revenue maximization, a standard notion of collusion, is often not beneficial to both firms and therefore not always a suitable definition of collusion. We discuss alternative notions of collusion based on different axioms and prove that these are always beneficial to both firms and always diminish consumer welfare. Subsection 2.3 provides numerical results.

Static model

We consider a price‐setting duopoly where each firm sells exactly one product; firm one sells product one, firm two sells product two. The price charged for product

$j\in \{1,2\}$

is denoted by

$p_j\ge 0$

. We assume that the customer's purchase behavior follows the well‐known multinomial logit model, which means that the customer assigns a (random) utility

$$U_j(p_j;\mathit{\theta }):=a_j-b_j{p}_j+{\epsilon }_j$$

1

to each product j, and a (random) utility

$U_0:={\epsilon }_0$

to the no‐purchase option, where

$\mathit{\theta }=(a_1,b_1,a_2,b_2)$

is an underlying parameter from the parameter space

$\mathrm{\Theta }:=\mathbb{R}\times (0,\infty )\times \mathbb{R}\times (0,\infty )$

, and where ε₀, ε₁, and ε₂ are independent, mean zero Gumbel random variables with scale parameter one. Among the three purchase options, the customer chooses the one with the highest utility, with ties broken uniformly at random (note that ties occur with probability zero).

The exponential

$v_j(p_j;\mathit{\theta }):=\exp (a_j-b_j{p}_j)$

of the expected utility of product j is called its attraction value. The attraction value of the no‐purchase option equals 1. As derived by, for example, Gallego and Topaloglu (2019, p. 113), product j is purchased with probability

$${\lambda }_j(\mathbf{p};\mathit{\theta }):=\frac{v_j(p_j;\mathit{\theta })}{1+v_1(p_1;\mathit{\theta })+v_2(p_2;\mathit{\theta })},$$

2

and a no‐purchase takes place with probability

${\lambda }_0(\mathbf{p};\mathit{\theta }):=1-{\lambda }_1(\mathbf{p};\mathit{\theta })-{\lambda }_2(\mathbf{p};\mathit{\theta })$

, where

$\mathbf{p}=(p_1,p_2)$

denotes the pair of both prices. We set marginal costs to zero, so the (expected) revenue for firm j as a function of the charged prices is given by

$r_j(\mathbf{p};\mathit{\theta }):={\lambda }_j(\mathbf{p};\mathit{\theta })p_j$

.

For future reference, we now define the optimal monopoly prices (i.e., when there is no competitor), the Nash equilibrium prices, and the maximizer of the joint‐revenue function. Regarding the monopoly prices, Li and Huh (2011, Theorem 2 and Corollary 1) show that if firm j is a monopolist—which is equivalent to setting the competitor's price to infinity—there exists a unique revenue‐maximizing price

$$p_j^{M}ONO(\mathit{\theta }):=\frac{W_0(\exp (a_j-1))+1}{b_j},$$

3

where W ₀ denotes the 0th branch of the Lambert W function (see Section EC.1 in the Supporting Information for details). The optimal monopoly revenue for firm j is given by

$r_j^{M}ONO(\mathit{\theta })=W_0(\exp (a_j-1))/b_j$

.

Li and Huh (2011, Theorem 4) also show that the static pricing game has a unique Nash equilibrium

${\mathbf{p}}^{N}E(\mathit{\theta })=(p_1^{NE}(\mathit{\theta }),p_2^{NE}(\mathit{\theta }))$

given by

$$p_j^{N}E(\mathit{\theta }):=\frac{1}{b_j}·\frac{1}{1-{\lambda }_j^{N}E(\mathit{\theta })},$$

4

where

${\lambda }_j^{N}E(\mathit{\theta }):=V({\lambda }_0^{N}E(\mathit{\theta })·\exp (a_j-1))$

denotes the purchase probability for product j under the Nash equilibrium, and where the corresponding no‐purchase probability

${\lambda }_0^{NE}(\mathit{\theta })$

is the unique solution

$z\in (0,1)$

to the equation 

$z+V(z·\exp (a_1-1))+V(z·\exp (a_2-1))=1$

; here, for

$x>0$

,

$V(x)$

is the unique solution

$z\in (0,1)$

to the equation 

$z·\exp (z/(1-z))=x$

. The expected revenue for firm j under the Nash equilibrium price pair is denoted by

$r_j^{N}E(\mathit{\theta })$

.

Finally, Li and Huh (2011, Theorem 2) show that the joint‐revenue function

$\mathbf{p}\mapsto r_1(\mathbf{p};\mathit{\theta })+r_2(\mathbf{p};\mathit{\theta })$

has a unique maximizer

${\mathbf{p}}^{J}RM(\mathit{\theta })=(p_1^{JRM}(\mathit{\theta }),p_2^{JRM}(\mathit{\theta }))$

given by

$$p_j^{J}RM(\mathit{\theta }):=u+\frac{1}{b_j},$$

5

where u is the unique solution to the equation 

$u=\exp (a_1-1-b_{1}u)/b_1+\exp (a_2-1-b_{2}u)/b_2$

. The expected revenue for firm j under the joint‐revenue‐maximizing price pair is denoted by

$r_j^{J}RM(\mathit{\theta })$

.

We conclude this section with the following remarks regarding notation. For each

$j\in \{1,2\}$

, the notation

$\neg j$

denotes the only element in the set

$\{1,2\}\setminus \{j\}$

, that is, represents the competitor of firm j. Also, for all

$x,y\in \mathbb{R}$

, we use the notation

6

In some proofs, we omit the argument

$\mathit{\theta }$

for the underlying parameter if

$\mathit{\theta }$

is fixed within that context, that is, we write

$r_j(\mathbf{p})$

instead of

$r_j(\mathbf{p};\mathit{\theta })$

,

$p_j^{N}E$

instead of

$p_j^{N}E(\mathit{\theta })$

, and so forth. Finally, price pairs are understood to be elements of [0, ∞)² unless stated otherwise.

Notions of collusion

Joint‐revenue maximization

Collusion is frequently associated with—or even defined as—joint‐revenue maximization (Gal, 2019, p. 71, OECD, 2017b, p. 19, Schwalbe, 2018, p. 569). However, the concepts of collusion and joint‐revenue maximization are fundamentally different: from the perspective of an individual firm, the objective of collusion is to raise its own revenue to a supra‐competitive level, not to maximize joint revenue per se. Although maximizing joint revenue can sometimes increase revenues for all involved firms, this need not always be the case.

To illustrate this point, we generate 1 million instances of

$\mathit{\theta }=(a_1,b_1,a_2,b_2)$

and verify whether

$r_j^{J}RM(\mathit{\theta })<r_j^{N}E(\mathit{\theta })$

for some

$j\in \{1,2\}$

, where a ₁ and a ₂ are drawn uniformly at random from the interval [ − 1, 5], and where b ₁ and b ₂ are drawn uniformly at random from the interval [0.001, 0.019]. These sampling intervals are in line with the empirical work of Li et al. (2019), as well as the simulation framework of van de Geer and den Boer (2022)—which in turn is “in line with the empirical work of Delahaye et al. (2017) […] and the simulation framework of Rayfield et al. (2015)”. It turns out that in all except 19% of the parameter instances, the joint‐revenue‐maximizing price pair causes revenue losses compared to the Nash equilibrium for one of the two firms (see the rightmost column of Table 1). These losses are especially large in asymmetric markets—for example, when a ₁ and b ₂ are high, and a ₂ and b ₁ are low.

TABLE 1

Performance results of four different notions of collusion compared to the Nash equilibrium

Notion of collusion	RPO	APO	NB	JRM
Mutually profitable	100%	100%	100%	19%
Average increase in prices	49%	46%	46%	124%
Average increase in revenues	14%	18%	17%	0%
Average decrease in consumer welfare	30%	32%	31%	32%

This shows that in many cases (asymmetric) firms that are in principle willing to collude are unlikely to act on it if collusion is defined by charging joint‐revenue‐maximizing prices. This does not mean that such firms cannot collude: in what follows we show that there are alternative ways to define cartel prices that are always profitable for both firms.

Axiomatic notions of collusion

We refer to any function

$\psi :\mathrm{\Theta }\to {[0,\infty )}^2$

as a notion of collusion, which can be based on a variety of favorable axioms from the perspective of the firms. We consider the following axioms. AXIOM 1 Mutually beneficial

For all

$\mathit{\theta }\in \mathrm{\Theta }$

:

$r_j(\psi (\mathit{\theta });\mathit{\theta })>r^N{E}_j(\mathit{\theta })$

for each

$j\in \{1,2\}$

.

AXIOM 2 Pareto optimality

For all

$\mathit{\theta }\in \mathrm{\Theta }$

, there exists no price pair

$\mathbf{x}$

such that

$r_j(\mathbf{x};\mathit{\theta })\ge r_j(\psi (\mathit{\theta });\mathit{\theta })$

for each

$j\in \{1,2\}$

, with strict inequality for at least one j.

AXIOM 3 Equal relative gains

For all

$\mathit{\theta }\in \mathrm{\Theta }$

:

$r_1(\psi (\mathit{\theta });\mathit{\theta })/r_1^{N}E(\mathit{\theta })=r_2(\psi (\mathit{\theta });\mathit{\theta })/r_2^{N}E(\mathit{\theta })$

.

AXIOM 4 Equal absolute gains

For all

$\mathit{\theta }\in \mathrm{\Theta }$

:

$r_1(\psi (\mathit{\theta });\mathit{\theta })-r_1^{N}E(\mathit{\theta })=r_2(\psi (\mathit{\theta });\mathit{\theta })-r_2^{N}E(\mathit{\theta })$

.

Mutually beneficial notions of collusion provide strictly higher revenue than the Nash equilibrium, for each firm, regardless of the model parameters (in contrast to, for example, joint‐revenue maximization). Pareto optimality ensures that no additional revenue can be gained without harming the other firm. The axioms of equal relative/absolute gains prevent imbalances in the collusive surplus compared to the Nash equilibrium, thereby making the notion of collusion more mutually attractive.

In this section, we consider three notions of collusion that firms could construct. Two of these definitions are induced by taking different combinations of the axioms given above: the first notion of collusion is defined by Axioms 2 and 3, the second notion by Axioms 2 and 4. The axiomatic derivation of the third notion of collusion, the Nash bargaining solution, is given in Section EC.2 in the Supporting Information because the underlying axioms are based on a broader framework. All three notions of collusion under consideration are mutually beneficial (Axiom 1) and Pareto optimal (Axiom 2).

Before we analyze these notions of collusion, we prove a technical result about Pareto optimal price pairs; a price pair

$\mathbf{p}$

is called Pareto optimal for a parameter

$\mathit{\theta }\in \mathrm{\Theta }$

if there exists no price pair

$\mathbf{x}$

such that

$r_j(\mathbf{x};\mathit{\theta })\ge r_j(\mathbf{p};\mathit{\theta })$

for each

$j\in \{1,2\}$

, with strict inequality for at least one j. The following lemma characterizes the set of all Pareto optimal price pairs as the graph of a decreasing function on an open interval, and establishes that there do not exist two different Pareto optimal price pairs that give a firm the same amount of revenue. The proof mostly revolves around showing that Pareto optimal price pairs that provide a certain amount of revenue for one of the two firms are unique maximizers of certain functions. Lemma 1

Let

$\mathit{\theta }=(a_1,b_1,a_2,b_2)\in \mathrm{\Theta }$

and

$j\in \{1,2\}$

. A price pair

$\mathbf{p}$

is Pareto optimal for

$\mathit{\theta }$

if and only if both

$p_j>p_j^{M}ONO(\mathit{\theta })$

and

$p_{\neg j}=f^P{O}_{\neg j}(p_j;\mathit{\theta })$

, where, for

$x\in (p_j^{M}ONO(\mathit{\theta }),\infty )$

,

7

is a function that strictly decreases from ∞ to

$p_{\neg j}^{M}ONO(\mathit{\theta })$

on its domain. Furthermore, for any

$\stackrel{\sim }{r}\in (0,r_j^{M}ONO(\mathit{\theta }))$

there exists a unique price pair

$\mathbf{p}$

with

$r_j(\mathbf{p};\mathit{\theta })=\stackrel{\sim }{r}$

that is Pareto optimal for

$\mathit{\theta }$

.

We now consider the three aforementioned axiomatic notions of collusion in detail. Our first theorem shows that the axioms of Pareto optimality and equal relative gains uniquely define a notion of collusion, denoted by

${\psi }^{R}PO$

(R for relative, PO for Pareto optimal), and establishes that

${\psi }^{R}PO$

is smooth and mutually beneficial. Because each function value

${\psi }^{R}PO(\mathit{\theta })$

is the unique zero of a strictly decreasing function, it can be computed to arbitrary precision with a bisection algorithm. Theorem 1

There exists a unique notion of collusion

${\psi }^{R}PO$

that satisfies both Axiom 2 (Pareto optimality) and Axiom 3 (equal relative gains). For all

$\mathit{\theta }\in \mathrm{\Theta }$

and each

$j\in \{1,2\}$

, it holds that

${\psi }_j^{R}PO(\mathit{\theta })$

is the unique zero of the continuous function

8

which strictly decreases from a positive value to a negative value on its domain

$(p_j^{M}ONO(\mathit{\theta }),\infty )$

. Moreover,

${\psi }^{R}PO$

is infinitely differentiable and mutually beneficial (Axiom 1).

To prove the theorem, we deduce from Lemma 1 that the revenue of firm j strictly decreases from the optimal monopoly value to zero along the graph of the function defined in (7), whereas the opponent's revenue strictly increases in the reversed direction. Consequently, the function defined in (8) strictly decreases from a positive value to a negative value. This guarantees the existence of a unique zero, which in turn ensures existence and uniqueness of a Pareto optimal notion of collusion that provides equal relative gains. Because the Nash equilibrium is not Pareto optimal it follows that

${\psi }^{R}PO$

is mutually beneficial. Smoothness follows from two subsequent applications of the implicit function theorem; first to show infinite differentiability of the function

$\mathit{\theta }\mapsto {\mathbf{p}}^{N}E(\mathit{\theta })$

, and then of

${\psi }^{R}PO$

.

Our next result shows that the axioms of Pareto optimality and equal absolute gains uniquely define a notion of collusion, denoted by

${\psi }^{A}PO$

(A for absolute, PO for Pareto optimal), and establishes that

${\psi }^{A}PO$

is smooth and mutually beneficial. Function values can again be approximated to arbitrary precision using a bisection algorithm. The proof of Theorem 2 is of a similar structure as the proof of Theorem 1. Theorem 2

There exists a unique notion of collusion

${\psi }^{A}PO$

that satisfies both Axiom 2 (Pareto optimality) and Axiom 4 (equal absolute gains). For all

$\mathit{\theta }\in \mathrm{\Theta }$

and each

$j\in \{1,2\}$

it holds that

${\psi }_j^{A}PO(\mathit{\theta })$

is the unique zero of the continuous function

9

which strictly decreases from a positive value to a negative value on its domain

$(p_j^{M}ONO(\mathit{\theta }),\infty )$

. Moreover,

${\psi }^{A}PO$

is infinitely differentiable and mutually beneficial (Axiom 1).

The third and final notion of collusion that we consider is the Nash bargaining solution, denoted by

${\psi }^{N}B$

, where, for all

$\mathit{\theta }\in \mathrm{\Theta }$

,

${\psi }^{N}B(\mathit{\theta })$

is defined as the maximizer of the function

$$\begin{array}{c}\hfill \mathbf{p}\mapsto f^{N}B(\mathbf{p};\mathit{\theta }):=\left(r_1(\mathbf{p};\mathit{\theta })-r_1^{N}E(\mathit{\theta })\right)\left(r_2(\mathbf{p};\mathit{\theta })-r_2^{N}E(\mathit{\theta })\right)\end{array}$$

10

on the domain

$\mathcal{P}(\mathit{\theta }):=\{\mathbf{p}\in {[0,\infty )}^2:r_1(\mathbf{p};\mathit{\theta })>r_1^{N}E(\mathit{\theta })\text{and}{r}_2(\mathbf{p};\mathit{\theta })>r_2^{N}E(\mathit{\theta })\}$

. This notion of collusion is uniquely defined by assuming Pareto optimality, symmetry, and the independence of irrelevant alternatives property (see Section EC.2 in the Supporting Information for details). Theorem 3 establishes that

${\psi }^{N}B$

is well‐defined, and characterizes every function value

${\psi }^{N}B(\mathit{\theta })$

as the unique maximizer of a strictly log‐concave function on a convex domain, which implies that it can be computed to arbitrary precision using a gradient ascent method. The theorem also establishes smoothness properties and that the Nash bargaining solution satisfies Axioms 1 and 2. Theorem 3

Let

$\mathit{\theta }\in \mathrm{\Theta }$

. There exists a unique price pair that maximizes the function

$\mathbf{p}\mapsto f^{N}B(\mathbf{p};\mathit{\theta })$

on

$\mathcal{P}(\mathit{\theta })$

. The domain

$\mathcal{P}(\mathit{\theta })$

is a (nonempty) convex set, and the function

$\mathbf{p}\mapsto f^{N}B(\mathbf{p};\mathit{\theta })$

is strictly log‐concave on

$\mathcal{P}(\mathit{\theta })$

. The notion of collusion

${\psi }^{N}B$

is infinitely differentiable, mutually beneficial (Axiom 1), and Pareto optimal (Axiom 2).

To prove Theorem 3, we first establish that the revenue functions

$\mathbf{p}\mapsto r_j(\mathbf{p};\mathit{\theta })$

are strictly log‐concave by explicitly computing the Hessians and showing that they are negative definite. This allows us to derive that the function

$\mathbf{p}\mapsto f^{N}B(\mathbf{p};\mathit{\theta })$

is strictly log‐concave, and that its domain

$\mathcal{P}(\mathit{\theta })$

is convex; these properties in turn ensure existence and uniqueness of the maximizer. We then recall that the Nash equilibrium is not Pareto optimal, which implies that

$\mathcal{P}(\mathit{\theta })$

is nonempty, and thus shows that

${\psi }^{N}B$

is mutually beneficial. Pareto optimality of

${\psi }^{N}B$

follows immediately from the observation that a Pareto improvement of

${\psi }^{N}B(\mathit{\theta })$

would give a strictly higher value of

$f^{N}B$

. Finally, infinite differentiability of

${\psi }^{N}B$

follows by applying the implicit function theorem to the gradient of the logarithm of

$f^{N}B$

.

Effects of collusion on prices, revenues, and consumer welfare

We measure consumer welfare (CW) by the expected post‐purchase utility obtained by the consumer:

$$\begin{array}{c}\hfill CW(\mathbf{p};\mathit{\theta }):=\mathbb{E}[\max \{U_0,U_1(p_1;\mathit{\theta }),U_2(p_2;\mathit{\theta })\}],\end{array}$$

11

for any underlying parameter

$\mathit{\theta }\in \mathrm{\Theta }$

and any price pair

$\mathbf{p}$

charged by the firms. Our next result shows that Pareto optimal price pairs are detrimental to consumers because they are component‐wise strictly higher than the Nash equilibrium price pair, and strictly reduce consumer welfare compared to the Nash equilibrium. Consequently, Pareto optimal notions of collusion are a threat to consumers; this includes the three examples from Subsection 2.2.2. Theorem 4

Let

$\mathit{\theta }\in \mathrm{\Theta }$

. For any price pair

$\mathbf{p}$

, it holds that

$CW(\mathbf{p};\mathit{\theta })=-\ln ({\lambda }_0(\mathbf{p};\mathit{\theta }))$

. Moreover, if

$\mathbf{p}$

is Pareto optimal for

$\mathit{\theta }$

, then

$p_j>p_j^{N}E(\mathit{\theta })$

for each

$j\in \{1,2\}$

, and

$CW(\mathbf{p};\mathit{\theta })<CW({\mathbf{p}}^{N}E(\mathit{\theta });\mathit{\theta })$

.

In the proof of Theorem 4, we derive that

$CW(\mathbf{p};\mathit{\theta })$

is Gumbel distributed with mean

$-\ln ({\lambda }_0(\mathbf{p};\mathit{\theta }))$

and scale parameter one. We then show that the optimal monopoly prices are strictly higher than the Nash equilibrium prices, which means that Pareto optimal price pairs are component‐wise strictly higher than the Nash equilibrium price pair due to Lemma 1. The result regarding reduced consumer welfare directly follows because the no‐purchase probability is a strictly increasing function of both prices.

To obtain more insight into the effects of collusion on prices, revenues, and consumer welfare, we now perform a simulation. We generate 1 million instances of

$\mathit{\theta }=(a_1,b_1,a_2,b_2)$

, with a ₁ and a ₂ drawn uniformly at random from the interval [ − 1, 5], and with b ₁ and b ₂ drawn uniformly at random from the interval [0.001,0.019]. For each instance we compute the relative increase in prices and revenues, and the relative decrease in consumer welfare (compared to the Nash equilibrium) under RPO, APO, NB, and JRM; Table 1 reports the averages.

The results from Table 1 show that RPO, APO, and NB have roughly equivalent effects on prices, revenues, and consumer welfare, whereas JRM performs rather differently. First, JRM is mutually profitable compared to the Nash equilibrium in only 19% of the cases; this is in stark contrast with the 100% for the other collusive solutions. Second, the average effect on revenues is 0%; this is because JRM is not a mutually beneficial notion of collusion, so that revenues can in fact decrease by switching from the Nash equilibrium to JRM. Third, the average effect of JRM on prices is much more extreme than for the other notions of collusion, but because these enormous price increases generally do not occur for both firms simultaneously, consumer welfare is affected by roughly the same amount as the other notions of collusion.

COLLUSION AND COMPETITION IN A DYNAMIC PRICING DUOPOLY

We now consider a sequential version of the pricing game where the parameters are initially unknown to the firms. Subsection 3.1 extends the model from Section 2 to this dynamic setting and provides the definition of a policy. In Subsection 3.2, we propose an algorithm called Collude‐or‐Compete that guarantees convergence to a built‐in notion of collusion when used by both players, and performs optimally against a class of alternative policies that a competitor might deploy.

Dynamic model

We consider a dynamic version of the static duopoly game introduced in Subsection 2.1. Although the firms can in principle change their selling prices at any instant, we divide the time horizon into periods and model the firms' pricing behavior as a discrete‐time simultaneous‐move game, as is common in the literature (see, e.g., Akçay et al., 2010, Cooper et al., 2015, Li & Huh, 2011, Maglaras & Meissner, 2006). This means that we divide the time horizon [0, ∞) into subsequent periods

$[t-1,t)$

of equal length, where the time unit is chosen small enough to ensure that the probability of two or more customers arriving in the same period is negligible, and assume that both players update their prices at the start of each period (cf. Talluri & van Ryzin, 2004, p. 58).

Let

$p_j(s)$

be the price charged by firm

$j\in \{1,2\}$

during the sth period

$[s-1,s)$

, for

$s\in \mathbb{N}$

, and write

$\mathbf{p}(s):=(p_1(s),p_2(s))$

for the corresponding price pair. Demand again follows the multinomial logit model, that is, if

$\mathit{\theta }\in \mathrm{\Theta }$

is the underlying parameter, the probability that a unit of product j is purchased during the sth period, given the price pair

$\mathbf{p}(s)$

, is given by

${\lambda }_j(\mathbf{p}(s);\mathit{\theta })$

. The probability of a no‐purchase is given by

${\lambda }_0(\mathbf{p}(s);\mathit{\theta })$

. The (expected) revenue for firm j during the sth period, given the price pair

$\mathbf{p}(s)$

, is given by

$r_j(\mathbf{p}(s);\mathit{\theta })$

. There exists a “true” underlying parameter

${\mathit{\theta }}^{\ast }$

, which is unknown to both firms but lies in a known convex and compact set

$\mathrm{\Xi }\subset \mathrm{\Theta }$

. Finally, let

$\psi :\mathrm{\Theta }\to {[0,\infty )}^2$

be a notion of collusion that is Lipschitz‐continuous on Ξ, for example one of the notions discussed in Subsection 2.2.2.

Let

${\mathcal{F}}_{0,j}$

be the trivial σ‐algebra. Denote the demand for product j during the sth period by

$d_j(s)\in \{0,1\}$

, and let

${\mathcal{F}}_{s,j}:=\sigma (\mathbf{p}(1),d_j(1),\text{…},\mathbf{p}(s),d_j(s))$

be the σ‐algebra generated by the price pairs and firm j's demand observations up to the sth period. We call

${(p_j(s))}_{s\in \mathbb{N}}$

a price policy or algorithm for firm j if

$p_j(s)$

is

${\mathcal{F}}_{s-1,j}$

‐measurable for all

$s\in \mathbb{N}$

.

Collude‐or‐compete

We propose a dynamic price algorithm called Collude‐or‐Compete, which by design is able to switch between two policies, or modules. One of these policies (the collusive policy) is designed to guarantee convergence of prices to the collusive solution

$\psi ({\mathit{\theta }}^{\ast })$

if used by both firms and activated simultaneously, and is described in Subsection 3.2.1. Use of this policy requires demand information of both firms; we describe in Subsection 3.2.2 how the competitor's (private) demand realizations can be extracted from (public) prices. Subsection 3.2.3 introduces the other policy (the competitive policy), which is designed to optimize revenue when playing against a wide range of policies that an opponent could deploy. Subsection 3.2.4 describes how the Collude‐or‐Compete algorithm switches between the two modules based on the competitor's price path, and shows how simultaneous activation of the collusive module is guaranteed if the algorithm is used by both firms. Subsection 3.2.5 provides a comprehensive formulation of the proposed algorithm.

Collusive policy

The collusive policy is based on ideas from den Boer and Zwart (2014). The key idea is to iteratively approximate

${\mathit{\theta }}^{\ast }$

using maximum‐likelihood estimation and charge the estimated collusive price, possibly with a perturbation added to ensure consistency of the parameter estimates.

In particular, if firm j activates the collusive policy at time

$\tau \ge 0$

, it starts by charging

$p_j(\tau +1)=p_{start,j}$

and

$p_j(\tau +2)={\kappa }_1{p}_{start,j}$

, where the initial price

$p_{start,j}>0$

is an input parameter and where

${\kappa }_1\in (0,1)$

. For every subsequent period

$t\ge \tau +3$

, the collusive policy uses the maximizer

${\widehat{\mathit{\theta }}}_{t-1}$

of the likelihood function

12

on Ξ; the following lemma establishes existence and uniqueness. Lemma 2

Let

$t\ge \tau +3$

. If

$p_k(\tau +1)\ne p_k(\tau +2)$

for each

$k\in \{1,2\}$

, then there exists a unique maximizer of

$L_{t-1}$

on Ξ.

To ensure consistency of the parameter estimates, the policy imposes for every

$t\ge \tau +2$

that the sample variance of firm j's prices satisfies

$$\begin{array}{c}\hfill Var(p_j(\tau +1),\text{…},p_j(t))\ge c_j{(t-\tau )}^{{\kappa }_0},\end{array}$$

13

where

${\kappa }_0\in (-1,0)$

and

$c_j:=2^{-2-{\kappa }_0}{(p_{start,j})}^2{({\kappa }_1-1)}^2$

, and where the sample variance is defined by

14

It achieves this by charging the estimated collusive price

${\psi }_j({\widehat{\mathit{\theta }}}_{t-1})$

, for all

$t\ge \tau +3$

, unless this would imply that the lower bound (13) on the sample variance of the prices is not satisfied. In that case, the next price should be chosen not too close to the average of the prices charged thus far. To this end, we define a taboo interval around the average price, and perturb the estimated collusive price if it falls within the taboo interval. In particular, the taboo interval is given by

15

where the half‐width

${\mu }_j(t)$

is given by

$$\begin{array}{c}\hfill {\mu }_j(t):=\sqrt{c_j\left({(t-\tau )}^{1+{\kappa }_0}-{(t-\tau -1)}^{1+{\kappa }_0}\right)\frac{t-\tau }{t-\tau -1}}.\end{array}$$

16

The price that the collusive policy charges for firm j during the tth period, for

$t\ge \tau +3$

, is given by ¹

$$\begin{array}{c}\hfill DCV{P}_j(t):={\psi }_j({\widehat{\mathit{\theta }}}_{t-1})+{\delta }_j(t),\end{array}$$

17

where the price perturbation

${\delta }_j(t)$

is given by

$$\begin{array}{c}\hfill {\delta }_j(t):=2{\mu }_j(t)\mathbb{1}\{{\psi }_j({\widehat{\mathit{\theta }}}_{t-1})\in T{I}_j(t)\}.\end{array}$$

18

Remark 1

The values of κ₀ and κ₁ are hard‐coded into the algorithm by the software developer, cannot be altered by the user, and are the same for all users. We show in Subsection 4.1 that the choice

${\kappa }_0=-1/2$

leads to asymptotically optimal performance. The choice of κ₁ can be market‐dependent.

Extracting demand information from prices

Computing the prices determined by the collusive policy requires demand observations from both firms. We explain in this section how the competitor's demand realizations can be inferred from their price path. The key feature underlying our inference process is that different demand observations by the competitor correspond to different selling prices. Using the same price algorithm as the competitor enables one to “reverse engineer” the (private) demand data that has resulted in the (public) selling prices. By continuously applying this procedure, both users of the algorithm ensure that they base their decisions on the same data set consisting of price and demand data. As a result, from an informational viewpoint, the situation is then equivalent to the situation where demand information is publicly available.

We now explain in more detail the mechanism of demand inference from price paths that is incorporated in the Collude‐or‐Compete algorithm. This mechanism utilizes that both firms use the algorithm and are synchronized, that is, that they simultaneously activate the collusive module at some time τ—we explain in Subsection 3.2.4 that synchronization is guaranteed per construction of the algorithm. The mechanism is based on the following idea. If firm j observes demand

$d_j(t)=1$

, then she knows with certainty that

$d_{\neg j}(t)=0$

. On the other hand, if firm j observes no demand, that is,

$d_j(t)=0$

, then both

$d_{\neg j}(t)=0$

and

$d_{\neg j}(t)=1$

are possible. For both of these cases, firm j computes the corresponding maximum‐likelihood estimate and the corresponding prices that the collusive policy would set for each firm, ² and sets her own price

$p_j(t+1)$

assuming that

$d_{\neg j}(t)=0$

. After observing

$p_{\neg j}(t+1)$

, firm j immediately adapts her price if

$p_{\neg j}(t+1)$

reveals that

$d_{\neg j}(t)=1$

. We now describe the mechanism in more detail.

At the beginning of each period

$t+1$

, where

$t\ge \tau +3$

, firm j computes the maximizers

${\widehat{\mathit{\theta }}}_{t,j}^{(0,0)}$

,

${\widehat{\mathit{\theta }}}_{t,j}^{(0,1)}$

,

${\widehat{\mathit{\theta }}}_{t,j}^{(1,0)}$

of the likelihood function

$L_t$

on Ξ, corresponding to each of the three demand possibilities

$(d_j(t),d_{\neg j}(t))\in \{(0,0),(0,1),(1,0)\}$

. She also computes the prices that the collusive policy would set,

$(p_j^{(0,0)}(t+1),p_{\neg j}^{(0,0)}(t+1))$

,

$(p_j^{(0,1)}(t+1),p_{\neg j}^{(0,1)}(t+1))$

,

$(p_j^{(1,0)}(t+1),p_{\neg j}^{(1,0)}(t+1))$

, corresponding to each of these three possibilities. If

$d_j(t)=1$

, then firm j sets

$p_j(t+1)=p_j^{(1,0)}(t+1)$

. If

$d_j(t)=0$

, then firm j assumes that

$d_{\neg j}(t)=0$

and sets

$p_j(t+1)=p_j^{(0,0)}(t+1)$

; but, once firm j observes that

$p_{\neg j}(t+1)=p_{\neg j}^{(0,1)}(t+1)$

, firm j infers that

$d_{\neg j}(t)=1$

and immediately changes her price to

$p_j(t+1)=p_j^{(0,1)}(t+1)$

. In this way, firm j can reconstruct

$d_{\neg j}(t)$

for all

$t\ge \tau +3$

.

The competitor's demand during periods

$\tau +1$

and

$\tau +2$

are inferred from

$p_{\neg j}(\tau +3)$

in a similar manner. In particular, before determining

$p_j(\tau +3)$

, firm j computes the maximizers

${\widehat{\mathit{\theta }}}_{\tau +2,j}^{(x_1,y_1),(x_2,y_2)}$

of the likelihood function

$L_{\tau +2}$

on Ξ, now corresponding to each of the nine demand possibilities

$(d_j(\tau +1),d_{\neg j}(\tau +1))=(x_1,y_1)$

and

$(d_j(\tau +2),d_{\neg j}(\tau +2))=(x_2,y_2)$

, where

$(x_1,y_1),(x_2,y_2)\in \{(0,0),(0,1),(1,0)\}$

. She also computes the prices that the collusive policy would set,

$(p_j^{(x_1,y_1),(x_2,y_2)}(\tau +3),p_{\neg j}^{(x_1,y_1),(x_2,y_2)}(\tau +3))$

, corresponding to each of these nine possibilities. Then, at the start of period

$\tau +3$

, firm j assumes that

$(d_{\neg j}(\tau +1),d_{\neg j}(\tau +2))=(0,0)$

and sets

$p_j(\tau +3)=p_j^{(d_j(\tau +1),0),(d_j(\tau +2),0)}(\tau +3)$

; but, once firm j observes that

$p_{\neg j}(\tau +3)=p_{\neg j}^{(0,y_1),(0,y_2)}(\tau +3)$

for some

$(y_1,y_2)\in \{(1,1),(0,1),(1,0)\}$

with

$d_j(\tau +1)+y_1\le 1$

and

$d_j(\tau +2)+y_2\le 1$

, firm j infers that

$(d_{\neg j}(\tau +1),d_{\neg j}(\tau +2))=(y_1,y_2)$

and immediately changes her price to

$p_j(\tau +3)=p_j^{(d_j(\tau +1),y_1),(d_j(\tau +2),y_2)}(\tau +3)$

.

This mechanism, to infer (private) demand information from (public) selling prices, hinges on two assumptions: a technical and a mathematical one. On the technical side, we need to assume that the time (say,

$\epsilon \in (0,1)$

time units) required to observe the competitor's price and potentially adapt one's price in response to this observation, is sufficiently small such that the probability of a customer arrival during

$[t,t+\epsilon )$

is negligible. Whether this is possible in practice is difficult to determine without being engaged in actual implementation; at the same time, it is not obvious that it is technically impossible, now or in the near future. Investigating the technical feasibility of this scheme is therefore an important direction for future research, but outside the scope of this paper.

The second assumption underlying our demand inference scheme is that different demand observations correspond to different prices. Formally stated, the mechanism works if, with probability one,

$p_{\neg j}^{(0,0)}(t+1)\ne p_{\neg j}^{(0,1)}(t+1)$

for all

$t\ge \tau +3$

, as well as

$p_{\neg j}^{(0,y_1),(0,y_2)}(\tau +3)\ne p_{\neg j}^{(0,{\stackrel{\sim }{y}}_1),(0,{\stackrel{\sim }{y}}_2)}(\tau +3)$

for all distinct

$(y_1,y_2),({\stackrel{\sim }{y}}_1,{\stackrel{\sim }{y}}_2)\in \{(0,0),(0,1),(1,0),(1,1)\}$

. We have unfortunately not been able to formally prove this property, and we believe that this constitutes a relevant question for future research. On the other hand, throughout all our simulations we observed not a single instance that violated this condition. We conjecture that the required conditions needed to infer demand from price paths are satisfied, and in the rest of the paper we assume that this is the case.

Competitive policy

The competitive policy is based on ideas from Broadie et al. (2011). The idea is to maximize the (unknown) revenue function using a stochastic gradient ascent method introduced by Kiefer and Wolfowitz (1952), which applies price perturbations around a so‐called pivot price to obtain a local estimate of the derivative, and updates the pivot price accordingly. Choosing appropriate perturbation sizes and step sizes between subsequent pivot prices ensures convergence of prices to the maximizer of the revenue function.

In particular, from the perspective of firm j, the competitive policy divides the time horizon into consecutive cycles, each cycle consisting of two subsequent time periods: in the nth cycle, for

$n\in \mathbb{N}$

, it charges the price

$p_j^{(n)}+{\beta }_{n,j}$

during the first period, and

$p_j^{(n)}-{\beta }_{n,j}$

during the second period, where

$p_j^{(n)}$

is called the nth pivot price. The price perturbations are given by

$$\begin{array}{c}\hfill {\beta }_{n,j}:=K_{\beta ,j}/n^{1/4},\end{array}$$

19

where

$K_{\beta ,j}$

is a positive constant. We require that

$K_{\beta ,j}<p_{\max ,j}/2$

, where

$$\begin{array}{c}\hfill p_{\max ,j}:=\underset{p\ge 0,\mathit{\theta }\in \mathrm{\Xi }}{sup}\{B{R}_j(p;\mathit{\theta })\}\end{array}$$

20

determines a price ceiling for the competitive policy, and where, for all

$\mathit{\theta }=(a_1,b_1,a_2,b_2)\in \mathrm{\Theta }$

and

$p\ge 0$

,

$$\begin{array}{c}\hfill B{R}_j(p;\mathit{\theta }):=\frac{1}{b_j}\left(W_0\left(\frac{\exp (a_j-1)}{1+\exp (a_{\neg j}-b_{\neg j}p)}\right)+1\right)\end{array}$$

21

denotes the best‐response price of firm j given that her opponent charges the price p (see Section EC.12 in the Supporting Information for the derivation). The demand observations from these two periods, say, periods t and

$t+1$

, are used to compute the next pivot price

$$\begin{array}{c}\hfill p_j^{(n+1)}:={\mathrm{\Pi }}_{n+1}\left(p_j^{(n)}+{\alpha }_{n,j}\left(\frac{(p_j^{(n)}+{\beta }_{n,j})d_j(t)-(p_j^{(n)}-{\beta }_{n,j})d_j(t+1)}{{\beta }_{n,j}}\right)\right),\end{array}$$

22

where

${\mathrm{\Pi }}_{n+1,j}$

denotes the Euclidean projection function onto the interval

$[{\beta }_{n+1,j};p_{\max ,j}-{\beta }_{n+1,j}]$

, and where the “step sizes” are given by

$$\begin{array}{c}\hfill {\alpha }_{n,j}:=K_{\alpha ,j}/n,\end{array}$$

23

with

$K_{\alpha ,j}$

a positive constant. The projection step ensures that the prices charged by the policy are contained in the interval

$[0,p_{\max ,j}]$

. The constants

$K_{\alpha ,j}$

and

$K_{\beta ,j}$

, as well as the initial pivot price

$p_j^{(1)}\in [{\beta }_{1,j};p_{\max ,j}-{\beta }_{1,j}]$

, are input parameters that can be chosen by firm j.

Switching between modules and achieving synchronization

In this section, we explain how the Collude‐or‐Compete algorithm switches between the collusive policy and the competitive policy based on the opponent's price path. We speak of the collusive/competitive “module” instead of “policy” when we view it as part of the overarching Collude‐or‐Compete algorithm, and not as a stand‐alone policy.

The algorithm always starts by running the collusive module; but, as soon as the opponent charges a price that cannot be the output of the collusive module, the algorithm immediately switches to the competitive module. The first time that the competitive module is activated, it runs

$K_{\gamma ,j}$

Kiefer–Wolfowitz cycles (for firm j), where

$K_{\gamma ,j}\in \mathbb{N}$

is an input parameter. After that, the algorithm (temporarily) switches back to the collusive module. The goal of this is to make collusion possible if the opponent recently started using the Collude‐or‐Compete algorithm. But, again, when the opponent deviates from the prices determined by the collusive module, the algorithm immediately switches back to the competitive module, continuing with the

$(n+1)$

th cycle if it last performed the nth cycle. The mth time that the competitive module is activated it runs

$m{K}_{\gamma ,j}$

cycles before activating the collusive module again. The “batch size” is increased in this manner to ensure that the collusive module runs less frequently over time (relative to the competitive module) against an opponent that does not use the same algorithm.

If both firms use the Collude‐or‐Compete algorithm, their collusive modules need to be activated simultaneously in order for prices to converge to the collusive solution

$\psi ({\mathit{\theta }}^{\ast })$

. To achieve this, the algorithm can activate the collusive module prematurely, overriding the aforementioned routine of switching between modules. On a high level the mechanism works as follows. Suppose that both firms use the Collude‐or‐Compete algorithm, consider the perspective of firm j, and let the mth phase be the time interval between the mth and

$(m+1)$

th moment in time that firm

$\neg j$

activates the collusive module. The start of a phase is marked by two prices charged subsequently by firm

$\neg j$

that have a ratio of κ₁, and concludes with a certain number of Kiefer–Wolfowitz cycles. ³ Because these prices are highly structured, firm j can recognize when her opponent performs a phase, but does not know the duration of the phase in advance. However, after observing two subsequent phases, firm j can infer from the opponent's price path that the opponent ran

$mk$

and

$(m+1)k$

Kiefer–Wolfowitz cycles during the subsequent phases, in that order, for some

$m,k\in \mathbb{N}$

. This reveals to firm j that

$K_{\gamma ,\neg j}=k$

, and therefore reveals that the next phase contains

$(m+2)k$

Kiefer–Wolfowitz cycles. This enables firm j to exactly determine the starting time of phase

$m+3$

in advance, allowing her to activate the collusive module at exactly this time.

Formally, the mechanism is as follows. Suppose that there exist

$t,n\ge 0$

,

$K>0$

, and

$m,k\in \mathbb{N}$

such that

24

25

26

27

then firm j activates the collusive module at time

$t+6+2(3m+3)k$

.

The first equality in (24) indicates activation of the collusive module by firm

$\neg j$

at time t, and (25) indicates

$mk$

Kiefer–Wolfowitz cycles starting at time

$t+2$

, concluding phase m. Similarly, phase

$m+1$

corresponds to the second inequality in (24) combined with (26); this phase starts at time

$t+2+2mk$

and ends at time

$t+4+2(2m+1)k$

. At time

$t+6+2(2m+1)k$

, two periods after the end of the previous phase, firm j has observed the third activation of the collusive module by firm

$\neg j$

(from time t onward), therefore knows that two phases have been completed, and is thus able to infer the values of

$k,m$

and that

$K_{\gamma ,\neg j}=k$

. At this point, firm j knows that her opponent will now run

$(m+2)k$

Kiefer–Wolfowitz cycles (which can be confirmed using (27)) and will activate the collusive module at time

$t+6+2(3m+3)k$

.

In the rest of the paper, we suppose that the synchronization mechanism is implemented in full generality in a function

${\mathtt{SYNC}}_j$

; for all

$t\ge 0$

,

${\mathtt{SYNC}}_j(t)$

equals 1 if the synchronization mechanism dictates that firm j should activate the collusive module at time t, and equals 0 otherwise.

Comprehensive formulation of the algorithm

In the preceding sections, we have described in detail the individual components of our algorithm. In the current section, we synthesize these into a compact description of the complete algorithm. We take the perspective of firm j. In the description we write

$p_{j,\epsilon }(s)$

for the price charged by firm j during

$[s-1,s-1+\epsilon )$

and

$p_j(s)$

for the price charged during

$[s-1+\epsilon ,s)$

, for all

$s\ge 0$

, where ε denotes the time required to observe the competitor's price and potentially adapt one's price in response to this observation (see Subsection 3.2.2).

Collude‐or‐Compete algorithm $C{C}_j(p_{start,j};p_j^{(1)};K_{\alpha ,j};K_{\beta ,j};K_{\gamma ,j})$ (A) Initialize parameters and state variables. Let $K_{\gamma ,j}\in \mathbb{N}$ and $p_{start,j},p_j^{(1)},K_{\alpha ,j},K_{\beta ,j}>0$ such that $K_{\beta ,j}<p_{\max ,j}/2$ and $p_j^{(1)}\in [K_{\beta ,j};p_{\max ,j}-K_{\beta ,j}]$ . Additionally, let $k:=0$ , $\gamma :=K_{\gamma ,j}$ , and let τ be the time at which firm j has activated the Collude‐or‐Compete algorithm. (B) Run the collusive module. Charge $p_j(\tau +1)=p_{start,j}$ . If ${\mathtt{SYNC}}_j(\tau +1)=1$ , let $\tau :=\tau +1$ and go to part B. Charge $p_j(\tau +2)={\kappa }_1{p}_{start,j}$ . If ${\mathtt{SYNC}}_j(\tau +2)=1$ , let $\tau :=\tau +2$ and go to part B. If $p_{\neg j}(\tau +2)/p_{\neg j}(\tau +1)\ne {\kappa }_1$ , let $\tau :=\tau +2$ and go to part C. Charge $p_{j,\epsilon }(\tau +3)=p_j^{(d_j(\tau +1),0),(d_j(\tau +2),0)}(\tau +3)$ . If $p_{\neg j,\epsilon }(\tau +3)=p_{\neg j}^{(0,y_1),(0,y_2)}(\tau +3)$ for some $(y_1,y_2)\in \{(0,0),(1,1),(0,1),(1,0)\}$ with $d_j(\tau +1)+y_1\le 1$ and $d_j(\tau +2)+y_2\le 1$ , charge $p_j(\tau +3)=p_j^{(d_j(\tau +1),y_1),(d_j(\tau +2),y_2)}(\tau +3)$ , store the demand data $d_{\neg j}(\tau +1)=y_1$ , $d_{\neg j}(\tau +2)=y_2$ for future computations, let $t:=\tau +3$ and go to part B1. Otherwise, charge $p_j(\tau +3)=p_{j,\epsilon }(\tau +3)$ , let $\tau :=\tau +3$ and go to part C. (B1) Main loop of the collusive module. Charge $p_{j,\epsilon }(t+1)=p_j^{(d_j(t),0)}(t+1)$ . If $p_{\neg j,\epsilon }(t+1)=p_{\neg j}^{(0,y)}(t+1)$ for some $y\in \{0,1\}$ with $d_j(t)+y\le 1$ , charge $p_j(t+1)=p_j^{(d_j(t),y)}(t+1)$ , store the demand data $d_{\neg j}(t)=y$ for future computations, let $t:=t+1$ and repeat part B1. Otherwise, charge $p_j(t+1)=p_{j,\epsilon }(t+1)$ , let $\tau :=t+1$ and go to part C. (C) Run the competitive module. Let $t:=\tau$ and $n:=k+1$ . (C1) Main loop of the competitive module. If ${\mathtt{SYNC}}_j(t)=1$ , let $\tau :=t$ and go to part B. Charge $p_j(t+1)=p_j^{(n)}+K_{\beta ,j}/n^{1/4}$ . If ${\mathtt{SYNC}}_j(t+1)=1$ , let $\tau :=t+1$ and go to part B. Charge $p_j(t+2)=p_j^{(n)}-K_{\beta ,j}/n^{1/4}$ . Let $t:=t+2$ . If $n-k=\gamma$ , let $k:=k+\gamma$ , $\gamma :=\gamma +K_{\gamma ,j}$ , $\tau :=t$ and go to part B. Otherwise, let $n:=n+1$ and repeat part C1.

Part A initializes the hyper‐parameters of the algorithm. It also introduces three state variables: τ keeps track of when the algorithm switches between modules, k stores how many Kiefer–Wolfowitz cycles have been executed so far, and γ determines how many cycles the competitive module needs to run the next time it is activated.

Part B consists of the collusive module. During the initial two periods it charges subsequent prices with a fixed ratio of

${\kappa }_1\ne 1$

to enable maximum‐likelihood estimation. At the start of the third period it sets the price that corresponds to the scenario where the opponent made no sales during the previous two periods. If the opponent's price reveals that a different scenario occurred, the “wrong” price is adjusted accordingly after ε time units, and the inferred demand data are stored for future computations. Part B1 consists of the collusive main loop: assume that the opponent made no sale during the previous period, set the corresponding price, adjust the price after ε time units if the opponent's price reveals that the no‐sale assumption was wrong, store the inferred demand data, and repeat. During these steps the state variable t is used to keep track of time. If the synchronization mechanism dictates at any point that the collusive module has to be initialized, the algorithm immediately re‐activates part B. Similarly, if the opponent charges a price that cannot be the output of the collusive module, the algorithm switches to part C.

Part C consists of the competitive module. It first introduces the state variable t, which keeps track of time, and n, which determines the competitive cycle that needs to be executed next. Part C1 consists of the competitive main loop: perform the nth Kiefer–Wolfowitz cycle, and update the state variables (i.e., increase t by 2 and n by 1). Again, if the synchronization mechanism requires it, the loop is interrupted and part B is activated. If the required number of cycles (i.e., γ cycles) have been completed without interruption, the state variables are updated accordingly (i.e., k is increased by γ and γ is increased by

$K_{\gamma ,j}$

), and part B is activated.

POLICY PERFORMANCE

In this section, we analyze the performance of the Collude‐or‐Compete algorithm against an opponent that uses the same algorithm (Subsection 4.1), and against an opponent whose prices are determined by an alternative policy within a class of “reasonable” competitive policies (Subsection 4.2). In both cases, we define regret and prove optimal regret bounds. The main results of this section, Theorems 6 and 7, can be summarized as follows. If the Collude‐or‐Compete algorithm is (eventually) used by both firms, prices converge to the collusive solution

$\psi ({\mathit{\theta }}^{\ast })$

with probability one, and the expected cumulative regret is of order

$t^{3/4}$

(up to logarithmic terms). On the other hand, if one firm uses the Collude‐or‐Compete algorithm while the opponent prices according to a noisy reaction function, the prices generated by CC converge to a best‐response price under some mild assumptions, and the expected cumulative regret is of order

$\sqrt{t}$

. Subsection 4.3 provides numerical illustrations of these results.

Policy performance against a collusive opponent

Throughout Subsection 4.1, we consider the case that both firms use the Collude‐or‐Compete algorithm, possibly activated at different starting times. In particular, firm

$j\in \{1,2\}$

uses the policy

$C{C}_j(p_{start,j};p_j^{(1)};K_{\alpha ,j};K_{\beta ,j};K_{\gamma ,j})$

from some point onward—where the hyper‐parameters can be different for each firm. Due to the mechanism described in Subsection 3.2.4 there exists a time of synchronization τ at which the firms simultaneously initiate the collusive module, after which both firms price according to the policy described in Subsection 3.2.1.

Recall that the collusive policy is designed to learn the collusive price pair

$\psi ({\mathit{\theta }}^{\ast })$

, under mutual use of the policy, by estimating the unknown underlying model parameter

${\mathit{\theta }}^{\ast }$

based on accumulating price and demand data. Had

${\mathit{\theta }}^{\ast }$

been known, the firms could insist on charging the price pair

$\psi ({\mathit{\theta }}^{\ast })$

from time τ onward, in which case the expected revenue for firm j per period would be

$r_j(\psi ({\mathit{\theta }}^{\ast });{\mathit{\theta }}^{\ast })$

. We therefore measure the loss or regret for firm j at time t compared to the revenue under the “true” collusive solution by

$$\begin{array}{c}\hfill R_j^{col}(t):=\sum _{s=\tau +1}^t\left(r_j(\psi ({\mathit{\theta }}^{\ast });{\mathit{\theta }}^{\ast })-d_j(s)p_j(s)\right).\end{array}$$

28

We show in this section that the firms, under mutual use of the Collude‐or‐Compete algorithm, learn the collusive price pair

$\psi ({\mathit{\theta }}^{\ast })$

and achieve sublinear expected regret.

Recall that

${\widehat{\mathit{\theta }}}_t$

denotes the maximum‐likelihood estimator of

${\mathit{\theta }}^{\ast }$

based on the price and demand data from periods

$\tau +1,\text{…},t$

. Our first result in this section entails that

${\widehat{\mathit{\theta }}}_t$

is a consistent estimator, and provides a high‐probability bound on the estimation error. Theorem 5

Let

$t\ge \tau +2$

. There exist positive constants K ₁, K ₂, and

$y_{\max }$

(which do not depend on t, τ, or

${\mathit{\theta }}^{\ast }$

) such that, for all

$y\in (0,y_{\max }]$

,

$$\begin{array}{c}\hfill \mathbb{P}(\parallel {\widehat{\mathit{\theta }}}_t-{\mathit{\theta }}^{\ast }\parallel <y)\ge 1-K_1(t-\tau )·\exp (-K_2{y}^2{(t-\tau )}^{1+{\kappa }_0}).\end{array}$$

29

To prove this theorem, we apply Brouwer's invariance of domain theorem to derive conditions which imply that

${\widehat{\mathit{\theta }}}_t$

lies in a small neighborhood of

${\mathit{\theta }}^{\ast }$

. Using matrix inequalities and Hoeffding's concentration bounds we show that the lower bound on the sample variance induced by the collusive policy implies that these conditions hold with high probability.

Our main result in this section is the following regret bound ⁴ . Theorem 6

It holds that

$\mathbb{E}[R_j^{col}(t)]=\stackrel{\sim }{O}({(t-\tau )}^{{\kappa }_0/2+1}+{(t-\tau )}^{1/2-{\kappa }_0/2})$

for each

$j\in \{1,2\}$

. In particular, if

${\kappa }_0=-1/2$

, then

$\mathbb{E}[R_j^{col}(t)]=\stackrel{\sim }{O}({(t-\tau )}^{3/4})$

.

To prove Theorem 6, we first show for all

$s\ge \tau +3$

that the instantaneous absolute revenue loss during the sth period, compared to the revenue under the true collusive price pair

$\psi ({\mathit{\theta }}^{\ast })$

, is bounded from above by a constant times the distance between

$\psi ({\mathit{\theta }}^{\ast })$

and the charged price pair. This latter term can be decomposed into two terms: the norm of the price pair perturbation induced by the collusive policy, and the distance between the true and estimated collusive price pair, which is bounded from above by a constant times the estimation error

$||{\mathit{\theta }}^{\ast }-{\widehat{\mathit{\theta }}}_{s-1}||$

. By construction of the collusive policy, the cumulative expected price perturbations are of the order

$O({(t-\tau )}^{{\kappa }_0/2+1})$

, and, by application of Theorem 5, the cumulative expected estimation errors are of the order

$\stackrel{\sim }{O}({(t-\tau )}^{1/2-{\kappa }_0/2})$

. The total expected regret is therefore

$\stackrel{\sim }{O}({(t-\tau )}^{{\kappa }_0/2+1}+{(t-\tau )}^{1/2-{\kappa }_0/2})$

.

The parameter κ₀ captures the trade‐off between exploration and exploitation. On the one hand, increasing κ₀ leads to more price dispersion and hence lower estimation errors, captured by the term

$\stackrel{\sim }{O}({(t-\tau )}^{1/2-{\kappa }_0/2})$

. On the other hand, price experiments are costly, which is captured by the term

$O({(t-\tau )}^{{\kappa }_0/2+1})$

. The optimal balance between the two competing objectives of earning and learning is struck by choosing

${\kappa }_0=-1/2$

. Remark 2

Kleinberg et al. (2008) show that the regret rate of

$\stackrel{\sim }{O}(t^{(d+1)/(d+2)})$

is asymptotically optimal for Lipschitz‐continuous bandits with d‐dimensional action space, where

$d\ge 1$

. The rate

$t^{3/4}$

for

$d=2$

(because there are two products our action space is two‐dimensional) corresponds with the regret bound derived in Theorem 6.

Policy performance against a competitive opponent

Throughout Subsection 4.2, we consider the case that firm

$j\in \{1,2\}$

uses the Collude‐or‐Compete algorithm, while the opponent's prices are given by a noisy reaction function. In particular, firm j uses the policy

$C{C}_j(p_{start,j},p_j^{(1)},K_{\alpha ,j},K_{\beta ,j},K_{\gamma ,j})$

from the start of the time horizon. For the opponent we consider the general framework that, for all

$s\in \mathbb{N}$

,

$$\begin{array}{c}\hfill p_{\neg j}(s)=\varphi (p_j(s))+{\epsilon }_s,\end{array}$$

30

where

$\varphi :[0,\infty )\to [0,\infty )$

is a function unknown to firm j, and where

${\epsilon }_s$

are

${\mathcal{F}}_{s-1,\neg j}$

‐measurable disturbance terms. In words, firm

$\neg j$

“reacts” on firm j, possibly with disturbance terms.

In Theorem 7, we prove an

$O(\sqrt{t})$

regret bound. To appropriately define regret we need to make some mild assumptions on ϕ and

${\epsilon }_s$

. For all reaction functions

$\phi :[0,\infty )\to [0,\infty )$

, which determine a price based on the price charged by the opponent, and all

$p\ge 0$

, let

$$\begin{array}{c}\hfill f_{\phi }(p):=r_j({[p,\phi (p)]}_j;{\mathit{\theta }}^{\ast })\end{array}$$

31

denote the expected revenue for firm j given that she charges the price p and the opponent charges

$\phi (p)$

. Let

${\mathrm{\Phi }}_{K_0}$

be the class of all twice continuously differentiable reaction functions φ such that

• (F1)
  $f_{\phi }$
  is strictly log‐concave at its stationary points,

which implies that

$f_{\phi }$

has a unique maximizer

$p_{\phi }^{\ast }$

(Lemma 3), and

• (F2)
  $|f_{\phi }^{\prime }(p)|\ge K_0|p-p_{\phi }^{\ast }|$
  for all
  $p\in [0,p_{\max ,j}]$
  ,

where K ₀ is a given positive constant. We assume that ϕ is an element of

${\mathrm{\Phi }}_{K_0}$

and that

$p_{\varphi }^{\ast }<p_{\max ,j}$

. Lemma 3

If φ is a twice continuously differentiable reaction function that satisfies Condition (F1), then there exists a unique maximizer

$p_{\phi }^{\ast }$

of

$f_{\phi }$

. If, additionally,

$p_{\phi }^{\ast }<p_{\max ,j}$

, then Condition (F2) is satisfied for all sufficiently small

$K_0>0$

.

We now show for two reasonable reaction functions that they are elements of our reaction‐function class. Define for all

$q\ge 0$

the constant (fixed‐price) function

$F{P}_q(p)$

that equals q for any

$p\ge 0$

. Lemma 4

Let

$\mathit{\theta }\in \mathrm{\Theta }$

and

$q\ge 0$

. The functions

$p\mapsto B{R}_{\neg j}(p;\mathit{\theta })$

and

$F{P}_q$

are elements of

${\mathrm{\Phi }}_{K_0}$

for all sufficiently small

$K_0>0$

.

Furthermore, we assume that

$\mathbb{E}[|{\epsilon }_s|]$

converges to zero, which means that the opponent gradually learns to price according to the reaction function ϕ, rendering

$p_{\varphi }^{\ast }$

the asymptotically optimal price for firm j, and

$f_{\varphi }(p_{\varphi }^{\ast })$

the asymptotically optimal expected revenue for firm j per period. We therefore measure the regret for firm j compared to the asymptotically optimal revenue by

$$\begin{array}{c}\hfill R_j^{comp}(t):=\sum _{s=1}^t\left(f_{\varphi }(p_{\varphi }^{\ast })-d_j(s)p_j(s)\right).\end{array}$$

32

The main result of this section is that the Collude‐or‐Compete algorithm learns the asymptotically optimal price

$p_{\varphi }^{\ast }$

and achieves

$O(\sqrt{t})$

expected regret under appropriate conditions on

${\epsilon }_s$

. To formulate our main result, define, for all

$s\in \mathbb{N}$

,

$$\begin{array}{c}\hfill {\xi }_s:=r_j({[p_j(s),\varphi (p_j(s))+{\epsilon }_s]}_j;{\mathit{\theta }}^{\ast })-r_j({[p_j(s),\varphi (p_j(s))]}_j;{\mathit{\theta }}^{\ast }).\end{array}$$

33

Note that

${\xi }_s$

is a random variable that captures how the opponent's noise

${\epsilon }_s$

on the reaction function distorts the expected revenue for firm j. We finally make the mild and reasonable assumption that our Collude‐or‐Compete algorithm can detect in finitely many time periods that the prices of firm

$\neg j$

are not determined by Collude‐or‐Compete. Under this assumption, we have the following result: Theorem 7

Let

$K_{\alpha ,j}>(\sqrt{2}-1)/(2K_0)$

. If there exists a positive constant

$K_{\xi }$

such that

$\mathbb{E}[|{\xi }_s|]\le K_{\xi }/\sqrt{s}$

for all

$s\in \mathbb{N}$

, and

$\mathbb{E}[|{\xi }_s{|}^2]$

is bounded uniformly in s, then

$\mathbb{E}[R_j^{comp}(t)]=O(\sqrt{t})$

.

To prove Theorem 7, we first show that the expected absolute revenue loss per period, compared to the asymptotically optimal revenue

$f_{\varphi }(p_{\varphi }^{\ast })$

, is bounded from above by the sum of three separate terms involving the mean square error of the pivot price, the square of the price perturbation induced by our competitive policy, and the expected absolute noise on the revenue function, yielding the following regret bound:

34

where K ₁ is a positive constant. By adapting the proof of Theorem 1 in Broadie et al. (2011) to the case where

$({\xi }_s)$

is not necessarily a martingale difference sequence, we show that there exists a positive constant C such that, for all

$s\in \mathbb{N}$

,

$$\begin{array}{c}\hfill \mathbb{E}\left[{\left(p_{\varphi }^{\ast }-p_j^{(\lceil s/2\rceil )}\right)}^2\right]\le C/\sqrt{s}.\end{array}$$

35

By substituting (19), (35), and the assumed upper bound of

$\mathbb{E}[|{\xi }_s|]$

into the regret bound (34), we arrive at the final conclusion

$\mathbb{E}[R_j^{comp}(t)]=O(\sqrt{t})$

.

Broadie et al. (2011, Proposition 1) show that

$O(1/\sqrt{s})$

is the minimal order of the upper bound in (35) over a wide range of sequences

$({\alpha }_{n,j})$

and

$({\beta }_{n,j})$

, rendering

$O(\sqrt{t})$

the minimal order of the upper bound in (34). This rate is asymptotically optimal (cf. Keskin & Zeevi, 2014 or Broder & Rusmevichientong, 2012).

Numerical illustrations

Collusive opponent

We now provide a numerical illustration of the theoretical results from Subsection 4.1. In particular, we show by means of simulation that the prices determined by the Collude‐or‐Compete algorithm converge to the collusive solution

$\psi ({\mathit{\theta }}^{\ast })$

when used by both firms, and that the growth rate of the regret is in accordance with Theorem 6.

To illustrate convergence to the collusive price pair

$\psi ({\mathit{\theta }}^{\ast })$

, we run a simulation consisting of 50,000 time periods. We set

${\kappa }_0=-1/2$

,

${\kappa }_1=5/11$

,

${\mathit{\theta }}^{\ast }=(2,0.010,3,0.004)$

,

$\psi ={\psi }^{R}PO$

(defined in Subsection 2.2.2) and set the hyper‐cube

$\mathrm{\Xi }=[-1,5]\times [0.001,0.019]\times [-1,5]\times [0.001,0.019]$

as the compact and convex parameter space, in line with the literature mentioned in Subsection 2.2.1. For this choice of

${\mathit{\theta }}^{\ast }$

, the joint‐revenue‐maximizing prices cause revenue losses of almost 80% compared to the Nash equilibrium for one of the firms, whereas the RPO prices increase revenue by almost 20% for both firms. The RPO prices are also significantly higher than the Nash equilibrium prices:

${\mathbf{p}}^{N}E({\mathit{\theta }}^{\ast })\approx (146,500)$

and

${\psi }^{R}PO({\mathit{\theta }}^{\ast })\approx (252,718)$

.

Regarding the price policies applied by the firms, suppose that firm one applies the policy

$C{C}_1(p_{start,1};p_1^{(1)};K_{\alpha ,1};K_{\beta ,1};K_{\gamma ,1})$

throughout the entire time horizon (i.e., from time 0 onward), with

$p_{start,1}=275$

,

$p_1^{(1)}=150$

,

$K_{\alpha ,1}=100$

,

$K_{\beta ,1}=100$

, and

$K_{\gamma ,1}=60$

. Firm two fixes its price to 500 for the initial 25,000 time periods, and then starts using the Collude‐or‐Compete algorithm; this setup illustrates that the Collude‐or‐Compete algorithm is self‐synchronizing, that is, prices converge to

$\psi ({\mathit{\theta }}^{\ast })$

even if the firms activate the Collude‐or‐Compete algorithm at different starting times. In particular, firm two activates the policy

$C{C}_2(p_{start,2};p_2^{(1)};K_{\alpha ,2};K_{\beta ,2};K_{\gamma ,2})$

at time 25,000, with

$p_{start,2}=770$

,

$p_2^{(1)}=450$

,

$K_{\alpha ,2}=300$

,

$K_{\beta ,2}=300$

, and

$K_{\gamma ,2}=50$

.

Figure 1a shows the price paths resulting from our simulation. The isolated (red) dots are the result of firm one switching to the collusive module (charging

$p_{start,1}=275$

and

${\kappa }_1{p}_{start,1}=125$

, in that order), which occurs with decreasing frequency as long as firm two keeps her price fixed to 500. Firm one predominantly uses the competitive module during this phase, and Figure 1a shows that her prices initially converge to the best‐response price

$B{R}_1(500;{\mathit{\theta }}^{\ast })\approx 146$

(conform Theorem 7). Synchronization is achieved at time

$\tau =25606$

, after which the prices charged by both firms converge to the collusive solution

${\psi }^{R}PO({\mathit{\theta }}^{\ast })$

. The taboo intervals of the collusive policy (Subsection 3.2.1) can be discerned in the figure as white regions that the price paths occasionally “jump” over.

FIGURE 1

Convergence of prices (left panel) and regret on a log–log scale (right panel) when both firms use the Collude‐or‐Compete algorithm

We repeat this simulation 1000 times in order to illustrate the growth rate of the regret. Figure 1b shows that the logarithm of the sample average of

${\stackrel{\sim }{R}}_1^{col}(t):={\sum }_{s=\tau +1}^t|r_1(\psi ({\mathit{\theta }}^{\ast });{\mathit{\theta }}^{\ast })-r_1(\mathbf{p}(s);{\mathit{\theta }}^{\ast })|$

asymptotically resembles a line with gradient 3/4 when plotted against

$\ln (t-\tau )$

, where

$\tau =25606$

denotes the time of synchronization. This illustrates that

$\mathbb{E}[R_1^{col}(t)]=O(\mathbb{E}[{\stackrel{\sim }{R}}_1^{col}(t)])=\stackrel{\sim }{O}({(t-\tau )}^{3/4})$

, conform Theorem 6.

Competitive opponent

We now provide a numerical illustration of the theoretical results from Subsection 4.2. In particular, we show by means of simulation that the prices determined by the Collude‐or‐Compete algorithm converge to the asymptotically optimal price when playing against an explore‐then‐commit policy, and that the growth rate of the regret is in accordance with Theorem 7.

To illustrate convergence to the asymptotically optimal price we run a simulation consisting of 1 million time periods. We again set

${\kappa }_0=-1/2$

,

${\kappa }_1=5/11$

,

${\mathit{\theta }}^{\ast }=(2,0.010,3,0.004)$

,

$\psi ={\psi }^{R}PO$

, and

$\mathrm{\Xi }=[-1,5]\times [0.001,0.019]\times [-1,5]\times [0.001,0.019]$

. Regarding the price policies applied by the firms, we suppose that firm one applies the policy

$C{C}_1(p_{start,1};p_1^{(1)};K_{\alpha ,1};K_{\beta ,1};K_{\gamma ,1})$

throughout the entire time horizon, with

$p_{start,1}=275$

,

$p_1^{(1)}=150$

,

$K_{\alpha ,1}=100$

,

$K_{\beta ,1}=100$

, and

$K_{\gamma ,1}=1000$

. Firm two uses an explore‐then‐commit policy: for each of the initial half million time periods, one of the five experimental prices 300, 400, 500, 600, and 700 is chosen uniformly at random and charged during that period. After these half million periods, firm two selects an experimental price

$p_2^{\ast }$

that provided the highest mean revenue per period, and commits to that price for the rest of the time horizon. This policy fits the competitive framework from Subsection 4.2 with the fixed‐price reaction function

$\varphi =F{P}_{p_2^{\ast }}$

.

Figure 2a shows the price paths resulting from our simulation. It illustrates that firm two initially explores five different prices and eventually commits to the price

$p_2^{\ast }=500$

. The prices charged by firm one converge to the asymptotically optimal price

$B{R}_1(500;{\mathit{\theta }}^{\ast })$

. The isolated (red) dots indicate the moments at which firm one activates the collusive module.

FIGURE 2

Convergence of prices (left panel) and regret (right panel) on a log–log scale when one firm uses the Collude‐or‐Compete algorithm and the other firm uses an explore‐then‐commit policy

We repeat this simulation 1000 times in order to illustrate the growth rate of the regret. It turns out that

$p_2^{\ast }=500$

in all thousand simulations. It therefore holds in the context of these simulations that

$\mathbb{E}[R_1^{comp}(t)]=\mathbb{E}[{\stackrel{\sim }{R}}_1^{comp}(t)]$

, where

${\stackrel{\sim }{R}}_1^{comp}(t):={\sum }_{s=1}^t(r_1((B{R}_1(500;{\mathit{\theta }}^{\ast }),500);{\mathit{\theta }}^{\ast })-r_1(\mathbf{p}(s);{\mathit{\theta }}^{\ast }))$

. Figure 2b illustrates that the logarithm of the resulting sample mean of

${\stackrel{\sim }{R}}_1^{comp}(t)$

asymptotically resembles a line with gradient 1/2 when plotted against

$\ln (t)$

, indicating that

$\mathbb{E}[{\stackrel{\sim }{R}}_1^{comp}(t)]=O(\sqrt{t})$

, and hence that expected regret is

$O(\sqrt{t})$

, conform Theorem 7.

DISCUSSION

Contributions. This work makes several contributions to the field of dynamic pricing and demand learning. First, in a pricing duopoly with multinomial logit purchase probabilities, we show for several axiomatic notions of collusion that they reduce consumer welfare and component‐wise increase sellers' revenues and prices compared to the Nash equilibrium. These properties hold regardless of the model parameters, so that these constitute stable notions of collusion in all markets modeled in this way. This result demonstrates that even in markets where the demand functions are very asymmetric, firms can define cartel prices in a way that is mutually beneficial and detrimental to consumer welfare. Second, we construct a price algorithm that learns the cartel prices from data when used by both players in the duopoly, and learns to respond optimally against a class of competitive policies. In both cases, we analyze the performance by proving theoretical regret bounds. To learn to collude, the firms do not need to know that the competitor is using the same algorithm, and the algorithms do not have to be initiated at exactly the same moment. The algorithm enables the firms to learn to price collusively without engaging in illicit forms of communication, and is thus an example of data‐driven algorithmic collusion. The algorithm includes a mechanism to infer sales data from price paths so that our algorithm works well even if sellers do not share their sales data with competitors. This has the important consequence that legal measures that forbid firms to share their sales data, directly or indirectly, will not fully mitigate the threat of algorithmic collusion. It also shows that defining “illicit communication” in the context of price cartels is a complex question: our work shows that price paths generated by algorithms inevitably contain information that can be “decoded” by firms that use the same algorithm to facilitate collusion. Our results on the performance of the algorithm when playing against a competitive opponent are of independent interest as such results are scarce in the literature.

The role of demand information. Our results also apply when demand information is shared publicly; Meylahn and den Boer (2022) provide several real‐life examples, including web‐shops that explicitly disclose inventory information (“x units in stock,” “x units sold in the last y hours”). Aouad and den Boer (2021) demonstrate in an assortment optimization problem that observing the competitor's demand realizations may not even be necessary in order to learn the underlying model. However, the decisions of both players would no longer be based on the same data set, which makes it more challenging to discern whether the opponent is using the same algorithm.

Extensions. Our model can be extended to multiple products, time‐varying parameters, and limits on the maximum number of price changes. Ideas from den Boer (2014) (multi‐product policies), Chen et al. (2020) and Cheung et al. (2017) (limited price changes), and Keskin and Zeevi (2017) (nonstationary environments) can be adapted to construct well‐performing price policies, both in a competitive and in a collusive setting. A second important extension that is left for future research is to allow for more than two players, each of which may either price competitively or be willing to form a cartel. This extension requires generalizing our notion of collusion to accommodate larger cartels, extending our results on synchronization and statistical aspects, and studying the stability properties of (sub)coalition structures in an oligopoly.

Footnotes

ACKNOWLEDGMENTS

The authors are grateful to the reviewers and editors for constructive suggestions. This research was supported by NWO Klein, Grant OCENW.KLEIN.016.

1

The abbreviation DCVP stands for “Duopolistic Controlled Variance Pricing,” based on the policy name “Controlled Variance Pricing” from den Boer and Zwart () for a monopolist.

2

Note that firm j requires the correct value of

$c_{\neg j}$

in order to compute the prices that the collusive policy would set for the competitor. Because

$c_{\neg j}=2^{-2-{\kappa }_0}{(p_{\neg j}(\tau +1))}^2{({\kappa }_1-1)}^2$

if firm

$\neg j$

activates the collusive module at time τ, this value can be computed by firm j immediately after period

$\tau +1$

.

3

Our description of the synchronization mechanism uses the property that the collusive module of firm

$\neg j$

is active for only two periods at a time. However, it is worth emphasizing that this property is not necessary for the mechanism to work; it only makes for a simpler description. That is, if firm

$\neg j$

runs the collusive module for more than two periods, firm j can still check whether the opponent's prices conform to the collusive module by applying the demand‐information extraction‐mechanism from Subsection . Therefore, firm j can still distinguish two subsequent phases, infer

$K_{\gamma ,\neg j}$

, and derive when the opponent will activate the collusive module.

4

Here we use the notation

$f(t)=\stackrel{\sim }{O}(g(t))$

as shorthand for

$f(t)=O(g(t)\ln {(g(t))}^k)$

for some arbitrary

$k>0$

.

ORCID iD

Thomas Loots

Arnoud V. denBoer

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.82 MB