论文标题
AIMD有限平均分布式异质资源分配的融合
The Convergence of Finite-Averaging of AIMD for Distributed Heterogeneous Resource Allocations
论文作者
论文摘要
在几个社会选择问题中，代理商对分配多个可分割和异质资源的分配具有能力限制，以最大程度地提高功利主义社会福利。代理人通过计算，通信资源或隐私注意事项受到限制。在本文中，我们分析了最近提出的分布式解决方案的收敛性，该解决方案将这些资源分配给具有最小通信的代理商。它基于随机添加剂 - 加入和乘法酶（AIMD）算法。代理人不需要彼此交换信息，而是与中央代理商相互交换的，该中央代理一次跟踪一次分配的总资源。我们在有限的窗口大小上制定了时间平均分配，并将系统建模为具有位置依赖概率的马尔可夫链。此外，我们表明，时间平均分配向量会收敛到独特的不变度度量，并且沿阵行的属性也具有。
In several social choice problems, agents collectively make decisions over the allocation of multiple divisible and heterogeneous resources with capacity constraints to maximize utilitarian social welfare. The agents are constrained through computational or communication resources or privacy considerations. In this paper, we analyze the convergence of a recently proposed distributed solution that allocates such resources to agents with minimal communication. It is based on the randomized additive-increase and multiplicative-decrease (AIMD) algorithm. The agents are not required to exchange information with each other, but little with a central agent that keeps track of the aggregate resource allocated at a time. We formulate the time-averaged allocations over finite window size and model the system as a Markov chain with place-dependent probabilities. Furthermore, we show that the time-averaged allocations vector converges to a unique invariant measure, and also, the ergodic property holds.
