O presente trabalho propõe-se analisar a industrialização do Brasil no contexto de mudanças econômicas e políticas no primeiro governo de Getúlio Vargas, de 1930 até 1945. Na literatura de economia brasileira com relação ao surgimento da indústria no Brasil, duas visões se contrapõem: de um lado, a industrialização como subproduto da intervenção do governo no setor cafeeiro; de outro, a industrialização intencionalmente promovida pelo governo. Com base em uma análise de equilíbrio em um jogo dinâmico de informação imperfeita, é evidenciada a racionalidade da criação de instituições para o desenvolvimento industrial na década de 1930. Este resultado de equilíbrio mostra as mudanças pela qual o Brasil passou a partir da década de 1930, com mudanças da estrutura tributária, educacional, financeira e relações de trabalho, ou seja, essa mudança institucional gerou campo fértil para o surgimento do processo de industrialização que caracterizou o primeiro governo Vargas e também mostra a intencionalidade desse governo, quando se observa a transformação do sistema tributário, de tal modo a ficar imune das oscilações econômicas externas e também as mudanças educacionais, que passou a incentivar o ensino primário, secundário e técnico profissionalizante, medidas essas feitas para atender o novo panorama econômico brasileiro. Outro ponto que corrobora o resultado do equilíbrio de Nash perfeito em subjogos é a perda da importância do setor cafeeiro no período que engloba o século XIX até o final do primeiro governo Vargas, onde as evidências mostram que os cafeicultores tinham, antes e durante a década de 1930, tendências a diversificarem investimentos por conta da perda da renda com o setor cafeicultor. / This study proposes to examine the industrialization of Brazil in the context of economic and political changes in the first government of Getulio Vargas, from 1930 until 1945. In the literature of the Brazilian economy with the coming of industry in Brazil, two visions are in opposition: on one hand, industrialization as a byproduct of government intervention in the coffee sector, on the other, deliberately promoted industrialization by the government. Based on an analysis of equilibrium in a dynamic game of imperfect information, rationality is evident from the creation of institutions for industrial development in the 1930s. The result shows the changes of equilibrium in which Brazil went from the 1930s, with changes in the tax structure, educational, financial and labor relations, that institutional change created fertile ground for the rise of industrialization that characterized the first Vargas government and also shows the intention of this government, when one observes the transformation of the tax system, so be immune to external economic fluctuations and also educational changes, which came to encourage the primary, secondary and technical vocational, measures designed to meet the new economic landscape of Brazil. Another point that confirms the outcome of the Nash equilibrium is perfect in subgame the loss of the importance of the coffee sector in the period that includes the nineteenth century until the end of the first Vargas government, where the evidence shows that farmers had, since the decade of 1930, to diversify investment trends due to the loss of income to the grower industry.

O presente trabalho propõe-se analisar a industrialização do Brasil no contexto de mudanças econômicas e políticas no primeiro governo de Getúlio Vargas, de 1930 até 1945. Na literatura de economia brasileira com relação ao surgimento da indústria no Brasil, duas visões se contrapõem: de um lado, a industrialização como subproduto da intervenção do governo no setor cafeeiro; de outro, a industrialização intencionalmente promovida pelo governo. Com base em uma análise de equilíbrio em um jogo dinâmico de informação imperfeita, é evidenciada a racionalidade da criação de instituições para o desenvolvimento industrial na década de 1930. Este resultado de equilíbrio mostra as mudanças pela qual o Brasil passou a partir da década de 1930, com mudanças da estrutura tributária, educacional, financeira e relações de trabalho, ou seja, essa mudança institucional gerou campo fértil para o surgimento do processo de industrialização que caracterizou o primeiro governo Vargas e também mostra a intencionalidade desse governo, quando se observa a transformação do sistema tributário, de tal modo a ficar imune das oscilações econômicas externas e também as mudanças educacionais, que passou a incentivar o ensino primário, secundário e técnico profissionalizante, medidas essas feitas para atender o novo panorama econômico brasileiro. Outro ponto que corrobora o resultado do equilíbrio de Nash perfeito em subjogos é a perda da importância do setor cafeeiro no período que engloba o século XIX até o final do primeiro governo Vargas, onde as evidências mostram que os cafeicultores tinham, antes e durante a década de 1930, tendências a diversificarem investimentos por conta da perda da renda com o setor cafeicultor. / This study proposes to examine the industrialization of Brazil in the context of economic and political changes in the first government of Getulio Vargas, from 1930 until 1945. In the literature of the Brazilian economy with the coming of industry in Brazil, two visions are in opposition: on one hand, industrialization as a byproduct of government intervention in the coffee sector, on the other, deliberately promoted industrialization by the government. Based on an analysis of equilibrium in a dynamic game of imperfect information, rationality is evident from the creation of institutions for industrial development in the 1930s. The result shows the changes of equilibrium in which Brazil went from the 1930s, with changes in the tax structure, educational, financial and labor relations, that institutional change created fertile ground for the rise of industrialization that characterized the first Vargas government and also shows the intention of this government, when one observes the transformation of the tax system, so be immune to external economic fluctuations and also educational changes, which came to encourage the primary, secondary and technical vocational, measures designed to meet the new economic landscape of Brazil. Another point that confirms the outcome of the Nash equilibrium is perfect in subgame the loss of the importance of the coffee sector in the period that includes the nineteenth century until the end of the first Vargas government, where the evidence shows that farmers had, since the decade of 1930, to diversify investment trends due to the loss of income to the grower industry.

O presente trabalho propõe-se analisar a industrialização do Brasil no contexto de mudanças econômicas e políticas no primeiro governo de Getúlio Vargas, de 1930 até 1945. Na literatura de economia brasileira com relação ao surgimento da indústria no Brasil, duas visões se contrapõem: de um lado, a industrialização como subproduto da intervenção do governo no setor cafeeiro; de outro, a industrialização intencionalmente promovida pelo governo. Com base em uma análise de equilíbrio em um jogo dinâmico de informação imperfeita, é evidenciada a racionalidade da criação de instituições para o desenvolvimento industrial na década de 1930. Este resultado de equilíbrio mostra as mudanças pela qual o Brasil passou a partir da década de 1930, com mudanças da estrutura tributária, educacional, financeira e relações de trabalho, ou seja, essa mudança institucional gerou campo fértil para o surgimento do processo de industrialização que caracterizou o primeiro governo Vargas e também mostra a intencionalidade desse governo, quando se observa a transformação do sistema tributário, de tal modo a ficar imune das oscilações econômicas externas e também as mudanças educacionais, que passou a incentivar o ensino primário, secundário e técnico profissionalizante, medidas essas feitas para atender o novo panorama econômico brasileiro. Outro ponto que corrobora o resultado do equilíbrio de Nash perfeito em subjogos é a perda da importância do setor cafeeiro no período que engloba o século XIX até o final do primeiro governo Vargas, onde as evidências mostram que os cafeicultores tinham, antes e durante a década de 1930, tendências a diversificarem investimentos por conta da perda da renda com o setor cafeicultor. / This study proposes to examine the industrialization of Brazil in the context of economic and political changes in the first government of Getulio Vargas, from 1930 until 1945. In the literature of the Brazilian economy with the coming of industry in Brazil, two visions are in opposition: on one hand, industrialization as a byproduct of government intervention in the coffee sector, on the other, deliberately promoted industrialization by the government. Based on an analysis of equilibrium in a dynamic game of imperfect information, rationality is evident from the creation of institutions for industrial development in the 1930s. The result shows the changes of equilibrium in which Brazil went from the 1930s, with changes in the tax structure, educational, financial and labor relations, that institutional change created fertile ground for the rise of industrialization that characterized the first Vargas government and also shows the intention of this government, when one observes the transformation of the tax system, so be immune to external economic fluctuations and also educational changes, which came to encourage the primary, secondary and technical vocational, measures designed to meet the new economic landscape of Brazil. Another point that confirms the outcome of the Nash equilibrium is perfect in subgame the loss of the importance of the coffee sector in the period that includes the nineteenth century until the end of the first Vargas government, where the evidence shows that farmers had, since the decade of 1930, to diversify investment trends due to the loss of income to the grower industry.

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / A teoria dos jogos à um ramo da matemÃtica dedicado ao estudo de situaÃÃes que surgem quando mÃltiplos agentes de decisÃo buscam atingir seus objetivos individuais, possivelmente conflitantes entre si. Em sua formulaÃÃo dinÃmica linear quadrÃtica (LQ), as soluÃÃes de equilÃbrio de Nash dos jogadores podem ser obtidas em termos das equaÃÃes algÃbricas de Riccati acopladas, que, a depender do mÃtodo numÃrico utilizado para seu cÃlculo, podem gerar resultados insatisfatÃrios sob o ponto de vista da estabilidade e precisÃo numÃrica. Neste sentido, esta dissertaÃÃo propÃe um novo algoritmo para uma soluÃÃo alternativa das equaÃÃes algÃbricas de Riccati acopladas associadas aos jogos dinÃmicos (LQ), com estrutura de informaÃÃo em malha aberta, utilizando, para isso, conceitos da teoria da dualidade e otimizaÃÃo estÃtica convexa. Em adiÃÃo, obtÃm-se uma nova metodologia para a sÃntese de uma famÃlia de controladores Ãtimos. A teoria dos jogos tambÃm revela um enorme potencial de aplicaÃÃo em problemas de controle multiobjetivo, no qual està incluÃdo o controle Hinf, que pode ser formulado como um jogo dinÃmico de soma-zero. Considerando essa formulaÃÃo, as novas metodologias propostas neste trabalho sÃo estendidas aos problemas de controle Hinf com rejeiÃÃo de perturbaÃÃo, gerando resultados com melhores propriedades de desempenho e estabilidade que os obtidos via equaÃÃo algÃbrica de Riccati modificada. Por fim, atravÃs de exemplos numÃricos e simulaÃÃes computacionais, as novas metodologias sÃo confrontadas com as metodologias tradicionais, evidenciando-se os aspectos mais relevantes de cada abordagem.

Submitted by Bernardo Lustosa (bernardo.lustosa@clearsale.com.br) on 2013-09-09T23:42:12Z No. of bitstreams: 1 Tese v25 - Com Ficha Catalográfica no Final.pdf: 1307168 bytes, checksum: f1e2947e6ac3832680ea2397380348f3 (MD5) / Rejected by Suzinei Teles Garcia Garcia (suzinei.garcia@fgv.br), reason: Prezado Bernardo, Falta ficha catalográfica na 3ª página. Att. Suzi 3799-7876 on 2013-09-10T12:37:23Z (GMT) / Submitted by Bernardo Lustosa (bernardo.lustosa@clearsale.com.br) on 2013-09-10T13:40:50Z No. of bitstreams: 1 Tese v26 - Com Ficha Catalográfica na Terceira Página.pdf: 1307219 bytes, checksum: 1d84d82fc68651266396b568690933bf (MD5) / Approved for entry into archive by Suzinei Teles Garcia Garcia (suzinei.garcia@fgv.br) on 2013-09-10T13:51:29Z (GMT) No. of bitstreams: 1 Tese v26 - Com Ficha Catalográfica na Terceira Página.pdf: 1307219 bytes, checksum: 1d84d82fc68651266396b568690933bf (MD5) / Made available in DSpace on 2013-09-10T14:06:34Z (GMT). No. of bitstreams: 1 Tese v26 - Com Ficha Catalográfica na Terceira Página.pdf: 1307219 bytes, checksum: 1d84d82fc68651266396b568690933bf (MD5) Previous issue date: 2013-08-13 / Em redes de inovação baseadas em trocas de informação, o agente orquestrador se apropria das informações dos atores periféricos, gera inovação e distribui em forma de valor agregado. É sua função promover a estabilidade na rede fazendo com que a mesma tenha taxas não negativas de crescimento. Nos mercados de análise de crédito e fraude, por exemplo, ou bureaus funcionam como agentes orquestradores, concentrando as informações históricas da população que são provenientes de seus clientes e fornecendo produtos que auxiliam na tomada de decisão. Assumindo todas as empresas do ecossistema como agentes racionais, a teoria dos jogos se torna uma ferramenta apropriada para o estudo da precificação dos produtos como mecanismo de promoção da estabilidade da rede. Este trabalho busca identificar a relação de diferentes estruturas de precificação promovidas pelo agente orquestrador com a estabilidade e eficiência da rede de inovação. Uma vez que o poder da rede se dá pela força conjunta de seus membros, a inovação por esta gerada varia de acordo com a decisão isolada de cada agente periférico de contratar o agente orquestrador ao preço por ele estipulado. Através da definição de um jogo teórico simplificado onde diferentes agentes decidem conectar-se ou não à rede nas diferentes estruturas de preços estipuladas pelo agente orquestrador, o estudo analisa as condições de equilíbrio conclui que o equilíbrio de Nash implica em um cenário de estabilidade da rede. Uma conclusão é que, para maximizar o poder de inovação da rede, o preço a ser pago por cada agente para fazer uso da rede deve ser diretamente proporcional ao benefício financeiro auferido pela inovação gerada pela mesma. O estudo apresenta ainda uma simulação computacional de um mercado fictício para demonstração numérica dos efeitos observados. Através das conclusões obtidas, o trabalho cobre uma lacuna da literatura de redes de inovação com agentes orquestradores monopolistas em termos de precificação do uso da rede, servindo de subsídio de tomadores de decisão quando da oferta ou demanda dos serviços da rede. / In innovation networks based on information exchange, the orchestrating actor, or hub, captures information from the peripherical actors, promotes innovation and then distributes it for the network in the form of added value. Orchestration comprises promoting the network’s stability in order to avoid negative growth rates. The credit and fraud agencies, for example, can be understood as orchestrating hubs, concentrating the historical information of the population generated by their clients and offering products that support decision making. Assuming all the companies of this ecosystem as rational agents, game theory emerges as an appropriate framework for the study of pricing as a mechanism to promote the network’s stability. The present work focuses on the identification of a relationship between the different pricing options that can be proposed by the orchestrating hub and the network’s stability and efficiency. Since the network power is given by the combined strength of its members, the innovation generated is a function of the isolated decision of each peripherical agent on whether to hire the orchestrating hub’s services for the price defined by the latter. Through the definition of a simplified theoretical game in which agents decide whether to connect or not to the network based on the pricing structure defined by the hub, the present study analyzes the equilibrium conditions and concludes that the Nash equilibrium entails the network’s stability. One of the conclusions is that in order to maximize the innovation power of the network, the agents should be charged a price that is proportional to the financial benefit obtained by the innovation generated by the net. The study presents as well a computer simulation of a fictitious market for a numerical demonstration of the observed effects. With these conclusions, the present study fills a gap in the literature on monopolistic orchestrated innovation in terms of the pricing structures of the network connection and its use. It can be used as a basis for decision making both on the supply and the demand sides of the services of the hub.

This thesis is organized into two parts, one for my main area of research in the field of stochastic games, and the other for my contributions in the area of service systems. We first provide an abstract for my work in stochastic games. The field of stochastic games has been actively pursued over the last seven decades because of several of its important applications in oligopolistic economics. In the past, zero-sum stochastic games have been modelled and solved for Nash equilibria using the standard techniques of Markov decision processes. General-sum stochastic games on the contrary have posed difficulty as they cannot be reduced to Markov decision processes. Over the past few decades the quest for algorithms to compute Nash equilibria in general-sum stochastic games has intensified and several important algorithms such as stochastic tracing procedure [Herings and Peeters, 2004], NashQ [Hu and Wellman, 2003], FFQ [Littman, 2001], etc., and their generalised representations such as the optimization problem formulations for various reward structures [Filar and Vrieze, 1997] have been proposed. However, they suffer from either lack of generality or are intractable for even medium sized problems or both. In our venture towards algorithms for stochastic games, we start with a non-linear optimization problem and then design a simple gradient descent procedure for the same. Though this procedure gives the Nash equilibrium for a sample problem of terrain exploration, we observe that, in general, it need not be true. We characterize the necessary conditions and define KKT-N point. KKT-N points are those Karush-Kuhn-Tucker (KKT) points which corresponding to Nash equilibria. Thus, for a simple gradient based algorithm to guarantee convergence to Nash equilibrium, all KKT points of the optimization problem need to be KKT-N points, which restricts the applicability of such algorithms. We then take a step back and start looking at better characterization of those points of the optimization problem which correspond to Nash equilibria of the underlying game. As a result of this exploration, we derive two sets of necessary and sufficient conditions. The first set, KKT-SP conditions, is inspired from KKT conditions itself and is obtained by breaking down the main optimization problem into several sub-problems and then applying KKT conditions to each one of those sub-problems. The second set, SG-SP conditions, is a simplified set of conditions which characterize those Nash points more compactly. Using both KKT-SP and SG-SP conditions, we propose three algorithms, OFF-SGSP, ON-SGSP and DON-SGSP, respectively, which we show provide Nash equilibrium strategies for general-sum discounted stochastic games. Here OFF-SGSP is an off-line algorithm while ONSGSP and DON-SGSP are on-line algorithms. In particular, we believe that DON-SGSP is the first decentralized on-line algorithm for general-sum discounted stochastic games. We show that both our on-line algorithms are computationally efficient. In fact, we show that DON-SGSP is not only applicable for multi-agent scenarios but is also directly applicable for the single-agent case, i.e., MDPs (Markov Decision Processes). The second part of the thesis focuses on formulating and solving the problem of minimizing the labour-cost in service systems. We define the setting of service systems and then model the labour-cost problem as a constrained discrete parameter Markov-cost process. This Markov process is parametrized by the number of workers in various shifts and with various skill levels. With the number of workers as optimization variables, we provide a detailed formulation of a constrained optimization problem where the objective is the expected long-run averages of the single-stage labour-costs, and the main set of constraints are the expected long-run average of aggregate SLAs (Service Level Agreements). For this constrained optimization problem, we provide two stochastic optimization algorithms, SASOC-SF-N and SASOC-SF-C, which use smoothed functional approaches to estimate gradient and perform gradient descent in the aforementioned constrained optimization problem. SASOC-SF-N uses Gaussian distribution for smoothing while SASOC-SF-C uses Cauchy distribution for the same. SASOC-SF-C is the first Cauchy based smoothing algorithm which requires a fixed number (two) of simulations independent of the number of optimization variables. We show that these algorithms provide an order of magnitude better performance than existing industrial standard tool, OptQuest. We also show that SASOC-SF-C gives overall better performance.

Revenue Management (RM) is the practice of managing perishable assets by control-ling their availability and/or prices with an objective to maximize the total revenue. Seat inventory allocation falls in the purview of quantity-based RM. The liberalization of the aviation sector and the subsequent entrance of the low-cost carriers saw an ever-increasing customer base for the airline industry. Given the large number of buyers, firms were free to decide the price at which they would sell tickets. The low-cost carriers started to follow a third degree price discrimination and segmentation of the market, charging a higher price to the market with a relatively inelastic demand. Although a lot of work has been done in the area of seat inventory allocation under a monopolistic market scenario, we realized that not a lot of work had been done in a competitive market scenario. This thesis considers the problem of seat inventory allocation and pricing in a duopoly where each of the competing airlines have two fare-classes. We consider the possibility that the same fare-class may be priced differently by the two competing airlines and allow for the over flow of passengers between the airlines in the same fare-class. In the first part of our work, we develop a non-linear mathematical model for setting the booking limits for one of the two competing air-lines such that the revenue earned is maximized. We consider over flow of passengers from one airline to another in the same fare-class in response to a price differential and compare the results obtained from our model with the standard Expected Marginal Seat Revenue (EMSR) model under a monopolistic scenario. The results show that our model gives higher revenues than that obtained from the EMSR model. In the second part of our work, we consider a non-cooperative game between two competing airlines with price cutting as the strategy to increase their demand. Through numerical computations, we identify the pure strategy Nash equilibrium. From the results, we conclude that Nash equilibrium is achieved only when both the airlines follow the same pricing strategy indicating that individual price cutting will not be beneficial. This also indicates that unless the competitors enter into a cooperative coalition with each other, they would not benefit from deep discount offers. In the third and final part, we prove theoretically the existence of pure strategy Nash equilibrium in a two airline, two fare-class problem with price sensitive over flow of customers in the same fare-class that was computationally analysed earlier. The strategy / strategies at which Nash equilibrium is achieved are identified. We show that Nash equilibrium is only achieved when both the airlines price identically. Hence, our thesis concludes that differential pricing does not hold any significance for the competing airlines from an operational perspective.

This thesis investigates decision-making in two-player imperfect information games against opponents whose actions can affect our rewards, and whose strategies may be based on memories of interaction, or may be changing, or both. The focus is on modelling these dynamic opponents, and using the models to learn high-reward strategies. The main contributions of this work are: 1. An approach to learn high-reward strategies in small simultaneous-move games against these opponents. This is done by using a model of the opponent learnt from sequence prediction, with (possibly discounted) rewards learnt from reinforcement learning, to lookahead using explicit tree search. Empirical results show that this gains higher average rewards per game than state-of-the-art reinforcement learning agents in three simultaneous-move games. They also show that several sequence prediction methods model these opponents effectively, supporting the idea of using them from areas such as data compression and string matching; 2. An online expectation-maximisation algorithm that infers an agent's hidden information based on its behaviour in imperfect information games; 3. An approach to learn high-reward strategies in medium-size sequential-move poker games against these opponents. This is done by using a model of the opponent learnt from sequence prediction, which needs its hidden information (inferred by the online expectation-maximisation algorithm), to train a state-of-the-art no-regret learning algorithm by simulating games between the algorithm and the model. Empirical results show that this improves the no-regret learning algorithm's rewards when playing against popular and state-of-the-art algorithms in two simplified poker games; 4. Demonstrating that several change detection methods can effectively model changing categorical distributions with experimental results comparing their accuracies to empirical distributions. These results also show that their models can be used to outperform state-of-the-art reinforcement learning agents in two simultaneous-move games. This supports the idea of modelling changing opponent strategies with change detection methods; 5. Experimental results for the self-play convergence to mixed strategy Nash equilibria of the empirical distributions of plays of sequence prediction and change detection methods. The results show that they converge faster, and in more cases for change detection, than fictitious play.

Studien går ut på att analysera marknadsstrukturen för två industriföretag(Holmen och SCA) under antagandet att båda konkurrerar mot varandragenom att köpa rå material samt genom att sälja förädlade produkter.Produktmarknaden som undersöks är pappersmarknaden och antas varakoncentrerad. Rå materialmknaden som undersöks ärmassavedmarknaden och antas karaktäriseras som en duopsony. Detvisade sig att Holmen och SCA köper massaved från en stor mängdskogsägare. Varje företag skapar varje månad en prislista där de bestämmerbud priset föassaved. Priset varierar beroende på region. Både SCA ochHolmen väljer mellan två strategiska beslut, antigen att buda högt pris ellerlågt pris. Genom spelteori så visade det sig att båda industriföretagenanvänder mixade strategier då de i vissa tillfällen budar högt och i andratillfällen budar lågt. Nash jämviktslägen för mixade strategier räknades utmatematiskt och analyserades genom dynamisk spelteori.Marknadskoncentrationen för pappersmarknaden undersöktes viaHerfindahl-Hirschman index (HHI). Porters femkraftsmodell användes föratt analysera industri konkurrensen. Resultatet visade attproduktmarknaden är koncentrerad då HHI testerna gav höga indexvärdenmellan 3100 och 1700. Det existerade dessutom ett Nash jämviktsläge fö mixade strategier som gav SCA förväntad lönsamhet 1651 miljoner kronoroch Holmen 1295 miljoner kronor. Dynamisk spelteori visade att SCA ochHolmens budgivning följer ett mönster och att högt/lågt bud beror påavvikelser från Nash jämviktslägets sannolikhetsdistribution. Nashjämviktslägets råder ifall sannolikhetsdistributionerna vid låg budgivningär 68,6 procent för SCA och 66,7 procent för Holmen. Detta gav indikatore för icke samarbetsvilliga spel. Slutsatsen är att om två spelare (kvarnar) når / The research aims to analyze the market structure of two companies in th forest industry (Holmen and SCA) with the assumption that thes companies compete at buying raw materials and selling products. Theproduct market in this study is the paper market under the assumption thatboth companies operate in a concentrated product market. The rawmatial market that one investigates in this study is the pulpwood marketunder the assumption that it is a duopsony. What this study has concludedis that Holmen and SCA buy pulpwood from lots of different self-managingforest owners. Each company creates a monthly pricelist where they decidethe bid price of pulpwood. The amount varies depending on the region. Bot SCA and Holmen chooses between two strategic decisions, either to bid highor to bid low. Through game theory, it has been clear that each company usesmixed strategies as they sometimes give high bids and sometimes give lowbids. The Nash equilibrium for mixed strategies have been calculatedmathematically and analyzed through the dynamics of game theory. As fore market concentration, the product market has been investigatedthrough the Herfindahl-Hirschman index (HHI). Porter's five-force modelwas used to analyze the industry competition. The results showed that theproduct market is concentrated as the HHI tests gave High index scoresbetween 3100 and 1700. In addition, there existed a Nash equilibrium in amixed strategy that gave SCA expected payoff 1651 million SEK and Holmen1295 million SEK. The dynamic game theory showed that SCA and Holmen'sbidding follows a repeating trajectory and that the high/low bidding is dueto deviations from Nash equilibrium probability distribution. The Nashequilibrium situation prevails if the probability distribution at low biddingis 68.6 percent for SCA and 66,7 percent for Holmen. This providedindicators for a non-cooperative game. The conclusion is that if two players

Les grands réseaux de communication sont partout, des centres de données avec des millions de serveurs jusqu’aux réseaux sociaux avec plusieurs milliards d’utilisateurs.Cette thèse est dédiée à l’étude fine de la complexité de différents problèmes combinatoires sur ces réseaux. Dans la première partie, nous nous intéressons aux propriétés des plongements des réseaux de communication dans les arbres. Ces propriétés aident à mieux comprendre divers aspects du trafic dans les réseaux (tels que la congestion). Plus précisément, nous étudions la complexité du calcul de l’hyperbolicité au sens de Gromov et de paramètres des décompositions arborescentes dans les graphes. Ces paramètres incluent la longueur arborescente (treelength) et l’épaisseur arborescente (treebreadth). Au passage, nous démontrons de nouvelles bornes sur ces paramètres dans de nombreuses classes de graphes, certaines d’entre elles ayant été utilisées dans la conception de réseaux d’interconnexion des centres de données. Le résultat principal dans cette partie est une relation entre longueur et largeur arborescentes (treewidth), qui est un autre paramètre très étudié des graphes. De ce résultat, nous obtenons une vision unifiée de la ressemblance des graphes avec un arbre, ainsi que différentes applications algorithmiques. Nous utilisons dans cette partie divers outils de la théorie des graphes et des techniques récentes de la théorie de la complexité / Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example