We study the fair division of indivisible items on complete bipartite graph under weakly lexicographic preferences, which considers vertices as goods to be allocated to n agents, with the requirement that the bundles have to be connected. We prove that for any complete bipartite graph, there exists an instance where no connected EFX allocation can be found. However, for a complete bipartite graph such that the number of vertices on both sides is greater than n, a connected EF1 allocation can always be found.

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

Complete Bipartite Graph Division Under Weakly Lexicographic Preferences

  • Kuncheng Shao,
  • Hao Guo

摘要

We study the fair division of indivisible items on complete bipartite graph under weakly lexicographic preferences, which considers vertices as goods to be allocated to n agents, with the requirement that the bundles have to be connected. We prove that for any complete bipartite graph, there exists an instance where no connected EFX allocation can be found. However, for a complete bipartite graph such that the number of vertices on both sides is greater than n, a connected EF1 allocation can always be found.