game-theory   1242
Solution concept - Wikipedia
In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

Many solution concepts, for many games, will result in more than one solution. This puts any one of the solutions in doubt, so a game theorist may apply a refinement to narrow down the solutions. Each successive solution concept presented in the following improves on its predecessor by eliminating implausible equilibria in richer games.

nice diagram
concept  conceptual-vocab  list  wiki  reference  acm  game-theory  inference  equilibrium  extrema  reduction  sub-super
27 days ago by nhaliday
A final game with Elwyn Berlekamp — Numberphile
The legendary Elwyn Berlekamp died on April 9, 2019. In a final filming session with Numberphile, the games expert taught us how to play Amazons.
games  game-theory  rather-interesting  planning  nudge-targets
6 weeks ago by Vaguery
ON THE GEOMETRY OF NASH EQUILIBRIA AND CORRELATED EQUILIBRIA
Abstract: It is well known that the set of correlated equilibrium distributions of an n-player noncooperative game is a convex polytope that includes all the Nash equilibrium distributions. We demonstrate an elementary yet surprising result: the Nash equilibria all lie on the boundary of the polytope.
pdf  nibble  papers  ORFE  game-theory  optimization  geometry  dimensionality  linear-algebra  equilibrium  structure  differential  correlation  iidness  acm  linear-programming  spatial  characterization  levers
6 weeks ago by nhaliday
[1809.04881] The Zeckendorf Game
Zeckendorf proved that every positive integer n can be written uniquely as the sum of non-adjacent Fibonacci numbers. We use this to create a two-player game. Given a fixed integer n and an initial decomposition of n=nF1, the two players alternate by using moves related to the recurrence relation Fn+1=Fn+Fn−1, and whoever moves last wins. The game always terminates in the Zeckendorf decomposition, though depending on the choice of moves the length of the game and the winner can vary. We find upper and lower bounds on the number of moves possible. The upper bound is on the order of nlogn, and the lower bound is sharp at n−Z(n) moves, where Z(n) is the number of terms in the Zeckendorf decomposition of n. Notably, Player 2 has the winning strategy for all n>2; interestingly, however, the proof is non-constructive.
number-theory  game-theory  rather-interesting  nudge-targets  consider:feature-discovery
7 weeks ago by Vaguery
[1804.00947] The Transactional Conflict Problem
The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item.
While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem.
Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely "requestor wins" and "requestor aborts" implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems.
We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms.
Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput.
We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures.
concurrency  distributed-processing  constraint-satisfaction  asynchronous-dynamics  heuristics  game-theory  mechanism-design  to-simulate  consider:genetic-programming  consider:performance-measures  consider:feature-discovery
8 weeks ago by Vaguery
[1903.01373] α-Rank: Multi-Agent Evaluation by Evolution
We introduce {\alpha}-Rank, a principled evolutionary dynamics methodology for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous- and discrete-time evolutionary dynamical systems applied to empirical games, and scales tractably in the number of agents, the type of interactions, and the type of empirical games (symmetric and asymmetric). Current models are fundamentally limited in one or more of these dimensions and are not guaranteed to converge to the desired game-theoretic solution concept (typically the Nash equilibrium). {\alpha}-Rank provides a ranking over the set of agents under evaluation and provides insights into their strengths, weaknesses, and long-term dynamics. This is a consequence of the links we establish to the MCC solution concept when the underlying evolutionary model's ranking-intensity parameter, {\alpha}, is chosen to be large, which exactly forms the basis of {\alpha}-Rank. In contrast to the Nash equilibrium, which is a static concept based on fixed points, MCCs are a dynamical solution concept based on the Markov chain formalism, Conley's Fundamental Theorem of Dynamical Systems, and the core ingredients of dynamical systems: fixed points, recurrent sets, periodic orbits, and limit cycles. {\alpha}-Rank runs in polynomial time with respect to the total number of pure strategy profiles, whereas computing a Nash equilibrium for a general-sum game is known to be intractable. We introduce proofs that not only provide a unifying perspective of existing continuous- and discrete-time evolutionary evaluation models, but also reveal the formal underpinnings of the {\alpha}-Rank methodology. We empirically validate the method in several domains including AlphaGo, AlphaZero, MuJoCo Soccer, and Poker.
collective-behavior  performance-measure  rather-interesting  teams  game-theory  credit-assignment  algorithms  machine-learning  to-understand  artificial-life
8 weeks ago by Vaguery
[1707.01231] Random Matching under Priorities: Stability and No Envy Concepts
We consider stability concepts for random matchings where agents have preferences over objects and objects have priorities for the agents. When matchings are deterministic, the standard stability concept also captures the fairness property of no (justified) envy. When matchings can be random, there are a number of natural stability / fairness concepts that coincide with stability / no envy whenever matchings are deterministic. We formalize known stability concepts for random matchings for a general setting that allows weak preferences and weak priorities, unacceptability, and an unequal number of agents and objects. We then present a clear taxonomy of the stability concepts and identify logical relations between them. Furthermore, we provide no envy / claims interpretations for some of the stability concepts that are based on a consumption process interpretation of random matchings. Finally, we present a transformation from the most general setting to the most restricted setting, and show how almost all our stability concepts are preserved by that transformation.
assignment-problems  mechanism-design  game-theory  collective-behavior  operations-research  algorithms  heuristics  to-explain  to-write-about  to-simulate
12 weeks ago by Vaguery
[1705.10239] Fair Division of a Graph
We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. This framework captures, e.g., fair allocation of land plots, where the graph describes the accessibility relation among the plots. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee. While finding good allocations according to these solution concepts is computationally hard in general, we design efficient algorithms for special cases where the underlying graph has simple structure, and/or the number of agents -or, less restrictively, the number of agent types- is small. In particular, despite non-existence results in the general case, we prove that for acyclic graphs a maximin share allocation always exists and can be found efficiently.
assignment-problems  fairness  operations-research  planning  collective-behavior  cake-cutting  game-theory  constraint-satisfaction  rather-interesting  variant-problems  mathematical-recreations  to-write-about  to-simulate
12 weeks ago by Vaguery
[1808.01906] The Fluid Mechanics of Liquid Democracy
Liquid democracy is the principle of making collective decisions by letting agents transitively delegate their votes. Despite its significant appeal, it has become apparent that a weakness of liquid democracy is that a small subset of agents may gain massive influence. To address this, we propose to change the current practice by allowing agents to specify multiple delegation options instead of just one. Much like in nature, where --- fluid mechanics teaches us --- liquid maintains an equal level in connected vessels, so do we seek to control the flow of votes in a way that balances influence as much as possible. Specifically, we analyze the problem of choosing delegations to approximately minimize the maximum number of votes entrusted to any agent, by drawing connections to the literature on confluent flow. We also introduce a random graph model for liquid democracy, and use it to demonstrate the benefits of our approach both theoretically and empirically.
mechanism-design  game-theory  collective-behavior  algorithms  planning  voting  to-understand  to-write-about  to-simulate
12 weeks ago by Vaguery
[1604.03655] A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is nnnnnn. We additionally show that even if we do not run our protocol to completion, it can find in at most n3(n2)n queries a partial allocation of the cake that achieves proportionality (each agent gets at least 1/n of the value of the whole cake) and envy-freeness. Finally we show that an envy-free partial allocation can be computed in at most n3(n2)n queries such that each agent gets a connected piece that gives the agent at least 1/(3n) of the value of the whole cake.
cake-cutting  assignment-problems  mechanism-design  algorithms  rather-complicated  to-understand  consider:looking-to-see  to-simulate  computational-complexity  game-theory
12 weeks ago by Vaguery
[1508.05143] A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents
We consider the well-studied cake cutting problem in which the goal is to identify a fair allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem for the last fifty years to obtain a bounded envy-free protocol for more than three agents. We propose a discrete and bounded envy-free protocol for four agents.
game-theory  cake-cutting  assignment-problems  algorithms  rather-interesting  to-write-about  consider:looking-to-see  nudge-targets  mechanism-design  heuristics  performance-measure
12 weeks ago by Vaguery
[1312.6546] Fair assignment of indivisible objects under ordinal preferences
We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stochastic dominance relation between fractional or randomized allocations to systematically define varying notions of proportionality and envy-freeness for discrete assignments. The computational complexity of checking whether a fair assignment exists is studied for these fairness notions. We also characterize the conditions under which a fair assignment is guaranteed to exist. For a number of fairness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists. Our algorithmic results also extend to the case of unequal entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open question posed by Bouveret, Endriss, and Lang (ECAI 2010). We also propose fairness concepts that always suggest a non-empty set of assignments with meaningful fairness properties. Among these concepts, optimal proportionality and optimal weak proportionality appear to be desirable fairness concepts.
assignment-problems  operations-research  collective-behavior  game-theory  algorithms  heuristics  voting  planning  mathematical-programming  to-write-about  to-simulate  consider:looking-to-see  mechanism-design  define-your-terms
12 weeks ago by Vaguery
[1501.06626] Manipulating the Probabilistic Serial Rule
The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its superior fairness and welfare properties. However, PS is not immune to manipulative behaviour by the agents. We initiate the study of the computational complexity of an agent manipulating the PS rule. We show that computing an expected utility better response is NP- hard. On the other hand, we present a polynomial-time algorithm to compute a lexicographic best response. For the case of two agents, we show that even an expected utility best response can be computed in polynomial time. Our result for the case of two agents relies on an interesting connection with sequential allocation of discrete objects.
assignment-problems  voting  rostering  operations-research  game-theory  collective-behavior  to-simulate  strategy  rather-interesting  to-understand  computational-complexity
12 weeks ago by Vaguery

Copy this bookmark:

description:

tags: