This dissertation is concerned with the characterization, existence and computation of equilibrium solutions in a two-stage model of interacting producers. The model represents an industry involved with two major stages of production. On the production side there exist some (upstream) firms which perform the first stage of production and manufacture a semi-finished product, and there exist some other (downstream) firms which perform the second stage of production and convert this semi-finished product to a final commodity. There also exist some (vertically integrated) firms which handle the entire production process themselves. In this research, the final commodity market is an oligopoly which may exhibit one of two possible behavioral patterns: follower-follower or multiple leader-follower. In both cases, the downstream firms are assumed to be price takers in purchasing the intermediate product. For the upstream stage, we consider two situations: a Cournot oligopoly or a perfectly competitive market. An equilibrium analysis of the model is conducted with output quantities as decision variables. The defined equilibrium solutions employ an inverse derived demand function for the semi-finished product. This function is derived and characterized through the use of mathematical programming problems which represent the equilibrating process in the final commodity market. Based on this analysis, we provide sufficient conditions for the existence (and uniqueness) of an equilibrium solution, under various market assumptions. These conditions are formulated in terms of properties of the cost functions and the final product demand function. Next, we propose some computational techniques for determining an equilibrium solution. The algorithms presented herein are based on structural properties of the inverse derived demand function and its local approximation. Both convex as well as nonconvex cases are considered. We also investigate in detail the effects of various integrations among the producers on firms' profits, and on industry outputs and prices at equilibrium. This sensitivity analysis provides rich information and insights for industrial analysts and policy makers into how the foregoing quantities are effected by mergers and collusions and the entry or exit of various types of firms, as well as by differences in market behavior. / Ph. D.

Les travaux de cette thèse s'inscrivent tous dans la thématique " traitement du signal pour les réseaux de communications distribués ". Le réseau est dit distribué au sens de la décision. Dans ce cadre, le problème générique et important que nous avons approfondi est le suivant. Comment un terminal, qui a accès à plusieurs canaux de communications, doit-il répartir (de manière autonome) sa puissance d'émission entre ses canaux et l'adapter dans le temps en fonction de la variabilité des conditions de communications ? C'est le problème de l'allocation de ressources adaptative et distribuée. Nous avons développé 4 axes de travail qui ont tous conduits à des réponses originales à ce problème ; la forte corrélation entre ces axes est expliquée dans le manuscrit de thèse. Le premier axe a été l'alignement opportuniste d'interférence. Un des scénarios de référence est le cas où deux couples émetteur-récepteur communiquent en interférant (sur la même bande, en même temps, au même endroit, ...), où les 4 terminaux sont équipés de plusieurs antennes et où un émetteur est contraint de ne pas (ou peu) interférer sur l'autre (canal à interférence dit MIMO). Nous avons conçu une technique d'émission de signal multi-antennaire qui exploite l'observation-clé suivante et jamais exploitée auparavant: même lorsqu'un émetteur est égoïste au sens de ses performances individuelles, celui-ci laisse des ressources spatiales (dans le bon espace de signal et que nous avons identifié) vacantes pour l'autre émetteur. L'apport en performances en termes de débit par rapport aux meilleurs algorithmes existants a été quantifié grâce à la théorie des matrices aléatoires et des simulations Monte Carlo. Ces résultats sont particulièrement importants pour le scénario de la radio cognitive en milieu dense. Dans un second temps, nous avons supposé que tous les émetteurs d'un réseau sont libres d'utiliser leurs ressources de manière égoïste. Les ressources sont données ici par les canaux fréquentiels et la métrique individuelle de performance est le débit. Ce problème peut être modélisé par un jeu dont les joueurs sont les émetteurs. Une de nos contributions a été de montrer que ce jeu est un jeu de potentiel, ce qui est fondamental pour la convergence des algorithmes distribués et l'existence d'équilibre de Nash. De plus, nous avons montré l'existence d'un paradoxe de Braess : si l'espace d'optimisation d'un joueur grandit, les performances individuelles et globales peuvent s'en trouver réduites. Cette conclusion a une conséquence pratique immédiate : il peut y a voir intérêt de restreindre le nombre de canaux fréquentiels utilisables dans un réseau à interférence distribué. Dans le jeu précédent, nous avions constaté que les algorithmes distribués d'allocation de ressources (les algorithmes d'apprentissage par renforcement typiquement) demandent un grand nombre d'itérations pour converger vers un état stable tel qu'un équilibre de Nash. Nous avons ainsi proposé un nouveau concept de solution d'un jeu, à savoir l'équilibre de satisfaction ; les joueurs ne modifient pas leur action, même si celle-ci ne maximise pas leur gain, pourvu qu'un niveau minimal de performance soit atteint. Nous avons alors développé une méthodologie d'étude de cette solution (existence, unicité, convergence, ...). Une de nos contributions a aussi été de donner des algorithmes d'apprentissage qui convergent vers cette solution en un temps fini (et même court génériquement). De nombreux résultats numériques réalisés dans des scénarios imposés par Orange ont confirmé la pertinence de cette nouvelle approche. Le quatrième axe de travail a été la conception de nouveaux algorithmes d'apprentissage qui convergent vers des solutions de type équilibre logit, epsilon-équilibre ou équilibre de Nash. Notre apport a été de montrer comment modifier les algorithmes existants pour que ceux-ci évitent les phénomènes de cycles et convergent vers un équilibre présélectionné au départ de la dynamique. Une idée importante a été d'introduire une dynamique d'apprentissage de la fonction métrique de performances en couplage avec la dynamique principale qui régit l'évolution de la distribution de probabilité sur les actions possibles d'un joueur. Le cadre de ces travaux est parfaitement réaliste d'un point de vue informatif au niveau des terminaux en pratique. Il est montré une voie possible pour améliorer l'efficacité des points de convergence, ce qui constitue un problème encore ouvert dans ce domaine.

The goal of this thesis is to use and advance the techniques developed in the field of exact and approximation algorithms for many of the problems arising in the context of the Internet. We will formalize the method of dual fitting and the idea of factor-revealing LP. We use this combination to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61 respectively. We also provide the first polynomial time algorithm for the linear version of a market equilibrium model defined by Irving Fisher in 1891. Our algorithm is modeled after Kuhn's primal-dual algorithm for bipartite matching. We also study the connectivity properties of the Internet graph and its impact on its structure. In particular, we consider the model of growth with preferential attachment for modeling the graph of the Internet and prove that under some reasonable assumptions, this graph has a constant conductance.

Multi-agent reinforcement learning (MARL) poses the same planning problem as traditional reinforcement learning (RL): What actions over time should an agent take in order to maximize its rewards? MARL tackles a challenging set of problems that can be better understood by modeling them as having a relatively simple environment but with complex dynamics attributed to the presence of other agents who are also attempting to maximize their rewards. A great wealth of research has developed around specific subsets of this problem, most notably when the rewards for each agent are either the same or directly opposite each other. However, there has been relatively little progress made for the general problem. This thesis address this lack. Our goal is to tackle the most general, least restrictive class of MARL problems. These are general-sum, non-deterministic, infinite horizon, multi-agent sequential decision problems of complete and incomplete information. Towards this goal, we engage in two complementary endeavors: the creation of tractable models and the construction of efficient algorithms to solve these models. We tackle three well known models: stochastic games, decentralized partially observable Markov decision problems, and partially observable stochastic games. We also present a new fourth model, Markov games of incomplete information, to help solve the partially observable models. For stochastic games and decentralized partially observable Markov decision problems, we develop novel and efficient value iteration algorithms to solve for game theoretic solutions. We empirically evaluate these algorithms on a range of problems, including well known benchmarks and show that our value iteration algorithms perform better than current policy iteration algorithms. Finally, we argue that our approach is easily extendable to new models and solution concepts, thus providing a foundation for a new class of multi-agent value iteration algorithms.

This dissertation describes the development of a game-based methodology that facilitates the exploration and selection of research and development (R&D) projects under uncertain competitive scenarios. The proposed method provides an approach that analyzes competitor positioning and formulates response strategies to forecast the impact of technical design choices on a project's market performance. A critical decision in the conceptual design phase of propulsion systems is the selection of the best architecture, centerline, core size, and technology portfolio. A key objective of this research is to examine how firm characteristics such as their relative differences in completing R&D projects, differences in the degree of substitutability between different project types, and first/second-mover advantages affect their product development strategies. Several quantitative methods are investigated that analyze business and engineering strategies concurrently. In particular, formulations based on the well-established mathematical field of game theory are introduced to obtain insights into the project selection problem. The use of game theory is explored in this research as a method to assist the selection process of R&D projects in the presence of imperfect market information. The proposed methodology focuses on two influential factors: the schedule uncertainty of project completion times and the uncertainty associated with competitive reactions. A normal-form matrix is created to enumerate players, their moves and payoffs, and to formulate a process by which an optimal decision can be achieved. The non-cooperative model is tested using the concept of a Nash equilibrium to identify potential strategies that are robust to uncertain market fluctuations (e.g: uncertainty in airline demand, airframe requirements and competitor positioning). A first/second-mover advantage parameter is used as a scenario dial to adjust market rewards and firms' payoffs. The methodology is applied to a commercial aircraft engine selection study where engine firms must select an optimal engine project for development. An engine modeling and simulation framework is developed to generate a broad engine project portfolio. The proposed study demonstrates that within a technical design environment, a rational and analytical means of modeling project development strategies is beneficial in high market risk situations.

Vaccination has been used to control the spread of infectious diseases for centuries with widespread success. Deterministic models studying the spread of infectious disease often use the assumption of mass vaccination; however, these models do not allow for the inclusion of human behaviour. Since current vaccination campaigns are voluntary in nature, it is important to extend the study of infectious disease models to include the effects of human behaviour. To model the effects of vaccination behaviour on the spread of influenza, we examine a series of models in which individuals vaccinate according to memory or individual decision-making processes based upon self-interest. Allowing individuals to vaccinate proportionally to an exponentially decaying memory function of disease prevalence, we demonstrate the existence of a Hopf bifurcation for short memory spans. Using a game-theoretic influenza model, we determine that lowering the perceived vaccine risk may be insufficient to increase coverage to established target levels. Utilizing evolutionary game theory, we examine models with imitation dynamics both with and without a decaying memory function and show that, under certain conditions, periodic dynamics occur without seasonal forcing. Our results suggest that maintaining diseases at low prevalence with voluntary vaccination campaigns could lead to subsequent epidemics following the free-rider dilemma and that future research in disease control reliant on individual-based decision-making need to include the effects of human behaviour.

This dissertation studies econometric analysis of game-theoretic models. I develop novel empirical models and methodologies to facilitate robust and computationally tractable econometric analysis. In Chapter 1, I develop an empirical model for analyzing stable outcomes in the presence of incomplete information. Empirically, many strategic settings are characterized by stable outcomes in which players’ decisions are publicly observed, yet no player takes the opportunity to deviate. To analyze such situations, I build an empirical framework by introducing a novel solution concept that I call Bayes stable equilibrium. The framework allows the researcher to be agnostic about players’ information and the equilibrium selection rule. Furthermore, I show that the Bayes stable equilibrium identified set is always weakly tighter than the Bayes correlated equilibrium identified set; numerical examples show that the shrinkage can be substantial. I propose computationally tractable approaches for estimation and inference and apply the framework to study the strategic entry decisions of McDonald’s and Burger King in the US. In Chapter 2, I study identification and estimation of a class of dynamic games when the underlying information structure is unknown to the researcher. I introduce Markov correlated equilibrium, a dynamic analog of Bayes correlated equilibrium studied in Bergemann and Morris (2016), and show that the set of Markov correlated equilibrium predictions coincides with the set of Markov perfect equilibrium predictions that can arise when the players might observe more signals than assumed by the analyst. I propose an econometric approach for estimating dynamic games with weak assumption on players’ information using Markov correlated equilibrium. I also propose multiple computational strategies to deal with the non-convexities that arise in dynamic environments. In Chapter 3, I propose an extremely fast and simple approach to estimating static discrete games of complete information under pure strategy Nash equilibrium and no assumptions on the equilibrium selection rule. I characterize an identified set of parameters using a set of inequalities that are expressed in terms of closed-form multinomial logit probabilities. The key simplifications arise from using a subset of all identifying restrictions that are particularly easy to handle. Under standard assumptions, the identified set is convex and its projections can be obtained via convex programs. Numerical examples show that the identified set is quite tight. I also propose a simple approach to construct confidence sets whose projections can be obtained via convex programs. I demonstrate the usefulness of the approach using real-world data.

Satisficing game theory is an alternative to traditional non-cooperative game theory which offers increased flexibility in modeling players' social interactions. However, satisficing players with conflicting attitudes may implement dysfunctional behaviors, leading to poor performance. In this thesis, we present two attempts to "bridge the gap" between satisficing and non-cooperative game theory. First, we present an evolutionary method by which players adapt their attitudes to increase raw payoff, allowing players to overcome dysfunction. We extend the Nash equilibrium concept to satisficing games, showing that the evolutionary method presented leads the players toward an equilibrium in their attitudes. Second, we introduce the conditional utility functions of satisficing theory into an otherwise traditional non-cooperative framework. While the conditional structure allows increased social flexibility in the players' behaviors, players maximize individual utility in the traditional sense, allowing us to apply the Nash equilibrium. We find that, by adjusting players' attitudes, we may alter the Nash equilibria that result.

No description available.

International Telemetering Conference Proceedings / October 18-21, 2004 / Town & Country Resort, San Diego, California / An Ad hoc network with unicasting is considered, in which each node has an M element antenna array. Transmission from node l(i) to i is quasi-synchronous, so that code acquisition is not required. Space-Time (S-T) waveforms are transmitted with temporal dimension Ns Nyquist samples. An adaptive, distributed S-T waveform design algorithm is developed, which maintains QoS while attempting to minimize transmit power. The resulting Iterative Minimum Mean-Square Error{Time Reversal algorithm (IMMSE-TR) sets the transmit S-T vector at node i to the conjugate time-reverse of the linear MMSE S-T detector. It is shown that IMMSE-TR corresponds to a noncooperative game which attempts to minimize transmit power while paying an interference tax. Simulation results are presented demonstrating high power efficiencies for heavily-loaded systems.