Many sequential decision-making tasks require satisfaction of multiple,
partially contradictory objectives. Existing approaches are monolithic, namely
all objectives are fulfilled using a single policy, which is a function that
selects a sequence of actions. We present auction-based scheduling, a modular
framework for multi-objective decision-making problems. Each objective is
fulfilled using a separate policy, and the policies can be independently
created, modified, and replaced. Understandably, different policies with
conflicting goals may choose conflicting actions at a given time. In order to
resolve conflicts, and compose policies, we employ a novel auction-based
mechanism. We allocate a bounded budget to each policy, and at each step, the
policies simultaneously bid from their available budgets for the privilege of
being scheduled and choosing an action. Policies express their scheduling
urgency using their bids and the bounded budgets ensure long-run scheduling
fairness. We lay the foundations of auction-based scheduling using path
planning problems on finite graphs with two temporal objectives. We present
decentralized algorithms to synthesize a pair of policies, their initially
allocated budgets, and bidding strategies. We consider three categories of
decentralized synthesis problems, parameterized by the assumptions that the
policies make on each other: (a) strong synthesis, with no assumptions and
strongest guarantees, (b) assume-admissible synthesis, with weakest rationality
assumptions, and (c) assume-guarantee synthesis, with explicit contract-based
assumptions. For reachability objectives, we show that, surprisingly,
decentralized assume-admissible synthesis is always possible when the
out-degrees of all vertices are at most two.

基于拍卖的调度是一种用于多目标决策问题的模块化框架，它使用单独的策略来实现每个目标，并通过拍卖机制解决冲突和组合策略，同时提供长期调度公平性。本研究解决了路径规划问题上的基于拍卖的调度基础，并提出了分散算法来合成一对策略、初步分配的预算和出价策略，在不同的分散合成问题中进行了分类和讨论。

基于拍卖的调度

Auction-Based Scheduling

Resource allocation games such as the famous Colonel Blotto (CB) and
Hide-and-Seek (HS) games are often used to model a large variety of practical
problems, but only in their one-shot versions. Indeed, due to their extremely
large strategy space, it remains an open question how one can efficiently learn
in these games. In this work, we show that the online CB and HS games can be
cast as path planning problems with side-observations (SOPPP): at each stage, a
learner chooses a path on a directed acyclic graph and suffers the sum of
losses that are adversarially assigned to the corresponding edges; and she then
receives semi-bandit feedback with side-observations (i.e., she observes the
losses on the chosen edges plus some others). We propose a novel algorithm,
EXP3-OE, the first-of-its-kind with guaranteed efficient running time for SOPPP
without requiring any auxiliary oracle. We provide an expected-regret bound of
EXP3-OE in SOPPP matching the order of the best benchmark in the literature.
Moreover, we introduce additional assumptions on the observability model under
which we can further improve the regret bounds of EXP3-OE. We illustrate the
benefit of using EXP3-OE in SOPPP by applying it to the online CB and HS games.

本文研究资源分配游戏的在线版本，将其视为带有旁观者信息路径规划问题，并提出了一种基于 EXP3 算法的有效学习策略，证明其性能可以匹配先前文献中的最优策略。