Fair Division with Minimal Withheld Information in Social Networks

We present a study of a few graph based problems motivated by fair allocation of resources in a social network. The central role in the paper is played by the following problem:

What is the largest number of items we can allocate to the agents in the given social network so that each agent hides at most one item and overall at most k items are hidden and no one envies its neighbors. We have shown that the problem admits an \(\mathsf{XP}\) algorithm and is \(\mathsf{W[1]}\)-hard parameterized by \(k\). Moreover, within the running time, we can identify agents that should hide their items and can construct an ordering in which agents should pick items into their bundles to get a desired allocation. Besides this problem we also consider the existence and verification version of this problem. In the existence problem we are given a social network, valuations, a budget and the goal is to find an allocation without envy. In verification problems we additionally are given allocation and the goal is to determine if the allocation satisfies required property.

Ivan Bliznets, Anton Bukov & Danil Sagunov