On Improving Resource Allocations by Sharing

• URL: http://arxiv.org/abs/2112.07525v1
• Date: Tue, 14 Dec 2021 16:41:08 GMT
• Title: On Improving Resource Allocations by Sharing
• Authors: Robert Bredereck, Andrzej Kaczmarczyk, Junjie Luo, Rolf Niedermeier, Florian Sachse
• Abstract summary: Given an initial resource allocation, our goal is to improve the allocation without reassigning resources. We introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents.
• Score: 27.43373407900506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

Related papers

• Intelligent Hybrid Resource Allocation in MEC-assisted RAN Slicing Network [72.2456220035229]
  We aim to maximize the SSR for heterogeneous service demands in the cooperative MEC-assisted RAN slicing system. We propose a recurrent graph reinforcement learning (RGRL) algorithm to intelligently learn the optimal hybrid RA policy.
  arXiv  Detail & Related papers  (2024-05-02T01:36:13Z)
• Generative AI-enabled Quantum Computing Networks and Intelligent Resource Allocation [80.78352800340032]
  Quantum computing networks execute large-scale generative AI computation tasks and advanced quantum algorithms. efficient resource allocation in quantum computing networks is a critical challenge due to qubit variability and network complexity. We introduce state-of-the-art reinforcement learning (RL) algorithms, from generative learning to quantum machine learning for optimal quantum resource allocation.
  arXiv  Detail & Related papers  (2024-01-13T17:16:38Z)
• Human-Centric Resource Allocation for the Metaverse With Multiaccess Edge Computing [4.217982035156334]
  We propose an adaptive edge resource allocation method based on multi-agent soft actor-critic with graph convolutional networks (SAC-GCN) The effectiveness of SAC-GCN is demonstrated through the analysis of user experience, balance of resource allocation, and resource utilization rate.
  arXiv  Detail & Related papers  (2023-12-23T18:07:46Z)
• Compressed Regression over Adaptive Networks [58.79251288443156]
  We derive the performance achievable by a network of distributed agents that solve, adaptively and in the presence of communication constraints, a regression problem. We devise an optimized allocation strategy where the parameters necessary for the optimization can be learned online by the agents.
  arXiv  Detail & Related papers  (2023-04-07T13:41:08Z)
• Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making [3.5788754401889022]
  Resource-Aware distributed Greedy is the first algorithm to account for each robot's on-board resources independently. RAG balances the trade-off of centralization, for global near-optimality, vs. decentralization, for near-minimal on-board computation, communication, and memory resources.
  arXiv  Detail & Related papers  (2022-04-15T15:47:05Z)
• Multi-resource allocation for federated settings: A non-homogeneous Markov chain model [2.552459629685159]
  In a federated setting, agents coordinate with a central agent or a server to solve an optimization problem in which agents do not share their information with each other. We describe how the basic additive-increase multiplicative-decrease (AIMD) algorithm can be modified in a straightforward manner to solve a class of optimization problems for federated settings for a single shared resource with no inter-agent communication. We extend the single-resource algorithm to multiple heterogeneous shared resources that emerge in smart cities, sharing economy, and many other applications.
  arXiv  Detail & Related papers  (2021-04-26T19:10:00Z)
• Resource allocation in dynamic multiagent systems [0.0]
  The MG-RAO algorithm is developed to solve resource allocation problems in multi-agent systems. It shows a 23 - 28% improvement over fixed resource allocation in the simulated environments. Results also show that, in a volatile system, using the MG-RAO algorithm configured so that child agents model resource allocation for all agents as a whole has 46.5% of the performance of when it is set to model multiple groups of agents.
  arXiv  Detail & Related papers  (2021-02-16T17:56:23Z)
• GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning [50.90625274621288]
  Disparate access to resources by different subpopulations is a prevalent issue in societal and sociotechnical networks. We introduce a new class of problems, Graph Augmentation for Equitable Access (GAEA), to enhance equity in networked systems by editing graph edges under budget constraints.
  arXiv  Detail & Related papers  (2020-12-07T18:29:32Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  We introduce a novel method to steer the agents toward a stable population state, fulfilling the given resource constraints. The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian.
  arXiv  Detail & Related papers  (2020-10-21T10:11:17Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  The paper investigates the general problem of resource allocation for mitigating channel fading effects in Free Space Optical (FSO) communications. Under this framework, we propose two algorithms that solve FSO resource allocation problems.
  arXiv  Detail & Related papers  (2020-07-27T17:38:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.