La th´eorie de la complexit´e permet de classifier les probl`emes en fonction de leur difficult´e. Le cadre classique dans lequel elle s’applique est celui d’un algorithme centralis´e qui dispose de toutes les informations. Avec l’essor des r´eseaux et des architectures d´ecentralis´ees, l’algo- rithmique distribu´ee a ´et´e ´etudi´ee. Dans un grand nombre de probl`emes, en optimisation et en ´economie, les d´ecisions et les calculs sont effectu´es par des agents ind´ependants qui suivent des objectifs diff´erents dont la r´ealisation d´epend des d´ecisions des autres agents. La th´eorie des jeux est un cadre naturel pour analyser les solutions de tels probl`emes. Elle propose des concepts de stabilit´e, le plus classique ´etant l’´equilibre de Nash.Une mani`ere naturelle de calculer de telles solutions est de “ faire r´eagir “ les agents ; si un agent voit quelles sont les d´ecisions des autres joueurs ou plus g´en´eralement un “ ´etat du jeu “, il peut d´ecider de changer sa d´ecision pour atteindre son objectif faisant ainsi ´evoluer l’´etat du jeu. On dit que ces algorithmes sont des “ dynamiques “.On sait que certaines dynamiques convergent vers un concept de solution. On s’int´eresse `a la vitesse de convergence des dynamiques. Certains concepts de solutions sont mˆeme complets pour certaines classes de complexit´e ce qui rend peu vraisemblable l’existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilis´e alors trois approches pour obtenir une convergence rapide : am´eliorer la dynamique (en utilisant par exemple des bits al´eatoires), restreindre la structure du probl`eme, et rechercher une solution approch´ee.Sur les jeux de congestion, on a ´etendu les r´esultats de convergence rapide vers un ´equilibre de Nash approch´e aux jeux n´egatifs. Cependant, on a montr´e que sur les jeux sans contrainte de signe, calculer un ´equilibre de Nash approch´e est PLS-complet. Sur les jeux d ’appariement, on a ´etudi´e la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle param´etr´ee par un r´eseau social. En particulier, on a am´elior´e des dynamiques naturelles afin qu’elles atteignent un ´equilibre enO(log(n)) tours (avec n le nombre de joueurs). / Complexity theory allows to classify problems by their algorithmic hardness. The classical framework in which it applies is the one of a centralized algorithm that knows every informa- tion. With the development of networks and decentralized architectures, distributed dynamics was studied. In many problems, in optimization or economy, actions and computations are made by independant agents that don’t share the same objective whose realization depends on the actions of other agents. Game theory is a natural framework to study solutions of this kind of problem. It provides solution concepts such as the Nash equilibrium.A natural way to compute these solutions is to make the agents “react” ; if an agent sees the actions of the other player, or more generally the state of the game, he can decide to change his decision to reach his objective and updates the state of the game. We call �dynamics� this kind of algorithms.We know some dynamics converges to a stable solution. We are interested by the speed of convergence of these dynamics. Some solution concepts are even complete for some complexity classes which make unrealistic the existence of fast converging dynamics. We used three ways to obtain a fast convergence : improving dynamics (using random bits), finding simple subcases, and finding an approximate solution.We extent fast convergence results to an approximate Nash equilibria in negative congestion games. However, we proved that finding an approximate Nash equilibrium in a congestion games without sign restriction is PLS-complete. On matching game, we studied the speed of concurrent dynamics when players have partial information that depends on a social network. Especially, we improved natural dynamics for them to reach an equilibrium inO(log(n)) rounds (with n is the number of players).

O modelo a ser apresentado consiste em um jogo de preço e localização entre duas firmas. Utiliza-se o pressuposto de que os consumidores têm sua utilidade positivamente afetada por um efeito de rede, ou seja, são diretamente influenciados pela tamanho da demanda do bem. Dispondo os consumidores uniformemente distribuídos dentro de um intervalo linear [0, 1], buscamos encontrar os equilíbrios de preço e localização do jogo proposto. Verificamos que, dados os pressupostos do modelo, existem equilíbrios de Nash para cada subjogo e dependerão da força dos efeitos de rede. Quando os efeitos de rede são fortes o suficiente, os preços praticados serão inicialmente reduzidos até que o monopólio seja alcançado por uma das firmas, quando o preço será elevado e a outra firma passará a cobrar um preço nulo. No subjogo de localizações foi possível identificar que, no caso em que o poder do efeito de rede está acima de um determinado nível, as firmas não irão diferenciar seus produtos e se localizarão em algum ponto dentro do intervalo fechado [1/4 , 3/4] / The model to be presented is a price-location game between two firms. The assumption is that consumers\' utility is positively affected by a network effect, i.e. it is directly influenced by the size of demand. Distributing consumers uniformly in a linear interval [0, 1] we seek the price and location equilibrium of the proposed game. We found that, given the model assumptions, there are Nash equilibria for each subset that depend on the strength of network effects. When network effects are strong enough, prices are initially reduced until the monopoly is reached by one of the firms, then the price rises and the other firm shall charge a null price. In the subgame of locations, when the power of the network effect is above a certain level, the firms will not differentiate their products and will be located at any point within the closed interval [1/4 , 3/4]

Thesis advisor: Hideo Konishi / My doctoral dissertation contains three essays on menu auction and its related applications. The first chapter is a theoretical generalization of classical menu auction model, and the second and the third chapters are applications to a resource allocation problem and an industrial organization problem. Menu auction (Bernheim and Whinston, 1986) is a first-price package auction with complete information. They show that every Nash equilibrium under some refinements always leads to an efficient outcome. Therefore, this becomes a natural efficiency benchmark for package auction designs (e.g., Ausubel and Milgrom 2002). Menu auction can also be viewed as a model of economic influence where the auctioneer is going to choose an action which affects bidders' payoff so that each bidder tries to influence the outcome by monetary transfer to the auctioneer. This framework is widely adopted in political lobbying models where the special interest groups lobbying the government over trade policies (e.g., Grossman and Helpman 1994). However, the applicability is limited by quasi-linear preferences and the absence of budget constraints. In my first chapter, ``Menu Auctions with Non-Transferable Utilities and Budget Constraints'', I extends Bernheim and Whinston's (1986) menu auction model under transferable utilities to a framework with non-transferable utilities and budget constraints. Under appropriate definitions of equilibria consistent with subgame perfection, it is shown that every truthful Nash equilibrium (TNE) is a coalition-proof Nash equilibrium (CPNE) and that the set of TNE payoffs and the set of CPNE payoffs are equivalent, as in a transferable utility framework. The existence of a CPNE is assured in contrast with the possible non-existence of Nash equilibrium under the definition by Dixit, Grossman, and Helpman (1997). Moreover, the set of CPNE payoffs is equivalent to the bidder-optimal weak core. The second chapter relates menu auction to a resource allocation problem. Kelso and Crawford (1982) propose a wage-adjustment mechanism resulting in a stable matching between heterogeneous firms and workers. Instead of a benevolent social planner, in ``Profit-Maximizing Matchmaker'' (w. Hideo Konishi), we consider a profit-maximizing auctioneer to solve this many-to-one assignment problem. If firms can only use individualized price, then the auctioneer can only earn zero profit in every Nash equilibrium and the sets of stable assignments and strong Nash equilibria are equivalent. Otherwise, the auctioneer might earn positive profit even in a coalition-proof Nash equilibrium. This reinforces Milgrom's (2010) argument on the benefit of using simplified message spaces that it not only reduces information requirement but also improves resource allocation. The third chapter applies menu auction in an industrial organization problem. In ``Choosing a Licensee from Heterogeneous Rivals'' (w. Hideo Konishi and Anthony Creane), we consider a firm licensing its production technology to rivals when firms with heterogeneous in production costs competing in a Cournot market. While Katz and Shapiro (1986) show that a complete transfer in duopoly can be joint-profit reducing, we show that it is always joint-profit improving provided that at least three firms remain in the industry after transfer. While transfers between similarly efficient firms may reduce welfare, the social welfare must increase if the licensor is the most efficient in the industry, contrast with Katz and Shapiro (1985) in the duopoly environment. This has an important implication in competition regulation. Then we investigate relative efficiency of the licensee under different licensing auction mechanisms. With natural refinement of equilibria, we show that a menu auction licensee, a standard first-price auction licensee, and a joint-profit maximizing licensee are in (weakly) descending order of efficiency. / Thesis (PhD) — Boston College, 2012. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Economics.

The results section of my thesis includes three chapters. The first two chapters are on theoretical game theory. In both chapters, by mathematical modelling and game theoretical tools, I am predicting the behaviour of the players in some real world issues. Hoteling-Downs model plays an important role in the modern political interpretations. The first chapter of this study investigates an extension of Hoteling-Downs model to have multi-dimensional strategy space and asymmetric candidates. Chapter 3 looks into the inspection game where the inspections are not the same in the series of sequential inspections. By modelling the game as a series of recursive zero-sum games I find the optimal strategy of the players in the equilibrium. The forth chapter investigates direct optimization methods for large scale problems. Using Matlab implementations of Genetic and Nelder-Mead algorithms, I compare the efficiency and accuracy of the most famous direct optimization methods for unconstraint optimization problems based on differing number of variables.

O presente trabalho busca apresentar uma aplicação da teoria dos jogos, de modo a complementar a literatura que utiliza esse referencial teórico e alcançar conclusões pertinentes que desafiam o senso comum. O assunto trabalhado são os debates políticos televisivos e o excesso de acusações realizadas pelos participantes. Através de premissas e expectativas dos jogos não cooperativos, que foram aplicadas sobre os debates de 2º turno das eleições presidenciais de 1989, 2006, 2010 e 2014, a hipótese de que a razão de tal comportamento é a própria organização do jogo, e não uma eventual falta de propostas a serem apresentadas pelos políticos, não é refutada empiricamente. Além disso, sugestões de mudanças de regras desses programas são realizadas, de modo que seu objetivo principal, a exposição de planos de governo, passe a ser atingido. / The present work seeks to present an application of the Game Theory, in order to complement the literature that uses this theoretical reference and to reach pertinent conclusions that defy common sense. The topic that is going to be studied are the televised political debates and the excess of accusations made by the participants. Through assumptions and expectations of non-cooperative games, that were applied to the 2nd round debates of the 1989, 2006, 2010 and 2014 presidential elections, the hypothesis that the reason for such behavior is the organization of the game, not an eventual lack of proposals by the political parties, is not empirically refuted. In addition, suggestions for changes in the rules of these programs are made, in order to ensure that the primary debates\' goal of exposing government plans is reached.

No description available.

Heterogeneous Computing (HC) systems achieve high performance by networking together computing resources of diverse nature. The issues of task assignment and scheduling are critical in the design and performance of such systems. In this thesis, an auction based game theoretic framework is developed for dynamic task scheduling in HC systems. Based on the proposed game theoretic model, a new dynamic scheduling algorithm is developed that uses auction based strategies. The dynamic scheduling algorithm yields schedules with shorter completion times than static schedulers while incurring higher scheduling overhead. Thus, a second scheduling algorithm is proposed which uses an initial schedule generated with a learning automaton based algorithm, and then heuristics are used to identify windows of tasks within the application that can be rescheduled dynamically during run time.

The optimal allocation of the resources to the emergency locations in the event of multiple crises in an urban environment is an intricate problem, especially when the available resources are limited. In such a scenario, it is important to allocate emergency response units in a fair manner based on the criticality of the crisis events and their requests. In this research, a crisis management tool is developed which incorporates a resource allocation algorithm. The problem is formulated as a game theoretic framework in which the crisis events are modeled as the players, the emergency response centers as the resource locations with emergency units to be scheduled and the possible allocations as strategies. The pay-off is modeled as a function of the criticality of the event and the anticipated response times. The game is played assuming a specific region within a certain locality of the crisis event to derive an optimal allocation. If a solution is not feasible, the perimeter of the locality in consideration is increased and the game is repeated until convergence. Experimental results are presented to illustrate the efficacy of the proposed methodology and metrics are derived to quantify the fairness of the solution. A regression analysis has been performed to identify the statistical significance of the results.

The problem of resource allocation and management in the context of multiple crises occurring in an urban environment is challenging. In this thesis, the problem is formulated using game theory and a solution is developed based on the Nash equilibrium to optimize the allocation of resources to the different crisis events in a fair manner considering several constraints such as the availability of resources, the criticality of the events, the amount of resources requested etc. The proposed approach is targeted at managing small to medium level crisis events occurring simultaneously within a specific pre-defined perimeter with the resource allocation centers being located within the same fixed region. The objective is to maximize the utilization of the emergency response units while minimizing the response times. In the proposed model, players represent the crisis events and the strategies correspond to possible allocations. The choice of strategies by each player impacts the decisions of the other players. The Nash equilibrium condition will correspond to the set of strategies chosen by all the players such that the resource allocation optimal for a given player also corresponds to the optimal allocations of the other players. The implementation of the Nash equilibrium condition is based on the Hansen's combinatorial theorem based approximation algorithm. The proposed solution has been implemented using C++ and experimental results are presented for various test cases. Further, metrics are developed for establishing the quality and fairness of the obtained results.

This paper studies the problem of multi-period pricing for perishable products in a competitive (oligopolistic) market. We study non cooperative Nash equilibrium policies for sellers. At the beginning of the time horizon, the total inventories are given and additional production is not an available option. The analysis for periodic production-review models, where production decisions can be made at the end of each period at some production cost after incurring holding or backorder costs, does not extend to this model. Using results from game theory and variational inequalities we study the existence and uniqueness of equilibrium policies. We also study convergence results for an algorithm that computes the equilibrium policies. The model in this paper can be used in a number of application areas including the airline, service and retail industries. We illustrate our results through some numerical examples. / Singapore-MIT Alliance (SMA)