全偏好域上的约束序列规则

此外，通过我们对对象的选择，我们对所有(，0，0)∈F有((0))≥((0))≥(0，0))，对所有∈F也有((0))≥((0))。然而，由于((8))>((8))≥，这与Lemm A3.3相矛盾。3.3计算复杂性如命题3.1所示，该机制在最多的回合中终止，并分别表示不同的主体和对象的nu mber。在每一轮中，该算法解决了一个线性prog ram的实例来计算。进一步，该算法利用eeds对瓶颈Agent集合进行筛选。我们现在证明了在多项式时间内，通过求解至多线性规划的非齐次，可以找到它。我们回想起，任何一个极小的主体集，其（,，(0)∈)的目标值等于。算法2提供了一个简单的程序来筛选这样的氨基集合。我们将初始化为所有代理的集合。在每一步中，算法都考虑从。如果去掉这样一个agent使线性规划获得更高的目标值，那么很明显agent一定属于瓶颈。另一方面，如果线性规划obtai ns的ob jective值仅为，那么agent可以安全地从考虑si中删除，因为它是一个较小的候选集。input：,..,do（{},，(0)∈)的目标值；如果==then（{}）endendReturn算法2：寻找瓶颈集的过程算法M2至多以迭代结束，因此总的来说，约束规则的每一轮最多需要求解(+1)个线性p个rograms。因此，算法1可以在约束的大小、代理和对象的数量为多项式的时间内执行。3.4可实现性对象分配机制中的随机化经常被用作从预先的角度结合公平的工具。随机分配机制的结果被视为确定性结果之上的概率分布，从这种分布中得出的结果是在实践中得到实现的。根据Birkho-von Neumann定理，每个双随机的随机分配都可以实现为对可实现的确定性分配的抽签，即每个agent都是一个对象，每个对象都被分配给一个agent的deter ministic分配。然而，在存在任意约束条件的情况下，这样的对满足这些约束条件的deterministic赋值的抽奖分解可能不存在。下面的例子说明了这种情况。考虑一个简单的例子，一个主体={1}，三个对象={，,}，在存在约束1，+1，≤2/3，1，+1，≤2/3和1，+1，≤2/3的情况下，随机问题的一个潜在的可行解是设置1，=1，=1，=1/3。然而，可以很容易地看出，并不存在满足这三个约束的确定性分配，仍然存在Ns1,+1,+1,=1。在许多实际应用中，人们可以表明，满足这些约束的任意随机分配都可以表示为对Deter-ministic分配的抽奖。例如，Nguyen等人对于具有有限补点的组合ass对齐问题。（2016）证明人们总是可以将一个可行的分配分解为一个对determi nistic分配的抽奖，这里每个对象的容量被至多加法所侵犯，其中表示最大外滩的大小。

在第4节的具体应用中，我们对d和ai进行了具体的实现。另一方面，我们对随机分配解施加约束的模型，广义上是对后确定性结果施加约束的方法。正如Balbuzanov(2019)所指出的，任何一组关于后置任务的树状约束都可以用随机赋值上的一组l线性不等式来表示。虽然这样的约简总是存在的，但它不是计算上的。4应用本节，我们讨论了如何将约束序列规则应用于约束对象分配的几个具体应用。4.1无约束对象分配我们可以将我们的模型应用于无约束对象分配问题，只要对所有的在这种情况下，约束条件下的随机分配输出与Katta和Sethuraman(2006)的扩展概率串行算法所给出的随机分配输出一致，本文讨论了扩展概率串行算法。在每一轮中，扩展的概率算法构造了一个Generow n et工作，其中Agent在该轮中的对象集合中选择他们最喜欢的红色对象。在参数最大-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-我们注意到，这个agent集合恰恰是这个roun d中最受约束的集合，即agent能从她的偏好对象中得到恰好是λ()（而不是更多）的概率共享。在constrainedseri al r ule算法中，由于没有其他约束限制t h e随机作为签名，因此同一组智能体将被选为t he bott Renekk集。4.2双层次约束Budish et al.（2013）考虑了具有一般配额约束的对象分配问题，提出了一大类普遍可实现的约束，称为“双层次约束”，即满足这些约束的任意随机分配都可以在满足相同约束的确定性分配上实现。它们的约束形式为≤p(，)∈，≤，其中×是一组agent-object对，x是确定性分配，并且都是整数。constraintstructure H=(，)由这些约束的集合组成。onH的一个附加要求是它必须包括所有的sin gleton集。一个约束结构H是一个层次结构，如果对于每一个，\'∈H，\'or\'或\'orTM\'=.最后，H是一个b I-层次结构，如果它是H,那么H=HühandHüH=.是一个b I-层次结构，那么H是一个b I-层次结构，如果H是H,则H是b I-层次结构。布迪什等人。（201 3）提出了两层次配额约束下的对象分配的广义概率串行机制。然而，它们的机制只对上限配额起作用，并假定所有的下限=0。相反，我们可以直接使用我们的约束序列rul e算法m中的约束结构H中的不等式（即使在偏好关系中存在间接关系的情况下），通过对所有的(，)∈R的ΔC(Ⅵ)={x∈ΔD≤x(，)∈H}进行推导，从而推广了Budish等人的方法。即使对于下限配额限制，我们也能做到这一点的关键技术创新在于，我们的算法在任何时间都向前看，以确保在任何时间得到的部分会导致一个可行的随机分配。4.3类型依赖的分布限制Sashlagi等人。（2020）不符合ABI-层次结构的学习类型依赖的d Istribute约束。在这种设置中，每个agent与一个type age相关联，其中表示一组类型。Let表示一组任意的agent类型，Let更是表示一个任意的对象。

一个单一的con strint是t-h-e形式，≤pε，≤，即该机制对一个给定对象上属于特定agent类型集合的所有agent的总分配量施加限制和上限配额。如前所述，可以很容易地看出，这种分布约束可以很容易地在我们的框架中表示。由于约束不符合一个双层次结构，我们的机制的结果不能总是作为对可行的决定性分配的抽签来实现。然而，正如Ashlagi等人所表明的那样。（2020）将满足这些约束的随机分配分解为一个几乎可行的确定性结果上的分布，其中每个约束和上限约束都是由at mo st.4.4显式的事后约束Balbuzanov(2019)考虑了当我们是givenan显式的事后可行分配列表，并且t h e随机分配必须作为对t h es e分配的抽奖而隐含时的随机obj ect分配问题。对于一个偏好，设(th)是所有允许确定性赋值的集合，ΔC(th)是集合C的凸壳。他证明了对于每个(th)，存在一个由矩阵参数化的极小约束集，对于所有(，)∈×和约束，≥0,且向量≥0使得ΔC(th)={x∈ΔD x≤}。Hegenerali利用概率SERIAL机制将这些不等式结合到Agent具有严格偏好的情况下。4.5组合赋值是另一类p roblems，其中ou r机制可以应用于当偏好表现出复合性时，将不可分对象的包分配给Agent的问题（Budish（2011）；Budish和Cantillon(2012)；Nguyen et al.(2016))。形式上，设为一组底层对象，其中每个对象都是副本。一个物体的bun可以用avector表示，在N+中，这个向量的第1个坐标对应于该物体的拷贝数，并且N+=Nü0}。设={∈N+P∈≤}最多是所有大小束的集合。我们假设每个包在单个副本中可用。每个agent都有兴趣In从集合中消耗一个bundle，并且在集合上有一个Compleet e和传递偏好。这类问题中的一个常见应用程序是课程分配问题。每个学生最多只能被分配一个课程表，其中每门课都有一定的座位数。这个可行的随机分配集合可以用下面的一组con-straints来描述，该集合使任一物体的分配总量至多等于它的供应量。在每个偏好条件下，我们有:ΔC(t)=ΔC={∈ΔDx∈X∈·,≤，Δ∈}。从定义2.2中可以看出，所有的智能体在能力约束条件下都是相同类型的。在此之前，受约束的seria l ru le保证了通常受约束和无嫉妒的结果。此外，正如Nguyen等人所指出的那样。

（2016年），该机制的任何结果都可以作为对违反供应限制的确定性分配的抽签来实现。参考abdulkadirooglu，阿蒂拉和泰芬·桑梅斯，“学校选择：一种机制设计方法，“美国经济评论，2003年，93(3)，72 9-747.阿克巴普尔，穆罕默德和阿夫申·尼克扎德，“近似随机分配机制”，2014.阿什拉吉，伊泰，阿明·萨贝尔一世，还有阿里·沙梅利，“分布约束下的分配机制”，OperationsResearch,2020年，68(2)，467-479.巴尔布扎诺夫，伊万，“约束随机匹配”技术报告，工作文件2019.Biró，佩特，塔马斯·弗莱纳，罗伯特·W·欧文，和大卫·F·曼洛夫，“大学招生申请低配额和普通配额”，“理论计算机科学，2010年，411(34-36)，3136-3153.博戈莫尔纳亚，安娜，“随机分配：修改系列规则，“经济理论杂志，2015年，158,308-318。和埃尔韦·穆林，“随机分配问题的新解法”，经济理论杂志，2001年，100(2)，295-328.布迪什，埃里克，“c ombinatorial指派问题：收入相等的近似共--复合均衡“,《政治经济学杂志》,2011年，119(6)，1061-1103。埃斯特尔·坎蒂隆，“多单位分配问题：课程分配的理论和证据，“美国经济评论，2012年，102(5)，2237-71，车延九，小岛富仁、保罗·米尔格罗姆，设计随机分配机制：《美国经济评论》，2013年，103(2)，585-623.陈，颜和Tayfun S"onmez，“改善校园住房的安全性：一项外周研究，“美利加经济评论，2002年，92(5)，1669-1686.德拉克雷塔兹，大卫，斯科特·杜克·科米纳斯，亚历山大·泰特尔博伊姆，“难民安置”，牛津郡大学经济系工作文件，2016.埃切尼克，费德里科和M Bumin Yenmez，“如何控制受控学校选择”，《美国经济评论》，2015年，105(8)，2679-94。，安东尼奥·米拉莱斯，而张俊，《受约束的伪市场均衡》，arXiv预印本arXiv:1909.05986，2019年。埃勒斯，拉斯，伊萨·哈法利尔，M Bumin Yenmez，穆罕默德·耶尔德勒姆，“有控制的cho冰约束的学校选择：硬边界与软边界，“经济组学理论杂志，2014年，15 3,648-683.埃尔迪尔，Aytek和Haluk Ergin，经济理论杂志，2017,17,268-292。Fleiner，Tamás和Naoyuki Kamiyama，《用较低的配额稳定并购交易的拟阵分析》，《数学运筹学》，2016年，41(2)，734-744。Foley，Duncan K,《资源分配和产业部门》，《耶鲁生态经济学论文集》，1967年。Fragiada kis，Daniel和Peter Troyan，《在硬分配约束下改进匹配》，Theo reticalEconomics，2017，12(2)，863-908。Goto，Masahiro，Ryoji Kurat a，Naoto Hamada，Atsushi Iwasaki和Makoto Yokoo，《用等级制度改进非浪费匹配的《最低配额》，载于“2015年自治代理和多代理系统国际会议的Pro ceedings”，第2页。

1887-1888.哈法利尔，伊萨·埃，M Bumin Yenmez，穆罕默德·耶尔德勒姆，“择校中的消极作用”，理论经济学，2013年，8(2)，325-363.滨田，科基，岩山一夫、而宫崎修一，“低配额的hosp itals/resident问题，”算法，2016年，74(1)，440-465.Hylland，Aanund和Richard Zeckhauser，《个人对职位的公平分配》，政治经济杂志，1979年，87(2)，293-314.镰田，雄一郎与小岛富仁、“分配约束下的e？cient ma tching：理论与应用，“美国经济评论，2015年，105(1)，67-99.卡塔，Akshay-Kumar和Jay Sethuraman，“在完全优先度上的ran dom a signment问题的解决方案”，《经济理论杂志》，2006年，131(1)，231-250.小岛，Fuhito，“多个不可分割对象的随机分配”，2009年，57(1)，134-142，“学校选择：“游戏和经济omic行为”的不可能性，2012年，75(2)，685-693.Kominers，斯科特·杜克和泰芬·桑梅斯，“为匹配中的多样性设计”，在“欧共体”2013年，第603-604页，Nguyen,Thanh，艾哈迈德·佩瓦·恩迪，和拉凯什·沃赫拉，经济理论杂志，2016年，165，20 9-241.阴道，Marek和M·乌特库·翁弗，“分解随机机制”，《数理经济学杂志》，2015年，61，21-33。罗伯逊，杰克和威廉·韦伯，《切蛋糕算法：如果可以，就要公平》，AK彼得斯/CRC出版社，1998年。罗斯，Alv in E，Tayfun S"onmez和M Utkuünver，《两两肾脏Exchange》，经济理论杂志，2005年，125(2)，151-188。苏，弗朗西斯·爱德华，《出租和谐：公平分工中的斯佩纳引理》，美国数学月刊，1999年，106(10)，930-942。韦斯特卡议员，亚历山大，《德国大学adm issions系统的分析》，经济理论，2013年，53(3)，561-589.ylmaz，zz.具私人捐赠的概率序列机制，“博弈与经济行为，2010,69（2）,475-491。