算法博弈论.pptVIP

社交网络·互联网·市场·人之算法博弈论 成员： 目录： 算法博弈论背景 算法博弈论简介 博弈论研究的主要问题 主要内容和分类 非合作博弈 合作博弈 自私路由问题 算法博弈论背景 互联网的兴起与其他新兴的发明类似，虽然为人类生活带来了福利，促进了商业、经济的发展，但也带来了很多问题。因此，在大规模网络环境下，个人自利行为的相互制约与系统机制的整体约束，成为虚拟社会、经济系统以及社交网络在成长过程中保持稳定的一类重要因素。在此背景下，算法博弈论脱颖而出，人们可以利用它来研究在大规模网络环境下人与人、人与网络的交互系统以及人与市场规则相互作用下的规律。 算法博弈论简介 博弈论是应用数学的一个分支，当前其应用领域已经从最初的军事领域扩展到政治、经济、文化、法律和哲学等社会性学科以及生物、工程和计算机等理工性学科，并以经济学科中的应用最被人所熟知。博弈论试图以数学方式刻画策略性场景中的用户行为，每个用户的选择成功与否取决于其他人的行为选择。 博弈论研究的主要问题 算法博弈论一方面分析大规模数据博弈问题的快速计算问题。 另一方面则探讨算法协议在大规模网络下参与者的各种博弈行为。 主要简介和分类 博弈论将实体间的相互操作看作是一个博弈，每个博弈参与者依据系统设计者事先定义好的规则选择策略并进行操作，在博弈结束时获得一定收益。博弈可以分为静态博弈和动态博弈，静态博弈指所有博弈者同时进行策略选择，动态博弈指博弈者的操作具有先后之分。博弈类型也可以分为完全信息博弈和非完全信息博弈，其中完全信息博弈指全体博弈者在进行策略选择时完全知道有关作出决定的所有信息，非完全信息博弈则相反，可能需要依凭一定的概率假设进行操作。还可以分为非合作博弈与合作博弈，在非合作博弈中，实体用户之间没有签约协议或存在协作，在合作博弈中，实体间先协同获得最大的团体利益，再将团体利益分配到每个个体实体，在利益分配时会涉及到公平性和团体稳定性等问题。当前 研究中较多的采用非合作博弈，从合作博弈的角度出发的研究并不太多。 非合作博弈 博弈论的主要内容是关于个人在群体之间的行为模式研究。其中，纳什均衡这一重要概念刻画了所有博弈参与者在追求个人利益最优条件下的稳定状态。所谓纳什均衡是指某一策略组合，任意一个博弈者在该策略组合下不可能通过单独行动来增加收益，即为了自身利益的最大化，没有人愿意单方面改变自己的当前策略。从本质上说，纳什均衡是一种非合作博弈状态。 合作博弈 博弈论的另一主要研究内容是关于参与者之间的合作博弈，其主要目标是考虑如何促进并维护博弈参与者之间的合作。在合作博弈中，核心问题是如何合理、有效地确定参与者各自应得的份额，所有参与者的份额组合称为合作博弈的解。基于不同的公平性概念，人们给出了各种不同解的定义。但目前这些概念都有不尽如人意的地方。 自私路由问题 在我们讨论的自私路由问题中，每个用户都是“自私”的，他们的目标是选择恰当的路径来运输物品，使得运输费用最小化。由于整个网络中物品的运输路径决定于所有用户此他们的自私行为可能会导致整体社会效益降低。下面通过这个例子，让读者初步了解这些自私行为所带来的负面影响。 庇古实例 其中，弧a1 拥有常数延时 函数，弧a2 的延时函数为x 说明弧a2 上的延时费用着 流量的增加而增加。 由于每个用户是以运输费用最小化为目的，因此该实例存在唯一的纳什均衡解，即所有人都选择弧a2，从而a2 上总流量为1，延时费用等于1。。对于上述纳什均衡，其目标函数值为1。另一方面，考虑另一可行解，即分别为弧a1 和a2 分配1/2物品流量。容易验证，该可行解是最优解，最优目标函数值为3/4。由此可见，用户们的自私行为使总体运输费用增加到最优解的4/3。在庇古实例中，可以看到用户的自私行为导致整体社会效益的增加。 未来研究方向 网络博弈有着巨大的研究空间。除了对自利和理性的网络参与者的行为进行分析外，在统计行为、博弈行为及集体知识挖掘等方面都有很好的研究前景。目前，云计算定价理论与实践也是算法博弈论最为热门的应用领域之一。同时，在电子商务中，买卖双方许多策略性行为设计分析和应用使得算法博弈论与大数据分析的结合有了用武之地。可以看出，在计算机科学理论与技术的推动下，算法博弈论正成为跨学科的重要方法论。 感谢聆听 欢迎提问