Inhalt des Dokuments
Envy-Free Allocations Respecting Social Networks
Andrzej Kaczmarczyk (TU Berlin)
Finding an envy-free allocation of indivisible resources to agents is a central task in many multiagent systems. Often, non-trivial envy-free allocations do not exist, and finding them can be a computationally hard task. Classic envy-freeness requires that every agent likes the resources allocated to it at least as much as the resources allocated to any other agent. In many situations this assumption can be relaxed since agents often do not even know each other. We enrich the envy-freeness concept by taking into account (directed) social networks of the agents. Thus, we compare every agent's resources with those of its (out)neighbors. This leads to a "more local" concept of envy-freeness. We also consider a strong variant where every agent must like its own allocations more than those of all its (out)neighbors.
We analyze the classic and the parameterized complexity of finding allocations that are envy-free with respect to one of the variants of our new concept, and that either are complete, are Pareto-efficient, or optimize the utilitarian social welfare. To this end, we study different restrictions of the agents' preferences and of the social network structure. We identify cases that become easier (from (Sigma^P_2)-hard or NP-hard to P) and cases that become harder (from P to NP-hard) when comparing classic envy-freeness with our graph-based envy-freeness. Furthermore, we spot cases where graph envy-freeness is easier to decide than strong graph envy-freeness, and vice versa.
This is a joint work with Robert Bredereck and Rolf Niedermeier.
Back to the research colloquium site.