Distributed Task Allocation for Self-Interested Agents With Partially Unknown Rewards

• 成果类型: Article
• 署名作者: Mandal, Nirabhra; Khajenejad, Mohammad; Martinez, Sonia
• 署名单位: University of California System; University of California San Diego; University of Tulsa; University of Tulsa
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3560566
• 发表日期: 2025
• 页码: 6284-6291
• 关键词: games; resource management; Heuristic algorithms; Nash equilibrium; training; silicon; nickel; Data mining; Clustering algorithms; Artificial intelligence; Best response; partition game; projected gradient ascent; unknown reward; weight game

摘要

This article provides a novel solution to a task allocation problem, by which a group of agents assigns a discrete set of tasks in a distributed manner. In this setting, heterogeneous agents have individual preferences and associated rewards for doing each task; however, these rewards are only known asymptotically. The assignment problem is formulated by means of a combinatorial partition game for known rewards, with no constraints on the number of tasks per agent. We relax this into a weight game, which together with the former, are shown to contain the optimal task allocation in the corresponding set of Nash equilibria (NE). We then propose a projected, best-response, ascending gradient dynamics (PBRAG) that converges to an NE in finite time. This forms the basis of a distributed online version that can deal with a converging sequence of rewards by means of an agreement subroutine. We present simulations that support our results.