提出竞争性资源分配机制，显著降低在线分配的累积损失。
Regret Bounds for Competitive Resource Allocation with Endogenous Costs
- 基于交互矩阵设计竞争性分配策略，利用反馈信息动态调整
- 在对抗性序列下实现O(√(T log N))的最优后悔界
- 环状拓扑结构可平衡计算开销与分配误差，适合模块化系统
研究在T轮中对N个相互作用模块进行在线资源分配的问题。与标准在线优化不同，成本具有内生性：依赖于完整的分配向量，通过交互矩阵W刻画成对合作与竞争关系。分析三种范式：(I) 均匀分配（无视成本）、(II) 门控分配（估计成本）、(III) 基于乘法权重更新的竞争分配（揭示成本）。主要结果表明，在有界变差的对抗序列下，均匀分配的后悔为Ω(T)，门控分配为O(T^{2/3})，竞争分配为O(√(T log N))。性能差距源于竞争分配能利用交互中揭示的内生成本信息。进一步证明，矩阵W的拓扑结构决定计算-后悔权衡：完全交互（|E|=O(N²)）获得最紧边界但每步开销高；稀疏拓扑（|E|=O(N)）最多使后悔增加O(√(log N))，同时将每步开销从O(N²)降至O(N)。具有合作与竞争边的环状拓扑（如五元素的Wuxing拓扑）最小化计算×后悔乘积。这些结果首次为模块化架构中的去中心化竞争分配提供了后悔理论支持，并确立成本内生性是区别于部分可观测性的根本挑战。
原文摘要 · Abstract (English)
We study online resource allocation among N interacting modules over T rounds. Unlike standard online optimization, costs are endogenous: they depend on the full allocation vector through an interaction matrix W encoding pairwise cooperation and competition. We analyze three paradigms: (I) uniform allocation (cost-ignorant), (II) gated allocation (cost-estimating), and (III) competitive allocation via multiplicative weights update with interaction feedback (cost-revealing). Our main results establish a strict separation under adversarial sequences with bounded variation: uniform incurs Omega(T) regret, gated achieves O(T^{2/3}), and competitive achieves O(sqrt(T log N)). The performance gap stems from competitive allocation's ability to exploit endogenous cost information revealed through interactions. We further show that W's topology governs a computation-regret tradeoff. Full interaction (|E|=O(N^2)) yields the tightest bound but highest per-step cost, while sparse topologies (|E|=O(N)) increase regret by at most O(sqrt(log N)) while reducing per-step cost from O(N^2) to O(N). Ring-structured topologies with both cooperative and competitive links - of which the five-element Wuxing topology is canonical - minimize the computation x regret product. These results provide the first formal regret-theoretic justification for decentralized competitive allocation in modular architectures and establish cost endogeneity as a fundamental challenge distinct from partial observability. Keywords: online learning, regret bounds, resource allocation, endogenous costs, interaction topology, multiplicative weights, modular systems, Wuxing topology
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。