Dominate a zero-sum game

Question

Consider a zero-sum game with 2 contestants. Each round, each contestant chooses, independently of each other, one of \$n \ge 2\$ different choices. Depending on the two chosen choices, one player is awarded an amount from the other player's pot. For example, the following table shows the gains (positive integers) and losses (negative integers) for Player 1 for each of \$9\$ possible choices:

$$\begin{array}{c|c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses B} & \text{Player 1 chooses C} \\ \hline \text{Player 2 chooses A} & 1 & 2 & 2 \\ \hline \text{Player 2 chooses B} & -2 & 1 & 2 \\ \hline \text{Player 2 chooses C} & 3 & -1 & 0 \\ \end{array}$$

For example, if Player 1 chooses \$A\$ and Player 2 chooses \$C\$, Player 1 gains \$3\$ and Player 2 loses \$3\$.

However, this table is needlessly complex. We can see that, assuming both players are playing to win, some choices are always suboptimal. For example, Player 1 would never choose \$B\$. No matter what Player 2 chooses, Player 1 choosing \$C\$ will produce a result that is either better or equal to \$B\$, as each element in \$C\$ is greater than or equal to its corresponding element in \$B\$. Therefore, we can say that \$C\$ dominates \$B\$, and we can remove \$\text{Player 1 chooses B}\$ from our matrix:

$$\begin{array}{c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses C} \\ \hline \text{Player 2 chooses A} & 1 & 2 \\ \hline \text{Player 2 chooses B} & -2 & 2 \\ \hline \text{Player 2 chooses C} & 3 & 0 \\ \end{array}$$

Additionally, we can see that Player 2 would never choose \$A\$ over \$B\$, as their payoff is always higher or equal from \$B\$ than it is from \$A\$, as each value in \$B\$ is less than or equal to it's corresponding element in \$A\$. So if Player 1 chooses \$A\$, then Player 2 either loses \$1\$ (\$A\$), gains \$2\$ (\$B\$) or loses \$3\$ (\$C\$). If Player 1 instead chooses \$C\$, then Player 2 either loses \$2\$ (\$A\$), loses \$2\$ (\$B\$) or gains \$0\$ (\$C\$). In either case, Player 2 would choose \$B\$ over \$A\$, as their result would never be worse when choosing \$B\$.

Therefore, we can say that \$B\$ dominates \$A\$, and we can remove \$\text{Player 2 chooses A}\$ from the matrix:

$$\begin{array}{c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses C} \\ \hline \hline \text{Player 2 chooses B} & -2 & 2 \\ \hline \text{Player 2 chooses C} & 3 & 0 \\ \end{array}$$

Here however, no more choices dominate. This is our final matrix, and would be the output for this input.

---

You are to take a rectangular matrix \$n\times m\$, where \$n, m \ge 2\$, and output the same matrix with all dominated options removed. You may also take the matrix transposed and/or with reversed signs from the examples provided in the question.

The matrices will only contain integers between \$-9\$ and \$9\$ (inclusive). You may also take \$n\$ and/or \$m\$ as input if you wish. The matrix is not guaranteed to contain any dominated options. The matrix may be reduced to a \$1\times1\$ matrix, at which point there are no more dominated options.

You may input and output in any convenient format. If there is more than one valid output, you may output any valid one. This is code-golf so the shortest code in bytes wins.

Test cases

^{Done by hand, don't hesitate to point out mistakes or suggest more}

Input
Output
Explanation

[[ 1  2  2]
 [-2  1  2]
 [ 3 -1  0]]
[[-2  2]
 [ 3  0]]
Column C dominates Column B, Row B dominates Row A

[[ 2  1  3  3]
 [ 0  0 -1  0]
 [ 1  1  0  0]]
[[0]]
Column A dominates B, Column D dominates C, Row B dominates Rows A+C, Column B dominates Column D (or vice versa)

[[ 2  0  4  1  2]
 [-1  6  0 -3  3]
 [ 0 -2  1 -1  1]
 [ 4 -2  1  2  3]]
[[1]]
Column E dominates Column D, Row C dominates Row D, Column E dominates Column A, Row C dominates Row A, Column E dominates Column E, Row C dominates Row B, Column E dominates Column B

[[ 7 -3 -5 -9 -8 -2]
 [ 6  7  6 -1  2  0]
 [-5 -8  3 -1 -8 -8]
 [-8  8  1  0  9 -2]
 [-3  0 -1 -4  8  1]
 [-2  2 -4  3 -7 -2]
 [ 4  8  1  8 -9 -9]
 [-1 -6 -4  1  9  5]]
[[ 7 -3 -5 -9 -8 -2]
 [-5 -8  3 -1 -8 -8]
 [-8  8  1  0  9 -2]
 [-3  0 -1 -4  8  1]
 [-2  2 -4  3 -7 -2]
 [ 4  8  1  8 -9 -9]
 [-1 -6 -4  1  9  5]]
Row C dominates Row B

[[  4 -6  2  ]
 [ -2 -5 -9  ]
 [  6 -2 -2  ]
 [  8  0  7  ]
 [ -9  4  2  ]]
[[ 4 -6  2]
 [-2 -5 -9]
 [-9  4  2]]
Row C dominates Row D, Row B dominates Row C

[[ 9 -7]
 [ 2  4]]
[[ 9 -7]
 [ 2  4]]
No rows or columns dominate

[[ 2  2  2]
 [ 2  3  2]
 [ 2  2  2]]
[[2]]
 Column B dominates Columns A+C, Row A dominates Rows B+C

[[ 1  4]
 [ 2  0]
 [ 1  4]]
[[ 2  0]  or [[ 1  4] 
 [ 1  4]]     [ 2  0]]
 Rows A and C are equal so we remove one of them. Either output is OK, but removing both rows isn't.

^{Note that for the 7th test case, there are many different ways to get to the final version}

Answer 1

J, ^{43 41 40} 39 bytes

f=.(#~1=1#.]*/ .>:|:)@~.
f&.:-&.|:@f^:_

Try it online!

tldr how

Create a function f to filter out dominated rows.

Apply plain f, followed by f "under" a negative transpose, until we reach a fixed point.

Answer 2

Jelly,  22  21 bytes

Qµ>Ạ€TLʋ€’ỊTịNZ
Ç⁺$ƬṪ

Try it online! Or see the test-suite.

How?

Ç⁺$ƬṪ - Link: matrix
   Ƭ  - collect up inputs to this until no change:
  $   -   last two links as a monad:
Ç     -     call Link 1 (see below)
 ⁺    -     repeat that
    Ṫ - tail

Qµ>Ạ€TLʋ€’ỊTịNZ - Link 1: matrix
Q               - de-duplicate (since one of any repeats wants keeping)
 µ              - start a new monadic chain, call that X
         ’      - with a decremented version of X, say Z, on the right:
       ʋ€       -   for each row in X:
  >             -     (row) greater than (Z) (vectorises)
   Ạ€           -     for each comparison: all truthy?
     T          -     truthy indices (i.e. indices in X which dominate row,
                                      including the index of row itself)
      L         -     length
          Ị     - insignificant? (vectorises) (i.e. 1 if no other row dominates, else 0)
           T    - truthy indices
            ị   - index into:
             N  -   negated (X)
              Z - transpose

---

As a single Link (21):
Qµ>Ạ€TLʋ€’ỊTịNZµ$⁺$ƬṪ
...or:
Qµ>Ạ€TLʋ€’ỊTịNZµ$Ƭm2Ṫ

Answer 3

Haskell, ^{106 101} 100 bytes

• -5 bytes thanks to kops.

until=<<((==)<*>)$g.g
g m=transpose.map(map(0-))$nub m\\(m>>=tail.mapM(\i->[i..9]))
import Data.List

Try it online!

The relevant function is until=<<((==)<*>)$g.g, which takes as input a matrix in the format described in the statement (not transposed and without flipped signs).

Very slow, but hey, we are codegolfing! See below for a (much) more efficient version.

How?

Most of the work is done by g. This function takes a matrix m as input and returns the matrix obtained after "half an operation". To be more specific, g takes m, removes dominated rows, then transposes m and flips all the signs. These last two operations are basically equivalent to swapping the roles of Player 1 and Player 2. It's not hard to see that applying g twice performs a full iteration: dominated rows and columns are removed, the two transpositions cancel out, and so do the two sign flipping. Let's now look at the code.

g m=                            -- the function g takes a matrix m and returns
    transpose.                  -- the transpose of
    map(map(0-))$               -- the matrix obtained by flipping the signs of
    nub m                       --   m with duplicate rows removed
    \\(                         --   to which we also remove
        m>>=                    --   any row obtained by taking a row of m (say r)
            tail.               --   and taking any but the first
            mapM(               --   list whose j-th entry
                \i->[i..9]))    --   lies between i and 9 (where i is the j-th entry of r)

nub m yields m with duplicate rows deleted; this is necessary since otherwise duplicate rows could potentially stick around forever. m>>=tail.mapM(\i->[i..9]) basically generates a list of all the possible rows (strictly) dominated by some row of m (this is obviously the slow part, since there can be up to \$\approx m\cdot19^n\$ such rows).

---

The anonymous function until=<<((==)<*>)$g.g (courtesy of kops) iterates g.g until the resulting matrix stops changing.

Haskell, ^{107 102} 101 bytes, much faster

• -5 bytes thanks to kops.

    until=<<((==)<*>)$g.g
    g m=transpose[(0-)<$>r|r<-nub m,all(or.zipWith(<)r)$m\\(r<$m)]
    import Data.List

Try it online!

Answer 4

Charcoal, 40 bytes

Ｆ⊗Ｌ⁺θ§θ⁰≔Ｅ§θ⁰±ＥΦθ⬤θ⎇⁼μνπ⊙μ‹ρ§ξς§μλθＩθ

Try it online! Link is to verbose version of code. Outputs using Charcoal's default format (each cell on its own line with rows double-spaced from each other). Explanation:

Ｆ⊗Ｌ⁺θ§θ⁰

Loop a large enough number of times (twice the number of rows and columns; probably overkill, so 4 bytes could be saved if this is the case).

Φθ⬤θ⎇⁼μνπ⊙μ‹ρ§ξς

Keep rows which, for each row, have at least one cell less than the corresponding cell from the other row, unless the two rows are equal, in which case keep the first of the duplicates.

≔Ｅ§θ⁰±Ｅ...§μλθ

Transpose and negate the filtered matrix. (Actually to save bytes the matrix is filtered for each column of the transpose. Fortunately this doesn't result in enough nesting to trouble the buggy deverbosifier on the version of Charcoal currently on TIO.)

Ｉθ

Output the remaining matrix.

Answer 5

Ruby, 112 ... 102 bytes

->m{1until m==[:min,:max].map{|x|m=m.transpose|[];m-=m.combination(2).map{|a,b|a.zip(b).map &x}}[1];m}

Try it online!