Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise
Many scenarios where agents with restrictions compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have restrictions that make them incompatible with some resources. We assume that a Principle chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their restrictions within certain limits. The Principle's goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We establish hardness results for some variants of this budget-constrained maximization problem and present algorithmic results for other variants. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.
Code (1)
Similar Papers 제목 키워드 기반
Implementability of Honest Multi-Agent Sequential Decision-Making with Dynamic Population
We study the design of decision-making mechanism for resource allocations over a multi-agent system in a dynamic environment. Agents' privately observed preference over resources evolves over time and the population is d…
Decision MakingSequential Decision MakingFacilitating Matches on Allocation Platforms
We consider a setting where goods are allocated to agents by way of an allocation platform (e.g., a matching platform). An ``allocation facilitator'' aims to increase the overall utility/social-good of the allocation by …
On Maximum Weighted Nash Welfare for Binary Valuations
We consider the problem of fairly allocating indivisible goods to agents with weights representing their entitlements. A natural rule in this setting is the maximum weighted Nash welfare (MWNW) rule, which selects an all…
Possible and Necessary Allocations via Sequential Mechanisms
A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given f…
Multi-Agent Reinforcement Learning Based Resource Allocation for UAV Networks
Unmanned aerial vehicles (UAVs) are capable of serving as aerial base stations (BSs) for providing both cost-effective and on-demand wireless communications. This article investigates dynamic resource allocation of multi…
Multi-agent Reinforcement LearningQ-Learningreinforcement-learningReinforcement Learning+1