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

集合Pn表示学生集合N对项目集合P的所有偏好。我们用元组（N，P，l，u，).学生i从项目Q子集中选择φi（Q） P是QAS中最好的项目i、 也就是φi（Q）=p<==> P∈ Q和pip′，p′∈ 给定一个市场（N，p，l，u，), 作业是一种通信：N∪ P→ N∪ P，这样下面的公式就成立了。u（i）∈ P我∈ 氮气。u（p）∈ 2N，P∈ P3。我∈ 氮磷∈ P，我们有u（i）=P当且仅当i∈ u（p）如果每个项目都满足其配额，那么分配u是可行的，也就是说P∈ P，l（P）≤ |u（p）|≤u（p）。我们用D表示可行的确定性赋值集。我们可以用n×k零一行随机矩阵xx=[xip]i来描述一个可行的确定性指派∈N、 p∈我们称之为赋值矩阵。我们用学生标识行，用项目标识列。对于每个条目xipof X，xip=1，当且仅当我被分配到项目p的空间，我们有（p）≤十一∈Nxip≤ u（p），P∈ PPropotion 3.1和相关讨论。除非另有说明，我们可能会稍微滥用符号，用P表示项目座位集。和XP∈Pxip=1，我∈ NWe表示X的第i行，X（t）表示迭代过程的步骤/时间t的分配（本文中我们将对任何矩阵使用这种表示法）。随机分配是P上的概率分布。我们将用L（P）表示随机分配的集合。随机分配是可行确定性分配上的概率分布；我们将用L（D）来表示这个集合。

相应的赋值矩阵的凸组合表示给定学生被分配给定项目的概率：R=[rip]i∈N、 p∈P、 其中R=XX∈DλXX，使得λX≥ 0, 十、∈ D和XX∈DλX=1随机分配矩阵R是n×k行随机矩阵；它的第i行是student i.Budish等人（2013）的随机分配，扩展了著名的Birkho ff-Von Neumann双随机矩阵定理，该定理表示每个双随机矩阵都可以写成排列矩阵的凸组合，适用于我们更一般的行随机矩阵设置。下面是他们结果的直接结果，并表示本文中的任何随机赋值都可以在确定性赋值上实现。提议3。1.任何可行随机分配矩阵都可以写成可行确定性分配矩阵的凸组合。L（D）中的任意两个概率分布导致同一行随机矩阵R将无法区分，因为它们为每个学生提供相同的效用水平。因此，我们用它的行随机矩阵R，它的随机分配矩阵来识别arandom。我们用可行随机分配集或等价随机分配矩阵来表示。最后，一种确定性分配机制是映射ψ：Pn→ D、 这是一个函数，它接受学生的任何偏好，并输出一个可行的、确定性的学生作业，以进行项目。类似地，随机分配机制是Φ：Pn的映射→ R，输出一个可行的随机赋值。我们用ψ表示() (Φ()) 参考文件的结果（随机）分配∈ 请注意。3.1效率、激励和公平优先顺序离子P诱导随机分配集合L（P）的偏序，我们称之为与之相关的随机优势关系用sd表示的土地(i） 。

从最喜欢的到最不喜欢的ias p知识产权我··ipk。我们是维克托里∈ 他草率地控制了易建联∈ 关于iift=1，2，k、 我们有txj=1ripj≥tXj=1yipjZero一个n×n矩阵，其中每一行和每一列之和为一。约束结构H是一个层次结构（也称为层流族），如果S、 T∈ H我们有以下一种观点：S T还是T S还是S∩ T=. 如果一个约束结构H可以写成两个不相交的层次结构的并集，我们就说它是一个双层次结构。Budish等人（2013年）证明，约束结构为双层次结构的条件是行次随机矩阵可实现的充分条件。很容易看出我们问题中的约束结构是一个双层次结构。优先考虑, 我们说R∈ R随机支配Y∈ R如果Risd(i） 哎,，我∈N和r6=Y。如果随机分配矩阵R不受任何其他随机分配矩阵的随机支配，则它通常是有效的。我们转向公平。随机分配∈ R在Profile没有嫉妒∈ 如果每个学生都喜欢自己的分配而不是其他学生的分配，那就是i、 j∈ N、 我们有Risd(i） Rj。如果i、 j∈ N、 Rjsd(i） 里=> Ri=Rj。上面介绍的随机分配的两个性质都扩展到了机制。随机分配机制Φ是策略证明，如果对任何学生来说，报告她的真实偏好弱地支配任何其他行为，也就是说，如果对任何学生来说∈ N、 有什么优惠吗∈ Pn和偏好排序′我∈ P、 我们有() sd(i） Φi(′我-i） 。如果在错误陈述偏好的情况下，没有学生能够在真实报告的情况下获得严格支配分配的分配，那么这是很弱的策略证明。

形式上，Φ是弱策略证明，如果对于任何一个∈ N、 有什么优惠吗∈ Pn和偏好排序′我∈ P、 我们有(′我-i） sd(i） Φi() =>Φi(′我-i） =Φi().4.低报价下的随机优先权机制下列机制是优先权机制的自然延伸。Giadakis等人（2016年）也发表了类似的版本。我们在这里描述它是为了完整性，因为它允许我们定义RPLQ机制，并在RP和PSQ机制的扩展之间绘制平行线。据我们所知，我们是第一个在这种情况下考虑统一彩票优先机制的人。4.1低引号下的优先级机制由n个字母上的一组排列表示，这组排列由学生的所有顺序组成。确定一个市场（N，P，l，u，) 和一个置换σ∈ Sn。权力配额下的优先权机制（PrioLQ），我们将用|∑=P rioLQ表示()σ然后按如下步骤进行：步骤1：学生σ（1）被分配到她最喜欢的项目的座位，根据σ（1），即μσ（σ（1））=φσ（1）（P）。。。步骤k：用Pkl表示 P在步骤k开始时未满足较低配额的项目集。IfXp∈Pkll（p）-十一∈Nxip（k）！<N- k+1（4.1）学生σ（k）根据其优先顺序被分配到她最喜欢的可用项目中σ（k）。除此之外，学生σ（k）是她在Pkl最喜欢的项目中的一个位置。形式上，μσ（σ（k））=（φσ（k）P\\Sk-1j=1μσ（σ（j））, 条件4。1σ（k）Pkl, 另一方面，由于集合N和P是有限的，因此很明显算法会在有限的时间内终止。此外，还需要检查最终分配是否可行。

因为| Sn |=n！，我们有n！优先级机制，每一种机制都是由一组学生的不同排列引起的。注意：选择特定分配的顺序不必是唯一的。显然，任何优先级机制都不会对称地对待学生：学生σ（1）总是得到她最喜欢的项目，而σ（n）得到剩下的任何项目。恢复公平性的一种方法是随机分配确定性的任务，我们将在下一节讨论。它也可以使用主列表（ML）来解决，这是一种独立于学生的参考文献的外部排序。例如，可以根据学生的累积GPA、出勤记录或课外活动创建此类排序。在确定性的情况下，我们引入以下公平的概念。效率的定义反映了对项目施加的限制。定义4.1。分配u∈ D是1。当μ（j）时，ML为一般iu（i）对于某些i，j∈ N、 在主列表中，j在i之前。2.如果不是由任何其他u′控制的帕累托，则最低配额受限有效∈ D、 我们所说的∈ D帕累托主导u′∈ 在一家公司工作∈ Pnif我∈ N使u（i）我（我）和J∈ N、 u（j）ju′（j），其中u（j）ju′（j）如果u（j）ju′（j）或u（j）=u′（j）。这两个属性都扩展到了机制。如果与所有成员如实报告相比，没有任何学生联盟能够通过联合误报使所有成员至少发挥同样的作用，并且至少有一个成员严格地发挥更好的作用，那么机制ψ是强有力的群体策略证明。形式上，如果没有∈ 请注意，S N、 及′s∈ P | S |使得ψi(′s-（S）iψi(), 我∈ S和J∈ 这就是ψj(′s-（S）jψj().提议4。2.对于任何市场（N、P、l、u、，), PrioLQ是：1。最低限额限制效率2。强有力的团队战略3。ML fairWe称读者为Tofragidakis等人。

（2016）以证明（2）和（3）。（1）的证明遵循与经典优先级机制类似的论点，省略。4.2彩票机制该机制如下所述：确定偏好文件∈ Pn，从sna上的均匀分布中随机抽取学生σ的排列，然后运行P rioLQ()σ.偏好文件的低配额随机优先级机制（RPLQ）,我们将用RP LQ来表示(), 然后定义为稍微滥用符号，我们用P\\Sk表示-1j=1μσ（σ（j））学生σ（1）到σ（k）之后的剩余项目集- 1） 他们做出了选择。这种公平的概念相当于双边匹配市场中公正的无嫉妒性，其中市场的一方优先于另一方，例如在学校选择方面。RP L Q() =NXσ∈SnP rioLQ()σ由于RPLQ是可行的帕累托最优确定性分配的凸组合，因此由此产生的随机分配也是可行的且有效的。例4.3。较低的配额会引发嫉妒。假设N=[4]和P={a，b，c}没有配额。让学生有偏好 如下所示；把这个市场叫做Γ。然后RP LQ（Γ）输出矩阵R。这个随机分配是无嫉妒的，因为每个学生都被分配了她的首选。现在假设l（b）=2，l（c）=1，而l（a）=0；让我们称之为市场ζ。由此产生的随机赋值rplq（ζ）是R′。 =1 2 3,4a a bb c ac b cR=a b c 1001,20103，4R′=ABC“#1/21/411/411/2101/2207/818 3，观察到R′并不随机支配R′相对于, 所以这个随机分配不是没有嫉妒心的。RPLQ满足了一个较弱的无嫉妒概念。策略证明是PrioLQ策略证明的自然延伸。这些结果与随机优先机制一致（Bogomolnaia和Moulin，2001）。提议4。4.对于任何市场（N、P、l、u、，), RPLQ机制是1。

防战略2。这是免费的。附录A。RPLQ通常可能是无效的；效率低下也可能完全是由较低的配额造成的。例4.5。设N=[6]和P={a，b，c，d}。补充l（b）=l（c）=2，并且没有其他配额。学生有偏好. 由此产生的随机分配矩阵是R，它由R′随机支配。 =1,2,3 4,5,6a bb ac dd cR=a b c d 3/5 1/15 1/3 0 1,2,30 2/3 1/3 0 4,5,6R′=a b c d 2/3 0 1/3 0 1,2,30 2/3 1/3 0 4,5,65低引用下的概率序列机制，如Bogomolnia and Moulin（2001）的PS机制，是经典随机分配问题有序有效随机分配机制集中的核心元素。在饮食算法中，时间在0到1之间连续运行，学生以恒定的单位进食速度从他们最喜欢的可用项目中进食。当且仅当项目完全吃光时，他们才被要求离开他们目前正在吃的项目，在这种情况下，他们会转移到下一个最喜欢的可用项目。我们遵循与PrioLQ相同的基本理念：只要有足够的时间满足所有较低的配额，就允许学生从他们最喜欢的可用项目开始学习。当约束开始“咬人”时，我们将其菜单限制为尚未满足较低配额的项目。我们注意到，该机制可被视为解决了inAshlagi等人提出的具有分布约束的问题的一个特例。

（2020）所有学生都属于同一类型。5.1进食算法与PrioLQ类似，在低配额下概率序列（PSLQ）的设计中，我们需要确定在执行的任何时间点呈现给学生的菜单，以及学生应该被转移到消费可能无法满足其低配额的项目的最佳时间。直觉上，如果我们继续使用相同的饮食模式，只要其他项目都能满足他们的配额，学生就应该被允许食用她最喜欢的项目。例5.1。假设N=[5]和P={a，b，c}。假设项目和学生分别有以下配额和偏好，a b cu（·）2 2l（·）1 2 =1,2 3,4 5a b cb a ac c bR=a b c“#3/4 0 1/4 1,20 3/4 1/4 3,40 0 1观察到学生5无法独自满足较低的c配额。因此，我们寻找临界时间tc∈ [0,1）因此，如果我们继续保持相同的饮食模式稍长一点，我们将无法满足较低的c配额。作为条件4.1的连续类似物，当考虑到PrioLQ时，我们假设Tc必须满足（1- tc）=l（c）- 这就是剩余的学生人数，在5号学生吃到tc之前，完全足以满足较低的c配额。重新排列，我们得到C=n- l（c）n- 1=生成的随机分配矩阵为R，这显然是可行的。考虑任何一点∈ [0，1]在算法执行期间，用R（t）表示此时的分配矩阵（即，输入rip（t）表示在时间t之前，我从项目p吃了多少学生）。我们必须确保R（1）是可行的。在下文中，我们定义了（·）+：R→ R≥0为（x）+=max{0，x}。修正t∈ [0, 1]. t，n（1）- t） 是可以分配给projectsP的剩余学生人数。

我们将用元组[zp（t）]p来表示这种分布∈P∈ Rk≥0，wherePp∈Pzp（t）=n（1）- t） 。为了使解决方案可行，我们需要zp（t）+Xi∈Nrip（t）≥ l（p），P∈ 预先安排，我们有ZP（t）≥ l（p）-十一∈Nrip（t），P∈ 自zp（t）以来的Pand≥ 0, P∈ P根据定义，我们有zp（t）≥l（p）-十一∈Nrip（t）+因此，将所有项目相加，n（1- t）=Xp∈Pzp（t）≥Xp∈Pl（p）-十一∈Nrip（t）+（5.1）注意分布的集合[zp（t）]p∈P、 与部分赋值R（t）一起，确定在t=1时可得到的可行随机赋值矩阵集。这激发了以下定义。定义5.2。修正t∈ [0, 1]. 我们说p项目∈ 当（i）l（P）>Pi时，P在t处有效∈Nrip（t）；或（ii）l（p）≤圆周率∈Nrip（t）<u（p）和N（1）- t） >Xp∈Pl（p）-十一∈Nrip（t）+我们用A（t）表示时间t的活动项目集。为了确保R（1）是可行的，我们将学生的选择限制为A（t）中的所有项目∈ [0, 1].例5.3。例5。1.继续。如例5.1所示，在tc=3/4时，n（1- tc）=l（c）- tcSincePi∈Nrip（t）>l（p），对于p=a、b和pi∈Nric（t）<l（c），tcis c唯一的活跃项目。在我们正式定义迭代过程之前，让我们再介绍一个概念。我们将χipto定义为一个指标函数，它告诉我们学生i在t时是否在吃项目p。χip（t）=（1，p=φi（A（t））0，否则我们假设所有代理都有单位进食速度。优先考虑, 进食算法定义为以下一系列递归步骤。设t=0，A=A（0）=P，R=R（0）=[0]i∈N、 p∈P.给定t，A，R，电视-1，Av-1=A（电视）-1） ，房车-1=R（电视）-1） ，为了所有的p∈ Av-1定义：1。电视（p）=sup{t∈ [0,1]：Xj∈N房车-1jp+χjp（电视）-1） （t）- 电视-1)< u（p）}2。τv=minp∈Av-1tv（p）3。λ=sup{t∈ [0,1]：n（1）- t） >Xp∈Pl（p）-十一∈Nrip（电视）-1) - χip（电视）-1） （t）- 电视-1)!+}4.tv=min{τv，λ}5。rvip=rv-1ip+χip（电视）-1） （电视）- 电视-1), 我∈ N、 p∈ P6。

如果λ>τv，则letAv=Av-1\\{p∈ Av-1:tv（p）=tv}else letAv=Av-1\\{p∈ Av-1:l（p）-十一∈Nrip（电视）-1) - χip（电视）-1)λ!+= 0}按构造，Av Av-1对于所有周期v等J∈ N使得Aj=. 我们定义SLQ() = Rj=R（1）表示偏好文件. 请注意，eating算法是一个异常的mous：映射→ P SLQ( ) 从n首选项来看是对称的伊藤是一个天才。注意，如果我们定义c=inf{t∈ [0,1]：n（1）- t） =Xp∈Pl（p）-十一∈Nrip（t）！+}（5.2）然后n（1）- t）=Xp∈Pl（p）-十一∈Nrip（t）！+，t>tc（5.3），因此，如果tc<1，学生在某个时间停止进食的所有项目∈ （tc，1]总分配等于他们的较低配额。因此，如果有学生在任何t点转移到项目p∈ （0，1），尤其是，它必须保持t≥ tc，所以p的总分馏率为l（p）。如果tc=1，我们恢复PS机制。5.2有序效率和无嫉妒Bogomolnaia和Moulin（2001）根据项目集定义的以下二元关系的无环性，描述有序效率。定义5.4。给定一个随机分配矩阵R∈ R和偏好文件∈ P、 我们定义了二元关系τ（R，) 在项目集P上，如下所示p、 q∈ P:Pτ（R，) Q<==> 我∈ N:piq和riq>0关系τ（R，) 是循环的，如果存在形式为pτpτ的关系循环。。。τpnτp（用τ表示τ（R），)).在我们的环境中，τ的无环性并不是衡量有序效率的有效标准，从例子4可以推断出这一点。3.Kojima和Manea（2010）考虑了最大配额和外部选项的问题；有序效率的特征是τ（R）的非循环性) 不浪费。定义5.5。