本論文研究兩個有關量子計算理論中的問題，其一為量子博弈論，其二為量子查詢複雜度。 / 博弈論於經濟學、計算機科學、生物學、數學等領域中皆為一門重要課題，近年越來越多有關的研究都把焦點放於量子博弈論之上。本論文的第一部份，我們研究由張氏於2010 年提出的量子策略博弈模型。其中研究重點在於某特定類型的博弈中，計算使用量子策略比經典策略多出的優勢。我們成功建構出一個特定的博弈，並証明使用量子策略比經典策略多出的優勢跟策略的多少成線性關係。 / 本論文的第二部份，主要研究有關量子查詢複雜度，它提供一個簡單的框架，用於理解量子力學的計算能力和限制。我們研究的重點在於量子的安得拉-卡普-羅森伯格猜想，那是關於決定某一類圖特性所需的量子查詢複雜度。我們將會介紹施氏與張氏的猜想、布爾函數分析及查詢複雜度研究中重要的研究結果。我們嘗試証明施氏與張氏的猜想，並於最後提出一個有關布爾函數塊敏感度，影響度及方差值的猜想。 / We study two problems, one in quantum game theory and another in quantum query complexity. / Game theory is an important research topic in many elds like economics, computer sciences, biology, mathematics, etc. A growing trend is that game theory is being studied under quantum setting. In part I, we study the quantum strategic game model proposed by Zhang [Zha10], in which one of the main problem is to measure quantitatively the advantages of using quantum strategies over classical ones. A natural measure is the increase of payoff , which is quantified in terms of multiplicative incentive in a normalized n x n bimatrix game. The maximal incentive under superposition mapping, which maps a classical correlated equilibrium p to a quantum state Σ[subscript s] Pspp(s) jsi, is conjectured to be Ω(n). However only a correlated equilibrium with multiplicative incentive n°·⁵⁸⁵··· under such mapping was found. We proved this conjecture by constructing a classical correlated equilibrium with multiplicative incentive of (n+3)/4 =Ω(n) under such mapping. The proof is much simpler than the old one and gives an optimal result. / On the other hand, we studied quantum query complexity, which provides a simple framework for understanding the computational power and limit by quantum mechanics. In particular, we are interested in the quantum version of Aanderaa-Karp-Rosenberg conjecture for non-trivial monotone graph properties. In part II, we introduce the conjecture by Shi and Zhang [SZ05], survey some important results in Boolean function analysis and query complexity. We put down some partial results on resolving conjecture of Shi and Zhang and propose another conjecture regarding block sensitivity, in uence and variance of a Boolean function, which is simple, interesting and related to the problem. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Wong, Chung Hoi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves [89]-94). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese. / Chapter I --- Quantum Strategic Game --- p.1 / Chapter 1 --- Classical and Quantum Strategic Game --- p.5 / Chapter 1.1 --- Classical Strategic Game Theory --- p.6 / Chapter 1.1.1 --- Notation for Strategic Game --- p.6 / Chapter 1.1.2 --- Classical Equilibrium --- p.7 / Chapter 1.2 --- Quantum Strategic Game Theory --- p.9 / Chapter 1.2.1 --- Notation for Quantum Strategic Game --- p.9 / Chapter 1.2.2 --- Quantum Equilibrium --- p.11 / Chapter 1.3 --- Preservation of Equilibrium --- p.11 / Chapter 1.3.1 --- Quantum to Classical --- p.12 / Chapter 1.3.2 --- Classical to Quantum --- p.12 / Chapter 2 --- Incentives in Quantum Strategic Game --- p.15 / Chapter 2.1 --- Previous Result --- p.15 / Chapter 2.2 --- Improved Multiplicative Incentive to n0:638 --- p.17 / Chapter 2.3 --- Improved Multiplicative Incentives to (n) --- p.19 / Chapter II --- Quantum Aanderaa-Karp-Rosenberg Conjecture --- p.23 / Chapter 3 --- Introduction --- p.27 / Chapter 3.1 --- Non-Trivial Monotone Graph Properties --- p.27 / Chapter 3.2 --- Aanderaa-Karp-Rosenberg Conjecture --- p.27 / Chapter 3.3 --- Conjecture of Shi and Zhang --- p.28 / Chapter 4 --- Boolean Function Analysis --- p.31 / Chapter 4.1 --- Notations --- p.31 / Chapter 4.1.1 --- Sensitivity and Block Sensitivity --- p.32 / Chapter 4.1.2 --- p-biased Mean and Variance --- p.33 / Chapter 4.1.3 --- p-biased Influence --- p.34 / Chapter 4.2 --- p-biased Fourier Analysis --- p.36 / Chapter 5 --- Decision Tree Complexity --- p.43 / Chapter 5.1 --- Deterministic Decision Tree Complexity --- p.43 / Chapter 5.2 --- Randomized Decision Tree Complexity --- p.45 / Chapter 5.3 --- Non-Deterministic Decision Tree Complexity --- p.47 / Chapter 5.4 --- Quantum Query Complexity --- p.50 / Chapter 5.5 --- The General Adversary Bound --- p.52 / Chapter 5.6 --- Quantum Query Complexity Lower Bound --- p.54 / Chapter 6 --- Classes of Boolean Function and Their Properties --- p.59 / Chapter 6.1 --- Properties of Monotone Functions --- p.59 / Chapter 6.2 --- Properties of Transitive Functions --- p.64 / Chapter 6.3 --- Properties of Monotone and Transitive Function --- p.70 / Chapter 7 --- Conjecture of Shi and Zhang --- p.73 / Chapter 7.1 --- Designing the Adversary Matrix by Fourier Coefficients of the Weight Function --- p.73 / Chapter 7.2 --- Designing of Adversary Matrix by Level k Fourier Weight --- p.78 / Chapter 8 --- Block Sensitivity-Influence Conjecture --- p.81 / Chapter 8.1 --- Boolean Functions That Satisfy the BSI Conjecture --- p.83 / Chapter 8.2 --- Recursive k-Majority --- p.84 / Chapter 8.3 --- Tribes of Size k --- p.85 / Chapter 8.4 --- Boolean Functions with Small Sensitivity Are Sparse --- p.87 / Bibliography --- p.89

本論文擴展Young(1993b)所提出的演化議價模型(evolutionary bargaining model)以容許一個包含多個買家和賣家的雙邊市場。 本文應用隨機穩定性(stochasticstability)作為解決方案概念，發現當市場雙邊參與者的人數相同時，長期穩定分成會收歛到納什談判解 (Nash bargaining solution)，這和 Young的發現相符。然而, 若雙邊參與者的人數並不相同。則長遠而言，人數較少的一方將分得近乎所有得益.此結論符合瓦爾拉斯結論(Walrasian outcome)。 / This thesis extends the evolutionary bargaining model of Young (1993b), to allow for a two-sided market with multiple numbers of buyer and seller. Applying the solution concept of stochastic stability, we find that if the number of players in the two sides are symmetrical, then the long run stable division converges to the Nash bargaining solution, which coincides with Young's finding. However, if the number of players in the two sides are asymmetrical, then the smaller side obtains almost all of the surplus in the long run, which is consistent with the unique Walrasian outcome. / Detailed summary in vernacular field only. / Tam, Yin Chi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 52-53). / Abstracts also in Chinese. / Abstract --- p.i / 摘要 --- p.ii / Acknowledgements --- p.iii / Chapter 1. --- Introduction --- p.1 / Chapter 2. --- Literature Review --- p.6 / Chapter 3. --- The Model --- p.8 / Chapter 4. --- Convergence of the Evolutionary Bargaining Process --- p.14 / Chapter 5. --- Mutations in the Evolutionary Bargaining Process --- p.16 / Chapter 6. --- Generic Stability --- p.19 / Chapter 6.1 --- Asymmetric Market and the Walrasian Outcome --- p.20 / Chapter 6.2 --- Symmetric Market and the Nash Bargaining Solution --- p.23 / Chapter 7. --- Discussion --- p.25 / Chapter 8. --- Conclusion --- p.27 / Appendix --- p.28 / Proof of Theorem 3 --- p.28 / Figures and Tables: --- p.46 / References --- p.52

Thesis. 1976. Ph.D.--Massachusetts Institute of Technology. Dept. of Economics. / Microfiche copy available in Archives and Dewey. / Vita. / Bibliography: leaves 26-28, 79-80. / Learning behavior and the noncooperative equilibrium.--A game of fair division. / Ph.D.

She, Yingni. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 74-78). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Scope --- p.2 / Chapter 1.2 --- Motivation --- p.5 / Chapter 1.3 --- Structure of the Thesis --- p.6 / Chapter 2 --- Literature Review --- p.7 / Chapter 2.1 --- Intelligent Agents and Multiagent Systems --- p.8 / Chapter 2.1.1 --- Intelligent Agents --- p.8 / Chapter 2.1.2 --- Multiagent Systems --- p.10 / Chapter 2.2 --- Minority Game --- p.13 / Chapter 2.2.1 --- Minority Game --- p.13 / Chapter 2.2.2 --- Characteristics of Minority Game --- p.14 / Chapter 2.2.3 --- Strategies for Agents in Minority Game --- p.18 / Chapter 2.3 --- Resource Allocation --- p.22 / Chapter 2.3.1 --- Strategies for Agents in Multiagent Resource Allocation --- p.23 / Chapter 3 --- Individual Agent´ةs Wealth in Minority Game --- p.26 / Chapter 3.1 --- The Model --- p.26 / Chapter 3.2 --- Motivation --- p.27 / Chapter 3.3 --- Inefficiency Information --- p.28 / Chapter 3.4 --- An Intelligent Strategy --- p.31 / Chapter 3.5 --- Experiment Analysis --- p.32 / Chapter 3.6 --- Discussions and Analysis --- p.35 / Chapter 3.6.1 --- Equivalence to the Experience method --- p.36 / Chapter 3.6.2 --- Impact of M' and S' --- p.38 / Chapter 3.6.3 --- Impact of M and S --- p.41 / Chapter 3.6.4 --- Impact of Larger Number of Privileged Agents --- p.48 / Chapter 3.6.5 --- Comparisons with Related Work --- p.48 / Chapter 4 --- An Adaptive Strategy for Resource Allocation --- p.53 / Chapter 4.1 --- Problem Specification --- p.53 / Chapter 4.2 --- An Adaptive Strategy --- p.55 / Chapter 4.3 --- Remarks of the Adaptive Strategy --- p.57 / Chapter 4.4 --- Experiment Analysis --- p.58 / Chapter 4.4.1 --- Simulations --- p.58 / Chapter 4.4.2 --- Comparisons with Related Work --- p.62 / Chapter 5 --- Conclusions and Future Work --- p.69 / Chapter 5.1 --- Conclusions --- p.69 / Chapter 5.2 --- Future Work --- p.71 / A List of Publications --- p.73 / Bibliography --- p.74

It is demonstrated that for certain markets where traders have constant elasticity of substitution utility (CES) functions, the existence of a price equilibrium can be determined in polynomial time. It is also shown that for a certain range of elasticity of substitution where the CES market does not satisfy gross subsitutability that price equilibira can be computed in polynomial time. It is also shown that for markets satisfying gross substitutability, equilibria can be computed in polynomial time even if the excess demand is a correspondence. On the experimental side, equilibrium computation algorithms from computer science without running time guarantees are shown to be competitive with software packages used in applied microeconomics. Simulations also lend support to the Nash equilibrium solution concept by showing that agents employing heuristics in a restricted form of Texas Holdem converge to an approximate equilibrium. Monte Carlo simulations also indicate the long run preponderance of skill over chance in Holdem tournaments.

Co-management is considered an alternative approach to fisheries management, however, not all co-managed fisheries have been successful. Most studies discussing the success and failure of co-management have emphasized economic and social attributes of success and failure, such as fishery rights and institutional arrangements. The effect on co-management of biological characteristics, such as the growth rate of the fish stock and the stock size, has gained little attention. This study investigates the influence of intrinsic growth rate (r) and relative stock size (B') on fishers' decision to cooperate with catch quotas. The concept of mixed strategies from game theory is incorporated with basic economic concepts and a biomass dynamics model to capture important aspects in a fishery cooperative. The discounting concept is applied to capture the fishers' tendency to cooperate (��[subscript i]). Profits from fishing are specified for each fisher within a 2 by 2 matrix with two players and two strategies (cooperative and non-cooperative). When both players have dominant strategies, where one player's best strategy coincides with the other player's best strategy, the game has a pure strategy equilibrium. Alternatively, the equilibrium outcome of the game is determined using mixed strategies. The results indicate that the biological parameters, r and B', influence fishers' cooperation. However, social parameters (��[subscript i]) and economic parameters (profit/cost ratio when the stock is at the carrying capacity) must also be considered. Furthermore, this study finds that the fishers are more likely to play the cooperative strategy over very wide ranges of r and B' when their tendencies to cooperate are high. In contrast, the fishers are more likely to play mixed strategy when their tendencies to cooperate are low. Having a large discrepancy between the fishers' tendencies to cooperate has less influence on the outcomes of the game than having high values for the fishers' tendencies to cooperate. The profit/cost ratio generally accentuates the most frequent outcomes of the game. For instance, if the outcomes are mostly mixed strategies, a higher ratio expands the mixed strategy outcomes over wider ranges of r and B'. / Graduation date: 2001

Thesis (Ph. D.)--Drexel University, 2006. / Includes abstract and vita. Includes bibliographical references (leaves 76-78).

<p>Game theory involves the study of how self-interested agents interact in various settings. Perhaps the best-known game theoretic solution concept is that of Nash equilibrium. However, Nash equilibrium makes a number of assumptions, such as rationality of all of the players and the ability of the players to choose the same equilibrium when more than one exists. Because of these assumptions, it is unclear if simply solving for Nash equilibrium is always the correct thing to do. In some settings, one player can instead credibly commit to a strategy, and communicate this to the other player, before the other player can make a decision. This has become known as a Stackelberg game. Computing optimal strategies to commit to in normal-form or Bayesian Stackelberg games is a topic that has recently been gaining attention, in part due to the application of such algorithms in various security and law enforcement scenarios. My work on Stackelberg games falls into three main areas. </p><p>First, I focus on general games, where we give efficient algorithms and hardness results for Bayesian, extensive-form and stochastic games. In each of these settings we study the relationship between different modeling assumptions and the tractability of finding an optimal strategy to commit to. For Bayesian games our results are mainly negative; we show that not only are the problems here NP-hard, but in many cases they are also inapproximable. Our results for extensive-form games are more mixed; we are able to give polynomial time algorithms for four cases. However, we also show that if we relax the assumptions made in these four cases, then the problem usually becomes NP-hard. Finally, our results for stochastic games are again somewhat negative, as we show that the problem is NP-hard is most reasonable cases. However, here we are also able to give an approximation algorithm to compute optimal commitment strategies in a setting where correlation is allowed.</p><p>I next focus on Stackelberg security games. Stackelberg security games usually involve the scheduling of scarce defense resources to cover some subset of potential targets. We first study methods for going from marginal solutions (which ignore overlapping coverage between different schedules) to valid mixed commitment strategies in graphical settings. Here we are able to characterize two new classes of games where mixed strategies corresponding to the marginal probabilities are guaranteed to exist, and give algorithms for finding them. Next, we offer a simple model of interdependencies between nodes in a network based on probabilistic failure cascades, extending the well-known independent cascade model of the spread of infectious diseases or ideas. We give an algorithm for this problem and experimentally show that this algorithm scales to realistic security settings and outperforms the state of-the-art alternatives. Finally, we create an approach for optimal interdiction of attack plans. We show how to model an attack plan interdiction problem as a large-scale integer linear program similar to an integer programming approach for solving partial satisfaction planning problems. We also give several oracle-based approaches for solving this and then evaluate them experimentally. </p><p>Third, I analyze how much benefit a player can derive from commitment in various types of games, in a quantitative sense that is similar to known concepts such as the value of mediation and the price of anarchy. To do this we introduce and study the value of pure commitment (the benefit of committing to a pure strategy), the value of mixed commitment (the benefit of committing to a mixed strategy), and the mixed vs. pure commitment ratio (how much can be gained by committing to a mixed strategy rather than a pure one).</p> / Dissertation

This thesis is an examination of the traveler’s dilemma and its backward induction argument. I begin by explaining relevant terminology, the prisoner’s dilemma, and the iterated prisoner’s dilemma; the discussion of which aids my examination of the traveler’s dilemma and its backward induction argument. My evaluation of the traveler’s dilemma involves a dissection of the game into its different components, a presentation of the salient similarities and differences between the traveler’s dilemma and the prisoner’s dilemma, and the exploration of three possible solutions. The first two solutions are adapted from ones initially created to solve other backward induction argument problems. The third solution is original and its foundation rests on the unique structure of the traveler’s dilemma. I focus on this third solution and consider several objections to it. I end this thesis with some ancillary comments about the possibility of generalizing the third solution to other backward induction argument problems. / February 2008

El propósito de esta tesis es el analizar a través de la Teoría de Juegos los incentivos de los agentes y grupos sociales a recurrir al conflicto y la confrontación para alcanzar sus objetivos.En su primera parte se incorporan los recientes avances en la teoría de formación de grupos a un modelo económico de conflicto. Esta rama de la literatura económica ha ignorado este aspecto. La formación de grupos en modelos de conflicto presenta dos elementos fundamentales. Primero, la formación de una coalición genera efectos externos en otros grupos. Segundo, la gran coalición puede considerarse como una situación de paz universal dado que no se dedican recursos al conflicto.El primer capítulo presenta un modelo generalizado de búsqueda de rentas en equilibrio parcial. El principal propósito es analizar la estabilidad de la paz universal, la situación eficiente. Ésta resulta ser muy resistente a las desviaciones, especialmente si los individuos se comportan cooperativamente dentro de los grupos. La paz universal es también el resultado del proceso secuencial de formación de grupos introducido por Bloch (1996). Situaciones conflictivas puedes ser estables solo si los agentes tienen expectativas positivas sobre la reacción de los demás agentes a su desviación.En el segundo capítulo, se analiza un modelo en equilibrio general donde los grupos luchan por el control de un recurso. El acceso a dicho recurso viene dado por una contienda de exclusión donde solo una coalición puede ser. Si el recurso es explotado cooperativamente y la tecnología del conflicto es relativamente mejor que la tecnología de producción, la paz universal no es estable. Si el recurso es explotado no cooperativamente y se convierte en un recurso de propiedad común, el conflicto puede ser socialmente eficiente dado que alivia la sobreexplotación.En el capítulo tres se explora un modelo de negociación con dos jugadores donde uno de ellos posee información incompleta acerca de la fuerza de su oponente. Se considera la posibilidad de que cada periodo las partes puede luchar un conflicto total que termina el juego o una "batalla" que solo introduce retraso pero cuyo resultado transmite información acerca de la verdadera relación de fuerzas en caso de conflicto absoluto. Por tanto, un conflicto limitado puede ayudar a las partes a ponerse de acuerdo porque evita el optimismo en el largo plazo. Este aspecto introduce una novedad don respecto a otros modelos de negociación con información incompleta dado que la transmisión de información es difícilmente manipulable. El principal resultado es que el conflicto puede abrir la puerta al acuerdo si unas expectativas optimistas lo están evitando pero puede retrasarlo si la parte informada lo usa para mejorar su posición.Finalmente en el capítulo cuarto verificamos empíricamente las implicaciones de este modelo a través de un análisis de duración. Nos fijamos en la dependencia mostrada por la tasa de riesgo de conflictos reales. Si un conflicto es un mecanismo de persuasión, esta dependencia debe ser positiva, es decir, cuanto más dura un conflicto, más probable es que este acabe. Realizamos dicho análisis con una base de datos de guerras coloniales e imperiales entre 1816 y 1988. Los resultados obtenidos apoyan la hipótesis de una tasa de riesgo creciente. / The aim of the Ph.D dissertation can be summarized as follows: I use the tools of Game Theory to analyze why and how individuals and groups resort to confrontation and conflict in order to attain their goals.In a first part, I incorporate recent advances in coalition formation theory to an economic model of conflict: This strand of the economic literature has typically neglected this issue. Coalition formation in conflict models displays two particular features: Group formation generates spillovers across outsiders; and the grand coalition can be thought off as a situation of universal peace because no resources are devoted to conflict.Chapter one presents a generalized rent-seeking model in partial equilibrium. Our main goal is to analyze the stability of universal peace, the efficient situation. It turns out to be very resilient to possible deviations, specially if individuals behave cooperatively within coalitions. Universal peace is also the outcome of the sequential game of coalition formation introduced by Bloch (1996). Conflict situations can be sustained as stable outcomes only if players hold optimistic (and not necessarily rational) expectations about outsiders reactions to deviation. In the second chapter I move to a general equilibrium model where groups fight for the right to control a resource. Access to that resource is driven by an exclusion contest that is won by only one coalition. If the resource is exploited cooperatively and conflict technology is relatively better than the production technology, universal peace is not stable. If the resource is exploited non-cooperatively, it becomes a common property resource and in that case, conflict may be socially efficient because it alleviates overexploitation. In chapter three we explore a two-person bargaining model where one player has incomplete about the opponent strength. We consider the possibility that at each period parties can fight either a total conflict that ends the game or a "battle" that only causes delay but whose outcome conveys information about the true strengths in case of absolute conflict. Then, limited conflict may actually help parties to settle because it precludes optimism in the long run. This feature introduces a novelty with respect to previous bargaining models with incomplete information because here information transmission is hardly manipulable. The main result is that conflict opens the door to agreement if too optimistic expectations precluded it, but delays it when the informed party uses conflict to improve their bargaining positions.Finally, in chapter four we test empirically the implications of the bargaining model through a duration analysis. We focus on the duration dependence displayed by the hazard rate of real conflicts: If conflict is a learning-persuasion device, this dependence must be positive, that is, the more a conflict lasts the more likely it ends. We perform the analysis with data on colonial and imperial wars from 1816 to 1988: The results obtained give support to the increasing hazard hypothesis.