基于彩票机制的网络资源优化分配

2022-6-11 05:37:08

通过基于彩票的机制优化网络资源分配Ssoham R.Phade和Venkat Anantharam*+摘要我们表明，在资源分配问题中，通过实施彩票，具有累积前景理论偏好的p层的事前聚合效用可以比确定性分配更高。我们提出了一个称为系统问题的优化问题，以找到最优彩票分配。系统问题表现为两层结构，包括排列文件和给定排列文件的最优分配。对于任何固定的置换文件，我们提供了一种基于市场的机制来发现最优配置，并证明均衡价格的存在。我们证明了系统问题一般具有对偶缺口，并且原始问题是NP难问题。然后，我们考虑系统问题的放松，并导出最优彩票结构的一些定性特征。1简介我们考虑网络中的拥塞管理问题，以及不同偏好的异构用户之间的资源分配问题，尤其是人类代理。这是网络经济学中一个公认的问题，应用于交通和电信网络、能源智能电网、信息和金融网络、劳动力市场和社会网络等等。基于市场的解决方案已被证明对此非常有用，其机制多种多样，例如*由NSF科学和技术中心资助的研究CCF-0939370：“信息科学”，NSF资助的ECCS-1343398、CNS-1527846和CIF-1618145，以及威廉和弗洛拉·休利特基金会支持的伯克利长期网络安全中心。+作者是加利福尼亚大学伯克利分校电气工程和计算机科学系，加利福尼亚州伯克利市，邮编94720。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:11

苏哈姆_phade@berkeley.edu,ananth@eecs.berkeley.eduauctions和固定利率定价【9】。在本文中，我们考虑一种基于彩票的机制，而不是文献中研究的确定性分配。我们主要问以下问题：（i）彩票是否比永恒的实现更具优势？（ii）如果是，那么是否存在基于市场的机制来实施最佳彩票？为了回答第一个问题，我们需要确定资源分配的目标。关于彩票的优势有大量文献：埃克霍夫（Eckhoff）和斯通（d Stone）认为，使用彩票是出于公平考虑；博伊斯认为，彩票有助于减少投机者的追捧；Morg an【19】表明，当筹集资金的实体放松税收权力时，彩票是通过自愿基金为公共产品融资的有效方式；Hyland和Zeckhauser[10]建议实施彩票，以激发诚实的偏好，并有效分配工作。在所有这些作品中，都有一个潜在的假设，即分配的物品是不可分割的，这也是使用彩票的关键原因之一。然而，我们注意到，即使要分配的物品是可分割的，也会实施彩票，例如在彩票和巴黎币博彩中。在几个实验中[2 1]，已经观察到基于彩票的奖励比具有相同预期价值的确定性奖励更具吸引力，因此在最大限度地提高对人们行为的预期影响方面具有优势。我们还观察到，几家公司推出基于彩票的服务，以激励消费者购买其产品或使用其服务，从而提高收入。因此，尽管基于彩票的机制正在广泛实施，但似乎缺乏对其的理论理解。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:14

这是本文的动机之一，旨在证明基于彩票的机制的使用是合理的，该机制基于人类如何评估期权的行为经济学模型。我们采取了一种功利主义的方法，即最大化玩家的事前总效用或净幸福感。（参见[1]及其与其他目标（如收入最大化）的关系参考。）我们使用累积前景理论（CPT）对每个参与者的效用进行建模，这是特沃斯基（Tversky）和卡尼曼（Kahneman）[27]首创的一个框架，该框架基于对人类受试者的广泛实验[4]，被认为可以形成一个比预期效用理论（isexpected utility theory，EUT）更好的理论来模拟人类在面对前景时的行为。重要的是要强调，CPT将EUT作为特例，因此提供了对现有建模技术的严格概括。CPT假设了一个概率权重函数，该函数与彩票分配结果的顺序一起决定了一个玩家的概率敏感性（详情见第2节），这一属性在彩票和赌博中起着重要作用。正如博伊斯（Boyce）[3]所指出的，“正是这种不用花钱就能买到好东西的诱惑让彩票分配具有了吸引力。”概率加权函数通常对小概率进行过加权，而对大概率进行过加权，这捕捉到了“剩余”效应。CPTalso提出了一个参考点，将前景结果分为收益和损失两个领域，以模拟参与者的损失厌恶。为了关注概率敏感性的影响，并避免参考点考虑带来的复杂性，我们假设所有参与者的参考点都等于0，并且我们只考虑非负面结果的前景。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022

2022-6-11 05:37:17

事实上，这与等级依赖性（RDU）模型相同【22】。我们将主要关注[13]中考虑的框架，即具有弹性传输的互联网吞吐量控制框架。然而，该框架具有足够的通用性，可以应用于其他几个领域中出现的网络资源分配问题。Kelly sugg认为，彻底的分配问题是为用户实现最大的综合利用率。提出了一个市场，在这个市场中，每个用户根据从网络收到的暂定费率，向网络提交她愿意支付的每单位时间的金额；网络接受这些提交的金额并确定每个网络链接的价格。然后，根据用户提交的数量按比例分配吞吐量，并根据用户希望使用的链接的价格总和按比例分配吞吐量。在某些假设下，Kelly证明了存在均衡价格和吞吐量分配，并且这些分配实现了最大的总效用。因此，最大化聚集性的整个系统问题被分解为一个网络问题和几个用户问题，每个用户一个。此外，在【14】中，作者提出了两类算法，可用于实现上述优化问题的松弛。我们考虑为每个用户分配prospectof吞吐量，而不是分配单个吞吐量。这种前景包括一组有限的吞吐量和分配给每个吞吐量的概率，其中一个吞吐量将以其相应的概率实现（定义见第2节）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:20

然后，我们提出了一个问题，即找到潜在客户的最佳分配方案，每个客户一个，包括该用户的吞吐量和相关概率，这将最大化所有参与者的总效用，也是可行的。如果可以实现，则每个用户的潜在客户分配文件是可行的，即存在可行吞吐量分配的概率分布，每个参与者的收益与其分配的潜在客户一致。如果所有参与者都具有凹效用函数的EUT效用，就像通常假设的风险厌恶模型一样，可以证明存在一个可行的确定性分配，可以达到最优，因此没有必要考虑彩票。然而，如果玩家的效用是由CPT建模的，那么可以通过确定的分配获得最佳的聚合效用。例如，Qu iggin[23]考虑了在几个具有RDU偏好的同质参与者之间分配一个数量的问题。他得出结论，在玩家RDU偏好的特定条件下，最优分配系统是一种彩票方案，有少量大额奖品和大量小额奖品，并且严格优于在玩家之间确定分配总金额。在第5节中，我们将这些结果扩展到具有异构播放器的网络设置。在第2节中，我们描述了网络模型、彩票结构和玩家效用的CPT模型。我们提出了一个称为系统问题的优化问题，以确定最优彩票方案。如第2节所述，这种优化问题的解决方案展示了一种分层结构，即找到一个置换文件，以及相应的可行吞吐量分配。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…

2022-6-11 05:37:23

为了网络可行性的目的，排列文件规定了将每个参与者的订单吞吐量分配耦合在一起的方式。玩家的彩票分配CPT值仅取决于其自身吞吐量的顺序，而不取决于与其他玩家的耦合。给定一个排列方案，找到最佳可行吞吐量分配的问题是一个凸规划问题，我们称之为固定排列系统问题，并导致了一个很好的价格机制。在第3节中，我们证明了均衡价格的存在，均衡价格将固定排列系统问题分解为一个网络问题和几个用户问题，每个层一个，如【13】所示。价格可以解释为施加在玩家身上的成本，可以以多种形式实施，例如排队拍卖或先到先得分配的等待时间[2，26]，网络间TCP协议中的延迟或数据包丢失[17，15]，玩家在比赛中投入的功能或资源[18，6]，或者仅仅是金钱或奖励积分。另一方面，寻找最佳置换公式是一个非凸问题。在第4节中，我们研究了系统问题中的对偶缺口，并考虑通过允许置换为双随机矩阵而不是将其限制为置换矩阵来放松系统问题。我们证明了松弛系统问题和d中存在强对偶，因此它的值等于原始系统问题的对偶（定理4.2）。我们还考虑了链接约束保持在期望中的问题，称为平均系统问题，并证明了强对偶在这种情况下成立，因此它的值等于松弛问题。第五章，我们进一步研究了平均系统问题，并证明了最优彩票结构的一个结果。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:26

例4.3证明了原系统问题中的度差可以是非零的，定理4.4表明原系统问题是NP难问题。在第6节中，我们总结了一些有待进一步研究的问题。2模型考虑一个网络，其中有一组资源或链接，以及一组用户或玩家。让cj>0表示链路j的有限容量∈ [m] 设c：=（cj）j∈[米]∈ Rm。（除非另有规定，否则所有向量将被视为列向量。）每个用户i都有一个固定的routeJi，它是[m]的非空子集。设A为n×m矩阵，其中，如果链接j，ij=1∈ Ji，否则Aij=0。设x：=（xi）i∈[n]∈ Rn+表示分配文件，其中用户i被分配吞吐量xi≥ 通过路线Ji中的链接的0。我们认为，如果满足网络的容量限制，即ATx，则分配文件x是可行的≤ c、其中不平等是协调的。设F表示所有可行分配文件的集合。我们假设网络约束是Fis有界的，因此是一个多面体。而不是将固定吞吐量分配给玩家i∈ [n] ，我们考虑给她分配彩票（或潜在客户）李：{（pi（1），yi（1）），…，（pi（ki），yi（ki））}，（2.1）其中yi（Li）≥ 0，li∈ [ki]表示吞吐量，pi（li），li∈ [ki]是分配吞吐量yi（li）的概率。我们假设彩票是详尽的，即Pli∈pi（li）=1。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022

2022-6-11 05:37:29

（注意，对于li的某些值，我们允许pi（li）=0∈ [ki]和yi（li）=yi（li）对于某些li，li∈ [基文]。）Le t L=（Li，i∈ [n] ）表示彩票文件，其中每个玩家i分配彩票Li。现在，我们描述了CPT模型，该模型用于测量每个玩家从彩票中获得的“效用”或“幸福感”（更多详细信息，请参见[29]）。每个游戏者i与值函数vi:R相关联+→ R+是连续的、可区分的、凹的和严格递增的，概率加权函数wi：[0，1]→ [0，1]这是连续的，严格递增的，满足wi（0）=0和wi（1）=1。对于前景Liin（2.1），让πi：[ki]→ [ki]是一种per突变，因此Zi（1）≥ zi（2）≥ · · · ≥ zi（ki），（2.2）和yi（li）=所有li的zi（πi（li））∈ [基文]。（2.3）前景可以等效地写为li={（▄pi（1），zi（1））；…；（▄pi（ki），zi（ki））}，其中▄pi（li）：=pi（π）-1i（li））适用于所有li∈ [基文]。使用价值函数vi（·）和概率权重函数wi（·）对潜在LIF玩家i的CPT值进行评估，如下所示：vi（Li）：=kiXli=1dli（pi，πi）vi（zi（Li）），（2.4），其中dli（pi，πi）是由d（pi，πi）：=wi（pi（1））和dli（pi，πi）：=wi（pi（1）+·+）-pi（Li）给出的决策权重- wi（～pi（1）+···+～pi（li- 1）），对于1<li≤ ki。虽然等式（2.4）中右侧的表达式取决于置换πi，但可以确认，只要πi是（2.2）和（2.3），该公式的计算值Vi（Li）是相同的。潜在客户Li的CPT值可等效为Vi（Li）=kiXli=1wiliXsi=1pi（si）[六（字（里））- vi（zi（li+1）））]，其中zi（ki+1）：=0。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:33

因此，最低分配zi（ki）通过wi（1）=1和分配值的每个增量vi（zi（li））进行加权- vi（zi（li+1）），锂∈ [千- 1] ，通过接收至少等于zi（li）的分配的概率的概率加权函数进行加权。对于任何有限集，让（S）表示集合S上所有概率分布的标准单纯形，即。，（S）：={（p（S），S∈ S） | p（S）≥ 0s∈ S、 Xs型∈Sp（s）=1}。因此pi：=（pi（li））li∈[千]∈ （[ki]）。我们认为，如果存在联合分布p，彩票计划是可行的∈ （Qi【ki】），从而满足以下条件：（i）所有参与者的边际分布与LIF一致，即Pl-ip（li，l-i） =所有li的pi（li）∈ [ki]，其中-iin求和时，取qi′6=i[ki′中的值。（ii）对于每个（li）i∈[n]∈Qi【ki】支持分布p（即p（（li）i∈[n] ）>0），分配比例（yi（li））i∈[n] 是可行的。分布p和吞吐量（yi（li），i∈ [n] ，li∈ 【ki】）一个可行的彩票计划共同定义了一个彩票计划。在下文中，我们将注意力限制在特定类型的彩票计划上，其中网络以相同的概率实现了k分配文件y（l）：=（yi（l））i中的一个∈[n]∈ Rn+，用于l∈ [k] 。让[k]={1，…，k}表示结果集，如果结果l发生，则执行分配文件yi（l）。很明显，这样的方案对每个分配文件y（l）都是可行的，l∈ [k] 属于F。因此，Player i面对的前景是Li={（1/k，yi（l））}kl=1，这样的一个混合方案完全由元组y来表示：=（yi（l），i∈ [n] ，l∈[k] ）。如果把k取得足够大，任何彩票方案都可以用这样的一个近似值来表示。Le t yi：=（yi（l））l∈[k]∈ Rk+。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-6-11 05:37:35

设zi：=（zi（l））l∈[k]∈ Rk+是向量，πi：[k]→ [k] 是一个排列，使得zi（1）≥ zi（2）≥ · · · ≥ zi（k），andyi（l）=所有l的zi（πi（l））∈ [k] 。注意，yi完全由π和zi表示。那么玩家i的CPT值将为vi（Li）=kXl=1hi（l）vi（zi（l）），其中hi（l）：=wi（l/k）- wi（（l- 1） /k）对于l∈ [k] 。让hi：=（hi（l））l∈[k]∈ Rk+。注意，对于所有i，l，hi（l）>0，因为假设权重函数严格递增。从个人分配比例和排列πIf的角度来看彩票方案y∈ [n] ，允许我们将影响个人偏好的y特性与与与网络实现相关的特性分开。之后，我们将看到优化聚合效用的问题可以分解为两个层次：（i）优化资源分配的凸问题，以及（ii）找到最优排列文件的非凸问题。Le t z：=（zi（l），i∈ [n] ，l∈ [k] ），π：=（πi，i∈ [n] ），h：=（hi（l），i∈ [n] ，l∈[k] ）和v：=（vi（·），i∈ [n] ）。设sk表示[k]的所有置换的集合。在彩票方案可行的情况下，优化骨料效用vi（Li）的问题可以表述为：SYS[z，π；h，v，A，c]maximenxi=1kXl=1hi（l）vi（zi（l））subject toXi∈Rjzi（πi（l））≤ cj，j∈ [m] ，则，l∈ [k] ，zi（l）≥ zi（l+1），我∈ [n] ，则，l∈ [k] ，πi∈ Sk公司，我∈ [n] 。这里Rj：={i∈ [n] | j∈ Ji}是其路线使用链接j的所有玩家的集合。我们为所有i设置zi（k+1）=0，并且zi（k+1）不被视为变量。这将考虑条件zi（l）≥ 0代表所有i∈ [n] ，l∈ [k] 。3平衡系统问题SYS[z，π；h，v，A，c]在z和π上优化。在本节中，我们确定πi∈ Skfor all i和optimize over z。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:38

让我们用SYS\\u FIX[z；π，h，v，A，c]来表示这个执行置换系统问题。SYS\\u FIX[z；π，h，v，A，c]最大化xi=1kXl=1hi（l）vi（zi（l））受试者毒性∈Rjzi（πi（l））≤ cj，j∈ [m] ，则，l∈ [k] ，zi（l）≥ zi（l+1），我∈ [n] ，则，l∈ [k] 。（与SYS（z，π；…）相比，在SYS \\u FIX（z；π，…）中，置换π被认为是固定的。）由于vi（·）被假定为凹函数，且对于所有i，l，hi（l）>0，因此该问题具有线性约束的凹目标函数。对于所有j∈ [m] ，l∈ [k] ，设λj（l）≥ 0是响应约束spi的双变量∈Rjzi（πi（l））≤ 分别为CJ和forall i∈ [n] ，l∈ [k] ，设αi（l）≥ 0是对应于约束zi（l）的双变量≥ zi（l+1）。设λ：=（λj（l），j∈ [m] ，l∈ [k] ）和α：=（αi（t），i∈ [n] ，l∈ [k] ）。然后，固定置换系统问题SYS\\u FIX[z；π，h，v，A，c]的拉格朗日可以写成：L（z；α，λ）：=nXi=1kXl=1hi（L）vi（zi（L））+nXi=1kXl=1αi（L）[zi（L）- zi（l+1）]+mXj=1kXl=1λj（l）[cj-xi∈Rjzi（πi（l））]=nXi=1kXl=1hi（l）vi（zi（l））+（αi（l）- αi（l- 1））字（l）-Xj公司∈Jiλj（π-1i（l））zi（l）+mXj=1kXl=1λj（l）cj，其中αi（0）=0表示所有i∈ [n] 。将拉格朗日函数与我们得到的zi（l）进行区分，L（z；α，λ）zi（l）=hi（l）v′i（zi（l））+αi（l）- αi（l- 1) -Xj公司∈Jiλj（π-1i（l））.Le tρi（l）：=Xj∈Jiλj（π-1i（l）），（3.1）对于所有i∈ [n] ，l∈ [k] 。这可以解释为第l个最大分配zi（l）的玩家i的单位价格。玩家i的彩票价格由pkl=1ρi（l）zi（l）给出，或者等效地，kXl=1ri（l）[zi（l）- zi（l+1）]，其中ri（l）：=lXs=1ρi（s），对于所有l∈ [k] 。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:41

（3.2）对于l∈ [k]-1] ，αi（l）c可以解释为玩家i的非负价格从其第l大分配转移到其第（l+1）大分配。由于分配zi（l+1）不能大于分配zi（l），因此在zi（l）的价格中有αi（l）的补贴，在zi（l+1）的价格中有αi（l）的同等附加费。只有当约束具有约束力，即zi（l）=zi（l+1）时，该补贴和附加费才为非零（因此为正）。另一方面，αi（k）是给予参与者i的最低分配的价格补贴，因为她不能收取高于零分配边际效用的任何费用。Le t hi：=（hi（l））l∈[k]∈ Rk+。考虑一下播放器i的以下用户问题：用户[mi；ri，hi，vi]最大化kxl=1hi（l）vikXs=lmi（s）ri（s）！-kXl=1mi（l）受mi（l）影响≥ 0, l∈ [k] ，（3.3）式中，ri：=（ri（l），l∈ [k] ）是一个速率向量，使得0<ri（1）≤ ri（2）≤ · · · ≤ ri（k）。（3.4）我们可以这样解释：用户i的低安装位置δi（k）：=zi（k）的收费率为ri（k）。设mi（k）表示在较低安装位置上花费的预算，因此mi（k）=ri（k）δi（k）。对于1≤ l<k，她被收取额外分配δi（l）的费率ri（l）：=zi（l）- zi（l+1），超出zi（l+1）直到下一个最低分配zi（l）。设mi（l）表示仅用于额外分配的预算，因此mi（l）=ri（l）δi（l）。Le t m：=（mi（l），i∈ [n] ，l∈ [k] ）和δ：=（δi（l），i∈ [n] ，l∈ [k] ）。考虑以下网络问题：网络[δ；m，π，A，c]最大化xi=1kXl=1mi（l）log（δi（l）），服从δi（l）≥ 0, 我，l、 Xi∈RjkXs=πi（l）δi（s）≤ cj，jl、这是著名的Eisenbe-rg Gale凸规划[8]，可以有效地求解。Kelly等人[14]提出了用于确定均衡价格和分配的连续时间算法。有关这些问题的多项式时间算法的结果，请参见[11，5]。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:44

我们有以下分解结果：定理3.1。对于任何固定π，都存在平衡参数r*, m级*, δ*和z*这样（i）对于每个玩家，i，m*隔离用户问题用户*i、 hi，vi），（ii）δ*解决网络问题NET[δ；m*, π、 A，c]，（iii）m*i（l）=δ*i（l）r*i（l）对于所有i，l，（iv）δ*i（l）=z*i（l）- z*所有i、l和（v）z的i（l+1）*解决固定排列系统问题SYS\\u FIX[z；π，h，v，A，c]。证据由于SYS\\u FIX[z；π，h，v，A，c]是一个凸优化问题，我们知道存在z*= （z）*i（l），i∈ [n] ，l∈ [k] ），α*= (α*i（l），i∈ [n] ，l∈ [k] ）和λ*= (λ*j（l），j∈ [m] ，l∈ [k] ）以使hi（l）v′i（z*i（l））=ρ*i（l）- α*i（l）+α*i（l- 1),我，l、（3.5）z*i（l）≥ z*i（l+1），α*i（l）≥ 0, α*i（l）（z）*i（l）- z*i（l+1））=0，我，l、（3.6）Xi∈Rjz公司*i（πi（l））≤ cj，λ*j（l）≥ 0, λ*j（l）[cj-xi∈Rjz公司*i（πi（l））]=0，j l、（3.7）式中ρ*i（l）：=Xj∈Jiλ*j（π-1i（l）），并且z*解决固定排列系统问题SYS\\u FIX[z；π，h，v，A，c]。因此，语句（v）适用于z的选择*. 让r*i（l）：=Pls=1ρ*i（s），δ*i（l）：=z*i（l）- z*i（l+1）和d m*i（l）：=δ*i（l）r*i（l）对于所有i，l.从（3.5），我们有ρ*i（1）>0，因为vi（·）严格递增，hi（1）>0和α*i（0）=0。因此，速率向量r*isatis fies（3.4）适用于所有i。还请注意，通过构造，向量r*, δ*, z*和m*满足定理的陈述（iii）和（iv）。现在，我们表明（i）陈述成立。修复播放机i。观察用户问题用户*i、 hi，vi]具有凹面物镜f函数，因为hi（l）>0，r*i（l）>0且vi（·）为凹形。区分用户问题用户的目标功能*i、 hi，vi]关于mi=m时的mi（l）*i、 wegetlXs=1hi（s）v′i（z*i（s））r*i（l）- 从（3.5）中，我们得到lxs=1hi（s）v′i（z）*i（l））=lXs=1ρ*一（s）- α*i（l）=r*i（l）- α*i（l）。因此，lXs=1hi（s）v′i（z*i（s））r*i（l）- 1 = -α*i（l）r*i（l）≤ 0，其中等式为i ffα*i（l）=0。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:48

如果m*i（l）>0，则δ*i（l）>0，因此，通过（3.6），α*i（l）=0。因为这对所有人都适用∈ [k] ，这些正是m的最优性所必需和充分的条件*在用户i的问题中，它是一个凸问题。我们现在证明，州议员t（ii）成立。对应于网络问题网的拉格朗日函数〔δ；m〕*, π、 A，c]可写为：L（δ；u）=XikXl=1m*i（l）log（δi（l））+XjXluj（l）cj公司-xi∈RjkXs=πi（l）δi（s）,其中，uj（l）是对应于链接约束的双变量，u：=（uj（l），j∈ [n] ，l∈ [k] ）。设uj（l）=λ*j（l）。如果m*i（l）>0，则δ*i（l）>0，并在δ处区分拉格朗日函数与δi（l）*i（l），我们得到L（δ；λ*)δi（l）δi（l）=δ*i（l）=m*i（l）δ*i（l）-Xj公司∈JilXs=1λ*j（π-1i（s））=r*i（l）-lXs=1ρ*i（s）=0。如果m*i（l）=0，则L（δ；λ*)δi（l）δi（l）=δ*i（l）≤ 自λ起为0*j（l）≥ 所有j，l为0。进一步，从（3.7）中，我们得到λ*j（l）hcj-圆周率∈RjPks=πi（l）δ*对于所有j，l，i（s）i=0。因此，δ*解决网络问题NET[δ；m*, π、 A、c]。因此，固定排列系统问题可以分解为用户问题（每个玩家一个）和网络问题（任何固定排列文件π）。与[14]中的框架类似，我们有如下迭代过程：网络向每个用户i呈现一个速率向量ri。每个用户解决用户问题用户[mi；ri，hi，vi]，然后提交他们的预算向量mi，网络收集这些预算向量（mi）i∈[n] 并解决网络问题NET[δ；m*, π、 A，c]得到相应的分配z（可通过增量分配δ计算）和双变量λ。然后，网络根据（3.1）和（3.2）给出的这些双变量计算每个用户对应的速率向量，并将其作为u更新速率呈现给用户。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-6-11 05:37:51

定理3.1表明，最大化总效用的固定排列系统问题在上述迭代过程的平衡点处得到解决。如果值函数vi（·）是严格共模的，那么可以证明最优彩票分配z*对于固定排列系统，问题是唯一的。然而，双变量λ和速率ri，i、不必是唯一的。尽管如此，如果使用【14】中提出的连续时间算法来解决网络问题，那么基于李雅普诺夫稳定性的类似分析（如【14】中所述）表明，上述迭代过程收敛于均衡彩票分配z*.其中一种排列形式，比如π*, 解决了系统问题。在下一节中，我们将更详细地探讨这一点。然而，有趣的是，对于任何固定的置换文件π，任何确定性解决方案都是具有置换文件π的彩票计划的特例。因此，可以保证任何置换文件π的固定置换系统问题的解决方案至少与任何确定性分配一样好。这里有一个简单的例子，基于彩票的分配比确定性分配带来了严格的改进。示例3.2。考虑一个有n个玩家的网络和一个容量为c的链路。设n=10，c=10。对于所有参与者i，我们使用Kahneman和Tversky[27]提出的值函数和权重函数，由vi（xi）=xβii，βi给出∈ [0，1]和wi（pi）=pγii（pγi+（1- p） γi）1/γi，γi∈ （0，1）。对于所有i，我们取βi=0.88和γi=0.61∈ [n] 。这些参数被报告为[27]中经验数据的最佳拟合。概率权重函数如图1所示。利用价值函数vi（·）的对称性和凹性，通过将c／n分配给每个参与方i，给出了最优确定性分配。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:37:54

此分配的聚合性为n* v（c/n）=10。现在考虑以下彩票分配：让k=n=10。设πi（l）-1=所有i的l+i（mod k）∈ [n] 和l∈ [k] 。让x∈ [c/n，c]和zi（1）=x0.2 0.4 0.6 0.8 10.20.40.60.8Pi图1：所有i的概率加权函数∈ [n] zi（l）=（c- x） /（n- 1）就我而言∈ [n] l=2，k、请注意，这是一种可行的彩票分配。这样的彩票方案可以解释如下：从所有玩家中随机均匀地选择一个“中奖”玩家。给她分配奖励x，并平均分配剩余奖励c- 其他玩家中的x。事前聚合效用由N给出* [w（1/n）v（x）+（1- w（1/n）v（（c）- x） /（n- 1))] .该函数在x=9.7871时达到最大值14.1690。因此，上述彩票改进了任何确定性分配的聚合效用。最优彩票分配至少与14.1690.4最优排列和对偶间隙一样好。系统问题SYS[z，π；h，v，A，c]可以等价地表示为maxπi∈Sk公司i、 z:zi（l）≥zi（l+1）i、 lminλ≥0nXi=1kXl=1hi（l）vi（zi（l））+mXj=1kXl=1λj（l）cj公司-xi∈Rjzi（πi（l））.（一）请注意此问题的价值。它等于系统问题SYS的最优值[z，π；h，v，A，c]。通过交换max和min，我们得到了以下对偶问题：minλ≥0最大πi∈Sk公司i、 z:zi（l）≥zi（l+1）i、 lnXi=1kXl=1hi（l）vi（zi（l））+mXj=1kXl=1λj（l）cj公司-xi∈Rjzi（πi（l））.（二）请注意此双重问题的价值。通过弱对偶，我们知道wps≤ Wds。对于固定λ≥ 0和满足zi（l）的x-ed z≥ zi（l+1），i、 l，对偶问题（II）中的最佳置换函数π应最小zemXj=1kXl=1λj（l）Xi∈Rjzi（πi（l）），等于xixl^ρi（l）zi（πi（l）），此处^ρi（l）：=Pj∈Jiλj（l），是球员i在结果l下的单位分配价格。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:02

由于数zi（l）是按降序排列的，因此任何最优置换πi都必须满足ρi（π-1i（1））≤ ρi（π-1i（2））≤ · · · ≤ ρi（π-1i（k））。（4.1）换句话说，对偶问题（II）的任何最优排列π必须按照与价格ρi（l）相反的顺序分配吞吐量。引理4。1、如果问题（I）和（II）之间存在强对偶性，则任何最优置换文件π*所有i的满意度（4.1）。我们在附录A中证明了这个引理。一般来说，问题（i）和（II）之间存在非零对偶差距（参见示例4.3，其中最佳置换结果为π*不符合（4.1））。突变π可以用k×k每突变矩阵来表示，其中，对于s，t，如果πi（s）=t，Mi（s，t）=1，否则Mi（s，t）=0∈ [k] 。网络约束SPI∈Rjzi（πi（l））≤ cj，l∈ [k] ，可等效为asPi∈RjMizi≤ cj1，其中1表示大小适当的向量，其所有元素均等于1，且不等式为坐标不等式。系统问题的一个可能的解决方法是考虑双随机矩阵，而不是将它们限制为置换矩阵。如果一个矩阵的所有条目都是非负的，并且每一行和每一列的总和都是1，那么它就是双重随机的。因此，置换矩阵是双随机矩阵。允许Ohmkdenote全双随机k×k矩阵集与letOhm*kdenote所有k×k置换矩阵的集合。Le t M=（Mi，i∈ [n] ）表示双随机矩阵。然后，松弛的系统问题可以写为：SYS\\u REL[z，M；h，v，A，c]maximenxi=1kXl=1hi（l）vi（zi（l））subject toXi∈RjMizi≤ cj1，j、 zi（l）≥ zi（l+1），我，l、密歇根州∈ Ohmki、那么相应的原始问题可以写成如下：∈Ohmki、 z:zi（l）≥zi（l+1）l、，iminλj≥0,jXiXlhi（l）vi（zi（l））+XjλTjcj1-xi∈RjMizi.（三）式中λj=（λj（l））l∈[k]∈ Rk+。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:05

让WPRD注意这个问题的价值。交换min和max，我们得到相应的对偶：minλj≥0,jmaxMi公司∈Ohmki、 z:zi（l）≥zi（l+1）l、，iXiXlhi（l）vi（zi（l））+XjλTjcj1-xi∈RjMizi.（四）请注意此问题的价值。如果relaxedsystem问题中的链接约束成立，则kxi∈RjkXl=1zi（l）=kXi∈RjTMizi公司≤kTcj1=cj。（4.2）这一不平等本质上表明，链接约束应保持在预期范围内。因此，我们有以下平均系统问题：SYS\\u AVG[z；h，v，A，c]maximenxi=1kXl=1hi（l）vi（zi（l））受试者毒性∈RjkkXl=1zi（l）≤ cj，j、 zi（l）≥ zi（l+1），我，l、及其相应的主要问题：maxz:zi（l）≥zi（l+1）l、，imin？λj≥0,jXiXlhi（l）vi（zi（l））+Xj′λjcj公司-xi∈RjkkXl=1zi（l）,（五）和对偶问题：min|λj≥0,jmaxz:zi（l）≥zi（l+1）l、，iXiXlhi（l）vi（zi（l））+Xj'λjcj公司-xi∈RjkkXl=1zi（l）,（六）式中|λj∈ R是对应于链接约束的双变量。Le t wPa和Wdadenote分别计算这些原始问题和对偶问题的值。那么我们有以下关系：定理4。2、对于h、v、A和c确定的任何系统问题，我们有WPS≤ Wpr=Wpa=Wda=Wdr=Wds。证据如前所述，如果我们更换条件Mi∈ Ohm将原始松弛问题（III）与条件Mi联系起来∈ Ohm*k、我们得到了原始系统问题（I）。自从Ohm*k Ohmk、我们有Wps≤ Wpr。constraintPi∈RjkPkl=1zi（l）≤ CJ可以等效地写为XI∈Rj米兹≤ cj1，对于所有j，其中“Mi”是矩阵，其所有条目等于1/k。因此，如果我们替换Mi∈ Ohm将原始松弛问题（III）与“Mi”联系起来，我们将原始平均问题（V）联系起来。这意味着Wpa≤ Wpr。然而，如前面等式（4.2）所示，如果对于某些固定分配z，链接约束对于任何双随机矩阵Mi都是满足的，那么它们对于“Mi”也是满足的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-6-11 05:38:08

因此，平均系统问题SYS\\u AVG[z；h，v，A，c]的最大值至少与相关系统问题SYS\\u rel[h，v，A，c]的最大值相同。由于松弛系统问题的最大值等于其相应的原问题的值，我们得到了Wpa≥ Wpr。因此，我们确定Wpr=Wpa。平均系统问题有一个带线性约束的凹目标函数。因此，强对偶成立，我们得到Wpa=Wda。我们现在显示Wda=Wdr。来自Wpr≤ Wdrand Wpr=Wpa=Wda，我们得到Wda≤ Wdr。假设λj=(R)λj1。然后松弛对偶问题的目标函数（IV），nXi=1kXl=1hi（l）vi（zi（l））+mXj=1λTjcj1-xi∈RjMizi=nXi=1kXl=1hi（l）vi（zi（l））+mXj=1？λjcj公司-xi∈RjkkXl=1zi（l）,等于对偶平均问题（V）的目标函数。这意味着Wdr≤ Wda。这确定了Wda=Wdr。由于任何双随机矩阵Mi都是由Birkhoff-von Neumann定理构成的置换矩阵的凸组合，因此在对偶问题（IV）中，对于任何固定的λj，zi，都可以通过置换矩阵实现最优。这确定Wdr=Wds。这就完成了证明。因此，二元性缺口是“硬”链接约束的一种表现。在上述定理的证明中，我们看到松弛问题与平均问题“等价”，并且这种松弛具有很强的对偶性。我们稍后将进一步详细研究平均问题（第5节）。我们在引理4.1中观察到，如果强对偶性在系统问题中成立，那么最佳置换函数π*满意度（4.1）。考虑一个简单的例子，两个玩家共享一个链接。假设在最佳情况下，λ（l）是l的价格∈ [k] 对应于不同结果下的这一联系，并假设并非所有这些都是相等的。然后，对偶问题的最佳每突变概率将按照相同的顺序调整两个参与者的分配，即。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:10

玩家1的高分配将与玩家2的高分配对齐。然而，我们可以直接从系统问题中看到，一个最佳π*应该按照相反的顺序调整两个玩家的分配。下面的例子建立在这一观察结果的基础上，并表明系统问题不需要具有强对偶性。示例4.3。考虑以下示例，其中有两个玩家{1，2}和一个容量为2.9的单链接。设k=2。假设两个参与者对应的CPT特征如下：h（1）=，h（2）=，h（1）=，h（2）=，v（x）=log（x+0.05）+3，v（x）=2 log（x+0.05）+3（x+0.05）+3。对于这个问题，很容易看出π=（1，2）和π=（2，1）是最佳置换。通过求解固定置换系统的置换问题，我们得到的最优值为7.5621。相应的变量值为z（1）=y（1）=1.95，z（2）=y（2）=0.95，z（1）=y（2）=1.95，z（2）=y（1）=0.95，对于i=1，2，l=1，2，双变量值为λ（1）=，λ（2）=，和αi（l）=0。可以检查这些是否满足KKT条件。现在让我们来评估双重问题（II）的价值。根据对称性，我们可以假设λ（1），而不失一般性≤ λ(2). 结果，对偶问题的最优置换由π=π=（1，2）给出。对于固定的λ（1）和λ（2），我们解决以下优化问题：maxz（1）≥z（2）≥0z（1）≥z（2）≥0对数（z（1）+0.05）+对数（z（2）+0.05）+2对数（z（1）+0.05）+3对数（z（1）+0.05）+2对数（z（2）+0.05）+3对数（z（2）+0.05）- λ（1）[z（1）+z（1）]- λ（2）[z（2）+z（2）]+2.9[λ（1）+λ（2）]+6。（七）如果λ（1）≤ 0.5，则问题（VII）的值等于∞ （letz（1）→ ∞). 如果λ（1）>0.5（因此λ（2）>0.5，因为λ（2）≥ λ（2）），然后我们观察到问题（VII）中最大化的有效域是紧的，并且问题（VII）有一个有限值。因此，没有必要考虑λ（1）>0.5。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:13

在最佳情况下，存在α（1）、α（2）、α（1）、α（2）≥0使得λ（1）=z（1）+0.05+α（1），λ（2）=z（2）+0.05- α（1）+α（2），λ（1）=z（1）+0.05++α（1），λ（2）=z（2）+0.05+- α（1）+α（2）和α（1）[z（1）- z（2）]=0，α（2）z（2）=0，α（1）[z（1）- z（2）]=0，α（2）z（2）=0。现在，我们考虑十六个（4×4）案例中的每一个，基于它们的内在品质zi（l）≥ zi（l+1）对于i=1，2和l=1，2，是否严格保持。情况A1（z（1）=0，z（2）=0）。然后λ（1）≥ 1/0.15.情况B1（z（1）>0，z（2）=0）。然后λ（1）<1/0.15，λ（2）≥ 2/0.15，α（1）=0，z（1）=3λ（1）- 0.05.情况C1（z（1）=z（2）>0）。然后λ（2）/2≤ λ(1) ≤ λ（2），λ（1）+λ（2）<1/0.05，α（1）=2λ（1）- λ（2），α（2）=0，z（1）=z（2）=λ（1）+λ（2）- 0.05.案例D1（z（1）>z（2）>0）。然后λ（1）<λ（2）/2，0<λ（1）<1/0.15，0<λ（2）<2/0.15，α（1）=0，α（2）=0，z（1）=3λ（1）- 0.05，z（2）=3λ（2）- 0.05.情况A2（z（1）=0，z（2）=0）。然后λ（1）≥ (1/0.15) + 0.5.情况B2（z（1）>0，z（2）=0）。然后0.5<λ（1）<2.15/0.3，λ（2）≥（1/0.75）+0.1，α（1）=0，z（1）=6λ（1）- 3.- 0.05.情况C2（z（1）=z（2）>0）。这是不可能的，因为λ（1）≤ λ(2).案例D2（z（1）>z（2）>0）。然后0.5<λ（1）<2.15/0.3，0.1<λ（2）<2.15/1.5，α（1）=0，α（2）=0，z（1）=6λ（1）- 3.- 0.05，z（2）=30λ（2）- 3.- 0.05.如果情况A1或情况A2成立，则λ（1）≥ 1/0.15. 对于任何固定的λ（1），λ（2），通过选择足够小的zi（l），i=1，2，l=1，2（考虑相应情况所构成的条件），我们得出问题（VII）的值大于或等于2.9*(1/0.15) = 19.3333 > 7.5621. 类似地，如果caseB1成立，则λ（2）≥ 2/0.15，我们得到问题（VII）的值大于或等于2.9*(2/0.15) = 38.6667 > 7.5621.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:16

对于剩下的4种情况，将目标函数（VII）中的zi（l），i=1，2，l=1，2替换相应的表达式，并对每对c类{C1，D1}×{B2，D2}的最优可行对（λ（1），λ（2））进行评估，情况（C1，D2）的最小值为8.2757。对每种情况进行数值计算，得出表2所示的最小值。因此，最佳对偶值为8.2757，这严格大于原始值。定理4。原始问题（I）是NP难问题。B2 D2C1 10.2284 8.2757D1 10.1814 9.5006图2：单元格中的数字表示相应情况下目标函数（VII）的最佳值。证据我们描述了一个多项式时间过程，该过程将整数划分问题的一个实例简化为原始问题的一个特例。给定一组正整数{c，c，…，cn}，整数划分问题是找到一个子集S [n] ，以便XI∈Sci=Xi/∈Sci。如果这样一个集合S存在，那么我们就说存在一个整数分区。考虑一个由Yi给出的有n个参与者和n+1个链接约束的网络≤ ci，我∈ [n] ，andnXi=1yi≤Pni=1ci。利用这些链路约束很容易实现网络。设k=2。让所有玩家的Cpt特征如下：hi（1）=1- ，hi（2）=，vi（xi）=xi，我∈ [n] ，其中=1/10。让WPS记录系统问题的最佳值。Weshow那个Wps≥ T：=（1）-）Pi∈[n] ciif且仅当存在整数分区时。假设一个整数分区由集合S给出，如果i∈ S和πi=[2，1]否则，对于所有i，zi（1）=ci，zi（2）=0∈ [n] 。此分配的聚合实用程序等于T和henceWps≥ T假设Wps≥ T然后有一个分配，比如z*和π*聚合效用至少为T。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:19

因为k=2，π*实际上定义了[n]的一个分区，由S={i]给出∈ [n] ：πi（1）=1}。我们有，总效用W（1）+W（2）≥ T、其中w（1）：=Xi∈S（1- ）子（1）+Xi/∈Szi（2），W（2）：=Xi/∈S（1- ）子（1）+Xi∈Szi（2）。所以W（1）和W（2）中至少有一个至少和T/2一样大≥ T/2。因此，Xi∈Szi（1）+1- Xi/∈Szi（2）≥圆周率∈[n] ci。但是，由于z*是可行的，链接约束给定xi∈Szi（1）+Xi/∈Szi（2）≤圆周率∈[n] ci。既然<1/2，我们应该有PI/∈Szi（2）=0和pi∈Szi（1）=（Pi∈[n] ci）/2，表示S形成一个整数分区。这就完成了证明。5平均系统问题和最优彩票结构假设它足以确保链接约束在预期中得到满足，就像在平均系统问题中一样。考虑由以下优化问题的值给出的R+上的函数Vavgi（(R)zi）：MaximizekXl=1hi（l）vi（zi（l））subject TokXL=1zi（l）=zi，zi（l）≥ zi（l+1），l∈ [k] 。（八） Le t Zi（(R)Zi）表示可行（Zi（l））l的集合∈[k] 在上述问题中，对于任何固定的“zi”≥ 我们观察到Zi（\'Zi）是一个封闭且有界的多面体，因此Vavgi（\'Zi）定义良好。引理5.1。对于任何连续的、可微分的、凹的和严格递增的值函数vi（·），函数Vavgi（·）是连续的、可微分的、凹的和严格递增的。我们在附录A中证明了这个引理。平均系统问题SYS\\u AVG[z；h，v，A，c]可以写成Maximizenxi=1Vavgi（\'zi）subject toXi∈Rj’zi≤ cj，j、 \'\'子≥ 0, i、 Kelly【13】表明，这个问题可以分解为用户问题，每个用户一个问题，最大化Vavgi（(R)zi）- ρi zi服从于zi≥ 0，以及一个网络问题，MaximizenXi=1？ρi？zisubject toXi∈Rj’zi≤ cj，j、 \'\'子≥ 0, i、在这个意义上，存在ρi≥ 0, 我∈ [n] ，这样，对于每个i，用户问题的最佳解决方案可以解决网络问题和平均系统问题。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:22

请注意，这种分解不同于第3节中所述的分解。在这里，网络问题旨在最大化其总收入ni=1'ρi'zi，而不是最大化加权聚合效用，其中效用被替换为代理对数函数。为了开发收敛到平衡的迭代方案，上述分解不如第3节中的分解有用。然而，上述分解会引发以下用户问题：user\\u AVG[zi；(R)ρi，hi，vi]MaximizekXl=1hi（l）vi（zi（l））-(R)ρikkXl=1zi（l）受zi（l）约束≥ zi（l+1），l∈ [k] ，其中，如前所述，zi（k+1）=0。我们在命题4.2中观察到，在平均系统问题中存在强对偶性。让z*是解决这个问题的最佳彩票方案。然后，首先，z*满意度z*i（l）≥ z*i（l+1）i、 l和是不可预测的，即“z”*:= （(R)z）*i）我∈[n]∈ F、其中“z”*i： =（1/k）Plz*i（l）。此外，z*优化平均系统问题的目标函数。此外，还存在∧*j≥ 0表示所有j，这样原始平均问题（V）和双重平均问题（VI）都在z处达到最优*, (λ*j、 j∈ [m] ）。对于玩家i，考虑价格\'ρ*i： =Pj∈Ji？λ*j、通过对价格|λ求和得到*J对应于玩家i路线上的链接。从双平均pr问题（VI）中，确定|λj=|λ*jj、我们得到了最优彩票分配z*对于玩家，我应该优化问题用户的平均值*i、嗨，vi]。现在，我们对概率加权函数施加了一些附加条件，这些条件通常是基于经验证据和某些心理论点假设的[12]。我们假设概率加权函数wi（pi）对于其余的概率规划和约束x的小值是凹的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:25

形式上，存在一个概率π∈ [0，1]使得wi（pi）在间隔pi上是凹的∈ [0，~pi]和区间上的凸[~pi，1]。通常，反射点pi约为1/3。Le t w公司*i： [0，1]→ [0，1]是支配wi（·）的最小凹函数，即w*i（pi）≥ 所有pi的wi（pi）∈ [0, 1]. 让p*我∈ [0，1]是w*i（pi）在区间[p]上是线性的*i、 1）。引理5.2。根据wi（·）的假设，我们有p*我≤ 计划w*i（pi）=pi的wi（pi）∈ [0，p*i] 。如果p*i<1，则对于任何pi∈ [p*i、 1），我们有WI（pi）≤ wi（pi）+（pi- pi）1- wi（pi）1- 圆周率。（5.1）对于所有pi∈ [pi，1]。这个引理的证明包含在附录A中。我们现在表明，在一定条件下，最优彩票分配z*isatis Fiesz公司*i（l*) = z*i（l*+ 1） =···=z*i（k），（5.2），其中l*:= 最小{l∈ [k] ：（l- 1） /千≥ p*i} ，提供p*我≤ （k）- 1） /k.因此，对于典型的最优彩票分配，最低分配发生的概率很大，大约等于1-p*i、还有一些我们认为是奖金的高级场所。提议5.3。对于任何平均用户问题，user\\u AVG[zi；\'ρ*i、 hi，vi]具有严格递增、连续、可微分和严格凹值函数vi（·），以及严格递增的连续概率加权函数wi（·）（满足wi（0）=0和wi（1）=1），使得p*我≤ （k）- 1） /k，最佳彩票分配时间z*isatis fies方程（5.2）。证据平均用户问题user\\u AVG的拉格朗日函数*i、 hi，vi]isL（zi；αi）=kXl=1hi（l）vi（zi（l））-ρ*ikkXl=1zi（l）+kXl=1αi（l）[zi（l）- zi（l+1）]，其中αi（l）≥ 0是对应于订单约束Zi（l）的双变量≥ zi（l+1），αi（0）=0。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:28

对于zi（l），我们得到，L（zi；αi）zi（l）=hi（l）v′i（zi（l））-ρ*ik+αi（l）- αi（l- 1).自出现问题以来，用户平均*i、 hi，vi]具有凹目标函数和线性约束，存在α*i（l）≥ 0，使hi（l）v′i（z*i（l））=ρ*ik- α*i（l）+α*i（l- 1), l∈ [k] ，（5.3）和α*i（l）[z*i（l）- z*i（l+1）]=0，l∈ [k] 。（5.4）如果z*iconsists of the same allocations then it littley satifies equality（5.2）等式。如果没有，则存在l∈ {2，…，k}这样z*i（l- 1） >z*i（l）=z*i（l+1）=···=z*i（k），即z*i（l）是最低分配，以概率（k）出现- l+1）/k，下一个最低分配等于z*i（l- 1). 总结方程式响应l≤ l≤ 从（5.3）中，我们得到“kXs=lhi（s）#v′i（z*i（l））=k- l+1kρ*我- α*i（k）+α*i（l- 1). （5.5）对应于l=l的方程式- 1英寸（5.3）表示，hi（l- 1） v′i（z*i（l- 1)) =ρ*ik- α*i（l- 1) + α*i（l- 2). （5.6）自z*i（l- 1） >z*i（l），从（5.4），我们有α*i（l- 1) = 0. 因此，从（5.5）和（5.6）中，我们得到了- 1） v′i（z*i（l- 1)) ≥ρ*ik≥k- l+1“kXs=lhi（s）#v′i（z*i（l））。此外，由于vi（·）是严格凹的且严格递增，z*i（l- 1） >z*i（l）表示0<v′i（z*i（l- 1） <v′i（z*i（l））。因此，hi（l- 1） >k- l+1“kXs=lhi（s）#（5.7）如果（l- 2） /千≥ p*i、 thenhi（左- 1） =wil- 1公里- wi公司l- 2公里≤k- l+1wi（1）- wi公司l- 1公里=k- l+1“kXs=lhi（s）#.（5.8），其中不等式从（5.1）得出，pi=（l- 2） /k和pi=（l-1） /k.然而，（5.8）与（5.7）相矛盾，因此（l-2） /k<p*i、这证明了引理。6结论和未来工作我们发现，如果我们考虑到玩家的概率敏感性，那么彩票分配会提高玩家的事前聚集效用。我们考虑了RDU模型（CPT效用的特例）来建模概率敏感性。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:31

然而，该模型仅限于奖励分配，将其扩展到具有参考点和损失厌恶的一般CPT模型是很有意思的。这将使我们能够研究惩罚或负担分配中的损失分配，例如刑事司法、军事起草等。对于任何固定的排列文件，我们证明了在基于市场的机制中存在均衡价格，以实现最佳彩票。Wealso还发现，找到最佳置换文件是一个NP难问题。我们注意到，在无线网络【16】和多路由网络【30】中，系统问题在跨层优化方面具有相似性。一些启发式方法有助于在跨层优化中获得近似最优解。需要为我们的系统问题开发类似的方法。我们把这个留给以后的工作。系统问题的困难来自硬链接约束。因此，通过仅将这些条件放宽到期望值，我们导出了RDUmodel中每个代理的概率权重函数的典型假设下最优彩票结构的一些定性特征。正如所观察到的，玩家通常以高概率确保他们的最小分配，以低概率赌更高的回报。引理4.1的一个证明。假设问题（I）及其对偶（II）具有相同的值。（I）的值与系统问题SYS的值相同【z，π；h，v，A，c】。Le t us用Θ（π，z，λ）表示目标函数：=nXi=1kXl=1hi（l）vi（zi（l））+mXj=1kXl=1λj（l）cj公司-xi∈Rjzi（πi（l））.由于F是一个多面体，对于任何固定的置换文件π，可行Zi集都是闭合且有界的。函数Θ（π，z，λ）在z上是连续的，因此固定置换系统问题SYS\\u FIX[z；π，h，v，A，c]有一个有界值。我们还注意到该值是非负的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-6-11 05:38:34

因为有很多置换结果π∈QiSk，m最大化这些，我们得到系统问题有一个有界的非负值，比如W，在z处达到sayat*和π*. ThusnXi=1kXl=1hi（l）vi（z*i（l））=W，（A.1）和彩票z*对于置换函数π是可行的*, i、 e.z*i（l）≥ z*i（l+1）表示所有i∈ [n] ，l∈ [k] andXi公司∈Rjz公司*i（π*i（l））≤ CJ适用于所有j∈ [m] ，l∈ [k] 。（A.2）如果这不是真的，那么目标函数Θ（π）的最小值*, z*, λ）关于λ-∞ 而不是W≥ 对偶问题（II）的值等于W。考虑函数Θd:Rm×k+→ R、通过最大化问题（II）中的目标函数，给出n，关于固定λ的π和d z≥ 0，Θd（λ）：=最大πi∈Sk公司i、 z:zi（l）≥zi（l+1）i、 lΘ（π，z，λ）。我们注意到函数Θd（λ）是下半连续的，因为函数Θ（π，z，λ）在λ中是连续的。自（vi（·）起，i）如果是凹严格递增函数，则存在一个足够大的有限λ，使得0≤ M：=Θd（λ）<∞. 因此，在λj（l）定义的域上，实现了Θd（λ）的最小值∈ [0，M/（minjcj）]对于所有j，l。由于这是一个有界区域，且函数Θd（λ）是下半连续的，因此存在λ*使得Θd（λ*) = 最小λ≥0Θd（λ）=W。自Θd（λ）起*) = W，我们有Θ（π*, z*, λ*) ≤ W然而，根据（A.1）、（A.2）和f，λ*j（l）≥ 对于所有j，l，我们得到Θ（π*, z*, λ*) ≥ W因此Θ（π*, z*, λ*) = W因此，定义Θd（λ）的最大值*) 在z实现*, π*. 这意味着π*isatis fies（4.1）for all i.引理的证明5.1。Let'zi≥ 0和τ>0。让z*我∈ Zi（\'Zi）应确保Vavgi（\'Zi）=Pkl=1hi（l）vi（z*i（l））。我们有，（z*i（l）+τ）l∈[k]∈ Zi（\'Zi+τ）和Vavgi（\'Zi+τ）≥kXl=1hi（l）vi（z*i（l）+τ）>kXl=1hi（l）vi（z*i（l））=Vavgi（(R)zi），其中严格不等式来自于vi（·）严格递增的因子。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝