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

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Optimal Resource Allocation over Networks via Lottery-Based Mechanisms》
---
作者：
Soham R. Phade and Venkat Anantharam
---
最新提交年份：
2018
---
英文摘要：
  We show that, in a resource allocation problem, the ex ante aggregate utility of players with cumulative-prospect-theoretic preferences can be increased over deterministic allocations by implementing lotteries. We formulate an optimization problem, called the system problem, to find the optimal lottery allocation. The system problem exhibits a two-layer structure comprised of a permutation profile and optimal allocations given the permutation profile. For any fixed permutation profile, we provide a market-based mechanism to find the optimal allocations and prove the existence of equilibrium prices. We show that the system problem has a duality gap, in general, and that the primal problem is NP-hard. We then consider a relaxation of the system problem and derive some qualitative features of the optimal lottery structure.
---
中文摘要：
我们证明，在资源分配问题中，通过实施彩票，具有累积前景理论偏好的玩家的事前聚合效用可以超过确定性分配。我们制定了一个优化问题，称为系统问题，以找到最优的彩票分配。系统问题呈现出一个由排列轮廓和给定排列轮廓的最优分配组成的两层结构。对于任何固定的排列模式，我们提供了一种基于市场的机制来寻找最优配置并证明均衡价格的存在性。我们证明了系统问题一般具有对偶缺口，并且原始问题是NP难问题。然后，我们考虑了系统问题的松弛，并导出了最优彩票结构的一些定性特征。
---
分类信息：

一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--
一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Computer Science        计算机科学
二级分类：Networking and Internet Architecture        网络和因特网体系结构
分类描述：Covers all aspects of computer communication networks, including network architecture and design, network protocols, and internetwork standards (like TCP/IP). Also includes topics, such as web caching, that are directly relevant to Internet architecture and performance. Roughly includes all of ACM Subject Class C.2 except C.2.4, which is more likely to have Distributed, Parallel, and Cluster Computing as the primary subject area.
涵盖计算机通信网络的所有方面，包括网络体系结构和设计、网络协议和网络间标准（如TCP/IP）。还包括与Internet体系结构和性能直接相关的主题，如web缓存。大致包括除C.2.4以外的所有ACM主题类C.2，后者更有可能将分布式、并行和集群计算作为主要主题领域。
--
一级分类：Mathematics        数学
二级分类：Optimization and Control        优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--
一级分类：Quantitative Finance        数量金融学
二级分类：Risk Management        风险管理
分类描述：Measurement and management of financial risks in trading, banking, insurance, corporate and other applications
衡量和管理贸易、银行、保险、企业和其他应用中的金融风险
--

---
PDF下载：
--> Optimal_Resource_Allocation_over_Networks_via_Lottery-Based_Mechanisms.pdf (227.99 KB)

2022-6-11 05:37:05 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：网络资源 Architecture Optimization Applications Contribution

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

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

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

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

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

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

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

（注意，对于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。

因此，最低分配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+。