Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(Jeux de congestion). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Pradeau, Thomas. Congestion games with player-specific cost functions : Jeux de congestion avec fonctions de coût spécifiques à chaque joueur.

Degree: Docteur es, Mathématiques, 2014, Université Paris-Est

Nous considérons des jeux de congestion sur des graphes. Dans les jeux non-atomiques, nous considérons un ensemble de joueurs infinitésimaux. Chaque joueur veut aller d'un sommet à un autre en choisissant une route de coût minimal. Le coût de chaque route dépend du nombre de joueur la choisissant. Dans les jeux atomiques divisibles, nous considérons un ensemble de joueurs ayant chacun une demande à transférer d'un sommet à un autre, en la subdivisant éventuellement sur plusieurs routes. Dans ces jeux, un équilibre de Nash est atteint lorsque chaque joueur a choisi une stratégie de coût minimal. L'existence d'un équilibre de Nash est assurée sous de faibles hypothèses. Les principaux sujets sont l'unicité, le calcul, l'efficacité et la sensibilité de l'équilibre de Nash. De nombreux résultats sont connus dans le cas où les joueurs sont tous impactés de la même façon par la congestion. Le but de cette thèse est de généraliser ces résultats au cas où les joueurs ont des fonctions de coût différentes. Nous obtenons des résultats sur l'unicité de l'équilibre dans les jeux non-atomiques. Nous donnons deux algorithmes capables de calculer un équilibre dans les jeux non-atomiques lorsque les fonctions de coût sont affines. Nous obtenons une borne sur le prix de l'anarchie pour certains jeux atomiques divisibles et prouvons qu'il n'est pas borné en général, même lorsque les fonctions sont affines. Enfin, nous prouvons des résultats sur la sensibilité de l'équilibre par rapport à la demande dans les jeux atomiques divisibles

We consider congestion games on graphs. In nonatomic games, we are given a set of infinitesimal players. Each player wants to go from one vertex to another by taking a route of minimal cost, the cost of a route depending on the number of players using it. In atomic splittable games, we are given a set of players with a non-negligible demand. Each player wants to ship his demand from one vertex to another by dividing it among different routes. In these games, we reach a Nash equilibrium when every player has chosen a minimal-cost strategy. The existence of a Nash equilibrium is ensured under mild conditions. The main issues are the uniqueness, the computation, the efficiency and the sensitivity of the Nash equilibrium. Many results are known in the specific case where all players are impacted in the same way by the congestion. The goal of this thesis is to generalize these results in the case where we allow player-specific cost functions. We obtain results on uniqueness of the equilibrium in nonatomic games. We give two algorithms able to compute a Nash equilibrium in nonatomic games when the cost functions are affine. We find a bound on the price of anarchy for some atomic splittable games, and prove that it is unbounded in general, even when the cost functions are affine. Finally we find results on the sensitivity of the equilibrium to the demand in atomic splittable games

Advisors/Committee Members: Meunier, Frédéric (thesis director).

Subjects/Keywords: Jeux de congestion; Théorie algorithmique des jeux; Jeux multiclasses; Jeux atomiques; Jeux non-Atomiques; Prix de l'anarchie; Network congestion games; Price of anarchy; Algorithmic game theory; Atomic games; Nonatomic games

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Pradeau, T. (2014). Congestion games with player-specific cost functions : Jeux de congestion avec fonctions de coût spécifiques à chaque joueur. (Doctoral Dissertation). Université Paris-Est. Retrieved from http://www.theses.fr/2014PEST1096

Chicago Manual of Style (16th Edition):

Pradeau, Thomas. “Congestion games with player-specific cost functions : Jeux de congestion avec fonctions de coût spécifiques à chaque joueur.” 2014. Doctoral Dissertation, Université Paris-Est. Accessed April 16, 2021. http://www.theses.fr/2014PEST1096.

MLA Handbook (7th Edition):

Pradeau, Thomas. “Congestion games with player-specific cost functions : Jeux de congestion avec fonctions de coût spécifiques à chaque joueur.” 2014. Web. 16 Apr 2021.

Vancouver:

Pradeau T. Congestion games with player-specific cost functions : Jeux de congestion avec fonctions de coût spécifiques à chaque joueur. [Internet] [Doctoral dissertation]. Université Paris-Est; 2014. [cited 2021 Apr 16]. Available from: http://www.theses.fr/2014PEST1096.

Council of Science Editors:

Pradeau T. Congestion games with player-specific cost functions : Jeux de congestion avec fonctions de coût spécifiques à chaque joueur. [Doctoral Dissertation]. Université Paris-Est; 2014. Available from: http://www.theses.fr/2014PEST1096


Université Paris-Sud – Paris XI

2. Zeitoun, Xavier. Complexité des dynamiques de jeux : Complexity of games dynamics.

Degree: Docteur es, Informatique, 2013, Université Paris-Sud – Paris XI

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…

Advisors/Committee Members: Rougemont, Michel de (thesis director).

Subjects/Keywords: Complexité; Equilibre de Nash; Dynamique; Jeux de congestion; Couplage stable; Complexity; Nash equilibrium; Dynamics; Congestion games; Stable matching

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Zeitoun, X. (2013). Complexité des dynamiques de jeux : Complexity of games dynamics. (Doctoral Dissertation). Université Paris-Sud – Paris XI. Retrieved from http://www.theses.fr/2013PA112083

Chicago Manual of Style (16th Edition):

Zeitoun, Xavier. “Complexité des dynamiques de jeux : Complexity of games dynamics.” 2013. Doctoral Dissertation, Université Paris-Sud – Paris XI. Accessed April 16, 2021. http://www.theses.fr/2013PA112083.

MLA Handbook (7th Edition):

Zeitoun, Xavier. “Complexité des dynamiques de jeux : Complexity of games dynamics.” 2013. Web. 16 Apr 2021.

Vancouver:

Zeitoun X. Complexité des dynamiques de jeux : Complexity of games dynamics. [Internet] [Doctoral dissertation]. Université Paris-Sud – Paris XI; 2013. [cited 2021 Apr 16]. Available from: http://www.theses.fr/2013PA112083.

Council of Science Editors:

Zeitoun X. Complexité des dynamiques de jeux : Complexity of games dynamics. [Doctoral Dissertation]. Université Paris-Sud – Paris XI; 2013. Available from: http://www.theses.fr/2013PA112083

3. Simo Kanmeugne, Patrick. Simulation crédible des déplacements de piétons en temps réel : modèle microscopique à influence macroscopique : Real-time simulation of autonomous pedestrians navigation : a macroscopic-influenced microscopic model.

Degree: Docteur es, Informatique, 2014, Université Pierre et Marie Curie – Paris VI

Le but de nos travaux est de définir des algorithmes permettant de simuler les déplacements de piétons dans un environnement urbain, en temps réel, et de manière crédible. Les modèles existants pour ce type d'exercice sont développés suivant deux types d'approches : microscopiques - les piétons sont modélisés comme des agents autonomes - et macroscopiques - les piétons sont considérés comme soumis à des lois d'écoulement. Selon nous, ces deux approches ne s'opposent pas, mais se complètent mutuellement. Aussi nous inspirons-nous des jeux de congestion et des SMA pour proposer une formulation générique du problème de déplacement de piétons. Nous introduisons la notion de ressource de navigation, décrite comme une région de l'espace que les agents utilisent pour atteindre leurs objectifs, et via lesquelles ils interagissent pour estimer leurs dépenses énergétiques, et nous proposons une stratégie de déplacement basée sur les heuristiques taboues. Le concept d'environnement issu du paradigme SMA s'avère adapté pour appréhender la complexité de la simulation. L'environnement est vu comme un composant indépendant et ontologiquement différent des agents. Une partie de la dynamique de la simulation est ainsi déléguée à l'environnement sans altérer l'autonomie des agents, ce qui favorise la crédibilité des résultats et le passage à l'échelle. Nous comparons notre modèle avec un modèle microscopique standard via plusieurs scénarii de simulation et montrons que notre modèle produit des résultats plus crédibles du point de vue d'un observateur extérieur et plus proches des études empiriques connues du déplacement des piétons.

In this work, we focus on real-time simulation of autonomous pedestrians navigation. Existing models for this purpose tend to diverge on whether to build on pedestrians' characteristics and local interactions - microscopic approaches - or to focus on pedestrians' flow regardless of individual characteristics - macroscopic approaches. Our position is that the two approaches should not be separated. Thus, we introduce a Macroscopic-Influenced Microscopic approach which aims at reducing the gap between microscopic and macroscopic approaches by providing credible walking paths for a potentially highly congested crowd of autonomous pedestrians. Our approach originates from a least-effort formulation of the navigation task, which allows us to consistently account for congestion at every levels of decision. We use the multi-agent paradigm and describe pedestrians as autonomous and situated agents who plan dynamically for energy efficient paths, and interact with each other through the environment. The navigable space is considered as a set of contiguous resources that agents use to build their paths. We emulate the dynamic path computation for each agent with an evolutionary search algorithm that implement a tabu search heuristic, especially designed to be executed in real-time and autonomously. We have compared an implementation of our approach with a standard microscopic model, against low-density and high…

Advisors/Committee Members: El Fallah Seghrouchni, Amal (thesis director).

Subjects/Keywords: Simulation comportementale; Systèmes Multi-Agents; Jeux de congestion; Planification dynamique; Interactions; Crédibilité.; Multi-agent system; Behavorial simulation; 004

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Simo Kanmeugne, P. (2014). Simulation crédible des déplacements de piétons en temps réel : modèle microscopique à influence macroscopique : Real-time simulation of autonomous pedestrians navigation : a macroscopic-influenced microscopic model. (Doctoral Dissertation). Université Pierre et Marie Curie – Paris VI. Retrieved from http://www.theses.fr/2014PA066597

Chicago Manual of Style (16th Edition):

Simo Kanmeugne, Patrick. “Simulation crédible des déplacements de piétons en temps réel : modèle microscopique à influence macroscopique : Real-time simulation of autonomous pedestrians navigation : a macroscopic-influenced microscopic model.” 2014. Doctoral Dissertation, Université Pierre et Marie Curie – Paris VI. Accessed April 16, 2021. http://www.theses.fr/2014PA066597.

MLA Handbook (7th Edition):

Simo Kanmeugne, Patrick. “Simulation crédible des déplacements de piétons en temps réel : modèle microscopique à influence macroscopique : Real-time simulation of autonomous pedestrians navigation : a macroscopic-influenced microscopic model.” 2014. Web. 16 Apr 2021.

Vancouver:

Simo Kanmeugne P. Simulation crédible des déplacements de piétons en temps réel : modèle microscopique à influence macroscopique : Real-time simulation of autonomous pedestrians navigation : a macroscopic-influenced microscopic model. [Internet] [Doctoral dissertation]. Université Pierre et Marie Curie – Paris VI; 2014. [cited 2021 Apr 16]. Available from: http://www.theses.fr/2014PA066597.

Council of Science Editors:

Simo Kanmeugne P. Simulation crédible des déplacements de piétons en temps réel : modèle microscopique à influence macroscopique : Real-time simulation of autonomous pedestrians navigation : a macroscopic-influenced microscopic model. [Doctoral Dissertation]. Université Pierre et Marie Curie – Paris VI; 2014. Available from: http://www.theses.fr/2014PA066597

.