Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent's own history of play and requires no foreknowledge of the firms' preferences. Our algorithms are constructed by splitting up the statistical problem of learning one's preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur a regret which grows at most logarithmically in the time horizon. Our results show that, in the case of matching markets, competition need not drastically affect the performance of decentralized, communication and coordination free online learning algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Multi-Agent Lipschitz Bandits
We study the decentralized multi-player stochastic bandit problem over a continuous, Lipschitz-structured action space where hard collisions yield zero reward. Our objective is to design a communication-free policy that …
Improving the Efficiency of Language Agent Teams with Adaptive Task Graphs
Large language models (LLMs) are increasingly deployed in teams, yet existing coordination approaches often occupy two extremes. Highly structured methods rely on fixed roles, pipelines, or task decompositions assigned a…
Decentralized Collective World Model for Emergent Communication and Coordination
We propose a fully decentralized multi-agent world model that enables both symbol emergence for communication and coordinated behavior through temporal extension of collective predictive coding. Unlike previous research …
Contrastive LearningCoordinated Path Following of UAVs using Event-Triggered Communication over Networks with Digraph Topologies
This article presents a novel time-coordination algorithm based on event-triggered communication to ensure multiple UAVs progress along their desired paths in coordination with one another. In the proposed algorithm, a U…
Deep and Decentralized Multi-Agent Coverage of a Target with Unknown Distribution
This paper proposes a new architecture for multi-agent systems to cover an unknowingly distributed fast, safely, and decentralizedly. The inter-agent communication is organized by a directed graph with fixed topology, an…