First of all, I would like to thank my three amazing supervisors Nathalie Bertrand, Nicolas Markey, and Ocan Sankur for being there through thick and thin during the journey of these past three years. From the very rst week of allowing me to exibly change the topic to the last week of suggesting minute details on how I can improve my presentation on the D-day, it goes without mentioning that this dissertation wouldn't see the light of the day without them. They taught me how to lter out the literature without being completely lost, when to stop spending time on a harder problem and to try out easier ones in order to boost con dence, how to present without making my audience asleep, how to write proofs with clarity and reread them until the last typo has been found and then once more -I hope I'll be able to carry forward these immense valuable lessons in the journey ahead to some degree of success. Last but absolutely not the least, during the pandemic, their all-out mental support have been an immense source of strength, especially while the daily news from far home was making me numb. I would not dare to thank them for their humanity, the least I can do is humbly acknowledging their e ort for being there for me beyond academia.

Of course, even though the dissertation has been made out o the past three years, the training to come at this point has been started long ago. I would like to take this opportunity to thank all my teachers for whom I got to be interested in mathematical sciences in the rst place from the very school days. Special mention goes to Sanjay sir and Alok babu from my secondary and high-school maths training. I thank my professors from CMI, for guiding me in various stages of my learning, upbringing, whenever I have been in doubt, and even when I thought I was not. Especially, I cannot thank enough to Prof. Srivathsan for his immense e ort to make his classes the best learning experience and most enjoyable ever, and for being the ultimate go to person to a generation of students for any academic guidance that we needed in CMI and beyond.

Even though the life outside the workplace had started on a good note with travelling places and visiting friends whenever I got a chance, the pandemic inevitably doomed it for all of us after March . Since then, and of course before that as well, it is the friends and peers who kept the lights up when I needed it the most. It was Rituraj, Arif, Neetu, Anirban, and Ayan who made the days in Rennes the happening they were, and when they eventually left, it was Shabina, Pooja, Soumen, and Arun who took the baston for last couple of months with cheers, foods, movies and more. I thank them all for all the memories we created together. I am grateful to Ali and Masha, for inviting me over and over for beautiful Iranian dishes, for the most lovely discussion over politics, movies, and art, and for accompanying me from the very rst day of moving to the very last day of last-minute shopping. I also thank Quentin for introducing me to the beautiful art of playing piano. Despite having the language barriers that we had, he has been the most patient, motivating, fun and loving instructor that I could ever get.

When the locked down happened, and kept happening in phases, it is the good old peers from CMI who came together to keep each other's sanity via daily dose of discord voice chats, and

seasonal game sessions. Those are Sougata, Ritam, Prantar, Arghya, Debraj, Anirban, Soumyajit, Rajarshi, and I am thanking them all by not revealing their usernames out here. Special mention to Nisarg for always being there, across the pond, connected to via our countless late night calls: we talked, we listened, we complained, we shared, and we grew up from liberalism to the left.

Last but not the least, I am forever grateful to my parents and my sister for their constant encouragement, cooperation, and for understanding my occasional tantrums when I might not have been in my best. I know the journey had been tough for them too, specially during the pandemic, and for all the other instances I could not physically be there when they needed me the most. I dedicate this thesis to them.

iii R M Lorsque nous nous rendons d'un endroit à un autre, nous voulons généralement éviter autant que possible les embouteillages, et nous avons souvent tendance à changer notre itinéraire prédestiné si nous voyons que les mises à jour sur notre itinéraire choisi montrent un tra c important. Mais il peut arriver que d'autres personnes, qui étaient déterminées à choisir le même itinéraire, voient la même mise à jour, et changent leur itinéraire pour celui que nous sommes en train de changer. Il en résulte une situation dans laquelle une route précédemment peu fréquentée devient plus fréquentée, et une route plus fréquentée peut devenir moins fréquentée qu'auparavant. Et, nous sommes de retour à la case départ.

Mais il peut y avoir des moyens de résoudre ce problème : ( ) les navetteurs peuvent décider entre eux qui changera et qui ne changera pas, ou ( ) la mise à jour peut venir directement aux navetteurs avec une solution de changement de manière à ce que s'ils suivent tous la suggestion, ils deviennent en fait meilleurs. On peut se demander comment les navetteurs communiquent et conduisent de manière coopérative a n de tirer pro t de ce type de situation. Dans un avenir prévisible avec les véhicules automatisés [ , ], on imagine que les communications de véhicule à véhicule (V V) ou de véhicule à infrastructure (V I) seront réalisables [ ]. Dans cette thèse, notre préoccupation n'est pas de savoir comment ces communications sont réalisables, nous nous intéressons plutôt à des problèmes tels que, si une telle communication est e ectivement établie, quel type de solution une telle prise de décision coopérative garantirait la réduction de l'e et de congestion, et comment synthétiser une telle plani cation des itinéraires pour les navetteurs, qui assure cette garantie.

Tout comme le tra c routier, un autre domaine où le contrôle de la congestion est pertinent dans notre vie quotidienne est l'internet. Comme nous passons de plus en plus de temps sur l'internet (surtout depuis que la pandémie nous a tous condamnés), nous rencontrons chaque jour un problème ou un autre. Un jour, nous devons éteindre notre appareil photo pendant une réunion en ligne entre deux personnes, tandis qu'un autre jour de chance, nous participons à un séminaire en ligne avec trente personnes. Télécharger un chier aujourd'hui peut prendre deux fois plus de temps qu'hier pour la même taille. Nous sommes tous passés par là.

Bien que les raisons de ce phénomène puissent être multiples, comme l'indisponibilité ou la rupture de liaisons, les paquets de données peuvent traverser di érents noeuds de réseau interne (routeurs), mais l'une des principales raisons des uctuations de performances sur l'internet est la congestion du réseau. Le contrôle de la congestion est donc crucial dans l'Internet d'aujourd'hui. La forme prédominante de contrôle de la congestion est incarnée par le protocole de contrôle de la transmission (TCP) [ ], qui fournit un moyen able de transmission des données de bout en bout, et évite également tout congestion collapse. Intuitivement, ce protocole fonctionne dans l'intérêt d'un réseau dans son ensemble (ou du moins d'une partie su samment grande), et par conséquent, du point de vue d'un point d'extrémité, il n'est pas toujours dans son intérêt de se conformer au protocole. Cela donne lieu à une analyse de la théorie des jeux [ , , , ] des protocoles de type TCP dans la littérature : Akella et al. [ ], en utilisant l'analyse de la théorie des jeux de TCP, compare l'e cacité des comportements stables entre les variations récentes de TCP (par ex. SACK) avec les variations traditionnelles, et concluent que les variations récentes sont plus sensibles au comportement égoïste ; Lopez et al. [ ] étudient le protocole basé sur les fontaines (FBP), et comparent les performances du mécanisme stable entre FBP et TCP en présence de congestion ; Kesselman et al. [ ] mesurent la dégradation des performances à cause de la congestion dans un modèle de tra c de type TCP, et proposent une politique de détection précoce pour réduire la dégradation, et ce ne sont là que quelques exemples parmi une vaste littérature sur l'analyse de la théorie des jeux des protocoles de type TCP. Il s'agit là de quelques exemples tirés d'une vaste littérature sur l'analyse de la théorie des jeux des protocoles de type TCP. L'un des points communs entre toutes ces études est qu'elles portent sur les performances des comportements stables d'Internet dans des contextes di érents mais spéci ques lorsque les utilisateurs naux interagissent de manière égoïste et provoquent des congestions. De plus, dans ces contextes spéci ques, ces études se concentrent principalement sur la mesure du pire scénario d'un modèle sans véri er directement les propriétés d'une instance de ces modèles.

En théorie, ce type de scénarios pratiques est souvent abstrait dans des jeux de graphes, et des problèmes similaires sont étudiés sur ces graphes, qui commentent, le plus souvent, les pires/meilleurs scénarios dans cette classe particulière de jeux. Nous en discutons davantage dans la section de ce chapitre. Dans cette thèse, nous considérons ce domaine d'un point de vue méthodes formelles, où au lieu de traiter le pire/meilleur scénario pour un modèle de jeu de congestion, nous sommes plus intéressés par le type de performance de stabilité qui peut être garanti dans une instance donnée de ce modèle. C'est pourquoi nous commençons par présenter les méthodes formelles et la manière dont elles abordent les questions de théorie des jeux, avant d'examiner plus en détail la manière dont nous abordons l'analyse des jeux de congestion dans une perspective de véri cation.

C M

De nos jours, nous sommes fortement dépendants des systèmes informatisés : du smartphone à la navette spatiale, du distributeur automatique de billets au véhicule automatisé, du contrôle du tra c aux centrales nucléaires -la liste s'allonge chaque jour, tout comme notre dépendance à leur égard. Nous voulons que ces systèmes soient à l'abri des défaillances. Lorsqu'un système tombe en panne, nous sommes confrontés à des crises allant de pertes nancières à des pertes de vies humaines. Par exemple, un défaut fatal dans le logiciel de contrôle [ ] du missile Ariane-a provoqué un crash à peine secondes après son lancement le juin . Un défaut de logiciel dans la partie contrôle de l'appareil de radiothérapie Therac-[ ] a causé la mort de six patients cancéreux entre et . En informatique, méthodes formelles est un domaine dans lequel nous raisonnons formellement sur un tel système informatisé : nous véri ons les propriétés d'un système donné (model checking), et construisons des modèles qui sont corrects par construction (synthèse) à partir d'une spéci cation donnée. Dans les problèmes de model checking, une entrée consiste généralement en un système et une spéci cation logique (par exemple une formule en logique temporelle [ ]), et le problème v Résumé de la thèse demande si le système satisfait la spéci cation. Selon le type de formules considérées comme spéci cation, le problème de model checking demande si une ou toutes les exécutions du système en question satisfont la spéci cation.

En réalité, un concepteur/contrôleur peut ne contrôler que des parties du système entier, et il peut vouloir véri er une spéci cation sur les exécutions du système qui implique ces parties. Par exemple, considérons un ascenseur dans un bâtiment comme le système, et la spéci cation est que lorsque quelqu'un appelle d'un certain étage, l'ascenseur doit s'arrêter à cet étage pour prendre cette personne. Cette spéci cation concerne une partie particulière du système, qui n'a presque rien à voir avec des exécutions telles que : ne pas rester coincé entre les étages, ouvrir la porte lorsqu'il s'arrête à un étage ou ne pas ouvrir la porte lorsqu'il passe d'un étage à l'autre, etc. Par conséquent, pour véri er si l'ascenseur satisfait à la spéci cation, nous ne devons ni véri er toutes les exécutions, c'est su sant, ni véri er une seule exécution, ce qui ne peut garantir que l'arrêt d'un seul appel.

Ces types de problèmes dans les méthodes formelles sont résolus en utilisant l'approche de la théorie des jeux : dans notre exemple, la personne qui appelle l'ascenseur est le environnement, et l'ascenseur lui-même est le système. Dans ces jeux à deux joueurs entre le système et l'environnement, l'environnement vise à montrer que le système est défectueux, tandis que le système tente d'établir qu'il ne l'est pas. En d'autres termes, le problème de véri cation exige que le concepteur/contrôleur puisse faire en sorte que le système gagne contre tout comportement de l'environnement. Ces jeux sont appelés jeux à somme nulle, et une solution dans un tel jeu est une stratégie gagnante. D'autre part, il est possible que les concepteurs des di érents composants d'un système soient eux-mêmes en concurrence les uns avec les autres pour certaines ressources. Dans ce cas, au lieu de gagner ou de perdre le jeu, chaque joueur obtient un gain. Le gain peut être positif, ce que l'on appelle généralement une récompense, et il peut être négatif, ce que l'on appelle un coût. Contrairement à la victoire dans un jeu, l'objectif du joueur est ici d'optimiser son gain : maximiser s'il s'agit d'une récompense, minimiser s'il s'agit d'un coût. Ces jeux sont appelés jeux à somme non nulle.

De plus, dans un jeu à somme non nulle, l'objectif des concepteurs des di érents composants d'un système peut être en contradiction directe avec l'intérêt général du système. Par conséquent, alors qu'une solution du point de vue du système est un optimum social, du point de vue d'un composant particulier, qui joue égoïstement, une solution serait un choix qui est le meilleur par rapport aux choix de tous les autres joueurs. Comme cela est vrai pour tous les composants, ils voudraient ensemble atteindre une certaine forme de stabilité dans leurs choix les uns par rapport aux autres ; et ce serait la solution de leur point de vue. Toutefois, cette notion de stabilité n'est pas unique.

Les équilibres de Nash (NE) [ ], la notion de stabilité la plus courante, est le concept de solution qui est immunisé contre toute déviation d'un seul joueur à n'importe quel moment du jeu si tous les joueurs suivent leurs choix correspondants donnés par cette notion, depuis le début du jeu. Mais il existe également d'autres notions, qui sont étudiées en fonction de divers contextes. Par exemple, Subgame perfect Equilibria (SPE) (SPE) [ ] est un concept de solution pour la stabilité, qui est plus pertinent dans un contexte où chaque joueur peut prendre des décisions dynamiquement, étape par étape, en voyant comment les autres joueurs réagissent. La stabilité est également assurée contre toute déviation d'un seul joueur à n'importe quelle étape du jeu, comme l'EN, sauf qu'elle l'est même si . Equilibres forts [ , ] est une notion de stabilité qui est immunisée non seulement contre les déviations d'un seul joueur mais aussi contre les déviations coordonnées de plusieurs vi Résumé de la thèse joueurs, tandis que les équilibres de Stackelberg [ , ] sont la solution stable lorsqu'il y a quelques joueurs dont l'objectif est égal à celui du système lui-même (non égoïstement), tandis que d'autres joueurs jouent dans leur propre intérêt.

Néanmoins, il n'est pas garanti que l'une ou l'autre notion d'ensemble stable de choix existe toujours dans tous les jeux à somme non nulle. Par conséquent, l'une des tâches dans ce contexte est toujours de trouver les notions qui conviennent le mieux à l'objectif, et si cette notion de stabilité existe dans cette classe particulière de jeux à somme non nulle.

J

Dans cette thèse, nous nous intéressons à des jeux particuliers à somme non nulle, appelés jeux de congestion, joués sur un réseau. Les jeux de congestion modélisent le partage égoïste des ressources entre plusieurs joueurs [ ]. Un cas particulier est celui des jeux de congestion jeux de congestion, dans lesquels les joueurs visent à l'acheminement du tra c à travers un réseau encombré. Dans jeux de congestion de réseau, chaque joueur choisit un ensemble de transitions, formant un chemin simple d'un état source à un état cible, et le Le coût d'une transition augmente avec sa charge, c'est-à-dire avec le nombre de joueurs qui l'utilisent. de joueurs qui l'utilisent. Dans la section suivante, nous passons en revue l'état de l'art sur les jeux de congestion de réseau.

T

Les jeux de congestion de réseau peuvent être classés en variantes atomiques et non atomiques. non atomiques. La sémantique non-atomique est appropriée pour de grandes populations de joueurs. de joueurs et est donc considérée comme un continuum. On considère alors des portions de la population qui appliquent des stratégies prédé nies, et l'e et d'un joueur individuel l'e et d'un joueur individuel sur le coût des autres. Sur En revanche, dans les jeux atomiques, le nombre de joueurs est xe, et chaque joueur peut avoir un impact signi catif sur le coût supporté par les autres joueurs. Nous nous concentrons uniquement sur les jeux atomiques dans cette thèse.

J

Réseau congestion, également appelés jeux atomiques de routage égoïste dans la littérature. dans la littérature, ont été étudiés pour la première fois par Rosenthal [ ]. Ces jeux sont dé nis par un graphe dirigé, un nombre de paires de sommets de paires de sommets source-cible, et des fonctions de coût non décroissantes pour chaque arête du graphe. Pour chaque paire source-cible, un joueur doit choisir une route de la source au sommet cible. route de la source au sommet de la cible. Étant donné leur choix de chemins simples, le coût encouru par un joueur dépend du nombre d'autres joueurs qui choisissent des chemins partageant des arêtes avec lui. autres joueurs qui choisissent des chemins partageant des arêtes avec leur chemin, et des fonctions de coût de ces bords. Dans ce contexte, un équilibre de Nash de Nash associe chaque joueur à un chemin de telle sorte qu'aucun joueur n'a intérêt à s'en écarter. joueur n'est incité à dévier : il ne peut pas diminuer son coût en choisissant un chemin di érent.

Rosenthal Rosenthal a prouvé que les jeux de congestion de réseau sont des jeux potentiels, de sorte que les équilibres de Nash existent toujours. existent toujours. Monderer et Shapley [ ] ont étudié d'une manière plus générale jeux potentiels, et ont expliqué comment utiliser itérativement les meilleures stratégies de meilleure réponse pour converger vers un équilibre. Il est intéressant de vii Résumé de la thèse noter que, sous des hypothèses raisonnables sur les fonctions de coût, Bertsekas et Tsitsiklis ont établi qu'il existe une correspondance directe correspondance directe entre les équilibres du routage égoïste et du routage distribué du plus court chemin, qui distribué, qui est utilisé en pratique pour le routage des paquets dans les réseaux informatiques. réseaux informatiques [ ]. Nous renvoyons le lecteur intéressé à citeroughgarden-chap pour une introduction et de nombreux résultats de base sur les jeux de routage généraux.

Une question naturelle est de savoir si le routage égoïste est très di érent d'une stratégie de routage décidée par un organisme centralisé. stratégie de routage décidée par une autorité centralisée. En d'autres termes, En d'autres termes, à quelle distance un optimum égoïste peut-il être de l'optimum social, dans lequel les les joueurs coopéreraient. La notion de prix de l'anarchie, d'abord proposée par Koutsoupias et Papadimitriou [ ], est le rapport entre le pire coût d'un équilibre de Nash et le coût de l'optimum social.

Cela permet de mesurer à quel point les équilibres de Nash peuvent être mauvais. Dans le contexte des jeux de congestion de réseau, le prix de l'anarchie a été étudié pour la première fois par Suri et al. [ ], en établissant une limite supérieure de 5 2 lorsque toutes les fonctions de coût sont a nes. Une limite supérieure a née a été fournie par Awerbuch et al. [ ]. Bornes sur la notion duale de prix de stabilité, qui est le rapport entre le coût d'un meilleur équilibre de Nash et le coût de l'optimum social ont également été étudiés pour les jeux de jeux de routage [ ].

A

Plusieurs travaux ont étudié des ra nements de ce cadre. Dans [ ], les auteurs étudient les jeux de congestion de réseau dans lesquels chaque bord est traversé avec une durée xe indépendante de sa charge, tandis que le coût de chaque bord dépend de la charge. On dit donc que le modèle a des coûts dépendants du temps, puisque la charge dépend des moments où les joueurs traversent un bord donné. auxquels les joueurs traversent un bord donné. Les auteurs prouvent l'existence des équilibres de Nash par réduction au cadre de [ ]. Une extension de ce cadre avec des automates temporisés et des horloges contraintes temporelles a été étudiée dans [ , ]. peuvent être imposées dans le graphe. La mise en place de durées xes avec des coûts dépendant du temps est intéressant dans les applications où les joueurs partageant une ressource (un bord) voient leur qualité de service diminuer. ressource (un bord) voient leur qualité de service diminuer, alors que le temps d'utilisation de la ressource n'est pas a ecté. la ressource n'est pas a ecté [ ]. Cela peut être le cas, par exemple dans certaines applications de télécommunication et de streaming multimédia. La temporisation apparaît également, par exemple, dans les applications [ , ] où la charge a ecte les temps de parcours et où l'objectif des joueurs est de minimiser le temps total de déplacement. D'autres travaux se concentrent sur les modèles de ux avec un aspect temporel [ , ].

J

Dans les jeux classiques de congestion de réseau, les joueurs choisissent leurs stratégies (leurs chemins simples) en une seule fois. Cependant, il peut être intéressant de laisser les agents choisir leurs chemins dynamiquement, c'est-à-dire étape par étape, en observant les choix précédents des autres joueurs. Dans cet article, nous étudions les jeux de congestion de réseau avec des coûts dépendant du temps comme dans [ ], mais avec des retards unitaires, et dans un cadre dynamique. Plus précisément, à chaque étape, chacun des joueurs sélectionne simultanément le bord qu'il veut prendre ; chaque joueur doit ensuite payer un coût qui dépend de la charge du bord qu'il a choisi. l'arête qu'il a choisie, et traverse cette viii Résumé de la thèse arête en une seule étape. Nous nommons ces jeux : jeux dynamiques de congestion de réseaux (dynamic NCG en abrégé) ; le comportement des joueurs dans ces jeux est formalisé au moyen de stratégies, indiquant aux joueurs ce qu'ils doivent jouer en fonction de la con guration actuelle. Remarquez que, puisque l'e et de congestion s'applique aux arêtes utilisées simultanément par plusieurs joueurs, prendre des cycles peut être intéressant dans un NCG dynamique, ce qui rend notre cadre plus complexe que la plupart des NCG. modèles [ , , , ].

Un tel cadre dynamique a été étudié dans [ ] pour les jeux d'allocation de ressources. d'allocation des ressources, qui étend [ ] aux choix dynamiques.

C

. Nous étudions les concepts de solution classiques sur les jeux dynamiques de congestion de réseau. réseau dynamique. Un pro l de stratégie (i.e., une fonction assignant une stratégie à chaque joueur) est un équilibre de Nash (NE) lorsque chaque stratégie unique est une réponse optimale aux stratégies des autres joueurs. d'autres termes, sous un tel pro l stratégique, aucun joueur ne peut réduire ses baisser ses coûts en changeant unilatéralement ses stratégies. Remarquez que les NE ne doivent pas nécessairement exister en général, et lorsqu'ils existent, ils peuvent ne pas être uniques. être uniques. Dans le cadre des jeux dynamiques, les équilibres de Nash sont généralement mis en oeuvre en utilisant des stratégies d'optimisation. généralement renforcés par des stratégies de punition, par lesquelles tout joueur joueur qui dévie sera puni par tous les autres joueurs une fois que la déviation a été détectée. Cependant, ces stratégies de punition peuvent aussi augmenter le coût encouru par les joueurs qui punissent, et ne constituent donc pas une menace crédible. ne constituent pas une menace crédible. Subgame-Perfect Equilibria (SPE) ra ne NE et Nous abordons ce problème en exigeant que le pro l stratégique soit un NE le long de tout jeu.

NE et SPE visent à minimiser le coût individuel de chaque joueur (sans se soucier des coûts des autres). sans se soucier des coûts des autres) ; dans un contexte de collaboration, les joueurs peuvent plutôt essayer de réduire le coût social, c'est-à-dire la somme des coûts encourus par tous les joueurs. encourus par tous les joueurs. Les pro ls stratégiques qui y parviennent sont appelés social optima (SO). De toute évidence, le coût social de NE et SPE ne peut être inférieur à celui de l'optimum social ; Le prix de l'anarchie mesure la gravité des comportements égoïstes par rapport aux comportements collaboratifs. comportements égoïstes par rapport aux comportements collaboratifs.

P

(jeux de congestion de réseau paramétrés) Tous les problèmes ci-dessus ont été abordés en partant du principe que tous les joueurs (et les contrôleurs, le cas échéant) connaissent le nombre de joueurs dans le réseau, ce qui est crucial pour concevoir un équilibre ou un optimum social. Comme une solution pour un certain nombre de joueurs apriori ne nous donne aucune information sur ce à quoi ressemblerait une solution pour un autre nombre de joueurs, nous devrions la résoudre à partir de zéro sur le même réseau chaque fois que le nombre de joueurs change.

L'étude de l'incertitude dans le tra c suscite un intérêt croissant. Une approche commune pour traiter ce problème consiste à généraliser le cadre déterministe au cadre stochastique avec un nombre inconnu de joueurs. Wang et al. En dehors des approches stochastiques, il existe d'autres méthodes pour calculer directement les équilibres dans un cadre paramétrique. Klimm et Wardo[ ] ont trouvé que la complexité du calcul des équilibres dans les jeux de congestion atomique avec des fonctions paramétriques de coût-a ne est PPAD-complète, en exprimant l'évolution des équilibres localement par une nouvelle matrice Laplacienne en bloc.

Nous essayons d'aborder le même problème avec le nombre de joueurs comme paramètre en exprimant le NE pour un grand nombre de joueurs en termes de NE pour un plus petit nombre de joueurs en utilisant une propriété semi-linéaire, ce qui évite au contrôleur, qui assigne un pro l stable à tous les joueurs, de calculer le NE à partir de zéro. Malheureusement, le cas général reste ouvert dans cette thèse, et nous donnons des résultats préliminaires pour les graphes series-parallèles.

C

Dans la première partie, nous adoptons un point de vue de complexité informatique pour étudier les jeux dynamiques de congestion des réseaux. jeux de congestion de réseaux dynamiques. Nous établissons d'abord la complexité du calcul de l'optimum Nous montrons que le calcul de l'optimum social est in PSPACE et NP-hard. Nous prouvons ensuite que les stratégies de meilleure réponse peuvent être calculées en temps polynomial. temps polynomial, et que les GCN dynamiques sont des jeux potentiels, montrant ainsi l'existence d'équilibres de Nash. montrant ainsi l'existence d'équilibres de Nash dans tout GNC dynamique ; ceci montre également que certains équilibres de Nash peuvent être calculés en temps pseudo-polynomial. Nous donnons ensuite un algorithme EXPSPACE (resp. EXPSPACE) algorithme pour décider de l'existence d'équilibres de Nash (resp. équilibres sous-jeux-parfaits) dont les coûts sociaux satisfont des limites données. Ce site nous permet de calculer le meilleur et le pire de ces équilibres, puis le prix de l'anarchie et le prix de la stabilité. Ces résultats sont publiés dans [ ].

Notez que certaines des complexités élevées découlent du codage binaire du nombre de joueurs. codage binaire du nombre de joueurs, qui est le principal paramètre d'entrée. Par exemple, la complexité exponentielle de l'espace du NE contraint tombe à un temps pseudo-polynomial. temps pseudo-polynomial pour un nombre xe de joueurs. Ce paramètre devient important puisque nous préconisons l'étude de problèmes de calcul, tels que le calcul des équations de Nash. problèmes de calcul, tels que le calcul des équilibres de Nash avec une donné. Nous croyons également que le calcul de valeurs précises pour le prix de l'anarchie et le prix de la stabilité est important. prix de l'anarchie et le prix de la stabilité est intéressant, plutôt que de plutôt que de fournir des limites sur l'ensemble de toutes les instances, comme dans le cas suivant e.g. [ ].

x Résumé de la thèse Dans la deuxième partie, nous nous limitons aux arènes de jeu qui sont des graphes sérieparallèles, et notre modèle au modèle communément étudié des jeux de congestion de réseau : sans stratégies dynamiques et sans e et de congestion non-synchrone dans le calcul du coût. Dans ce modèle, nous montrons que l'ensemble des pro ls NE est un ensemble semi-linéaire. De plus, l'ensemble semi-linéaire a une structure spéciale : tout vecteur période de l'ensemble semi-linéaire est un multiple d'un vecteur unique, que nous appelons le vecteur shift. De plus, nous émettons également une conjecture selon laquelle ce vecteur dit de décalage est le seul vecteur de période de l'ensemble semi-linéaire. Si cette conjecture s'avère vraie, nous montrons une manière très simple de représenter l'ensemble de tous les pro ls NE, et nous donnons un algorithme pour calculer un NE pour un grand nombre de joueurs en utilisant les vecteurs de décalage et le NE d'un nombre relativement plus petit de joueurs.

O

Ce document est divisé en deux parties. Dans la partie I, qui est basée sur [ ], nous étudions les jeux dynamiques de congestion de réseau. Dans cette partie, au chapitre ??, nous xons les notations et adaptons les dé nitions de la littérature, qui seront utilisées dans les chapitres suivants. Dans le chapitre , nous considérons le problème de l'optimum social contraint, et résolvons le problème en PSPACE, tout en montrant que la borne inférieure est NP. Dans les chapitres et , nous considérons deux concepts de solution : Les équilibres de Nash et les équilibres parfaits de sous-jeu, et nous résolvons le problème de décision sous contrainte pour chacun d'eux, ce qui nous permet de conclure la partie I. Cette partie est principalement basée sur [ ].

Dans la partie II du document, nous considérons des jeux paramétrés de congestion de réseau sur des graphes série-parallèles, dans lesquels le nombre de joueurs est le paramètre. Ici, dans le chapitre , nous introduisons les dé nitions que nous utilisons spéci quement pour cette partie, et dans le chapitre , notre objectif était d'obtenir un algorithme pour calculer les NE pour les NCG avec beaucoup de joueurs à partir des NE des NCG avec moins de joueurs. Nous énumérons quelques résultats dans ce sens, et nous formulons une conjecture qui, si elle est vraie, nous donne une représentation de l'ensemble de tous les NE avec un nombre quelconque de joueurs en termes d'un vecteur dit shift et de NE avec un certain nombre ni de joueurs.

En n, dans le chapitre . , nous concluons en résumant brièvement tous les résultats, et en fournissant une liste de suivis immédiats et d'objectifs futurs.

xi I M

When we commute from one place to another, usually we want to avoid as much tra c as possible, and we often tend to change our predestined route if we see updates on our chosen route show a heavy tra c. But it may happen that others too, who were determined to choose the same route, see the same update, and switch their route to the one that we are changing into. As a result a situation arises where a previously lighter tra c route becomes heavier, and a heavier tra c might become lighter than before. And, we are back to square one.

But there might be ways to tackle this problem: ( ) the commuters may decide among themselves who will switch and who will not, or ( ) the update might come to the commuters directly with a solution to switch in a way such that if they all follow the suggestion, they actually become better o . One might ask how the commuters communicate and drive cooperatively in order to bene t in situations like this. In a foreseeable future with automated vehicles [ , ], both vehicle to vehicle (V V) or vehicle to infrastructure (V I) communications are imagined to be realizable [ ]. In this thesis, our concern is not how these communications are realizable, rather we are interested in problems like if such a communication is indeed established what kind of solution such a cooperative decision making would guarantee in lowering congestion e ect, and how to synthesize such a planning of routes for the commuters, which ensures the guarantee.

Like tra c on road, another area where congestion control is relevant in our daily life is the internet. As we keep spending more and more time on the internet (specially after the pandemic doomed us all), everyday we experience one problem or another. One day we need to turn o our camera during an online meeting between two people, while on another lucky day, we participate an online seminar with thirty people. Downloading a le today might take twice as much time as it had taken yesterday for the same size. We all have been there.

While there might be many facets of reasons for these happening, like -unavailability/broken links, packets that carry data may traverse di erent inner network nodes ('routers'), but one of the main reason behind the performance uctuations on the internet happens due to network congestion. Thus, controlling congestion is crucial in today's Internet. The predominant form of congestion control is embodied in Transmission Control Protocol (TCP) [ ], which provides a reliable way of end-to-end data transmission, and also avoiding any congestion collapse. Intuitively, this protocol works in the interest of a network as a whole (or at least of a su ciently large part), and therefore from an end-point's perspective it might not always be in their best interest to comply with the protocol. This gives rise to game-theoretic analysis [ , , , ] of TCP-like protocols in the literature: Akella et al. [ ], using game-theoretic analysis of TCP, compare e ciency of stable behaviors between recent variations of TCP (e.g. SACK) with traditional variations, and conclude that recent variations are more susceptible to sel sh behavior; Lopez et al. [ ] study the Fountain Based Protocol (FBP), and compare the performance of stable mechanism between FBP xii and TCP in the presence of congestion; Kesselman et al. [ ] measure degradation in performance because of congestion in a TCP-like tra c model, and propose an early detection policy to reduce degradation, and these are the few examples from a vast literature on game theoretic analysis of TCP-like protocols. One of the commonalities between all these is that they are studying the performance of stable behaviors of the internet in di erent but speci c contexts when end-users are interacting sel shly and causing congestion. Moreover, in those speci c contexts these studies focus mainly on measuring worst-case scenario of a model without directly checking the properties of an instance of those models.

In theory, these kind of practical scenarios are often abstracted in graph games, and similar problems are studied on those graphs, which comment on, more often than not, worst/best-case scenarios in that particular class of games. We discuss more on this in Section of this chapter. In this thesis, we view this area from a formal methods perspective, where instead of addressing worst/best-case scenario for a congestion game model, we are more interested in what kind of stability performance can be guaranteed in a given instance of this model. Therefore, we start with introducing formal methods, how they address game theoretical questions, and then delve into more details how we approach analyzing congestion games from a veri cation perspective. B F G In today's age, we are heavily dependent on computerized systems: from smartphone to space-shuttle, from ATM to automated vehicle, from tra c control to nuclear power plants -the list continues to grow each passing day, and so is our dependency on them. We want these systems to be immune to failure. When a system fails, we face crisis from nancial loss to loss of lives. For example, a fatal defect in the control software [ ] of the Ariane-missile caused a crash just within seconds of its launch on June , . A software aw in the control part of the radiation therapy machine Therac-[ ] caused the death of six cancer patients between and . In computer science, formal methods is a eld where we formally reason about such computerized system: we verify properties for a given system (model checking), and build models which are correct by construction (synthesis) from a given speci cation. In model checking problems, an input usually consists of a system and a logical speci cation (for example a formula in temporal logic [ ]), and the problem asks whether the system satis es the speci cation. Depending on what kind of formulas are being considered as the speci cation, the model checking problem asks whether one or all executions of the system in question satis es the speci cation.

In reality, a designer/controller may control only parts of the whole system, and they might want to verify a speci cation on the executions of the system which involves those parts. For instance, consider an elevator in a building as the system, and the speci cation is whenever someone calls from a certain oor, the elevator needs to stop at that oor eventually to pick up that person. Now, this speci cation is concerned with a particular part of the system, which has almost nothing to do with executions like : not getting stuck in between oors, opening the door when it stops at a oor or, not opening the door when it is running between oor etc. Therefore, to check whether the elevator satis es the speci cation, we should neither check all executions, it is enough nor to check a single execution, which can only guarantee for a single call to stop. xiii These types of problems in formal methods are solved using game-theoretic [ ] approach: in our example, the person who calls the elevator is the environment, and the elevator itself is the system. In such two-player games between the system and the environment, the environment aims to show that the system is faulty, while the system tries to establish that it is not. In other words, the veri cation problem demands that the designer/controller can make sure the system wins against any behaviour of the environment. These are called zero-sum games, and a solution in such a game is a winning strategy.

On the other hand, it is possible that the designers of di erent components of a system themselves compete with each other for certain resources. Here instead of either winning or loosing the game, each player obtains some payo . Payo can be positive, which is generally referred to as a reward, and it can be negative, which is referred to as a cost. Unlike winning a game, here a player's objective is to optimize their payo : maximize if it is a reward, minimize if it is a cost. These games are called non-zero sum games.

Moreover, in a non-zero sum game, the objective of designers of di erent components of a system's might be in direct contrast with the system's overall best interest. Therefore, while a solution from the system's perspective is a social optimum, from a particular component's perspective, who is playing selfishly, a solution would be a choice that is best with respect to all other player's choices. Because this is true for all components, they together would like to achieve some kind of stability in their choices with each other; and that would be the solution from their perspective. However, this notion of stability is not unique. Nash Equilibria (NE) [ ], the most common notion of stability, is the solution concept which is immune to any single player deviation at any point of the game if all players follow their corresponding choices given by it, from the beginning of the game. But there are other notions as well, which are studied depending on various contexts. For example, Subgame perfect Equilibria (SPE) [ ] is a solution concept for stability, which is more relevant in a context where each player can make decision dynamically, step by step, seeing how other players are responding. Strong Equilibria[ , ] is a notion of stability which is immune not only to single player deviations but also to coordinated deviation of several players, while Stackelberg equilibria [ , ] are the stable solution when there are some players whose objective are on par with the system itself (not sel shly), while some other players play in their self-interest. Nonetheless, it is not guaranteed that one or another notion of stable set of choices always exist in all non-zero sum games. Hence, one of the task in this context is always nd out which notions ts best for the purpose, and whether that notion of stability exists in that particular class of non-zero sum game.

C S R

In this thesis, we focus on particular non-zero sum games, called congestion games played on a network. Congestion games model sel sh resource sharing among several players [ ]. A special case is the one of network congestion games, in which players aim at routing tra c through a congested network. In network congestion games, each player chooses a set of transitions, forming a simple path from a source state to a target state, and the cost of a transition increases with its load, that is, with the number of players using it. In the next section, we review the state of the art on network congestion games.

xiv

R N C G

Network congestion games can be classi ed into atomic and non-atomic variants. Non-atomic semantics is appropriate for large populations of players, thus seen as a continuum. One then considers portions of the population that apply prede ned strategies, and there is no such thing as the e ect of an individual player on the cost of others. In contrast, in atomic games, the number of players is xed, and each player may signi cantly impact the cost other players incur. We only focus on atomic games in this thesis.

N

Network congestion games, also called atomic sel sh routing games in the literature, were rst considered by Rosenthal [ ]. These games are de ned by a directed graph, a number of pairs of source-target vertices, and non-decreasing cost functions for each edge in the graph. For each source-target pair, a player must choose a route from the source to the target vertex. Given their choice of simple paths, the cost incurred by a player depends on the number of other players that choose paths sharing edges with their path, and on the cost functions of these edges. In this setting, a Nash equilibrium maps each player to a path in such a way that no player has an incentive to deviate: they cannot decrease their cost by choosing a di erent path.

Rosenthal[ ] proved that network congestion games are potential games, so that Nash equilibria always exist. Monderer and Shapley [ ] studied in a more general way potential games, and explained how to iteratively use best-response strategies to converge to an equilibrium. Interestingly, under reasonable assumptions on the cost functions, Bertsekas and Tsitsiklis established that there is a direct correspondence between equilibria in sel sh routing and distributed shortest-path routing, which is used in practice for packet routing in computer networks [ ]. We refer the interested reader to [ ] for an introduction and many basic results on general routing games.

A natural question is whether sel sh routing is very di erent from a routing strategy decided by a centralized authority. In other words, how far can a sel sh optimum be from the social optimum, in which players would cooperate. The notion of price of anarchy, rst proposed by Koutsoupias and Papadimitriou [ ], is the ratio of the worst cost of a Nash equilibrium and the cost of the social optimum. This measures how bad Nash equilibria can be. In the context of network congestion games, the price of anarchy was rst studied by Suri et al. Bounds on the dual notion of price of stability, which is the ratio of the cost of a best Nash equilibrium and the cost of the social optimum were also studied for routing games [ ].

T

Several works investigated re nements of this setting. In [ ], the authors study network congestion games in which each edge is traversed with a xed duration independent of its load, while the cost of each edge depends on the load. The model is thus said to have timedependent costs since the load depends on the times at which players traverse a given edge. The authors prove the existence of Nash equilibria by reduction to the setting of [ ]. An extension of this setting with timed constraints was studied in [ , ].

The setting of xed durations with time-dependent costs is interesting in applications where the players sharing a resource (an edge) see their quality of service decrease, while the time to use the resource is una ected [ ]. This might be the case, for instance, in some telecommunication and multimedia streaming applications. Timing also appears, for instance, in [ , ] where the load xv a ects travel times and players' objective is to minimize the total travel time. Other works focus on ow models with a timing aspect [ , ].

D

In classical network congestion games, players choose their strategies (i.e., their simple paths) in one shot. However, it may be interesting to let agents choose their paths dynamically, that is, step by step, by observing other players' previous choices. In this thesis, we study network congestion games with time-dependent costs as in [ ], but with unit delays, and in a dynamic setting. More precisely, at each step, each of the players simultaneously selects the edge they want to take; each player is then charged a cost that depends on the load of the edge they selected, and traverses that edge in one step. We name these games dynamic network congestion games (dynamic NCG in short); the behaviour of the players in such games is formalized by means of strategies, telling the players what to play depending of the current con guration. Notice that, because the congestion e ect applies to edges used simultaneously by several players, taking cycles can be interesting in dynamic NCG, which makes our setting more complex than most NCG models [ , , , ].

Such a dynamic setting was studied in [ ] for resource allocation games, which extends [ ] with dynamic choices.

S

We study classical solution concepts on dynamic network congestion games. A strategy pro le (i.e., a function assigning a strategy to each player) is a Nash Equilibrium (NE) when each single strategy is an optimal response to the strategies of the other players; in other terms, under such a strategy pro le, no player may lower their costs by unilaterally changing their strategies. Notice that NE need not exist in general, and when they exist, they may not be unique. In the setting of dynamic games, Nash Equilibria are usually enforced using punishing strategies, by which any deviating player will be punished by all other players once the deviation has been detected. However, such punishing strategies may also increase the cost incurred by the punishing players, and hence do not form a credible threat. Subgame-Perfect Equilibria (SPE) re ne NE and address this issue by requiring that the strategy pro le is an NE along any play.

NE and SPE aim at minimizing the individual cost of each player (without caring of the others' costs); in a collaborative setting, the players may instead try to lower the social cost, i.e., the sum of the costs incurred to all the players. Strategy pro les achieving this are called social optima (SO). Obviously, the social cost of NE and SPE cannot be less than that of the social optimum; the price of anarchy measures how bad sel sh behaviours may be compared to collaborative ones.

P

All the above problems were addressed on an underlying assumption that all the players (and controllers if any) know the number of players in the network, which is crucial to design an equilibrium or social optimum. As a solution for a certain number of players apriori does not give us any information about what a solution for another number of players would look like, we would need to solve it from scratch on the same network every time the number of players changes.

There has been a growing interest in investigating uncertainty in tra c. One common approach to deal with this problem is to generalize the deterministic setting to the stochastic one with an unknown number of players. Apart from stochastic approaches, there have been other methods to directly compute equilibria in parametric setting. Klimm and Wardo[ ] found the complexity of computing Equilibria in atomic congestion games with parametric cost-a ne functions is PPAD-complete, by expressing the evolution of equilibria locally by a novel block Laplacian matrix.

We try to approach the same problem with number of players as the parameter by expressing NE for large number of players in terms of NE for smaller number of player using semi-linear property, and this spares the controller, who assigns a stable pro le to all players, to compute NE from scratch. Unfortunately, the general case remains open in this thesis, and we give preliminary results for series-parallel graphs.

C

In the rst part, we take a computational-complexity viewpoint to study dynamic network congestion games. We rst establish the complexity of computing the social optimum, which we show is in PSPACE and NP-hard. We then prove that best-response strategies can be computed in polynomial time, and that dynamic NCG are potential games, thereby showing the existence of Nash equilibria in any dynamic NCG; this also shows that some Nash equilibrium can be computed in pseudo-polynomial time. We then give an EXPSPACE (resp. EXPSPACE) algorithm to decide the existence of Nash Equilibria (resp. Subgame-Perfect Equilibria) whose social costs satisfy given bounds. This allows us to compute best and worst such equilibria, and then the price of anarchy and the price of stability. These results are appeared in [ ].

Note that some of the high complexities follow from the binary encoding of the number of players, which is the main input parameter. For instance, the exponential-space complexity of constrained NE drops to pseudo-polynomial time for a xed number of players. This parameter becomes important since we advocate the study of computational problems, such as computing Nash equilibria with a given cost bound. We also believe that computing precise values for the price of anarchy and the price of stability is interesting, rather than providing bounds on the set of all instances as in e.g. [ ].

In the second part, we restrict to game arena that are series-parallel graphs, and our model to the commonly studied model of network congestion games: without dynamic strategies and non-synchronous congestion e ect in the cost computation. In that model, we show that the set of NE pro les is a semi-linear set. Moreover, the semi-linear set has a special structure: any period vector of the semi-linear set is a multiple of a single vector, which we call the shift-vector. Moreover, xvii we also make a conjecture that this so-called shift vector is the sole period vector of the semi-linear set. If this conjecture turns out to be true, then we show a very simple way to represent the set of all NE pro les, and give an algorithm to compute an NE for a large number of players using the shift vectors and the NE of relatively smaller number of players.

O

This document is divided into two parts. In Part I, which is based on [ ], we study Dynamic network congestion games. In that part, in Chapter , we x the notations and adapt de nitions from literature, which will be used in the subsequent chapters. In Chapter , we consider the constrained Social optimal problem, and solve the problem in PSPACE, while the lower bound is shown to be NP. In Chapters and , we consider two solution concepts: Nash Equilibria and Subgame perfect Equilibria, and solve the constrained decision problem for each, and with this we conclude Part I. This part is mostly based on [ ].

In Part II of the document, we consider parameterized network congestion games on seriesparallel graphs, in which the number of players is the parameter. Here, in Chapter , we introduce the de nitions that we use speci cally for this part, and in Chapter , our aim was to obtain an algorithm to compute NE for NCG with many players from NE of NCG with fewer players. We list out some results on that direction, and we formulate a conjecture which, if true, gives us a representation of the set of all NE with any number of players in terms of a so-called shift vector and NE with some nite number of players.

Finally, in Chapter . , we conclude by summarizing all the results brie y, and by providing a list of immediate follow-ups and future objectives.

A

We assume an arbitrary order among the elements of src and tgt. This gives us a lexicographic ordering among the elements of src × tgt. We use this order to identify which player have which vertices among the source and target. To be fair, our model is not speci c to any player's identity, hence we do not keep this order as a part of the syntax.

Let us consider the elements of src × tgt with the order are (s 1 , t 1 ) < (s 1 , t 2 ) < . . . < (s |src| , t |tgt| ). We consider (s l , t m ), for l ≤ |src|, m ≤ |tgt|, to be the source-target vertex pair for Player i if

(s,t)<(s l ,tm) g(s, t) < i ≤ (s,t)≤(s l ,tm) g(s, t)

Preliminaries

Abusing notation, we denote the source and target vertex of Player i as src(i) and tgt(i). It is noteworthy that, whenever we will take an instance of an NCG A, n, g as input, since for all (s, t) ∈ src × tgt, g(s, t) ≤ n, the input size is logarithmic in n. This is clearly the case if all players have same source and target, which we refer as symmetric network congestion games. However, in case of non-symmetric games, where players do not have same source-target vertices, one way to encode the input in such a case is to take a list of source-target vertex pairs for each player. In such encoding, the input size os polynomial in n. But we can encode n in binary only because in this model of congestion games, apart from the source-target pair of vertices, identity of a player doesn't matter. That is why, instead of associating each pair of source-target vertices to each player, we chose to encode via a map which associates each pair of source-target vertex to the number of players who use those as such.

S

In a network congestion game, all players start from their source src(i) and simultaneously select the edges they want to traverse in order to reach their target tgt(i). In this journey from their source to target, each player pays some cost for traversing, and this cost depends on the cost functions f encoded in the transitions of the form (v, f, v ), and in turn, may depend on the number of players that also take the same edge, in case f is not a constant function.

Each player's objective in an NCG is to traverse from its source to target with minimum individual accumulated cost.

In classical network congestion games[ , ], each player selects a path from their source to target at once, at the beginning of a play, and continue with that path till they reach their target vertex. In that setting, we can also see that a player's congestion cost is measured by taking into account how many other players have taken the same edge throughout their traversal, and not necessarily at the same step. On the contrary, in Part I of this thesis, we consider a setting which di ers from the classical model in two aspects:

• rst, the game is played in rounds, during which all players take exactly one transition; the number of players using an edge e is measured dynamically, at each round.

We can also view this di erence in another perspective: while in our model of NCG, players pay "immediately" for the congestion, in classical model players pay "at the end" by seeing how many other players have also traversed the same edge.

• second, during the play, each player may adapt their choices depending on what the other players have been doing in the previous rounds. . Note that some of the edges like (s, x → x, v 1 ), (v 2 , x → x, v 3 ) are associated with linear cost functions, in which f : x → x means any player who takes this edge pays as much cost as the number of players who take the same edge in their traversal. Other edges like (v 1 , x → 6, v 2 ) are associated with constant cost functions, where each player who takes the edge (v 1 , x → 6, v 2 ) pays cost 6, no matter how many other players also take the same in their traversal.

s v 1 v 2 v 3 t x → x x → 5 x → 6 x → 3 x x → x x → 4x
On this arena, we consider dynamic NCG A, 2, g with two players, where g(s, t) = 2. Assume that Player 1 follows the path π

1 : s → v 1 → v 3 → t and Player 2 goes via π 2 : s → v 1 → v 2 → v 3 → t.
In classical NCGs, the cost for Player 1 would be 2 + 3 + 8 = 13, while for Player 2, it would be 2 + 6 + 1 + 8 = 17. Notice that, here, even though the edge v 3 → t is not used simultaneously, both players bear congestion e ect in their payable cost due to this edge. On the contrary, in our model, this gives rise to the following path (along with the costs):

P 1 → s P 2 → s P 1 →2 P 2 →2 ----→ P 1 → v 1 P 2 → v 1 P 1 →3 P 2 →6 ----→ P 1 → v 3 P 2 → v 2 P 1 →4 P 2 →1 ----→ P 1 → t P 2 → v 3 P 1 →0 P 2 →4 ----→ P 1 → t P 2 → t
Here, inside the brackets, we depict the current positions of the players, for example P 1 → s P 2 → s depicts that Player 1 and 2 both are at vertex s. On the other hand, labels over the transitions depict how much cost each player pays for taking that particular transition, for example at the first transition, both players observe congestion e ect on their cost and each of them pays cost 2, according to the associated cost function x → x.

Notice how edge v 3 → t of A is used by both players, but not simultaneously, so that the cost of using that edge is 4 for each of them.

An example of a strategy that dynamically adapts to the other players' behaviors, σ, consists in first taking the transition s → v 1 , and then either taking v 1 → v 3 if the other player took the same initial transition, or taking v 1 → v 2 otherwise.

From hereon, we call this setting dynamic NCG in order to distinguish it from other network congestion game models [ , ], which we often refer to as simply NCG.

C G S F D NCG

In congestion games, each player selects their edges simultaneously in order to traverse from their source to target, hence we can think of the dynamics of the game as a concurrent reachability game: where from each location, each player chooses an action to decide next location, for each joint action each player pays some individual cost, and their objective is to visit a designated location with minimum accumulated individual cost. We describe below, formally, how we associate a concurrent game structure with a dynamic NCG, and how we use that subsequently.

Preliminaries

C

For any n ∈ N, we write n = {i ∈ N : 1 ≤ i ≤ n} as the set of n Players. A configuration of a dynamic network congestion game A, n, g is a mapping c : n → V , indicating the position of each player in the arena. We de ne c src : i ∈ n → src(i) and c tgt : i ∈ n → tgt(i) as the initial and target con gurations.

With G = A, n, g , we associate a multi-weighted graph M = C, T , where C = V n is the set of all con gurations, and T ⊆ C × N n × C is a set of edges, where the n-tuple of weights on an edge indicates individual accumulated cost for each player. Formally, there is an edge (c, w, c ) in T if, and only if, there exists a collection e = (e i ) i∈ n of edges of E such that for all i ∈ n , writing e i = (v i , f i , v i ) and load e i (e) = #{j ∈ n | e j = e i } which denotes the number of players taking edge e i simultaneously with Player i, we have

c(i) = v i , c (i) = v i , and w(i) = f i (load e i (e)). Moreover, if c(i) = tgt(i)
, then as the game has stopped for player i, we know w(i) = 0, and c (i) remains tgt(i). We denote this edge with c e = ⇒ c . We may use the notation cost i (c e = ⇒ c ) for w(i) depending on the context, to directly specify the associated con gurations and edge. We call M the configuration graph of the dynamic NCG G. [ , ]. If we try to associate a configuration graph in the classical model to how we defined here, we can see that the edges cannot be associated with costs (weights in M = C, T for our model) of Players likewise. This is due to the fact that, in the classical model, a player's cost of taking an edge does not solely depend on the current transition, rather takes into account how many players might have taken the same edge in other transitions too, in the full-course of the game.

Remark . . Here, we can note the di erence in the way we compute cost between our model of network congestion games and the classical congestion games played on network

Two edges (c, w, c ) and (d, x, d ), in that order, are said to be consecutive whenever d = c . Given a con guration c, a path from c in a dynamic network congestion game is either the single con guration c (we call this a trivial path) or a non-empty, nite (ρ = (t j ) 1≤j<|ρ| ) or in nite (ρ = (t j ) j≥1 ) sequence of consecutive edges in M, where t 1 is a transition from c; the size of a path ρ is zero for trivial paths, and |ρ| ∈ N ∪ {+∞} otherwise. Extending the notation c e = ⇒ c of an edge, we often refer a path ρ = (t j ) 1≤j<|ρ| by a sequence like c 1

e 1 = ⇒ c 2 e 2 = ⇒ . . . c |ρ|-1 e |ρ|-1 = === ⇒ c |ρ| where t j = (c j , w j , c j+1 ) and w j = cost j (c j e j = ⇒ c j+1 ).
We write Paths( A, n, g , c) and Paths ω ( A, n, g , c) for the set of nite and in nite paths from c in A, n, g , respectively. A nite path ρ = (t j ) 1≤j≤|ρ| and another path ( nite or in nite) ρ = (t j ) j≥1 can be concatenated and can be written as ρ

• ρ if t |ρ| and t 1 are consecutive. Moreover, a nite path ρ = (t j ) 1≤j≤|ρ| ∈ Paths( A, n, g , c) is called complete if for t |ρ| = (c, w, c ), c (i) = tgt(i) for all i.
When the con guration c is clear from the context, we simply write PathsG for game G = A, n, g .

Given a path ρ, an index 1 ≤ j ≤ |ρ| and a player i ∈ n , we write ρ(j) for the j-th con guration of ρ, and ρ(j)(i) for the state of Player i in that con guration. For j ≥ 2, we de ne ρ ≤j as the pre x of ρ that ends in the j-th con guration; we let ρ ≤1 = ρ(1). Similarly, for 1 ≤ j ≤ |ρ| -1, we let ρ ≥j denote the su x that starts at the j-th con guration. Finally, if |ρ| is nite, we let ρ ≥|ρ| = ρ(|ρ|).

C

With each path ρ = (c j , w j , c j ) j , and each player i ∈ n , we associate a cost, written cost i (ρ), which is zero for trivial paths, +∞ for in nite paths along which c j (i) = tgt(i) for all j, and |ρ|-1 j=1 w j (i) otherwise. Moreover, when a player reaches their target vertex, they stay there with cost 0. We de ne the social cost of ρ as

soccost(ρ) = i∈ n cost i (ρ) C G
We now extend the con guration graph to a concurrent game structure[ ], which is a multi-agent extension of transition system[ ].

A move for Player i ∈ n from con guration c is an edge e = (v, f, v ) ∈ E such that v = c(i). A move vector from c is a sequence e = (e i ) i∈ n such that for all i ∈ n , e i is a move for Player i from c.

De nition . . The concurrent game structure (CGS) associated with a dynamic NCG

G = A, n, g is a tuple S = C, T, M, U , where -C, T is the configuration graph associated to G.
-M : C × n → 2 E lists the set of available moves for each player from each configuration.

-U : C × E n → T is the transition function such that for every configuration c and every move vector e = (e i ) i∈ n with

e i ∈ M (c, i) for all i ∈ n , U (c, e) = c e = ⇒ c .

S

A strategy for Player i in S from con guration c is a function σ i : Paths( A, n, g , c) → E that associates, with any history h, which is nite path from c in S, a move for Player i from the last con guration of h. A strategy profile is a family σ = (σ i ) i∈ n of strategies, one for each player. We write S i for the set of Player i strategies, and S n for the set of strategy pro les.

Let c be a con guration, h be a history from c and a strategy pro le σ = (σ i ) i∈ n from c. The residual strategy profile of σ after h is the strategy pro le σ h = (σ h i ) i∈ n from the last con guration of h de ned by

σ h i (h ) = σ i (h • h ).
The outcome of a strategy pro le σ from c is the in nite path ρ = (c i , w i , c i+1 ) i≥1 , hereafter denoted with outcome(σ), obtained by running the strategy pro le; it is formally de ned as the only in nite path such that (c 1 , w 1 , c 2 ) = U (c, σ(c)), and such that for any j ≥ 2, (c j , w

j , c j+1 ) = U (c j , σ(h )), where h = (c 1 , w 1 , c 2 ) • • • (c j-1 , w j-1 , c j ).
Pick a strategy pro le σ = (σ i ) i∈ n , and let ρ = (t j ) j≥1 be its outcome, writing

t j = (c j , (w i j ) i∈ n , c j ) for all j ≥ 1. Let k ∈ n . If c l (k) = tgt(k)
for some l ∈ N, then σ k is said to be winning for Player k. In that case, we de ne cost k (σ) as cost k (outcome(σ)). If c l (i) = tgt(i) for all i ∈ n , we de ne the social cost of σ as soccost(σ) = soccost(ρ).

A strategy σ i for Player i is called blind whenever the following holds: for any two nite paths ρ and ρ having same length k, and such that for any position 0 ≤ j < k we have ρ(j

)(i) = ρ (j)(i), then σ i (ρ) = σ i (ρ ).
Intuitively, this means that a blind strategy σ i follows a path in A, independently of what the other players do. A blind strategy can thus be represented as a path of the underlined arena A and we write |σ i | for the length of that path (until its rst visit to tgt, if any). A blind strategy may not be complete, in the sense that it does not necessarily assign a move to all the paths of Paths( A, n, g , c). We write B for the set of blind strategies.

O

In this section, we recall some standard solution concepts for optimizing strategies which concern with optimization of costs, individual or aggregate, depending on the context.

S O

In a collaborative situation, all players want to collectively minimize the total cost for all of them reaching their respective target vertex from their sources.

De nition . . A strategy profile

σ = (σ i ) i∈ n is called a social optimum (SO) if soccost(σ) = inf τ ∈S n soccost(τ )
Observation . . We make the following two observations:

• In a dynamic NCG, there might be several SO profiles (See Example . below), nonetheless, all of them have same social cost, by definition, even though individual costs of players might vary.

• If for two strategy profiles σ and σ , outcome(σ) = outcome(σ ), then σ is an SO profile if, and only if σ is an SO profile.

Example . . Consider the dynamic NCG

G = A 2 , 3, g played on arena A 2 , depicted in Fig 1.2a, where g(s, t) = 3. Consider the strategy profile σ = (σ i ) i∈ n depicted in Fig . b in which σ 1 = σ 2 .
Here σ 1 is a blind strategy represented by the path

ρ 1 = s 1 e 1 -→ v 1 e 2 -→ v 2 e 3 -→ v 3 e 4
-→ t (depicted as the red path), while σ 3 is also a blind strategy represented by the path

ρ 3 = s e 5 -→ v 4 e 6 -→ v 5 e 7 -→ v 6 e 8
-→ t, depicted as the green path in the figure. Following the profile σ, we have

cost 1 (σ) = cost 2 (σ) = 14, while cost 3 (σ) = 8.
We claim that this σ is an SO profile. To verify this, from observation . , we know that it is enough to compare with social costs of all the blind strategy profiles as outcome of any strategy profile can be viewed as blind strategy profiles. Now, apart from the paths ρ 1 and ρ 3 , mentioned just above, the other paths that can represent a strategy are

ρ 2 = s e 1 -→ v 1 e 9 -→ v 5 e 7 -→ v 6 e 8 -→ t and ρ 4 = s e 1 -→ v 1 e 2 -→ v 2 e 10 --→ v 6 e 8
-→ t. By directly representing a blind strategy profile by a -tuple of paths, we have σ = (ρ 1 , ρ 1 , ρ 3 ) and soccost(σ) = 14 × 2 + 8 = 36. The social costs for all other blind strategy profiles are:

. Optimizing strategies ρ 2 ,ρ 4 ,ρ 3 )) = 45 soccost((ρ 1 ,ρ 1 ,ρ 1 )) soccost((ρ 4 ,ρ 4 ,ρ 4

soccost((ρ 1 , ρ 2 , ρ 3 )) = 37 soccost((ρ 1 , ρ 4 , ρ 3 )) = 36 soccost((
)) = 54 soccost((ρ 2 , ρ 2 , ρ 2 )) = 63 soccost((ρ 3 , ρ 3 , ρ 3 )) = 72 soccost(ρ 1 , ρ 1 , ρ 2 ) = 43 soccost((ρ 1 , ρ 1 , ρ 4 )) soccost((ρ 2 , ρ 2 , ρ 1 )) soccost((ρ 4 , ρ 4 , ρ 1 ))      = 46 soccost((ρ 2 , ρ 2 , ρ 3 )) = 52 soccost((ρ 2 , ρ 2 , ρ 4 )) = 58 soccost((ρ 3 , ρ 3 , ρ 1 )) = 42 soccost((ρ 3 , ρ 3 , ρ 2 )) = 55 soccost((ρ 3 , ρ 3 , ρ 4 )) = 50 soccost((ρ 4 , ρ 4 , ρ 2 )) = 51 soccost((ρ 4 , ρ 4 , ρ 3 )) = 47
The rest of the blind strategy profiles are just permutations of the above, for which soccost does not change. Thus, σ is an SO profile.

E

In a sel sh situation, each player aims at optimizing their individual accumulated cost. Despite having only control over their own strategies (be it blind or dynamic), each player's cost gets a ected by what other players chose. Hence, intuitively, optimizing individual cost can be thought of as responding to other people's strategies by an optimal choice of strategy. Following this, we study best-response strategy, which is commonly used in the literature in the context of individual cost-optimization for a quantitative non-zero sum multiplayer game.

Given a strategy pro le σ = (σ i ) i∈ n , a player k ∈ n , and a strategy σ k ∈ S, we denote by σ -k , σ k the strategy pro le

(τ i ) i∈ n such that τ k = σ k and τ i = σ i for all i ∈ n \ {k}. The strategy σ k is a best-response to (σ i ) i∈ n \{k} if cost k (σ) = inf τ k ∈S cost k ( σ -k , τ k ). N E De nition . . A strategy profile σ = (σ i ) i∈ n is a Nash Equilibium (NE) if for every k ∈ n , σ k is a best-response to (σ i ) i∈ n \{k} .
In such cases, there are no pro table unilateral deviations, i.e, no player can improve their cost by switching from their current strategy alone.

NE can be de ned for sub-classes of strategy pro les. In particular, a blind NE is a strategy pro le which is immune to any unilateral blind strategy deviation: formally, a strategy pro le

σ = (σ i ) i∈ n is a blind NE if for any player k ∈ n , cost k (σ) = inf τ k ∈B cost k ( σ -k , τ k ).
A priori, a blind NE need not be an NE for general strategies. That is, from a blind strategy pro le, a player could have a pro table unilateral deviating strategy but not a pro table unilateral blind deviating strategy. But in fact, we will see in Chapter that all blind NE are general-strategy NE for dynamic NCG. The strategies played by Player 1 and 2 are symmetric. Intuitively, each of these two players play following the path s

Example . . Consider the arena A 2 displayed at Fig. . a and the dynamic NCG

G = A 2 , 3, g , where g(s, t) = 3 depicted at Fig . b, illustrated with the NE profile σ = (σ i ) i∈ 3 defined below. Preliminaries s v 1 v 2 v 3 v 4 v 5 v 6 t x → 2 x e 1 x → 3 x e 5 x → 3 e 2 x → 3 e 3 x → 2 x e 4 x → x e 9 x → 3 e 1 0 x → x e 6 x → 2x e 7 x → 2 x e 8 (a) An arena A2 for a dynamic NCG s v 1 v 2 v 3 v 4 v 5 v 6 t 4
e 1 -→ v 1 e 2 -→ v 2 e 3 -→ v 3 e 4
-→ t, unless one of them realizes at some point (either at v 1 or v 2 ) that the other player has deviated (via e 5 or e 9 respectively). In that case, the current player immediately follows the edge (e 9 or e 10 respectively) in order to "punish" the deviating player. Player 3 blindly follows the path s

e 5 -→ v 4 e 6 -→ v 5 e 7 -→ v 6 e 8 -→ t.
In Fig . b, these strategies are depicted by the red arrows (dashed arrows depict the conditional deviation) for Players 1 and 2, and green arrows for Player 3.

Note that,

outcome(σ) = (s, s, s) (4,4,3) = === ⇒ (v 1 , v 1 , v 5 ) (3,3,1) = === ⇒ (v 2 , v 2 , v 5 ) (3,3,2) = === ⇒(v 3 , v 3 , v 6 ) (4,4,2) = === ⇒ (t, t, t)
which implies cost 1 (σ) = cost 2 (σ) = 14 and cost 3 (σ) = 8. Clearly, Player 3 doesn't have any unilateral deviation from which they can improve their cost. On the other hand, by design, if any of Player 1 or 2 deviates from their current strategy at s or v 1 , the other player would punish by deviating at the next vertex. Hence, their unilateral deviation only increases their own cost, making it 20 (for deviating at s) or 15 (for deviating at v 1 ). Deviating at v 2 also keeps the deviating player's cost at 14 without improving it. Hence, none of the players has a unilateral profitable deviation from σ.

Therefore, σ is an NE profile.

. Optimizing strategies (c) outcome(σ, (v2, v2, v2)) In an NE, once a player deviated from their original strategy, other players can punish them even if that increases their own cost. Indeed, the condition for being NE only requires that the deviation should not be pro table for a deviating player. Subgame-perfect equilibrium (SPE) re nes the concept of NE and rules out such non-credible threats.

s v 1 v 2 v 3 v 4 v 5 v 6 t 4
s v 1 v 2 v 3 v 4 v 5 v 6 t e 1
s v 1 v 2 v 3 v 4 v 5 v 6 t e 1
De nition . . Fix an initial configuration, say c, then a Nash equilibrium profile from c is a subgame perfect equilibria (SPE) if for any finite history h from c and ending at c , the residual strategy profile after h is an NE from c .

By de nition, any strategy of an SPE needs to be complete, i.e, the strategy needs to associate a move to all the paths of Paths( A, n, g ). Hence, Remark . . A blind NE, which only associates a path from a player's source vertex to target, generally is not an SPE, simply because the profile is not complete.

Example . . Let us consider again the game

G = A 2 , 3, g with g(s, t) = 3 as usual. Let us consider the strategy profile σ = (σ i ) i∈ 3 depicted in Fig . .
Here, σ 1 and σ 2 map the empty path to edge e 1 , while σ 3 maps to e 5 . To describe rest of the strategy profile, instead of explicitly writing each edge to which it maps a history h of Paths( A, 3, g , c src ), we associate a path π = (e j ) j≥1 of A that is being followed by σ i . We denote this new way of describing σ as σ. Intuitively, we write σi (h) = π = (e j ) j≥1 to denote the following, in short: σ i (h) = e 1 , and if for j ≥ 1, h j denotes the finite path after applying σ for j steps, then σ i (h j ) = e j+1 .

Preliminaries

In the following, we define σ; moreover, for convenience we refer to Fig. . rather than using formal notation.

First, σ1 ((s, s, s)), σ2 ((s, s, s)) and σ3 ((s, s, s)) are shown as the red path (the only path involving e 3 ), blue path (involving e 9 ) and green path (involving e 5 ) respectively in Figure 1 But this doesn't make the definition of σ complete. For that, we need to define the residual strategies σ h i when h is not a prefix of outcome(σ). We also define those σ h in terms of σh . Now, any path h ending at configuration Similarly, for any path h ending at configuration

c 1 = (v 1 , v 1 , v 1 ) is not prefix of outcome(σ),
c 2 = (v 2 , v 2 , v 2 ), we define σh (c 2 ) = (σ h i (c 2 )) i∈ 3 to

C

In this Chapter, we have introduced a model of network congestion games, namely dynamic NCG, which di ers from commonly studied model of NCG in two aspects: (a) simultaneous costcomputation, and (b) dynamic strategies. We believe worth considering. We have also discussed brie y the solution concepts, mainly de nitions and example, both for optimizing individual and aggregate cost: namely Social optima, Nash equilibria and Subgame perfect equilibria. Now, in the subsequent chapters of this part, we will study more on these solution concepts one by one, while in Part II, we will be focusing on the model where the number of player is a parameter.

S O

In a congestion game, players play with the objective to traverse from their source to target vertex with minimal individual accumulated cost. But, their sel shly chosen strategies may result in a sub-optimal social cost. Therefore, a system which wants to optimize the overall cost, might be interested in nding out a solution by which it can assign strategies to individual players in its own interest. In this chapter, we address this problem for dynamic NCG by studying the optimal solution concept for a system as a whole, namely Social optima (SO).

Here, we recall from Section . of Chapter , that for a strategy pro le σ = (σ i ) i∈ n , we de ne the social cost of σ as soccost(σ) = i∈ n cost i (ρ), with ρ = outcome(σ).

In order to compute the optimal social cost for a dynamic NCG, we consider a decision version of this problem (Problem . below). In this chapter, we show di erent approaches to solve this problem. Starting with a brief explanation of a very naive approach at the very beginning of Section . , we go on to explain an abstract weighted graph approach in Section . . for symmetric NCG. Then, we explain why this approach fails for non-symmetric NCG on an example, and subsequently we explain an adaptation called src-abstract weighted graph approach in Section . . to nally solve for the non-symmetric case. We conclude the section by showing that the decision problem can be solved in PSPACE. In section . , we show a reduction from Partition problem to symmetric NCG to conclude that the problem is NP-hard.

Problem . (CONSTRAINED-SO).

Given a dynamic NCG G and a bound K ∈ N, does there exists a strategy profile with social cost less than or equal to K? Remark . . Concerning CONSTRAINED-SO, some immediate observations are:

• We take a non-negative integer K as the bound in CONSTRAINED-SO because the cost functions, f ∈ F, maps an edge to a non-negative integer by our assumption on the model. Hence, the individual cost, cost i (ρ) for any path is a non-negative integer too, so is the social cost soccost(σ) of strategy profile σ.

• Once we are able to solve Problem . , we can compute the optimal social cost of a dynamic NCG G = A, n, g by the binary search Algorithm . Note that, the initial value for U (see line of Algorithm ) is an upper bound of social cost for any strategy profile, hence the optimal social cost must be less than or equal to U , which justifies the above binary search as a way to compute the optimal social cost of G.

In section . , we rst give an algorithm to solve CONSTRAINED-SO in PSPACE, then we show that even for symmetric dynamic NCGs, CONSTRAINED-SO is NP-hard.

Social Optima

Algorithm Binary search to compute optimal social cost

: procedure Opt-soccost(G) : U = (v,f,v )∈E f(n) : L = 0; : while L ≤ U do : if L = U -1 then return U : else : K := L+U 2 :
Solve CONSTRAINED-SO problem for G and K

: if the answer is "Yes" then

: U := K : else : L := K S CONSTRAINED-SO
To begin with, recall what we de ned as the con guration graph M = C, T associated to G and thereafter its extension to a concurrent game structure (CGS) S from Section . . Note that, it su ces to nd a path ρ in S with social cost less or equal to a given value K. Indeed, for a path ρ = (c j , w j , c j+1 ) j≥1 , we can de ne a blind strategy pro le σ = (σ i ) i∈ n such that outcome(σ) = ρ as follows: by de nition, each edge (c j , w j , c j+1 ) of ρ can be viewed as U (c j , e j ) for some edge vector e j = (v j,i , f j,i , v j,i ) i ∈ E n , and we de ne the blind strategy σ i (which can be written as path) to be (v j,i , f j,i , v j,i ) j≥1 .

As the size of M (which is also the size of S) is O(|V | n ), where the number of players n is encoded in binary, this algorithm where we non-deterministically guess a path S, uses exponential space in the number of bits needed to encode n. However, we may not need to use the exact con guration to assert the existence of such a path. In the following, for pedagogical purposes, we rst de ne an abstract weighted graph associated with G, and solve the problem for symmetric (where there is a unique source-target pair for all players) NCGs and then we extend the same to what we call a src-abstract weighted graph associated with G and solve the same problem for non-symmetric NCG.

A W S

CONSTRAINED-SO

S NCG

With a con guration c, we associate an abstract con guration c ∈ n V , de ned as c(v) = #{i ∈ n : c(i) = v}. The abstract weighted graph associated with an NCG (not necessarily symmetric) G = A, n, g is a weighted graph P = A, B , where A contains all abstract con gurations and there is an edge (a, w, a ) ∈ B ⊆ A × N × A if, and only if, there is a mapping b : E → n such that e∈E b(e) = n, which intuitively means that b(e) players are taking the edge e in the current transition from abstract con guration a to a . Moreover, they satisfy the following:

. Solving the CONSTRAINED-SO problem

a(v) = e=(v,f,v ) b(e) w = e=(v,f,v ) b(e) × f(b(e)) a (v) = e=(v ,f,v)
b(e).

Similarly to the CGS representation, an abstract path of a network congestion game is either a single abstract con guration or a non-empty, nite or in nite sequence of consecutive edges in the abstract weighted graph P. The cost of an abstract path is the sum of weights of its edges (if any). Then we have, Lemma . . For NCG G, For any w ∈ N ∪ {+∞}, there is a path in M with social cost w if, and only if, there is an abstract path in P with the same cost w.

Proof. From any path ρ = (c i , w i , c i+1 ) i≥0 in M, a path τ = (a i , w i , a i+1 ) i≥0 can be constructed in P, where the a i 's are Parikh images [ ] of the c i 's.

For the other direction, let us consider a path τ = (a i , w i , a i+1 ) i≥0 of P. From this, we can construct a path in M by starting with a con guration c 0 , of which a 0 is the Parikh image and then continuing with c i for each i > 0 such that a i 's are Parikh images of c i 's respectively. By de nition of P itself, we get the existence of such a c 0 , and subsequently c i for i > 0. Moreover, w i 's remain unaltered as it is in the path in M. Note that, there might be multiple paths in M that can be associated to a path in P in such a way, but existence of one su ces for our purpose.

With this, we consider a symmetric NCG G = A, n, g , where there is a s in src and t in tgt such that, g(s, t) = n. Recall K is the value in the CONSTRAINED-SO problem so that we look for a strategy pro le in G with social cost less or equal to K.

Algorithm. We consider the abstract weighted graph P = A, B associated with G, and start a path nding algorithm from the vertex cs , where cs (s) = n, with a counter L initialized at 0. At each step, from the current vertex a of A, we guess an edge (a, w, a ) ∈ B, check whether L+w is still less or equal to K. If it is so, the guess is correct, hence we change the current con guration to a and update the counter value to L+w. We keep another counter len, also initialized at 0, which we increment by 1 each time we make a successful guess. The algorithm terminates whenever it reaches a such that a (t) = n, or when len exceeds n V . As the counter is singly exponential in size of the input (# of bits needed to encode n), this non-deterministic algorithm runs in polynomial space. Hence, by Savitch's theorem [ ], the problem is in PSPACE.

When the algorithm terminates after reaching ct , we know that there is a path in P with cost less or equal to K. By lemma . , that means there is a path ρ in M with social cost less or equal to K, which again asserts the existence of a strategy pro le σ with soccost(σ) ≤ K.

Note that, in the algorithm, we look for a path of length up to n V , which is the maximum length of any path without a cycle. Even though, any path in P corresponds to a path in M with same social cost as stated in Lemma . , it is also true that any cycle in P may not necessarily correspond to a cycle in M, because two di erent con gurations of M, which are permutations of each other, correspond to same abstract con guration of P (because their Parikh images are identical). However, in a symmetric network congestion game, as all players have same sourcetarget, a transition from one permutation to another permutation of positions between players only contributes in increasing the social cost just like a cycle does. Hence, from an abstract path τ of P containing a cycle, we can construct a path τ of M with social cost less than that of ρ.

The construction goes as follows. Let a ∈ A is the con guration of P, on which τ completes its cycle. Let us also suppose that ρ is a path in M which corresponds to τ , by Lemma . we know such a path exists. Now the cycle on a of τ corresponds to some path from c 1 to c 2 of ρ, where for c 1 , c 2 of C there is a permutation φ : n → n such that c 1 (i) = c 2 (π(i)) for all i. This necessarily implies c1 = c2 = a. Let us assume in the path from c src to c 1 to c 2 in C, Player i follows the path s

π 1 -→ u i π 2 -→ v i , then by construction Player φ(i) follows the path s π 1 -→ v i π 2
-→ u i . We construct the path ρ in C by letting Player i follow the path s π 1 -→ v i , and Player π(i) follow the path s π 1 -→ u i for each i, and this gives us a direct path from c src to c 2 without occurring c 1 . For the rest, we let them follow their paths from c 2 to c tgt of ρ. As we remove some positive weighted parts of the path τ , the resulted path must have less weight than τ . Again from Lemma . , this means there is a path ρ with social cost less than that of ρ. Following this construction for every cycle of τ until there is no cycle remains, we have, Lemma . . In symmetric NCG G, if an abstract path τ of P containing a cycle corresponds to a path ρ in M, then there is a path τ in M without any cycle and τ has lower cost than that of τ , which also corresponds to a path ρ in M.

This justi es why we only guess a path in P without a cycle. But, Lemma . is not necessarily true for non-symmetric NCG. Consider the following example which shows why it is not true for a non-symmetric NCG. . , where g(s 1 , t 2 ) = 1 and g(s 2 , t 1 ) = 1. Here cost-functions f's are omitted from the arena because they are not relevant for current discussion. In the abstract weighted graph P associated to G, any path that corresponds to a complete path of M contains a cycle (c, w, c), where c = (0, 1, 1, 0) and w depends on the f's. Hence, the above algorithm discards any path containing a cycle, it would not answer "yes", even though there might be a profile with social cost less than the given K. In conclusion, the algorithm is not sound for non-symmetric NCG.

Example . . Consider the non-symmetric NCG

G = A, 2, g , depicted in Figure
Thus, we extend the abstract weighted graph to what we call src-abstract weighted graph in the sequel and solve the general CONSTRAINED-SO problem based on this.

src

W G S

CONSTRAINED-SO

NCG

An src-abstract weighted graph associated to an NCG is an extension of the abstract weighted graph, where additional to the Parikh image of the con guration, we store information about the source vertices of the players. With a con guration c ∈ C of the multi-weighted con guration graph M associated to G = A, n, g , we associate an src-abstract con guration C , which is a (|src| + 1) × |V | matrix over n , and is de ned as follows:

C (0, v) = #{i ∈ n : c(i) = v} for each v ∈ V, and
C (s, v) = #{i ∈ n : c(i) = v, src(i) = s} for each s ∈ src, v ∈ V
Here recall that we de ned src(i) to be the source vertex of Player i, which we get from g and the arbitrary ordering that we considered in Section . . Intuitively, C (0, v) is the Parikh image of . Solving the CONSTRAINED-SO problem

s 1 s 2 v 1 v 2 t 1 t
v ∈ V C (s, v) = e=(v,f,v ) b(s, e) w = s∈V,e∈E b(s, e) × f(b(s, e)) C (s, v) = e=(v ,f,v) b(s, e)
Similar to the abstract weighted graph, an src-abstract weighted path of an NCG is either a single src-abstract con guration or a non-empty, nite or in nite sequence of consecutive edges in P. The cost of an src-abstract weighted path is the sum of weights w's of its edges (if any). Therefore, here we have a counterpart of Lemma . as follows:

Lemma . . For any w ∈ N ∪ {+∞}, there is a path in M with social cost w if, and only if, there is an src-abstract weighted path in P with cost w.

We now describe below an algorithm for solving the CONSTRAINED-SO problem for G = A, n, g and K ∈ N.

Algorithm. We consider the src-abstract weighted graph P = A , B and start a path nding algorithm from the vertex C src ∈ A , where C src is the src-abstract con guration corresponding to c src of C. Hence, by de nition, for s ∈ src,

C src (0, s) = C src (s, s) = t∈tgt g(s, t) and for v ∈ V \ src, C src (0, v) = 0.
Additionally, at each step of the algorithm, we maintain two counters L, len, both of which initialized at 0, and a matrix of size |src| × |tgt| M which is initialized at all zero entries. Here, L keeps track of the social cost up to the current step and len keeps track of the length of ongoing the src-abstract weighted path. Starting from C src , at each step, we make a guess (C , w, C ) ∈ B. Then we check the following three things to declare the guess as "correct":

• Check whether L+w ≤ K • Check whether len ≤ n |V | 2 +|V | • If for some s ∈ src, t ∈ tgt, C (s, t) > C (s, t), check whether M (s, t) ≤ g(s, t).
The rst two checks are to maintain that we are guessing a path without a cycle in P, and with social cost less than the threshold K. The third condition is to check when a new player reaches a target vertex t, whether the number of players with source s and target t is being maintained.

If all the above checks answers positively, we update the current vertex from C to C , and increment L and len by w and 1 respectively. Finally, for every s of src and t of tgt, we update M (s, t) by adding C (s, t) -C (s, t). Then, we proceed to make the next guess unless ∀t ∈ tgt, C (0, t) = s∈src g(s, t). If one of the checks fails, it means the guess is not correct.

Again, here we have relied upon the following fact:

. Solving the CONSTRAINED-SO problem Lemma . . If there is a weighted path in M with cost less or equal to K, then there is an src-abstract weighted path without a cycle in P with social cost less or equal to K.

                        (s 1 , s 2 ) 0 . . . . . . (s 1 , t 2 ) 0 (s 2 , t 1 ) 0 . . . . . . (t 2 , t 2 ) 0                         (s 1 , s 2 ) 0 . . . . . . (s 1 , t 2 ) 0 (s 2 , t 1 ) 0 . . . . . . (t 2 , t 2 ) 0                         (s 1 , s 2 ) 0 . . . . . . (s 1 , t 2 ) 0 (s 2 , t 1 ) 0 . . . . . . (t 2 , t 2 ) 0                         (s 1 , s 2 ) 0 . . . . . . (s 1 , t 2 ) 1 (s 2 , t 1 ) 1 . . . . . . (t 2 , t 2 ) 0 s 1 s 2 v 1 v 2 t 1 t 2 s 1 s 2 v 1 v 2 t 1 t 2 s 1 s 2 v 1 v 2 t 1 t 2 s 1 s 2 v 1 v 2 t 1 t 2 s 1 s 2 v 1 v 2 t 1 t 2 s 1 s 2 v 1 v 2 t 1 t 2 s 1 s 2 v 1 v 2 t 1 t 2 s 1 s 2 v 1 v 2 t 1 t 2 f e 1 (1) + f e 2 (1) ≤ K f e 3 (1) + f e 4 (1) ≤ K f e 5 (1) + f e 6 (1) ≤ K
Proof. Suppose ρ = (c i , w i , c i+1 ) 0≤i≤|ρ|-1 is a path in M with social cost less or equal to K. First of all, we can assume that ρ contains no cycle, because if it does, we can remove the cycle and get a path with lower social cost. Now our job is to show such a path in M has a corresponding path in P, which also does not contain any cycle. This is not readily obvious because two con gurations c and c of M may have the same src-abstract con guration in P. Here, we show that if two such con gurations appear in ρ, we can construct a shorter path with less social cost. This construction intuitively truncates the part between these two con gurations, but this is not exactly the same as removing a cycle, hence we need the following justi cation.

Let us assume there are two con gurations c j and c l with j < l ≤ |ρ| -1 such that there exists a permutation map φ : n → n satisfying c l (φ(k)) = c j (k) for all k ∈ n . Then we can assume that there must be an index k ∈ n such that Player k and Player φ(k) do not have same source vertex. Because, if it is not the case , i.e, if for all k ∈ n src(φ(k)) = src(k), then we could construct another path ρ = (ĉ i , w i , ĉi+1

) 0≤i≤|ρ |-1 in M as follows: Suppose Player k's Social Optima path in ρ is s π 1 -→ u π 2 -→ v and Player φ(k)'s path is s π 1 -→ v π 2 -→ u, then in ρ, we assign Player k's path to s π 1 -→ v and Player φ(k)' path to s π 1
-→ u, and so on for every such pair. Hence, we could take ρ instead of ρ.

Therefore, we assume for any two con gurations c j and c l , with j < l, either they are not permutations of each other, or if they are, then there is at least one pair of that players that di er in their source vertex. From Lemma . , we know there is a corresponding path τ = (C i , w i , C i+1 ) 1≤i≤|τ | in P with same social cost. Now, by construction, in τ , any two C j and C l must di er at some (s, v) ∈ src × V . Hence, τ doesn't contain a cycle.

As the size of P is at most n (|V |+1)×|V | , which is exponential in the input size, we need a counter of size that is polynomial in the input. Therefore, the non-deterministic path nding algorithm yields the following complexity result: Theorem . . CONSTRAINED-SO can be solved in PSPACE.

C L B

CONSTRAINED-SO

In this section, we show that even for symmetric dynamic NCGs, the CONSTRAINED-SO problem is NP-hard by reducing a well-known NP-complete problem, namely the Partition problem. The reduction has been adapted from [ , Theorem . ] showing NP-hardness of the same problem in classical (non-dynamic) NCG.

Theorem . . The CONSTRAINED-SO problem is NP-hard in dynamic NCGs.

Proof. Recall[ ] that the partition problem asks whether a given set of positive integers can be partitioned into two subsets such that the sum of the numbers in the two subsets are equal. Consider an instance L = (r i ) i∈ m of this Partition problem, and let S = r i ∈L r i /2, M = 14S+12m+1, and n = 2S+2m. For any r ∈ N, we de ne the threshold cost function T r as T r (i) = 1 if i ≤ r, and T r (i) = M otherwise. We construct a dynamic NCG arena A L with vertices V = {src, tgt, d 1 , d 2 } ∪ {s i , a i,1 , a i,2 } i∈ m . The transitions are de ned as follows:

• for each i ∈ m , there is a transition from src to s i with cost function T r i +2 ;

• from each s i , there is a transition to a i,1 and another one to a i,2 with the same cost function that assigns cost 2 for one player, and 4 for more;

• for i ∈ m and j ∈ {1, 2}, there is a transition from a i,j to d j with constant cost 1, and a transition to tgt with cost function T 1

• from each d j , there is a transition to tgt with cost function T S .

The construction is illustrated in Figure . . We prove that there exists a strategy pro le in G L = A L , n, g , where g(src, tgt) = n, with social cost less than M if, and only if, L is a positive instance of the partition problem. Assume that the instance L has a solution L 1 , L 2 . We describe the behaviour of the strategy pro le in G L achieving social cost less than M .

. Complexity Lower Bound for CONSTRAINED-SO

src s i . . . . . . a i,1 a i,2 d 1 d 2 tgt 1 if x≤r i +2 M if x>r i +2 2 if x≤1 4 if x>1 2 if x≤1 4 if x>1 1 if x≤S M if x>S 1 if x≤S M if x>S 1 if x=1 M if x>1 1 if x=1 M if x>1
Figure .

: The reduction of Theorem . . The gure shows the edges involving states s i , a i,1 , a i,2 . The full graph is obtained by reproducing the shown construction for all i ∈ m .

• Initially, all players are at src. During the rst step, for each i ∈ m , (r i + 2) players move to s i . This incurs a total cost of i∈ m r i + 2 = i∈ m r i + 2 × m = 2S + 2m;

• Consider i ∈ m , and let j ∈ {1, 2} be such that r i ∈ L j . From state s i we let r i + 1 players move to a i,j , and one player to a i,3-j . The r i + 1 players each pay a cost of 4, and other player a cost of 2. Overall, we get a total cost of i∈ m ((

r i + 1) × 4 + 1 × 2) = 8S + 4m + 2m = 8S + 6m;
• From each a i,j , one player takes the transition directly to tgt. All other players move to d j .

Overall, 2m players directly move to tgt, while all other players, that are 2S of them, move to {d 1 , d 2 }. The total cost of this step is therefore 2S + 2m × 2 = 2S + 4m;

• From each d j , players necessarily move directly to tgt. For each i ∈ m and j ∈ {1, 2}, exactly r i players arrive to d j from a i,j . Thus there are exactly S players in each d j , so that the total cost of this step is 2S.

Summing over all steps, the social cost of this strategy pro le is 14S + 12m < M . Now for the opposite direction, consider any strategy pro le σ in A, n , outcome of which is π in the associated con guration graph, with social cost less than M . We are going to construct a partition of L. First we divide the path taken by the players from src to tgt in three phases: Phase : from src to some s i ; Phase : from some s i to some a i,j ; Phase : from a i,j to tgt, either directly or via d j . We now analyze the cost incurred by players under pro le σ (or, in path π) in all three phases.

In phase 1, each player pays either cost 1 or cost M . By assumption on π, all players must have a cost of 1, and this is only possible if r i + 2 players move to s i , for each i ∈ m . The total cost of this phase is thus 2S + 2m.

In phase 3, a player pays a cost of either 2, M or M + 1. The latter two cases are not possible by assumption. So phase 3's contribution to the social cost has to be 2 × n = 4S + 4m. Then, the social cost of phase 2 is strictly less than (14S + 12m + 1) -(2S + 2m) -(4S + 4m) = 8S + 6m + 1. By phase 1, there are r i + 2 players at each s i , so the minimum contribution to the social cost for these r i + 2 players is 2 × 1 + 4 × (r i + 2) = 4r i + 6. Summing over all i ∈ m , this yields r i ∈L (4r i + 6) = 8S + 6m. Thus, the social cost of phase 2 is 8S + 6m. But this Social Optima cost is achieved only when from each s i exactly one transition is taken by one player and the other transition is taken by r i + 1 players.

Therefore, each a i,j contains either one player or (r i + 1) players under σ. Given the cost functions, at most 2S players can move to tgt via d 1 or d 2 (otherwise players would get a cost of M ). So 2m remaining players must take the transition from some a i,j to tgt. But at each a i,j , there is a unique player that takes this transition due to the cost function. If a i,j contains r i + 1 players, r i players take the path via d j , each paying a cost of 2. As there are in total 2S players taking the route via some d j , and each d j can contain at most S players because of the cost functions, there must be exactly S players which arrive at each d j under σ. That is, for each i, j, there are exactly r i players coming from some a i,j to d j , and their total is S. This de nes the required partition of L.

Finally, let us also point out that the reduction is polynomial. Indeed the size of the arena A L is polynomial in the number of elements in the instance L and the number of players in G L is exactly the sum of the elements considered in L.

C

In this chapter, we consider the constrained SO problem, the decision version of which asks whether there is a strategy pro le with social cost less than or equal to the given threshold.

To solve this problem, we exploit the game structure, and using an abstraction of con gurations, we give a non-deterministic algorithm which veri es correctly if it is provided a strategy pro le which indeed has the social cost less than or equal to the threshold. Thus, the computational complexity of the constrained SO problem lies in PSPACE. For lower bound, we show even for the symmetric case, the problem is NP-hard. Therefore, a future work would be to reduce the complexity gap for the constrained SO problem.

N E

In this chapter, we will talk about one of the solution concepts that is most common in the context of non-zero-sum multi-player games, namely Nash Equilibria. Here, in dynamic NCG, as mentioned earlier, we can imagine each player plays selfishly, i.e, their objective is to go from their source to target vertices with minimal accumulated individual cost. As a sel sh player, each player tries to choose their strategy in a way that changing this strategy would not bene t to themselves if everyone else plays the same -this brings a stability in the players' choices, and that is formalized in a Nash equilibrium.

Recall De nition . from Chapter : a strategy pro le is a Nash Equilibrium (NE) if each player's strategy in that pro le is a best response to the rest of the players' strategies. In other words, no player can lower their cost by unilaterally deviating from it.

We rst investigate whether NE exist in dynamic NCG in Section . , and answer the question positively. We then address the problem whether in a given dynamic NCG, given a bound K there is a Nash equilibrium with social cost not more than K. We obtain complexity results on this problem in Section . .

E N E

In order to show existence of dynamic NCG, we rst establish that NE exist when the strategy pro les, including deviations, are restricted to blind strategies, i.e, blind NE exist in dynamic NCG (recall de nitions from Section . . ). With that, we will then show that those blind NE are in fact NE in dynamic NCG.

To prove that blind Nash equilibria always exist, we establish that dynamic NCG with blind strategies are potential games [ , ] which are known to have Nash Equilibria.

E N E NCG

A potential function[ ] is a function which associates a value to a strategy pro le, which is also referred to as a potential value of a strategy pro le with respect to the corresponding function.

Potential function must satisfy the following property: when a player unilaterally deviates from the strategy pro le, the change in that player's accumulated cost between both strategy pro les is equal to the change in the potential value of the two pro les. A game is called a potential games if there exists a potential function associated to the game.

Nash Equilibria

Consider a dynamic NCG G = A, n, g , a blind strategy pro le π = (π i ) i∈ n , and let N π denote the maximum length of the paths prescribed by π. We de ne the following function, which is an adaptation of that used in [ ]:

ψ(π) = Nπ j=1 e∈E loade(π,j) i=1 f e (i)
where load e (π, j) denotes the number of players who take the edge e at j th step of π, and f e is the cost function on edge e.

Lemma . . ψ is a potential function for G restricted to only blind strategies.

Proof. Here we consider a blind strategy pro le π = (π i ) i∈ n and another pro le π = (π i , π -i ), where Player i deviates from π i to π i . As earlier, we also denote N π and N π to be the length of longest paths prescribed by π and π respectively. Now when Player i unilaterally deviates from its blind strategy π i to π i , the only edges on which a change in the number of players happens are the edges which are part of exactly one of π i and π i . Moreover, even on these edges the load di ers by exactly 1: it gets increased on the edges which are in π i but not in π i , and gets decreased on the edges which are in π i but not in π i . Therefore, we have the following:

ψ(π) -ψ(π ) = Nπ j=1 e∈E loade(π,j) i=1 f e (i) - N π j=1 e∈E loade(π ,j) i=1 f e (i) = |π i | j=1 e∈π i f e (load e (π i , j)) - |π i | j=1 e∈π i f e (load e (π i , j)) = cost i (π) -cost i (π )
Hence, ψ indeed is a potential function.

Using the above-de ned potential function, one can derive an algorithm to nd a Nash equilibrium, by a classical best-response iteration. Starting with an arbitrary blind strategy pro le, at each step we replace some player's strategy with their best-response, and we continue as long as some player's cost can be decreased. When this procedure terminates, the pro le at hand is a blind Nash equilibrium. In this argument, what remains is to show that in dynamic NCG with blind strategy pro les, best responses exist.

Lemma . . Given a dynamic NCG G = A, n, g , a blind strategy profile π, and i ∈ n , Player i has a blind strategy π i that is their best response to π. This strategy has a size at most

N π + |V | and can be computed in time O(|V | 2 .N 2 π ).
Proof. We let A = V, E, src, tgt . We de ne a weighted graph G obtained by concatenating N π + 1 copies of A, in which the moves of all players but Player i are hard-coded. Formally, S = V × N π + 1 , E where:

. Existence of Nash Equilibria

• For each edge (v, f, v ) in E, there is an edge ((v, N π + 1), f(1), (v , N π + 1)) in E : this encodes the fact that, after N π + 1 steps, all other players have reached the target state, and Player i plays alone;

• For each edge e = (v, f, v ) in E and each index 1 ≤ k ≤ N π , there is an edge ((v, k), w, (v , k + 1)) in E with w = f(load e (π -i , k) + 1), where load e (π -i , k) is the number of players (except Player i) taking edge e at step k when following π -i . This way, w corresponds to the cost incurred to Player i if they were to take edge e at step k.

By construction, any blind strategy π i for Player i in A, n, g corresponds to a path ρ from (src(i), 1) to (tgt(i), N π + 1) in S such that the weight of ρ is equal to cost i (π -i , π i ): Player i can follow the exact same path as they would in S by ignoring the second component in the state space of S.

Conversely, any path in S from (src(i), 1) to (tgt(i), N π +1) corresponds to a path from src(i) to tgt(i) in A, which is a blind strategy π i . The cost of the path is equal to cost i (σ -i , σ i ) by construction.

This shows that the best-response strategy can be computed by a shortest weighted path computation in S. This path has size at most N π + |V |: after N π steps, the path enters con gurations of the form (c, N π + 1), so all other players have already reached the target; since the shortest path is acyclic, the bound follows.

This computation can be done with Dijkstra's algorithm, which runs in

O((|V | • N π ) 2 ).
Finally, we have the following:

Theorem . . In dynamic NCG, blind Nash equilibria always exist, and we can compute one in pseudo-polynomial time.

Proof. We apply the previous lemma as follows. Consider an initial strategy pro le π 0 assigning to each player any acyclic path (thus, of length at most |V |) from their corresponding source to target. We have

ψ(π 0 ) ≤ |V | • e∈E n i=1 f e (i) ≤ |V | • n • max e∈E f e (n)
. This quantity is pseudo-polynomial in the size of A, n, g .

Let π 1 , π 2 , . . . denote the strategy pro les generated by this iterative procedure. Let m i = N π i . By Lemma . , we have

m i ≤ m 1 + (i -1)|V |. We then have k i=1 |V | 2 m 2 i ≤ |V | 2 k i=1 (m 1 + i|V |) 2 ≤ |V | 2 k i=1 (n|V | + i|V |) 2 ≤ |V | 4 • k • (n + k) 2
where the second step follows from m 1 ≤ n|V |. Applying Lemma . again, the running time of the iterative procedure until the k-th

step is O(|V | 4 • k • (n + k) 2 ).
In the worst case, we stop after k = ψ(π 0 ) steps, so that the algorithm runs in pseudo-polynomial time. We now show that blind NE are in fact NE. This is proved using the observation that given a blind strategy pro le, the most pro table deviation for any player can be assumed to be a blind strategy.

Lemma . . In dynamic NCG, blind NE are NE.

Proof. Consider a blind NE π = (π i ) i∈ n for dynamic game G = A, n, g . This means no player has a unilateral deviating blind strategy by which they can improve their cost.

Let us suppose π is not an NE of G, which implies there is some player i who has a unilateral deviating strategy σ i such that cost i (σ i , π -i ) < cost i (π). Now, let us consider outcome i (σ i , π -i ) which is a path from src(i) to tgt(i) in A. As all but Player i are playing with blind strategy pro le, if we replace Player i's strategy σ i by the blind strategy outcome i (σ i , π -i ), none of the players' outcome and cost are going to change. Hence,

cost i (outcome i (σ i , π -i ), π -i ) < cost i (π i , π -i ),
which is a contradiction to the fact that π is a blind NE. Therefore, π, a blind NE, is indeed an NE for G.

Lemma . . There exists a dynamic NCG with an NE σ such that for all blind NE π , we have cost(π) < cost(π ).

Proof. The proof is based on the dynamic NCG depicted on Fig. . , for which we prove there is an NE with total cost 36, while any blind NE has higher social cost.

We consider the arena A shown in Fig. . with n = 3 players, with g(s, t) = 3.

s q 1 q 2 q 3 q 4 q 5 q 6 t x → 2 x e1 x → 3 x e 5
x → 3 e 2

x → 3 e 3 x → 2 x e 4

x → x e 6

x → 2x e 7

x → The strategy pro le σ = (σ i ) i∈ 3 is de ned as follows.

2 x e8 x → x p u n 1 x → 3 p u n 2
For i ∈ {1, 2}, strategy σ i chooses e 1 e 2 e 3 e 4 with the following exception: if Player 3 -i picks e 5 at s, then σ i takes pun 1 at q 1 ; if Player 3 -i picks pun 1 at q 1 , then σ i takes pun 2 at q 2 . Strategy σ 3 follows e 5 e 6 e 7 e 8 .

We have cost i (π) = 14 for i ∈ {1, 2}, and cost 3 (π) = 8, so cost(π) = 36.

.

Constrained NE Problem

We rst show that π is a Nash equilibrium. First, Player 3 has no incentive to deviate since taking e 1 at q 0 would alone cost 6, and the rest of the path, either through e 2 or pun 1 e 7 , has a cost more than 3 so that the total cost is more than cost 3 (π). For Players 1 and 2, there are three states where they can deviate. If Player i ∈ {1, 2} chooses e 5 at q 0 , then the cost is 6 + 2 + 6 + 6 = 20 as Player 3 -i chooses pun 1 . Similarly, if they choose pun 1 at q 1 then Player 3 -i chooses pun 2 at q 2 which yields a cost of 4 + 1 + 4 + 6 = 15 > cost i (π). Last, if Player i chooses pun 2 at q 2 , their cost is 4 + 3 + 3 + 4 = 14 = cost i (π).

We now show that the pro le π has a lower cost than any blind Nash equilibrium.

There are only four possible blind strategies in our game following one of the four paths ρ 1 = e 1 e 2 e 3 e 4 , ρ 2 = e 5 e 6 e 7 e 8 , ρ 3 = e 1 pun 1 e 7 e 8 and ρ 4 = e 1 e 2 pun 2 e 8 . We will represent these pro les as tuples of paths, e.g. (ρ 1 , ρ 1 , ρ 2 ). We are going to consider all possible tuples and show that each tuple is either not a Nash equilibrium or has cost more than cost(π) = 36.

Observe that when we permute the players in a Nash equilibrium, it remains a Nash equilibrium with the same social cost. So we only need to consider the case where all players use the same strategy (4 possibilities), the case where they all choose distinct strategies ( 43 ), and the case where two of them choose the same strategy and the other one a di erent one ( 41 × 3 1 ). So there are 20 pro les to check, and the rest of the pro les are permutations of these.

The following is an exhaustive list of the costs of these pro les.

cost(ρ 1 , ρ 1 , ρ 1 ) = 18 × 3 = 54 cost(ρ 2 , ρ 2 , ρ 2 ) = 24 × 3 = 72 cost(ρ 3 , ρ 3 , ρ 3 ) = 21 × 3 = 63 cost(ρ 4 , ρ 4 , ρ 4 ) = 18 × 3 = 54 cost(ρ 1 , ρ 2 , ρ 3 ) = 12 + 13 + 12 = 37
cost(ρ 1 , ρ 3 , ρ 4 ) = 12 + 14 + 15 = 41 cost(ρ 1 , ρ 2 , ρ 4 ) = 12 + 12 + 13 = 37 cost(ρ 2 , ρ 3 , ρ 4 ) = 14 + 15 + 16 = 45 All pro les have cost at least 36, and the only one that matches is (ρ 1 , ρ 1 , ρ 2 ). However, this is not a Nash equilibrium. In fact, the cost of Player 1 here is , but they could pro t from deviating to ρ 3 since cost 1 (ρ 3 , ρ 1 , ρ 2 ) = 13.

cost(ρ 1 , ρ 1 , ρ 2 ) = 14 × 2 + 8 = cost(ρ 1 , ρ 1 , ρ 3 ) = 16 × 2 + 11 = 43 cost(ρ 1 , ρ 1 , ρ 4 ) = 14 × 2 + 14 = 42 cost(ρ 2 , ρ 2 , ρ 1 ) = 16 × 2 + 10 = 42 cost(ρ 2 , ρ 2 , ρ 3 ) = 20 × 2 + 15 = 55 cost(ρ 2 , ρ 2 , ρ 4 ) = 18 × 2 + 14 = 50 cost(ρ 3 , ρ 3 , ρ 1 ) = 16 × 2 + 14 = 46 cost(ρ 3 , ρ 3 , ρ 2 ) =

C NE P

Computing some (blind) NE may not be satisfactory for two reasons: one might want to compute the best (or the worst) NE in terms of the social cost; and as Lemma . claims, blind NE are suboptimal, i.e., a lower social cost can be achieved by NE with general strategies. This justi es the study of more complex strategy pro les. In this section, we address these two concerns by considering a constrained NE problem, similar to CONSTRAINED-SO considered in the last chapter, Nash Equilibria which decides existence of an NE with bounded social cost. As it has been shown in Chapter , a binary search using the solution to this decision problem gives us the optimal cost -here, in particular, optimal social cost for an NE in a given dynamic NCG. Hence, we consider the following problem:

Problem . (CONSTRAINED-NE). Given a dynamic NCG G and a bound K ∈ N, does there exist an NE with social cost less than or equal to K?

We rst characterize the outcome of any NE, and then we use the characterization both to decide CONSTRAINED-NE and to de ne a strategy pro le with the same outcome.

C N E Let us consider a dynamic NCG A, n, g , and the corresponding game structure S = C, T, M, U . Given two con gurations c, c with c ⇒ c , we let cost i (c, c ) denote the cost of Player i on this transition from c(i) to c (i). We de ne dev i (c, c ) as the set of all con gurations reachable when all players but Player i choose moves prescribed by the given transition c ⇒ c :

dev i (c, c ) = {c ∈ C | c ⇒ c and ∀j ∈ n \ {i}. c (j) = c (j)}.
Moreover, we de ne the value of con guration c for Player i is

val i,c = sup σ -i ∈S -i inf σ i ∈S i cost i ((σ -i , σ i ), c).
where recall S i is the set of all Player i strategies, and we denote S -i to be the set of strategy pro les for the coalition of all but Player i. Here, val i,c corresponds to the value of a two player zero-sum game where Player i plays against the opposing coalition, starting at c. Intuitively, it is the worst cost that Player i cannot avoid to pay when the opposing coalition plays against them from con guration c. By [ ], those values can be computed in polynomial time in the size of the game.

Lemma . . For a dynamic NCG G = A, n, g , the value of configuration c for Player i, val i,c , can be computed in EXPTIME, Proof. Here the two-player game between Player i and the opposing coalition is a game with state space |V | × n -1 |V |×(|V |+1) because each state keeps track of the position of Player i and the abstract position of the coalition similar to what we de ned as an src-abstract weighted graph in Section . . . It follows that each val i,c can be computed in exponential time in the size of the input A, n, g . Moreover, memoryless optimal strategies exist (in S), that is, the opposing coalition has a memoryless strategy σ -i to ensure a cost of at least val i,c from c.

The characterization of Nash equilibria outcomes is given in the following lemma.

Lemma . . For dynamic NCG G = A, n, g , a path ρ in the corresponding concurrent game structure S is the outcome of a Nash equilibrium if, and only if,

∀i ∈ n . ∀1 ≤ l < |ρ|. ∀c ∈ dev i (ρ(l), ρ(l + 1)). cost i (ρ ≥l ) ≤ val i,c + cost i (ρ(l), c).
.

Constrained NE Problem

The intuition is that if the su x cost i (ρ ≥l ) of ρ has cost more than val i,c + cost i (ρ(l), c), then Player i has a pro table deviation regardless of the strategy of the opposing coalition, since val i,c is the maximum cost that the coalition can in ict to Player i at con guration c where the deviation is observed. The lemma shows that the absence of such a su x means that a NE with given outcome exists, which the proof constructs.

Proof. Consider a Nash equilibrium σ = (σ i ) i∈ n with outcome ρ. Consider any player i, and any strategy σ i for this player. Let ρ denote the outcome of σ[i → σ i ]. Let l denote the index of the last con guration where ρ and ρ are identical. Since σ is a Nash equilibrium, we have

cost i (ρ) ≤ cost i (ρ ), that is, cost i (ρ ≥l ) ≤ cost i (ρ(l), ρ (l + 1)) + cost i (σ[i → σ i ], ρ ≤l+1 )
where cost i (σ[i → σ i ], ρ ≤l+1 ) is the cost for Player i of the outcome of the residual strategy

(σ[i → σ i ]) ρ ≤l+1
. Since the choice of σ i is arbitrary here, we have,

cost i (ρ ≥l ) ≤ cost i (ρ(l), ρ (l + 1)) + inf σ i ∈S cost i (σ[i → σ i ], ρ ≤l+1 ).

Moreover, we have inf

σ i ∈S cost i (π[i → σ i ], ρ ≤l+1 ) = inf σ i ∈S cost i (π[i → σ i ], ρ (l + 1))
since memoryless strategies su ce to minimize the cost [ ]. We then have

inf σ i ∈S cost i (π[i → σ i ], ρ (l + 1)) ≤ sup σ -i ∈S -i inf σ i ∈S cost i ((σ -i , σ i ), ρ (l + 1)).
We obtain the required inequality

cost i (ρ ≥l ) ≤ cost i (ρ(l), ρ (l + 1)) + sup σ -i ∈S -i inf σ i ∈S cost i ((σ -i , σ i ), ρ (l + 1)) ≤ cost i (ρ(l), c) + val i,c .
Conversely, consider a path ρ that satis es the condition. We are going to construct a Nash equilibrium having outcome ρ. The idea is that players will follow ρ, and if some player i deviates, then the coalition -i will apply a joint strategy to maximize the cost of Player i, thus achieving at least val i,c , where c is the rst con guration where deviation is detected.

Let us de ne the punishment function P ρ : Paths( A, n, g , c src ) → n ∪ {⊥} which keeps track of the deviating players and the step where such a player has deviated, here c src is the initial con guration where Player i is at src(i). For path h = h(c, w, c ), we write

P ρ (h ) =    ⊥ if h ≤ pref ρ, i if h ≤ pref ρ, h(c, w, c ) ≤ pref ρ, and i ∈ n min. s.t. c (i) = ρ(|h| + 1)(i), P ρ (h) otherwise.
Intuitively, ⊥ means that no players have deviated from ρ in the current path. If P π (h) = j, then Player j was among the rst players to deviate from ρ in the path h; so for some l, h(l)(j) = ρ(l)(j) but h(l + 1)(j) = ρ(l + 1)(j). Notice that if several players deviate at the same step, there are Nash Equilibria no conditions to be checked, and the strategy can be chosen arbitrarily. For each con guration c and coalition -i, let σ -i,c be the strategy of coalition -i maximizing the cost of Player i from con guration c; thus achieving at least val i,c . Player j's strategy in this coalition, for j = i, is denoted σ -i,c,j . For path h = h(c, w, c ), de ne

τ i (h ) =        (c (i), m(i), c (i)) if P ρ (h ) = ⊥, ρ(|h | + 1) = (c , w , c ),
and m ∈ E n is such that T (c , m) = (w , c ),

arbitrary if P ρ (h ) = i, σ -j,c,i (h ) if P ρ (h ) = j for some j = i.
The rst case ensures that the outcome of the pro le (τ i ) i∈ n is ρ. The third case means that Player i follows the coalition strategy σ -j,c after Player j has deviated to con guration c. The second case corresponds to the case where Player i has deviated: the precise de nition of this part of the strategy is irrelevant.

Let us show that this pro le is indeed a Nash equilibrium. Consider any player j ∈ n and any strategy τ j . Let ρ denote the outcome of (τ -j , τ j ), and l the index of the last con guration where ρ and ρ are identical. We have

cost j ((τ -j , τ j )) = cost j (ρ ≤l ) + cost j (ρ(l), ρ (l + 1)) + cost j ((τ -j , τ j ), ρ ≤l+1 ) ≥ cost j (ρ ≤l ) + cost j (ρ(l), ρ (l + 1)) + val j,ρ (l+1)(j) ≥ cost j ((τ i ) i∈ n ),
where the second line follows from the fact that the coalition switches to a strategies ensuring a cost of at least val j,ρ (l)(j) at step l; and the third line is obtained by assumption. This shows that (τ i ) i∈ n is indeed a Nash equilibrium and concludes the proof.

Even though, in this chapter, our main concern is CONSTRAINED-NE, we can easily generalize the problem with a bound, not just for the social cost, but also for any one or more player's individual accumulated cost. For an integer vector γ = (γ i ) i∈ n , and for a path ρ in the multi-weighted con guration graph M = C, T associated to a dynamic NCG G, γ-social cost is de ned by:

soccost γ (ρ) := i∈ n γ i cost i (ρ)
De nition . ( γ-minimal NE). For an integer vector γ = (γ i ) i∈ n , a strategy profile is called a γ-minimal NE if it is an NE with optimal γ-social cost.

In the following, we describe how we compute γ-minimal NE, which for γ i = 1 for all i ∈ n gives us the optimal NE.

A

We de ne a graph that describes the set of outcomes of Nash equilibria by augmenting the n-weighted con guration graph M = C, T . For any integer vector γ = (γ i ) i∈ n , we de ne the weighted graph

M A,n,g , γ = C , T with C = C × ( Y ∪ {0, ∞}) n where Y = |V | • max e∈E f e (n)
b i = min(b i -w i , min c ∈dev i (c(i),c (i)) cost i (c, c ) + val i,c -w i ). ( . )
Notice that by de nition of C , b i must be non-negative for all i ∈ n , so there are no transitions ((c, b), z, (c , b )) if the above expression is negative for some i. Notice also that the size of M A,n,g , γ is doubly-exponential in that of the input A, n , since this is already the case for C, while Y is singly-exponential.

Intuitively, for any path ρ that visits some state (c, b) in this graph, in order for ρ to be compatible with a Nash equilibrium, each player i must have cost no more than b i in the rest of the path. In fact, the second term of the minimum in ( . ) is the least cost Player i could guarantee by not following (c, w, c ) but going to some other con guration c ∈ dev i (c, c ), so the bound b i is used to guarantee that these deviations are not pro table. The de nition of b i in ( . ) is the minimum of b i -w i and the aforementioned quantity since we check both the previous bound b i , updated with the current cost w i (which gives the left term), and the non-pro tability of a deviation at the previous state (which is the right term). If this minimum becomes negative, this precisely means that at an earlier point in the current path, there was a strategy for Player i which was more pro table than the current path regardless of the strategies of other players; so the current path cannot be the outcome of a Nash equilibrium. This is why the de nition of M A,n,g , γ restricts the state space to nonnegative values for the b i .

We prove that computing the cost of a Nash equilibrium minimizing the γ-weighted social cost reduces to computing a shortest path in M A,n,g , γ . In particular, letting γ i = 1 for all i ∈ n , a γ-minimal Nash equilibrium is a best Nash equilibrium (minimizing the social cost), while taking γ i = -1 for all i ∈ n , we get a worst Nash equilibrium (maximizing the social cost).

Theorem . . For dynamic NCG A, n, g and vector γ, the cost of the shortest path from (c src , ∞ n ) to some (c tgt , b) in M A,n,g , γ is the cost of a γ-minimal Nash equilibrium.

Proof. We show that for each path of A, n, g from c src to c tgt , there is a path in M A,n,g , γ from (c src , ∞ n ) to some (c tgt , b) with the same cost, and vice versa.

Consider a Nash equilibrium π = (σ j ) j∈ n with outcome ρ = (c j , w j , c j+1 ) 1≤j<l . We build

a sequence b 1 , b 2 , . . . such that ρ = ((c j , b j ), γ • w j , (c j+1 , b j+1 )) 1≤j<l is a path of M A,n,g , γ . We set b 1 (j) = ∞ for all j ∈ n . For j ≥ 1, de ne b j+1 (i) = min b j (i) -w j (i), min c ∈dev j (c j (i),c j+1 (i)) cost i (c j , c ) + val i,c -w j (i) .
We are going to show that for all 1 ≤ j ≤ l, cost i (ρ ≥j ) ≤ b j , which shows that b j ≥ 0, and thus ρ is a path of M A,n,g , γ .

Nash Equilibria

We show this by induction on j. This is clear for j = 1. Assume this holds up to j ≥ 1. We have, by induction that cost i (ρ ≥j ) ≤ b j (i) for all i ∈ n . Moreover, since π is a Nash equilibrium, by Lemma . , ∀i ∈ n , cost i (ρ ≥j ) ≤ min c ∈dev i (ρ(j),ρ(j+1))

val i,c + cost i (ρ(j), c ).

Therefore,

cost i (ρ ≥j+1 ) = cost i (ρ ≥j ) -w j (i) ≤ min(b j (i) -w j (i), min c ∈dev i (ρ(j),ρ(j+1)) val i,c + cost i (ρ(j), c ) -w j (i))
as required, and both paths have the same γ-weighted cost.

Consider now a path

((c i , b i ), z i , (c i+1 , b i+1 )) 1≤i<l in M A,n,g , γ .
By the de nition of M A,n,g , γ , there exists w 1 , w 2 , . . . such that ρ = (c j , w j , c j+1 ) 1≤j<l is a path of A, n, g , and z j = γ • w j . So it only remains to show that that ρ is the outcome of a Nash equilibrium. We will show that ρ satis es the criterion of Lemma . . We show by backwards induction on 1 ≤ j ≤ l that for all i ∈ n ,

. cost i (ρ ≥j ) ≤ b j (i), . cost i (ρ ≥j ) ≤ min c ∈dev i (ρ(j),c ) cost i (ρ(j), c ) + val i,c .
For j = l, we have cost i (ρ ≥l ) = 0 so this is trivial. Assume the property holds down to j + 1 for some 1 ≤ j < l. By induction hypothesis, we have

cost i (ρ ≥j+1 ) ≤ b j+1 (i) = min b j (i) -w j (i), min c ∈dev i (ρ(j),c ) cost i (ρ(j), c ) + val i,c -w j (i) .
Therefore,

cost i (ρ ≥j ) = cost i (ρ ≥j+1 )+w j (i) ≤ min b j (i), min c ∈dev i (ρ(j),c ) cost i (ρ(j), c ) + val i,c ,
as required. By Lemma . , ρ is the outcome of a Nash equilibrium.

Thanks to Theorem . , we can compute the costs of the best and worst NE of A, n, g in exponential space. We can also decide the existence of an NE with constraints on the costs (both social and individual), by non-deterministically guessing an outcome and checking in M A,n,g , γ that it is indeed an NE. We obtain the following conclusion:

Corollary . . In dynamic NCG, the CONSTRAINED-NE problem is in EXPSPACE.

Proof. As noted earlier, the number of vertices in M A,n,g , γ is doubly exponential since |C| = |V | n is doubly exponential. Storing a con guration and computing its successors can be performed in exponential space. One can thus guess a path of size at most the size of the graph and check whether its cost is less than the given bound. This can be done using counters that can be stored (in binary) in exponential space. Hence, the overall algorithm lies in EXPSPACE.

. Conclusion

Note that one can e ectively compute a NE pro le satisfying the constraints in doubly-exponential time by nding the shortest path of M A,n,g , γ , and applying the construction of (the proof of) Lemma . .

C

To recap, in this chapter, we rst obtained the existence of Nash equilibria in dynamic network congestion games: rst only for blind strategy pro les, and then establishing the fact that blind NE are NE for dynamic NCG.

Subsequently, we observed that, there can be dynamic games with NE which are better than any blind NE in that dynamic games: better in terms of social cost. Therefore, we investigated how to tackle the following problem : Given a dynamic game and a constraint, does there exist an NE with social cost upper-bounded by the constraint? or are there NE with social cost at least as much as the given bound? We obtained upper-bound complexity results for the above problem, and hardness results of these problem are yet to be answered.

S P E

In the last chapter, we considered Nash Equilibria (NE) as a solution concept of congestion games. Intuitively, such an equilibrium gives a recipe to the players such that if each player follows the strategy, then they cannot do better by switching from it at any step. In other words, an NE is a stable strategy pro le, it is immune to any unilateral deviation at every step of its outcome. The last point is crucial, i.e, it is stable with respect to any unilateral deviation only when a player tries to deviate from a con guration which appears in a pre x of the outcome of the strategy pro le.

In this chapter, we will be discussing another solution concept that we often consider in the context of non-zero sum multi-player games: namely, Subgame perfect Equilibria (SPE). Intuitively this is also a strategy pro le in which no player would bene t by changing their strategy unilaterally at any step of the play like NE. On top of that, if the players decide to play according to an SPE, not necessarily from the con gurations that are in a pre x of the outcome of the pro le, but also from any arbitrary con guration. When the players decide to play such a strategy pro le, from that step on ward, no player would bene t by switching their strategy from the one prescribed by the pro le.

This might make SPE to be an interesting solution concept to study on its own, but we explain further in the following with an example why SPE is a necessary optimal solution concept in a dynamic setting.

N

Let us rst recall Example . where the arena and an NE are shown again at Figure . here.

s v 1 v 2 v 3 v 4 v 5 v 6 t x → 2 x e 1
x → 3 x e 5

x → 3 e 2

x → 3

e 3 x → 2 x e 4 x → x e 9 x → 3 e 1 0 x → x e 6
x → 2x In this example, in the NE pro le depicted in . b, Players 1 and 2 (who are depicted by red tokens) play a strategy in which they threat each other: to be speci c, they "punish" the other player by switching to the dotted edge immediately in the next step (from v 1 or v 2 ) if they see that the other player had chosen to take the bottom path (from s or v 1 respectively). By forcing them . On Existence of SPE in Dynamic NCG to take the above path together, these threats make both the players pay a higher cost than they would have paid if they did not threaten to "punish" each other in the pro le. These threats, which are costlier for the player who threatens, are called non-credible threats, and may appear in an NE pro le which is supposed to be somewhat cost-e ective for all players.

These threats appear in NE pro les, because intuitively, an NE pro le keeps a player's interest only in those histories that are pre xes of the outcome of the pro le itself, not in any other history. For example, if we consider an history in the above game, in which Player 1 is at v 1 already, and Players 2 and 3 are at vertex v 4 , then starting from that history, applying the NE pro le depicted in Figure . b is not a best-response for all players. The pro le prescribes Player 1 to take edge e 9 in the next step, but the cheaper response would be to continue on the path v 1

e 2 -→ v 2 e 3 -→ v 3 e 4 -→ t.
This example illustrates that when the players can take dynamic decisions, an SPE is a better tted solution concept for stability than an NE. This is why we consider studying SPE in this chapter. Now, let us recall the de nition from Chapter , which says, an NE pro le σ is an SPE if for any history h ending at any con guration c, the residual strategy σ| h is also NE from c.

In the next section, we brie y discuss the existence of SPE in dynamic NCG, which is an open question. Next, in Section . , we consider a decision problem like the ones that we considered in case of SO and NE in earlier chapters, and give a EXPSPACE algorithm for solving it.

O E SPE D NCG

Like Nash Equilibria, the rst natural question that arises for SPE is whether SPE always exist in dynamic NCG. Unfortunately, this is still an open question for our model. In the case of turn-based reachability games [ ], existence of an SPE is shown by reducing decision making at possibly in nitely many nodes of unraveling tree to decision making only at nite nodes. Moreover, an SPE is de ned by assigning plays from those nite nodes by applying Kuhn's Theorem[ ] on an extensive game structure. We can not apply a similar argument because our model is concurrent -hence we do not have an extensive game structure. On the other hand, the closest model of ours, dynamic resource allocation games studied by Avni et al [ ] shows an example where SPE do not exist. Their model somewhat generalizes dynamic network congestion games, and their example in which an SPE does not exist cannot be captured in a network game.

Nonetheless, we could always ask given a game and a bound whether there is an SPE with social cost bounded by the given threshold. If in future, it turns out there is a game where SPE does not exist, then for the above decision problem, for any threshold, the answer would always be No.

C SPE

In this section, we address the associated constrained SPE problem, similar to what we did in the case of Nash equilibria and Social optima:

Problem . (CONSTRAINED-SPE). Given a dynamic NCG G and a bound K ∈ N, decide if there exist an SPE profile with social cost less or equal to K.

To solve the above problem, we rst characterize the outcome of an SPE, and then obtain an algorithm for CONSTRAINED-SPE based on the characterization. But before that, let us rst see the main factors that di erentiate this characterization with that of NE. D SPE NE In order to characterize a play as the outcome of an NE in Lemma . , we needed to make sure that when a player deviates, there exists a strategy pro le of the other players by which the deviating player is made to pay more cost than they would have if they had not deviated.

Note that, after a deviation, the strategy pro le made of a coalition "punishing" strategies and a deviating strategy has no other requirement to ful ll than to increase the cost of the deviating player. Hence we could make use of the val i,c and the memoryless coalition strategy pro le which realizes val i,c as Player i (the deviating player)'s cost. Recall that val i,c is the cost that the opposing coalition can force Player i to pay if they deviate from con guration c. In contrast, when we characterize a play as the outcome of an SPE, additionally we need to make sure that the pro le made of the corresponding "punishing" coalition strategies and any deviating strategy is an SPE. This additional condition makes the characterization of SPE outcomes technically more challenging than that of its counterpart for NE.

The characterization we propose is inspired from the one in [ ] for SPE of a turn-based quantitative reachability game, where it is also guaranteed that SPE always exist [ ]. Before going into details of the characterization, we rst introduce some notions and establish their connection with SPE: W SPE Intuitively, an SPE is immune to any single player deviation, from any step of any history, which appears to be a strong requirement for a strategy pro le (and hence its outcome). In the following, we de ne a weak version of SPE, which is easier to characterize. Then we establish an equivalence between this weak SPE and SPE, and hence reduce the characterization of SPE outcomes to that of weak SPE outcomes.

A strategy σ i is said to be first-shot deviating from another strategy σ i if they coincide on all histories except the empty history. With this, we rst de ne a weak version of Nash equilibria, and then re ne later it to weak SPE, as follows: De nition . . A strategy profile σ = (σ i ) i∈ n is called a weak NE if for all i ∈ n , for every first-shot deviating strategy σ i , it holds that cost i ( σ -i , σ i ) ≥ cost i (σ).

Remark . . In [ ],

weak NE is a profile which is immune to one-shot deviating strategies and very-weak NE is a profile which is immune to rst-shot deviating strategies; here we do not use one-shot deviating strategies, hence in our terminology there are only weak NE (and weak SPE), which are very-weak NE (and very-weak SPE respectively)

in [ ].
In general a weak NE is not an NE.

Lemma . . There exists an NCG that admits a weak NE which is not an NE.

Proof. The simple idea is a strategy pro le might be immune to single player deviation at its rst step, but that does not imply it will be immune to single player deviation at any step.

. Constrained SPE problem x → 0 . Here two players decide at the beginning, and take the path colored in red, and another player takes the green path. The rst two players' cost is , and the other player's cost is . If one of the rst two players changes their strategy at the very rst step, they will end up paying cost . One the other hand, if the player who is currently taking the green path changes their strategy at the very step and decides to take the red path, they will pay cost . Therefore, here no player has a rst-shot deviating strategy by which they can lower their current cost, so that the pro le is a weak NE.

s v 1 v 2 v 3 v 4 v 5 v 6 t 4 e 1
On the contrary, one of the players, who are currently taking the red path, can switch their path from s

e 1 -→ v 1 e 2 -→ v 2 e 3 -→ v 3 e 4 -→ t to s e 1 -→ v 1 e 9 -→ v 5 e 7 -→ v 6 e 8
-→ t, and pay which is lower than their current cost. Therefore, the strategy pro le depicted here is not an NE.

De nition . . A strategy profile is a weak subgame-perfect equilibrium (wSPE) if it is a weak NE from every finite history of the game.

In Lemma . , we saw that a weak NE is not necessarily an NE. But, we will see that this is not true for SPE, i.e, a weak SPE is actually an SPE. Intuitively, this is because if indeed there is a single player deviation from some step (other than the rst) of a weak SPE outcome, then from that step's point of view the deviation is a rst-shot deviation. As weak SPE requires a pro le to be a weak NE from every step, a weak SPE would not have this single player deviation from any step, hence it will actually be an SPE. Formally,

Theorem . . In a dynamic NCG, a strategy profile is an SPE if, and only if, it is a weak SPE.

Proof. Recall from Chapter , given a strategy pro le σ and a history h, we write outcome(σ, h) for the outcome of the residual strategy σ h from the last con guration of h. Similarly, we let

cost k (σ, h) = cost k (outcome(σ, h)).
It is easy to see that NEs are weak NEs, and subsequently SPEs are weak SPEs. This is because if a strategy pro le is immune to single player deviation from any step of its outcome, it surely is immune to single player deviation from the rst step.

For the opposite direction, let us consider a weak SPE σ = (σ) i∈ n of a dynamic NCG G. Suppose that σ is not an SPE; then there exists a history h of G such that the residual strategy σ h is not an NE from the last con guration of h.

This implies there is i, and a strategy σ i of Player i with cost i (σ, h) > cost i ( σ -i , σ i , h). In particular, cost i ( σ -i , σ i , h) is nite, and along the outcome of this strategy pro le, Player i reaches tgt(i).

Subgame Perfect Equilibria

We pick σ i as a pro table deviating strategy (after history h) with minimum number of deviations from σ i . Because Player i reaches tgt(i) along outcome( σ -i , σ i , h), there exist pro table strategies with nitely many deviations.

We write h for the longest nite history along the path outcome( σ -i , σ i , h) where σ i deviates from σ i , i.e, σ i (hh ) = σ i (hh ) = c and outcome(σ, hh c) = outcome( σ -i , σ i , hh c).

Now if cost i (σ, hh ) ≤ cost i ( σ -i , σ i , hh ), then deviating at history hh is unnecessary for Player i for having pro table deviating strategy from h, and that contradicts the minimality of the number of deviations of σ i from σ i . Hence we get cost i (σ, hh ) > cost i ( σ -i , σ i , hh ). But that implies we have a rst-shot pro table deviating strategy for Player i, σ i , from history hh , which contradicts the assumption that σ is a weak SPE.

C O A SPE

In this section, we rst informally explain how we characterize the outcomes of an SPE, then we introduce formally the tools that we need for the characterization. Finally, in Theorem . , we state the characterization using those tools. Therefore, before diving into technical jargon, let us rst describe intuitively how we proceed:

• Broadly speaking, we associate a value through a function λ (and thus referring to them as λ-values) to each player and each edge of the con guration graph, such that the λ-values e ectively capture the criteria for starting an SPE outcome from that edge. To be more speci c, similar to val i,c of the NE outcome characterization, though technically more involved, these λ-values give an upper bound to the cost of each player in the outcome of any SPE that starts from that edge.

• Obviously, the next question is: how do we de ne these λ-values associated to a player and an edge of the con guration graph?

The one line answer is we start with some initial λ-values, iteratively update them until they reach a x-point. But, the main technical challenge lies in how we update these λ-values iteratively. We do not update λ-values of all edges together in the con guration graph, rather we only update in some part of the con guration graph.

When the λ-values reach their x-point there, then only we proceed to some next part of the graph where we use the values of a part which have been updated earlier. In the following, we explain what these parts are in the con guration graph, then we discuss how we update them inside an individual part, and thereafter we nally delve into more technical details.

One can imagine that the game is played in phases inside the con guration graph, where each phase corresponds to the number of players that have already reached their target vertices. A play transitions from one phase to the next when a player reaches their target vertex. Intuitively, a play is split into these phases because once a player reaches their target, the game stops there for that particular player, they do not contribute in congestion for any other players any further, hence they also do not a ect λ-values for the subsequent edges.

There can be multiple components in a single phase, each of which corresponds to a di erent set of players (but same number of players) who are at their target vertex. Note that, there is no edge between two such components of a single phase because from a con guration where, say only Player is at their target, there cannot be an edge to a con guration where

. Constrained SPE problem s t x → 3x e 2
x → x e 1 (a) An NCG G = A, 3, g , where g(s, t) = 3 (s, s, s) only Player is at their target, and so on. There will be at most n+1 such phases in the con guration graph, where the rst phase represents no player is at their target, and the last phase represents all players are at their target vertices. These phases are in fact, referred to as the parts of the con guration graph on which one update on λ-values happens at a time.

(s, s, t) (s, t, s) (t, s, s) (s, t, t) (t, t, s) (t, s, t) (t, t, t) X 0 X 1 X 2 X 3 7
We start with some initial λ-values for all edges of every phases in the con guration graph, then we start updating those values from the nal phase, and moving backwards until the rst phase. Moreover, in each phase of the graph, we update the λ-values iteratively till they reach a x-point inside that phase. These updates in a phase depend on the λ-values of the later phases. Note that, because there is no edge between di erent components of a single phase of the con guration graph, the λ-values of an edge in one component do not a ect λ-values of another edge in another component of that same phase.

T D

Let us consider a dynamic NCG A, n, g which we x for the following discussion. We denote the associated multi-weighted con guration graph by M = C, T , where recall from Section . , C ⊆ V n is the set of con gurations and T ⊆ C × N n × C is the set of transitions in the con guration graph.

We partition the set C of con gurations into (X j ) 0≤j≤n such that a con guration c is in X j if, and only if, j = #{i ∈ n | c(i) = tgt(i)}. Since tgt(i) is a sink state in A, if there is a transition from some con guration in X j to some con guration in X k , then k ≥ j. We de ne X ≥j = i≥j X i , and

Z j = {(c, w, c ) ∈ T | c ∈ X j } and Z ≥j = {(c, w, c ) ∈ T | c ∈ X ≥j }.
In Figure . , we depict such a partition of the con guration graph C of the NCG G considered.

For all 0 ≤ j ≤ n, we inductively de ne a sequence of families of labeling functions λ j * 0≤j≤n , where each λ j * = (λ j * i ) i∈ n is a family of labeling function, and for all i ∈ n , λ j * i : Z ≥j → N ∪ {-∞, +∞} is a labeling function associated to Player i, which maps an edge from Z ≥j to its so-called λ-value.

De nition . . For any family λ = λ i i∈ n with λ i : Z ≥j → N ∪ {-∞, +∞} and any c ∈ X ≥j , a path ρ = (t k ) k≥1 from c visiting c tgt is said to be λ-consistent if for any i ∈ n and for any 1 ≤ k ≤ |ρ|, it holds that cost i (ρ ≥k ) ≤ λ i (t k ). We write Γ λ (c) to denote the set of all λ-consistent paths from c.

We now de ne the sequence λ j * 0≤j≤n . For j = n, we have X ≥n = {c tgt } and Z ≥n = {(c tgt , 0 n , c tgt )}; there is a single path, which obviously is the outcome of an SPE since no deviations are possible. For all i ∈ n , we let λ n * i (c tgt , 0 n , c tgt ) = 0. Now, x j < n, assuming that λ (j+1) * has been de ned, we go on to de ne λ j * . In order to de ne λ j * , we introduced an intermediary sequence of families of labeling functions µ = µ k k≥0,i∈ n , where each family

µ k = (µ k i ) i∈ n comprises of µ k i : Z ≥j → N ∪ {-∞, +∞}, of which (λ j * i
) i∈ n will be the limit. We call these µ k 's as the λ j * -building functions. For each of these λ j * -building functions µ k , from any con guration c of Z ≥j , we have the set of µ k -consistent paths denoted by Γ µ k (c) De nition . . For any 0 ≤ j ≤ n, we define λ j * -building functions µ k : Z ≥j → N ∪ {-∞, +∞} as follows: they coincide with λ (j+1) * on Z ≥j+1 , i.e, for any e ∈ Z ≥j+1 , we let . Constrained SPE problem

µ k i (e) = λ (j+1) * i (e);
and for e ∈ Z j = Z ≥j \ Z ≥j+1 they are defined inductively (induction on k):

• for the base case:

µ 0 i (e) = 0 if c(i) = tgt(i), +∞ otherwise • for k > 0, assuming µ k-1 i has been defined, µ k i (e) =            0 if c(i) = tgt(i) min c ∈dev i (c,c ) sup ρ∈Γ µ k-1 (c ) (cost i (c, c )+cost i (ρ)) if for all (c, w, c) ∈ Z ≥j . Γ µ k-1 (c) = ∅ -∞ otherwise ( . )
where

dev i (c, c ) = {c ∈ C | c ⇒ c and ∀j ∈ n \ {i}. c (j) = c (j)
} is the set of configurations which can be obtained from Player i's unilateral deviation from the transition c to c , and c itself.

Lemma . . For any e ∈ Z ≥j , any i ∈ n , and any k > 0, we have

µ k i (e) ≤ µ k-1 i (e).
Proof. We prove the statement by induction on k, starting with k = 1. Write e = (c, w, c ). If c = tgt(i), then by de nition µ k i (e) = µ k-1 i (e) = 0; otherwise, µ 0 i (e) = ∞; in both cases, the result holds. Now, let us assume that for some k > 0, the following holds: for all i ∈ n and all e ∈ Z ≥j , it holds µ k i (e) ≤ µ k-1 i (e). Then for any c ∈ X ≥j , it implies Γ µ k (c, w, c ) ⊆ Γ µ k-1 (c, w, c ). Fix an arbitrary e = (c, w, c ) ∈ T . For any c ∈ dev i (c, c ), c also belongs to X ≥j , hence, by induction hypothesis, we have

Γ µ k (c ) ⊆ Γ µ k-1 (c ).
As supremum over a larger set would be at least as much as it is for a smaller set, we have:

sup ρ∈Γ µ k (c ) (cost i (c, c ) + cost i (ρ)) ≤ sup ρ∈Γ µ k-1 (c ) (cost i (c, c ) + cost i (ρ)).
As the above is true for any c ∈ dev i (c, c ), it remains true for the minimum, hence:

min c ∈dev i (c,c ) sup ρ∈Γ µ k (c ) (cost i (c, c ) + cost i (ρ)) ≤ min c ∈dev i (c,c ) sup ρ∈Γ µ k-1 (c ) (cost i (c, c ) + cost i (ρ))
which implies µ k+1 (e) ≤ µ k (e).

As the costs are non-negative integers, the µ k values are bounded by 0 if it is not -∞, so they cannot decrease arbitrarily. Therefore, µ k indeed reaches a x-point, which is by de nition λ j * . Following this for each j from n to 0, we nally have λ 0 * , and we write Γ * for Γ λ 0 * .

Subgame Perfect Equilibria

C

As promised, we now characterize the outcomes of any SPE using the λ-values as follows:

Theorem . . A path ρ in the configuration graph of G = A, n, g is the outcome of an SPE if, and only if, ρ ∈ Γ * (c src ).

Proof. Let us rst consider an SPE σ of G, of which ρ is the outcome. We shall show that for any c and any history h ending in con guration c, outcome(σ, h) ∈ Γ * (c). In fact, we prove by induction on j that outcome(σ, h) ∈ Γ λ j * (c) if c ∈ X j . Then, for h = c src , we get the expected result.

For j = n, for any history h ending in X n , outcome(σ, h) is a path looping on c tgt . We de ned λ n * (e) = 0 for e ∈ X n , so that the result holds.

Assume the statement is true for some j + 1 ≤ n: for any history h ending in some con guration c ∈ X j+1 , outcome(σ, h) ∈ Γ (j+1) * (c).

To prove the result at level j, we rely on the fact that λ j * is the limit of sequence µ k as de ned earlier, and we start another induction to show that for any k ≥ 0, for any history h whose last con guration c is in X j , the path outcome(σ, h) belongs to Γ µ k (c).

We begin with the case k = 0. Fix a history h ending in some c ∈ X j . Write outcome(σ, h) = (c r , w r , c r+1 ) r≥1 . Let r be the least integer such that c r in outcome(σ, h) belongs to X >j . We need to show that for any i ∈ n and any r, cost i ((outcome(σ, h)) ≥r ) ≤ µ 0 i (c r , w r , c r+1 ). If r < r , then either µ 0 (c r , w r , c r+1 ) = +∞, or µ 0 (c r , w r , c r+1 ) = 0 and c r (i) = tgt(i); in both cases, the result also holds. If r ≥ r , we have

µ 0 i (c r , w r , c r+1 ) = λ (j+1) * i
(c r , w r , c r+1 ), and by our outer induction hypothesis, cost i (outcome(σ, h) ≥r ) ≤ λ (j+1) * ((c r , w r , c r+1 )).

We now prove the induction step. We assume that outcome(σ, h) ∈ Γ µ k-1 (c) for any history h ending in c ∈ X j . Write outcome(σ, h) = (c r , w r , c r+1 ) r≥1 . We rst observe that µ k i (c r , w r , c r+1 ) = -∞ for any r ≥ 1. This is because for any (c r , w, c) ∈ T and for any c src h = ⇒ c, by our current induction hypothesis Γ µ k-1 (c) contains outcome(σ, h), hence it is not empty.

Therefore, the only thing left to show now is the following:

for all i ∈ n , For all r ≥ 1, cost i (outcome(σ, h) ≥r ) ≤ µ k i (c r , w r , c r+1 ) This is obvious if c r (i) = tgt(i).
As previously, we let r be the least integer such that the con guration c r along outcome(σ, h) belongs to X >j . For r < r : assume cost i (outcome(σ, h) ≥r ) > µ k i (c r , w r , c r+1 ); then by de nition of µ k i ,

cost i (outcome(σ, h) ≥r ) > min c ∈dev i (cr,c r+1 ) sup ρ∈Γ µ k-1 (c ) {cost i (c r , c ) + cost i (ρ)},
which implies the existence of an edge

(c r (i), f, v ) in E such that cost i (outcome(σ, h) ≥r ) > cost i (c r , c r+1 [i → v ]) + cost i (σ, h • (c r , w , c r+1 [i → v ])).
.

Constrained SPE problem

Because of our induction hypothesis for k-1, we have,

outcome(σ, h • (c r , w , c r+1 [i → v ])) ∈ Γ µ k-1 (c r , w , c r+1 [i → v ])
This shows a pro table rst-shot deviation for Player i, contradicting our hypothesis that σ is an SPE.

Otherwise for r ≥ r , the condition follows directly from the outer induction hypothesis, because µ k coincides with λ j * for edges in those regions.

We now prove the converse implication. Picking ρ ∈ Γ * (c src ), we build a weak SPE σ = (σ i ) i∈ n (which is an SPE by Theorem . ), step-by-step; for notational convenience, instead of de ning σ i (h) for any history h, we directly de ne what outcome(σ, h) would be.

As a rst step, we let outcome(σ, c src ) = ρ. Now let us construct the rest of σ. Consider an arbitrary history h = h • (c, w, c ), and suppose outcome(σ, h) is already de ned to be (c j , w j , c j+1 ) j≥1 . Note that, here c 1 = c because c is the last con guration of h by consideration. Now, if c 2 = c , then we do not need to de ne outcome(σ, h ), as it is already de ned from h itself, and we have outcome(σ, h ) = (c j , w j , c j+1 ) j≥2 . Otherwise c = c 2 , and we de ne outcome(σ, h ) in that case below.

If c is a con guration which is obtained by two or more players' deviation from outcome(σ, h) , i.e, if there exists k = l ∈ n such that c (k) = c 2 (l), then pick any ρ ∈ Γ * (c ) (which we know is not empty) and de ne outcome(σ, h • (c, w, c )) = ρ.

Otherwise c 2 di ers from c only at a single player's position, say Player i's. In that case we de ne

outcome(σ, h • (c, w, c )) = arg max ρ∈Γ * (c ) {cost i (c 1 , c ) + cost i (ρ)}.
( . )

Note that, here we can take arg max because λ * i (e) is nite (which we shall establish in Corollary . ) for any e ∈ E, so there are nitely many plays in Γ * (c). This ends our de nition of the strategy pro le σ, which we now prove is a weak SPE.

Consider an arbitrary history h and denote outcome(σ, h) by (c j , w j , c j+1 ) 1≤j . Pick a conguration c such that (c 1 , w , c ) ∈ T , c (j) = c 2 (j) for all j = i, but c (i) = c 2 (i). That is, c is a con guration obtained by Player i's deviation from σ i at the end of h.

We show that such a single player deviation is not pro table if, after that deviation, all players continue to play following σ:

cost i (c 1 , c ) + cost i (σ, h • (c 1 , w , c )) = sup ρ∈Γ * (c ) {cost i (ρ) + cost i (c 1 , c )} (by ( . )) ≥ min c∈dev i (c 1 ,c 2 ) sup ρ∈Γ * (c) {cost i (ρ) + cost i (c, c)} = λ * i ((c 1 , w 1 , c 2 )) ≥ cost i (σ, h)

Subgame Perfect Equilibria

So no such con guration c would be pro table for Player i. Hence from any history h, σ is a weak NE. Therefore, we can conclude that σ is an SPE.

S

Having the characterization of outcomes of SPE by the notion of λ-consistency, we now are going to establish the upper bounds of the λ-values for an NCG G. Remember, by de nition a λ-value could be +∞, but the nite values that any λ-function maps into is, in fact, bounded. Here, we show the upper bound on those nite values of λ.

A λ-map is nothing but a x-point of so-called λ-building functions, denoted here by µ k 's. In Lemma . , we establish the nite upper bound of µ k 's after |V | iterations (V is the set of vertices of the NCG under consideration). Corollary . tells us when a µ k function reaches their

x-point in a phase Z ≥j . Finally, combining these two together, we get Corollary . which gives us an upper bound for λ-values.

ρ ∈ Γ µ m-1 (c ), we have cost i (ρ) = 0. Therefore, µ m i (e) = cost i (c, c
), which is bounded by κ. Now assume that the induction hypothesis holds up to step m-1, and consider a con guration c such that the length of a shortest path from c(i) to tgt(i) in A is m. Fix an edge (c, w, c ) ∈ T . Write (c(i), f, v ) ∈ E for the rst edge of a shortest path from c(i) to tgt. We consider a con guration c such that c (j) = c (j) for all j = i, and c (i) = v . By construction, there is a path from c (i) to tgt(i) of length ≤ m -1. By induction hypothesis, for any edge (c , w, c) ∈ T , we have µ m-1 i ((c , w, c)) ≤ (m -1) × κ. This implies that for any path

ρ = (t j ) j≥1 ∈ Γ µ m-1 (c ), we have cost i (ρ) ≤ µ m-1 i (t 1 ) ≤ (m -1) × κ. Therefore, µ m i (c, w, c ) ≤ cost i (c, c ) + (m -1) × κ ≤ m × κ.
Lemmas . and . provide a bound on the number of steps until any sequence of λ j * -building functions stabilize:

Corollary . . Any sequence (µ k ) k≥0 of λ j * -building functions stabilizes after at most |V |(1 + n • κ • |E| n ) steps.
From Lemma . , we also get that the sequence (µ k ) k≥0 built for computing λ j * cannot stabilize unless for all i ∈ n , for all e ∈ Z ≥j , we have µ k i (e) ≤ |V | × κ. By Lemma . :

Corollary . . For any 0 ≤ i, j ≤ n, and any e ∈ Z ≥j , we have λ j * i (e) ≤ |V | × κ.

. Constrained SPE problem U C

CONSTRAINED-SPE

With the characterization of the outcomes of all SPE (Theorem . ), what remains to solve in CONSTRAINED-SPE is to check whether there is a path in Γ * (c src ) with cost less than the given threshold. Now, when we non-deterministically guess a play and verify whether the play is the outcome of an SPE, at each step we check whether the play is ful lling the condition for being λ * -consistent up to the current step. Moreover, at each step, while we guess a new con guration from the current one, we also make sure that there is a λ-consistent play for a suitable λ from all the con gurations that are reachable (but not currently guessed) in one step. In order to perform these λ-consistency checks at each step, we make use of an in nite graph structure, namely the counter graph.

A counter graph is de ned according to a family of labeling functions λ = λ i i∈ n and a con guration c such that any path from c to c tgt in the counter graph is actually λ-consistent. In this section, after formally de ning what a counter graph is, we establish this relation between a path in the graph and a λ-consistent play in Lemma . . In Lemma . , we establish the equivalence between the fact that supremum of Player i's cost over µ k -consistent plays is +∞ with the existence of a cycle in the corresponding counter graph.

Moreover, in Lemma . , we show an upper bound for the nite value that the intermediary µ k -functions can take. Recall, we establish an upper bound of the nite value that a λ-function can take in Corollary . , and also an upper bound for the nite values that a µ k can map to, when k ≥ |V |. Because the µ k 's are non-increasing (Lemma . ), the intermediary µ k -values could be higher than that of when k ≥ |V |. Therefore, establishing this upper bound gives us the necessary computations for the space we need for the CONSTRAINED-SPE algorithm, which we describe in the nal part of this section.

(i) = 0 if d(i) = tgt(i), or b i = min{b i -w i , µ i (d, w, d ) -w i } otherwise (provided that b i ≥ 0 for all i, in order for (d , b ) to be an edge of C[µ, c]).
Intuitively, in con guration (d, b) of the counter graph, b is used to enforce µ-consistency: each edge taken along a path imposes a constraint on the cost of the players for the rest of the path; this constraint is added to the constraints of the earlier edges, and propagated along the path.

With the initial con guration c, we associate b c such that b c i = 0 if c(i) = tgt(i) and b c i = +∞ otherwise: this con guration imposes no constraints since no edges have been taken yet. We call (c, b c ) to be the initial configuration of the counter graph C[µ, c].

Notice that C[µ, c] is in nite, but as we show below, only nitely many states are reachable from the initial con guration. We write |C | reach for the number of reachable states in C .

We extend the region decomposition of M = C, T to any counter graph C[µ, c] = C , T in the natural way: (c , b ) ∈ X j if c ∈ X j , and an edge

((c , b ), w , (c , b )) ∈ Z ≥j if (c , w , c ) ∈ Z ≥j . Subgame Perfect Equilibria We call a path π from (c, b c ) to (c tgt , b) (for some b) a valid path in C[µ, c]. For any path π ∈ C[µ, c], where c ∈ X j , we write π = π[j] • π[j + 1] • • • π[n]
where π[l] denotes the (possibly empty) section of path in Z l . We also use the notation maxb l (µ, c) to denote the maximum nite counter value that appears in the vertices reachable from (c, b c ) and belonging to X j . More precisely,

maxb l (µ, c) = max{m ∈ N | ∃(c , b ) ∈ X l s.t. (c, b c ) → * (c , b ) and ∃i ∈ n , b (i) = m}
We extend this notation to maxb ≥l (µ, c), which denotes max j≥l maxb j (µ, c). When all the counter values are in {0, ∞}, we let maxb l (µ, c) = 0.

Lemma . . There exists a path

π = ((c j , b j ), w j (c j+1 , b j+1 )) j from (c, b c ) to a vertex (c tgt , b) (for some b) in the counter graph C[λ, c] = C , T of G if, and only if, there is a λ-consistent path ρ = (c j , w j , c j+1 ) j from c to c tgt in G.
Proof. Assume that such a path π exists. Along π, for each player i, let k(i) be the least index such that c k(i) (i) = tgt(i). Then it is enough to show that for 1 ≤ k < k(i), we have cost i (ρ ≥k ) ≤ λ i (c k , w k , c k+1 ). And indeed we have

0 ≤ b k(i) (i) ≤ b k(i)-1 (i) -cost i (c k(i)-1 , c k(i) ) ≤ b k(i)-2 (i) -cost i (c k(i)-2 , c k(i)-1 ) -cost i (c k(i)-1 , c k(i) ) . . . ≤ b k+1 (i) - k(i)-1 j=k+1 cost i (c j , c j+1 ) so that cost i (ρ ≥k ) ≤ b k+1 (i) ≤ λ i (c k , w k , c k+1 ).
Conversely, if there is a λ-consistent path ρ = (c j , w j , c j+1 ) 1≤j<|ρ| from c, we de ne π = ((c j , b j ), w j , (c j+1 , b j+1 )) 1≤j<|ρ| with:

b 1 (i) = 0 if c 1 (i) = tgt(i) +∞ otherwise And for 1 ≤ j ≤ |ρ|, b j (i) = min{b j-1 (i) -cost i (c j-1 , c j ), λ i (c j-1 , w j-1 , c j ) -cost i (c j-1 , c j )}
For π to be a valid path in C[λ, c], we have to prove that b j (i) ≥ 0 for all 1 < j ≤ |ρ| and all i ∈ n . For j = 1, it is evident. For j > 1, the second element of the minimum de ning b j (i) is non-negative, because

cost i (c j-1 , c j ) ≤ cost i (ρ ≥j-1 ) ≤ λ i (c j-1 , w j-1 , c j ). Suppose the rst element b j-1 (i) - cost i (c j-1 , c j ) is negative. Using de nition of b j-1 (i), we can say the above inequality can be true only if either b j-2 (i) -j-1 k=j-2 cost i (c k , c k+1 ) < 0, or λ i (c j-2 , w j-2 , c j-1 ) - j-1 k=j-2 cost i (c k , c k+1 ) < 0.
But again the latter cannot be true because it directly contradicts λconsistency of ρ. Hence, our supposition can only be true if the former constraint holds. We repeat the process with b j-2 (i), coming down to the condition b 2 (i)

-j-1 k=2 cost i (c k , w k , c k+1 ) < 0 to make our supposition b j-1 (i) -cost i (c j-1 , c j ) < 0 true. But b 2 (i) = λ i (c 1 , w 1 , c 2 ) - cost i (c 1 , c 2 ), so that the inequality above entails λ i (c 1 , w 1 , c 2 ) < j-1 k=1 cost i (c k , c k+1
). This contradicts the λ-consistency condition at the beginning of ρ. It follows that b j (i) ≥ 0 for all 1 ≤ j ≤ |ρ| and all i ∈ n .

Lemma . . sup ρ∈Γ µ k (c) cost i (ρ) = +∞ if, and only if, there exists a valid path π in C[µ k , c] with the following conditions:

• π is of the form h • β • h , where β is a cycle in C[µ k , c]; • Player i's (constant) counter value b(i) is positive throughout β.
Proof. sup ρ∈Γ µ k (c) cost i (ρ) = +∞ implies there exists a sequence of paths (ρ m ) m≥1 in Γ µ k (c) such that cost i (ρ m ) → ∞ as m grows. By Lemma . , for each of those ρ m , there exists corresponding

π m from (c, b c ) to (c tgt , b) in C[µ k , c].
As a player's cost in a single edge is bounded, the length of π m has to grow unboundedly. First of all, that is only possible if there is a cycle β in C[µ k , c] -we have the rst condition now. Now Player i's counter value cannot be 0 in β because then the cycle doesn't contribute to make cost i (ρ) → +∞. Thus the second condition also holds.

Conversely, for π

= h • β • h in C[µ k , c],
where β is a cycle and Player i's cost > 0 in β, we construct a sequence of paths π m = h • β m+1 • h for m ≥ 0. By Lemma . , corresponding to this sequence of paths, there exists a sequence of paths (ρ m ) m≥0 in Γ µ k-1 (c ), and for those paths, cost i (ρ m ) → ∞ as m grows. Hence, µ k i (c, w, c ) = +∞ if these condition holds.

At this point, we have bounded the nite values that the λ j * 's can take. But in the transitioning from λ (j+1) * to λ j * , µ k i can take larger values when k < |V |. In the sequel, we bound the values that any family µ k = µ k i i∈ n can return. To this aim, we begin with working on the supremum of the cost for Player i of the paths in Γ µ k (c).

When we consider a maxb l (µ k , c) with c ∈ X j of M, it is implicit that l ≥ j. For l > j, we have

maxb l (µ k , c) ≤ maxb l (µ 0 , c) ≤ max e∈Z l i∈ n λ l * i (e) ≤ |V | × κ because µ k i (e) = µ 0 i (e) = λ l * i (e)
for those e ∈ Z ≥l and for all i ∈ n . So it remains to bound maxb j (µ k , c); but for that too, when k ≥ |V |, we have maxb j (µ k , c) ≤ |V | × κ. Therefore, we only need to provide a bound for maxb j (µ k , c) when k < |V |.

Lemma . . For an edge e = (c, w, c ) ∈ Z j and a λ j * -building function

µ k = µ k i i∈ n , if µ k i (e) is non-zero finite then µ k i (e) ≤ (n|C| + 2|V |) × k l=1 (n|C|) l-1 • κ l .
Subgame Perfect Equilibria Moreover, the above bound also applies to maxb j (µ k , c ) for any c ∈ X j :

maxb j (µ k , c) ≤ (n|C| + 2|V |) × k l=1 (n|C|) l-1 • κ l .
Proof. We can claim that the nite maximum counter value appearing in X j of any counter graph C[µ k , c ] (where c ∈ X j ) is bounded by the nite maximum µ k i (e) value appearing in the same region (maximum over i and e ∈ Z j ), i.e,

maxb j (µ k , c ) ≤ max{µ k i (c, w, c) ∈ N | ((c, b), w, (c , b )) ∈ Z j of C[µ k , c ], i ∈ n }.
This is justi ed because for the initial vertex (c, b c ) of X j , b c ∈ {0, ∞}. Hence, a counter value becomes nite and non-zero, when some µ k i (e) for e ∈ Z j becomes nite and non-zero. But by de nition of counter graph, ((c, b), w, (c , b )) ∈ Z j implies (c, w, c ) ∈ Z j , hence we can obtain,

maxb j (µ k , c ) ≤ max{µ k i (c, w, c ) ∈ N | (c, w, c ) ∈ Z j , i ∈ n }.
By induction on k, we prove that for any c ∈ X j and any i ∈ n ,

maxb j (µ k , c ) ≤ max{µ k i (e) ∈ N | e ∈ Z j } ≤ (n|C| + 2|V |) × k l=1 (n|C|) l-1 • κ l .
As µ 0 i (e) ∈ {0, ∞} for all ∈Z j , the given bounds hold for k = 0. We x an arbitrary e = (c, w, c ) ∈ Z j and a player i ∈ n such that µ k i (e) ∈ N \ {0}. That µ k i (e) is a non-zero nite value means that sup ρ∈Γ µ k-1 (c) cost i (ρ) ∈ N for some c ∈ dev i (c, c ).

If c(i) = tgt(i) then sup ρ∈Γ µ k-1 (c) cost i (ρ) = 0, and that makes µ k i (e) ≤ cost i (c, c) ≤ κ, satisfying the given bound.

Otherwise, c(i) = tgt, and depending whether c belongs to X j or X >j , we analyze two cases:

• c ∈ X l for some l > j: Then

µ k i (e) ≤ sup ρ∈Γ µ k-1 (c) {cost i (c, c) + cost i (ρ)} ≤ cost i (c, c) + max e ∈Z l i∈ n µ k-1 i (e ) ≤ (1 + |V |) × κ. • c ∈ X j : Now consider C[µ k-1 , c],
and its initial vertex (c, b c). By Lemma . , for any

path ρ ∈ Γ µ k-1 (c), we have a corresponding valid path π ρ in C[µ k-1 , c].
We also consider the region decomposition

π ρ = π ρ [j] . . . π ρ [n]. From the fact that sup ρ∈Γ µ k-1 (c) < +∞,
we argue that in π ρ , from (c, b c) within each |C| step either one counter value strictly decreases, or Player i reaches tgt(i). Otherwise, there would have been a cycle in C[µ k-1 , c] resulting in the supremum being +∞ ( thanks to lemma . ). Recall by design, the counter values of π ρ in X j lie in maxb j (µ k-1 , c) ∪{0, +∞}, and when a counter value decreases along an edge, it decreases at least by 1. Therefore, within n × |C| × (maxb j (µ k-1 , c) + 1) steps from (c, b c) at least one of the counter value becomes 0. When a player-l counter value becomes 0, π ρ must reach the next region (making the corresponding c(l) = tgt(i)), otherwise π ρ is not a valid path. Moreover, from the next region, cost i (ρ

[j + 1] . . . ρ[n]) is bounded by µ k-1 i (e )
, where e denotes the rst edge of ρ which belongs to Z >j . Therefore,

cost i (ρ) ≤ (n × |C| × (maxb j (µ k-1 , c) + 1)) × κ + max l>j maxb l (µ k-1 , c) ≤ (n × |C| + |V |) × κ + (n × |C|) × maxb j (µ k-1 , c) × κ.
If Player i reaches tgt within X j , cost i (ρ) would be much smaller. In the above, we have used the bound from Corollary . as µ k-1 (e) = λ l * (e) for e ∈ X l for l > j. Now as c ∈ X j , we can use the induction hypothesis for giving a bound to maxb j (µ k-1 , c). As the above shown bound works for any ρ ∈ Γ µ k-1 (c), it works for the supremum too, hence we have

µ k i (c, w, c ) ≤ sup ρ∈Γ µ k-1 (c) cost i (c , c) + cost i (ρ) ≤ |V | × κ + (n × |C| + |V |) × κ + (n × |C|) × maxb j (µ k-1 , c) × κ ≤ (n|C| + 2|V |) × κ + (n|C| × κ) × (n|C| + 2|V |) × k-1 l=1 (n|C|) l-1 • κ l = (n|C| + 2|V |) × k l=1 (n|C|) l-1 • κ l
This provides a bound for any maxb l (µ, c) for any λ j * -building function µ, c ∈ X j , and l ≥ j. Hence, we can conclude that the counter graph C[µ, c] = C , T can be made nite, by taking

C = {(d, b) ∈ C × ([0; Y ] ∪ {+∞}) n | c ⇒ * d}, with Y = n |V | • |V | n.|V | • κ |V | ,
which is doubly-exponential in the encoding of n. Note that, this makes |C | reach at most doubleexponential too -which will be one of the key arguments in the complexity analysis of the nal algorithm.

A

With all these ingredients, we now describe a non-deterministic algorithm for the decision problem CONSTRAINED-SPE. To be speci c, if indeed there is an SPE with social cost less than the threshold K, then our algorithm can verify that. In this veri cation algorithm, a certi cate is a play (or alternatively a path in the con guration graph) which is potentially the outcome of an SPE with social cost less than K. At the end, we conclude the complexity of the above algorithm in Theorem . .

To start with, we compute λ * -values for each edge in the con guration graph. In order to do that, we start with λ n * , and inductively compute λ j * = λ j * i i∈ n from λ (j+1) * until j = 0. When computing λ j * from λ (j+1) * , we use the intermediary family of labeling functions µ k . That is, for each j ∈ n , starting from µ 0 = µ 0 i i∈ n , we compute µ k+1 from µ k until it becomes µ k = µ k+1 , i.e, reaches a x-point. Then we declare λ j * = µ k .

Recall that, for any j, for any intermediary family of functions µ k = µ k i i∈n , (where µ k i : Z ≥j → N ∪ {+∞, -∞}) we only need to compute µ k i (e) for e ∈ Z j because for e ∈ Z ≥j+1 ,

µ k i (e ) = λ (j+1) * i (e ).
In the following, we explain how we compute µ k i (c, w, c ) for (c, w, c ) ∈ Z j , assuming {µ k-1 i (e) | e ∈ Z ≥j } are stored:

• First we verify that whether µ k i (c, w, c ) is not -∞. By ( . ), we know that µ k would be -∞ only if there exists an edge (c, w , c ) ∈ Z j from c in the con guration graph such that Γ µ k-1 (c ) is empty. Therefore, to verify this, we check for each edge (c, w , c ) ∈ Z j , whether Γ µ k-1 (c ) is not empty. In order to do that,we guess a valid path (but do not store) in

C[µ k-1 , c ]. If there is such a path in C[µ k-1 , c ],
there will be one of length bounded by |C|, which is doubly-exponential in the size of the input. Hence we keep a counter which we increase by 1 every time we correctly guess a new edge along the path, and the counter stops either when we reach a (c tgt , b), or at the latest when it reaches |C|. As the length of such a path is bounded by |C|, which is doubly exponential in the input size, we can encode the necessary counter using only exponential space. Therefore, if indeed µ k i (c, w, c ) is not -∞, we can verify that using exponential space.

• Once we veri ed the above, and concluded that µ k i (c, w, c ) is not -∞, we know that it must be in N ∪ {+∞}. Now, we rst check whether µ k i (c, w, c ) is +∞. For that, we need to verify the conditions stated in Lemma . , i.e, for each c ∈ dev i (c, c ), we need a valid path π of the form

h • β • h in C[µ k-1 , c ],
where β is a cycle and Player i's counter value is > 0 throughout β.

We guess such a path π in C[µ k-1 , c ] for each edge (c, w , c ) ∈ dev i (c, c ). Of this path. we rst guess the very rst vertex of the cycle β, say (c 1 , b 1 ) (with b 1 (i) > 0). Then we guess the cycle itself, keeping only the currently guessed edge in memory at each step. Note that, if there is a cycle on (c 1 , b 1 ), there has to be one within length |C| because within a cycle only the con gurations change, not the counter-values. Then we guess a path from (c , b c ) to (c 1 , b 1 ), and another path from (c 1 , b 1 ) to (c tgt , b) (for some b).

The length of the part up to (c 1 , b 1 ) is bounded by |C | reach , whilst we can always get a path of length at most |C| (if it exists) from (c 1 , b 1 ) to (c tgt , b). This discrepancy between the two bounds is mainly because for the latter part of the path, we do not exactly x the nal vertex (b can be any tuple of n non-negative values), we just want the rst component to be c tgt , while for the former part it gets xed to (c 1 , b 1 ).

If we can guess such a path π for each of c ∈ dev i (c, c ), we return µ k i (c, w, c ) = +∞.

• Otherwise, we have at least 1 and at most |V | con gurations c ∈ dev i (c, c ) such that sup ρ∈Γ µ k-1 (c ) cost i (ρ) ∈ N. We call this set of con gurations as dev i (c, c )| finsup .

.

Conclusion

To compute the nite value of µ k i (c, w, c ), we compute M j = sup ρ∈Γ µ k-1 (c j ) cost i (ρ) for each of c j ∈ dev i (c, c )| finsup , and then take the minimum. In order to compute M j , we rst tentatively set M j = min e∈E f e (1), and proceed iteratively as follows: we guess a valid path π of length at most |C | reach of C[µ k-1 , c j ] such that cost i (ρ) ≥ M j , where ρ is the corresponding path of π in G. If such a path exists, we increase M j by 1, and repeat. At some point, we get M j such that there doesn't exist a valid path π of length at most |C | reach with Player i's cost larger than or equal to M j + 1, but there exists a valid path with Player i's cost larger than or equal to M j . We store that M j . When all values M j have been computed, we return:

M = min j∈ |dev i (c,c )| finsup | {cost i (c, c j ) + M j }.
We use at most doubly-exponential space in the procedure of guessing a path, and we reuse that space for guessing the next path in the above algorithm.

We keep a binary counter throughout transitioning from µ k-1 to µ k to ag whether the xpoint has been reached. Once we reach λ * = λ * i , we nally check whether

Γ λ * (c src ) is empty by guessing a path in C[λ * , c src ] from (c src , b csrc ) to (c tgt , b).
In conclusion, we use doubly-exponential space: ( ) to store {µ k-1 i (e) | i ∈ n , e ∈ T } which is double-exponential in the encoding of the number of players, and ( ) to encode a counter which keeps checking whether the length of our guessed paths does not exceed |C | reach .

Theorem . . The existence of SPEs in a dynamic NCG can be decided in EXPSPACE.

C

In this chapter, we have studied SPE in dynamic network congestion games. Even though, we do not have certain result whether SPE always exist in dynamic NCG or not, we have shown that how constrained SPE can be of interest. Henceforth, we studied constrained SPE problem: rst we characterized the outcome of SPE, then based on the characterization, we developed an algorithm which decides in EXPSPACE whether given a dynamic game and constraint, there exists an SPE in the game with social cost less or equal to that constraint value.

The natural two problems that remain open are : ( ) existence of SPE, ( ) nding lower bound complexity results for constrained SPE problem.

P II N C F

In this part of the thesis, we continue our study on network congestion games, but from a di erent perspective. Here, instead of xing a number of players, we consider the number of players as a parameter in the model. Our objective here is to study how the optimal strategy pro les behave with this parameter.

But the scope of this part is restricted compared to Part I. That is why, in this chapter, we rst specify what the particular restrictions are, and what new notions we introduce for adjusting with the new restricted setting for tackling network congestion game with the number of players as a parameter.

R

First of all, we remove the two speci cities that we earlier considered in Part I, namely: synchronous cost computation and dynamic strategies. This is solely for technical reason, and we believe studying this problem on other model of congestion games (including the one that we considered in Part I) could be a future work of interest. Here:

• costs are computed non-synchronously, as it is done in classical network congestion games [ , , ]. That means two players bears congestion e ect in their cost for an edge even if they do not take that edge in their route at the same step.

• Strategies are just paths from source to target, unlike the dynamic strategies that we considered in Part I.

Therefore, both syntactically and semantically, we go back to network congestion games from the literature. Moreover, we restrict the cost functions associated with the edges to linear functions only, contrary to a ne functions that we considered in Part I. Finally, we restrict the network arena to only series-parallel graphs instead of any directed graphs that have been considered in Part I. With this, let us introduce our setting formally, where some of the de nitions might just be inherited from Chapter , but recalled again anyway.

D S P

Let H be a family of non-decreasing linear functions from N to N. Formally, a function h

: N → N of H is of the form h(x) = w • x, with w ≥ 0.
We rst rede ne our notion of a network in this part, which is a directed acyclic graph with a single source-target vertex pair, contrary to multiple source-target vertex pairs considered in Part I. Formally, . Definitions

De nition . (Network).

A network is a tuple N = V, E, s, t , where V, E forms a directed acyclic graph, s and t are the source and target vertices respectively, and for every v ∈ V , there is a path from s to v, and a path from v to t. Moreover, there is no incoming edge to s, and no outgoing edge from t.

As mentioned before, here we restrict our study on series-parallel networks. In order to dene series-parallel network, we rst de ne two ways of composing any two networks: two networks

N 1 = V 1 , E 1 , s 1 , t 1 and N 2 = V 2 , E 2 ,
s 2 , t 2 , and they can be composed to form a single network by:

• Series composition: Intuitively, two networks are composed to a single one by merging the target vertex t 1 of the former and the source vertex s 2 of the latter to a new vertex. As the new vertex is no longer a target vertex, the self-loop from t 1 is also removed. We refer to this network as

N 1 ⊕ N 2 Formally, N 1 ⊕ N 2 = V, E, s, t , where V = V 1 ∪ V 2 ∪ {u} \ {t 1 , s 2 } E = E 1 ∪ E 2 ∪ {(v, u) : (v, t 1 ) ∈ E 1 } ∪ {(u, v) : (s 2 , v) ∈ E 2 }
and s = s 1 , and t = t 2 .

• Parallel composition: Intuitively, two networks are composed parallelly by merging the two source vertices into a new source, and two target vertices into a new target vertex. We refer the new network as N 1 N 2 . Formally, N 1 N 2 = V, E, s, t , where

V = V 1 ∪ V 2 ∪ {s, t} \ {s 1 , t 2 , s 2 , t 2 } E = E 1 ∪ E 2 ∪ {(s, v) : (s 1 , v) ∈ E 1 } ∪ {(s, v) : (s 2 , v) ∈ E 2 } ∪ {(v, t) : (v, t 1 ) ∈ E 1 } ∪ {(v, t) : (v, t 2 ) ∈ E 2 }
De nition . (Series-Parallel Network). A network N = V, E, s, t is called a series-parallel network if either it is a single edge (s, t), or series or parallel composition of two series-parallel networks.

Example . . Consider Figure . . Here . a is a single edge between source and target, the basic unit for any series-parallel network. Any series-parallel network is built starting from single edge(s), and composing them either in series or in parallel. For example, the network

N 1 ⊕ N 2 of Figure . d is built by composing N 1 of . b and N 2 of . c, while N 1 N 2 is built by composing them in parallel. P N C G
We de ne parameterized network congestion game (pNCG) on this series-parallel network, which is a network congestion game without xed number of players. Formally,

De nition . (Parameterized Network Congestion Game).

A parameterized network congestion game (pNCG) is a tuple G = V, T, s, t , where V is the set of vertices, T ⊆ V × H × V is the set of transitions labeled by non-decreasing linear functions, and the underlying graph N = V, E, s, t , where

E = {(v, v ) : for each (v, h, v ) ∈ T }, is a series-parallel network.
Framework for parameterized games on series-parallel graphs s t e Note that, syntactically a pNCG is no di erent from the underlying arena N on which the game is de ned. This is in contrast with the network congestion game (De nition . ) de ned in Chapter , where apart from the arena the number of players n, and a source-target assigning map g were part of an instance.

S

Intuitively, a pNCG captures in nitely many NCG , one for every integer n ∈ N. Hence, with a pNCG G, we associate in nitely many network congestion games, denoted by G n for each n ∈ N \ {0}. Here G n denotes the congestion game G, n, g , where g(s, t) = n. Because, a pNCG only associates with symmetric NCG, we omit g from the notation, and simply write G n = G, n . This also means pNCG inherits the semantics, i.e, objective of a player, and how a game proceeds in rounds, from NCG itself, as it is explained in the semantics part on Page .

S

Because a pNCG captures a class of NCG, σ is a Player i strategy in a pNCG G means σ is a Player i strategy in an NCG from the class that G represents. Moreover, as mentioned earlier, in this part, we restrict the strategy space only to what we called earlier blind strategies. Recall from Chapter , a blind strategy π is a path from s to t in the arena. A path π from s to t in G is denoted as a sequence of the form s

e 1 -→ v 1 . . . e |π| --→ t.
For such a path π, we write e j ∈ π for 1 ≤ j ≤ |π|. We denote PathsG to be the set of all paths in G. As all the players in any associated NCG G n have same source-target vertex pair, a strategy can be directly associated to the pNCG G itself.

A strategy profile σ of G n for any n ∈ N\{0} is a n-tuple (π i ) i∈ n where each π i is a strategy of G. We call σ to be a strategy pro le of G itself, if it is a strategy pro le of G n for some n ∈ N \ {0}.

In the next chapter of this part, our main objective is to investigate how optimal strategy pro le for stability behaves as the parameter evolves. Hence, instead of denoting a strategy pro le of G n as a n-tuple of paths in G, we use two notations that are more resilient to the change in n, and therefore easier to observe if and how strategy pro les relate to each other when n varies:

• Path representation of a strategy pro le: Here a strategy pro le is a |PathsG|-tuple m = (m π ) π∈PathsG , in which m π denotes the number of players taking path π in the strategy pro le. Necessarily, for a strategy pro le m of G n , π∈PathsG m π = n.

• Edge representation of a strategy pro le: Here a strategy pro le is a |E|-tuple n = (n e ) e∈E , in which n e denotes the number of players taking e in their strategy in this pro le. Here necessarily for every vertex v ∈ V \ {s, t} the number players incoming to v in a strategy pro le has to match up to the number of players outgoing from v. Formally,

e∈In(v) n e = e∈Out(v)
n e , where In(v) and Out(v) are the set of incoming and outgoing edges of v.

In both representations, we do not keep the information about which player is playing which strategy as all of them has same source-target vertex pair, but this makes multiple strategy pro les to have same path/edge representation. Two strategy pro les that have the same path representation are isomorphic to each other up to permutation of the players. As a player's identity does not matter for our current context, we can consider path representation as a unique representation of a strategy pro le, and simply refer to a strategy pro le unless otherwise mentioned. On the other hand, that is not the case with edge representation.

Here is an example where two strategy pro les (path representation) have same edge representation.

Example . . Consider a pNCG namely, say G, on network . d from Figure . , and consider the associated NCG with three players G 3 = G, 3 . In this network, the paths are

π 1 = s e 1 -→ u e 3 -→ v e 4 -→ t, π 2 = s e 1 -→ u e 3 -→ v e 5 -→ t, π 3 = s e 2 -→ u e 3 -→ v
m 1 (π 1 ) = 1 m 2 (π 1 ) = 2 m 1 (π 2 ) = 1 m 2 (π 2 ) = 0 m 1 (π 3 ) = 1 m 2 (π 3 ) = 1 m 1 (π 4 ) = 0 m 2 (π 4 ) = 0
Both path profiles have the same edge-representation, which is n = (n e ) e∈E , where n e 1 = 2, n e 2 = 1, n e 3 = 3, n e 4 = 1 and n e 5 = 2.

We write B edge for the set of edge-representations of all strategy pro les, while we write B path for the set of path-representations of all strategy pro les. Moreover, there is a map which associates a path-strategy pro le uniquely to its corresponding edge-strategy pro le as follows:

Framework for parameterized games on series-parallel graphs De nition . . Γ : B path → B edge maps each path-strategy profile m = (m π ) π∈PathsG to a edge-strategy profile n = (n e ) e∈E where:

n e = π:e∈π m π
To have a simpler notation without any further confusion, we always use m to denote a path representation, while we use n to denote an edge-representation of a strategy pro le.

C

As mentioned earlier, we get back to the non-synchrounous way of computing cost, which has been usual in the literature [ , , , , ] with few exceptions[ , ]. To recall, here a player bears congestion e ect on their cost due to some other player if they both take that edge in their path. With each path-strategy pro le m ∈ B path , and each path π ∈ PathsG, we associate a cost, written as cost π ( m) = e∈π h e (Γ( m) e ), meaning a player who is taking path π in pro le m pays cost π ( m).

Subsequently, the social cost of a strategy pro le m is

soccost( m) = π∈PathsG m π • cost π ( m)
Similarly, from an edge-strategy pro le too, a player's cost can be de ned, but we never use that cost in the sequel, hence it is not being de ned formally.

C

In this chapter, we have formally de ned Parameterized network congestion games on seriesparallel network, in a restricted setting than Part I, putting restriction on (a) arena, and (b) types of strategies. Moreover, the way of computing cost has also been altered from what it was in the earlier part. Each of these restrictions rose from our technical limitations, and we will justify those in details when we approach the problem that we study in the next chapter.

N E P N

In this chapter, we study Nash Equilibria (NE) of parameterized network congestion games (pNCG). Intuitively, a pNCG is a class of network congestion games, in which a game arena is xed and the number of players varies from one game to another. Hence, any NE for an NCG of the class of games represented by a pNCG , is considered as an NE of that pNCG itself. Formally,

De nition . (path-NE). A path-strategy profile

m = (m π ) π∈P G is an NE for pNCG G if it is an NE of NCG G, k , where k = π∈PathsG m π .
We refer such m as a path NE of G.

Recall from Chapter , we de ned a map Γ which associates each path-strategy pro le to an edge-strategy pro le by counting how many players takes each edge in the path-strategy pro le. Using that map, we de ne the following:

De nition . (edge-NE

). An edge-strategy profile n = (n e ) e∈E is said to be an NE for pNCG i there exists a path-strategy profile m = (m π ) e∈PathsG such that Γ( m) = n and m is an NE of for G. Subsequently, we refer to such n as an edge NE of G.

We know NE always exists for an NCG[ ], we have the following result regarding the existence of an NE for a pNCG : Corollary . . Nash equilibria always exists for a parameterized network congestion games.

From hereon, we use N path and N edge to denote the set of path NE and edge NE pro les, respectively.

From earlier chapter of this thesis, we know how to compute an NE for an NCG, and therefore we can e ectively compute NE for any game from the class of games represented by any given pNCG . But from those algorithms, irrespective of the number of players, we essentially need to follow the same method to compute an NE. A priori, we did not know whether an NE of one game is somehow related to an NE of another game from the same class of games represented by a given pNCG . And if they are, can we use that relation to compute an NE for a game from an NE for another game without computing it from scratch?

More speci cally, we are concerned with the problem if and how we can compute an NE for a game with large number of players from NE of games with smaller number of players. In this chapter, we investigate this problem for series-parallel network. Formally, we address the following problem:

De nition . (Problem ). Given a pNCG G on a series-parallel network, can we compute a finite representation of a mapping NE :

N → N |E| such that NE(k) is an NE of G, k .
Remark . . Even though currently, in this chapter, our objective is to study the problem only for series-parallel graphs, many results that we obtain on the way are also true for general graphs. Hence, we specify in the statements when we prove a result only for series-parallel graphs.

In the next section, we rst characterize path NE pro les. From that characterization, we move on to show that the set of edge NE pro les is a semi-linear set, so it has a nite basis and a nite set of periods. We then compute the set of periods, the set of bases, and nally discuss about computability and expressibility of NEs.

C NE P P E R

Here, we rst show when a path-strategy pro le m is a path NE . Intuitively, m is a path NE i for a path π, which is taken by some player in the pro le (i.e. m π > 0), and for any other path π (which may or may not be taken by a player in m), the cost that a player pays in π is less or equal to the cost they would pay in π if they unilaterally deviate. Moreover, cost in π is sum of the cost of each edge e of π, which in turn, is just w e • n e , where Γ( m) = n = (n e ) e∈E . Formally, we have the following (here π \ π denotes the set of edges which are in π, but not in π ): where

Γ( m) = n = (n e ) e∈E .
Proof. The proof is pretty straightforward. Consider a path-strategy pro le m = (m π ) π∈PathsG which satis es ( . ). We also assume Γ( m) = n = (n e ) e∈E . If m is not a path NE , then there exists i ∈ n such that Player i is a deviating player who bene ts by unilaterally deviate from their current strategy. Suppose π be the path Player i is currently taking in m, and π be a cost-e ective unilateral deviation for Player i. Hence, m π ≥ 1 (as Player i is taking π in m) and w e • (n e + 1). Now, if a player deviates from π to π , for the common part of the two paths, π ∩ π , the number of players remain same. Hence, a player who was taking π in m should deviate unilaterally from π to π , and reduce their own cost. That contradicts to our hypothesis that m is an NE pro le.

Note that we have not used series-parallel graph in the above, which implies Theorem . holds for any graph. This also holds true for the next section ( . ) too, but from Section . onward, we will see results that are proven only on series-parallel network.

. Set of NE Profiles as a Semi-linear Set

S NE P S S

A strategy pro le in edge representation is a subset of N |E| . In this section, using the above characterization, we establish that the set N edge ⊆ N |E| of a pNCG G is a semi-linear set. Upon proving this, we will be able to give a structure to N edge , which in turn, enables us to compute an NE for sufficiently large number of players from NE for comparatively small number of players. First, we recall some de nitions from the literature related to semi-linear sets [ ]. Here, we are only interested in semi-linear subsets of N |E| , so we consider the de nitions accordingly. Theorem . . For a parameterized network congestion game, N edge is a semi-linear set.

Proof. In order to prove this, we show that the set of NE pro les in edge-representation is de nable in Presburger arithmetic (PrA ). We know from [ ] that a set de nable in PrA is semi-linear, and vice-versa. We rst recall the de nitions from literature regarding PrA : it is the first-order theory of the model (N, +, =). For every number n ∈ N, the relations <, ≤, modulo comparison relation ≡ m , for natural numbers n ≥ 1, and the functions x → nx of multiplication by natural numbers are de nable in (N, +, =). Therefore, we show here how we can de ne N edge using formulas in PrA .

First, we write the formulas below, and then we justify that each component of each formula is in PrA , in which we will be using the above symbols for having a shorter version of PrA formulas instead of what we would have got if we use only (N, +, =).

EdgePro le(

n = (n e ) e∈E ) := ∀e ∈ E, e∈In(v) n e = e∈Out(v) n e
Here, universal quanti cation over a nite set corresponds to a conjunction over nitely many formulas, each of which are PrA formulas, hence so is EdgePro le( n). Any n such that n |= EdgePro le( n) is an edge pro le of the network.

Nash Equilibria for

∧ (∃ m = (m π ) π∈P , (Γ( m) = n) ∧ PathNE( m) )
Here, PathNE( m) is only satis ed by path-representation of a strategy pro le which is an NE of G, and nally EdgeNE( n) captures the edge representations of those strategy pro les which are NE. Therefore, the set N G can be de ned as:

N G := {(n e ) e∈E ∈ N |E| : (n e ) e∈E |= EdgeNE( n) }
which shows it is a PrA -de nable set, hence by [ ], N G is a semi-linear set too.

P NE

As N G is a semi-linear set, and in nite (at least one NE for each G, k ) for any network G, there exists at least one base vector b and one set of period vectors P i which is non-empty, when we express N G = i∈I L(b i ; P i ). Also note that, by de nition a period vector d = (d e ) e∈E of G is itself a strategy pro le, i.e, d |= EdgePro le( n) (where EdgePro le is the formula in the proof of Theorem . ). Our next objective is to characterize the period vectors for a given pNCG . Intuitively, we rst establish that in a period vector, the cost across any path is constant. This is the key component that we establish only for series-parallel networks, hence restricting the full chapter to this class of graphs.

Theorem . . For pNCG G on a series-parallel network, for any period vector d = (d e ) e∈E , we have the following:

∃κ d ∈ N ∀π ∈ PathsG , e∈π w e • d e = κ d ( . )
Proof. Recall from De nition . of Chapter , a series-parallel network is de ned as either a single edge between s and t, or series/parallel composition of two series-parallel networks. Here, in this proof, we use structural induction on that compositions of series-parallel networks. The base case of this structural induction is a single edge.

For a network G comprised of a single edge e between s and t, the cost must be constant across all paths as there is only one path.

To formalize the induction hypothesis, suppose G 1 = V 1 , E 1 , s 1 , t 1 and G 2 = V 2 , E 2 , s 2 , t 2 are the two series-parallel graphs, and d 1 , d 2 are the two period vectors associated with these two networks respectively. Moreover, we denote P 1 and P 2 as the set of all paths from the corresponding source to target in G 1 and G 2 respectively. As the induction hypothesis, we have the following: for any period vector d 1 = (d In the induction step, one by one, we consider G rst as the series composition G 1 ⊕ G 2 and then as the parallel composition G 1 G 2 , we denote the set of paths to be PathsG, and establish that for any period vector d of G, there is a κ d satisfying above.

Firstly, we consider G to be G 1 ⊕ G 2 . From the series composition, we have t 1 of G 1 and s 2 of G 2 merged into a single vertex, say v, of G. Therefore, any path π of PathsG can be thought of as concatenating two paths π 1 of P 1 and π 2 of P 2 , slightly abusing notations though. w e • d e > 0. Note that, even though we x a π 1 ∈ P 1 and π 2 ∈ P 2 , and de ned M , this would remain the same if we take some other π 1 ∈ P 1 and π 2 ∈ P 2 because of the induction hypothesis.

Nash Equilibria for Parametric Network congestion games

Now, we consider an NE pro le n = (n e ) e∈E ∈ N G , and also an arbitrary path NE m = (m π ) π∈PathsG with Γ( m) = n. With this, we can take a path π ∈ P 1 with m π > 0. Now for this π ∈ P 1 , and the π 2 ∈ P 2 that we xed earlier, we have from ( . ): This contradicts to the fact that n is an edge NE and m π > 0. Hence, M must be 0, which implies we can take

κ d = κ 1 = κ 2 .
A S E P V

We now have two sets of linear equations that a period vector of a pNCG must satisfy, the rst one being the set of flow equations for the arena, and the second one, with a parameter κ x , is the one that we got from Theorem . . We call the latter set of equations the κ x -parameterized cost equations. Together, we have:

Corollary . . Any period vector d = (d e ) e∈E of a pNCG on a series-parallel network game is a solution to the following system of linear equations:

• ∀v ∈ V \ {s, t} e∈In(v)
x e = e∈Out(v)

x e

• ∃κ x ∀π ∈ PathsG e∈π w e .x e = κ x

We refer to the above system of equations as E(κ x ) with (x e ) e∈E , corresponding to each edge, and a parameter κ x .

Note that, in E(κ x ) there are |V | -2 many ow equations, |PathsG| many equations from Theorem . , and |E| many variables. If |V | -2 + |PathsG| > |E|, then the system of equations may have multiple solutions. Consider Example . , where this is indeed the case.

. Period vectors of edge NE profiles As we see in the above example, the κ x -parameterized cost equations may not be optimal as a set, in the sense that there might be a smaller set of linear equations, which is a subset of κ xparameterized cost equations and the set of solutions of whose coincides with the same.

s v t x → x a x → 2x b x → x c x → 2x d
In the following, we compute such a minimal set, and then go on to prove that together with the ow equations, this set has a unique solution.

We de ne a set of covering paths for a pNCG G. Intuitively, this is a subset of PathsG such that for a given strategy pro le d edge , if the cost across all the paths in this covering set of paths is constant, then so is across all paths from s to t.

A

CovP(G) Intuitively, we choose a subset of all paths in such a way that cost of all the other paths in PathsG is already determined by the paths that are already chosen in the set.

To construct such a set, for vertex v ∈ V , we rst x an ordering O among the outgoing edges Out(v) from each vertex, and among its incoming edges In(v) of each vertex. With respect to this ordering, for each v, we de ne two paths: a path from v to t, denoted by fst_fwd(v), and a path from s to v, denoted by fst_bwd(v).

Intuitively, we construct these two paths for v ∈ V \ {s, t} in the following manner:

• fst_fwd(v): We build the path step by step, adding an edge at each step from v, till we reach t. At the very rst step, we start from vertex v, and consider the first edge, say e 0 = (v, v 1 ) in Out(v) with respect to ordering O.

If v 1 = t, then fst_fwd(v) = v e 0 -→ v 1 , otherwise
Nash Equilibria for Parametric Network congestion games we extend v e 0 -→ v 1 by considering rest of the from v 1 in following inductive way. At i th step, say the currently built path is π = v e 0 -→ . . .

e i-1 ---→ v i . If v i = t,
then we declare π to be fst_fwd(v), otherwise we add the rst edge from Out(v i ) with respect to O to π, and proceed to the next step.

• fst_bwd(v): Similarly, we build this path step by step too, except here, at each step we build it in reverse order, starting from v, and terminating when we reach s.

Moreover, we de ne both fst_fwd(t) and fst_bwd(s) to be the empty path. Proof. We rst show that the set S indeed satis es ( . ), i.e, we need to show that for any strategy pro le if the cost across every path in S is the same in that pro le, then the cost across all paths (including those that are not in S) is the same too. We , the other case is symmetric.

.

Period vectors of edge NE profiles

With this assumption, we show the following by induction: For all 0 ≤ j ≤ |ρ| -1, the path π j = e j • fst_fwd(v j+1 ), which is a path from v j (of ρ) to t, satis es j≤i≤|ρ|-1

w e i • d e i > e∈π j w e • d e
Once we prove this, we can actually show that there are two paths π, π in S, for which As the induction hypothesis, let us suppose the statement is true for some j < |ρ| -1. Then to show it is true for j + 1, we start with the induction hypothesis and proceed as follows:

j≤i≤|ρ|-1 w e i • d e i > e∈π j w e • d e =⇒ j≤i≤|ρ|-1 w e i • d e i -w e j • d e j > e∈π j w e • d e -w e j • d e j =⇒ j+1≤i≤|ρ|-1 w e i • d e i > e∈fst_fwd(v j+1 ) w e • d e
[From the fact π j = e j • fst_fwd(v j+1 )] Now adding an identical term to both sides, we get

e∈fst_bwd(v j+1 ) w e • d e + j+1≤i≤|ρ|-1 w e i • d e i > e∈fst_bwd(v j+1 ) w e • d e + e∈fst_fwd(v j+1 ) w e • d e = e∈fst_bwd(v j+1 )•fst_bwd(v j+1 ) w e • d e = c x (*) =⇒ e∈fst_bwd(v j+1 ) w e • d e + j+1≤i≤|ρ|-1 w e i • d e i > e∈fst_bwd(v j+1 ).π j+1 w e • d e
which nally implies:

j+1≤i≤|ρ|-1 w e i • d e i > e∈π j+1 w e • d e
This ends the proof of the induction.

Now consider

j = |ρ| -1. As π |ρ|-1 = v |ρ|-1 e |ρ|-1
---→ t, by the statement we just proved, we have w e |ρ|-1 • d e |ρ|-1 > w e |ρ|-1 • d e |ρ|-1 , which clearly is a contradiction.

Nash Equilibria for Parametric Network congestion games

Hence, S satis es ( . ). Finally we will show now that the size of S is |E| -|V | + 2. Note that in Algorithm , except for s, for each vertex v with degree ≥ 2, we add deg(v) -1 many paths to S. And for s, we add deg(s) many paths. Moreover, any path in the set S, barring the very rst one that gets added in the procedure, has an unique identifying edge that is not shared by any other paths in the set. And the path, that gets added rst in the set, is the only path of which every edge is the " rst" outgoing edge (with respect to ordering O) of the corresponding vertex. This means at each step the algorithm adds a new path in the set until it terminates. Therefore, the size of the set: For this particular example, we write a candidate for period vector as x = (x a , x b , x c , x d ). Now, for S -ac , x = (3, 3, 1, 2) works as 2.3 + 1 = 3 + 2.2 but for the path ac, the value is 4. Similarly, it is easy to check that for S -bd and S -bc , (2, 1, 3, 0) and (3, 0, 1, 2) works for supporting example which makes that no S -π is a set of covering paths for π ∈ S.

|S| = v:deg(v)≥2 (deg(v) -1) + 1 = v∈V \{t} (deg(v) -1) + 1 [As t
Remark . . In the following, in essence we are going to show that this minimality holds for all graphs. We say this in essence because this is not the result we seek, rather our larger goal is to obtain period vectors for the set of NE. As a mandatory byproduct, we can see that the covering set of paths computed in Algorithm is, in fact, a minimal set of covering paths.

"S

With this set of covering paths CovP(G) of size |E| -|V | + 2, we now have a reduced system of parameterized linear equations with parameter κ x , which a period vector of arena G satis es:

• ∀v ∈ V \ {s, t} e∈In(v) x e = e∈Out(v) x e • ∃κ x ∀π ∈ CovP(G) e∈π w e .x e = κ x
We refer to this system of equations as E CovP (κ x ). Here, we have |V | -2 ow equations as before, and |E| -|V | + 2 κ x -parameterized cost equations. This constitutes a system of |E| linear equations over |E| unknowns and a parameter κ x .

We can also express this system of parameterized linear equations as M G • X = b, where M G is an |E| × |E| matrix, which we refer to as the period-generator of G, with entries only from {w e : e ∈ E} ∪ {0, -1, 1}, b is a column matrix with |E| rows, in which the rst |V | entries are 0 and rest of the entries are κ x , and each of the |E| entries of X is the unknown variable x e from the linear equations, corresponding to each edge of E.

Each column of M G corresponds to an edge e ∈ E, the rst |V | -2 rows of M G correspond to each vertex v ∈ V \ {s, t}, and each of the rest of |E| -|V | + 2 rows correspond to each of the paths in CovP(G). Therefore, each entry of M G can be referred to be either as the (v, e) th entry for each v ∈ V \ {s, t} and e ∈ E, or as the (π, e) th entry for each π ∈ CovP(G) and e ∈ E. To be speci c, here we explain how exactly M G looks like:

• Let us consider m v,e to be the (v, e) th entry, then

m v,e =      1 if e ∈ In(v) -1 if e ∈ Out(v) 0 otherwise ( . )
We denote the v th row of M G by m v .

• And for the (π, e) th entry, denoted by m π,e , we have

m π,e = w e if e ∈ π 0 otherwise ( . )
We denote the π th row of M G by m π for π ∈ CovP(G).

Theorem . . For any network G = V, E, s, t , the |E| × |E| period-generator M G is invertible.

Proof. Suppose there exists an f satisfying M G • f = 0. Then there are exactly three possibilities regarding f :

• either f ≥ 0, i.e, for all edges e ∈ E, f e ≥ 0, or • f ≤ 0, i.e, for all edges e ∈ E, f e ≤ 0, or

• there exists e i , e j ∈ CovP(G) such that f e i > 0 and f e j < 0.

In all three cases, we will reach a contradiction if f = 0, henceforth proving that

M G • f = 0 implies f = 0. Case : f ≥ 0.
Suppose towards contradiction that f = 0, and there is an edge e such that f e > 0. Let us also assume π ∈ CovP(G) be a path of which e is an edge, and consider the row-matrix m π as it was de ned in ( . ).

Now, M

G • f = 0 implies m π • f = e∈π w e • f e = 0.

Nash Equilibria for Parametric Network congestion games

Because for all edges e , w e > 0, and f e ≥ 0, f e > 0 makes ρ π . f = e∈π w e • f e greater than 0 too. This contradicts with the hypothesis M G • f = 0. Therefore, there cannot be such an edge e with f e > 0, which means f ≥ 0 implies f = 0.

Case

: f ≤ 0.
This case is symmetric to Case , which means in this case also f has to be 0. Case : ∃e i , e j ∈ E : (f e i > 0) ∧ (f e j < 0).

s + + + +/0 +/0 - S 0 F 0 - - -/0 S 1 - F 1 - - + + + + + + - S 2 F 2 - - F 3 S 3 - + t - u v -/0 -/0
Before going into details, we rst brie y summarize the main steps of the whole argument by which we proceed with this case:

Step I: We argue that there is a path π with e i , e l ∈ π such that f e i > 0 and f e l < 0.

Step II: We de ne the notions of positive, negative and zero paths, and argue why all paths are, in fact, zero paths from M G • f = 0.

Step III: We show the existence of either a positive or a negative path. To prove this, we build a sequence of sets of vertices along with an increasing sequence of integers which are bounded above, thus making it impossible to grow the sequence in nitely. But by design, the sequence only stops if there is either a positive or a negative path. Now, the existence of either path contradicts with Step II, thus concluding that the hypothesis on the Case itself is wrong. S I We can easily conclude from Case and that, there cannot be a path π ∈ PathsG such that there is an edge e ∈ π with f e > 0 (or f e < 0 resp.), and for all other paths e of π, f e ≥ 0 (or f e ≤ 0 resp).

Therefore, for any π ∈ CovP(G), either for all edges e ∈ π, f e = 0, or there are edges e, e ∈ π such that f e > 0 and f e < 0. If indeed for all paths π, for all edges e ∈ π, f e = 0, we have nothing to show further, Case stops here. Hence, we can assume there is a path π where the latter condition holds. We consider this path π ∈ CovP(G) in the subsequent part of the discussion.

S

II Here, we de ne some notions as follows: for any path v σ v , we call σ positive, negative, and zero respectively if S III Now let's get back to π considered in the rst step. Without loss of generality, we assume that the rst non-zero (i.e, positive or negative) edge of π is positive.

Recall from the plan, here, our objective is to show that there exists either a positive or negative path.

We construct an in nite sequence of non-empty sets of vertices S l l≥0 , along with another increasing sequence of non-negative integers F l l≥0 . Moreover, we de ne the latter sequence in such a way that each F l is bounded above .

Hence, there is a contradiction because using only nitely many numbers it is not possible to form an in nite increasing sequence! We start with the construction of the sequences S l l≥0 and F l l≥0 . In Lemma . , we show that S l 's are non-empty, which is crucial to justify F l 's are indeed well-de ned. In Nash Equilibria for Parametric Network congestion games Lemma . , we prove that the sequence F l l≥0 are indeed increasing. We nally conclude giving the bound for F l 's, and with the argument how the contradiction comes in place. Now, we start de ning the sequence of sets of vertices as follows:

S 0 = {v ∈ V : ∃ a path σ : s σ v such that (∀e ∈ σ f e ≥ 0) and (∀e ∈ Out(v) , f e < 0)}
Intuitively, S 0 is the set of vertices to which there is a path σ from s satisfying (a) all the edges in σ are positive or zero, and (b) all the edges outgoing from v are strictly negative.

First, we claim that S 0 is non-empty. We assumed the rst non-zero edge of π to be positive.

Let u e -→ v be that edge, then if every outgoing edge of v is negative, then v is in S. Otherwise, there is an edge v e -→ v in Out(v), which is either positive or zero. This v might be a candidate of S 0 , if all the outgoing edges of v are negative. If not, we take a non-negative outgoing edge of v , and continue. In this way, if we reach t before nding a v in S 0 , then we have a positive path from s to t, a contradiction! Hence, S 0 must be non-empty.

And we de ne,

F 0 = u e - →v∈E v∈S 0 f e
Here, we take the sum over all the f e -values of all edges that are incoming to vertices of S 0 . As by de nition, all the incoming f e 's are positive or zero for S 0 , we have F 0 ≥ 0.

The sequence starts from S 0 , then for each m ≥ 0, we inductively de ne S 2m+1 from S 2m and S 2m+2 from S 2m as follows:

S 2m+1 = {v ∈ V : ∃v ∈ S 2m , ∃ a path v σ v such that for all e ∈ σ, f e ≤ 0} S 2m+2 = {v ∈ V : ∃v ∈ S 2m+1 , ∃ a path v σ v such that for all e ∈ σ, f e ≥ 0}
Moreover, we de ne:

F 2m+1 = u e - →v∈E u∈S 2m+1 ,v∈S 2m |f e | and F 2m+2 = u e - →v∈E u∈S 2m+1 ,v∈S 2m+2 f e
Intuitively, here as F 2m+1 , we take the sum of all absolute values of f e over the set of incoming edges from S 2m to S 2m+1 , while as F 2m+2 , we take the sum of all absolute values of f e over the set of all outgoing edges from S 2m+1 to S 2m+1 . Notice that in Figure . , that the rst set of f e values are negative, while the latter set of f e values are positive.

To show that the sequence F l l≥0 is well-de ned, we need to show that S l is non-empty for all l ≥ 0. Earlier, we established that S 0 is non-empty. For the rest, consider the following lemma:

Lemma . . For l ≥ 0, S l is non-empty.

Proof. By induction on l, we, in fact, prove that: S l is non-empty, and for every vertex v of S l , there is a positive path from s to v, and a negative path from v to t.

First consider l = 0. We already observed that S 0 is non-empty. Moreover, by de nition of S 0 , for any vertex v ∈ S 0 , there is a positive path σ + sv from s to v. Now, because for any path Hence, σ , which is a path from v to t, is a negative path. Therefore, the base case of the induction is done.

π c ∈ CovP(G), ρ π c • f = e∈π c w e • f e = 0,
For the inductive step, we assume that the statement is true for l = 2m, i.e, S 2m is nonempty, and for every vertex v of S 2m , there is a positive path from sσ + sv v, and a negative path from vσ - vt t. Now, consider l = 2m + 1. From the inductive hypothesis, we have that S 2m is non-empty, however, we additionally claim that there is a vertex v in S 2m such that for all outgoing edges e of Out(v), f e < 0. Suppose this is not the case. Then, starting from any v of S 2m , we can construct a path σ till t such that for all edges e ∈ σ, f e ≥ 0. But that constitutes a positive path from s to t itself, which is a contradiction! Therefore, our claim is true. Now, consider such a vertex v from S 2m , for which every outgoing edge e is negative, which implies

e∈Out(v) f e < 0.
Because there is a positive path from s to every vertex of S 2m , and a negative path from every vertex to t, s and t themselves cannot be in S 2m , i.e, the chosen v is in V \ {s, t}. Hence, we can consider the row-vector ρ v of M G corresponding to vertex v. Now, from

ρ v • f = 0, we have e∈In(v) f e = e∈Out(v)
f e which is negative. Hence, there has to be an edge u e -→ v for which f e < 0, which implies u ∈ S 2m+1 . That is S 2m+1 is non-empty.

Moreover, for every vertex u of S 2m+1 , by de nition, there is a vertex v in S 2m such that there is a negative path u σ - uv v. Therefore, adjoining σ - uv to the negative path v σ - vt t, we Nash Equilibria for Parametric Network congestion games get a negative path, say σ - ut = σ - uv • σ - vt , form u to t. Now, to show there is a positive path from s to u, we proceed similarly as we did when we ought to show that for every vertex v of S 0 has a negative path to t, except here is a change of sign. Consider a path π ∈ PathsG via u such that π = σ • σ - ut for some σ. Then we have

e∈π w e • f e = e∈σ w e • f e + e∈σ - ut w e • f e = 0
Hence, σ is a positive path indeed. This concludes proving the statement for l = 2m + 1.

Finally, we need to show the same for l = 2m + 2, where we assume the statement is true for l = 2m + 1. Again we start with the argument that there is a vertex v in S 2m+1 such that every incoming edge of v is positive. If not, then we can back track from v via non-negative edges till we reach s, and this implies existence of a negative path form s to t, hence a contradiction! Therefore, indeed there is a vertex v in S 2m+1 such that every edges of In(v) is positive. Now, x this vertex v from S 2m+1 , and we have

e∈In(v)
f e > 0. Again, we have

e∈In(v) f e = e∈Out(v)
f e , from which we get there must be an edge v

e - → u ∈ Out(v) such that f e > 0.
Hence, S 2m+2 is non-empty.

For a vertex u in S 2m+2 , there is a vertex v in S 2m+1 , therefore we get a positive path σ + su by simply adjoining the positive paths σ + sv and σ + vu . For the negative path, our argument is exactly similar as it was in case of a vertex of S 0 . We consider a path π from s to t, that extends σ + su by, say v σ t. Therefore, Hence, σ, which is a path from u to t, is a negative path.

As S l is non-empty for all l ≥ 0, we establish that F l is well-de ned for all l ≥ 0. In the following, we show that the sequence F l l≥0 is, in fact, an increasing sequence.

Lemma . . For any l ≥ 0, F l+1 > F l .

Proof. We prove this by induction on l, the approach is quite similar to how we proved Lemma . . First note that, from M G • f = 0, we have for any vertex v,

e∈In(v) f e = e∈Out(v)
f e , which we can also write in terms of absolute value of f e 's as:

e∈In(v) fe>0 |f e | + e∈Out(v) fe<0 |f e | = e∈Out(v) fe>0 |f e | + e∈In(v) fe<0 |f e | ( . )
As this is true for any vertex v, it holds if we take a sum over any collection of vertices of V .

In particular, for all l ≥ 0, Now, for l = 0, in the left hand side (L.H.S) of identity ( . ), the rst term is F 0 and the second term is strictly positive (as for all vertices in S 0 , all outgoing edges are negative). Moreover, in the right hand side (R.H.S), the rst term is 0 (because there is no positive outgoing edge), and the second term is F 1 . Therefore, we have

F 0 + M = 0 + F 1 where M = e∈Out(v),fe<0 v∈S 0 |f e | > 0. Hence, F 1 > F 0 .
Therefore, the base case of the induction is done.

As the inductive hypothesis, we assume that the statement is true for l = 2m, which means:

F 2m+1 > F 2m .
For l = 2m + 1, we consider ( . ) with substituting l by 2m + 1, by which we get Here, the rst term in the L.H.S is positive from the fact that there is a vertex v in S 2m+1 for which all the edges in In(v) is positive. We argued this inside the proof of Lemma . , the crux being otherwise we would have a negative path from s to t, which, in turn, would give us a contradiction!

The second term of the L.H.S is at least F 2m+1 because the term here is the sum of all the |f e |'s of all negative outgoing edges of all vertices in S 2m+1 , while F 2m+1 is just the sum over a particular subset of those edges.

The rst term of the R.H.S is exactly F 2m+2 because for v ∈ S 2m+1 , for any edge v e -→ u with f e > 0, we put u in S 2m+2 .

Finally, for the second term of R.H.S, note that for any v ∈ S 2m+1 , for any edge u e -→ v ∈ In(v), if f e < 0, then u also belongs to S 2m+1 . Therefore, that particular |f e | also appears as a contributing factor when we consider outgoing edges Out(u) of u. That means this quantity gets completely subsumed by the second term of the L.H.S. More speci cally, we can rewrite the above as:

P + (F 2m+1 + Q + R) = F 2m+2 + Q where P = e∈In(v),fe>0 v∈S 2m+1 |f e | > 0 Q = e∈In(v),fe<0 v∈S 2m+1 |f e | = v e - →v ∈Out(v),fe<0 v∈S 2m+1 ,v ∈S 2m+1 |f e | R = v e - →v ∈Out(v),fe<0 v∈S 2m+1 ,v / ∈S 2m+1 |f e | Clearly, F 2m+2 > F 2m+1 .
The remaining case is when l = 2m + 2. Again we consider ( . ) with substituting l by 2m + 2:

e∈In(v),fe>0 v∈S 2m+2 |f e | + e∈Out(v),fe<0 v∈S 2m+2 |f e | = e∈Out(v),fe>0 v∈S 2m+2 |f e | + e∈In(v),fe<0 v∈S 2m+2 |f e |
This case is similar to S 0 . Here the rst term of the L.H.S is at least F 2m+2 , the second term is positive just like it has been argued in case of S 0 . On the other hand, the rst term of the R.H.S takes care of the internal edges of S 2m+2 , and hence the whole terms gets subsumed by the rst term of the L.H.S. Finally, the second term of the R.H.S is exactly F 2m+3 because for any vertex v of S 2m+2 , by de nition for any negative incoming edge u e -→ v, e is in S 2m+3 . Hence, here we can rewrite the above as:

(F 2m+2 + Q + R ) + P = Q + F 2m+3 where Q = e∈Out(v),fe>0 v∈S 2m+2 |f e | = v e - →v ∈In(v),fe<0 v∈S 2m+2 ,v ∈S 2m+2 |f e | P = e∈Out(v),fe<0 v∈S 2m+2 |f e | > 0 R = v e - →v ∈In(v),fe<0 v∈S 2m+2 ,v / ∈S 2m+2 |f e |
. Period vectors of edge NE profiles Therefore, F 2m+3 > F 2m+2 .

As we mentioned brie y earlier, F l for each l ≥ 0 belongs to a nite set. In particular, it is easy to see that, F l ∈ { e∈E |f e | : E ⊆ E}, which is a nite set. Therefore, an in nitely-increasing sequence F l l≥0 cannot be possible.

Hence, our initial assumption that there exist edges e i , e j with f e i > 0 and f e j < 0 is wrong.

So, we can conclude from the analyses of the above three cases, whenever M G • f = 0, f must also be 0. In other words, M G is invertible.

C

Here, we will show that all the period vectors for a N G are co-linear.

As M G is invertible, we have a unique parameterized solution for M G • X = b, and that is:

X = M -1 G 0 κ x
That is two period vectors di er from each other due to their corresponding value taken for the parameter κ . d, which we can write as d = p q .g. δ, where gcd(p, q) = 1. Also note that gcd e∈E δ e = 1. Now, if we can show q|g, we are done. Let us de ne g = gcd(g, q), and take m n = g/g q/g , which implies gcd(m, n) = 1. From this, we can further write d = p.m n δ where gcd(p.m, n) = 1. Suppose n = 1. In that case, from the fact d e ∈ N for all e ∈ E (by design), we have n|δ e for all e ∈ E, which essentially means gcd e∈E δ e ≥ n > 1. Contradiction! That means n must be 1, and we are through.

Therefore we have:

N G = i∈I L(b i , {m ij • δ : 1 ≤ j ≤ |P i |, m ij ∈ N}) ( . )
Here, Base = {b i : i ∈ I} is the nite set of basis for some index set I, with |I| < ∞. Note that, for any semi-linear set, the choice of basis and the set of period vectors may not necessarily be unique. As of yet, we have established a property which every period vectors necessarily satis es.

D

From ( . ), we have m • δ for some m ∈ N as a period vector for some base vector b. Here, b itself is an edge NE which means there is a path NE corresponding to it. And for any path-strategy pro le corresponding to m • δ, we know that the costs across all paths are identical. With these, and using the series/parallel composition, we thus formulate the following conjecture:

Conjecture . . For series-parallel graph G, δ is a period vector for all the bases of N edge G .

Although, we do not have a proof for the above conjecture for the moment, which understandably makes the rest of the part incomplete. Therefore, for the rest, we show what the consequences are if it is indeed true.

First of all, then we can write: Note that, the sets of bases in ( . ) and ( . ) may not necessarily be identical. In the next section, we embark upon to compute the set of bases in the latter case, to draw a complete picture for the set of NE of an pNCG in a series-parallel graph (albeit the proof of conjecture).

N G = i∈I L(b i ; { δ}) (

B S E NE

Recall Problem . at the beginning of this Chapter. Our objective was to compute Nash equilibria for su ciently large number of k. In fact, we will represent the set of all NE, N G , by a nite basis, and the sole period vector, from which the solution of the above problem comes as an easy consequence.

First, we show that if one component of an NE pro le of a series-parallel network G is bounded, then so are all other components. In other words: Lemma . . The set BoundN E(e, M ) = { n = (n e ) e∈E ∈ N G : n e < M } is finite when G is a series-parallel network.

Proof. In order to prove this, it is enough to show that for every edge e ∈ E, there exists a function f e,e : N → N such that for all NE n with n e < M , n e < f e,e (M ).

. Conclusion

We prove the above by structural induction on G. The base case of this induction is when G is a single parallel network. Now: w e • n e ≤ w e • (n e + 1) Thus, f e,e (M ) = w e w e (M + 1) ( . ) S C Suppose G 1 and G 2 are two series-parallel networks composed in series at vertex v, yielding a network G. We also suppose that e is an edge of G 1 , and e is an edge of G 2 . As an induction hypothesis, we assume that for every edge e of G, there is a f e,e . Then from ow equations, a crude upper-bound for n e can be given as: Suppose G 1 and G 2 are two series-parallel networks composed in parallel, yielding a network G. We also suppose that e is an edge of G 1 and e is an edge of G 2 . As an induction hypothesis, we assume that for every edge e of G 1 , there is a f e,e , then

C

In this chapter, we considered the problem which asks for a nite representation of a function which maps an integer k to an edge NE pro le with k players. We established that the set of edge NE pro les is a semi-linear set, and we obtained a parameterized system of equations, of which every period vectors of the semi-linear set is a solution. Then, we exploit the semantics of the system of equations to show that given a parameter, there is a unique solution to the system of equations. From this, because of the parameter, we established that all the period vectors of the semi-linear set that characterized the set of all NE, are co-linear. Finally, we formulate a conjecture which says that not only all the period vectors are co-linear, there is a unique period vector which works for all bases. If this conjecture turns out to be true, then we would have a nite representations of the set of all NE of a pNCG, which easily answers the problem that we considered at the beginning of the chapter.

In this chapter, we summarize the contributions of this thesis, discuss the shortcomings and try to shed lights on what possible future directions can be taken from here.

S N C G F N P

We de ned a new model of network congestion games with two features: cost computation at synchronized congestion only and dynamic strategies In this model, we obtained algorithms for three constrained optimal problems: Social optima (SO), Nash Equilibria (NE) and Subgame Perfect Equilibria (SPE) in Chapter , and respectively. In the following, we brie y recall how we addressed these problems, and what complexity bounds we obtained.

We started with the constrained social optimal problem, in which given an instance of a network congestion game and a value, we asked whether there is a strategy pro le with social cost less than the given value. To solve this problem, a naive approach could to guess a play (aka a path in the con guration graph), step by step, while maintaining a counter to keep in check the social cost within the given threshold. This approach would give us a EXPSPACE complexity. To have a better upper bound complexity result, we exploited the graph structure and the cost computation model, and abstracted away exact con guration to their Parikh image. Then in that abstract con guration graph, we non-deterministically guess a play, and check whether its social cost is less than the given threshold. Because acyclic strategy pro les su ce, this yields a PSPACE-algorithm.

In case of Nash Equilibria (NE), we rst showed the existence of NE in our model of network congestion games, by showing convergence of the best-response dynamics. Then, we studied a similar constrained problem for NE, where the input again is an instance of an NCG and a threshold. Our approach to tackle this problem was similar to what we did for SO, except here we verify two conditions. We non-deterministically, step by step, guess a play of the game, and at each step verify: whether the cumulative social cost up to current step is still less than the threshold, and whether it is going to be the outcome of an NE.

To check the rst condition, just like the SO problem, we maintain a counter which stores the cumulative social cost, and verify at each step.. For the second condition, our algorithm makes use of a characterization of all NE outcomes. The characterization justi es that if a player were to deviate, there is a response from the coalition of other players which would make this deviating player's cost worse than what would have been if they didn't deviate. Now, in the characterization itself, we made use of a two-player (zero-sum) total payo game[ ], and the value in that game. This game is actually between a deviating player and the coalition of all other players, and the value in that game is the worst cost that the deviating player may end Conclusion up paying due to how the coalition punishes. Our algorithm maintains a counter for each player, and veri es at each step whether the cost up to that step is less than the values of these two-player games for each deviating player and for their all possible unilateral deviating con gurations.

Because computing the value in the above-mentioned two player games can be done in EXP-TIME, our algorithm has an EXPSPACE complexity.

Finally, we turned our focus to subgame perfect equilibria (SPE) -another solution concept for stability, but more relevant in the dynamic setting. Unlike NE, in our model of NCG we have neither a proof of existence of SPE, nor we have an example where we can show that SPE do not exist.

Nonetheless, we considered the constrained SPE problem similar to that of SO and NE. Not surprisingly this is technically more challenging than the earlier two. Again our basic approach remains the same as it were for NE: we guess a play in the game, and verify whether it is an outcome of an SPE with social cost less than the threshold given in the decision problem. To verify whether the play is indeed an outcome of an SPE, we make use of a characterization of outcomes of SPE.

The main idea behind the characterization is to de ne a function which maps an edge to a so called λ-value such that any SPE outcome starting from that edge must have cost less than that λ-value, and then showing that any play is an outcome of an SPE i it is so-called λ-consistent.

In fact, we build this λ-mapping recursively till it reaches a x-point: the i th λ-value is de ned using the (i -1) th λ-consistent plays, and so on. Initially, all plays are λ-consistent, at each step when we update the λ-values, and subsequently the set of λ-consistent plays gets re ned, which nally, when reaches a xed-point, gives exactly the set of outcomes of all SPE. One way to obtain a negative instance on the existence of SPE problem (if exists) could be to see if there is an NCG, for which at some step of updating λ-value, the set of λ-consistent plays became empty. Nonetheless, at the end, we check whether the set corresponding to the x-point contains a play with social cost less than the bound given in question. This gives us EXPSPACE-membership of constrained SPE problem.

P N C G

In this second part of the thesis, we consider parametric network congestion game (pNCG) where the number of players is a parameter. Our aim in this part has been to compute optimal strategy pro les (NE, SO etc) for arbitrary large number of players from their counterpart in the same network with small number of players. We rst introduced a necessary framework to study pNCG for series-parallel network. It is noteworthy that for this part, we re-adjust the model to only consider path strategies and nonsynchronous path computation. As per our knowledge, it has not been studied how NE pro les are related with each other when we vary the number of players in an instance of congestion games, in any model. Therefore, we considered the classical model for the network congestion games , and started studying the same on it; of course our future goal would be to extend it into our model of NCG, mainly to incorporate the dynamic strategy structure.

Then we started studying NE for pNCG in series-parallel graph. The set of all NE is a semilinear set in the current framework, and we obtained a pattern on the set of period vectors of the semi-linear set. At this point, we made a conjecture which says, in fact, there is a unique period vector for a pNCG. If the conjecture turns out to be true, then we can compute each and every Conclusion NE of the pNCG by a nite set of NE (for small number of players) and the unique period vector (which we call the shift vector of pNCG). This will enable us to comment on best/worst NE in the pNCG, how they evolve as the number of players change in an NCG.

F W

In this section, we rst go through some of the follow-up questions that have come up in the earlier chapters, and then we discuss some research directions that our work may embark upon.

I M This thesis leaves several complexity questions open. We have NP-hardness for Social optimal, but there too remains a gap with the PSPACE membership. Hence, an immediate series of follow-up questions would be to nd hardness complexity results for NE and SPE problem, and/or to improve the upper bound complexity results to close the gaps.

E SPE

Even though we obtained an algorithm for constraint SPE problem, we haven't managed to neither positively nor negatively answer whether SPE exists in our model. In another dynamic model of congestion games, namely dynamic resource-allocation games[ ], there does not always exist an SPE. But in that game, the non-synchronous cost computation model has been a major contributing factor in designing an instance where SPE doesn't exist, which has no immediate consequences in our setting. Therefore, it remains an open problem in our model.

P C

Regarding parametrized congestion games, one way to go ahead is to prove the conjecture that we formulate, which says, there is an unique period vector for a pNCG. As mentioned earlier, this completes studying the problem for NE, and an immediate follow-up would be if similar results can be obtained for SO, which in turn might show how Price of Anarchy (PoA)/Price of Stability(PoS) evolves as the number of players grows in an NCG.

Even though some of the results on this part have been proven only for series-parallel graphs, some other results, notably the most technically challenging result on this part have been shown for any network arena whatsoever. This opens up a possibility to look at the problem for larger class of arenas, and possibly extending to dynamic strategies.

L O

C I In our model of NCG, the players when they make their next move from a vertex, know where all the other players are, and take their decision accordingly. This may not always be realistic. There might be scenario where one or more player get to know only partial information about other players' position, which should leads us to study imperfect information games in the context of network congestion games. Both in turn-based [ , , ] and concurrent [ , , , ] settings, imperfect information games Conclusion have been studied extensively for di erent objectives. But, to the best of our knowledge, imperfect information have not yet been studied in congestion games. To give a basic framework, we can start with the concurrent game structure that we have associated with NCG, where a con guration of the NCG represents a state of the concurrent game. We declare two states of the concurrent game equivalent from the point of view of a player if in the respective con gurations, the number of players that they observe is the same. We have used similar information graph in our model for solving the decision problem related to social optima. But for the equilibria we have used full observations of a player, therefore we believe this is an interesting framework to investigate what kind of stable pro les can be achieved when the information set is partial, and how well/bad it might perform with respect to a pro le which optimizes social cost.

D T C

In our model of NCG, there is no separate temporal component. Similar to any other possible resources a ected due to congestion, like fuel cost in case of road-tra c, and connection/broadcast quality in case of internet, time here is also abstracted as a part of the cost. A separate temporal component had been added and studied in the context of congestion games in [ , , ]. Avni et al. [ ] compute congestion cost depending on how much time (continuous) a player spend with another player together at some vertex. Cost functions are associated with vertices, and there are conditions associated with edges which make players stay at a vertex for some time. Because they consider continuous time-points, this framework raises an uncountable strategy space for players. The setting is more general than what we have considered here except they do not consider dynamic strategies. They have studied the existence of NE, and then following the classical approach they comment on bounds of PoA/PoS for their model. Hence, what we can propose for a future work is to study our constraint problems(SO, NE, and SPE) in the timed setting with dynamic strategies. Notably, existence of SPE also needs to be addressed when we extend timed setting into dynamic strategy space.

Both the above mentioned long-term objectives are related to our model described in Part I. This is because, having only some preliminary results in Part II, we believe there are lots of gaps to ll in here on its own, and then only we could provide a convincing argument to go forward on that line of research. Nonetheless, we believe computing solution concepts for instances with many players from instances with fewer players could be, in general, an interesting topic to investigate in several contexts.

Mot clés : Jeux de congestion, équilibres de Nash, équilibres parfaits en sous-jeux, jeux de congestion paramétrés, théorie algorithmique des jeux Résumé : Les jeux de congestion sont un domaine de recherche bien étudié ; dans ce domaine, les jeux de congestion dans les réseaux premettent de représenter la congestion des réseaux de distribution, et d'étudier à quel point un modèle de réseau est bon ou mauvais en termes de coût total lorsque chaque joueur joue de façon égoïste, cherchant uniquement à optimiser son propre coût ; Nous considérons ces jeux de congestion du point de vue des méthodes formelles, cherchant à vérifier par exemple que, dans un réseaux fixé, il existe un profil de stratégies optimal qui satisfasse une propriété donnée.

Nous définissons un modèle de jeux de congestion avec deux particularités : d'une part, le calcul du coût d'une transition dépend du nombre de joueurs utilisant simultanément une arête ; d'autre part, les joueurs choisissent leur chemin de façon dynamique en fonction des choix des autres joueurs. Nous montrons que dans ce modèle les équilibres de Nash existent toujours en mon-trant la convergence de la dynamique de meilleure réponse. Nous étudions ensuite le problème de vérification mentionné ci-dessus, résolvant le problème de l'existence d'un équilibre social, d'un équilibre de Nash ou d'un équilibre parfait en sous-jeux ayant un côut borné.

Dans une deuxième partie, nous étudions les jeux de congestion paramétrés, dans lesquels le nombre de joueurs est un paramètre. Nous nous intéressons à l'évolution des équilibres de Nash en fonction du nombre de joueurs : notre objectif est de calculer efficacement l'ensemble des équilibres de Nash pour un nombre arbitrairement grand de joueurs, à partir des équilibres de Nash pour de petits nombres de joueurs. Nos premiers résultats portent sur les réseaux série-parall'ele, sans les particularités ci-dessus. Nous conjecturons que ces résultats s'étendent à l'ensemble des graphes, ce qui donnerait lieu à un calcul efficace de tous les équilibres de Nash, quel que soit le nombre de joueurs. The most common problem is to study, broadly speaking, how well or how bad a model of NCG is in terms of total cost for all players when each player plays selfishly. We view network congestion games from a formalmethods standpoint, in which we are interested in problem like: given an instance (network and number of players fixed) of a chosen model of NCG and given a specification, does there exist an optimal profile satisfying the specification?

We define a model of network congestion games with two pecularities: first, the players bear congestion effect on their cost for an edge only if they use that edge with other players simultaneously; second, players can choose their path dynamically, at each step of their route, which differs from the classical setting where players choose their path at the beginning. We show that in this model Nash Equilibria always exist by showing convergence of best-response dynamics. Then we study three decision problems on Social optima, Nash Equilibria and Subgame perfect Equilibria, each of which asks whether, given an instance of our model and a bound, there is a corresponding strategy profile with bounded social cost.

In the second part of the thesis, we study parameterized network congestion games, where the number of players is left as a parameter. Our main problem here is to compute Nash Equilibria for instances with many players, from instances with fewer players, instead of computing them from scratch. Here, we started solving the problem for the classical model of NCG, without the above mentioned two pecularities, and with the arena restricted to series-parallel graph. We obtained some preliminary results on this problem, and formulated a conjecture about how to efficiently compute all Nash equilibria for any number of players.

Figure . :

 . Figure . : An arena A for a dynamic NCG

  Figure . : Example of an NE and an SO on arena A 2

  Figure . : Depiction of an SPE σ, explained in Example . : Fig . a represents the outcome, while Fig . b, . c and . d represent outcome of σ when applied to the corresponding con gurations

  .3a; in fact, Fig. . a captures outcome(σ).

  and we define σh 1 (c 1 ) to be the red path shown in Fig. . b, and both σh 2 (c 1 ) and σh 3 (c 1 ) to be the blue path shown on A 2 , shown in the same figure.

  follow the red, blue and blue path respectively as shown in Fig.. c. Finally, for any path ending at c 3 = (v 2 , v 2 , v 5 ), we define σh (c 3 ) = (σ h i (c 3 )) i∈ 3 to follow the red, blue and green path respectively as shown in Fig.. d

Figure . :

 . Figure . : An example where a cycle appears in the abstract weighted graph for an SO

Figure . :

 . Figure . : Depiction of a run of the CONSTRAINED-SO-algorithm on Example .

Figure . :

 . Figure . : An arena on which blind Nash equilibria are sub-optimal.

  18 × 2 + 16 = 52 cost(ρ 3 , ρ 3 , ρ 4 ) = 18 × 2 + 15 = 51 cost(ρ 4 , ρ 4 , ρ 1 ) = 16 × 2 + 14 = 46 cost(ρ 4 , ρ 4 , ρ 2 ) = 16 × 2 + 12 = 44 cost(ρ 4 , ρ 4 , ρ 3 ) = 18 × 2 + 15 = 51

  , and T ⊆ C × N × C ; remember that all players have a strategy realizing cost at most Y in A, n, g . The initial state is (c src , ∞ n ). The set of transitions T is de ned as follows: ((c, b), z, (c , b )) ∈ T if, and only if, there exists (c, w, c ) ∈ T , z = γ • w (where • is dot product), and for all i ∈ n ,

  Figure . : An example of NE with non-credible threats

  For our running example, the game of Figure . a, we have already shown an SPE in Figure . , in Chapter .

Figure . :

 . Figure . : An weak NE but not an NE

  Figure . : Illustration of an NCG with its con guration graph in phases

Lemma . .

 . For any edge e = (c, w, c ) ∈ Z j , the (|V | + 1) th family µ |V | of λ j * -building functions satisfies µ |V | i (e) ≤ |V | × κ, where κ = max e∈E f e (n). Proof. We prove a slightly stronger statement. Let m be the length of the shortest path from c(i) to tgt in A. We show (by induction) that µ m i (e) ≤ m × κ. As m ≤ |V | and by Lemma . , this entails our current lemma. If m = 1, then there is an edge e from c[i] to tgt in A. Let us consider an edge e = (c, w , c ) such that c [j] = c [j] for all j = i, and c [i] = tgt(i). Now if Γ µ m-1 (c) = ∅ for any (c, w, c) ∈ T , then anyway µ m i (e) = -∞, and the result holds. Otherwise, we have Γ µ m-1 (c ) = ∅, and for any

  ne a counter graph as follows: De nition . . With any family of labeling functions µ = µ i i∈ n and configuration c, we associate an infinite-state counter graph C[µ, c] = C , T to capture µ-consistent paths from c: • the set of vertices is C = C × (N ∪ {+∞, -∞}) n • T contains all edges ((d, b), w, (d , b )) such that (d, w, d ) is an edge of M and for all i ∈ n , either b

Figure . :

 . Figure . : Series and Parallel composition of networks

  Now consider two path-strategy profiles m 1 and m 2 as follows:

  Theorem . . In any network G with linear cost functions, a path-strategy profilem = (m π ) π∈PathsG is an NE i ∀π, π ∈ PathsG, m π > 0 =⇒ e∈π\π w e • n e ≤ e∈π \πw e • (n e + 1) ( . )

  e∈π\π w e • n e > e∈π \π w e • n e , otherwise π is not more cost-e ective than π. But, that contradicts ( . ), hence m is an NE.For the opposite direction, suppose a strategy pro le m = (m π ) π∈PathsG is a path NE with Γ( m) = n = (n e ) e∈E , and also suppose towards a contradiction that there are paths π, π ∈ PathsG such that m π > 0 and e∈π\π w e • n e > e∈π \π

  De nition . . A set S ⊆ N |E| is called linear if there is a base vector b ∈ N n and a finite set of period vectorsP = {p 1 , p 2 , . . . p m } such that ∀s ∈ S, ∀i ∈ [m], ∃λ i ∈ N, s = b + i∈ m λ i • p iSuch a linear set S can also be written as L(b; P ) De nition . . A set S ⊆ N |E| is said to be semi-linear if it is a finite union of linear sets.Therefore, a semi-linear set S can be expressed asS = i∈I L(b i ; P i ) where both |I|, |P i | are nite.Now, we show that the set of NE pro les of a pNCG is a semi-linear set.

  Parametric Network congestion games Next, we enrich the grammar by introducing a unary operator Γ which maps N |P| to N |E| , and de nable in (N, +, =): Γ( m = (m π ) π∈P ) := (n e ) e∈E , where n e = e∈π m π This unary operator maps a path pro le to its corresponding edge pro le in the network. We further introduce two formulas which essentially capture the set of path NE and edge NE . PathNE( m = (m π ) π∈P ) := ∀π, π ∈ P, m π > 0 =⇒ e∈π\π w e • Γ( m) e ≤ e∈π \π w e • (Γ( m) e + 1) EdgeNE( n = (n e ) e∈E ) := EdgePro le( n)

e

  ) e∈E 1 of G 1 and similarly for d 2 = (d (2) e ) e∈E 2 of G 2 , there are κ d 1 and κ d 2 such that: ∀π ∈ P 1 , e∈π w e • d (1) e = κ d 1 , and ( . ) ∀π ∈ P 2 , e∈π w e • d (2) e = κ d 2 ( . )

  Moreover, any period vector d = (d e ) e∈E of G can be expressed as ( d 1 = (d e ) e∈E 1 , d 2 = (d e ) e∈E 2 ), simply because E = E 1 E 2 , where d 1 and d 2 are the period vectors of G 1 and G 2 respectively. From the induction hypothesis, we have κ d 1 , κ d 2 ∈ N for these d 1 , d 2 . Therefore, for any π ∈ P, we have e∈π w e • d e = e∈π 1 w e • d e + e∈π 2 w e • d e = κ d 1 + κ d 2 . So, κ = κ d 1 + κ d 2 works! Now we consider G = G 1 G 2 , and a period vector d of G. Slightly abusing the notations, we can say that the set of paths PathsG can be decomposed into two disjoint sets: the set of paths in G 1 , denoted by P 1 and the set of paths in G 2 , denoted by P 2 . For d = (d e ) e∈E , from the induction hypothesis, we have κ 1 and κ 2 such that ∀π ∈ P 1 e∈π w e • d e = κ 1 and ∀π ∈ P 2 e∈π w e • d e = κ 2 . Now we consider two paths π 1 ∈ P 1 and π 2 ∈ P 2 . If we prove that e∈π 1 w e •d e = e∈π 2 w e •d e , we are done. Without loss of generality, suppose towards a contradiction that e∈π 1 w e • d e > e∈π 2 w e • d e , and we denote M = e∈π 1 w e • d e -e∈π 2

  e∈π\π 2 w e • n e ≤ e∈π 2 \π w e • (n e + 1) We denote L = e∈π 2 \π w e • (n e + 1) -e∈π\π 2 w e • n e . By de nition of period vector, for any λ ∈ N, we have e∈π\π 2 w e • (n e + λd e ) ≤ e∈π 2 \π w e • (n e + λd e + 1) We take λ = L M Then, π\π 2 w e • n eπ 2 \π w e • (n e + 1) + λ e∈π w e • d e -e∈π 2 w e • d e = -L + L M • M > 0 =⇒ e∈π\π 2 w e • (n e + λd e ) > e∈π 2 \π w e • (n e + λd e + 1)

Figure . :

 . Figure . : An arena G to show S is a set of covering paths

  Formally, De nition . . For pNCG G, we call a set CovP(G) ⊆ PathsG a set of covering paths of G if for any strategy profile d = (d e ) e∈E ∀π, π ∈ CovP(G) e∈π w e • d e = e∈π w e • d e =⇒ ∀π, π ∈ PathsG e∈π w e • d e = e∈π w e • d e ( . ) Note that, PathsG itself is a set of covering paths for G. But we are looking for a covering set of a speci c size |E| -|V | + 2 for a given G = V, E , and that is what we compute next.

Example . .

 . Consider again the running example here: the game G depicted in Figure . . We take the ordering O on the edges as a ≺ b and c ≺ d. This is applied to In(u) and Out(u) for all u ∈ V . Hence, fst_fwd(s) = fst_bwd(v) = a, and fst_bwd(t) = fst_fwd(v) = c. With these two paths for each vertex v, we nally compute a set of covering paths as shown in Algorithm . Intuitively, for each vertex v with out-degree ≥ 2, and for each outgoing edge in Out(v), say v e -→ u, we consider the path fst_bwd(v) • e • fst_fwd(u), which is a path from s to t, and add it to the set of covering paths. Algorithm Computing a set of covering paths for arena G : Initialize with S = ∅ : for each vertex v with out-degree deg v ≥ 2 do : if v is the source vertex s then : for 0 ≤ j ≤ deg s -1 do %Adding deg s paths : Add e j • fst_fwd(u j ) to S %s e j -→ u j is the j th edge in Out(s) : else : for 1 ≤ j ≤ deg v -1 do %Adding deg v -1-many paths : Add fst_bwd(v) • e j • fst_fwd(u j ) to S %v e j -→ u j is the j th edge in Out(v) : return S Lemma . . For a pNCG G = V, E, s, t , the set S computed in Algorithm is a set of covering paths CovP(G), and it is of size |E| -|V | + 2.

  x a strategy pro le d = (d e ) e∈E , and we denote κ d = e∈π w e • d e = e∈π w e • d e for all π, π ∈ S . Suppose towards a contradiction that ( . ) is not true, i.e, there is a path ρ . . t ∈ PathsG for which e∈ρ w e •d e = κ d . We rst consider e∈ρ w e •d e > κ d

  d e , which is a contradiction, hence proving that such a ρ, for which the cost is not same as that of κ d , cannot exist.As fst_fwd(v) = e • fst_fwd(u), where v e -→ u is the rst edge in Out(v), we have fst_bwd(v).fst_fwd(v) ∈ S for any v ∈ V . Now, base case of the induction is j = 0: we have π 0 = e 0 • fst_fwd(v 1 ). From our previous assumption, we have e∈ρ w e • d e > κ d = e∈π 0 w e • d e .

Figure . :

 . Figure . : In an arbitrary graph, how S m 's and F m 's would have been if Case were true. Here, up to level is shown, curved-arrows denote positive and negative paths with label + andrespectively, and straight-arrows denote edges, S m 's are the set of vertices in the enclosed area, and F m 's are the sum of absolute values in the area enclosed by dotted green lines

  e∈σ w e • f e > 0, e∈σ w e • f e < 0, and e∈σ w e • f e = 0 respectively. An edge is just a path of length 1, hence an edge e is called positive (resp. negative and zero) if f e > 0 (resp. f e < 0 and f e = 0). Because M G • f = 0 implies for all π ∈ CovP(G), m π • f = e∈π w e • f e = 0, in terms of this notions, all paths σ ∈ CovP(G) are zero paths. Moreover, from the de nition of covering paths of a network, in fact, all paths σ ∈ PathsG are zero paths.

  we have, in fact, for any path π ∈ PathsG: e∈π w e • f e = 0 Again, consider the positive path σ + sv from s to v, and let π be the path from s to t, via v such that π = σ + sv • σ for some v σ t. Then, from the above identity, we have e∈π w e • f e = e∈σ + sv w e • f e + e∈σ w e • f e = 0

  e∈π w e • f e = e∈σ + su w e • f e + e∈σ w e • f e = 0.

  x . Suppose d and d are the two period vectors, and c d and c d are the values taken for the parameter respectively. We have M G (c d . d -c d . d ) = 0. Moreover, because M G is invertible, we have d = c d c d d. And this is true for any two period vectors d, d . Now x a period vector d and consider g = gcd e∈E d e . Let us de ne δ = (δ e ) e∈E as δ e = de g ∀e ∈ E. Then, Lemma . . For any period vector d of G, there exists m d ∈ N such that d = m d δ Proof. Consider an arbitrary period vector d . Remember, we have already xed a d from which we de ned δ. Moreover, we had d = c d c d

  For series-parallel graph G, δ = M -1 G 0 c δ is called the shift vector for NE of G.

  e∈E 2 w e • n e ≤ e∈E 1 w e • (n e + 1) Then, f e,e (M ) = max e ∈E 1 w e f e,e (M ) min ê∈E 2Therefore, for all pair of edges e, e in a series-parallel network f e,e exists, hence BoundN E(e, M ) is a nite set.Hence, we can rewrite ( . )N G = e∈E L(BoundN E(e, δ e ) , δ) ( . )From this, we can nally have a nite representation of NE(k) as follows. We denote κ δ to be the number of players in δ, then we take m = k κ δ. Then, among k players, for m • κ δ players, we consider δ. And because k -m • κ δ < κ δ , for any edge NE n with k -m • κ δ players, there has to be at least one e ∈ E such that n e < δ e , i.e, n ∈ BoundN E(e, δ e ) .

  Title: A Verification Viewpoint to Network Congestion Games Keywords: Congestion games, Nash Equilibria, Subgame perfect Equilibria, Parametrized congestion games, Algorithmic game theory Abstract: Congestion games are a well-studied area of research, and Network congestion games (NCG) model the problem of congestion in flow networks.

  [ ] et Correa et al. [ ] ont étudié le PoA pour les jeux de congestion non atomiques avec demandes stochastiques. Cominetti et al. [ ] ont étudié le cadre atomique des jeux de congestion de Bernoulli dans lesquels chaque joueur participe au ix Résumé de la thèse jeu avec une probabilité indépendante, et ont trouvé que la limite supérieure de la PoA pour les modèles déterministes tient toujours. Cominetti et al. [ ] a trouvé que de tels jeux de congestion de Bernoulli convergent vers un ensemble de jeux de Poisson au sens de Myerson[ ], lorsque les probabilités de participation des joueurs tendent vers zéro. Wang et al. [ ] étudie un autre modèle pour les jeux de congestion de réseaux atomiques avec des demandes stochastiques, dans lequel au lieu des probabilités de participation individuelles, ils considèrent les distributions du nombre de joueurs comme une connaissance commune, ce qui suit le cadre de l'incertitude de la population proposé par Myerson[ ]. L'incertitude de la demande a également été considérée dans d'autres jeux tels que les jeux d'allocation de ressources par Ashlagi et al. [ ].

  Wang et al. [ ] and Correa et al. [ ] studied the PoA for non-atomic xvi congestion games with stochastic demands. Cominetti et al. [ ] studied the atomic setting of Bernoulli congestion games in which each player participates in the game with an independent probability, and found that the upper bound of the PoA for deterministic models still hold. Cominetti et al. [ ] found such Bernoulli congestion games converge to a set of Poisson games in the sense of Myerson[ ], when players' participating probabilities tend to zero. Wang et al.

	[ ] studies another model for atomic network congestion games with stochastic demands, in
	which instead of individual participation probabilities, they consider distributions of numbers of
	players as common knowledge, which follows the framework of population uncertainty proposed
	by Myerson[ ]. Demand uncertainty has also been considered in other games such as resource
	allocation games by Ashlagi et al. [ ].

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .An arena is a weighted graphA = V, E, src, tgt , where V is the set of vertices, E ⊆ V × F × Vis a set of transitions labeled with non-decreasing piecewise a ne cost functions, and src, tgt ⊆ V are the sets of source and target vertices. In our discussion, we consider that each vertex except possibly the vertices of tgt has at least one outgoing edge, and every target vertex t ∈ tgt is reachable from every vertex v ∈ V .

			Contents
			II N	C
			F
	C L		. De nitions N E F P	P	N
	R I In the rst part of this thesis, we consider dynamic Network Congestion Games (dynamic NCG) . Characterization of NE Pro les: Path and Edge Representations . . . . . . . . . Set of NE Pro les as a Semi-linear Set . . . . . . . . . . . . . . . . . . . . . . . Period vectors of edge NE pro les . . . . . . . . . . . . . . . . . . . . . . . . . . A System of Equations for Period Vectors . . . . . . . . . . . . . . . . Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Basis for the Set of all Edge NE pro les . . . . . . . . . . . . . . . . . . An arena A for a dynamic NCG . . . . . . . . . . . . . . . . . . . . . . . . . Example of an NE and an SO on arena A 2 . . . . . . . . . . . . . . . . . . . . with a xed number of players. And, in the second part of this thesis, we consider Network conges-Depiction of an SPE σ, explained in Example . : Fig . a represents the out-tion games (NCG) with number of players as a parameter. Here, in this chapter, we introduce the come, while Fig . b, . c and . d represent outcome of σ when applied to the model for the rst part only, and for the second part we have a respective chapter for preliminaries, corresponding con gurations . . . . . . . . . . . . . . . . . . . . . . . . . . de nitions etc.
	. An example where a cycle appears in the abstract weighted graph for an SO . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Let F be a family of non-decreasing functions from N to N, which are piecewise-a ne, with . I N C . Depiction of a run of the CONSTRAINED-SO-algorithm on Example . . . . . . . . The reduction of Theorem . . The gure shows the edges involving states P nitely many pieces. We assume that each f ∈ F is represented by the endpoints of the intervals, I and the coe cients, all encoded in binary. P . Game Arena: Network with Cost Functions . . . . . . . . . . . . . . . . . . . Dynamic Congestion Games Played on a Network . . . . . . . . . . . . . . . . Concurrent Game Semantics For Dynamic NCG . . . . . . . . . . . . . . . . . Optimizing strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . s i , a i,1 , a i,2 . The full graph is obtained by reproducing the shown construction B for all i ∈ m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . An arena on which blind Nash equilibria are sub-optimal. . . . . . . . . . . . N G A N C F
		.	. . An example of NE with non-credible threats . . . . . . . . . . . . . . . . . . Social Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
		.	. . An weak NE but not an NE . . . . . . . . . . . . . . . . . . . . . . . . . . . Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	. .	Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Illustration of an NCG with its con guration graph in phases . . . . . . . . .
	S	.	O Series and Parallel composition of networks . . . . . . . . . . . . . . . . . . .
	. . D . . N . De nition . (Network Congestion Game). A network congestion game (NCG) is a triplet Solving the CONSTRAINED-SO problem . . . . . . . . . . . . . . . . . . . . . . . . C G P N An arena G to show S is a set of covering paths . . . . . . . . . . . . . . . . . Abstract Weighted graphs: Solving CONSTRAINED-SO for Symmetric NCG . . src-abstract Weighted Graphs: Solving CONSTRAINED-SO for NCG . . . Complexity Lower Bound for CONSTRAINED-SO . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (s,t)∈src×tgt E In an arbitrary graph, how S m 's and F m 's would have been if Case were true. Here, up to level is shown, curved-arrows denote positive and negative paths G = A, n, g where A is an arena as above, n ∈ N is the number of players, and g : src × tgt → with label + and -respectively, and straight-arrows denote edges, S m 's are the {0, . . . , n} maps each source-target vertex pair (s, t) to a number k ≤ n, which means k players set of vertices in the enclosed area, and F m 's are the sum of absolute values in the have s and t as their source and target vertices respectively. area enclosed by dotted green lines . . . . . . . . . . . . . . . . . . . . . . . Naturally, it is required that, g(s, t) = n.
		.	Existence of Nash Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . .
			. .	Existence of blind Nash Equilibria in dynamic NCG . . . . . . . . . .
		.	Constrained NE Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . .
		.	Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	S		P	E
		.	On Existence of SPE in Dynamic NCG . . . . . . . . . . . . . . . . . . . . .
		.	Constrained SPE problem . . . . . . . . . . . . . . . . . . . . . . . . . . . .
			. .	Characterization of the Outcomes of All SPE . . . . . . . . . . . . .
			. .	Using the Characterization for CONSTRAINED-SPE . . . . . . . . . . . .
		.	Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
			xviii xx		xix xxi

  As an alternative proof to existence of blind NE, we could have bounded the length of outcomes of blind NE as follows: all players have a strategy realizing cost at most |V | • κ, where κ = max e∈E f e (n), since the shortest path from src(i) to tgt(i) has length at most |V |, and the cost for a player at each step along edge e is at most κ. It follows that no path along which the cost for some player is larger than |V | • κ can be the outcome of a blind NE. As a consequence, if a dynamic NCG has a blind NE, then it has one of length at most |V | • κ • |V | n (by removing zero-cycles). Using this bound, we can transform dynamic NCG into classical congestion games, in which blind NE always exist[ , ].

	Nash Equilibria
	Remark . .

  is the only vertex with no outgoing edge ] Example . . Let us consider the example in Figure.. Here, the set of all paths PathsG = {ac, bc, ad, bd}, where the set computed by applying algorithm , S = {ac, ad, bc}. In fact, this is a minimal set satisfying ( . ), we consider the following sets S -ac , S -ad and S -bc , where S -π =

	= |E| -(|V | -1) + 1 = |E| -|V | + 2

S \ {π} for π ∈ S. Now, we will show for each of these sets there exists a x = (x e ) e∈E for which

∀π 1 , π 2 ∈ S -π e∈π 1 w e x e =

e∈π 2 w e x e holds but ∀π 1 , π 2 ∈ P A e∈π 1 w e x e = e∈π 2 w e x e doesn't hold. Hence, none of them can be a set of covering paths, proving the minimality of S.