Efficient and Fair Allocation on Graphs: From Orientation to Position-Aware Valuations

摘要

In traditional resource/task allocation models, an agent's value on an item is fixed regardless of when, where, or how the agent consumes the item. In this work, we introduce a more general framework involving a set of positions (for example, roles within a company), where agents have valuations that depend on the specific positions they are assigned. This setting is well motivated as the agent faces different resources and support at different positions, and thus may need varying levels of effort to complete the item, supposing the items are chores. We further consider the constrained setting when each item can only be allocated to a certain set of positions (e.g., a research project cannot be assigned to an administrative staff). We particularly consider the case when the constraints form a graph where edges are items and vertices are positions, so an item can only be allocated to an incident position, which is known as the orientation problem [Christodoulou et al. EC 2023]. In this paper, fairness is measured by maximin share (MMS), and efficiency is measured by Pareto and social optimality. We present a complete set of results on the computational complexity and approximation algorithms for computing efficient and fair allocations.