具有最小优先级的概率序列和随机优先级机制

应用引理D.9，我们得到了不等式。接下来，我们区分两种情况。首先，假设学生i不是唯一一个吃p的人，也就是说J∈ N\\{i}，t∈ [0，tp）使得j∈ Np（t，e）); 让我们用J.ByLemmaD的这组学生来表示。2由此得出I6=j∈ Np（t，e）) => J∈ Np（t，e）′), T∈ [0，tp）。因此，自从tp≤ 根据假设，我们也有r′jp≥ rjp，J∈ J、 如果tp<t′p，则不等式是严格的。因此，为了达成一个矛盾，假设确实如此。但是自从pis在′最多是总任务量, i、 e.ωp（1，e）′) ≤ ωp（1，e）),这意味着r′ip<rip，这是一个矛盾。因此，我们得出结论：tp=t′和henceNp（t，e′) = Np（t，e）) 在区间[0，tp]上。此外，rip=r′ipand P SLQ( )和P SLQ(′) 必须在[0，tp]上重合。因为算法在[0，tp）和自tc上重合≤ tp，我们必须有tc′=tc，所以在剩下的算法执行过程中（1）- t） =Xp∈Pl（p）- ωp（t，e）)+, T∈ [tp，1]换句话说，这个子问题的算法的行为与PS机制完全相同。正如Bogomolnaia和Moulin（2001）所证明的，这种机制是弱策略证明的，因此我们可以得出结论，Ri=R′i。剩下的情况是，当我是唯一一个从朋德那里吃东西的学生时. 注意，由于rip=ωp（1，e) < 1，我们必须有l（p）=0。此外，r′ip≥ ωp（1，e）′) ≥ωp（1，e）). 然而，回想一下，我们已经展示了ωp（1，e）′) ≤ ωp（1，e）), 所以我们得出ωp（1，e）′) =ωp（1，e）) r′ip=rip。此外，请注意，如果我的首选土地′在[0，tp]上，iis p，theeating算法再次重合，结果后面的参数与上图中的参数相同。

接下来，假设情况并非如此。上段还暗示，不可能存在另一个项目q，即l（q）≤ωq（tp，e）) < u（q）（这意味着q/∈ A） 。这符合方程式D。2和nostudent将被要求在′在t′p>tp之前，不等式是严格的，因为在′这不是假设。如果存在这样的q，因为ωqis是不递减的int和tc′≥ t′p>tp=tc=> t′q>tq，我们得到ωq（1，e）′) = ωq（t′q，e）′) > ωq（tq，e）′) ≥ ωq（tq，e）) = ωq（1，e）)但是，既然我们假设两个赋值都是可行的，n=Xp∈PωP（1，e）) <Xp∈PωP（1，e）′) = 矛盾。总而言之，我们已经证明，如果我是唯一一个从朋德那里吃东西的学生, 总分配ωq（1，e）) 任何项目的∈ P\\{P}要么是l（q），如果在算法执行期间学生在s点被转移到q，要么是u（q），如果项目被完全吃掉。这使我们得出以下结论。我们已经证明，在没有其他参数配置的情况下，我们可以得到Ri6=R′i。然而，由于n∈ N、 0<ωp（1，e）) < 1，并且上下q值是整数，这种配置是不可能的。请注意，我们在上面的假设中假设，在不丧失普遍性的情况下，pis是第一个项目p i，因此学生从p转向p确实没有丧失普遍性，并且不会使我们的结论无效。如果我们选择另一个pll>1的项目，我们的分析结果是ωps（1，e）) 是l（ps）或u（ps），对于所有s=l+1，子问题中的k。这些不一定是整数，但回想一下，我们减去了tpl之前获得的此类项目的分配-1从他们的配额中。因此，它们在原始问题中的总分配是l（ps）或u（ps）；尤其是一个整数。D.1非整数报价下的战略操纵示例D.10。

设N=[2]，P={a，b}，假设项目和学生分别有以下配额和偏好。a bu（·）∞ 2/3 2/3升（·）0 2/3 2/3 =1 2 bb cc A结果随机分配矩阵为R。现在假设1误报′: B′A.′c、 得到的随机分配矩阵是R′，我们得到了R′sd() R6=R′时。R=abc 2/3 0 1/3 10 2/3 1/3 2R′=a b c 2/3 1/3 0 10 1/3 2/3 2E命题5。13.证据。假设有一个随机分配机制，它通常是有效的、无嫉妒的、弱策略性的。让我们用R=R来表示这个机制(). 我们的目的是通过考虑示例D.10中的设置，以及在不同偏好情况下，期望属性对随机分配矩阵集施加的限制，来获得一个矛盾。在下面, 有序效率意味着r2a=0，r1a=2/3。实际上，假设r1b+r1c>1/3，并且r1b>0（情况r1c>0类似）。然后，学生1和2以及项目a和b形成一个有价值的链，这意味着R不是引理5所说的一般有效。9.矛盾。因此，r1a=2/3，r2a=0。让我们参数化r1b=t和r1c=1/3- t代表t∈ [0, 1/3]. 因此，引用b和c以及R的可行性意味着r2b=2/3- t和r2c=1/3+t。让我们表示特定t的随机分配矩阵∈ [0,1/3]通过Rt，isRt=a b c 2/3 t 1- t 10 2/3- t 1/3+t 2检查任何t∈ [0,1/3]，RTI通常效率高且不嫉妒。支持学生1错误陈述给′: B′A.′c、 一会儿保持不变；让我们用′= (′, ) R′=R(′). 通过无嫉妒，r′1b=r′2b=1/3，通过有序效率，r1a=2/3（使用与上述段落类似的参数）。

以下是偏好文件的唯一有序有效且无嫉妒的随机分配′R′=abc 2/3 1/3 0 10 1/3 2/3 2现在假设学生2对′: B′A.′c、 一会儿保持不变；让我们通过′′= (, ′) R′′=R(′′). 无嫉妒意味着r′1a+r′1b=r′2a+r′2b，这反过来又意味着r′1c=r′2c=1/3。依次效率意味着r′\'1a=r′\'2b=2/3。因此，以下是唯一的顺序有效且无嫉妒的随机分配′′R′′=abc 2/3 0 1/3 10 2/3 1/3 2观察任何t∈ [0,1/3]，标准差() R和R′sd() 因为我们要求R是弱策略证明，所以我们需要选择一个合适的t*∈ [0，1/3]所以R′=Rt*= RandR′′=Rt*= R.ButR\'sd() Rt*R′=Rt*=> T*= 1/3andR′sd() Rt*R′n=Rt*=> T*= 这是一个矛盾。因此，我们发现了一个没有随机分配机制的市场，它通常是有效的、无嫉妒的、弱策略证明的。结果如下。