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

Optical signal-to-noise ratio (OSNR) is considered as the dominant performance parameter at the physical layer in optical networks. This thesis is interested in control and optimization of channel OSNR by using optimization and game-theoretic approaches, incorporating two physical constraints: the link capacity constraint and the channel OSNR target. To start, we study OSNR optimization problems with link capacity constraints in single point-to-point fiber links via two approaches. We first present a framework of a Nash game between channels towards optimizing individual channel OSNR. The link capacity constraint is imposed as a penalty term to each cost function. The selfish behavior in a Nash game degrades the system performance and leads to the inefficiency of Nash equilibria. From the system point of view, we formulate a system optimization problem with the objectives of achieving an OSNR target for each channel while satisfying the link capacity constraint. As an alternative to study the efficiency of Nash equilibria, we use the system framework to investigate the effects of parameters in cost functions in the game-theoretic framework. Then extensions to multi-link and mesh topologies are carried out. We propose a partition approach by using the flexibility of channel power adjustment at optical switches. The multi-link structure is partitioned into stages with each stage being a single sink. By fully using the flexibility, a more natural partition approach is applied to mesh topologies where each stage is a single link. The closed loop in mesh topologies can be unfolded by selecting a starting link. Thus instead of maximization of channel OSNR from end to end, we consider minimization of channel OSNR degradation between stages. We formulate a partitioned Nash game which is composed of ladder-nested stage Nash games. Distributed algorithms towards the computation of a Nash equilibrium solution are developed for all different game frameworks. Simulations and experimental implementations provide results to validate the applicability of theoretical results.

Optical signal-to-noise ratio (OSNR) is considered as the dominant performance parameter at the physical layer in optical networks. This thesis is interested in control and optimization of channel OSNR by using optimization and game-theoretic approaches, incorporating two physical constraints: the link capacity constraint and the channel OSNR target. To start, we study OSNR optimization problems with link capacity constraints in single point-to-point fiber links via two approaches. We first present a framework of a Nash game between channels towards optimizing individual channel OSNR. The link capacity constraint is imposed as a penalty term to each cost function. The selfish behavior in a Nash game degrades the system performance and leads to the inefficiency of Nash equilibria. From the system point of view, we formulate a system optimization problem with the objectives of achieving an OSNR target for each channel while satisfying the link capacity constraint. As an alternative to study the efficiency of Nash equilibria, we use the system framework to investigate the effects of parameters in cost functions in the game-theoretic framework. Then extensions to multi-link and mesh topologies are carried out. We propose a partition approach by using the flexibility of channel power adjustment at optical switches. The multi-link structure is partitioned into stages with each stage being a single sink. By fully using the flexibility, a more natural partition approach is applied to mesh topologies where each stage is a single link. The closed loop in mesh topologies can be unfolded by selecting a starting link. Thus instead of maximization of channel OSNR from end to end, we consider minimization of channel OSNR degradation between stages. We formulate a partitioned Nash game which is composed of ladder-nested stage Nash games. Distributed algorithms towards the computation of a Nash equilibrium solution are developed for all different game frameworks. Simulations and experimental implementations provide results to validate the applicability of theoretical results.

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

En esta tesis se analizan tres mecanismos de subasta distintos, todos ellos bajo el supuesto de valoraciones privadas e independientes.El primer mecanismo que analizamos es una subasta de múltiples unidades en la que los objetos son vendidos secuencialmente por medio de subastas de precio descendente. La característica que hace a esta subasta diferente de la "estándar", analizada por Weber (1983) es que después de la venta del primer objeto el precio no vuelve a subir, sino que los objetos que quedan son ofrecidos al resto de los compradores al mismo precio. Si los objetos no se venden a ese precio, la subasta continúa dejando que el precio siga descendiendo. Esta subasta se analiza en dos contextos: con un modelo de valoraciones continuas y con uno de valoraciones discretas. Se demuestra que si existe un equilibrio simétrico con pujas monótonas, el resultado de la subasta es ineficiente con probabilidad positiva. Aplicando el teorema de equivalencia de rentas se concluye que la subasta no maximiza los beneficios esperados del vendedor. Para poder comparar los precios medios y las varianzas analizamos un modelo de valoraciones discretas. Demostramos que los precios esperados son menores en nuestra subasta y que también lo es la varianza de los beneficios del vendedor. Damos un ejemplo de una familia de funciones de utilidad von Neumann- Morgenstern tal que la utilidad esperada del vendedor es mayor en una u otra de las subasta dependiendo de los valores del parámetro a.El segundo mecanismo que analizamos es una subasta asimétrica de primer precio donde la valoración de uno de los postores es conocida. Demostramos que no existe ningún equilibrio en estrategias puras y caracterizamos un equilibrio en estrategias mixtas en el que el postor cuya valoración es conocida randomiza su puja, mientras que los demás postores juegan una estrategia pura (y monótona). El resultado de la subasta es ineficiente con probabilidad positiva y el beneficio esperado del postor cuya valoración es conocida es menor que en una subasta estándar. Sin embargo, no es obvio que los demás postores mejoren su situación: el hecho de que uno de los postores juegue una estrategia mixta tiene el mismo efecto en sus rivales que un precio de reserva aleatorio. Esto puede obligarles a pujar más agresivamente de lo que pujarían en una subasta normal. El efecto en los beneficios del vendedor también es ambiguo. Tomando un ejemplo con la función de distribución uniforme y comparando los beneficios esperados del vendedor y de los compradores en las dos subastas, obtenemos que, en nuestro ejemplo (con 2 y con 3 postores) los beneficios esperados del vendedor son mas altos en la subasta asimétrica que en la normal.Para terminar, hacemos un repaso de la literatura en subastas secuenciales cuando los compradores desean más de una unidad del bien que se subasta, y analizamos una subasta secuencial de primer precio con y sin opción de compra. Para ello usamos el mismo modelo que Black y de Meza (1992) usan para analizar la subasta secuencial de segundo precio. Demostramos que cuando las preferencias son unidimensionales no existe ningún equilibrio monótono y simétrico, lo cual implica que el resultado de la subasta no puede ser eficiente. Cuando se introduce una opción de compra que permita comprar la segunda unidad al mismo precio al que se adquirió la primera, existe un equilibrio en estrategias puras para algunos valores de los parámetros del modelo. En este caso la opción siempre se ejerce, lo cual lleva a una asignación de los bienes diferente que la que resulta en la subasta secuencial de segundo precio. Cuando la valoración por la segunda unidad es aleatoria, las subastas de primer y segundo precio sin opción de compra son equivalentes. Por último, exponemos las dificultades de caracterizar un equilibrio cuando cuando se introduce la opción de compra en este modelo. / In this thesis we analyze three different auction mechanisms, all of them under the private and independent valuations assumption. The first auction we analyze is a multi-unit auction where the objects are sold sequentially by descending-price auctions. The feature that makes this auction different from the "standard" one is that after one object has been sold, the price does not return to a high level, but the remaining objects are offered to the rest of the bidders at the same price. If the objects fail to be sold at that price, the auction is resumed letting the price descend again. We analyze this auction in two different contexts: a continuous valuation model, and a discrete valuation one. We show that if a symmetric, monotone bidding functions equilibrium exists, the outcome of the auction is inefficient with positive probability. Applying the revenue equivalence theorem we conclude that the auction cannot maximize the seller's expected revenue. In order to be able to compare the averages expected prices and variances, we analyze a discrete-valuation model. We show that the average expected prices are lower in our auction, and that so is the variance of the seller's expected revenue. We give an example of a family of von Neumann-Morgenstern utility functions under which the seller's expected utility may be higher in each of the auctions depending on the value of a parameter a.The second mechanism we analyze is an asymmetric first-price auction where the valuation of one of the bidders is common knowledge. We show that no pure strategy equilibrium exists and we characterize a mixed strategy equilibrium in which the bidder whose valuation is common knowledge randomizes his bid while the other bidders play a (monotone) pure strategy. The outcome of the auction is inefficient with positive probability, and the expected profit of the bidder whose valuation is common knowledge is lower than in a standard auction in which her valuation is private knowledge. However, it is not obvious that the other bidders are better off: the fact that one of the bidders plays a mixed strategy has the effect of on the other bidders as a random reserve price bidder. This may force all them to bid more aggressively than they would in the standard auction. The effect on the seller's expected revenue is also ambiguous. In an example with the uniform distribution, we compare the expected profits of seller and buyers in this auction with those in a standard symmetric private valuation model. In our example, with 2 and 3 bidders, the seller's expected revenue is higher in the asymmetric auction than in a standard auction.To finish, we survey the literature on sequential auctions with multi-unit demand, and we analyze a sequential first-price auction with and without a buyer's option. To do it we use the same model that Black and de Meza (1992) used to analyze the secuencial second-price caution. We show that when the preferences are unidimensional, no monotone symmetric pure strategy equilibrium exists, which implies that the outcome of the auction cannot be efficient. When an option to buy the second unit at the price paid for first one is introduced, there exists a pure strategy equilibrium for some values of the parameters of the model. In this case the option is always exercised, leading to a different allocation than that of the sequential second-price auction. When the valuations for the second unit is stochastic, the first-price and second-price auctions without a buyer's option are efficient and revenue equivalent. To finish, we give some insights into the difficulties of solving for an equilibrium when the buyer's option is introduced in this model.

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.

There was a time when the conventional wisdom was that, because economics is a science concerned with complex, naturally occuring systems, laboratory experiments had little to offer economists. But experimental economics has now become a well-established tool that plays an important role in helping game theory bridge the gap between the study of ideally rational behavior modeled in theory and the study of actual "real-world" behavior of agents. Although it has older antecedents, experimental economics is a fairly new line of work, having originiated more or less contemporaneously with game theory. As economist focused on microeconomic models which depend on the preferences of the agents, the fact that these are dificult to observe in natural environments made it increasingly attractive to look to the laboratory to see -in a controlled environment- whether the assumptions made about individuals were descriptive of their behavior. But game theory is the part of economic theory that does not focus solely on the strategic behavior of individuals in economic environments, but also other issues that will be critical in the design of economic institutions, such as how information is distributed, the influence of agents' expectations and beliefs, and the tension between equilibrium and efficiency. Game theory has already achieved important insights into issues sucs as the design of contracts and allocation mechanisms that take into account the sometimes counterintuitive ways in which individual incentives operate in environments with decision makers that have different information and objectives.This thesis is divided into three chapters that present self-contained studies of economic situations where experiments may help game theory to explain field observations. In deriving the results, besides the game theory literature, rigorous statistical and econometric methods are used.

Multiagent learning (MAL) is the study of agents learning while in the presence of other agents who are also learning. As a field, MAL is built upon work done in both artificial intelligence and game theory. Game theory has mostly focused on proving that certain theoretical properties hold for a wide class of learning situations while ignoring computational issues, whereas artificial intelligence has mainly focused on designing practical multiagent learning algorithms for small classes of games. This thesis is concerned with finding a balance between the game-theory and artificial-intelligence approaches. We introduce a new learning algorithm, FRAME, which provably converges to the set of Nash equilibria in self-play, while consulting experts which can greatly improve the convergence rate to the set of equilibria. Even if the experts are not well suited to the learning problem, or are hostile, then FRAME will still provably converge. Our second contribution takes this idea further by allowing agents to consult multiple experts, and dynamically adapting so that the best expert for the given game is consulted. The result is a flexible algorithm capable of dealing with new and unknown games. Experimental results validate our approach.

Multi-hop wireless network are promising techniques in the field of wireless communication. The dynamic topology of the network and the independent selfish participants of the network make it difficult to be modeled by traditional tools. Game theory is one of the most powerful tools for such problems. However, most current works have certain limitations. There has not been widely accepted solution for the problem yet. In this thesis we propose our solutions for the problem of bandwidth sharing in wireless networks. We assume the nodes are rational, selfish but not malicious independent agents in the game. In our model, nodes are trying to send their data to the access point. Some nodes may require others to forward their package to successfully connect to the access point. However, nodes are selfish and do not wish to help others. Therefore it is possible that some nodes may refuse the requirement. In that case, the unpleasant nodes may punish the others by slowing down their traffic, in which case both parties will suffer. Therefore it is non-trivial to find out the Equilibrium for these nodes after the bargain process. What is the proper distribution of resources among these nodes? We propose a solution based on the game theory. Our solution fulfils the goal of fairness and social welfare maximum.