关于算法博弈论若干问题的研究.pdf

复旦大学
硕士学位论文
关于算法博弈论若干问题的研究
姓名:陈宁
申请学位级别:硕士
专业:计算机软件与理论
指导教师:朱洪
20040528
中文摘要关键词卖,并且讨论其中的馕侍猓颐侵っ髟谡庵帜P拖耊均衡同计算模型下的若干问题,首先,我们考虑在算法机制设计中,机制本身有一个对中,判定獾拇嬖谛允荖的,并且给出了一个关于呐穆裟P鸵籫,计算复杂性,穆簦楹吓穆簦琖均衡,在这篇文章中,我们主要考察在算法博弈论⑶胰绻锌赡艿氖涑鲇雛比不是足够好,:,,,诓煌氖奔淅床斡肱穆舨⑶,并且建立了关于态价格序列之间非常有意义的联系:谝欢ǖ氖谐〖,,,,,我们考虑另外一种基于一定存在,,算法机制设计,穆簦性诓于输出结果的投的拍卖拍卖协议,—穆簦琲
..畉,.甒甒琖琧,琣,.瑂猟,—琣琯,,,—,琧琋猦琯,.:,琣琲
引言】了计算机科学中来分析个体用户的理性行为,包括作为新的通讯手段的出现和普及,,在经济学中关于竞争,合作,,换句话说,,,特别是算法设计与分析和复杂性理论,,一个算法问题的输入是确定的,,包括资源配置,市场价格,,,存在着大量的不知名的用户,而每个用户都是我们设计运用于蚪络中的算法协议时,我们必须将这些用户的行为考虑进去,因为每个参与者灰欢ɑ嵬耆ò,这就需要我们在算法协议运行时,,但是它们却有一个共同点:。这就使得我们可以从理论上对这些用广的行为进行分析,,博弈论越来越多的应用在等等
尘爸J.┺穆【腷模型,⑸娼酉嗷プ饔檬焙虻木霾咦杓年代是合作博弈发展的鼎盛时期,在这一阶段,涌现了包括和果随后,非合作博弈论也开始创建和发展,磕攴⒈砹斯赜诜呛献鞑┺牡⑺咎猓橇┤,证明者就某个问题通过和验证者进行交互使得验证者相信这复旦大学硕士学位论文算法博弈论正是在这样的背景下产生的学科:,我从博弈论的角度、~,,『玁獾母念引入了动态分析,提出了完美均衡的概念.『巡煌耆畔⒁,,和共同获得了诺贝尔醚具体到计算机科学中,博弈论主要研究的是在多用户的计算机网络系统中,以个入利益最大化为目标的各个用户怎样在已有信息的基础上作出理性的决策,而同时从整个系统来看,用户们又是怎样相互影响,从而最终达到系统的最优状态或其实博弈论的思想对计算机科学家尤其是从事计算理论研究的学者来说并不陌生,在复杂性理论中,~个诚实的强大的证明者,