Session: Multi-agent learning in games and markets
Chair: Manxi Wu
Cluster: Multi-agent Optimization and Games
Talk 1: Learning Optimal Stable Matches in Decentralized Markets with Unknown Preferences
Speaker: Bryce Ferguson
Abstract: Matching algorithms have demonstrated great success in several practical applications, but they often require centralized coordination and plentiful information. In many modern online marketplaces, agents must independently seek out and match with another using little to no information. For these kinds of settings, can we design decentralized, limited-information matching algorithms that preserve the desirable properties of standard centralized techniques? In this work, we constructively answer this question in the affirmative. We model a two-sided matching market as a game consisting of two disjoint sets of agents, referred to as proposers and acceptors, each of whom seeks to match with their most preferable partner on the opposite side of the market. However, each proposer has no knowledge of their own preferences, so they must learn their preferences while forming matches in the market. We present a simple online learning rule that guarantees a strong notion of probabilistic convergence to the welfare-maximizing equilibrium of the game, referred to as the proposer-optimal stable match. To the best of our knowledge, this represents the first completely decoupled, communication-free algorithm that guarantees probabilistic convergence to an optimal stable match, irrespective of the structure of the matching market.
Talk 2: Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements
Speaker: Devansh Jalota
Abstract: Fisher markets are one of the most fundamental models for resource allocation. However, the problem of computing equilibrium prices in Fisher markets typically relies on complete knowledge of users' budgets and utility functions and requires transactions to happen in a static market where all users are present simultaneously. Motivated by these practical considerations, we study an online variant of Fisher markets, wherein users with privately known utility and budget parameters, drawn i.i.d. from a distribution, arrive sequentially. In this setting, we first study the limitations of static pricing algorithms, which set uniform prices for all users, along two performance metrics: (i) regret, i.e., the optimality gap in the objective of the Eisenberg-Gale program between an online algorithm and an oracle with complete information, and (ii) capacity violations, i.e., the over-consumption of goods relative to their capacities. Given the limitations of static pricing, we design adaptive posted-pricing algorithms, one with knowledge of the distribution of users' budget and utility parameters and another that adjusts prices solely based on past observations of user consumption, i.e., revealed preference feedback, with improved performance guarantees. Finally, we present numerical experiments to compare our revealed preference algorithm's performance to several benchmarks.
Talk 3: Decentralized learning in Markov potential games and beyond
Speaker: Manxi Wu
Abstract: Infinite-horizon stochastic games provide a versatile framework for studying the repeated interaction among multiple strategic agents in dynamic environments. However, computing equilibria in such games is highly complex, and the long-run outcomes of decentralized learning algorithms in multi-agent settings remain poorly understood. The first part of this talk introduces a multi-agent reinforcement learning dynamics tailored for independent and decentralized settings, where players lack knowledge of the game model and cannot coordinate. The proposed dynamics guarantee convergence to a stationary Nash equilibrium in Markov potential games, demonstrating the effectiveness of simple learning dynamics even with limited information. In the second part of the talk, we extend the learning framework to encompass Markov near potential games, offering flexibility to incorporate a wide range of practically-relevant multi-agent interaction settings. We present efficient algorithms for approximating the stationary Nash equilibrium and substantiate their effectiveness through regret analysis and numerical experiments.
