The envy-free matching problem with pairwise preferences

Abstract In this paper, we consider the situation where each agent has a preference over a subset of items and exactly one item is matched to each agent. The envy-freeness of a matching guarantees that no one has envy for the others. We consider an envy-free matching in the situation where each agent has a preference that is defined based on comparisons of any two acceptable items. We prove that in this situation, the problem of checking the existence of an envy-free matching is generally hard.