Congestion games model scenarios where agents compete for shared resources, with the catch that sharing makes the resource less efficient. A classical example are road networks: The more cars share the same road, the slower traffic advances. One of the main goals in network design is the minimization of overall travel time. However, without incentive, participants of the network tend to less favorable equilibria. We consider an approach to create incentives based on the levy of tolls. In the tollbooth problem, we demand an additional toll for the use of roads to minimize the total travel time. The approach is well studied, however some weaknesses in the standard solutions give rise to variants of the problem. The variant in focus of this thesis is the minimum tollbooth problem, where we additionally minimize the number of necessary tollbooths. We consider the problem in two different settings: Games with infinite, and games with a finite number of participants. First, if the number of participants is large enough, we can interpret them as a continuous flow. We introduce and test a new probabilistic algorithm for the minimum tollbooth problem in this setting. The algorithm does not rely on additional parameters. Therefore, no tuning of such parameters are necessary, making the algorithm easy to deploy. We theoretically analyze the expected runtime of the algorithm and compare the theoretical results to the outcome of experiments on randomly generated instances. In the second scenario, the number of participants is low. Therefore, each participant can have a significant effect on congestion. We show that solving the minimum tollbooth problem in this setting is W[2]-hard, parameterized with the number of available tollbooths. The result transfers to the complexity of computing a social optimum. Nonetheless, under the restriction of instances on series-parallel graphs, we introduce both a polynomial-time algorithm for finding a social optimum and a polynomial-time algorithm for solving the minimum tollbooth problem for a given state. Following a separate aspect of congestion games to the ones mentioned above, we generalize congestion games through the introduction of uncertainty in the existence of resources. We prove that the existence of pure Nash equilibria is guaranteed for general strategy definitions. However, we demonstrate that even the fundamental task of computing the cost of a player is complete for a generalization of #P. We generalize the complexity class PLS, which is the appropriate class for general congestion games, by allowing access to #P functions when calculating the cost of a solution. We demonstrate completeness for this new class PLS^{#P} of finding a pure Nash equilibrium for a simple but natural definition of a strategy. We consider two further definitions of strategies in this setting. First, we describe the strategy through a Boolean circuit. We determine a condition under which finding a pure Nash equilibrium is possible in polynomial time. In particular, symmetric network congestion games fulfill this condition. Second, the players state a list of possible strategies, ordered by preference. The player then chooses the first element of the list without failing resources. We demonstrate that finding pure Nash equilibria remains hard for PLS^{#P}. However, the completeness could only be shown for priority lists of constant length. We observe, however, that access to #P allows finding a strategy that is above average, even if the neighborhood of a solution is exponentially large. This motivates the introduction of an average Nash equilibrium. We show that finding an average Nash equilibrium under list strategies is PLS^{#P}-complete., Mithilfe von Congestion Spielen können Situationen modelliert werden, in denen sich mehrere Agenten eine Menge von Ressourcen teilen müssen. Wichtig ist dabei insbesondere, dass die Benutzung einer Ressource teurer wird je mehr Agenten diese Ressource wählen. Ein typisches Beispiel findet sich im Straßenverkehr. Je mehr Fahrzeuge die gleiche Straße verwenden, desto langsamer geht der Verkehr auf dieser Straße voran. Wir betrachten einen Ansatz, indem es durch die Platzierung von Mautstationenen ermöglicht wird die Entscheidungen der Agenten zu beeinflussen. Das Ziel im Tollbooth Problem ist es nun, dass das reine Nash Gleichgewicht des Systems mit einem Zustand übereinstimmt, in dem, im Beispiel des Straßennetzwerks, die Summe aller Fahrzeiten minimiert werden. Der typische Ansatz zur Lösung dieses Problems birgt jedoch Fallstricke, die die Einführung mehrerer Varianten motiviert. Ein Fokus dieser Arbeit ist das Minimum Tollbooth Problem, bei dem zusätzlich die Anzahl der benötigten Mautstationen minimiert werden soll. Dabei unterscheiden wir zwei Szenarien: Spiele mit unendlicher und endlicher Spielerzahl. Ist die Spielerzahl unendlich kann sie vereinfacht als Fluss aufgefasst werden. Wir führen einen neuen probabilistischen Algorithmus ein der das Minimum Tollbooth Problem in diesem Szenario löst. Er stellt sich unter anderem dadurch heraus, dass für seine Verwendung keine Parameter gesetzt werden müssen, was die Einsetzbarkeit verbessert. Wir analysieren theoretisch die erwartete Laufzeit des Verfahrens, und vergleichen diese mit Resultaten aus Experimenten aus zufällig generierten Instanzen. Ist die Zahl der Spieler gering ist müssen wir annehmen, dass jeder Spieler einen nicht zu vernachlässigen Effekt auf die Kosten einer Ressource hat. Wir zeigen, dass das Minimum Tollbooth Problem in diesem Szenario W[2]-schwer ist, parametrisiert mit der Anzahl der verfügbaren Mautstationen. Dieses Ergebnis überträgt sich direkt auf die Komplexität des Berechnens eines sozialen Optimums. Eingeschränkt auf Spiele auf serien-parallelen Graphen beschreiben zwei polynomialzeit Algorithmen: Einer ermöglicht die Berechnung eines sozialen Optimums, der andere löst das Minimum Tollbooth Problems mit einem vorgegebenen Zustand. In einem zu den obigen Themen unabhängigen Aspekt führen wir ein, dass Ressourcen mit einer gegebenen Wahrscheinlichkeit ausfallen können. Wir weisen nach, dass reine Nash Gleichgewichte in dieser verallgemeinerung von Congestion Spielen garantiert existieren, selbst für allgemeinere Definitionen von Strategien. Wir stellen allerdings fest, dass selbst die grundlegende Operation des Berechnens der Kosten eines Spielers nun vollständig ist für eine Verallgemeinerung von #P. Um die Komplexität des Findens eines reinen Nash Gleichgewichtes zu analysieren führen wir anschließend die Komplexitätsklasse PLS^{#P} ein. Diese baut auf der Klasse PLS auf, welche geeignet ist um das Finden eines reinen Nash Gleichgewichts in klassischen Congestion Spielen zu beschreiben. Im Gegensatz zu PLS ist in PLS^{#P} der Zugriff auf Funktionen in #P in der Berechnung der Kosten einer Lösung erlaubt. Mithilfe dieser neuen Klasse kann nachgewiesen werden, dass das Finden eines reinen NashgleichgewichtsPLS^{#P}-vollständig ist, für eine einfache aber natürliche Definition einer Strategie. Im gleichen Szenario betrachten wir alternative Strategiedefinitionen. Zunächst können die Spieler ihre Strategie als einen Booleschen Schaltkreis darstellen. In dieser Darstellung ist es in Spezialfällen möglich ein reines Nashgleichgewicht in polynomieller Zeit zu bestimmen. Ein solcher Spezialfall sind die symmetrischen Netzwerk Congestion Spiele. Als zweite Variante stellen die Spieler ihre Strategie als Liste von Mengen von Ressourcen dar, welche nach Präferenz sortiert ist. Es wird dann die erste Menge ausgewählt, in der keine Ressource versagt. In diesem Modell weisen wir wieder PLS^{#P}-schwere nach, Vollständigkeit zeigen wir jedoch nur, falls die Längen der Listen durch gegebene Konstanten beschränkt sind. Weiterhin beobachten wir, dass es der Zugriff auf #P-Funktionen ermöglicht eine überdurchschnittliche Strategie zu bestimmen. Basierend auf dieser Beobachtung führen wir das average Nash Gleichgewicht ein und zeigen, dass das Finden eines solchen Gleichgewichts mit Listenstrategien ohne Längeneinschränkung vollständig für PLS^{#P} ist.