EFX Graph Division with (Weakly) Lexicographic Preferences
摘要
We study the fair division of indivisible items on undirected graphs under lexicographic preferences, which conside vertices as goods to be allocated to n agents, with the requirement that the bundles have to be connected. We prove that when the graph is a complete bipartite graph and the number of vertices on both sides is greater than n, an envy -free up to any good (EFX) division always exists. By introducing parameter k to relax the classical definition of lexicographic preferences, we prove that when \(k\le n-1\) , there does not always exist an EFX division for paths. However, if \(k = n\) , an envy-free division can always be found for connected graphs. Moreover, under weakly lexicographic preferences, we provide an algorithm based on the maximum weight matching algorithm that can output an EFX division in polynomial time.