Parameterized Complexity of Envy-Free Resource Allocation in Social Networks

Authors

  • Eduard Eiben University of London
  • Robert Ganian Vienna University of Technology
  • Thekla Hamm Vienna University of Technology
  • Sebastian Ordyniak University of Sheffield

DOI:

https://doi.org/10.1609/aaai.v34i05.6201

Abstract

We consider the classical problem of allocating resources among agents in an envy-free (and, where applicable, proportional) way. Recently, the basic model was enriched by introducing the concept of a social network which allows to capture situations where agents might not have full information about the allocation of all resources. We initiate the study of the parameterized complexity of these resource allocation problems by considering natural parameters which capture structural properties of the network and similarities between agents and items. In particular, we show that even very general fragments of the considered problems become tractable as long as the social network has bounded treewidth or bounded clique-width. We complement our results with matching lower bounds which show that our algorithms cannot be substantially improved.

Downloads

Published

2020-04-03

How to Cite

Eiben, E., Ganian, R., Hamm, T., & Ordyniak, S. (2020). Parameterized Complexity of Envy-Free Resource Allocation in Social Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7135-7142. https://doi.org/10.1609/aaai.v34i05.6201

Issue

Section

AAAI Technical Track: Multiagent Systems