TY - JOUR
T1 - Fair division with minimal withheld information in social networks
AU - Bliznets, Ivan
AU - Bukov, Anton
AU - Sagunov, Danil
N1 - Publisher Copyright:
© 2024 The Author(s)
PY - 2024/4/12
Y1 - 2024/4/12
N2 - 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 show that the problem admits an XP algorithm and is W[1]-hard parameterized by k. Moreover, within the running time, we can identify agents that should hide its items and can construct an ordering in which agents should pick items into its bundles to get a desired allocation. Besides this problem, we also consider the existence and verification versions 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 the verification problem, we are additionally given an allocation, and the goal is to determine if the allocation satisfies the required property.
AB - 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 show that the problem admits an XP algorithm and is W[1]-hard parameterized by k. Moreover, within the running time, we can identify agents that should hide its items and can construct an ordering in which agents should pick items into its bundles to get a desired allocation. Besides this problem, we also consider the existence and verification versions 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 the verification problem, we are additionally given an allocation, and the goal is to determine if the allocation satisfies the required property.
KW - EF1 allocation
KW - Fair division
KW - Fixed-parameter tractable
KW - FPT-algorithm
UR - http://www.scopus.com/inward/record.url?scp=85184992621&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2024.114446
DO - 10.1016/j.tcs.2024.114446
M3 - Article
AN - SCOPUS:85184992621
SN - 0304-3975
VL - 991
JO - Theoretical Computer Science
JF - Theoretical Computer Science
M1 - 114446
ER -