战略博弈的支付区域及其极值点

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《The Payoff Region of a Strategic Game and Its Extreme Points》
---
作者：
Yu-Sung Tu, Wei-Torng Juang
---
最新提交年份：
2018
---
英文摘要：
  The range of a payoff function for an $n$-player finite strategic game is investigated using a novel approach, the notion of extreme points of a non-convex set. The shape of a noncooperative payoff region can be estimated using extreme points and supporting hyperplanes of the cooperative payoff region. A basic structural characteristic of a noncooperative payoff region is that any of its subregions must be non-strictly convex if the subregion contains a relative neighborhood of a point on its boundary. Besides, applying the properties of extreme points of a noncooperative payoff region is a simple and effective way to prove some results about Pareto efficiency and social efficiency in game theory.
---
中文摘要：
利用一种新的方法，即非凸集极值点的概念，研究了一个n$人有限策略博弈的支付函数的范围。非合作支付区域的形状可以使用合作支付区域的极值点和支持超平面来估计。非合作支付区域的一个基本结构特征是，如果子区域包含其边界上一点的相对邻域，则其任何子区域都必须是非严格凸的。此外，应用非合作支付区域极值点的性质是证明博弈论中关于帕累托效率和社会效率的一些结果的一种简单有效的方法。
---
分类信息：

一级分类：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系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--

---
PDF下载：
--> The_Payoff_Region_of_a_Strategic_Game_and_Its_Extreme_Points.pdf (442.98 KB)

2022-5-31 11:37:26 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：Quantitative Coordination Environments Applications neighborhood

战略博弈的收益区域及其极值点柳成图和魏东娟。使用一种新的方法，即非凸集的极值点的概念，研究了n人有限战略博弈的支付函数的范围。非合作Payoff区域的形状可以使用合作Payoff区域的极值点和支持超平面来估计。非合作Payoff区域的基本结构特征是，如果子区域的边界上包含一个点的相对高度，则其任何子区域都必须是非严格凸的。此外，应用非合作支付区域的极值点性质是证明博弈论中关于帕累托有效性和社会有效性的一些结果的一种简单有效的方法。1、引言在本文中，我们试图探索非合作支付区域的基本性质及其潜在应用。在关于玩家战略行为的不同假设下，n-玩家有限战略博弈的支付区域可能发生。在相关策略下可实现的合作支付区域是由纯策略文件生成的支付向量的凸包；混合策略下可实现的非合作支付区域是刚刚描述的凸多面体的子集。与合作支付区域相比，非合作支付区域的形状通常过于复杂，无法简单描述。很常见的是，两人博弈的非合作支付区域可能看起来像一个锋利的回飞棒，但它永远不会像一个冰淇淋蛋筒（参见Binmore（2007）和Barron（2013））。在这里，这一基本特征将以严格的数学方式得到证明。我们引入了非凸集极值点的概念，并将其应用于非合作Payoff区域。

关键定理是，对于一个n人有限战略博弈，合作支付区域的任何极值点都是非合作支付区域的极值点，所有这些极值点都可以作为参与者选择纯战略的支付函数来实现。这使得我们可以直接推断，如果n维非合作Payoff区域的任何子集包含Payoff区域边界点的相对邻域，则该子集都不可能是严格凸的。另一方面，很容易看出，由n人有限战略博弈生成的合作和非合作支付区域具有相同的支持超平面。此外，RN中非合作Payoff区域的每个支撑超平面必须至少包含该Payoff区域的一个极值点，无论该Payoff区域的形状如何。这些结果将在第3节中介绍。非合作支付区域的一个极端点可以通过纯战略利益的发挥来实现，但反之亦然。我们很自然地比较单词和短语。非合作Payoff区域，非严格凸子区域，极值点，支持超平面。2 YU-SUNG TU和WEI-TORNG JUANGit为非退化混合战略计划无法实现的薪酬目标。在第4节中，我们给出了一些例子来说明事实上它们之间没有必要的关系。最后，我们在第5节中介绍了博弈论中关于帕累托效率和社会效率的一些应用。这些将证明，利用非合作Payoff区域的极值点的性质的方法是证明定理的一种简单而有效的方法。2、预赛和基本属性我们将考虑最终的战略游戏。设N={1，…，N}为层集。对于i∈ N、 非空有限集AI是玩家i可用的纯策略集。

纯战略文件集是笛卡尔产品Qi∈玩家的纯策略集。一个混合策略σiof player i是Ai上的概率分布，并且让（Ai）表示参与者i的混合策略集。笛卡尔乘积Qi∈N（Ai）是所有混合战略文件的集合。我们为n个匹配的参与者定义了一个相关策略，使其成为概率分布∈NAi，表示为（Qi∈NAi）相关策略集。然后，每个混合策略文件σ∈Qi公司∈N（Ai）可以通过以下方式诱导相关策略：Дσ（a）=Qi∈Nσi（ai）对于每个a∈Qi公司∈NAi，其中σi（ai）是σito ai指定的概率。我们将这种相关策略称为σ的诱导相关策略。对于i∈ N、 let ui：齐∈NAi公司→ R是参与者i的payoff函数。每个payoff函数ui都可以扩展到集合（Qi∈NAi）取期望值∈奈。我们还可以将其域扩展到setQi∈N（Ai）以这样一种方式，Ui的支付价值在混合战略利润σ∈Qi公司∈N（Ai）is（2.1）ui（σ）=ui（Дσ）=Xa∈Qi公司∈NAiИσ（a）ui（a），其中Дσ是σ的诱导相关策略。定义向量值支付函数u:Qi∈NAi公司→ Rnby u（a）=（u（a），联合国（a））。然后u可以扩展到集合（Qi∈NAi）和Qi∈N（Ai）通过ui。对于i∈ N和ai∈ Ai，让δAide注意集中在Ai的退化概率（Dirac测度）。很明显，纯战略文件a=（a，…，an）将对应于其混合战略文件σa=（δa，…，δan），我们有u（σa）=u（a）。因此，我们可以将纯战略文件集嵌入混合战略文件集。事实上，混合策略集和相关策略集之间也存在这种关系。下面的引理表明，不同的混合策略对应不同的相关策略。引理2.1。

在有限策略博弈中，所有混合策略的集合和所有诱导相关策略的集合是一一对应的。证据设| Ai |=每个i的MIF∈ N定义f：Qi∈N（Ai）→ （Qi∈NAi）byf（p）=νp，其中p=（p，…，pn），pi=（pi，…，pmii）表示所有i∈ N、 和Дpis是p的诱导相关策略。很明显，f的范围是所有变量的集合。以下是扩展到混合策略集的Ui的等效定义：对于任何σ∈Qi公司∈N（Ai），letui（σ）=Xa∈A···Xan∈σ（a）···σn（An）ui（a，…，An）。战略博弈的支付区域及其极值点3诱导相关战略。为了证明f是内射的，假设f（p）=f（q）。ThenQi公司∈Nprii=Qi∈NQRII对于任何（ri）i∈N带1≤ 国际扶轮社≤ 密歇根州。MJXRJ=1prjjYi的事实∈N \\{j}优先级=mjXrj=1qrjjYi∈N \\{j}每个j的qrii∈ N和每个（ri）i∈N \\{j}带1≤ 国际扶轮社≤ Mi意味着等式Qi∈N \\{j}prii=Qi∈N \\{j}qriiholds表示任何j∈ N对于任何（ri）i∈N \\{j}带1≤ 国际扶轮社≤ 密歇根州。我们再次使用mkxrk=1pkyi这一事实∈N \\{j，k}prii=mkXrk=1qrkkYi∈N \\{j，k}qrii对于每个j，k∈ N和每个（ri）i∈N \\{j，k}带1≤ 国际扶轮社≤ 密歇根州。这一事实意味着质量∈N \\{j，k}prii=Qi∈N \\{j，k}qrii对于任何j，k∈ N对于任何（ri）i∈N \\{j，k}带1≤ 国际扶轮社≤ 密歇根州。重复此过程。模式很清楚，最终得出的结论是，对于每个i，prii=qrii∈ N和每个ri∈ {1，…，mi}。因此，应用支付关系（2.1），我们可以将混合策略集合嵌入到相关策略集合中。备注2.1.1。在每个特定的战略游戏中，setQi∈NAican可被视为嵌入setQi中∈N（Ai）；塞奇∈N（Ai）可被视为嵌入到集合中（Qi∈NAi）。3、非合作支付区域游戏的支付区域可以在关于玩家能够做什么的不同假设下发生。

众所周知，当参与者独立选择策略时，payoff区域可能远离凸区域。如果我们能够获得关于非合作支付区形状的进一步信息，那将大有裨益。在本节中，我们引入了非凸集的极值点的概念，并将其与支持超平面一起应用于非合作Payoff区域。这种方法可以让我们深入了解非凸Payoff区域的一般形状。定义3.1。Let（N，（Ai）i∈N、 （ui）i∈N） 成为一个明确的战略游戏。三个范围u（Qi∈NAi）、u（Qi）∈N（Ai）），和u(（Qi∈NAi）分别由Spu、Snc和Sco表示，分别称为纯payoff区域、非合作payoff区域和合作payoff区域。从第2节，我们知道Spu Snc公司 上合组织。纯payoff region Spu是Rn的一个有限子集，Spu的凸包（由conv（Spu）表示）就是合作payoff region Sco，它是Rn中的一个凸多面体。非合作支付区Snc是Sco的一个子集，也是Sco的一组生成器，即，（3.1）Sco=conv（Spu）=conv（Snc）。在本文中，我们将提供非合作支付区的更多基本特征。首先，我们证明了n人有限战略博弈的非合作支付区域是Rn的一个封闭、有界和连通子集。引理3.2。Let（N，（Ai）i∈N、 （ui）i∈N） 成为一个明确的战略游戏。然后，非合作Payoff区域Sncis路径连通且紧凑。4杜宇松和魏东娟证明。假设Ai={Ai，…，amii}对于每个i∈ N、 然后设置（Ai）可与标准（mi）识别- 1） -单工密歇根州-1.对于每个j∈ N、 定义：Qi∈NRmi公司→ R byUj（x，…，xn）=x（ar，…，arnn）∈Qi公司∈NAixr···xrnnuj（ar，…，arnn），其中xi=（xi，…，xmii）∈ RMI适用于每个i∈ N定义向量值函数u:Qi∈NRmi公司→ RnbyU（x。

，xn）=（U（x，…，xn），Un（x，…，xn））表示所有（x，…，xn）∈Qi公司∈NRmi。那么U是关于欧几里德度量拓扑onQi的连续函数∈NRmiand注册号。显然，塞奇∈N密歇根州-1是QI的一个路径连通的紧凑子集∈NRmi。我们看到不合作的Payoff区域Sncis路径相连且紧凑，因为该区域是QI的形象∈N密歇根州-1在连续功能U下。现在，我们提出一种简单的方法，通过非合作Payoff区域的极值点和支持超平面来描述其形状。极端点。凸集的极值点在凸分析中起着重要作用，但这里我们将极值点的概念推广到非凸集。这个简单的扩展在一些应用中非常有用，例如描述非合作支付区域的形状，它为分析博弈论中的帕累托效率和社会效率提供了一种有效的方法；见第5节。在凸集极值点的概念下，闭凸多边形的任何角点都是一个极值点。当考虑非凸集时，需要进行最小修改才能保留此属性，如下所述。定义3.3。设S是Rn的非空子集。A点x∈ 如果（3.2）x，则称S为S的极值点∈ {θy+（1- θ） z |θ∈ （0，1）} 开关y，z∈ S表示x=y=z。让ext（S）表示S的所有极值点集。这意味着S的一个极值点是S中的一个点，它不是S中包含的任何线段的内部点。

由于定义为3.3的子集S可能是凸的，也可能不是凸的，因此无法检查点x是否位于连接S的两个不同点的线段内部；还必须检查线段是否包含在S中，即条件{θy+（1- θ） z |θ∈ （0，1）} 需要（3.2）中的S。闭合集可能没有极值点（如闭合半平面）、有限个极值点（如闭合多边形）或有限个极值点（如闭合圆盘）。备注3.3.1。RN子集S的内点不能是S的极值点。换句话说，所有极值点都必须是边界点。下一个引理是关于非空紧集极值点存在性的基本结果；见Ichiishi（1983年，第21页）。引理3.4。RN的每个非空紧子集都有极值点。在此定义中，我们不假设RN的子集S是凸的。我们将在示例4.2中看到，根据定义3.3，非凸多边形的角点（2，2）是一个极值点（见图2），尽管点（2，2）可以写成多边形中两个不同点的凸组合。战略对策的支付区域及其极值点RN中凸集的5A基本性质表明，任何紧凸子集 Rn是其极值点的凸包，即K=conv（ext（K））。此外，对于每个紧致子集S 这样conv（S）=K，我们有ext（K） S、 这些是克里恩-米尔曼定理和米尔曼定理在有限维情况下的明显结果（参见Rudin（1973，第75-76页））。因此，对于给定的有限战略博弈，（3.1）中的方程式得出了以下关系：Sco=conv（ext（Sco））和ext（Sco） Spu公司 Snc。本文的主要目的是探讨非合作支付区域的相关性质。

下面的定理说明了SNC的极值点与其他支付点之间的关系，这将在许多应用中发挥核心作用。定理3.5。Let（N，（Ai）i∈N、 （ui）i∈N） 成为一个明确的战略游戏。然后 6=外部（Sco） 外部（Snc） Spu。证据通过引理3.4，我们得到ext（Sco）6=. 显示ext（Sco） 外景（Snc），乐视∈ 外部（Sco）。然后v∈ SNC因为已知ext（Sco） Snc。如果v/∈ ext（Snc），则存在不同的点x，y∈ snc使v=λx+（1- λ） 某些λ的y∈ （0，1）。由于凸集Scocontains Snc，我们得到/∈ 分机（Sco），A交易。接下来我们展示ext（Snc） Spu。让v∈ ext（Snc），并假设对于某些混合策略文件σ，v=u（σ）∈Qi公司∈N（Ai）。假设Ai=（Ai，…，amii）foreach i∈ N，以下分解成立：对于某些j∈ N、 v=αju（aj，σ-j） +（1- αj）mjXt=2αtj1- αju（atj，σ-j） ！，其中，对于t=1，…，αtj=σj（atj），乔丹。自v起∈ ext（Snc）和连接u（aj，σ）的闭合线段-j） andPmjt=2αtj1-αju（atj，σ-j） 包含在Snc中，我们有v=u（aj，σ-j） =mjXt=2αtj1- αju（atj，σ-j） 。If（aj，σ-j）∈Qi公司∈奈，然后是v∈ Spu，我们完成了。否则，我们将继续分解混合战略文件（aj，σ-j） 如上所述。继续此过程。由于集合N是有限的，最终我们将得出结论，对于某些a，v=u（a）∈Qi公司∈奈。众所周知，具有曲线边界的二维非合作区域的情况非常常见，我们将在第4节中看到。边界的某些曲线部分看起来像抛物线，它是由玩家混合策略生成的一系列线段的包络线。这表明非合作支付区总是在抛物线之外。因此，任何包含非合作Payoff区域边界点的相对邻域的子区域都不能是严格凸的。

这个断言可以推广到更高的维度，并且可以使用定理3.5轻松证明，如下所述。备注3.5.1。首先注意，如果一个集合是严格凸的，则在RN中边界点和极值点重合。对于一个n人有限的战略博弈，定理3.5指出非合作支付区域只有有限个极值点。因此，只要子区域包含Snc边界点的相对邻域，任何子区域都必须是非严格凸的。6 YU-SUNG TU和WEI-TORNG Juange Rn中的非常闭凸集可以用闭半空间表示。因此，对于任何n人有限战略博弈，合作支付区域是包含它的所有闭合半空间的交集。类似地，非合作Payoff区域的凸包conv（Snc）可以表示为包含Snc的所有闭合半空间的相交（参见Rockafellar（1970，第99页））。Scoequals-conv（Snc）的事实使我们有动机从支持Sco超平面的角度来描述Sncin。支持超平面。对于任何给定的c∈ Rn \\{0}和α∈ R、 赛斯={x∈ Rn | c·x=α}在Rn中称为超平面。固定螺钉-= {x∈ Rn | c·x≤ α}和H+={x∈ Rn | c·x≥ α}被称为由H.defition 3.6确定的闭合半空间。设S是Rn的非空闭子集。超平面H被称为S的支撑超平面，如果S∩ H 6= S包含在由H.引理3.7确定的两个闭半空间之一。设Sand Sbe的rnconv（S）=conv（S）的非空闭子集。然后，集沙刮去相同的支撑超平面。证据设H={x∈ Rn | c·x=α}是S的支撑超平面，假设S H+。由于H+是一个凸集，conv（S）是包含S的最小凸集，因此我们有S conv（S） H+。因此S conv（S） H+。Let'x∈ S∩ H、 这意味着'x∈ conv（S）和c·'x=α。