On Improving Resource Allocations by Sharing

Authors

  • Robert Bredereck Humboldt-Universität zu Berlin, Berlin
  • Andrzej Kaczmarczyk TU Berlin, Berlin AGH University, Kraków
  • Junjie Luo Nanyang Technological University, Singapore
  • Rolf Niedermeier TU Berlin, Berlin
  • Florian Sachse TU Berlin, Berlin

DOI:

https://doi.org/10.1609/aaai.v36i5.20416

Keywords:

Game Theory And Economic Paradigms (GTEP)

Abstract

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

Downloads

Published

2022-06-28

How to Cite

Bredereck, R., Kaczmarczyk, A., Luo, J., Niedermeier, R., & Sachse, F. (2022). On Improving Resource Allocations by Sharing. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4875-4883. https://doi.org/10.1609/aaai.v36i5.20416

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms