The thesis consists of four papers. The first two essays deal with entry externalities, the third studies the Law of One Price (LOP), while the last essay examines average profits for a monopolist under uncertainty. In the first essay, entry externalities in the form of information and positive payoff externalities are studied. When a firm enters a market, it often imposes externalities on existing firms and/or future potential entrants. If products are substitutes, these externalities are typically negative; if products are complements, the externalities are typically positive. Externalities related to substitution or complementarities between products are called payoff externalities, since entry by one firm has a direct effect on the other firms' payoff. Another type of externality arises when firms have private information about the profitability of entry. In this case, the entry decision of one firm potentially reveals that firm's private information. The focus of the paper is on the scope for intervention for an uninformed social planner, when firms privately know the profitability of entry and moreover, the firms have an option to delay their entry. The main result is that there is insufficient entry, since firms delay too much in equilibrium and further, the social planner can increase welfare by subsidizing early entry. Continuing on this theme, the second essay has the same focus, but instead takes the time of entry as fixed, while generalizing the analysis of payoff externalities also to the case of negative payoff externalities. The main contribution is the characterization of equilibria under both positive and negative payoff externalities and the implications for public policy. Here, the scope for intervention will, in contrast to the results in the first essay, be low, when entry is profitable for uninformed firms. In the third essay (joint with Richard Friberg), deviations from the LOP are studied in the presence of transport costs, under the assumption that firms can endogenously choose to segment markets in order to prevent arbitrage by consumers. It is shown that the deviation from LOP can increase as transport costs fall between countries. The last essay (joint with Richard Friberg), studies the problem facing a monopolist when the cost of inputs is uncertain. The main result is that the monopolist can gain from this uncertainty, in the sense that average profits are increasing in the variability of costs. / Diss. Stockholm : Handelshögsk., 2001

No description available.

La programmation semi-définie est un outil fondamental d'optimisation convexe et polynomiale. Elle revient à optimiser une fonction linéaire sur un spectraèdre (un ensemble défini par des inégalités matricielles linéaires). En particulier, la programmation semi-définie est une généralisation de la programmation linéaire.Nous étudions l'analogue non-archimédien de la programmation semi-définie, en remplaçant le corps des nombres réels par le corps des séries de Puiseux. Notre approche est fondée sur des méthodes issues de la géométrie tropicale et, en particulier, sur l'étude de la tropicalisation des spectraèdres.En première partie de la thèse, nous analysons les images par la valuation des ensembles semi-algébriques généraux définis dans le corps des séries de Puiseux. Nous montrons que ces images ont une structure polyédrale, ce qui fournit un analogue réel du théorème de Bieri et Groves. Ensuite, nous introduisons la notion de spectraèdres tropicaux et nous montrons que, sous une hypothèse de généricité, ces objets sont décrits par des systèmes d'inégalités polynomiales de degré 2 sur le semi-corps tropical. Cela généralise un résultat de Yu sur la tropicalisation du cône des matrices positives.Une question importante relative à la programmation semi-définie sur les réels consiste à caractériser des projections de spectraèdres. Dans ce cadre, Helton et Nie ont conjecturé que tout ensemble semi-algébrique convexe est la projection d'un spectraèdre. La conjecture a été réfutée par Scheiderer. Néanmoins, nous montrons qu'elle est vraie ''à valuation près'' : dans le corps réel clos des séries de Puiseux, les ensembles semi-algébriques convexes et les spectraèdres projetés ont exactement les mêmes images par la valuation non-archimédienne.En seconde partie de la thèse, nous étudions des questions algorithmiques liées à la programmation semi-définie. Le problème algorithmique de base consiste à décider si un spectraèdre est vide. On ne sait pas si ce problème appartient à NP dans le modèle de la machine de Turing, et les algorithmes fondés sur la décomposition cylindrique algébrique ou la méthode de points critiques constituent l'état de l'art dans ce domaine. Nous montrons que, dans le cadre non-archimédien, les spectraèdres tropicaux génériques sont décrits par des opérateurs de Shapley associés aux jeux à paiement moyen stochastiques. Cela donne une méthode pour résoudre des problèmes de réalisabilité en programmation semi-définie non-archimédienne en utilisant les algorithmes combinatoires conçus pour les jeux stochastiques.Dans les chapitres finals de la thèse, nous établissons des bornes de complexité pour l'algorithme d'itération sur les valeurs qui exploitent la correspondance entre les jeux stochastiques et la convexité tropicale. Nous montrons que le nombre d'itérations est contrôlé par un nombre de conditionnement relié au diamètre intérieur du spectraèdre tropical associé.Nous fournissons des bornes supérieures générales sur le nombre de conditionnement. Pour cela, nous établissons des bornes optimales sur la taille en bits des mesures invariantes de chaînes de Markov. Comme corollaire, notre estimation montre que l'itération sur la valeur résout les jeux ergodiques à paiement moyen en temps pseudo-polynomial si le nombre de positions aléatoires est fixé. Enfin, nous expérimentons notre approche à la résolution de programmes semi-définis non-archimédiens aléatoires de grande taille. / Semidefinite programming (SDP) is a fundamental tool in convex and polynomial optimization. It consists in minimizing the linear functions over the spectrahedra (sets defined by linear matrix inequalities). In particular, SDP is a generalization of linear programming.The purpose of this thesis is to study the nonarchimedean analogue of SDP, replacing the field of real numbers by the field of Puiseux series. Our methods rely on tropical geometry and, in particular, on the study of tropicalization of spectrahedra.In the first part of the thesis, we analyze the images by valuation of general semialgebraic sets defined over the Puiseux series. We show that these images have a polyhedral structure, giving the real analogue of the Bieri--Groves theorem. Subsequently, we introduce the notion of tropical spectrahedra and show that, under genericity conditions, these objects can be described explicitly by systems of polynomial inequalities of degree 2 in the tropical semifield. This generalizes the result of Yu on the tropicalization of the SDP cone.One of the most important questions about real SDPs is to characterize the sets that arise as projections of spectrahedra. In this context, Helton and Nie conjectured that every semialgebraic convex set is a projected spectrahedron. This conjecture was disproved by Scheiderer. However, we show that the conjecture is true ''up to taking the valuation'': over a real closed nonarchimedean field of Puiseux series, the convex semialgebraic sets and the projections of spectrahedra have precisely the same images by the nonarchimedean valuation.In the second part of the thesis, we study the algorithmic questions related to SDP. The basic computational problem associated with SDP over real numbers is to decide whether a spectrahedron is nonempty. It is unknown whether this problem belongs to NP in the Turing machine model, and the state-of-the-art algorithms that certify the (in)feasibility of spectrahedra are based on cylindrical decomposition or the critical points method. We show that, in the nonarchimedean setting, generic tropical spectrahedra can be described by Shapley operators associated with stochastic mean payoff games. This provides a tool to solve nonarchimedean semidefinite feasibility problems using combinatorial algorithms designed for stochastic games.In the final chapters of the thesis, we provide new complexity bounds for the value iteration algorithm, exploiting the correspondence between stochastic games and tropical convexity. We show that the number of iterations needed to solve a game is controlled by a condition number, which is related to the inner radius of the associated tropical spectrahedron. We provide general upper bounds on the condition number. To this end, we establish optimal bounds on the bit-length of stationary distributions of Markov chains. As a corollary, our estimates show that value iteration can solve ergodic mean payoff games in pseudopolynomial time, provided that the number of random positions of the game is fixed. Finally, we apply our approach to large scale random nonarchimedean SDPs.

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.

[pt] O objetivo deste trabalho é aplicar a Teoria dos Jogos como elemento motivador no ensino da Matemática em turmas da terceira série do ensino médio de uma escola estadual da cidade do Rio de Janeiro, que apresentam com grande frequência dificuldades no aprendizado desta disciplina. Construímos então uma sequência didática a ser realizada em sala de aula: apresentação de breve histórico da teoria, realização do jogo Dilema do Prisioneiro e posterior explicação sobre os resultados previstos pela teoria para este jogo, introduzindo os conceitos de matriz de ganhos e estratégia dominante. Em seguida foi aplicado um teste simples de auto-avaliação, para fixação dos tópicos apresentados anteriormente. Assumindo então que neste momento os alunos estão familiarizados com os conceitos mais simples da Teoria dos Jogos, realizamos em sala de aula o jogo Barganha com Ultimato, para posterior comparação de resultados com aqueles obtidos por Bianchi, Carter e Irons e Castro e Ribeiro. / [en] The objective of this study is to apply Game Theory as a motivating element in the teaching of mathematics in those classes in the 3rd series of secondary education in the state schools of the city of Rio de Janeiro which have already frequently presented difficulties in learning this discipline. We construct a didactic sequence to be applied in the classroom: presentation of a brief history of the theory; the realisation of the game, the Prisoner s Dilema; and a subsequent explanation of the results predicted by Game Theory for this game, introducing the concepts of the result matrix and the dominant strategy. We then apply a simple self-assessment test in order to consolidate these topics. Once the students are familiarised with the basic concepts of Game Theory, we realise the Ultimatum Game in the classroom in order to compare the results with those obtained by Bianchi, Carter e Irons and Castro e Ribeiro.

Theheighteneduseofautomatizationindifferentmarketshasmadeahugeimpactformany differenttypesofcompaniesthatwanttotakeadvantageofthetechnicalachievementsto remaincompetitiveinthemarket.Automatizationhasmanydifferentaspects,makingit importantforcompaniestodeeplyanalyzetheorganizationalstructureandcurrent operativecapacitytodecideifautomatizationcansatisfytheircurrentandfutureneeds.Itis alsoimportanttodevelopeffectiveinvestmentcalculationstocorrectlyassesstheviability ofautomatization.Thisstudyaimstoexploretheeffectsofautomatization,specificallyin fieldsincompanieslikeeconomy,competence,ergonomicsandefficiency,aswellas understandingwhichmethodsandcriteriasAteaLogisticsABusesinassessinginvestment ofautomatedcharacterandwhatriskstheseinvestmentscanpotentiallyhaveinthework environment.Thisisdonebycomparingthetheoryofthesedifferentconceptswiththe empiricalevidenceprovidedbythecompany.Byanalyzingempiricalevidencewiththe literature,thisstudyaimstogiveinsightsonthedifferenteffectsthatautomatizationcan havebasedondifferentparameters. / Denökadeanvändningenavautomatiseringpåolikamarknaderharhaftstorbetydelseför mångaolikatyperavföretagsomvilldrafördelavdetekniskalandvinningarnaförattförbli konkurrenskraftigapåmarknaden.Automatiseringharmångaolikaaspekter,vilketgördet viktigtförföretagattdjupgåendeanalyseraorganisationsstrukturenochnuvarandeoperativa kapacitetförattavgöraomautomatiseringkantillgodosederasnuvarandeochframtida behov.Detärocksåviktigtattutvecklaeffektivainvesteringskalkylerförattkorrektbedöma automatiseringenslönsamhet.Dennastudiesyftartillattutforskaeffekternaav automatisering,specifiktinomområdeniföretagsomekonomi,kompetens,ergonomioch effektivitet,samtförståvilkametoderochkriterierAteaLogisticsABanvänderföratt bedömainvesteringaravautomatiseradkaraktärochvilkariskerdessainvesteringar potentielltkanha.iarbetsmiljön.Dettagörsgenomattjämförateorinfördessaolika begreppmeddeempiriskabevissomföretagettillhandahåller.Genomattanalyseraempiri medlitteraturensyftardennastudietillattgeinsikteromdeolikaeffektersom automatiseringkanhautifrånolikaparametrar.

<p>Computer programs keep finding their ways into new safety-critical applications, while at the same time growing more complex. This calls for new and better methods to verify the correctness of software. We focus on one approach to verifying systems, namely that of <i>model checking</i>. At first, we investigate two categories of problems related to model checking: <i>games</i> and <i>stochastic infinite-state systems</i>. In the end, we join these two lines of research, by studying <i>stochastic infinite-state games</i>.</p><p>Game theory has been used in verification for a long time. We focus on finite-state 2-player parity and limit-average (mean payoff) games. These problems have applications in model checking for the <i>μ</i>-calculus, one of the most expressive logics for programs. We give a simplified proof of memoryless determinacy. The proof applies <i>both</i> to parity and limit-average games. Moreover, we suggest a strategy improvement algorithm for limit-average games. The algorithm is discrete and strongly subexponential.</p><p>We also consider probabilistic infinite-state systems (Markov chains) induced by three types of models. <i>Lossy channel systems (LCS)</i> have been used to model processes that communicate over an unreliable medium. <i>Petri nets</i> model systems with unboundedly many parallel processes. <i>Noisy Turing machines</i> can model computers where the memory may be corrupted in a stochastic manner. We introduce the notion of <i>eagerness</i> and prove that all these systems are eager. We give a scheme to approximate the value of a reward function defined on paths. Eagerness allows us to prove that the scheme terminates. For probabilistic LCS, we also give an algorithm that approximates the limit-average reward. This quantity describes the long-run behavior of the system.</p><p>Finally, we investigate Büchi games on probabilistic LCS. Such games can be used to model a malicious cracker trying to break a network protocol. We give an algorithm to solve these games.</p>

Computer programs keep finding their ways into new safety-critical applications, while at the same time growing more complex. This calls for new and better methods to verify the correctness of software. We focus on one approach to verifying systems, namely that of model checking. At first, we investigate two categories of problems related to model checking: games and stochastic infinite-state systems. In the end, we join these two lines of research, by studying stochastic infinite-state games. Game theory has been used in verification for a long time. We focus on finite-state 2-player parity and limit-average (mean payoff) games. These problems have applications in model checking for the μ-calculus, one of the most expressive logics for programs. We give a simplified proof of memoryless determinacy. The proof applies both to parity and limit-average games. Moreover, we suggest a strategy improvement algorithm for limit-average games. The algorithm is discrete and strongly subexponential. We also consider probabilistic infinite-state systems (Markov chains) induced by three types of models. Lossy channel systems (LCS) have been used to model processes that communicate over an unreliable medium. Petri nets model systems with unboundedly many parallel processes. Noisy Turing machines can model computers where the memory may be corrupted in a stochastic manner. We introduce the notion of eagerness and prove that all these systems are eager. We give a scheme to approximate the value of a reward function defined on paths. Eagerness allows us to prove that the scheme terminates. For probabilistic LCS, we also give an algorithm that approximates the limit-average reward. This quantity describes the long-run behavior of the system. Finally, we investigate Büchi games on probabilistic LCS. Such games can be used to model a malicious cracker trying to break a network protocol. We give an algorithm to solve these games.

The main goal of my master thesis is evaluation an investment project of company on the base of dynamic methods of investment evaluation. Methods of evaluation are net present value, payoff period, gross investment, profitability index and internal rate of return.