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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

EFX Graph Division with (Weakly) Lexicographic Preferences

  • Kuncheng Shao,
  • Hao Guo

摘要

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.