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.

We study the fair scheduling of jobs among groups of (unrelated) machines and focus on the maximin share (MMS) fairness at the group level. The problem was first introduced by Li et al. [NeurIPS 2023], where each group consists of a number of identical machines (or identical up to different speeds), and the cost of a group is determined by the minimum makespan on completing all jobs assigned to it. It is left as an open problem when the machines within each group are unrelated. In this paper, we first resolve this problem and design a polynomial-time algorithm that computes a 2-approximate MMS allocation via linear programming techniques. We complement this result with a hard instance, showing that no algorithm can be better than $(2-\frac{1}{n})$-approximate MMS, where $n$ is the number of machines. Thus the approximation ratio 2 is asymptotically tight. When the groups consist of identical machines, we improve the approximation ratio to $\frac{4}{3}$.