subject:(Congestion games)

Georgia Tech

1. Zhong, Hai. Congestion game-based task allocation for multi-robot teams.

Degree: MS, Electrical and Computer Engineering, 2020, Georgia Tech

► Multi-robot teams can complete complex missions that are not amenable to an individual robot. A team of heterogeneous robots with complementing capabilities is endowed with… (more)

▼ Multi-robot teams can complete complex missions that are not amenable to an individual robot. A team of heterogeneous robots with complementing capabilities is endowed with advantages to allow deep collaboration in dynamic and complicated environments. Multi-robot Task Allocation (MRTA) presents a fundamental for multi-robot system research. Despite the previous research efforts, there remains a knowledge gap in developing decentralized approaches for MRTA by viewing robots as resources and optimizing the distribution of robots to achieve the best overall performance at the system level. To address this knowledge gap, the objective of this research is to develop decentralized resource allocation algorithms to provide approximate solutions for the MRTA problem. Both standard congestion game theory and weighted congestion game theory are exploited as the theoretical framework to formulate and solve the MRTA problems. Two types of resource allocation problems are considered, one has increasing marginal gain with respect to the number of participating robots, the other has decreasing marginal gain with respect to the number of participating robots. For MRTA problems with homogeneous robot teams, the sequential best response dynamics is integrated in the framework of standard congestion game theory. A concurrent version of best response dynamics with convergence guarantees is developed. In addition, a decentralized dual greedy algorithm is proposed and its convergence to a pure Nash equilibrium is proved. For MRTA problems with heterogeneous robot teams, the best sequential dynamics is shown to converge to pure Nash equilibrium in the framework of weighted congestion games. The suboptimality of the approximate solutions is discussed by λ-μ smoothness technique. Simulations and experiments using robots in the Robotarium are conducted to validate the effectiveness of the proposed algorithms. Advisors/Committee Members: Hutchinson, Seth (advisor), Coogan, Samuel (committee member), Vamvoudakis, Kyriakos (committee member).

Subjects/Keywords: Multi-robot systems; Task allocation; Congestion games

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

Zhong, H. (2020). Congestion game-based task allocation for multi-robot teams. (Masters Thesis). Georgia Tech. Retrieved from http://hdl.handle.net/1853/62843

Chicago Manual of Style (16^th Edition):

Zhong, Hai. “Congestion game-based task allocation for multi-robot teams.” 2020. Masters Thesis, Georgia Tech. Accessed March 06, 2021. http://hdl.handle.net/1853/62843.

MLA Handbook (7^th Edition):

Zhong, Hai. “Congestion game-based task allocation for multi-robot teams.” 2020. Web. 06 Mar 2021.

Vancouver:

Zhong H. Congestion game-based task allocation for multi-robot teams. [Internet] [Masters thesis]. Georgia Tech; 2020. [cited 2021 Mar 06]. Available from: http://hdl.handle.net/1853/62843.

Council of Science Editors:

Zhong H. Congestion game-based task allocation for multi-robot teams. [Masters Thesis]. Georgia Tech; 2020. Available from: http://hdl.handle.net/1853/62843

King Abdullah University of Science and Technology

2. Evangelista, David. Stationary Mean-Field Games with Congestion.

Degree: Computer, Electrical and Mathematical Sciences and Engineering (CEMSE) Division, 2019, King Abdullah University of Science and Technology

URL: http://hdl.handle.net/10754/655679

► Mean-field games (MFG) are models of large populations of rational agents who seek to optimize an objective function that takes into account their state variables… (more)

▼ Mean-field games (MFG) are models of large populations of rational agents who seek to optimize an objective function that takes into account their state variables and the distribution of the state variable of the remaining agents. MFG with congestion model problems where the agents’ motion is hampered in high-density regions. First, we study radial solutions for first- and second-order stationary MFG with congestion on Rd. The radial case, which is one of the simplest non one-dimensional MFG, is relatively tractable. As we observe, the Fokker-Planck equation is integrable with respect to one of the unknowns. Consequently, we obtain a single equation substituting this solution into the Hamilton-Jacobi equation. For the first-order case, we derive explicit formulas; for the elliptic case, we study a variational formulation of the resulting equation. For the first case, we use our approach to compute numerical approximations to the solutions of the corresponding MFG systems. Next, we consider second-order stationary MFG with congestion and prove the existence of stationary solutions. Because moving in congested areas is difficult, agents prefer to move in non-congested areas. As a consequence, the model becomes singular near the zero density. The existence of stationary solutions was previously obtained for MFG with quadratic Hamiltonians thanks to a very particular identity. Here, we develop robust estimates that give the existence of a solution for general subquadratic Hamiltonians. Additionally, we study first-order stationary MFG with congestion with quadratic or power-like Hamiltonians. Using explicit examples, we illustrate two key difficulties: the lack of classical solutions and the existence of areas with vanishing densities. Our main contribution is a new variational formulation for MFG with congestion. With this formulation, we prove the existence and uniqueness of solutions. Finally, we devise a discretization that is combined with optimization algorithms to numerically solve various MFG with congestion. Advisors/Committee Members: Gomes, Diogo A. (advisor), Tempone, Raul (committee member), Santamarina, Carlos (committee member), Fusco, Nicola (committee member).

Subjects/Keywords: mean-field games; congestion problems; stationary problems; calculus f variations

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

Evangelista, D. (2019). Stationary Mean-Field Games with Congestion. (Thesis). King Abdullah University of Science and Technology. Retrieved from http://hdl.handle.net/10754/655679

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Evangelista, David. “Stationary Mean-Field Games with Congestion.” 2019. Thesis, King Abdullah University of Science and Technology. Accessed March 06, 2021. http://hdl.handle.net/10754/655679.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Evangelista, David. “Stationary Mean-Field Games with Congestion.” 2019. Web. 06 Mar 2021.

Vancouver:

Evangelista D. Stationary Mean-Field Games with Congestion. [Internet] [Thesis]. King Abdullah University of Science and Technology; 2019. [cited 2021 Mar 06]. Available from: http://hdl.handle.net/10754/655679.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Evangelista D. Stationary Mean-Field Games with Congestion. [Thesis]. King Abdullah University of Science and Technology; 2019. Available from: http://hdl.handle.net/10754/655679

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

3. 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

URL: http://www.theses.fr/2014PEST1096

►

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… (more)

▼

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 Details Similar Records Cite « Share

❌

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

APA (6^th 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 (16^th 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 March 06, 2021. http://www.theses.fr/2014PEST1096.

MLA Handbook (7^th Edition):

Pradeau, Thomas. “Congestion games with player-specific cost functions : Jeux de congestion avec fonctions de coût spécifiques à chaque joueur.” 2014. Web. 06 Mar 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 Mar 06]. 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

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

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

URL: http://www.theses.fr/2013PA112083

►

La th´eorie de la complexit´e permet de classiﬁer les probl`emes en fonction de leur diﬃcult´e. Le cadre classique dans lequel elle s’applique est celui d’un… (more)

▼

La th´eorie de la complexit´e permet de classiﬁer les probl`emes en fonction de leur diﬃcult´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 eﬀectu´es par des agents ind´ependants qui suivent des objectifs diﬀ´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 aﬁn 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 Details Similar Records Cite « Share

❌

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

APA (6^th 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 (16^th Edition):

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

MLA Handbook (7^th Edition):

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

Vancouver:

Zeitoun X. Complexité des dynamiques de jeux : Complexity of games dynamics. [Internet] [Doctoral dissertation]. Université Paris-Sud – Paris XI; 2013. [cited 2021 Mar 06]. 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

5. Keijzer, B. de. Externalities and Cooperation in Algorithmic Game Theory .

Degree: 2014, Vrije Universiteit Amsterdam

URL: http://hdl.handle.net/1871/51284

Subjects/Keywords: games; algorithms; externalities; congestion; auction; cooperation; optimization

…Congestion Games 3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2… …4.6 Linear Congestion Games . . . . . . . . . . . . 4.7 Symmetric Singleton Linear… …Congestion Games 4.7.1 Uniform Altruism . . . . . . . . . . . 4.7.2 Non-Uniform Altruism… …5.4 Linear Congestion Games . . . . . . . . . . . . . . . . . . . . . . . 5.5 Singleton… …Linear Congestion Games with Identical Delay Functions 5.6 Minsum Machine Scheduling…

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

Keijzer, B. d. (2014). Externalities and Cooperation in Algorithmic Game Theory . (Doctoral Dissertation). Vrije Universiteit Amsterdam. Retrieved from http://hdl.handle.net/1871/51284

Chicago Manual of Style (16^th Edition):

Keijzer, B de. “Externalities and Cooperation in Algorithmic Game Theory .” 2014. Doctoral Dissertation, Vrije Universiteit Amsterdam. Accessed March 06, 2021. http://hdl.handle.net/1871/51284.

MLA Handbook (7^th Edition):

Keijzer, B de. “Externalities and Cooperation in Algorithmic Game Theory .” 2014. Web. 06 Mar 2021.

Vancouver:

Keijzer Bd. Externalities and Cooperation in Algorithmic Game Theory . [Internet] [Doctoral dissertation]. Vrije Universiteit Amsterdam; 2014. [cited 2021 Mar 06]. Available from: http://hdl.handle.net/1871/51284.

Council of Science Editors:

Keijzer Bd. Externalities and Cooperation in Algorithmic Game Theory . [Doctoral Dissertation]. Vrije Universiteit Amsterdam; 2014. Available from: http://hdl.handle.net/1871/51284

6. Lianeas, Athanasios. Παίγνια συμφόρησης: στοχαστικές επεκτάσεις και τεχνικές μείωσης του τιμήματος της αναρχίας.

Degree: 2015, National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ)

URL: http://hdl.handle.net/10442/hedi/38905

► The subject of this thesis is the theoretical analysis and generalization of congestion games models and it aims to provide a study on methods for… (more)

▼ The subject of this thesis is the theoretical analysis and generalization of congestion games models and it aims to provide a study on methods for reducing the Price of Anarchy and a study related to stochastic extensions of congestion games and in which extend the Price of Anarchy may be affected within them. First, the literature that relates mostly to the problems studied is presented and rightafter an extensive presentation of the results of the thesis follows. The problem of finding or approximating the best subnetwork in bottleneck routing games is studied. Although the corresponding problem in additive costs congestion games is almost fully understood, for the problem studied here, the existing results hold for more general games and in fact are much weaker than the ones presented here. For the simplest version of this problem, via a complex reduction, an NP hardness results for finding or approximating the best subnetwork of the underlying network is proved: it is NP hard to approximate the best subnetwork by a factor less than O(n⁰.121) (where n is the number of nodes of the network). In the positive side it is proven that in some subclasses of these games the paradox does not appear at all and also it is given an approximation algorithm for some cases where the NP hardness reductions cannot apply. Results that have to do with Braess paradox in additive costs congestion games are presented. Prior to the work presented here, it has been proved that if the underlying network of a congestion game is a random Erdos-Renyi graph then with high probability it suffers from Braess Paradox. Here, it is proven that the problem of finding the best subnetwork in such random networks can be essentially reduced to the problem of finding the best subnetwork of a network belonging to the simplest class of graphs that may suffer from the paradox. Using a very recent result from the theory of probabilities, it is given a polynomial approximation algorithm for finding best subnetworks in such networks. Then, the expansion properties of Erdos-Renyi graphs are used and an approximately good subnetwork for the initial network is drawn.By slightly changing direction, the basic properties of congestion games with uncertain delays and risk averse users are studied. The classic formulation of congestion games ignores uncertainty in delays that arises in many real life situations. Modelling the cause of uncertainty in delays, two orthogonal models are introduced, one with stochastic players, where each players participates in the game with a given probability and thus the actual delay on the edges that players choose gets uncertain, and another with stochastic edges where each edge, with a given probability, may ‘‘fail’’ and provide greater delay to the players using it. For the arising classes of games, the existence of pure Nash equilibrium and potentials and the behaviour of the price of anarchy is studied. Uniting the above directions, a new way for improving the price of anarchy in congestion games with uncertain delays and risk…

Subjects/Keywords: Παίγνια συμφόρησης; Τίμημα της αναρχίας; Παράδοξο του μπράες; Τυχαίες καθυστερήσεις; Congestion games; Price of anarchy; Braess paradox; Random latencies

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

Lianeas, A. (2015). Παίγνια συμφόρησης: στοχαστικές επεκτάσεις και τεχνικές μείωσης του τιμήματος της αναρχίας. (Thesis). National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Retrieved from http://hdl.handle.net/10442/hedi/38905

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Lianeas, Athanasios. “Παίγνια συμφόρησης: στοχαστικές επεκτάσεις και τεχνικές μείωσης του τιμήματος της αναρχίας.” 2015. Thesis, National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Accessed March 06, 2021. http://hdl.handle.net/10442/hedi/38905.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Lianeas, Athanasios. “Παίγνια συμφόρησης: στοχαστικές επεκτάσεις και τεχνικές μείωσης του τιμήματος της αναρχίας.” 2015. Web. 06 Mar 2021.

Vancouver:

Lianeas A. Παίγνια συμφόρησης: στοχαστικές επεκτάσεις και τεχνικές μείωσης του τιμήματος της αναρχίας. [Internet] [Thesis]. National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ); 2015. [cited 2021 Mar 06]. Available from: http://hdl.handle.net/10442/hedi/38905.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Lianeas A. Παίγνια συμφόρησης: στοχαστικές επεκτάσεις και τεχνικές μείωσης του τιμήματος της αναρχίας. [Thesis]. National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ); 2015. Available from: http://hdl.handle.net/10442/hedi/38905

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Illinois – Urbana-Champaign

7. Yekkehkhany, Ali. Risk-averse multi-armed bandits and game theory.

Degree: PhD, Electrical & Computer Engr, 2020, University of Illinois – Urbana-Champaign

URL: http://hdl.handle.net/2142/108439

► The multi-armed bandit (MAB) and game theory literature is mainly focused on the expected cumulative reward and the expected payoffs in a game, respectively. In… (more)

▼ The multi-armed bandit (MAB) and game theory literature is mainly focused on the expected cumulative reward and the expected payoffs in a game, respectively. In contrast, the rewards and the payoffs are often random variables whose expected values only capture a vague idea of the overall distribution. The focus of this dissertation is to study the fundamental limits of the existing bandits and game theory problems in a risk-averse framework and propose new ideas that address the shortcomings. The author believes that human beings are mostly risk-averse, so studying multi-armed bandits and game theory from the point of view of risk aversion, rather than expected reward/payoff, better captures reality. In this manner, a specific class of multi-armed bandits, called explore-then-commit bandits, and stochastic games are studied in this dissertation, which are based on the notion of Risk-Averse Best Action Decision with Incomplete Information (R-ABADI, Abadi is the maiden name of the author's mother). The goal of the classical multi-armed bandits is to exploit the arm with the maximum score defined as the expected value of the arm reward. Instead, we propose a new definition of score that is derived from the joint distribution of all arm rewards and captures the reward of an arm relative to those of all other arms. We use a similar idea for games and propose a risk-averse R-ABADI equilibrium in game theory that is possibly different from the Nash equilibrium. The payoff distributions are taken into account to derive the risk-averse equilibrium, while the expected payoffs are used to find the Nash equilibrium. The fundamental properties of games, e.g. pure and mixed risk-averse R-ABADI equilibrium and strict dominance, are studied in the new framework and the results are expanded to finite-time games. Furthermore, the stochastic congestion games are studied from a risk-averse perspective and three classes of equilibria are proposed for such games. It is shown by examples that the risk-averse behavior of travelers in a stochastic congestion game can improve the price of anarchy in Pigou and Braess networks. Furthermore, the Braess paradox does not occur to the extent proposed originally when travelers are risk-averse. We also study an online affinity scheduling problem with no prior knowledge of the task arrival rates and processing rates of different task types on different servers. We propose the Blind GB-PANDAS algorithm that utilizes an exploration-exploitation scheme to load balance incoming tasks on servers in an online fashion. We prove that Blind GB-PANDAS is throughput optimal, i.e. it stabilizes the system as long as the task arrival rates are inside the capacity region. The Blind GB-PANDAS algorithm is compared to FCFS, Max-Weight, and c-mu-rule algorithms in terms of average task completion time through simulations, where the same exploration-exploitation approach as Blind GB-PANDAS is used for Max-Weight and c-μ-rule. The extensive simulations show that the Blind GB-PANDAS algorithm conspicuously… Advisors/Committee Members: Nagi, Rakesh (advisor), Nagi, Rakesh (Committee Chair), Hajek, Bruce (committee member), Shomorony, Ilan (committee member), Srikant, Rayadurgam (committee member).

Subjects/Keywords: Online Learning; Multi-Armed Bandits; Exploration-Exploitation; Explore-Then-Commit Bandits; Risk-Aversion; Game Theory; Stochastic Game Theory; Congestion Games; Affinity Scheduling; MapReduce; Data Center

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

Yekkehkhany, A. (2020). Risk-averse multi-armed bandits and game theory. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/108439

Chicago Manual of Style (16^th Edition):

Yekkehkhany, Ali. “Risk-averse multi-armed bandits and game theory.” 2020. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed March 06, 2021. http://hdl.handle.net/2142/108439.

MLA Handbook (7^th Edition):

Yekkehkhany, Ali. “Risk-averse multi-armed bandits and game theory.” 2020. Web. 06 Mar 2021.

Vancouver:

Yekkehkhany A. Risk-averse multi-armed bandits and game theory. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2020. [cited 2021 Mar 06]. Available from: http://hdl.handle.net/2142/108439.

Council of Science Editors:

Yekkehkhany A. Risk-averse multi-armed bandits and game theory. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2020. Available from: http://hdl.handle.net/2142/108439

8. Παναγοπούλου, Παναγιώτα. Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων.

Degree: 2005, University of Patras

URL: http://nemertes.lis.upatras.gr/jspui/handle/10889/141

► Στην παρούσα διπλωματικής εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων, και συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παιγνίου Συμφόρησης, ώστε να αναλύσουμε την… (more)

▼ Στην παρούσα διπλωματικής εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων, και συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παιγνίου Συμφόρησης, ώστε να αναλύσουμε την επίδραση που έχει στην καθολική απόδοση ενός δικτύου και γενικότερα ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Αρχικά ασχολούμαστε με το πρόβλημα της εγωιστικής δρομολόγησης φορτίων από μια κοινή πηγή προς έναν κοινό προορισμό σε ένα δίκτυο επικοινωνίας. Σε ένα τέτοιο περιβάλλον οι χρήστες επιλέγουν εγωιστικά τις στρατηγικές τους, οι οποίες στην περίπτωση μας αντιστοιχούν σε μονοπάτια από την πηγή προς τον προορισμό Όταν οι χρήστες δρομολογούν τα φορτία τους σύμφωνα με τις στρατηγικές που επιλέγουν, έρχονται αντιμέτωποι με μια καθυστέρηση που προκαλείται από τα φορτία όλων των χρηστών καθώς διαμοιράζονται τις ακμές. Κάθε χρήστης στοχεύει στην ελαχιστοποίηση του εγωιστικού τον κόστους, που αντιστοιχεί σε αυτήν ακριβώς την καθυστέρηση, γεγονός που συνήθως έρχεται σε αντίθεση με το στόχο της βελτιστοποίησης της καθολικής απόδοσης του δικτύου. Η θεωρία των ισορροπιών Nash μας παρέχει μία σημαντική αρχή επίλυσης για τέτοιου είδους καταστάσεις: μια ισορροπία Nash, είναι μια κατάσταση του συστήματος τέτοια ώστε δεν υπάρχει κάποιος χρήστης που να μπορεί να μειώσει το εγωιστικό του κόστος αλλάζοντας μονομερώς τη στρατηγική του. Σε ένα τέτοιο δίκτυο λοιπόν περιμένουμε οι χρήστες να καταλήξουν σε μια ισορροπία Nash. Ωστόσο, ο υπολογισμός μιας τέτοιας ισορροπίας παραμένει ένα πρόβλημα του οποίου η πολυπλοκότητα είναι, στη γενική περίπτωση, άγνωστη. Στα πλαίσια αυτής της διπλωματικής εργασίας δείχνουμε πειραματικά ότι ο υπολογισμός μιας αγνής ισορροπίας Nash σε ένα περιβάλλον εγωιστικής δρομολόγησης, όπου η καθυστέρηση σε κάθε ακμή ισούται με το φορτίο της. μπορεί να γίνει σε πολυωνυμικό χρόνο για μια μεγάλη ποικιλία δικτύων και κατανομών των φορτίων των χρηστών. Επιπλέον, προτείνουμε μια αρχική ανάθεση χρηστών σε μονοπάτια η οποία, όπως δείχνουν οι προσομοιώσεις μας, οδηγεί σε μια αξιοσημείωτη μείωση του συνολικού αριθμού των βημάτων που απαιτούνται ώστε να καταλήξουμε σε μια αγνή ισορροπία Nash. Επίσης αποδεικνύουμε την ύπαρξη αγνών ισορροπιών Nash και για την περίπτωση που η καθυστέρηση σε κάθε ακμή είναι εκθετική συνάρτηση του φορτίου της. Στη συνέχεια προτείνουμε και αναλύουμε ένα νέο μηχανισμό κόστους που θέτει τιμές για την ανταγωνιστική χρησιμοποίηση πόρων από ένα σύνολο χρηστών. Το βασικό πλεονέκτημα αυτού του μηχανισμού είναι ότι οι πόροι θέτουν τα κόστη με έναν ισοδύναμο, δίκαιο τρόπο, και το πλέον σημαντικό είναι ότι κανένας πόρος δεν επωφελείται εις βάρος των χρηστών. Αυτός ο δίκαιος μηχανισμός κόστους επαγάγει ένα μη συνεργατικό παίγνιο μεταξύ των χρηστών, για το οποίο αναλύουμε τις ισορροπίες Nash. Αποδεικνύουμε ότι δεν υπάρχουν αγνές ισορροπίες Nash, εκτός από την περίπτωση όπου όλα τα φορτία είναι ίσα, ενώ δείχνουμε ότι υπάρχει πάντα μία πλήρως μικτή ισορροπία Nash. Επίσης αναλύουμε για το παίγνιο αυτό το Κόστος της Αναρχίας, που εκφράζει την απόκλιση της… Advisors/Committee Members: Σπυράκης, Παύλος, Panagopoulou, Panagiota, Σπυράκης, Παύλος, Κακλαμάνης, Χρήστος, Κυρούσης, Ελευθέριος.

Subjects/Keywords: Θεωρία παιγνίων; Παίγνια συμφόρησης; Παίγνια δυναμικού; 519.82; Game theory; Congestion games; Potential games; Price of anarchy

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

Παναγοπούλου, �. (2005). Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων. (Masters Thesis). University of Patras. Retrieved from http://nemertes.lis.upatras.gr/jspui/handle/10889/141

Chicago Manual of Style (16^th Edition):

Παναγοπούλου, Παναγιώτα. “Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων.” 2005. Masters Thesis, University of Patras. Accessed March 06, 2021. http://nemertes.lis.upatras.gr/jspui/handle/10889/141.

MLA Handbook (7^th Edition):

Παναγοπούλου, Παναγιώτα. “Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων.” 2005. Web. 06 Mar 2021.

Vancouver:

Παναγοπούλου �. Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων. [Internet] [Masters thesis]. University of Patras; 2005. [cited 2021 Mar 06]. Available from: http://nemertes.lis.upatras.gr/jspui/handle/10889/141.

Council of Science Editors:

Παναγοπούλου �. Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων. [Masters Thesis]. University of Patras; 2005. Available from: http://nemertes.lis.upatras.gr/jspui/handle/10889/141

9. Χριστοδούλου, Γεώργιος. Παιγνιοθεωρητική μελέτη δικτύων.

Degree: 2006, National and Kapodistrian University of Athens; Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ)

URL: http://hdl.handle.net/10442/hedi/22183

Subjects/Keywords: Τιμή αναρχίας; Μηχανισμοί; Παίγνια συμφόρησης; Φιλαλήθεια; Θεωρία παιγνίων; Price of anarchy; Mechanisms; Congestion games; Truthfulness; Game theory

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

Χριστοδούλου, . �. (2006). Παιγνιοθεωρητική μελέτη δικτύων. (Thesis). National and Kapodistrian University of Athens; Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ). Retrieved from http://hdl.handle.net/10442/hedi/22183

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Χριστοδούλου, Γεώργιος. “Παιγνιοθεωρητική μελέτη δικτύων.” 2006. Thesis, National and Kapodistrian University of Athens; Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ). Accessed March 06, 2021. http://hdl.handle.net/10442/hedi/22183.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Χριστοδούλου, Γεώργιος. “Παιγνιοθεωρητική μελέτη δικτύων.” 2006. Web. 06 Mar 2021.

Vancouver:

Χριστοδούλου �. Παιγνιοθεωρητική μελέτη δικτύων. [Internet] [Thesis]. National and Kapodistrian University of Athens; Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ); 2006. [cited 2021 Mar 06]. Available from: http://hdl.handle.net/10442/hedi/22183.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Χριστοδούλου �. Παιγνιοθεωρητική μελέτη δικτύων. [Thesis]. National and Kapodistrian University of Athens; Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ); 2006. Available from: http://hdl.handle.net/10442/hedi/22183

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

10. Massicot, Olivier. On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks.

Degree: MS, Aerospace Engineering, 2019, University of Illinois – Urbana-Champaign

URL: http://hdl.handle.net/2142/106130

► We study the influence of information design on routing in the presence of vagaries, following the canonical congestion game approach. We allow a central controller… (more)

Subjects/Keywords: Road-traffic; congestion; signaling games; signal; information design; game theory; price of anarchy; Wardrop equilibrium; Bayesian game

…Chapter 2 Selfish routing 2.1 Routing as a congestion game In this first section, the… …reader will find how a road network is canonically modeled as a congestion game and the general… …the work on potential games of Monderer and Shapley [30]. The model we will use… …This game is a congestion game, so we should expect it to be a potential game. It is indeed… …theory literature on best-response dynamics of potential games, although we only focus on a…

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

Massicot, O. (2019). On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks. (Thesis). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/106130

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Massicot, Olivier. “On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks.” 2019. Thesis, University of Illinois – Urbana-Champaign. Accessed March 06, 2021. http://hdl.handle.net/2142/106130.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Massicot, Olivier. “On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks.” 2019. Web. 06 Mar 2021.

Vancouver:

Massicot O. On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks. [Internet] [Thesis]. University of Illinois – Urbana-Champaign; 2019. [cited 2021 Mar 06]. Available from: http://hdl.handle.net/2142/106130.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Massicot O. On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks. [Thesis]. University of Illinois – Urbana-Champaign; 2019. Available from: http://hdl.handle.net/2142/106130

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

		in
And / Or
		in
And / Or
		in
And / Or
		in

Open Access Theses and Dissertations