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

设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。

让我们用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] 。

（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]。

我们有以下分解结果：定理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。

如果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更新速率呈现给用户。

定理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，给出了最优确定性分配。

此分配的聚合性为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下的单位分配价格。

由于数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+。

让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”也是满足的。

因此，平均系统问题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] 对应于不同结果下的这一联系，并假设并非所有这些都是相等的。然后，对偶问题的最佳每突变概率将按照相同的顺序调整两个参与者的分配，即。