Fair and Truthful Allocations Under Leveled Valuations
<|reference_start|>Fair and Truthful Allocations Under Leveled Valuations: We study the problem of fairly allocating indivisible goods among agents which are equipped with {\em leveled} valuation functions. Such preferences, that have been studied before in economics and fair division literature, capture a simple and intuitive economic behavior; larger bundles are always preferred to smaller ones. We provide a fine-grained analysis for various subclasses of leveled valuations focusing on two extensively studied notions of fairness, (approximate) MMS and EFX. In particular, we present a general positive result, showing the existence of $2/3$-MMS allocations under valuations that are both leveled and submodular. We also show how some of our ideas can be used beyond the class of leveled valuations; for the case of two submodular (not necessarily leveled) agents we show that there always exists a $2/3$-MMS allocation, complementing a recent impossibility result. Then, we switch to the case of subadditive and fractionally subadditive leveled agents, where we are able to show tight (lower and upper) bounds of $1/2$ on the approximation factor of MMS. Moreover, we show the existence of exact EFX allocations under general leveled valuations via a simple protocol that in addition satisfies several natural economic properties. Finally, we take a mechanism design approach and we propose protocols that are both truthful and approximately fair under leveled valuations.<|reference_end|>
@article{christodoulou2024fair,
    title={Fair and Truthful Allocations Under Leveled Valuations},
    author={George Christodoulou and Vasilis Christoforidis},
    journal={arXiv preprint arXiv:2407.05891},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.05891},
    primaryClass={cs.GT}
}