**game-theory**1242

Solution concept - Wikipedia

27 days ago by nhaliday

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
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

27 days ago by nhaliday

A final game with Elwyn Berlekamp — Numberphile

6 weeks ago by Vaguery

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

6 weeks ago by nhaliday

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

7 weeks ago by Vaguery

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

8 weeks ago by Vaguery

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
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.

8 weeks ago by Vaguery

[1903.01373] α-Rank: Multi-Agent Evaluation by Evolution

8 weeks ago by Vaguery

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

12 weeks ago by Vaguery

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

12 weeks ago by Vaguery

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

12 weeks ago by Vaguery

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

12 weeks ago by Vaguery

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

12 weeks ago by Vaguery

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

12 weeks ago by Vaguery

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

12 weeks ago by Vaguery

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

**related tags**

Copy this bookmark: