On s'intéresse aux jeux infiniment répétés avec observation imparfaite et privée, joués dans des réseaux. Différents réseaux peuvent modéliser les structures d'interaction, d'observation ou de communication d'un jeu répété. La communication est gratuite, et peut être privée ou publique. Différents modèles de jeux répétés sont étudiés, en fonction des réseaux considérés, de la nature de la communication, et du concept d'équilibre étudié. L'objectif principal de cette thèse est d'établir des conditions nécessaires et suffisantes sur les réseaux considérés afin d'obtenir un folk théorème / I study infinitely repeated games with imperfect private monitoring played on networks. Different networks may represent the structures of interaction, of monitoring, and of communication of the repeated game. Communication is costless, and may be either private or public. I study different models of repeated games, depending on the networks considered, on the nature of communication, and on the solution concept. The aim of this thesis is to establish necessary and sufficient conditions on the networks for a folk theorem to hold

We propose a new classification for multi-agent learning algorithms, with each league of players characterized by both their possible strategies and possible beliefs. Using this classification, we review the optimality of existing algorithms and discuss some insights that can be gained. We propose an incremental improvement to the existing algorithms that seems to achieve average payoffs that are at least the Nash equilibrium payoffs in the long-run against fair opponents. / Singapore-MIT Alliance (SMA)

[pt] Pesquisar preços pode ser custoso para os consumidores. Este artigo investiga os efeitos de busca na formação de conluio por parte das firmas. Para identificar tais efeitos, constrói-se um jogo repetido no qual os consumidores pesquisam preços seqüencialmente e as firmas competem por preços no jogo estático. Claramente, identificam-se dois efeitos distintos, por um lado, mais busca, i.e. mais consumidores pesquisando preços ou um menor custo de busca, facilita a formação de conluio, pois as firmas sustentam punições críveis mais severas. Por outro lado, mais busca dificulta a formação de conluio à medida que os desvios do conluio se tornam mais lucrativos. / [en] This paper investigates, through a theoretical approach, search effects on collusion. In order to identify these effects, we consider an infinitely repeated game; in the stage game, consumers search for prices sequentially and firms set price simultaneously. We clearly identify two different search effects on collusion; on the one hand, it facilitates collusion as the punishment payoff is lower. On the other hand, it makes collusion more difficult, since deviations are more profitable.

<p>In many economic settings agents behave strategically. Understanding and, sometimes regulating, that behavior is often crucial to enhance the efficiency with which scarce resources are allocated. A peculiar feature of economics is that cooperation among agents sometimes boosts efficiency, and sometimes hinders it. Social dilemmas, highly ubiquitous in economics, are situations in which cooperation boosts efficiency. Highly concentrated markets where a few firms operate, are situations in which cooperation (also known as collusion) among firms hinders efficiency. In such markets competition, rather than cooperation, boosts efficiency. In this dissertation, I study how uncertainty affects cooperation in social dilemmas, and how the presence of cooperative firms affects competition in concentrated markets.</p> <p><br></p> <p>Both of the settings I study in this dissertation (social dilemmas with noisy payoffs and duopsony with endogenous location and pricing strategy) face a similar challenge. Their complexity compromises the tractability of conventional equilibrium concepts. In other words, Nash equilibria do not exist, or there is a multiplicity of equilibria. This, in turn, precludes comparative static analyses characterizing the effect of exogenous market forces (uncertainty and firm ownership structure) on market and welfare outcomes.</p> <p><br></p> <p>I address this key challenge through a combination of genetic algorithms and laboratory experiments. A genetic algorithm consists of a selection process that identifies strategies that perform better than others, on average. Therefore, surviving strategies constitute, in a sense, average best responses. More than one strategy may survive. This happens when none of the surviving strategies is weakly dominated by the other surviving strategies. An equilibrium is a combination of surviving strategies. In this context, a comparative static analysis consists of the change in equilibrium (combination of surviving strategies) due to a change in exogenous forces. These comparative static analyses generate testable hypotheses. In Essays 1 and 2, I implement laboratory experiments to test these hypotheses.</p> <p><br></p> <p>In Essay 1, I compare infinitely repeated social dilemmas with deterministic and noisy payoffs. I test whether noise in payoffs (where noisy payoffs are generated by a random shock and are uncorrelated amongst agents), which introduces imperfect monitoring, affects cooperation. Experimental evidence shows that imperfect monitoring reduces cooperation because it hinders agents’ ability to threaten defectors with a reciprocal defection. Therefore, noise reduces efficiency by unraveling cooperation in social dilemmas. In Essay 2, I study whether correlation among agents’ noisy payoffs strengthens monitoring and restores cooperation. Experimental evidence shows that stronger (though still imperfect) monitoring due to correlation helps cooperation if and only if agents are prone to cooperate in the initial rounds of the repeated game. Therefore, correlation among shocks affecting agents’ payoffs may or may not increase efficiency depending on the type of players participating in the social dilemma.</p> <p><br></p> <p>Finally, in Essay 3, I use a genetic algorithm to generate comparative statics characterizing the effect of a cooperative firm on market equilibrium and efficiency in a spatial duoposony. A Nash equilibrium in this setting does not exist when location, price, and the degree of spatial price discrimination are all endogenous in the seminal Hotelling’s model. I use a genetic algorithm to identify a stable equilibrium in this setting. I find that a cooperative firm increases efficiency. But, counterintuitively, it does so when the cooperative does not directly compete with the privately owned firm. This is because the cooperative maximizes market share when its procurement region does not overlap with the privately owned firm’s procurement region.</p> <p><br></p>

This dissertation consists of four self-contained essays primarily concerned with incorporating the objectives of real world top managers, as revealed by the available empirical evidence, in supergame-theoretic analyses of long-term competition between oligopolistic firms. The first essay, "Ownership, Control, and Collusion", considers how the separation between ownership and control affects firms' competitive attitudes when top managers have the preference for smooth profit streams revealed by the evidence on "income smoothing" and when managerial compensation has the low pay-performance sensitivity found in many empirical studies. In a similar fashion, the second essay, "Stock-Related Compensation and Product-Market Competition", deals with the effects of the apparently more aggressive managerial incentives linked to stock price (e.g. stock options), which have become increasingly common in the U.S., on long-term oligopolistic competition. In the third paper, "Debt as a (Credible) Collusive Device", shareholders’ commitments to reduce conflicts with debtholders by choosing a top manager with a highly valuable reputation or with "conservative" incentives are considered. These forms of commitment have been shown to reduce the (agency) cost of debt finance; this paper characterizes their effects on the relation between firms' capital structure and product market competition. The fourth paper, "Multimarket Contact, Concavity, and Collusion", addresses the relation between multimarket contact and firms’ ability to sustain collusive behavior in repeated oligopolies. It explores how this relation is affected by the strict concavity of firms’ objective function induced by managerial objectives and by other features of reality, discusses the effects of conglomeration and horizontal mergers, and extends the results to non-oligopolistic supergames. / <p>Diss. Stockholm : Handelshögskolan, 1999</p>

A cyber-security problem is a conflict-resolution scenario that typically consists of a security system and at least two decision makers (e.g. attacker and defender) that can each have competing objectives. In this thesis, we are interested in cyber-security problems where one decision maker has superior or better information. Game theory is a well-established mathematical tool that can be used to analyze such problems and will be our tool of choice. In particular, we will formulate cyber-security problems as stochastic games with asymmetric information, where game-theoretic methods can then be applied to the problems to derive optimal policies for each decision maker. A severe limitation of considering optimal policies is that these policies are computationally prohibitive. We address the complexity issues by introducing methods, based on the ideas of model predictive control, to compute suboptimal polices. Specifically, we first prove that the methods generate suboptimal policies that have tight performance bounds. We then show that the suboptimal polices can be computed by solving a linear program online, and the complexity of the linear program remains constant with respect to the game length. Finally, we demonstrate how the suboptimal policy methods can be applied to cyber-security problems to reduce the computational complexity of forecasting cyber-attacks.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-10-23T17:05:10Z No. of bitstreams: 1 renanmottagoulart.pdf: 506891 bytes, checksum: 01d7b3b82d2bc0af0d295fc75de17b91 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-11-09T13:52:19Z (GMT) No. of bitstreams: 1 renanmottagoulart.pdf: 506891 bytes, checksum: 01d7b3b82d2bc0af0d295fc75de17b91 (MD5) / Made available in DSpace on 2017-11-09T13:52:19Z (GMT). No. of bitstreams: 1 renanmottagoulart.pdf: 506891 bytes, checksum: 01d7b3b82d2bc0af0d295fc75de17b91 (MD5) Previous issue date: 2017-09-01 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Jogos de repetição é um ramo de Teoria dos Jogos, em que um jogo é jogado repetidas vezes pelos jogadores. Neste cenário, assume-se que os jogadores nem sempre jogam de modo ótimo ou podem estar dispostos, se possível, a colaborar. Neste contexto é possível um jogador analisar o comportamento dos oponentes para encontrar padrões. Estes padrões podem ser usados para aumentar o lucro obtido pelo jogador ou detectar se o oponente está disposto a realizar uma colaboração mutualmente benéfica. Nesta dissertação é proposto um novo algoritmo baseado em kernel de similaridade capaz de prever as ações de jogadores em jogos de repetição. A predição não se limita a ação do próximo round, podendo prever as ações de uma sequência finita de rounds consecutivos. O algoritmo consegue se adaptar rapidamente caso os outros jogadores mudem suas estratégias durante o jogo. É mostrado empiricamente que o algoritmo proposto obtém resultados superiores ao estado da arte atual. / Repeated games is a branch of game theory, where a game can be played several times by the players involved. In this setting, it is assumed that the players do not always play the optimal strategy or that they may be willing to collaborate. In this context it is possible for a player to analyze the opponent’s behaviour to find patters. These patterns can be used to maximize the player’s profit or to detect if the opponent is willing to collaborate. On this dissertation it is proposed a new algorithm based on similarity kernel capable of predicting the opponent’s actions on repeated games. The prediction is not limited to the next round’s action, being able to predict actions on a finite sequence of rounds. It is able to adapt rapidly if the opponents change their strategies during the course of a game. It is shown empirically that the proposed algorithm achieves better results than the current state of the art.

Cette thèse étudie des propriétés limites de problèmes de contrôle optimal (un joueur, en temps continu) et de jeux répétés à somme nulle (à deux joueurs, en temps discret) avec horizon tendant vers l'infini. Plus précisément, nous étudions la convergence de la fonction valeur lorsque la durée du problème de contrôle ou la répétition du jeu tend vers l'infini (analyse asymptotique), et l'existence de stratégies robustes, i.e. des stratégies ԑ-optimales pour guarantir la valeur limite dans tous les problèmes de contrôle de durée suffisamment longue ou dans tous les jeux répétés de répétition suffisamment large (analyse uniforme). La partie sur le contrôle optimal est composée de trois chapitres. Le chapitre 2 est un article de présentation de la littérature récente sur les propriétés à long terme dans divers modèles d'optimisation dynamique. Dans les deux chapitres suivants, nous nous concentrons sur les problèmes de contrôle optimal où le coȗt de la trajectoire est évalué par une mesure de probabilité générale sur R_+, au lieu de la moyenne de T-horizon (moyenne de Cesàro) ou de la λ-escompté (moyenne d'Abel). Dans le chapitre 3, nous introduisons une condition de régularité asymptotique pour une suite de mesures de probabilité sur R_+ induisant un horizon tendant vers l'infini (en particulier, T tendant vers l'infini ou λ tendant vers zéro). Nous montrons que pour toute suite d'évaluations satisfaisant cette condition, la suite associée des valeurs du problème de contrôle converge uniformément si et seulement si cette suite est totalement bornée pour la norme uniforme. On en déduit que pour des problèmes de contrôle définis sur un domaine invariant compact et vérifiant une certaine condition de non-expansivité, la fonction valeur définie par une mesure de probabilité générale converge quand l'évaluation devient suffisamment régulière. En outre, nous prouvons dans le chapitre 4 que sous les mȇmes conditions de compacité et de non-expansivité, il existe des contrôles ԑ-optimaux pour tous les problèmes où le coȗt de la trajectoire est évalués par une mesure de probailité suffisamment régulières. La partie sur les jeux répétés se compose de deux chapitres. Le chapitre 5 est consacré à l'étude d'une sous-classe de jeux absorbants à information incomplète d'un côté. Le modèle que nous considérons est une généralisation du Big match à information incomplète d'un côté introduit par Sorin (1984). Nous démontrons l'existence de la valeur limite, du Maxmin, du Minmax, et l'égalité du Maxmin et de la valeur limite. Dans le chapitre 6, nous établissons plusieurs résultats concernant des jeux récursifs. Nous considérons d'abord les jeux récursifs avec un espace dénombrable d'états et prouvons que si la famille des fonctions valeur des jeux à n étapes est totalement bornée pour la norme uniforme, alors la valeur uniforme existe. En particulier, la convergence uniforme des valeurs des jeux à n étapes implique la convergence uniforme des valeurs des jeux escomptés. à l'aide d'un résultat dans Rosenberg et Vieille (2000), on en déduit un théorème taubérien uniforme pour les jeux récursifs. Deuxièmement, nous appliquons le résultat d'existence de la valeur uniforme à une classe des modèles général de jeux répétés et nous prouvons que la valeur limite et le Maxmin existent et sont égaux. Ces jeux répétés sont des jeux récursifs avec signaux où le joueur 1 peut toujours déduire le signal du joueur 2 de son propre signal. / This dissertation studies limit properties in optimal control problems (one-player, in continuous time) and in zero-sum repeated games (two-player, in discrete time) with large horizons. More precisely, we investigate the convergence of the value function when the duration of the control problem or the repetition of the game tends to infinity (the asymptotic analysis), and the existence of robust strategies, i.e. ԑ-optimal strategies to guarantee the limit value in all control problems with sufficiently long durations or in all repeated games with sufficiently large repetitions (the uniform analysis). The part on optimal control is composed of three chapters. Chapter 2 is a survey article on recent literature of long-term properties in various models of dynamic optimization. In the following two chapters, we focus on optimal control problems where the running cost is evaluated by a general probability measure, instead of the usual T-horizon average (Cesàro mean) or the λ-discount (Abel mean). In Chapter 3, we introduce an asymptotic regularity condition for a sequence of probability measures on positive real numbers which induces a horizon tending to infinity (in particular T tending to infinity or λ tending to zero) for the control problem. We prove that for any sequence of evaluations satisfying this condition, the associated sequence of value function of the control problem converges uniformly if and only if this sequence is totally bounded for the uniform norm. We deduce that for control problems defined on a compact invariant domain and satisfying some non expansive condition, the value function defined by a general probability measure converges as the evaluation becomes sufficiently regular. Further, we prove in Chapter 4 that under the same compact and non expansive conditions, there exist ԑ-optimal controls for all problems where the running cost is evaluated by a sufficiently regular probability measure. The part on repeated games consists of two chapters. Chapter 5 is devoted to the study of a subclass of absorbing games with one-sided incomplete information. The model we consider is a generalization of Big match with one-sided incomplete information introduced by Sorin (1984). We prove the existence of the limit value, Maxmin, Minmax, and that Maxmin is equal to the limit value. In Chapter 6, we establish several results for recursive games. We first consider recursive games with a countable state space and prove that if the family of n-stage value functions is totally bounded for the uniform norm, then the uniform value exists. In particular, the uniform convergence of n-stage values implies the uniform convergence of λ-discounted values. Combined with a result in Rosenberg and Vieille (2000), we deduce a uniform Tauberian theorem for recursive games. Second, we use the existence result of uniform value to a class of the generalized models of repeated games and prove that both the limit value and Maxmin exist and are equal. This class of repeated games are recursive games with signals where player 1 can always deduce the signal of player 2 from his own along the play.

No description available.

Les jeux stochastiques à somme nulle possèdent une structure récursive qui s'exprime dans leur opérateur de programmation dynamique, appelé opérateur de Shapley. Ce dernier permet d'étudier le comportement asymptotique de la moyenne des paiements par unité de temps. En particulier, le paiement moyen existe et ne dépend pas de l'état initial si l'équation ergodique - une équation non-linéaire aux valeurs propres faisant intervenir l'opérateur de Shapley - admet une solution. Comprendre sous quelles conditions cette équation admet une solution est un problème central de la théorie de Perron-Frobenius non-linéaire, et constitue le principal thème d'étude de cette thèse. Diverses classes connues d'opérateur de Shapley peuvent être caractérisées par des propriétés basées entièrement sur la relation d'ordre ou la structure métrique de l'espace. Nous étendons tout d'abord cette caractérisation aux opérateurs de Shapley "sans paiements", qui proviennent de jeux sans paiements instantanés. Pour cela, nous établissons une expression sous forme minimax des fonctions homogènes de degré un et non-expansives par rapport à une norme faible de Minkowski. Nous nous intéressons ensuite au problème de savoir si l'équation ergodique a une solution pour toute perturbation additive des paiements, problème qui étend la notion d'ergodicité des chaînes de Markov. Quand les paiements sont bornés, cette propriété d'"ergodicité" est caractérisée par l'unicité, à une constante additive près, du point fixe d'un opérateur de Shapley sans paiement. Nous donnons une solution combinatoire s'exprimant au moyen d'hypergraphes à ce problème, ainsi qu'à des problèmes voisins d'existence de points fixes. Puis, nous en déduisons des résultats de complexité. En utilisant la théorie des opérateurs accrétifs, nous généralisons ensuite la condition d'hypergraphes à tous types d'opérateurs de Shapley, y compris ceux provenant de jeux dont les paiements ne sont pas bornés. Dans un troisième temps, nous considérons le problème de l'unicité, à une constante additive près, du vecteur propre. Nous montrons d'abord que l'unicité a lieu pour une perturbation générique des paiements. Puis, dans le cadre des jeux à information parfaite avec un nombre fini d'actions, nous précisons la nature géométrique de l'ensemble des perturbations où se produit l'unicité. Nous en déduisons un schéma de perturbations qui permet de résoudre les instances dégénérées pour l'itération sur les politiques. / Zero-sum stochastic games have a recursive structure encompassed in their dynamic programming operator, so-called Shapley operator. The latter is a useful tool to study the asymptotic behavior of the average payoff per time unit. Particularly, the mean payoff exists and is independent of the initial state as soon as the ergodic equation - a nonlinear eigenvalue equation involving the Shapley operator - has a solution. The solvability of the latter equation in finite dimension is a central question in nonlinear Perron-Frobenius theory, and the main focus of the present thesis. Several known classes of Shapley operators can be characterized by properties based entirely on the order structure or the metric structure of the space. We first extend this characterization to "payment-free" Shapley operators, that is, operators arising from games without stage payments. This is derived from a general minimax formula for functions homogeneous of degree one and nonexpansive with respect to a given weak Minkowski norm. Next, we address the problem of the solvability of the ergodic equation for all additive perturbations of the payment function. This problem extends the notion of ergodicity for finite Markov chains. With bounded payment function, this "ergodicity" property is characterized by the uniqueness, up to the addition by a constant, of the fixed point of a payment-free Shapley operator. We give a combinatorial solution in terms of hypergraphs to this problem, as well as other related problems of fixed-point existence, and we infer complexity results. Then, we use the theory of accretive operators to generalize the hypergraph condition to all Shapley operators, including ones for which the payment function is not bounded. Finally, we consider the problem of uniqueness, up to the addition by a constant, of the nonlinear eigenvector. We first show that uniqueness holds for a generic additive perturbation of the payments. Then, in the framework of perfect information and finite action spaces, we provide an additional geometric description of the perturbations for which uniqueness occurs. As an application, we obtain a perturbation scheme allowing one to solve degenerate instances of stochastic games by policy iteration.