Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations

Fair allocation is a central problem in economics since decades. It arises naturally in real-world applications such as advertising, negotiation, rent sharing, inheritance, etc [14, 15, 16, 21, 29, 35]. In discrete fair division, the basic scenario is that we want to distribute a set M of m indivisible items among n agents, such that the allocation is deemed fair by the agents.