The payoff tables a monotonic QMIX mixer cannot represent

The constraint that makes greedy execution possible

QMIX is not an arbitrary centralized action-value network. Its mixer is constrained to be nondecreasing in each agent utilityRaising one agent utility cannot lower the mixed team value when other inputs are fixed.. If an agent raises its local utility while everything else is fixed, the mixed team value cannot fall. This is sufficient for a tuple of local maximizing actions to maximize the mixed value, provided the joint action set is a Cartesian product.

The QMIX paper implements this relationship with nonnegative mixing weights generated from state information. Agents still select actions using their own historiesEach agent chooses actions from its own available information at execution time.. State-conditioned mixing does not let an execution-time agent secretly see the global state. The analysis below freezes one state and observation pair so that representational questions can be answered without training a network.

Table one: addition is enough

Use rows for agent one's binary action and columns for agent two's. The table [[0,2],[1,3]] equals u1(a1)+u2(a2) with utilities [0,1] and [0,2]. Both agents prefer action one, producing the maximum three. Its mixed difference, Q00+Q11-Q01-Q10, is zero, as required for every additive two-agent table.

This difference is a useful invariant because row-only and column-only terms cancel. It lets us reject exact additive representation without depending on optimizer settings or a neural-network fit. A low training loss can be informative, but an algebraic contradiction is stronger evidence of impossibility.

Table two: monotonic need not mean additive

Now consider [[0,1],[1,4]]. Set both utilities to their binary action and define f(u,v)=u+v+2*u*v on the square [0,1]^2. Its partial derivatives are 1+2*v and 1+2*u, both positive. The four corners match the table exactly, while its mixed difference is two, ruling out an additive representation.

This explicitly constructed function witnesses the richer monotonic function class. It is not a trained QMIX network or a claim about exact finite-network parameterization. Both local greedy choices still select (1,1), whose team value is four. Nonlinearity has represented complementarity without reversing either agent's action ranking.

Table three: another agent reverses the ranking

The table [[0,2],[2,0]] rewards different actions. If agent two chooses zero, agent one prefers one; if agent two chooses one, agent one prefers zero. No fixed scalar ordering of agent one's two utilities can satisfy both strict preferences under a nondecreasing mixer. Equal utilities cannot help because equal inputs cannot produce different outputs with everything else fixed.

The CPU demo enumerates both possible row orderings and both column orderings, checking whether every row and column can be nondecreasing simultaneously. It accepts the first two tables and rejects the third. This is an exhaustive finite test, not an optimization failure. The table nevertheless has decentralized deterministic optimal choices, such as always selecting (0,1). Failure to represent all values therefore does not imply that every decentralized optimal policy is impossible.

Separate architecture from fitting

For a later fitting exercise, retain these exact witnesses and counterexamples as unit tests. Report constraint violations, value error, and greedy-policy agreement separately. Do not attribute a bad fit on the first two tables to representational impossibility, and do not expect unlimited epochs to remove the third table's contradiction.

A second state with indistinguishable local observations would introduce a separate information constraint. A powerful centralized mixer cannot supply an execution-time actor with information absent from that actor’s history.

Enumerate every local ordering

Each binary agent has two possible action orderings, giving four joint row-and-column orderings per payoff table. The extended data records the number of decreasing neighbor comparisons under all twelve table–ordering combinations. The ranking-reversal table fails every ordering; applying the strictly increasing remapping 3Q+7 does not remove the contradiction.

For these finite tables, the existence of a nondecreasing ordering is a statement about the monotonic function class. It does not establish that a chosen finite neural mixer will fit the table exactly or that optimization will find such a fit. Conversely, the impossible table needs no training run to diagnose. The contradictory ranking is already a certificate that a fixed scalar utility order is insufficient.

"""The payoff tables a monotonic QMIX mixer cannot represent
Deterministic, standard-library experiment. RESULTS contains the full data.
"""
from itertools import permutations, product

tables = {
    'additive': [[0, 2], [1, 3]],
    'monotonic nonlinear': [[0, 1], [1, 4]],
    'ranking reversal': [[0, 2], [2, 0]],
}

def monotonic_order_exists(table):
    for rows in permutations(range(2)):
        for cols in permutations(range(2)):
            ordered = [[table[r][c] for c in cols] for r in rows]
            row_ok = all(row[0] <= row[1] for row in ordered)
            col_ok = all(ordered[0][c] <= ordered[1][c] for c in range(2))
            if row_ok and col_ok:
                return True
    return False

for name, table in tables.items():
    difference = table[0][0] + table[1][1] - table[0][1] - table[1][0]
    print(f'{name}: mixed difference={difference}, monotonic={monotonic_order_exists(table)}')

def mixer(u, v):
    return u + v + 2 * u * v

for a, b in product(range(2), repeat=2):
    assert mixer(a, b) == tables['monotonic nonlinear'][a][b]
assert monotonic_order_exists(tables['additive'])
assert not monotonic_order_exists(tables['ranking reversal'])
print('constructed monotonic mixer greedy value:', mixer(1, 1))


records=[]
for name,table in tables.items():
    orderings=[]
    for rs in permutations(range(2)):
        for cs in permutations(range(2)):
            ordered=[[table[r][c] for c in cs] for r in rs]
            violations=sum(row[0]>row[1] for row in ordered)+sum(ordered[0][c]>ordered[1][c] for c in range(2))
            orderings.append(dict(rows=list(rs),columns=list(cs),violations=violations))
    records.append(dict(name=name,table=table,mixed_difference=table[0][0]+table[1][1]-table[0][1]-table[1][0],monotonic=monotonic_order_exists(table),orderings=orderings))
# Strictly increasing affine remapping preserves every ordering contradiction.
transformed=[[3*x+7 for x in row] for row in tables['ranking reversal']]
assert not monotonic_order_exists(transformed)
RESULTS=dict(tables=records,affine_reversal_still_impossible=True,mixer_corners=[dict(u=u,v=v,value=mixer(u,v)) for u,v in product(range(2),repeat=2)])
print('All 12 row/column orderings enumerated; affine-remapped reversal also rejected')

additive: mixed difference=0, monotonic=True
monotonic nonlinear: mixed difference=2, monotonic=True
ranking reversal: mixed difference=-4, monotonic=False
constructed monotonic mixer greedy value: 4
All 12 row/column orderings enumerated; affine-remapped reversal also rejected