Title: Solving Endgames in Large Imperfect-Information Games such as Poker Author: Bc. Karel Ha Department: Department of Applied Mathematics Supervisor: doc. Mgr. Milan Hladík, Ph.D., Department of Applied Mathematics Abstract: Endgames have a distinctive role for players. At the late stage of games, many aspects are finally clearly defined, deeming exhaustive analysis tractable. Specialised endgame handling is rewarding for games with perfect information (e.g., Chess databases pre-computed for entire classes of endings, or dividing Go board into separate independent subgames). An appealing idea would be to extend this approach to imperfect-information games such as the famous Poker: play the early parts of the game, and once the subgame becomes feasible, calculate an ending solution. However, the problem is much more complex for imperfect information. Subgames need to be generalized to account for information sets. Unfortunately, such a generalization cannot be solved straightaway, as it does not generally preserve optimality. As a consequence, we may end up with a far more exploitable strategy. There are currently three techniques to deal with this challenge: (a) disregard the problem entirely; (b) use a decomposition technique, which sadly retains only the same quality; (c) or formalize improvements of...

Un agent est un élément qui décide une action. Par ce formalisme très général on peut aussi bien désigner deux enfants jouant à pierre-papier-ciseaux, des êtres humains choisissant des produits sur un marché, un logiciel de routage calculant un plus court chemin sur Internet pour transporter des informations sur des routes numériques encombrées, qu’une enchère combinatoire automatique pour vendre des liens commerciaux et rapportant des milliards à google. Les chercheurs en théorie de la décision algorithmique et en théorie des jeux algorithmique – des mathématiciens et informaticiens – aiment à penser que ces exemples concrets peuvent être modélisés au moyen de systèmes décisionnels rationnels, aussi complexe la réalité soit-elle. Les systèmes décisionnels modernes trouvent leur complexité dans plusieurs dimensions. D’une part, les préférences d’un agent peuvent être complexes à représenter avec de simples nombres réels, alors que de multiples objectifs conflictuels interviennent dans chaque décision. D’une autre part, les interactions entre agents font que les récompenses de chacun dépendent des actions de tous, rendant difficile la prédiction des actions individualistes résultantes. L’objet de cette thèse en théorie algorithmique des systèmes décisionnels interactifs (jeux) est de poursuivre des efforts de recherche menés sur ces deux sources de complexité, et in fine, de considérer les deux complexités dans un même modèle. / An agent is an entity that decides an action. By using this abstraction, it is possible to model two children playing rock-paper-scissors, a software computing a shortest path on the internet for packet-routing on congest numerical networks, as well as an automatic combinatorial auction that sells commercial links in order to make google earn billions. The researchers in algorithmic decision theory and algorithmic game theory (mathematicians and computer scientists) like to think that these real-life examples can be modelled by mean of agents in an interaction decision system, no matter how complex is reality. The modern interactive decision systems find their complexity in multiple aspects. Firstly, the preferences of an agent can be complex to model with real numbers when there are multiple conflicting objectives resulting from every decision. Secondly, the interactions between agents are such that the payoff of every individual depends of the actions of all, making difficult the prediction of the resulting action-profile. This thesis aims at pursuing research efforts lead on these two sources of complexity, in order to consider ultimately both aspects in the same model.

No description available.

No description available.

Untersuchungsgegenstand dieser Arbeit ist ein spieltheoretisches Modell für die dezentrale Erzeugung von Netzwerken durch eigennützige Agenten. Diese Akteure verfolgen das Ziel, ein zusammenhängendes Netzwerk aufzubauen, welches ihre individuelle Verbindungsqualität maximiert. Direktverbindungen im Netzwerk haben Kosten, weshalb die Agenten ihre Ausgaben für das Erstellen von Direktverbindungen und die damit erzielten Kommunikationskosten ausbalancieren müssen. Dieses Modell wurde vor einem Jahrzehnt von Fabrikant, Luthra, Maneva, Papadimitriou und Shenker eingeführt, um reale Netzwerke, welche aus der Interaktion von eigenützigen Parteien entstanden sind, zu verstehen. Zu solchen Netzwerken zählen das Internet und auch soziale Netzwerke. Die vorliegende Arbeit trägt zu diesem Forschungsvorhaben bei, indem die sogenannten Network Creation Games aus drei Perspektiven betrachtet werden. Die erste Sichtweise ist die Approximationsperspektive. Es wird untersucht, welche Netzwerke von sehr einfachen, in ihrer Berechnungsstärke eingeschränkten Agenten erzeugt werden und wie diese im Vergleich mit Netzwerken von Agenten, die beliebige Berechnungsstärke haben, abschneiden. Als zweite Sichtweise wird die Dynamikperspektive betrachtet. Dazu werden sequentielle Versionen des Modells definiert und anhand dieser wird explizit der Prozess der Netzwerkerzeugung untersucht. Die Hauptfragestellung ist, ob unter der natürlichen Annahme, dass Agenten stets ihre Situation verbessern wollen, der Prozess zu einem Gleichgewicht konvergiert und, falls dem so ist, wie dieser Prozess beschleunigt werden kann. Die Abhandlung wird mit der dritten Sichtweise, der Strukturperspektive, abgerundet. Es werden eine Vielfalt neuer Struktureigenschaften für verschiedene Gleichgewichtskonzepte bewiesen und neue Werkzeuge, die bei der Analyse von Gleichgewichtsnetzwerken mit hohen Direktverbindungskosten hilfreich sind, vorgestellt. / The subject of study in this thesis is a game-theoretic model for decentralized network creation by selfish agents. These agents aim to create a connected network among themselves which maximizes their individual connection quality. Links in the network are costly and therefore agents try to find a trade-off between their cost spent on creating edges and their cost incurred by communicating within the network. This model was proposed a decade ago by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker with the goal of understanding real networks which emerge from the interaction of selfish entities without explicit central coordination, e.g. the Internet or social networks. We contribute to this research endeavor in many ways by considering these so-called Network Creation Games from three perspectives. Our first point of view on these games is the approximation perspective. We analyze which networks are created by very simple computationally bounded selfish agents and how these networks compare to networks built by agents having unlimited computational resources. The second point of view is the dynamics perspective. We turn the model into a sequential version and focus on the process of selfish network creation. For this, we investigate whether natural dynamics like best response dynamics are guaranteed to converge to an equilibrium of the game and if so, how this convergence process may be sped up. We complete the treatment of Network Creation Games with our third point of view: the structure perspective. We provide new structural insights for several equilibrium concepts and introduce new tools which shed light on the structure of equilibrium networks for high edge-cost.

Dans les chaînes d’approvisionnement, les producteurs font souvent appel à des entreprises de transport pour livrer leurs marchandises. Cela peut entraîner une concurrence entre les transporteurs qui cherchent à maximiser leurs revenus individuels en desservant un produc- teur. Dans ce travail, nous considérons de telles situations où aucun transporteur ne peut garantir la livraison de la source à la destination en raison de son activité dans une région restreinte (par exemple, une province) ou de la flotte de transport disponible (par exemple, uniquement le transport aérien), pour ne citer que quelques exemples. La concurrence est donc liée à l’expansion de la capacité de transport des transporteurs. Le problème décrit ci-dessus motive l’étude du jeu d’expansion de réseau multi-agent joué sur un réseau appartenant à de multiples transporteurs qui choisissent la capacité de leurs arcs. Simultanément, un client cherche à maximiser le flux qui passe par le réseau en décidant de la politique de partage qui récompense chacun des transporteurs. Le but est de déterminer un équilibre de Nash pour le jeu, en d’autres termes, la strategie d’extension de capacité et de partage la plus rationnelle pour les transporteurs et le client, respectivement. Nous rappelons la formulation basée sur les arcs proposée dans la littérature, dont la solution est l’équilibre de Nash avec le plus grand flux, et nous identifions ses limites. Ensuite, nous formalisons le concept de chemin profitable croissant et nous montrons son utilisation pour établir les conditions nécessaires et suffisantes pour qu’un vecteur de stratégies soit un équilibre de Nash. Ceci nous conduit à la nouvelle formulation basée sur le chemin. Enfin, nous proposons un renforcement du modèle basé sur les arcs et une formulation hybride arc- chemin. Nos résultats expérimentaux soutiennent la valeur des nouvelles inégalités valides obtenues à partir de notre caractérisation des équilibres de Nash avec des chemins croissants rentables. Nous concluons ce travail avec les futures directions de recherche pavées par les contributions de cette thèse. / In supply chains, manufacturers often use transportation companies to deliver their goods. This can lead to competition among carriers seeking to maximize their individual revenues by serving a manufacturer. In this work, we consider such situations where no single carrier can guarantee delivery from source to destination due to its operation in a restricted region (e.g., a province) or the available transportation fleet (e.g., only air transportation), to name a few examples. Therefore, competition is linked to the expansion of transportation capacity by carriers. The problem described above motivates the study of the multi-agent network expansion game played over a network owned by multiple transporters who choose their arcs’ capacity. Simultaneously, a customer seeks to maximize the flow that goes through the network by deciding the sharing policy rewarding each of the transporters. The goal is to determine a Nash equilibrium for the game, in simple words, the most rational capacity expansion and sharing policy for the transporters and the customer, respectively. We recap the arc-based formulation proposed in literature, whose solution is the Nash equilibirum with the largest flow, and we identify its limitations. Then, we formalize the concept of profitable increasing path and we show its use to establish necessary and sufficient conditions for a vector of strategies to be a Nash equilibrium. This lead us to the first path-based formulation. Finally, we propose a strengthening for the arc-based model and a hybrid arc-path formulation. Our experimental results support the value of the new valid inequalities obtained from our characterization of Nash equilibria with profitable increasing paths. We conclude this work with the future research directions paved by the contributions of this thesis.