{'fraction_non_alphanumeric': 0.0174901617839965, 'fraction_numerical': 0.0, 'mean_word_length': 5.426966292134831, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the complexity of equilibria in games with succinct representation

Algorithmic game theory studies computational and algorithmic questions arising from the behavior of players in strategic situations. The computational aspects of game theory became subject to closer scrutiny in the last two decades. One reason for this is certainly the advent of large scale communication networks – most prominently the Internet. Modern technology allows to monitor, evaluate, and influence the behavior of interacting agents in large systems. One may think of many (future) applications including distribution of goods and services in auctions, allocation of resources, routing of data packages, or regulation of vehicle traffic. One of the main contributions of game theory is the ability to predict how these games will be played. The most commonly used solution concepts are equilibrium concepts that describe which strategies will be adopted by players. One of the central challenges in algorithmic game theory is to characterize the computational complexity of such equilibria. Results in this direction yield important indicators if game-theoretic solution concepts are plausible outcomes of competitive environments in practice. Furthermore, computational complexity is of practical importance if one desires to predict or influence the outcome of a strategic situation in a large-scale environment. In this work, we answer fundamental complexity theoretic questions about several equilibrium concepts. We investigate the complexity of problems regarding the existence, recognition, and computation of Nash equilibria, strong equilibria, and sink equilibria. Probably the most prominent solution concept in (non-cooperative) game theory is the Nash equilibrium – a strategy profile, from which no player can profitably unilaterally deviate. A refinement of Nash equilibria is the concept of strong equilibrium – a strategy profile, from which no coalition wants to jointly deviate. We also study the dynamics that emerge when players iteratively play best responses. That is, in each time step one of the players chooses his optimal strategy given that strategies of the other players are fixed. We identify games in which this process converges to an equilibrium and study the duration of