Online Learning for Strategic Resource Allocation: From Policies to Mechanisms

Abstract:
Modern multi-agent systems increasingly operate in environments where agents are strategic, information is incomplete, and system dynamics evolve over time. This talk presents recent frameworks that address this challenge by developing learning-based methods for dynamic games, unified by the broader theme of strategic resource allocation in evolving and uncertain environments. The two frameworks progress from learning strategies in a two-player game to designing mechanisms for multi-agent systems, with performance measured in both cases by regret against an offline benchmark. The first studies a dynamic Colonel Blotto game in which a budget-constrained learner repeatedly allocates troops across battlefields against an opponent with an unknown strategy. Combining Lagrangian relaxation for the budget constraint with an efficient combinatorial bandits algorithm that exploits the graph structure of the game yields regret that is sublinear in the time horizon and polynomial in the problem parameters. The second addresses dynamic mechanism design for sequential auctions modeled as an infinite-horizon average-reward Markov decision process with unknown transition kernel and reward functions. The Vickrey-Clarke-Groves mechanism is extended to this dynamic setting, together with a reinforcement learning algorithm that achieves sublinear regret while approximately preserving efficiency, truthfulness, and individual rationality.