Envy-free allocations respecting social networks

摘要

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 determining whether they exist is computationally hard even under highly restricted settings. Classical 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 the 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 require that every agent likes its own allocation at least as much as those of all 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 allocation more than those of all its (out)neighbors.