Martin Bichler

Martin Bichler, Jan-Sebastian Hoehener

Autonomous pricing agents are widely deployed in online marketplaces, making algorithmic pricing a prominent application of multi-agent learning. Experimental studies often report collusive outcomes, but these findings typically rely on Q-learning in complete-information environments and lack rigorous convergence guarantees. In this paper, we study the stochastic learning dynamics of Regularized Robbins-Monro (RRM) algorithms in a Bayesian Bertrand competition with private costs. We show that this setting violates standard stability conditions, including monotonicity and the Minty variational inequality, rendering classical convergence results for gradient-based learning inapplicable. Despite this, we prove that Euclidean RRM algorithms converge almost surely to the unique, efficient Bayes-Nash equilibrium within a finite-dimensional approximation of the strategy space. By analyzing symmetric piecewise-linear pricing strategies in a duopoly, we explicitly construct a global Lyapunov function for the projected primal dynamics and establish global asymptotic stability of the equilibrium. Our analysis yields rigorous convergence guarantees for stochastic first-order learning algorithms in Bayesian Bertrand competition and provides a principled counterpoint to widespread claims of algorithmic collusion.

Stefan Heidekrüger, Paul Sutterer, Nils Kohring et al.

Applications of combinatorial auctions (CA) as market mechanisms are prevalent in practice, yet their Bayesian Nash equilibria (BNE) remain poorly understood. Analytical solutions are known only for a few cases where the problem can be reformulated as a tractable partial differential equation (PDE). In the general case, finding BNE is known to be computationally hard. Previous work on numerical computation of BNE in auctions has relied either on solving such PDEs explicitly, calculating pointwise best-responses in strategy space, or iteratively solving restricted subgames. In this study, we present a generic yet scalable alternative multi-agent equilibrium learning method that represents strategies as neural networks and applies policy iteration based on gradient dynamics in self-play. Most auctions are ex-post nondifferentiable, so gradients may be unavailable or misleading, and we rely on suitable pseudogradient estimates instead. Although it is well-known that gradient dynamics cannot guarantee convergence to NE in general, we observe fast and robust convergence to approximate BNE in a wide variety of auctions and present a sufficient condition for convergence

Martin Bichler, Sören Merting, Aykut Uzunoglu

Course assignment is a wide-spread problem in education and beyond. Often students have preferences for bundles of course seats or course schedules over the week, which need to be considered. The problem is a challenging distributed scheduling task requiring decision support. First-Come First-Served (FCFS) is simple and the most widely used assignment rule in practice, but it leads to inefficient outcomes and envy in the allocation. Recent theoretical results suggest alternatives with attractive economic and computational properties. Bundled Probabilistic Serial (BPS) is a randomized mechanism satisfying ordinal efficiency, envy-freeness, and weak strategy-proofness. This mechanism also runs in polynomial time, which is important for the large problem instances in the field. We report empirical results from a first implementation of BPS at the Technical University of Munich, which allows us to provide important empirical metrics such as the size of the resulting matching, the average rank, the profile, and the popularity of the assignments. These metrics were central for the adoption of BPS. In particular, we compare these metrics to Random Serial Dictatorship with bundle bids (BRSD). The BRSD mechanism is used to simulate the wide-spread First-Come First-Served (FCFS) mechanism and it allows us to compare FCFS (BRSD) and BPS. While theoretically appealing, preference elicitation is a major challenge when considering preferences over exponentially many packages. We introduce tools to elicit preferences which reduce the number of parameters a student needs to a manageable set. The approach together with BPS yields a computationally effective tool to solve course assignment problems with thousands of students, and possibly provides an approach for other distributed scheduling tasks in organizations.