Abstract

Distributed resource allocation arises in many application domains such as smart cities, intelligent transportation systems, sharing economy, cloud computing, edge-computing, power systems, etcetera. In several scenarios, the agents such as Internet of Things (IoT) devices may require multiple shared resources to achieve social optimum values; furthermore, they may have heterogeneous resource demands. Such distributed resource allocation problems are challenging to solve, especially when the agents are constrained through communication infrastructure, computational capabilities or do not wish to communicate with other agents in the network due to privacy reasons. Additionally, when the cost functions of agents are non-separable and are coupled through the allocation of multiple resources, in such cases, the single resource allocation algorithms are not efficient and provide suboptimal solutions.
In the available distributed solutions for multiple resources, best to my knowledge, agents exchange their information with at least one neighboring agent that may incur communication overhead or compromise agents' privacy. We develop several solutions to solve such problems for multiple divisible and multiple indivisible resources wherein no inter-agent communication is required. Moreover, we assume that each agent has private cost functions coupled with multiple resources; these functions are strictly convex, twice continuously differentiable, and increasing in each variable. Our first contribution is the stochastic distributed algorithm that solves multi-resource allocation problems with no direct agent-to-agent communication for divisible resources; moreover, it achieves social-optimum values. In the algorithms, each agent decides its resource demands locally, and an agent is unaware of the resource allocations of other agents. We solve the divisible multi-resource allocation problem by extending the additive-increase multiplicative-decrease (AIMD) algorithm for single resource allocation by Wirth and co-authors. In the algorithm, the agents keep increasing the demands for a resource linearly until they receive a one-bit signal from a central agency. The central agency broadcasts the signal whenever one of the allocated resources reaches its capacity. Agents then respond to this signal in a probabilistic manner to decrease the resource demand. By doing so, the social optimum is achieved in long-term averages.
Our second contribution is a derandomized AIMD algorithm to solve a class of distributed optimization problems for multiple divisible shared resources. The algorithm is a derandomized version of the stochastic additive-increase and multiplicative-decrease (AIMD) algorithm. The developed solution uses a one-bit feedback signal for each resource between the system and the agents, and it does not require inter-agent communication. We show empirically that the long-term average allocations of multiple shared resources converge to optimal allocations, and the system achieves minimum social cost. Furthermore, we show that the derandomized AIMD algorithm converges faster than the stochastic AIMD algorithm, and both approaches provide approximately the same solutions.

Our third contribution is the stochastic algorithm for multiple indivisible (unit-demand) resources, inspired by classical stochastic approximation techniques. Each agent's consumption is modeled as a Bernoulli random variable in the solution, and no inter-agent communication is required. Moreover, we provide fundamental guarantees of convergence. Additionally, we present an example illustrating the performance of the algorithm.
Finally, we study the development of Internet-of-Things (IoT) enabled sharing economy applications. In many sharing economy scenarios, agents both produce as well as consume a resource; we call them prosumers. A community of prosumers agrees to sell excess resources to another community in a prosumer market. We propose a stochastic algorithm to regulate the number of prosumers in a prosumer community; each prosumer has a cost function coupled through its time-averaged production and consumption of the resource.
Furthermore, each prosumer runs its distributed algorithm and takes (binary) decisions in a probabilistic way, whether to produce one unit of the resource or not and to consume one resource unit or not. In the developed approach, prosumers do not explicitly exchange information with each other due to privacy reasons but little with a central agency. Additionally, prosumers achieve the optimal values asymptotically.