More Like this

1. Algorithmic Collusion Without Threats

   https://doi.org/10.4230/LIPIcs.ITCS.2025.10  

   Arunachaleswaran, Eshwar Ram; Collina, Natalie; Kannan, Sampath; Roth, Aaron; Ziani, Juba (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   There has been substantial recent concern that automated pricing algorithms might learn to collude Supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors if they ever defect from a set of supra-competitive prices, and these strategies can be automatically learned. But threats are anti-competitive on their face. In fact, a standard economic intuition is that supra-competitive prices emerge from either the use of threats, or a failure of one party to correctly optimize their payoff. Is this intuition correct? Would explicitly preventing threats in algorithmic decision-making prevent supra-competitive prices when sellers are optimizing for their own revenue? No. We show that supra-competitive prices can robustly emerge even when both players are using algorithms which do not explicitly encode threats, and which optimize for their own revenue. Since deploying an algorithm is a form of commitment, we study sequential Bertrand pricing games (and a continuous variant) in which a first mover deploys an algorithm and then a second mover optimizes within the resulting environment. We show that if the first mover deploys any algorithm with a no-regret guarantee, and then the second mover even approximately optimizes within this now static environment, monopoly-like prices arise. The result holds for any no-regret learning algorithm deployed by the first mover and for any pricing policy of the second mover that obtains them profit at least as high as a random pricing would - and hence the result applies even when the second mover is optimizing only within a space of non-responsive pricing distributions which are incapable of encoding threats. In fact, there exists a set of strategies, neither of which explicitly encode threats that form a Nash equilibrium of the simultaneous pricing game in algorithm space, and lead to near monopoly prices. This suggests that the definition of algorithmic collusion; may need to be expanded, to include strategies without explicitly encoded threats. 

   more » « less
2. Frontiers: Algorithmic Collusion: Supra-competitive Prices via Independent Algorithms

   https://doi.org/10.1287/mksc.2020.1276  

   Hansen, Karsten T.; Misra, Kanishka; Pai, Mallesh M. (January 2021, Marketing Science)

   null (Ed.)

   Motivated by their increasing prevalence, we study outcomes when competing sellers use machine learning algorithms to run real-time dynamic price experiments. These algorithms are often misspecified, ignoring the effect of factors outside their control, for example, competitors’ prices. We show that the long-run prices depend on the informational value (or signal-to-noise ratio) of price experiments: if low, the long-run prices are consistent with the static Nash equilibrium of the corresponding full information setting. However, if high, the long-run prices are supra-competitive—the full information joint monopoly outcome is possible. We show that this occurs via a novel channel: competitors’ algorithms’ prices end up running correlated experiments. Therefore, sellers’ misspecified models overestimate the own price sensitivity, resulting in higher prices. We discuss the implications on competition policy. 

   more » « less
3. Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback

   https://doi.org/10.1609/aaai.v39i18.34089  

   Liu, Xiang; Chan, Hau; Li, Minming; Wu, Weiwei; Tran-Thanh, Long (April 2025, Proceedings of the AAAI Conference on Artificial Intelligence)

   We consider a general non-stochastic online pricing bandit setting in a procurement scenario where a buyer with a budget wants to procure items from a fixed set of sellers to maximize the buyer's reward by dynamically offering purchasing prices to the sellers, where the sellers' costs and values at each time period can change arbitrarily and the sellers determine whether to accept the offered prices to sell the items. This setting models online pricing scenarios of procuring resources or services in multi-agent systems. We first consider the offline setting when sellers' costs and values are known in advance and investigate the best fixed-price policy in hindsight. We show that it has a tight approximation guarantee with respect to the offline optimal solutions. In the general online setting, we propose an online pricing policy, Granularity-based Pricing (GAP), which exploits underlying side-information from the feedback graph when the budget is given as the input. We show that GAP achieves an upper bound of O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln B) on the alpha-regret where n, v_{max}, c_{min}, and B are the number, the maximum value, the minimum cost of sellers, and the budget, respectively. We then extend it to the unknown budget case by developing a variant of GAP, namely Doubling-GAP, and show its alpha-regret is at most O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln2 B). We also provide an alpha-regret lower bound Omega(v_{max}sqrt{Bn/c_{min}}) of any online policy that is tight up to sub-linear terms. We conduct simulation experiments to show that the proposed policy outperforms the baseline algorithms. 

   more » « less
4. Cost Based Nonlinear Pricing

   https://doi.org/10.1145/3580507.3597697  

   Bergemann, Dirk; Heumann, Tibor; Morris, Stephen (July 2023, ACM)

   Hartline, Jason (Ed.)

   The arrival of digital commerce has lead to an increasing use of personalization and differentiation strategies. With differentiated products along the quality dimension and/or the quantity dimension comes the need for nonlinear pricing policies or second degree price discrimination. The optimal pricing strategies for quality and quantity differentiated products were first investigated by Mussa and Rosen (1978) and Maskin and Riley (1984), respectively. The optimal pricing strategies were shown to depend heavily on the prior distribution of the private information regarding the types, and ultimately the willingness-to-pay of the buyers. Yet, frequently the sellers possess only weak and incomplete information about the distribution of demand. This paper aims to develop robust pricing policies that are independent of specific demand distributions and provide revenue guarantees across all possible distributions. 

   more » « less
5. The I.I.D. Prophet Inequality with Limited Flexibility

   https://doi.org/10.1287/moor.2022.0345  

   Perez-Salazar, Sebastian; Singh, Mohit; Toriello, Alejandro (January 2025, Mathematics of Operations Research)

   In online sales, sellers usually offer each potential buyer a posted price in a take-it-or-leave fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price frequently could be considered unfair. The literature on posted-price mechanisms and prophet inequality problems has studied the two extremes of pricing policies, the fixed-price policy and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than the latter. This work examines the middle situation, where there are at most k distinct prices over the selling horizon. Using the framework of prophet inequalities with independent and identically distributed random variables, we propose a new prophet inequality for strategies that use at most k thresholds. We present asymptotic results in k and results for small values of k. For k = 2 prices, we show an improvement of at least 11% over the best fixed-price solution. Moreover, k = 5 prices suffice to guarantee almost 99% of the approximation factor obtained by a fully dynamic policy that uses an arbitrary number of prices. From a technical standpoint, we use an infinite-dimensional linear program in our analysis; this formulation could be of independent interest to other online selection problems. 

   more » « less