TY - JOUR

T1 - Fair division with minimal withheld information in social networks

AU - Bliznets, I.

AU - Bukov, A.

AU - Sagunov, D.

N1 - Export Date: 21 March 2024 CODEN: TCSCD Адрес для корреспонденции: Bliznets, I.; University of GroningenNetherlands; эл. почта: iabliznets@gmail.com Сведения о финансировании: European Research Council, ERC Сведения о финансировании: Russian Science Foundation, RSF, 18-71-10042 Сведения о финансировании: Horizon 2020, 853234 Текст о финансировании 1: Research presented in section 3 was supported by Russian Science Foundation (project 18-71-10042 ). Research in sections 4 - 5 was partially supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 853234 ).

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. © 2024 The Author(s)

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. © 2024 The Author(s)

KW - EF1 allocation

KW - Fair division

KW - Fixed-parameter tractable

KW - FPT-algorithm

KW - Graphic methods

KW - Parameter estimation

KW - Existence problems

KW - Fair allocation

KW - Fair divisions

KW - Following problem

KW - FPT algorithms

KW - Graph-based

KW - Parameterized

KW - Running time

KW - Budget control

UR - https://www.mendeley.com/catalogue/b2980dda-d8a4-32b6-a2f5-8fa80c9b30b3/

U2 - 10.1016/j.tcs.2024.114446

DO - 10.1016/j.tcs.2024.114446

M3 - статья

VL - 991

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

M1 - 114446

ER -