3 accepted papers
We study almost envy-freeness in house allocation, where m houses are to be allocated among n agents so that every agent receives exactly one house. An envy-free allocation need not exist, and therefore we may have to settle for relaxations. We study different aggregate measures of envy as markers o
A graph G is c-closed if every two vertices with at least c common neighbors are adjacent to each other. This definition is an abstraction of the triadic closure property exhibited by many real-world social networks, namely, friends of friends tend to be friends themselves. Social networks, however,…
We study the computational complexity of fair division of indivisible items in an enriched model: there is an underlying graph on the set of items. And we have to allocate the items (i.e., the vertices of the graph) to a set of agents in such a way that (a) the allocation is fair (for appropriate no…