Date : 2012
Editeur / Publisher : [S.l.] : [s.n.] , 2012
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : anglais / English
Complexité de calcul (informatique)
Résumé / Abstract : Dans cette thèse, nous étudions la théorie des jeux sur les Processus de Décision de Markov (PDM). Des agents interagissent dans un environnement dynamique, modélisé par une chaîne de Markov. Les stratégies des agents contrôlent les probabilités de transition entre les étapes et les récompenses gagnées par chaque agent. Les récompenses sont géométriquement pondérées avec le temps. Nous étudions d’abord le cas compétitif. Deux agents agissent égoïstement, le jeu est à somme nulle et les agents contrôlent des ensembles disjoints d’états. Nous élaborons deux algorithmes pour calculer l’équilibre de Nash pour tous les facteurs de pondération suffisamment proches de 1. Puis nous considérons le cas statique coopératif, dans lequel les joueurs peuvent coordonner leurs stratégies. Nous utilisons ces deux algorithmes pour calculer la valeur des conditions dans un jeu de routage. Plusieurs fournisseurs partagent le même réseau. Ensuite, nous traitons des jeux dynamiques et coopératifs sur PDM. Des coalitions peuvent se former tout au long du jeu. Nous montrons comment distribuer la récompense dans chaque état, de sorte que la solution est optimisée pour la communauté et tous les agents sont satisfaits pendant le jeu. Nous appliquons ces concepts à un canal à accès multiple par fil avec un canal quasi-statique. Nous assignons le débit du codage dans chaque état du canal d’une manière équitable. Enfin, nous proposons trois méthodes afin de calculer un intervalle de confiance pour la valeur de Shapley sur les jeux de Markov. Ces méthodes ont une complexité polynomiale en le nombre d’agents, tandis que la complexité du calcul exact est exponentielle. Enfin, nous évaluons la performance de deux stratégies pour sélectionner dynamiquement la bande de fréquence de communication. Nous exploitations une formulation PDM avec un espace d’états dénombrable.
Résumé / Abstract : In this dissertation we deal with the design of strategies for agents interacting in a dynamic environment. The mathematical tool of Game Theory (GT) on Markov Decision Processes (MDPs) is adopted. The agents’ strategies control both the transition probabilities among the states and the rewards earned by each agent. Rewards are geometrically discounted over time. We first study the competitive case, in which two agents act selfishly. The game is zero-sum and the agents control disjoint sets of states. We devise two algorithms to compute the Nash equilibrium for all discount factors close enough to 1. Then we consider the long-run cooperative case, in which agents can coordinate their strategies. We utilize our two algorithms to compute the value of the coalitions in a routing game, in which several providers share the shame the same network and control the routing in disjoint sets of nodes. Next we deal the dynamic cooperative GT on MDPs, in which coalitions can from throughout the game. We show how to enforce a common agreement for which the pay-off is distributed at each state, in a global optimum way and such that no coalition is ever enticed to beak the agreement. We apply these concepts to a wireless multiple access channel, in which the channel is quasi-static. We assign the rate to users in each channel state in a fair and satisfactory manner. Next we provide three methods to compute a confidence interval for Shapley value on Markovian games. Such methods have polynomial complexity in the number of agents, while the complexity of the exact computation is exponential. Two methods are still valid when the values in each state are learned during the game. Finally we assess the performance of two strategies to dynamically select the frequency band to communicate on. We exploit an MDP formulation which uncountable state space.