Macaulay2 » Documentation
Packages » GameTheory :: blockDerangements(List)
next | previous | forward | backward | up | index | toc

blockDerangements(List) -- compute the block derangements

Description

Given a partition $\{F_0,\ldots,F_{n-1}\}$ of a finite set $F$, a block derangement of $F$ with respect to $\{F_0,\ldots,F_{n-1}\}$ is a permutation $P\colon F\to F$ of $F$ such that $P(F_i)\cap F_i=\emptyset$ for every $i\in\{0,\ldots,n-1\}$.

The function considers the input $D=(d_0,\ldots,d_{n-1})$, defines the set $F=F_0\cup\cdots\cup F_{n-1}$, where $F_i=\{(i,j)\mid j\in\{0,\ldots,d_i-2\}\}$ for every $i\in\{0,\ldots,n-1\}$, and computes the set of permutations of F. Then, it creates an empty list BD, and for each permutation $P$, if $P(F_i)\cap F_i=\emptyset$ for every $i\in\{0,\ldots,n-1\}$, then $P$ is added to the list BD. The function returns the list BD.

The number of elements of BD corresponds to the maximum number of totally mixed Nash equilibria of a generic game of a given format.

i1 : D = {3,3,3};
i2 : BD = blockDerangements D;
i3 : netList BD

     +--------------------+--------------------+--------------------+
o3 = |set {(2, 0), (1, 1)}|set {(2, 1), (0, 1)}|set {(0, 0), (1, 0)}|
     +--------------------+--------------------+--------------------+
     |set {(2, 1), (2, 0)}|set {(0, 0), (0, 1)}|set {(1, 0), (1, 1)}|
     +--------------------+--------------------+--------------------+
     |set {(1, 0), (2, 0)}|set {(2, 1), (0, 0)}|set {(0, 1), (1, 1)}|
     +--------------------+--------------------+--------------------+
     |set {(2, 1), (1, 1)}|set {(0, 0), (2, 0)}|set {(1, 0), (0, 1)}|
     +--------------------+--------------------+--------------------+
     |set {(1, 0), (2, 0)}|set {(2, 1), (0, 1)}|set {(0, 0), (1, 1)}|
     +--------------------+--------------------+--------------------+
     |set {(2, 1), (1, 1)}|set {(0, 1), (2, 0)}|set {(0, 0), (1, 0)}|
     +--------------------+--------------------+--------------------+
     |set {(1, 0), (1, 1)}|set {(2, 1), (2, 0)}|set {(0, 0), (0, 1)}|
     +--------------------+--------------------+--------------------+
     |set {(2, 1), (1, 0)}|set {(0, 0), (2, 0)}|set {(0, 1), (1, 1)}|
     +--------------------+--------------------+--------------------+
     |set {(2, 0), (1, 1)}|set {(2, 1), (0, 0)}|set {(1, 0), (0, 1)}|
     +--------------------+--------------------+--------------------+
     |set {(2, 1), (1, 0)}|set {(0, 1), (2, 0)}|set {(0, 0), (1, 1)}|
     +--------------------+--------------------+--------------------+

See also

Ways to use this method:


The source of this document is in /build/reproducible-path/macaulay2-1.25.06+ds/M2/Macaulay2/packages/GameTheory.m2:1494:0.