7.3.5 不可分物品的公平分配
由于在生活中并不是所有物品都是可分的，例如教师分配课程，云计算资源的分配。不可分割的物品有很大的应用价值。因此最近的研究对不可分割物品十分关注[18] 。在本节中，我们将介绍不可分物品的公平分配方法。
“分和选”（Divide and Choose）与之前可分割的物品的公平分配
类似，在只有两个参与者时，“分和选”方法十分直观并且有效。其流程是让一位参与者将所有不可分割的物品分成两捆，让另一位玩家去选择自己喜欢的一捆，剩下的一捆给第一个参与者。由于第一个参与者获得的是剩下的一捆，因此他在分成两捆时的最优策略是：
(𝑋1, 𝑋2) ∈ 𝑎𝑟𝑔 𝑚𝑎𝑥
(𝑆1,𝑆2)∈𝒜2(𝑀)
𝑚𝑖𝑛{𝑉1(𝑆1), 𝑉2(𝑆2)}.
Plaut 和 Roughgarden[19] 证明，如果我们通过最大化(𝑋1, 𝑋2)中较
小的捆的大小来打破平局，那么(X1, X2)对第一个参与者总是 MMS 和 EFX 的。而对于第二个参与者来说，他选择的是他更喜欢的一捆，因此对他来说这个分配是无嫉妒的。因此“分和选”方法是 EFX 和 MMS分配。
Sequential Allocation and Round-Robin 同样适用于不可分割物品的平均分配的是顺序拣选分配算法[Brams and Taylor][20] 。Bouveret和 Lang[21] 对其进行了深入的研究和讨论。在这些方法中，参与者有一系列的回合来挑选他们最喜欢的、未被他人挑选的物品。比较流行的顺序拣选分配是 Round-Robin，其中挑选序列重复模式为1, ⋯ , 𝑛。循环算法对不可分割的物品分配都是 EF1（但不一定是 EFX），但对混合分配却不是。为此，Aziz 等人[9] 提出了双循环方法，该方法可以给出针对混合分配的 EF1 分配。Amanatidis 等人[22] 和 Aziz 等人分别设计了更多的挑选序列，以达到近似 MMS 公平性。
Adjusted-Winner 是另一种被广泛使用的在两个参与者的情况下的公平分配方法。其原理是根据两个参与者之间估值的比率对物品进行排序。例如：
𝑉1(1)
𝑉1(2)
𝑉1(𝑚)
𝑉 (1) ≥ 𝑉 (2) ≥ ⋯ ≥ 𝑉 (𝑚) .
2 2 2
并让参与者 1 从左侧开始选择一组连续的保证他是 EF1 的最小物品集（剩余物品给参与者 2）。这样做的好处是确保了两个参与者之间的高社会福利[Bei 等人][23] 。这种分配是 EF1 分配，但不一定是 MMS 或 EFX 分配。
Envy-cycle Elimination 算法本质上是一种贪心算法，在每一轮中，都会为一个参与者分配一个新物品[Lipton 等人][10] 。该算法的核心在于通过参与者之间的物品交换，来确保参与者不会嫉妒别人或者被人嫉妒。该算法基于一个“嫉妒图”，图中的节点对应于一个参与者，如果参与者 i 对参与者 j 感到嫉妒，则在参与者 i 到参与者 j 之
间连一条边。该算法的工作原理是，每一步都将一个未分配的物品分配给一个不受任何其他参与者妒忌的参与者，即嫉妒图中入度为 0的节点。如果不存在这样的参与者，则图中必然包含一个有向循环。那么就可以通过交换循环中的参与者的物品包来解决循环问题，即循环中的参与者获得他指向的参与者的所持有的所有物品。当所有物品都分配完毕时，算法终止。并且可以实现 EF1 分配[Lipton 等人][10] 。
Bag-fifilling Algorithms 对于基于阈值的公平性（如 MMS）十分有效。其原理是假设我们有一个袋子，并不断往里面添加物品，直到某个参与者认为这袋物品已经足够好。然后，这个满意的参与者将袋子拿走，算法对剩余物品重复上述过程。其难点在于如何为袋子选择一个合适的阈值，从而使拿走袋子的参与者的近似值良好，并且给其他参与者剩下足够多的物品。通过进一步的设计和分析，近似率可以提高到 2/3[Garg 等人][24] ，随后进一步提高到 3/4[Garg 和 Taki][25] 。该方法对于 MMS 公平性，有很好的特性[Amanatidis 等人；Garg 等人][24] [26] ，例如规模不变性和在相同排序实例（所有人对于物品的喜好排序相同）上的简化。有趣的是，第二个特性表明，任何用于近似相同排序实例 MMS 分配的算法都适用于一般实例，并保持相同的近似率。利用这些特性，可以大大简化算法的设计。