博弈论(Game theory)有时也称为对策论,或者赛局理论,应用数学的一个分支,目前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。主要研究公式化了的激励结构(游戏或者博弈)间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。也是运筹学的一个重要学科。

VIP内容

我们并不是生活在真空中!我们与环境中的其他主体互动以做出理性的决定。例如,选择从你的公寓到校园的最快或最简单的路线,在eBay拍卖中选择最合适的出价,决定是否在双人扑克游戏中认输,或在石头剪刀布游戏中选择获胜的一步棋。在所有这些例子中,我们在做决策时必须与其他代理交互。特别是,我们的最佳策略取决于环境中其他代理的行为(例如,选择的路线取决于使用这些路线的其他人的数量,如果我的对手选择剪刀,我就选择石头)。在给定的环境中,面对其他战略主体时,我们如何做出理性的决策?最好的策略是什么?博弈论帮助我们回答这些问题。

博弈论是一种数学工具,它允许我们对特定环境下的利己主义和理性行为者的战略互动进行推理。该结构提供了一组框架,描述了在这样一个战略代理人的环境下的理性结果。虽然博弈论领域起源于经济文献,但计算机科学家在过去几十年里从建模和计算的角度对这一领域做出了重大贡献(这导致了计算博弈论)。此外,许多博弈论应用在现实世界中(例如,分配警力到洛杉矶国际机场的检查站,分配巡逻人员来保护非洲的野生动物,预测美国参议员的投票行为)。

观众将会学习到: (1) 引入基本的博弈论决策工具,建模和理解自利和战略代理的战略互动; (2) 了解建模工具的解决方案概念,以及如何使用它们来预测agent的决策行为; (3) 介绍了计算方面的计算这些解的概念; (4 )接触了博弈论在安全和社会科学领域的一些主要应用。 此外,如果时间允许,讲座将涵盖更高级的主题,包括解决复杂策略空间的博弈,博弈中的学习,完全信息的动态博弈,不完全信息的静态博弈,不完全信息的动态博弈。

成为VIP会员查看完整内容
0
30

最新内容

Mining processes of Bitcoin and similar cryptocurrencies are currently incentivized with voluntary transaction fees and fixed block rewards which will halve gradually to zero. In the setting where optional and arbitrary transaction fee becomes the prominent/remaining incentive, Carlsten et al. [CCS 2016] find that an undercutting attack can become the equilibrium strategy for miners. In undercutting, the attacker deliberately forks an existing chain by leaving wealthy transactions unclaimed to attract petty complaint miners to its fork. We observe that two simplifying assumptions in [CCS 2016] of fees arriving at fixed rates and miners collecting all accumulated fees regardless of block size limit are often infeasible in practice, thus inaccurately inflating its profitability. The intuition is that the fees deliberately left out by an undercutter may not be attractive to other miners (hence to the attacker itself): the left-out transactions may not fit into a block without "squeezing out" other to-be transactions, and thus claimable fees in the next round cannot be raised arbitrarily. This work views undercutting and shifting among chains as mining strategies of rational miners. We model profitability of undercutting strategy with block size limit present, which bounds the claimable fees in a round and gives rise to a pending transaction set. In the proposed model, we first identify conditions necessary to make undercutting profitable. We then present an easy-to-deploy defense against undercutting by selectively assembling transactions into a new block to invalidate the identified conditions. Indeed, in a typical setting with undercutters present, applying the avoidance technique is a Nash Equilibrium. Finally, we complement the analytical results with an experimental analysis using both artificial data of normally distributed fee rates and actual transactions in Bitcoin and Monero.

0
0
下载
预览

最新论文

Mining processes of Bitcoin and similar cryptocurrencies are currently incentivized with voluntary transaction fees and fixed block rewards which will halve gradually to zero. In the setting where optional and arbitrary transaction fee becomes the prominent/remaining incentive, Carlsten et al. [CCS 2016] find that an undercutting attack can become the equilibrium strategy for miners. In undercutting, the attacker deliberately forks an existing chain by leaving wealthy transactions unclaimed to attract petty complaint miners to its fork. We observe that two simplifying assumptions in [CCS 2016] of fees arriving at fixed rates and miners collecting all accumulated fees regardless of block size limit are often infeasible in practice, thus inaccurately inflating its profitability. The intuition is that the fees deliberately left out by an undercutter may not be attractive to other miners (hence to the attacker itself): the left-out transactions may not fit into a block without "squeezing out" other to-be transactions, and thus claimable fees in the next round cannot be raised arbitrarily. This work views undercutting and shifting among chains as mining strategies of rational miners. We model profitability of undercutting strategy with block size limit present, which bounds the claimable fees in a round and gives rise to a pending transaction set. In the proposed model, we first identify conditions necessary to make undercutting profitable. We then present an easy-to-deploy defense against undercutting by selectively assembling transactions into a new block to invalidate the identified conditions. Indeed, in a typical setting with undercutters present, applying the avoidance technique is a Nash Equilibrium. Finally, we complement the analytical results with an experimental analysis using both artificial data of normally distributed fee rates and actual transactions in Bitcoin and Monero.

0
0
下载
预览
Top