請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34278
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 呂育道(Yuh-Dauh Lyuu) | |
dc.contributor.author | Ching-Lueh Chang | en |
dc.contributor.author | 張經略 | zh_TW |
dc.date.accessioned | 2021-06-13T06:01:05Z | - |
dc.date.available | 2009-07-24 | |
dc.date.copyright | 2006-07-24 | |
dc.date.issued | 2006 | |
dc.date.submitted | 2006-06-23 | |
dc.identifier.citation | [AK] S. Aaronson and G. Kuperberg, http://www.complexityzoo.
com/. [CD06] X. Chen and X. Deng, 2D-SPERNER is PPAD-complete, Submitted to STOC (2006). [Che52] H. Chernoff, A measure of the asymptotic efficiency of tests of a hypothesis based on the sum of observations, Annals of Mathmematical Statistics 23 (1952), 493–507. [DGP05] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, The complexity of computing a nash equilibrium, Tech. Report TR05- 115, Electronic Colloquium on Computational Complexity, 2005. [FIKU05] L. Fortnow, R. Impagliazzo, V. Kabanets, and C. Umans, On the complexity of succinct zero-sum games, Proceedings of the 20th IEEE Conference on Computational Complexity, 2005, pp. 323– 332. [FKS95] J. Feigenbaum, D. Koller, and P. Shor, A game-theoretic classification of interactive complexity classes, Proceedings of the 10th Annual IEEE Conference on Computational Complexity, 1995, pp. 227–237. [FPS03] L. Fortnow, A. Pavan, and S. Sengupta, Proving sat does not have small circuits with an application to the two queries problem, Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 2003, pp. 347–357. [GK92] M. Grigoriadis and L. Khachiyan, Approximating solution of matrix games in parallel, Advances in Optimization and Parallel Computing (Amsterdam) (P. Pardalos, ed.), Elsevier, 1992, pp. 129–136. [GK95] , A sublinear-time randomized approximation algorithm for matrix games, Operations Research Letters 18 (1995), no. 2, 53– 58. [Hoe63] W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963), no. 301, 13–30. [Imm88] N. Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing (1988), 935–938. [KB04] R. H. Katz and G. Borriello, Contemporary logic design, 2nd ed., Prentice Hall, 2004. [Kha79] L. G. Khachiyan, A polynomial algorithm in linear programming, Soviet Mathematics Doklady 20 (1979), 191–194. [LN93] M. Luby and N. Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 448–457. [Nas51] J. Nash, Noncooperative games, Annals of Mathematics 54 (1951), 289–295. [New91] I. Newman, Private vs. common random bits in communication complexity, Information Processing Letters 39 (1991), 67–71. [OR94] M. J. Osborne and A. Rubinstein, A course in game theory, MIT Press, 1994. [Owe82] G. Owen, Game theory, Academic Press, 1982. [PST95] S. Plotkin, D. Shmoys, and E. Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research 20 (1995), no. 2, 257–301. [RA97] Klaus Reinhardt and Eric Allender, Making nondeterminism unambiguous, Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, pp. 244–253. [Rud76] W. Rudin, Principles of mathematical analysis, 3rd ed., McGraw- Hill, 1976. [Sha49] C. E. Shannon, Communication in the presence of noise, IRE 37 (1949), 10–21. [Sip05] M. Sipser, Introduction to the theory of computation, 2nd ed., Course Technology, 2005. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34278 | - |
dc.description.abstract | 我們考慮一以正整數n為索引的雙人策略性賽局序列,其中兩玩家都有2^n種純粹策略,並且被允許使用混合策略。我們也假設賽局中的獲利函數以一個n的多項式為上界,這表示賽局的輸贏並不大。我們定義一個玩家在對付一類玩家時所能保證的期望獲利值,為他對付該類中每個玩家時,所得期望獲利值的最大下界。在我們的主要結果中,我們假設第一個玩家可以知道第二個玩家的混合策略,但卻無法得知其隨機投擲的銅板結果。大致上來說,在此情況下只要第二個玩家的計算能力稍微降低,第一個玩家便可以大幅減少其所需要使用的純粹策略,而幾乎不降低其能保證的期望獲利。不論假設第一個玩家可以知道第二個玩家的混合策略,或者假設第一個玩家只能夠得知O(log n)位元關於第二個玩家的資訊,我們都得到一些關於第一個玩家欲保證一個夠好的期望獲利值所需要的計算能力。 | zh_TW |
dc.description.abstract | We consider families of two-person strategic games parameterized by a positive integer n. We assume that each of the players, the row player and the column player, has 2n strategies to choose from and can take mixed strategies.
We also assume that the games are not too “risky” in that the payoffs are at most polynomial in n in absolute value. The row player is said to guarantee an expected payoff of t 2 R against all column players of a certain class when his expected payoff is at least t against all column players of that class. This thesis studies the expected payoff the row player could guarantee against all column players of a certain computational power. In our main result we consider the case where the row player is informed of how the column player chooses his action but is not allowed to see the internal coin tosses of the column player. Roughly speaking, we show that when the computational power of the column player shrinks polynomially, the row player can have his number of pure strategies shrunk exponentially without harming his guaranteed expected payoff too much. We obtain several corollaries regarding the computational power needed by the row player to guarantee a good expected payoff against computationally bounded column players in situations where the row player is aware of the output strategy of the column player, the mixed strategy of the column player, or only O(log n) bits of information about the column player. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T06:01:05Z (GMT). No. of bitstreams: 1 ntu-95-R93922004-1.pdf: 250139 bytes, checksum: 9b64346cc0d2429c59d5b2a9fd0fa10c (MD5) Previous issue date: 2006 | en |
dc.description.tableofcontents | 1 Introduction 2
1.1 Two-Person Strategic Games 2 1.2 Our Results 3 1.3 Related Works 4 2 Preliminaries 6 2.1 Basic Terms in Game Theory 6 2.2 Randomized Circuits 8 2.3 Tail Inequalities 10 2.4 Conventions and Assumptions 10 3 Extraction of Small Numbers of Good Strategies 12 4 Implications on the Power of Players 20 A Complexity Classes 25 Bibliography 30 | |
dc.language.iso | en | |
dc.title | 玩家在雙人賽局中所需計算能力之研究 | zh_TW |
dc.title | On the Computational Power of Players in Two-Person Strategic Games | en |
dc.type | Thesis | |
dc.date.schoolyear | 94-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 戴天時,金國興 | |
dc.subject.keyword | 賽局,計算複雜度, | zh_TW |
dc.subject.keyword | game theory,circuit,computational complexity, | en |
dc.relation.page | 30 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2006-06-23 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 244.28 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。