# Coincidences between intervals in two partial orders on complex reflection
groups

Joel Brewster Lewis and Jiayuan Wang

###### Abstract

In a finite real reflection group, the reflection length of each element is
equal to the codimension of its fixed space, and the two coincident functions
determine a partial order structure called the absolute order. In complex
reflection groups, the reflection length is no longer always equal to the
codimension of fixed space, and the two functions give rise to two different
partial orders on the group. We characterize the elements $w$ in the
combinatorial family $G(m,p,n)$ of complex reflection groups for which the
intervals below $w$ in these two posets coincide.

##  1 Introduction

Suppose that $G$ is a group and $f:G\to\mathbb{R}_{\geq 0}$ is a subadditive
function (that is, $f(xy)\leq f(x)+f(y)$ for all $x,y\in G$) such that
$f(x)=0$ if and only if $x$ is the identity in $G$. It is easy to show (see
Proposition 5) that such a function naturally gives rise to a partial order
$\leq_{f}$ on $G$: one has

$x\leq_{f}y\qquad\Longleftrightarrow\qquad f(x)+f(x^{-1}y)=f(y).$

Two sources of functions $f$ naturally present themselves, one algebraic and
one geometric. First, if $T$ is any generating set of $G$, then the _$T$
-length_

$\displaystyle\ell_{T}:G$ $\displaystyle\to\mathbb{N}$ $\displaystyle x$
$\displaystyle\mapsto\min\\{k:\exists t_{1},\ldots,t_{k}\in T\text{ such that
}x=t_{1}\cdots t_{k}\\}$

has the requisite properties. The resulting partial order $\leq_{\ell_{T}}$
may equivalently be characterized by saying that $x\leq_{\ell_{T}}y$ if $x$
lies along a path of minimum length from the identity to $y$ in the Cayley
graph of $G$ generated by $T$, or that each minimum-length $T$-word
$x=t_{1}\cdots t_{\ell_{T}(x)}$ for $x$ can be extended to a minimum-length
$T$-word $y=t_{1}\cdots t_{\ell_{T}(y)}$ for $y$.

Second, if $G$ acts on a finite-dimensional vector space $V$ (i.e., by choice
of a linear representation), with the element $g$ having _fixed space_
$\operatorname{fix}(g):=\ker(g-1)$, it is easy to see [8, Prop. 2.9] that the
fixed space codimension
$\operatorname{codim\,fix}(g):=\dim(V)-\dim\operatorname{fix}(g)$ is
subadditive. Moreover, we have
$\operatorname{codim\,fix}(g)=0\Longleftrightarrow x=\mathrm{id}$ precisely
when the representation of $G$ is faithful. In this case, we denote by
$\leq_{\mathrm{cdf}}$ the resulting partial order.

It is reasonable to inquire when the two subadditive functions, and hence the
two partial orders, just defined (one by a set of generators, the other by a
choice of representation) coincide. In [8, Prop. 2.11], it was shown that a
necessary condition for this equality is that $G$ be a reflection group, with
$T=R$ its subset of reflections. In this case, it’s easy to see that

$\operatorname{codim\,fix}(g)\leq\ell_{R}(g)\text{ for all }g\in G.$ (1)

It has been known for fifty years that if $G$ is a _real_ reflection group
(i.e., a finite Coxeter group), then in fact
$\operatorname{codim\,fix}(g)=\ell_{R}(g)$ for all $g$ in $G$ [3, Lem. 2]. The
same holds true in the complex reflection group $G(m,1,n)$ (the wreath product
$(\mathbb{Z}/m\mathbb{Z})\wr\mathfrak{S}_{n}$) [13, Rem. 2.3(1)], as well as
various other natural groups [2, 8, 4], but it does _not_ hold in the other
finite complex reflection groups [5].

Even when the whole partial orders $(G,\leq_{\mathrm{cdf}})$ and
$(G,\leq_{\ell_{R}})$ do not coincide, certain important pieces of them may.
In [9, Cor. 6.6], it was shown that when $G$ is a well generated complex
reflection group and $c$ is a Coxeter element in $G$, the two intervals
$[\mathrm{id},c]_{\mathrm{cdf}}$ and $[\mathrm{id},c]_{\ell_{R}}$ are
identical—they are the _noncrossing partition lattice_ of $G$. This naturally
raises the question [9, Q. 8.11] of which other elements have this property.
The main result of this paper is to characterize these elements in the
infinite family $G(m,p,n)$ of irreducible complex reflection groups. We do
this in terms of the combinatorial description of the groups $G(m,p,n)$—see
Section 2 for details.

######  Theorem 1.

An element $w\in G(m,p,n)$ satisfies
$[\mathrm{id},w]_{\ell_{R}}=[\mathrm{id},w]_{\mathrm{cdf}}$ if and only if the
cycle weights of $w$ that are not $0\pmod{p}$ can be partitioned into pairs
that sum to $0$, and any subset of cycle weights that sums to $0\pmod{p}$ is a
disjoint union of some weights that are $0\pmod{p}$ and some pairs of weights
that sum to $0$.

The rest of the paper is devoted to the proof of Theorem 1. In Section 2, we
introduce the necessary background definitions and notations. After this, we
divide the proof of Theorem 1 in several stages. In Section 3, we prove the
given conditions are necessary by explicitly constructing elements that belong
to one interval but not the other when the conditions are not met. To show
that they are sufficient, we develop in Section 4 a detailed combinatorial
description of the interval $[\mathrm{id},w]_{\mathrm{cdf}}$ for $w\in
G(m,p,n)$, allowing us to establish that
$u\in[\mathrm{id},w]_{\mathrm{cdf}}\Longrightarrow
u\in[\mathrm{id},w]_{\ell_{R}}$ when $w$ satisfies the necessary conditions.

##  2 Background

###  2.1 The infinite family of complex reflection groups

Say that a linear transformation $t$ on a vector space $V$ is a _reflection_
if its _fixed space_

$\operatorname{fix}(t):=\\{v\in V:t(v)=v\\}=\ker(t-1)$

has codimension $1$, and that a finite subgroup $W\subset\operatorname{GL}(V)$
is a _reflection group_ if $W$ is generated by its subset of reflections.
Complex reflection groups (i.e., those for which the field of scalars of $V$
is $\mathbb{C}$) were classified by Shephard and Todd [11]: every complex
reflection group is a direct product of irreducible groups, and the
irreducible groups belong either to an infinite family $G(m,p,n)$ for positive
integers $m$, $p$, $n$ with $p\mid m$, or are one of $34$ exceptional
examples.111This description elides a few technicalities; among these are that
the definition of $G(1,1,n)$ given below (as the set of $n\times n$
permutation matrices) is not irreducible in its action on $\mathbb{C}^{n}$,
because it acts trivially on the subspace
$\operatorname{span}\\{(1,1,\ldots,1)\\}$. These technicalities will not play
a role in what follows. This paper is concerned primarily with the groups of
the infinite family; we describe them now.

By appropriate choice of basis, the group $G(m,1,n)$ may be realized
concretely as the group of $n\times n$ monomial matrices whose nonzero entries
are $m$th roots of $1$. Algebraically, $G(m,1,n)$ is the wreath product
$(\mathbb{Z}/m\mathbb{Z})\wr\mathfrak{S}_{n}$ of the cyclic group of order $m$
with the symmetric group $\mathfrak{S}_{n}$. Thus, its elements may be
represented by a pair $w=[u;a]$ where $u\in\mathfrak{S}_{n}$ is the
_underlying permutation_ of $w$ and
$a=(a_{1},\ldots,a_{n})\in(\mathbb{Z}/m\mathbb{Z})^{n}$ is its tuple of
_weights_. A _cycle_ of $w$ simply means a cycle of its underlying
permutation; in particular, we consider fixed points to be cycles (of size
$1$), and we denote by $c(w)$ the number of cycles of $w$. For any subset
$I\subseteq[n]$, we say that the weight of $I$ (relative to $w$) is
$\sum_{i\in I}a_{i}$. This notion will be especially relevant when $I$ is (the
underlying set of) a cycle of $w$ or a collection of cycles of $w$. In
particular, we denote by $\operatorname{wt}(w)$ the weight
$\sum_{i=1}^{n}a_{i}$ of $w$. For $p\mid m$, the group $G(m,p,n)$ is the
normal subgroup of $G(m,1,n)$ consisting of all those elements whose weight is
a multiple of $p$.

Let $\zeta=\exp(2\pi i/m)$. If $w=[u;a]$ is an element of $G(m,p,n)$ and
$(x_{1}\cdots x_{k})$ is a weight-$0$ cycle of $w$, the vector in
$\mathbb{C}^{n}$ whose $x_{i}$th entry is
$\zeta^{a_{x_{1}}+\ldots+a_{x_{i-1}}}$ for $i=1,\ldots,k$ and whose other
entries are $0$ is easily seen to be fixed by the action of $w$. In fact, the
collection of such vectors (taken over all weight-$0$ cycles of $w$) span
$\operatorname{fix}(w)$, and consequently
$\operatorname{codim\,fix}(w)=n-c_{0}(w)$, where $c_{0}(w)$ represents the
number of weight-$0$ cycles of $w$. Considering the case that
$\operatorname{codim\,fix}(w)=1$, we see that there are two flavors of
reflection in $G(m,p,n)$: first, for any $i\neq j$ in $\\{1,\ldots,n\\}$ and
any $a\in\mathbb{Z}/m\mathbb{Z}$, the element

$[(i\ j);(0,\ldots,0,a,0,\ldots,0,-a,0,\ldots,0)]$

with $a_{i}=a$ and $a_{j}=-a$ and $a_{k}=0$ if $k\neq i,j$ is a
_transposition-like reflection_. Second, if $p<m$, then for any $k$ in
$\\{0,1,\ldots,m/p-1\\}$, the element

$[\mathrm{id};(0,\ldots,0,kp,0,\ldots,0)]$

is a _diagonal reflection_ (where the nonzero weight may occur in any of the
$n$ positions).

Any real reflection group may be complexified by extension of scalars,
yielding a complex reflection group. In particular, the four infinite families
of real reflection groups are all realized inside the infinite family
$G(m,p,n)$:

  * •

the symmetric group $\mathfrak{S}_{n}$ is $G(1,1,n)$ (type A);

  * •

the hyperoctahedral group of signed permutations of degree $n$ is $G(2,1,n)$
(type B/C);

  * •

its normal subgroup of even-signed permutations is $G(2,2,n)$ (type D); and

  * •

the dihedral group of order $2\times m$ is $G(m,m,2)$ (type I).

###  2.2 Cycle partitions and reflection length

In any reflection group $W$ with reflections $R$, the _reflection length_
$\ell_{R}(w)$ of an element $w$ is defined to be

$\ell_{R}(w)=\min\\{k:\exists t_{1},\ldots,t_{k}\in R\text{ s.t.
}w=t_{1}\cdots t_{k}\\}.$

As mentioned in the introduction, when $W$ is a real reflection group or the
group $G(m,1,n)$, we have $\ell_{R}(w)=\operatorname{codim\,fix}(w)$ for all
$w\in W$. For the other groups $G(m,p,n)$ in the combinatorial family, a
formula for reflection length was given by Shi. In order to state it, we need
some additional terminology.

Given a finite set $S$, a _(set) partition_ of $S$ is a collection of disjoint
nonempty sets whose union is $S$. The elements of the partition are called its
_parts_. We use the following notation for set partitions: $[1\ 3\mid 2\mid
4]$ represents the set partition whose three parts are $\\{1,3\\}$, $\\{2\\}$,
and $\\{4\\}$; the same set partition could be written many different ways,
e.g., as $[2\mid 3\ 1\mid 4]$.

We will frequently deal with set partitions $\Pi$ of the set of cycles of an
element $w$ of $G(m,p,n)$. Let $w\in G(m,p,n)$ with cycles
$C_{1},\ldots,C_{k}$. We say that a set partition $\Pi$ on
$C_{1},\ldots,C_{k}$ is a _null cycle partition_ 222In [10], these partitions
of the cycles were called simply “cycle partitions”. if, for every part in
$\Pi$, the weights of its cycles sum to $0\pmod{p}$. For every null cycle
partition $\Pi$ of $w$, the _value_ $v(\Pi)$ is defined to be

$v(\Pi):=|\Pi|+v_{m}(\Pi),$

where $|\Pi|$ denotes the number of parts of $\Pi$ and $v_{m}(\Pi)$ denotes
the number of parts of $\Pi$ whose cycle weights sum to $0$ (not just
$0\pmod{p})$. For a fixed element $w\in G(m,p,n)$, there can be many null
cycle partitions with many different values. Let

$v_{\mathrm{max}}(w):=\mathrm{max}\\{v(\Pi):\Pi\text{ is a null cycle
partition for }w\\}$

be the maximum value of any null cycle partition of $w$; we say that the cycle
partitions that realize $v_{\mathrm{max}}(w)$ are its _maximum (null) cycle
partitions_. Then we have the following formula for reflection length.

######  Theorem 2 (Shi [13, Thm. 4.4]).

For $w\in G(m,p,n)$, its reflection length is

$\ell_{R}(w)=n+c(w)-v_{\mathrm{max}}(w).$

By combining Theorem 2 with the formula for fixed space codimension, Shi was
able to characterize the elements $w$ in $G(m,p,n)$ that satisfy
$\operatorname{codim\,fix}(w)=\ell_{R}(w)$.

######  Proposition 3 ([13, Prop. 5.3 (2)]).

Let $w\in G(m,p,n)$. Then $\ell_{R}(w)=\operatorname{codim\,fix}(w)$ if and
only if $w$ has a null cycle partition $\Pi$ in which the size $|B|$ of each
part $B$ is at most $2$, and which further satisfies the following conditions:
if $|B|=1$ then the cycle in $B$ has weight $0\pmod{p}$; if $|B|=2$, the
cycles in $B$ have nonzero weights that sum to $0$. Moreover, in this case,
the given cycle partition is maximum.

The following rephrasing is perhaps more congenial to work with.

######  Corollary 4.

An element $w\in G(m,p,n)$ satisfies
$\ell_{R}(w)=\operatorname{codim\,fix}(w)$ if and only if the multiset of
cycle weights of $w$ that are not $0\pmod{p}$ can be partitioned into pairs
that sum to $0$.

###  2.3 Posets from subadditive functions

We end this section by providing the proof of the result (mentioned in the
introduction) that the subadditive functions we consider really do determine a
poset structure. As observed in [5, Fn. 1], the proof in general is
essentially the same as the proof given in [2, Prop. 3] that
$\leq_{\mathrm{cdf}}$ is a partial order on the orthogonal group.

######  Proposition 5.

Let $G$ be any group and suppose that $f:G\to\mathbb{R}_{\geq 0}$ is a
subadditive function (i.e., $f(xy)\leq f(x)+f(y)$ for all $x,y\in G$) such
that $f(x)=0$ if and only if $x$ is the identity in $G$. Define a relation
$\leq_{f}$ on $G$ by

$x\leq_{f}y\qquad\Longleftrightarrow\qquad f(x)+f(x^{-1}y)=f(y).$

Then $\leq_{f}$ is a partial order on $G$.

###### Proof.

We have three properties to check.

Since $f(\mathrm{id})=0$, for any $x\in G$ we have
$f(x)=f(x)+f(\mathrm{id})=f(x)+f(x^{-1}x)$, and so $x\leq_{f}x$.

Suppose $x\leq_{f}y$ and $y\leq_{f}x$. Since $f$ takes only nonnegative
values, we have

$f(x)\leq f(x)+f(x^{-1}y)=f(y)\leq f(y)+f(y^{-1}x)=f(x).$

This forces $f(x^{-1}y)=0$; by the hypothesis on $f$, we have
$x^{-1}y=\mathrm{id}$, so $x=y$.

Finally, suppose $x\leq_{f}y$ and $y\leq_{f}z$. By subadditivity of $f$ and
the definition of $\leq_{f}$, we have

$\displaystyle f(z)$ $\displaystyle\leq f(x)+f(x^{-1}z)$ $\displaystyle\leq
f(x)+f(x^{-1}y)+f(y^{-1}z)$ $\displaystyle=f(y)+f(y^{-1}z)$
$\displaystyle=f(z).$

This forces $f(z)=f(x)+f(x^{-1}z)$, so $x\leq_{f}z$. ∎

######  Remark 6.

When $f=\ell_{T}$ is the length function for a generated group $G$, the poset
$(G,\leq_{T})$ is automatically graded by $\ell_{T}$, i.e., each cover
relation is between a pair of elements of $T$-lengths $k$ and $k+1$ for some
$k$. Nothing similar can be said for more general choices of the function $f$.
We mention two examples involving fixed space codimension:

  * •

In the group $G(4,2,2)$, the element
$w:=[\mathrm{id};(1,1)]=\begin{bmatrix}i&\\\ &i\end{bmatrix}$ has
$\operatorname{codim\,fix}(w)=2$ but the only element $x$ with
$x<_{\mathrm{cdf}}w$ is $x=\mathrm{id}$.

  * •

In the group $G(3,3,6)$, the element $w=[\mathrm{id};(1,1,1,2,2,2)]$ has
$\operatorname{codim\,fix}(w)=\ell_{R}(w)=6$. There are maximal chains of
length $6$ from $\mathrm{id}$ to $w$ in the fixed space codimension order (for
example,

$\mathrm{id}<_{\mathrm{cdf}}[(1\ 4);{\bf
0}]<_{\mathrm{cdf}}[\mathrm{id};(1,0,0,2,0,0)]<_{\mathrm{cdf}}[(2\
5);(1,0,0,2,0,0)]<_{\mathrm{cdf}}\\\
[\mathrm{id};(1,1,0,2,2,0)]<_{\mathrm{cdf}}[(3\
6);(1,1,0,2,2,0)]<_{\mathrm{cdf}}w$

is one such chain), but there is also the maximal chain

$\mathrm{id}<_{\mathrm{cdf}}[\mathrm{id};(1,1,1,0,0,0)]<_{\mathrm{cdf}}w,$

of length $2$.

Both examples involve elements that cover $\mathrm{id}$ in the fixed space
codimension poset that are not reflections. Indeed, Foster-Greenwood showed
[5, Prop. 2.4] that whenever a complex reflection group $W$ satisfies
$\ell_{R}(w)\neq\operatorname{codim\,fix}(w)$ for some $w\in W$, there exists
such a non-reflection atom in the $\mathrm{cdf}$-poset. The second example
further illustrates that $\ell_{R}(w)=\operatorname{codim\,fix}(w)$ is not
sufficient to guarantee
$[\mathrm{id},w]_{\ell_{R}}=[\mathrm{id},w]_{\mathrm{cdf}}$.

We now move to the proof of the main theorem.

##  3 Necessity

In this section, we prove that the given conditions are necessary, i.e., that
if the cycle weights of $w$ cannot be partitioned into pairs that sum to $0$
and singletons that are $0\pmod{p}$, or if they can be so partitioned but
there exists a subset of the cycle weights of total weight $0\pmod{p}$ that
cannot be similarly partitioned, then
$[\mathrm{id},w]_{\ell_{R}}\neq[\mathrm{id},w]_{\mathrm{cdf}}$. It will be
more convenient at first to phrase the first possibility in terms of
reflection length, allowing us to state a uniform result for all complex
reflection groups.

######  Proposition 7.

Let $W$ be any complex reflection group and let $w$ be an element of $W$. If
$\ell_{R}(w)>\operatorname{codim\,fix}(w)$, then there exists a reflection
that belongs to $[\mathrm{id},w]_{\ell_{R}}$ but not to
$[\mathrm{id},w]_{\mathrm{cdf}}$.

###### Proof.

We first establish the result for irreducible groups by a case-based approach;
then at the end we show that it extends to reducible groups.

Consider $w\in G(m,p,n)$ with $\ell_{R}(w)>\operatorname{codim\,fix}(w)$. By
3, we equivalently have that in any maximum null cycle partition of $w$, there
is either a part with at least three cycles, or there is a part with at least
two cycles and nonzero total weight. Fix such a maximum null cycle partition
$\Pi$, let $B$ be the part promised by the last sentence, and let
$C_{1}=(a\cdots)$ and $C_{2}=(b\cdots)$ be two of the cycles in $B$, of
respective nonzero weights $\alpha$ and $\beta$. Choose a reflection $t:=[(a\
b);(0,\ldots,0)]\in G(m,p,n)$ that transposes an element from one of these
cycles with an element from the other. Since $t$ is a reflection,
$\ell_{R}(t)=\operatorname{codim\,fix}(t)=1$. Since the entries transposed by
$t$ are in different cycles of $w$, multiplying $w$ by $t=t^{-1}$ merges these
two cycles into a single cycle, necessarily of weight $\alpha+\beta$. Let us
consider $\operatorname{codim\,fix}(tw)$ and $\ell_{R}(tw)$.

If $|B|=2$, then by assumption $\alpha+\beta\neq 0$. If instead $|B|>2$, since
$B$ is a part of a maximum null cycle partition, no subset of $B$ can have
weights that sum to $0$ (or else we could split this subset into its own part,
increasing the value of the partition), so also in this case $\alpha+\beta\neq
0$. Consequently in both cases $tw$ has the same number of weight-$0$ cycles
as $w$. It follows that
$\operatorname{codim\,fix}(tw)=\operatorname{codim\,fix}(w)$. Thus
$t\not\in[\mathrm{id},w]_{\mathrm{cdf}}$.

Let $\Pi^{\prime}$ be the partition of the cycles of $tw$ that we get from
$\Pi$ by deleting the two cycles $C_{1}$ and $C_{2}$ from $B$ and replacing
them with the merged cycle $tC_{1}C_{2}$, otherwise leaving the partition the
same. Clearly $v(\Pi^{\prime})=v(\Pi)$. Thus $\ell_{R}(tw)\leq
n+c(tw)-v(\Pi^{\prime})=n+c(w)-1-v(\Pi)=\ell_{R}(w)-1$. On the other hand, by
subadditivity, $1+\ell_{R}(tw)=\ell_{R}(t)+\ell_{R}(tw)\geq\ell_{R}(w)$, so in
fact we have equality, and $t\in[\mathrm{id},w]_{\ell_{R}}$. This completes
the proof in the case of the infinite family $G(m,p,n)$.

We next consider the exceptional groups. Here we proceed by a brute-force
computer calculation. For each exceptional group $W$, we performed for each
conjugacy class representative $w$ the following computation: if
$\ell_{R}(w)>\operatorname{codim\,fix}(w)$, we checked for each reflection $t$
whether $t\leq_{\ell_{R}}w$ and $t\not\leq_{\mathrm{cdf}}w$. In all cases, the
result of the calculation was to verify the existence of such a reflection.
The entire computation took a few minutes runtime on CoCalc, using SageMath
and its interface with GAP and the CHEVIE package [12, 6, 7].

Finally, we extend the result to all (not necessarily irreducible) complex
reflection groups. Let $W=W_{1}\times\cdots\times W_{k}$ be the decomposition
of $W$ into irreducibles (an internal direct product) and $w=w_{1}\cdots
w_{k}$ the corresponding decomposition of $w$. Reflection length and fixed
space codimension are both additive over direct products, so if
$\ell_{R}(w)>\operatorname{codim\,fix}(w)$, then some $w_{i}$ must satisfy
$\ell_{R}(w_{i})>\operatorname{codim\,fix}(w_{i})$. Since $W_{i}$ is
irreducible, it falls into one of the cases above, and so there exsits a
reflection $t$ in $W_{i}$ that satisfies $t\in[\mathrm{id},w_{i}]_{\ell_{R}}$
and $t\not\in[\mathrm{id},w_{i}]_{\mathrm{cdf}}$. The set of reflections of
$W$ is precisely the union of the sets of reflections of the $W_{i}$, so $t$
is a reflection in $W$. Using again that reflection length and fixed space
codimension are additive over direct products, it follows immediately that
$t\leq_{\ell_{R}}w$ but $t\not\leq_{\mathrm{cdf}}w$. This completes the proof.
∎

The following observation has appeared many times in the literature (e.g., as
[5, Lem. 2.4]); we include its proof for completeness.

######  Proposition 8.

Let $W$ be any reflection group and $w\in W$. If
$\ell_{R}(w)=\operatorname{codim\,fix}(w)$, then
$[\mathrm{id},w]_{\ell_{R}}\subseteq[\mathrm{id},w]_{\mathrm{cdf}}$.

###### Proof.

For any $u\in[\mathrm{id},w]_{\ell_{R}}$, we have by (1) and the definition of
the reflection length order that
$\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)\leq\ell_{R}(u)+\ell_{R}(u^{-1}w)=\ell_{R}(w)$.
By the subadditivity of $\operatorname{codim\,fix}$, we have
$\operatorname{codim\,fix}(w)\leq\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)$.
Since $\ell_{R}(w)=\operatorname{codim\,fix}(w)$, we have
$\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)=\operatorname{codim\,fix}(w)$,
i.e., $u\in[\mathrm{id},w]_{\mathrm{cdf}}$. ∎

We now shift our discussion to the particular case of the combinatorial groups
$G(m,p,n)$, and show the necessity of the second condition in 1.

######  Proposition 9.

Let $W=G(m,p,n)$ and $w\in W$. Suppose that
$\ell_{R}(w)=\operatorname{codim\,fix}(w)$ and that there exists a subset of
the cycles of $w$ whose weight is $0\pmod{p}$ and which cannot be partitioned
into pairs of cycles whose weights sum to $0$ and singleton sets containing a
cycle of weight $0\pmod{p}$. Then there is an element of
$[\mathrm{id},w]_{\mathrm{cdf}}$ that does not belong to
$[\mathrm{id},w]_{\ell_{R}}$.

###### Proof.

Fix $w\in G(m,p,n)$ with cycles $C_{1},\ldots,C_{k}$. Let
$S=\\{C_{i_{1}},\ldots,C_{i_{s}}\\}$ be a subset of cycles of $w$ whose
weights sum to $0\pmod{p}$, but which cannot be partitioned into pairs of
cycles whose weights sum to $0$ and singleton sets containing a cycle of
weight $0\pmod{p}$. Since any cycles of weight $0\pmod{p}$ can be removed from
$S$ while preserving this property, it suffices to assume that $S$ does not
contain any such cycle of $w$.

Let $u=w|_{S}$ be the element of $G(m,1,n)$ that agrees with $w$ on
$\operatorname{Supp}(S)$ and acts as the identity (with weight $0$) on
$\\{1,\ldots,n\\}\smallsetminus\operatorname{Supp}(S)$. Since the sum of the
weights of the cycles in $S$ is $0\pmod{p}$, in fact $u\in G(m,p,n)$. We now
show that $u\in[\mathrm{id},w]_{\mathrm{cdf}}$.

Since $S$ contains no cycles of weight $0\pmod{p}$, the only cycles of weight
$0$ in $u$ are the fixed points outside $\operatorname{Supp}(S)$, and so
$c_{0}(u)=n-|\operatorname{Supp}(S)|$. On the other hand, $u^{-1}w$ contains a
fixed point (of weight $0$) for each element of $\operatorname{Supp}(S)$ and
also all the cycles of $w$ not in $S$; in particular, it contains all
weight-$0$ cycles of $w$. Thus
$c_{0}(u^{-1}w)=|\operatorname{Supp}(S)|+c_{0}(w)$. It follows immediately
that

$\displaystyle\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)$
$\displaystyle=(n-c_{0}(u))+(n-c_{0}(u^{-1}w))$
$\displaystyle=|\operatorname{Supp}(S)|+n-|\operatorname{Supp}(S)|-c_{0}(w)$
$\displaystyle=n-c_{0}(w)$ $\displaystyle=\operatorname{codim\,fix}(w).$

Then $u\in[\mathrm{id},w]_{\mathrm{cdf}}$.

Let us now show that $u\notin[\mathrm{id},w]_{\ell_{R}}$. By 4 and the
defining property of $S$, $\ell_{R}(u)>\operatorname{codim\,fix}(u)$. Then we
have

$\ell_{R}(w)=\operatorname{codim\,fix}(w)=\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)<\ell_{R}(u)+\ell_{R}(u^{-1}w).$

Therefore, $u\notin[\mathrm{id},w]_{\ell_{R}}$. ∎

######  Corollary 10.

If $w\in G(m,p,n)$ satisfies
$[\mathrm{id},w]_{\ell_{R}}=[\mathrm{id},w]_{\mathrm{cdf}}$, then the cycle
weights of $w$ that are not $0\pmod{p}$ can be partitioned into pairs that sum
to $0$, and any subset of cycle weights that sums to $0\pmod{p}$ is a disjoint
union of some weights that are $0\pmod{p}$ and some pairs of weights that sum
to $0$.

###### Proof.

This follows immediately from 7 and 9, once we translate the condition
$\ell_{R}(w)=\operatorname{codim\,fix}(w)$ to a statement about cycles using
4. ∎

##  4 Sufficiency

It remains to show that the given conditions are sufficient to imply
$[\mathrm{id},w]_{\ell_{R}}=[\mathrm{id},w]_{\mathrm{cdf}}$. We begin with a
general lemma on the structure of the $\mathrm{cdf}$-interval below an
arbitrary element $w$.

######  Definition.

Suppose that $u,w\in G(m,p,n)$. Define an equivalence relation $\sim$ on the
cycles of $w$, as follows: for two cycles $C_{1}$ and $C_{2}$ of $w$, we have
that $C_{1}\sim C_{2}$ if there exists a cycle of $u$ that intersects both
$C_{1}$ and $C_{2}$, and we extend by transitivity. Denote by $\Pi_{u}(w)$ the
resulting set partition of the cycles of $w$.

######  Example 11.

For any $w\in G(m,p,n)$, we have $\Pi_{\mathrm{id}}(w)$ is the fully refined
partition in which each cycle belongs to its own part. If $c$ is an element of
$G(m,p,n)$ that has a single $n$-cycle, then $\Pi_{c}(w)$ is the trivial
partition in which all cycles of $w$ belong to the same part.

For $w=[(1\ 2\ 3)(6\ 7);(0,0,1,-1,-2,2,0,0)]$ and $u=[(2\ 3)(5\ 6)(7\
8);(0,0,0,3,0,3,0,0)]$ in $G(6,6,8)$, we have

$\Pi_{u}(w)=[(1\ 2\ 3)\mid(4)\mid(5)(6\ 7)(8)].$

For each part $B$ of $\Pi_{u}(w)$, we have by construction that the underlying
set of $B$ is stabilized by (the underlying permutations of) both $u$ and $w$.
Let $u|_{B}$ and $w|_{B}$ be the associated restrictions, both of which may be
viewed as elements of $G(m,1,\\#\operatorname{Supp}(B))\subseteq G(m,1,n)$.

######  Example 12.

In the previous example, we have

$\displaystyle w|_{B_{1}}$ $\displaystyle=[(1\ 2\ 3);(0,0,1,0,0,0,0,0)],$
$\displaystyle u|_{B_{1}}$ $\displaystyle=[(2\ 3);\textbf{0}],$ $\displaystyle
w|_{B_{2}}$ $\displaystyle=[\mathrm{id};(0,0,0,-1,0,0,0,0)]$ $\displaystyle
u|_{B_{2}}$ $\displaystyle=[\mathrm{id};(0,0,0,3,0,0,0,0)],$ $\displaystyle
w|_{B_{3}}$ $\displaystyle=[(6\ 7);(0,0,0,0,-2,2,0,0)],$ $\displaystyle
u|_{B_{3}}$ $\displaystyle=[(5\ 6)(7\ 8);(0,0,0,0,0,3,0,0)].$

The elements $w|_{B_{1}}$ and $u|_{B_{1}}$ may be viewed as elements of
$G(6,1,3)\subset G(6,1,8)$ via the embedding in which the first three
coordinates are permuted. Note that $w|_{B_{1}}$ is _not_ an element of
$G(6,6,8)$, since its weight is $1$ (not $0$), even though $w$ is.

######  Proposition 13.

Suppose that $u,w$ are any two elements of $G(m,p,n)$. Then

$\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)\geq
n+c(w)-2|\Pi_{u}(w)|+\\#\\{\text{parts of $\Pi_{u}(w)$ of nonzero weight}\\}.$

Furthermore, in the case of equality, for each part $B$ of $\Pi_{u}(w)$ we
have that $c(u|_{B})+c(u^{-1}w|_{B})=\\#\operatorname{Supp}(B)-c(w|_{B})+2$
and exactly one of the following holds:

  * •

$\operatorname{wt}(w|_{B})=0$ and all cycles of $u|_{B}$ and $u^{-1}w|_{B}$
have weight $0$,

  * •

$\operatorname{wt}(u|_{B})=\operatorname{wt}(w|_{B})\neq 0$, one cycle of
$u|_{B}$ has weight $\operatorname{wt}(w|_{B})$ while the others have weight
$0$, and all cycles of $u^{-1}w|_{B}$ have weight $0$, or

  * •

$\operatorname{wt}(u^{-1}w|_{B})=\operatorname{wt}(w|_{B})\neq 0$, one cycle
of $u^{-1}w|_{B}$ has weight $\operatorname{wt}(w|_{B})$ while the others have
weight $0$, and all cycles of $u|_{B}$ have weight $0$.

###### Proof.

Choose a part $B$ of $\Pi_{u}(w)$. Given any partition of
$\operatorname{Supp}(B)$ into two parts, it may be that there is a cycle of
$w|_{B}$ that includes elements from both parts. If not, there must be a cycle
of $u|_{B}$ that includes elements from both parts (since otherwise the cycles
of $w$ in $B$ would not be connected under $\sim$). Thus, the underlying
permutations of $u|_{B}$ and $w|_{B}$ generate a group that acts transitively
on $\operatorname{Supp}(B)$. Furthermore, since $u$ and $w$ stabilize
$\operatorname{Supp}(B)$, we have $(u|_{B})^{-1}\cdot(w|_{B})=(u^{-1}w)|_{B}$,
with $u|_{B}$ and $u^{-1}w|_{B}$ generating the same group as $u|_{B}$ and
$w|_{B}$.

If $\tau,\sigma_{1},\ldots,\sigma_{k}$ are permutations of $[N]$ such that
$\sigma_{1}\cdots\sigma_{k}=\tau$ and the group generated by
$\sigma_{1},\ldots,\sigma_{k}$ acts transitively on $[N]$, then [1, Eq. (4)]

$\sum_{i=1}^{k}c(\sigma_{i})\leq(k-1)N-c(\tau)+2.$ (2)

Taking $k=2$, $N=\\#\operatorname{Supp}(B)$, and $\tau,\sigma_{1},\sigma_{2}$
to be the underlying permutations of $w|_{B},u|_{B},u^{-1}w|_{B}$,
respectively, it follows immediately from (2) that

$c(u|_{B})+c(u^{-1}w|_{B})\leq\\#\operatorname{Supp}(B)-c(w|_{B})+2.$ (3)

Summing (3) over all parts $B$ of $\Pi_{u}(w)$, we have that

$c(u)+c(u^{-1}w)\leq n-c(w)+2|\Pi_{u}(w)|.$ (4)

Let us now consider how many cycles of $u$ and $u^{-1}w$ may be weight $0$.
Obviously $c_{0}(u|_{B})+c_{0}(u^{-1}w|_{B})\leq c(u|_{B})+c(u^{-1}w|_{B})$
(since each weight-$0$ cycle is a cycle). Furthermore, if the total weight of
$w|_{B}$ is nonzero, then (since $u|_{B}\cdot u^{-1}w|_{B}=w|_{B}$) at least
one of $u|_{B}$, $u^{-1}w|_{B}$ must have nonzero weight, and so in this case
at least one cycle of at least one of the two factors must have nonzero
weight. Therefore we can refine the previous inequality to give

$c_{0}(u|_{B})+c_{0}(u^{-1}w|_{B})\leq
c(u|_{B})+c(u^{-1}w|_{B})-\Big{[}\operatorname{wt}(w|_{B})\neq 0\Big{]},$ (5)

where the last summand on the right is an Iverson bracket. Summing (5) over
all parts $B$, we have

$c_{0}(u)+c_{0}(u^{-1}w)\leq c(u)+c(u^{-1}w)-\\#\\{\text{parts of $\Pi_{u}(w)$
of nonzero weight}\\}.$

Combining this with (4) yields

$c_{0}(u)+c_{0}(u^{-1}w)\leq n-c(w)+2|\Pi_{u}(w)|-\\#\\{\text{parts of
$\Pi_{u}(w)$ of nonzero weight}\\}.$

Subtracting both sides from $2n$ gives the desired inequality. The equality
condition forces equality in (3) and (5) for every part $B$; when
$\operatorname{wt}(w)=0$, this forces $c_{0}(u|_{B})=c(u|_{B})$ and
$c_{0}(u^{-1}w|_{B})=c(u^{-1}w|_{B})$, while otherwise it forces one of $u$
and $u^{-1}w$ to have all cycles of weight $0$ and the other to have all but
one cycle of weight $0$ (with the extra cycle necessarily of weight
$\operatorname{wt}(w)$). ∎

######  Proposition 14.

Suppose that $w\in G(m,p,n)$ is arbitrary and
$u\in[\mathrm{id},w]_{\mathrm{cdf}}$. Then

  1. (1)

$\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)=n+c(w)-2|\Pi_{u}(w)|+\\#\\{\text{parts
of $\Pi_{u}(w)$ of nonzero weight}\\}$ and

  2. (2)

every part of $\Pi_{u}(w)$ is either a singleton or consists of exactly two
cycles of nonzero weights that sum to $0$.

###### Proof.

Since $u\in[\mathrm{id},w]_{\mathrm{cdf}}$, we have
$\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)=\operatorname{codim\,fix}(w)=n-c_{0}(w)$.
By Proposition 13, we have

$n-c_{0}(w)=\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)\geq\\\
n+c(w)-2|\Pi_{u}(w)|+\\#\\{\text{parts of $\Pi_{u}(w)$ of nonzero weight}\\},$
(6)

and hence that

$c_{0}(w)+c(w)\leq|\Pi_{u}(w)|+\\#\\{\text{parts of $\Pi_{u}(w)$ of weight
$0$}\\}.$ (7)

Let $a$ be the number of parts of $\Pi_{u}(w)$ consisting of a single
weight-$0$ cycle of $w$, let $b$ be the number of parts consisting of a single
cycle of nonzero weight, let $c$ be the number of parts having total weight
$0$ with more than one cycle, and let $d$ be the total number of remaining
parts. Then of course $|\Pi_{u}(w)|=a+b+c+d$, $c_{0}(w)\geq a$, and $c(w)\geq
a+b+2c+2d$. Plugging these inequalities into (7) yields

$\displaystyle 2a+b+2c+2d$ $\displaystyle=a+(a+b+2c+2d)$ $\displaystyle\leq
c_{0}(w)+c(w)$ $\displaystyle\leq(a+b+c+d)+a+c$ $\displaystyle=2a+b+2c+d.$

This immediately forces $d=0$. Moreover, when $d=0$, the equality between the
first and last terms forces equality in the middle: hence we have equality in
(6) (the first of the two desired statements) as well as $c_{0}(w)=a$ and
$c(w)=a+b+2c$. From $c_{0}(w)=a$, we learn that each weight-$0$ cycle in $w$
belongs to its own part in $\Pi_{u}(w)$. From $c(w)=a+b+2c$, we learn that
each non-singleton part in $\Pi_{u}(w)$ consists of exactly two cycles and has
total weight $0$; since the weight-$0$ cycles are in singleton parts, it
follows that the non-singleton part of $\Pi_{u}(w)$ contain two cycles, both
of which have nonzero weight, and that the two weights sum to $0$. This is
precisely the second claim. ∎

As a last preliminary step towards Theorem 1, we prove the theorem in the case
of certain very special elements.

######  Lemma 15.

Suppose that $w\in G(m,p,n)$ is an element with a single cycle, or with two
cycles of nonzero weights that sum to $0$. Then
$[\mathrm{id},w]_{\mathrm{cdf}}=[\mathrm{id},w]_{\ell_{R}}$.

###### Proof.

We consider three cases.

First, suppose that $w$ consists of a single cycle of weight $0$. By 2 and the
definition of $\operatorname{codim\,fix}$,
$\ell_{R}(w)=\operatorname{codim\,fix}(w)=n-1$, and therefore by 8,
$[\mathrm{id},w]_{\ell_{R}}\subseteq[\mathrm{id},w]_{\mathrm{cdf}}$. We
consider the reverse inclusion. Let $u\in[\mathrm{id},w]_{\mathrm{cdf}}$.
Since $w$ has only one cycle, $\Pi_{u}(w)$ is the unique set partition of the
one-element set containing this cycle. By the definition of
$\leq_{\mathrm{cdf}}$, we have

$\displaystyle\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)$
$\displaystyle=n+1-2+0$ $\displaystyle=n+c(w)-2|\Pi_{u}(w)|+\\#\\{\text{parts
of $\Pi_{u}(w)$ of nonzero weight}\\}.$

Therefore, by Proposition 13, all cycles of $u$ and $u^{-1}w$ have weight $0$.
It follows immediately from Proposition 3 that
$\ell_{R}(u)=\operatorname{codim\,fix}(u)$ and
$\ell_{R}(u^{-1}w)=\operatorname{codim\,fix}(u^{-1}w)$, and hence that
$u\in[\mathrm{id},w]_{\ell_{R}}$, as claimed.

Second, suppose that $w$ consists of a single cycle of nonzero weight. By 2
and the definition of $\operatorname{codim\,fix}$,
$\ell_{R}(w)=\operatorname{codim\,fix}(w)=n$, and therefore by 8,
$[\mathrm{id},w]_{\ell_{R}}\subseteq[\mathrm{id},w]_{\mathrm{cdf}}$. We
consider the reverse inclusion. Let $u\in[\mathrm{id},w]_{\mathrm{cdf}}$.
Since $w$ has only one cycle, $\Pi_{u}(w)$ is the unique set partition of the
one-element set containing this cycle. By the definition of
$\leq_{\mathrm{cdf}}$, we have

$\displaystyle\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)$
$\displaystyle=n+1-2+1$ $\displaystyle=n+c(w)-2|\Pi_{u}(w)|+\\#\\{\text{parts
of $\Pi_{u}(w)$ of nonzero weight}\\}.$

Therefore, by Proposition 13, one of $u$ and $u^{-1}w$ has one cycle of
nonzero weight (and some number of cycles of weight $0$) and the other has all
cycles of weight $0$; moreover, this nonzero weight is $\operatorname{wt}(w)$,
which is $0\pmod{p}$. It follows immediately from Proposition 3 that
$\ell_{R}(u)=\operatorname{codim\,fix}(u)$ and
$\ell_{R}(u^{-1}w)=\operatorname{codim\,fix}(u^{-1}w)$, and hence that
$u\in[\mathrm{id},w]_{\ell_{R}}$, as claimed.

Finally, suppose that $w$ consists of two cycles of nonzero weights that sum
to $0$. By 2 and the definition of $\operatorname{codim\,fix}$,
$\ell_{R}(w)=\operatorname{codim\,fix}(w)=n$, and therefore by 8,
$[\mathrm{id},w]_{\ell_{R}}\subseteq[\mathrm{id},w]_{\mathrm{cdf}}$. We
consider the reverse inclusion. Let $u\in[\mathrm{id},w]_{\mathrm{cdf}}$. We
have two sub-cases, depending on the structure of $\Pi_{u}(w)$.

First, suppose that $\Pi_{u}(w)$ is the set partition with a single part that
contains both cycles of $w$. By the definition of $\leq_{\mathrm{cdf}}$, we
have

$\displaystyle\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)$
$\displaystyle=n+2-2+0$ $\displaystyle=n+c(w)-2|\Pi_{u}(w)|+\\#\\{\text{parts
of $\Pi_{u}(w)$ of nonzero weight}\\}.$

Therefore, by Proposition 13, all cycles of $u$ and $u^{-1}w$ have weight $0$.
It follows immediately from Corolary 4 that
$\ell_{R}(u)=\operatorname{codim\,fix}(u)$ and
$\ell_{R}(u^{-1}w)=\operatorname{codim\,fix}(u^{-1}w)$, and hence that
$u\in[\mathrm{id},w]_{\ell_{R}}$, as claimed.

Alternatively, it could be that $\Pi_{u}(w)$ is the set partition of two parts
$B_{1},B_{2}$, each containing exactly one cycle of $w$. By the definition of
$\leq_{\mathrm{cdf}}$, we have

$\displaystyle\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)$
$\displaystyle=n+2-4+2$ $\displaystyle=n+c(w)-2|\Pi_{u}(w)|+\\#\\{\text{parts
of $\Pi_{u}(w)$ of nonzero weight}\\}.$

By Proposition 13, we know that for either $i=1,2$, either $u|_{B_{i}}$ has
one cycle with weight $\operatorname{wt}(w|_{B_{i}})$ and some cycles of
weight $0$ (possibly none) while $u^{-1}w|_{B_{i}}$ has all cycles of weight
$0$, or the reverse. This leads to three possibilities for $u$, $u^{-1}w$:
each of them may have all cycles of weight $0$, may have two cycles of nonzero
weight that sum to zero and all other cycles of weight $0$, or may have one
cycle of nonzero weight and all others of weight $0$ (in which case
necessarily the one cycle must have weight $0\pmod{p}$, since $u,u^{-1}w\in
G(m,p,n)$). In all three situations, we have immediately from 4 that
$\ell_{R}(u)=\operatorname{codim\,fix}(u)$ and
$\ell_{R}(u^{-1}w)=\operatorname{codim\,fix}(u^{-1}w)$, and hence that
$u\in[\mathrm{id},w]_{\ell_{R}}$.

Since the preceding cases are exhaustive, the proof is complete. ∎

We are ready now to complete the second direction of the biconditional in the
main theorem.

######  Proposition 16.

If $w\in G(m,p,n)$ satisfies $\ell_{R}(w)=\operatorname{codim\,fix}(w)$ and
any subset of cycle weights that sums to $0\pmod{p}$ is a disjoint union of
some weights that are $0\pmod{p}$ and some pairs of weights that sum to $0$,
then $[\mathrm{id},w]_{\ell_{R}}=[\mathrm{id},w]_{\mathrm{cdf}}$.

###### Proof.

Let $w\in G(m,p,n)$ be as in the statement. Since
$\ell_{R}(w)=\operatorname{codim\,fix}(w)$, we have by 8 that
$[\mathrm{id},w]_{\ell_{R}}\subseteq[\mathrm{id},w]_{\mathrm{cdf}}$, and we
seek to prove the opposite inclusion. To that end, choose
$u\in[\mathrm{id},w]_{\mathrm{cdf}}$.

Consider the partition $\Pi_{u}(w)=\\{B_{1},\ldots,B_{k}\\}$ of the cycles of
$w$ induced by $u$. Since $u\in[\mathrm{id},w]_{\mathrm{cdf}}$, we have on one
hand by Proposition 14(2) that each $B_{i}$ either consists of a single cycle
of $w$ or of a pair of cycles whose weights sum to $0$. On the other hand, we
have by Proposition 14(1) that
$\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)=n+c(w)-2|\Pi_{u}(w)|+\\#\\{\text{parts
of $\Pi_{u}(w)$ of nonzero weight}\\}$. Therefore, by the equality case of
Proposition 13, we have for each part $B_{i}$ of $\Pi_{u}(w)$ that either
$u|_{B_{i}}$ has all cycles of weight $0$, or that $u|_{B_{i}}$ has a single
cycle whose weight is equal to $\operatorname{wt}(w|_{B_{i}})$ and some number
of other cycles of weight $0$. Combining these two separate statements leaves
us with three possibilities for each part $B_{i}$: either

  * •

$w|_{B_{i}}$ consists of two cycles of nonzero weight whose weights sum to
$0$, and $u|_{B_{i}}$ consists of a number of cycles of weight $0$, or

  * •

$w|_{B_{i}}$ consists of a single cycle, and $u|_{B_{i}}$ consists of a number
of cycles of weight $0$, or

  * •

$w|_{B_{i}}$ consists of a single cycle of nonzero weight, and $u|_{B_{i}}$
has one cycle of this weight and possibly some other cycles, all of which have
weight $0$.

By taking the union over all $B_{i}$, it follows in particular that the
multiset of cycle weights of $u$ is the union of a submultiset of the multiset
of cycle weights of $w$ and a multiset containing some number of copies of
$0$.

Let $S$ be the set consisting of all cycles $C$ of $w$ that fall into the
third category above, i.e., for which there is a corresponding cycle of $u$
supported on $\operatorname{Supp}(C)$ having the same weight as $C$. Thus, the
multiset of nonzero cycle weights of $u$ is precisely the same as the multiset
of weights of cycles in $S$. Since $u\in G(m,p,n)$, the nonzero cycle weights
of $u$ sum to $0\pmod{p}$, and therefore $S$ is a set of cycles of $w$ with
the property that the sum of the weights of its cycles is $0\pmod{p}$. By the
hypothesis on $w$, it follows that there exists a partition (call it $Q$) of
$S$ consisting of some singleton sets containing a cycle of weight $0\pmod{p}$
and some pairs in which the weights are nonzero but sum to $0$ (and no other
parts).

Define a partition $P_{u}(w)$ of the cycles of $w$ into parts of size $1$ and
$2$, as follows:

  * •

First, if two cycles of $w$ belong to the same part $B_{i}$ of $\Pi_{u}(w)$,
then they belong to the same part in $P_{u}(w)$. (The cycles in each pair in
this case have nonzero weights that sum to $0$.)

  * •

Second, if two cycles of $w$ both belong to $S$ (so, by definition of $S$, are
not covered in the prior case) and belong to the same part in $Q$, then they
belong to the same part in $P_{u}(w)$. (The cycles in each pair in this case
have nonzero weights that sum to $0$.)

  * •

Finally, let $S^{\prime}$ be the set of cycles of $w$ not covered in either of
the prior cases. Since $w\in G(m,p,n)$, the sum of all its cycle weights is
$0\pmod{p}$. The cycles of $w$ covered by the preceding cases have total
weight $0$, so the cycles of $S^{\prime}$ have total weight $0\pmod{p}$.
Therefore, by the hypothesis on $w$, there is a partition $Q^{\prime}$ of
$S^{\prime}$ each of whose parts is either a singleton of weight $0\pmod{p}$
or a pair of cycles of nonzero weight that sum to $0$. Let $P_{u}(w)$ include
all the parts of $Q^{\prime}$.

An example of this construction is given as Example 17 below.

Since each part of $P_{u}(w)$ is a union of parts of $\Pi_{u}(w)$, the
underlying permutations of $u$ and $w$ respect the underlying set partition of
$[n]$, and it makes sense to speak of the restrictions $u|_{B}$ and $w|_{B}$
for $B$ a part of $P_{u}(w)$. Furthermore, the partition $P_{u}(w)$ is a
_null_ cycle partition of $w$: each part of size two has total weight $0$, and
each part of size one has weight $0\pmod{p}$. Thus, each element $w|_{B}$
belongs to $G(m,p,n)$, not just to $G(m,1,n)$. Moreover, the same holds true
for $u$ because, my construction, each restriction $u|_{B}$ either has weight
$0$ or has the same weight as $w|_{B}$. Thus, we may view the products

$w=\prod_{B\in P_{u}(w)}w|_{B}\qquad\text{and}\qquad u=\prod_{B\in
P_{u}(w)}u|_{B}$

as factorizations of $w,u$ into elements of $G(m,p,n)$.

Next we claim that for each part $B$ of $P_{u}(w)$, the element $u|_{B}$
belongs to $[\mathrm{id},w|_{B}]_{\mathrm{cdf}}$. To see this we must consider
the several cases in which parts $P_{u}(w)$ were constructed. If $B$ is a part
of $\Pi_{u}(w)$ (consisting of either one or two cycles of $w$), then by
combining Propositions 13 and 14 in the same was as before: 14 says that we
are in the equality case of 13, and the conditions of the equality case imply
that
$\operatorname{codim\,fix}(u|_{B})+\operatorname{codim\,fix}(u^{-1}w|_{B})=\operatorname{codim\,fix}(w|_{B})$
in each case. The other possibility is that $B$ consists of two cycles, each
of which formed a singleton part in $\Pi_{u}(w)$. This could happen either
because the two cycles of $w$ belonged to the same part in the partition $Q$
of $S$, or because they belonged to the same part in the partition
$Q^{\prime}$ of $S^{\prime}$. We spell out the details for only the first of
these two cases; the other is very similar. So suppose that
$B=\\{C_{1},C_{2}\\}$ consists of two cycles of $w$ having nonzero weights
that sum to $0$, and that $u|_{B}$ consists of some number of cycles of weight
$0$, as well as one cycle of the same weight as $C_{1}$ and another of the
same weight as $C_{2}$. As before, by Propositions 13 and 14, we have for
$i=1,2$ that
$c(u|_{\\{C_{i}\\}})+c(u^{-1}w|_{\\{C_{i}\\}})=\\#\operatorname{Supp}(C_{i})+1$
and that $c_{0}(u|_{\\{C_{i}\\}})=c(u|_{\\{C_{i}\\}})-1$,
$c_{0}(u^{-1}w|_{\\{C_{i}\\}})=c(u^{-1}w|_{\\{C_{i}\\}})$. Substituting the
latter two equations into the former, subtracting from
$2\\#\operatorname{Supp}(C_{i})$, and adding the two resulting equations for
$i=1,2$ gives
$\operatorname{codim\,fix}(u|_{B})+\operatorname{codim\,fix}(u^{-1}w|_{B})=\\#\operatorname{Supp}(B)=\operatorname{codim\,fix}(w|_{B})$,
as needed.

Since each element $w|_{B}$ is either a single cycle of weight $0\pmod{p}$ or
a product of two cycles of nonzero weights that sum to $0$, we have by Lemma
15 that $u|_{B}\in[\mathrm{id},w|_{B}]_{\ell_{R}}$. The final result is now a
simple calculation: we have

$\operatorname{codim\,fix}(w)=\operatorname{codim\,fix}(u)+\operatorname{codim\,fix}(u^{-1}w)\leq\\\
\ell_{R}(u)+\ell_{R}(u^{-1}w)\overset{\begin{subarray}{c}\text{sub-}\\\
\text{additivity}\\\ \text{of }\ell_{R}\end{subarray}}{\leq}\sum_{B\in
P_{u}(w)}\ell_{R}(u|_{B})+\sum_{B\in P_{u}(w)}\ell_{R}(u^{-1}w|_{B})=\\\
\sum_{B\in
P_{u}(w)}\left(\ell_{R}(u|_{B})+\ell_{R}(u^{-1}w|_{B})\right)\overset{\text{Lem.~{}\ref{lem:special
elements}}}{=}\sum_{B\in
P_{u}(w)}\operatorname{codim\,fix}(w|_{B})\overset{\begin{subarray}{c}\text{cycle}\\\
\text{partition}\end{subarray}}{=}\operatorname{codim\,fix}(w),$

and therefore $\ell_{R}(u)=\operatorname{codim\,fix}(u)$ and
$\ell_{R}(u^{-1}w)=\operatorname{codim\,fix}(u^{-1}w)$, so
$u\in[\mathrm{id},w]_{\ell_{R}}$, as claimed. ∎

######  Example 17.

Consider the elements

$w=[(1\ 2)(3)(4)(5)(6)(7)(8)(9)(10);(0,1,-1,2,-2,4,-4,8,8,8)]\in G(16,8,10)$

and $u=[(1)(2)(3)(4\ 5)(6)(7)(8\ 9)(10);(0,0,0,1,-1,4,-4,0,0,8)]$. Then

$\Pi_{u}(w)=[(1\ 2)\mid(3)\mid(4)(5)\mid(6)\mid(7)\mid(8)(9)\mid(10)].$

Observe that this partition of the cycles is not a _null_ cycle partition
because in the part $B_{1}=\\{(1\ 2)\\}$, the cycle weight is not $0\pmod{8}$.
In the bulleted list in the definition of $P_{u}(w)$, the first category
consists of the parts $B_{3}=\\{(4),(5)\\}$ and $B_{6}=\\{(8),(9)\\}$, the
second category consists of the parts $B_{1}=\\{(1\ 2)\\}$ and
$B_{2}=\\{(3)\\}$, and the third category consists of the parts
$B_{4}=\\{(6)\\}$, $B_{5}=\\{(7)\\}$, and $B_{7}=\\{(10)\\}$. Therefore
$S=\\{(6),(7),(10)\\}$. The desired partition $Q$ of $S$ is $[(6)(7)\mid(10)]$
(in this case it is unique). To define $P_{u}(w)$, we have three steps. The
first step creates parts $(4)(5)$ and $(8)(9)$. The second step creates a part
$(6)(7)$. In the third step, we have leftover cycles $S^{\prime}=\\{(1\
2),(3),(10)\\}$, and the desired partition $Q^{\prime}$ is $[(1\
2)(3)\mid(10)]$. Thus $P_{u}(w)=[(1\
2)(3)\mid(4)(5)\mid(6)(7)\mid(8)(9)\mid(10)]$.

In contrast to $\Pi_{u}(w)$, this partition _is_ a null cycle partition of
$w$. Furthermore the restriction of $u$ to any part has weight $0\pmod{p}$
(including possibly weight $0$).

The proof of the main theorem is essentially trivial at this point.

See 1

###### Proof.

This follows immediately from 10 and 16, once we translate the condition
$\ell_{R}(w)=\operatorname{codim\,fix}(w)$ in 16 to a statement about cycles
using 4. ∎

## References

  * [1] Mireille Bousquet-Mélou and Gilles Schaeffer.  Enumeration of planar constellations.  Adv. in Appl. Math., 24(4):337–368, 2000.
  * [2] T. Brady and C. Watt.  A partial order on the orthogonal group.  Comm. Algebra, 30(8):3749–3754, 2002.
  * [3] R.W. Carter.  Conjugacy classes in the Weyl group.  Compositio Math., 25:1–59, 1972.
  * [4] J. Dieudonné.  Sur les générateurs des groupes classiques.  Summa Brasil. Math., 3:149–179, 1955.
  * [5] B. Foster-Greenwood.  Comparing codimension and absolute length in complex reflection groups.  Comm. Algebra, 42(10):4350–4365, 2014.
  * [6] The GAP Group.  GAP – Groups, Algorithms, and Programming, Version 4.12.2, 2022\.
  * [7] M. Geck, G. Hiss, F. Lübeck, G. Malle, and G. Pfeiffer.  CHEVIE – A system for computing and processing generic character tables for finite groups of Lie type, Weyl groups and Hecke algebras.  Appl. Algebra Engrg. Comm. Comput., 7:175–210, 1996.
  * [8] J. Huang, J.B. Lewis, and V. Reiner.  Absolute order in general linear groups.  J. Lond. Math. Soc. (2), 95(1):223–247, 2017.
  * [9] Joel Brewster Lewis and Alejandro H. Morales.  Factorization problems in complex reflection groups.  Canadian Journal of Mathematics, 73(4):899–946, 2021.
  * [10] Joel Brewster Lewis and Jiayuan Wang.  The hurwitz action in complex reflection groups.  Combinatorial Theory, 2(1), mar 2022.
  * [11] Geoffrey C Shephard and John A Todd.  Finite unitary reflection groups.  Canadian Journal of Mathematics, 6:274–304, 1954.
  * [12] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 10.0), 2023.  https://www.sagemath.org.
  * [13] Jian yi Shi.  Formula for the reflection length of elements in the group $G(m,p,n)$.  Journal of Algebra, 316(1):284–296, October 2007.


# A Versatile Multi-Agent Reinforcement Learning Benchmark for Inventory
Management

Xianliang Yang1 Zhihao Liu2 Wei Jiang3 Chuheng Zhang1 Li Zhao1 Lei Song1 Jiang
Bian1
1Microsoft Research Asia
2Institute of automation  Chinese academy of science
3University of Illinois Urbana-Champaign
{xianliang<EMAIL_ADDRESS>
###### Abstract

Multi-agent reinforcement learning (MARL) models multiple agents that interact
and learn within a shared environment. This paradigm is applicable to various
industrial scenarios such as autonomous driving, quantitative trading, and
inventory management. However, applying MARL to these real-world scenarios is
impeded by many challenges such as scaling up, complex agent interactions, and
non-stationary dynamics. To incentivize the research of MARL on these
challenges, we develop MABIM (Multi-Agent Benchmark for Inventory Management)
which is a multi-echelon, multi-commodity inventory management simulator that
can generate versatile tasks with these different challenging properties.
Based on MABIM, we evaluate the performance of classic operations research
(OR) methods and popular MARL algorithms on these challenging tasks to
highlight their weaknesses and potential.

##  1 Introduction

Reinforcement learning (RL) is a critical branch of machine learning that aims
to make a sequence of optimal decisions to maximize rewards[1]. It
demonstrates remarkable success in various game domains, surpassing human
performance in games like Go[2], StarCraft[3, 4, 5], and DOTA2[6, 7]. Besides
gaming, RL is widely used in diverse domains such as industrial production[8,
9, 10], energy control[11, 12], autonomous driving[13, 14, 15], quantitative
trading[16, 17, 18], and recommendation systems[19, 20]. The RL research is
closely tied to the availability of suitable environments, which is well-
established in various RL fields, including Multi-Agent Particle
Environment[21] and CityLearn[22] for energy control, SUMO[23] for autonomous
driving, Qlib[24] for finance, and RecoGym[25] for recommendation systems.

Multi-Agent Reinforcement Learning (MARL) is a sub-field of RL that focuses on
studying the behavior of multiple agents coexisting and interacting with each
other in a shared environment. Due to its ability to model complex
interactions and adapt to dynamic situations, MARL can be applied to real-
world production scenarios where diverse and complex decisions are made
simultaneously[26].

Despite its strong applicability, MARL encounters various challenges,
including scaling up, agent interactions, and non-stationary contexts, among
others [27]. To address these challenges, significant research efforts have
been dedicated to developing solutions[28, 29, 30, 31]. However, the absence
of a comprehensive benchmark makes it difficult to effectively test various
algorithms on diverse challenges, and prevents a thorough evaluation of
algorithm performance across an extensive range of problems.

Inventory management is a crucial aspect of Operations Research (OR),
encompassing a wide range of complex real-world scenarios that require
decision-making. The variety of commodities, warehouse interactions, and
demand fluctuations make it an ideal platform for MARL research. To leverage
this, we develop a Multi-Agent Benchmark for Inventory Management (MABIM),
simulating a multi-echelon multi-agent inventory environment based on the
OpenAI Gym framework[32]. MABIM captures the complexities inherent in MARL,
enabling comprehensive comparisons among different MARL algorithms within a
realistic production context. This benchmark promotes advancements in tackling
the diverse challenges of inventory management while also providing a platform
for assessing MARL algorithm performance across various tasks. The environment
code is available at https://github.com/VictorYXL/ReplenishmentEnv.

Our contributions could be summarized as follows:

  * •

We develop MABIM, an efficient and flexible inventory management environment
that utilizes real data from our partner in the retail and supports multi-
echelon warehouses while handling massive commodities. MABIM serves as an open
and effective benchmark for addressing inventory management challenges.

  * •

Leveraging MABIM’s flexibility, we simulate a wide range of MARL challenges,
including scaling up, cooperation, competition, generalization, and
robustness, further enhancing its applicability in various scenarios.

  * •

We conduct the performance evaluation of both classic OR algorithms and MARL
algorithms on these challenging scenarios, providing an in-depth analysis of
their individual strengths and weaknesses.

##  2 Background

In this section, we start by briefly introducing the current challenges faced
by MARL. Then, we present an overview of the existing MARL benchmarks.
Afterwards, we introduce the inventory management problem and provide a
concise summary of existing inventory management benchmarks.

#### MARL challenges.

MARL is a rapidly growing research field that concentrates on creating
learning algorithms for multiple agents operating within a shared environment.
Although it has experienced significant progress, several challenges continue
to persist. These challenges involve scaling up to accommodate a large number
of agents, effectively managing the intricate interactions between agents that
encompass cooperation and competition, and addressing the non-stationary
dynamics resulting from both environment and the interactive learning
agents[27].

#### MARL benchmarks.

Current MARL benchmarks have certain limitations that can impede a
comprehensive assessment and comparison of diverse algorithms. Table 2
compares common MARL benchmarks with ours, highlighting the maximum number of
agents, dynamic contexts (or exogenous state variables, see e.g.,[33, 34]),
and user customization flexibility. Previous benchmarks face challenges in
accommodating scenarios with thousands of agents, incorporating dynamic
contexts, and providing flexibility in a single framework. These limitations
may impact the precision and applicability for evaluating MARL algorithms,
underscoring the importance of developing a more comprehensive and versatile
benchmark in MARL research.

Table 1: Comparison for different MARL benchmarks.

| #Agents | Interaction | Contexts | Flexibility
---|---|---|---|---
SMAC[35] | 27 | Coop. |  |
GRF[36] | 11 | Coop. |  |
GoBigger[37] | 24 | Coop.&Comp. |  | ✓
MPE[38] | 40 | Coop.&Comp. |  |
MA-MuJoCO[39] | 6 | Coop. |  |
NeuralMMO[40] | 1024 | Coop.&Comp. |  | ✓
ManiSkill[41] | 2 | Coop. |  | ✓
MABIM(Ours) | 2000 | Coop.&Comp. | ✓ | ✓

Table 2: Comparison for existing inventory management benchmarks.

| Real data | Multi-echelon | Multi-SKU
---|---|---|---
OR-Gym[42] |  | ✓ |
MARLIM[43] | ✓ |  | ✓
IM Sim.[44] | ✓ |  | ✓
MABIM(Ours) | ✓ | ✓ | ✓

#### Inventory management.

Inventory management is a critical problem in the field of operations
research, involving the efficient control of the Stock Keeping Units (SKUs)
for storage, acquisition, and distribution to meet customer demands and
optimize costs[45]. The main objective of inventory management is to strike a
balance between stock availability and storage costs while minimizing
stockouts and overstocks[46]. One of the key challenges in this field is the
implementation of effective replenishment strategies[47]. Effective inventory
management can result in improved customer satisfaction, reduced operational
costs, and enhanced overall business performance.

Classic OR algorithms are effective in specific inventory management
scenarios. The base stock algorithm by Arrow et al. (1951)[48] maintains
desired inventory levels by ordering when the inventory falls below a
predetermined level, making it suitable for low order cost situations. Blinder
et al. (1990)[49] propose the ($s,S$) algorithm to avoid frequent
replenishment, triggering orders when stock falls below reorder point $s$ and
replenishing to the maximum level $S$. The base stock (BS) and ($s,S$)
algorithms are two popular OR algorithms and serve as baselines in our later
experiments. See Appendix A for more details.

Due to the generalization and applicability of reinforcement learning
algorithms, they are increasingly being applied to inventory management
problems. Examples include Deep Q-Network (DQN)[50], QMIX[51], QTRAN[52], IPPO
and MAPPO[53], and CD-PPO[54]. These RL algorithms demonstrate promising
capabilities for addressing inventory management challenges and may provide
performance improvement and better adaptability.

#### Inventory management benchmarks.

Despite the extensive research conducted on inventory management, there is a
lack of comprehensive benchmarks in this domain. Table 2 provides an overview
of existing efforts in this area. The characteristics highlighted in the table
not only align the benchmark more closely with real-world production scenarios
but also lend themselves to be transformed into challenges for MARL algorithms
effectively.

##  3 MARL formulation for inventory management

In this section, we first introduce how the inventory management problem is
modeled in our paper (Section 3.1), including the structure of the multi-
echelon system, the dynamic process for each time step, and the calculation of
the evaluation metric (i.e., the profit). Subsequently, we present the MARL
formulation of this problem (Section 3.2).

###  3.1 Inventory management model

#### Multi-echelon structure.

We illustrate the multi-echelon model used in MABIM in Figure 1. This
modelling is motivated by the real-world process where products are produced
by the factory and transmitted through echelons of warehouses sequentially
until they reach the consumers. The goal is to optimize replenishment
quantities for each restocking cycle (or time step), balancing inventory to
avoid overstocking (causing increasing costs) as well as understocking
(causing unmet demands).

Figure 1: Multi-echelon inventory model.

#### Workflow.

Each time step involves the agent making decisions regarding replenishment
quantities for SKUs and subsequently transitioning the environment to a new
state. Let $M\in\mathbb{Z}^{+}$ be the total warehouses, with the first one
being closest to customers, and $N\in\mathbb{Z}^{+}$ the total SKUs. Given a
variable $X\in\\{D,S,L\ldots\\}$, $X_{i,j}^{t}$ represents its value for the
$j$-th SKU in the $i$-th echelon at step $t$, with $0\leq i<M$ and $0\leq
j<N$. Given the above notations, the main progression of a step can be
described as follows:

$\displaystyle D_{i+1,j}^{t+1}=R_{i,j}^{t}$ (Replenish) $\displaystyle
S_{i,j}^{t}=\min(D_{i,j}^{t},I_{i,j}^{t})$ (Sell) $\displaystyle
A_{i,j}^{t}=\sum_{k=0}^{t-1}\mathbb{I}(k+L_{i,j}^{k}==t)\cdot S_{i+1,j}^{t}$
(Arrive)
$\displaystyle\gamma_{i}^{t}=\min\left(\frac{W_{i}-\sum_{j}I_{i,j}^{t}}{\sum_{j}A_{i,j}^{t}},1\right),B_{i,j}^{t}=\lfloor
A_{i,j}^{t}\cdot\gamma_{i}^{t}\rfloor$ (Receive) $\displaystyle
I_{i,j}^{t+1}=I_{i,j}^{t}-S_{i,j}^{t}+B_{i,j}^{t}$ (Update)

Here, $D,R,S,I,A,B\in\mathbb{Z}^{+}$ and $\mathbb{I}(\text{condition})$ is an
indicator function that returns 1 if the condition is true, and 0 otherwise.

  * •

Replenish: Each warehouse requests a replenishment quantity $R$ for each SKU
from the upstream source based on the policy, which becomes the demand of the
upstream source. The demand $D$ with $i=0$ comes from consumers, while other
demands $D$ with $i>0$ come from replenishment orders of downstream
warehouses.

  * •

Sell: Each warehouse sells the product to the downstream warehouse or
consumers to meet their demands as much as possible. Specifically, the sale
quantity $S$ is set to be the demand $D$ capped by the current inventory level
$I$.

  * •

Arrive: Replenished SKUs arrive after lead time $L$ steps, which may be
various. Thus, SKUs replenished at different steps may arrive simultaneously,
so the arrival quantity $A$ is the sum of multiple previous replenishment
quantities.

  * •

Receive: Limited warehouse capacity $W$ may prevent storing all arriving SKUs,
causing overflow. The system allows custom acceptance strategies, and we
present a built-in uniform receiving strategy in the above equation.

  * •

Update: The inventory for each SKU is updated after each step.

#### Profit.

After each step, we calculate the profit generated by each SKU in each
warehouse independently using the following formulation:

$\text{profit}=\underbrace{p\cdot S}_{\text{Incoming}}-\underbrace{c\cdot
S}_{\text{Procurement cost}}-\underbrace{v\cdot(A-B)}_{\text{Overflow
cost}}-\underbrace{o\cdot\mathbb{I}(R>0)}_{\text{Order
cost}}-\underbrace{h\cdot I}_{\text{Holding
cost}}-\underbrace{k\cdot(D-S)}_{\text{Backlog cost}}$ (1)

Here $p,c,v,o,h,k\in\mathbb{R}^{+}$ represent the unit selling price,
procurement cost, overflow, order, holding, and backlog costs, respectively.
We omit all subscripts denoting SKU, echelon, and step indices for better
readability. Profit can serve as a useful metric for evaluating the
effectiveness of a given strategy, and can also be used to design rewards in
RL algorithm.

###  3.2 MARL formulation

In our formulation, each SKU in each warehouse is modelled as an agent, which
is responsible for making decisions regarding its replenishment amount in a
warehouse. To ensure the environment is more scalable and adaptable to various
scenarios, MABIM provides built-in functions for shaping actions, rewards, and
observation states. Besides, interfaces are also available to customize them
easily in order to accommodate specific needs and requirements.

  * •

The observation state for each agent is configurable, allowing for the
inclusion of all current and past features of an agent. In addition to SKU
features, warehouse or environment information can also be included, such as
inventory occupancy and profitability.

  * •

The action signifies the quantity of SKUs to be restocked. The system offers
various built-in action-to-replenishment converters for enhanced
generalization. In subsequent experiments, the average demand is used as a
factor to establish the purchasing quantity.

  * •

The reward is also configurable, with various built-in options provided. In
the following experiments, we use the profit of each SKU in each warehouse as
reward.

The details regarding observation state, reward, and action settings can be
found in Appendix B.

##  4 Core features of MABIM

Building on the MARL formulation for inventory management, MABIM provides a
high degree of flexibility to tackle different challenges frequently
encountered in MARL research (Section 4.1). To further enhance MARL research,
MABIM also offers some other features such as efficiency, ease of use, and
fidelity (Section 4.2).

###  4.1 Tasks with configurable challenges

Compared to other inventory management environments, MABIM provides greater
configuration flexibility, enabling the simulation of a wide range of
challenges for MARL algorithms. This adaptability allows for customization
tailored to specific use cases, enhancing the applicability of algorithms
across various challenging tasks. Some typical challenges include:

  * •

Scaling up: In the context of MARL, scaling up refers to the impact of
numerous agents on training results and efficiency. While most recent MARL
benchmarks do not support a large number of agents, our environment can
support thousands of agents.

  * •

Cooperation: Cooperation between agents involves collaboration between
warehouses at adjacent echelons. To satisfy consumer demands, deeper
cooperation is needed in longer chains. Incentives, such as product profits or
backlog penalties, ensure efficient product transfer.

  * •

Competition: Competition between agents arises when they vie for limited
warehouse capacity. In our environment, reduced capacity or increased storage
costs stimulate agents to compete for storage space.

  * •

Non-stationary contexts: Non-stationary contexts present a challenge for MARL,
as they require the development of algorithms capable of learning in dynamic
environments with fluctuating conditions. Examples include entirely new
contexts to test the algorithm’s generalization ability or noisy contexts to
evaluate its robustness. These non-stationary factors may stem from external
or internal sources. In the MABIM framework, the demand represents external
context, and the features of SKUs serve as internal context.

The challenges mentioned above can be managed by adjusting parameters,
allowing for versatile combinations. Altering parameters such as the number of
SKUs, warehouses, and warehouse capacity creates challenging environments to
test competition, cooperation, and scaling up, as illustrated in Figure 2.

MABIM contains a total of 51 built-in tasks with various challenges. For more
details, refer to Appendix C.

Figure 2: Combined challenge. $\uparrow$, $\downarrow$, and ~ signify
increasing, decreasing, and keep steady.

###  4.2 Other Features

In addition to processing various challenges with configurable difficulties,
MABIM possesses several noteworthy features worth mentioning.

#### Efficient implementation.

MABIM efficiently stores all SKU features and performs operations such as SKU
initialization, purchasing, and selling in matrices. This approach ensures
system efficiency and resource conservation.

#### Easy of use.

MABIM utilizes a unified Gym[32] interface and offers wrappers for common OR
and RL algorithms. This consistency simplifies integration with other MARL
frameworks and reduces the learning curve for researchers. Moreover, a
visualization tool for analyzing SKU and warehouse states is provided. See
Appendix D for more details.

#### High fidelity.

MABIM aims to simulate real-world inventory management across various aspects
to ensure more applicable solutions for actual production scenarios. Key
features include the use of over 2000 real demand data of SKUs, running rule-
based algorithms for warmup to avoid cold starts, providing different overflow
strategies for processing overflow SKUs rather than discarding them directly,
and incorporating an acceptance strategy that allocates storage space based on
volume ratios to ensure fairness.

##  5 Experiment

###  5.1 Experiment Settings

During experiments, we compare the performance of OR and MARL algorithms. OR
algorithms include base stock (BS) and ($s,S$), and MARL algorithms include
IPPO[53] and QTRAN[52]. For more details about the algorithm and hyper-
parameter, see Appendix A and Appendix B.

We present an overview of the experiment settings in Table 3. In our
experiments, challenging tasks are derived from a standard task that follows
general inventory management logic with realistic data settings. By modifying
the setting, we develop versatile challenging tasks that primarily focus on
scaling up, cooperation, competition, generalization and robustness. For more
details on the environment design, refer to AppendixC.

Table 3: Experiments settings. "-" means the value is the same as the standard
task, "stable" refers to stable contexts from real data, "add gap" implies
constant variance with random mean changes, "add noise" keeps the mean
constant but adds noise to increase variance, and "#SKU * N" indicates N times
the number of SKUs.

Task | #Echelon | #SKU | Capacity | Train contexts | Test contexts
---|---|---|---|---|---
Standard | 1 | 200 | #SKU * 100 | Stable | Stable
Scaling up | - | $500,1000,2000$ | - | - | -
Cooperation | 2, 3 | - | - | - | -
Competition | - | - | #SKU * 50, #SKU * 25 | - | -
Generalization | - | - | - | - | Add gap
Robustness | - | - | - | Add noise | Add noise

We calculate the mean profit over all SKUs and warehouses, and then sum these
mean profits over time steps to use as the evaluation metric. For the MARL
algorithm, we select the best-performing model from the validation set and
evaluate it on the test set. All training jobs are conducted using a single
A100 graphics card.

###  5.2 Scaling up

We present the results for scaling up experiments in Table 4. The IPPO
algorithm performs effectively when there is a small number of SKUs. However,
its performance deteriorates as the number of agents increases, and it fails
entirely when the number of SKUs reaches 2000. For QTRAN, although it yields
good results, the training process demands significant time and GPU memory,
making it resource-intensive.

Table 4: Result of scaling up tasks.

Experiment | Mean profit | Time usage | Memory usage
---|---|---|---
BS static | BS dynamic | ($s,S$) static | ($s,S$) hindsight | IPPO | QTRAN | IPPO | QTRAN | IPPO | QTRAN
200 SKUs | 6.29k | 6.32k | 8.18k | 8.81k | 9.83k | 9.07k | 11.47h | 12.80h | 3.15G | 5.63G
500 SKUs | 6.93k | 7.71k | 9.09k | 10.13k | 11.21k | 11.11k | 16.90h | 18.15h | 5.79G | 11.91G
1000 SKUs | 5.64k | 6.37k | 7.92k | 8.85k | 8.2k | 9.44k | 23.60h | 34.58h | 10.39G | 22.61G
2000 SKUs | 4.48k | 5.58k | 6.69k | 7.97k | 1.96k | 8.32k | 31.23h | 52.28h | 19.77G | 44.31G

We examine the impact of scaling up on the MARL algorithm by displaying the
profit on the test set during training iterations in Figure 3. As the number
of SKUs increases, finding an optimal strategy for IPPO becomes more
challenging, resulting in convergence failure at 2,000 agents, even after 5
million iterations. Although QTRAN exhibits better performance, it encounters
substantial training instability, which could present risks in real-world
applications. This highlights the difficulties associated with increasing
agent numbers in the training process.

Figure 3: Mean profit in scaling up tasks.

###  5.3 Competition

We present the competition results in Table 5. When capacity becomes lower,
competition for capacity is more incentivized, leading to a greater impact on
the base stock’s static mode and the IPPO algorithm. As a result, these
methods may face challenges in maintaining optimal performance under
constrained capacity conditions.

Table 5: Result of competition tasks. Experiment | BS static | BS dynamic | ($s,S$) static | ($s,S$) hindsight | IPPO | QTRAN
---|---|---|---|---|---|---
Normal capacity | 6.29k | 6.32k | 8.18k | 8.81k | 9.83k | 9.07k
Lower capacity | 5.01k | 3.64k | 6.13k | 7.06k | 6.46k | 6.74k
Lowest capacity | -7.4k | 1.42k | 3.32k | 4.55k | -1.9k | 2.04k

We analyze algorithm policies by plotting them in Figure 4. As capacity
decreases, BS strategy stays unchanged since it calculates stock levels per
SKU without considering overall capacity, causing overflow and higher costs.
IPPO reduces replenishment quantity, potentially avoiding short-term purchases
to prevent losses but not maximizing long-term profit. Both ($s,S$) static and
QTRAN algorithms show better stability in performance.

Figure 4: Policies for competition tasks. The demand, replenishment, and
overflow represent the total quantity encompassing all SKUs.

###  5.4 Cooperation

We present the cooperation results in Table 6. To assess the collaboration
between upstream and downstream operations, we design two-echelon and three-
echelon inventory management models. The MARL algorithms is not as effect as
in single echelon, especially IPPO. To determine if learning both upstream and
downstream strategies simultaneously results in poor performance, we introduce
IPPO+BS and QTRAN+BS algorithms. These algorithms utilize the IPPO/QTRAN
algorithm for the upstream warehouse and the BS algorithm for warehouses in
other warehouse. The combined algorithm’s performance significantly surpasses
that of the pure OR and MARL algorithms. Based on these observations, we
hypothesize that MARL performs well in a single warehouse, but encounters
difficulties when managing both types of interactions.

Table 6: Result of cooperation tasks.

Experiment | BS static | BS dynamic | ($s,S$) static | ($s,S$) hindsight | IPPO | IPPO + BS | QTRAN | QTRAN + BS
---|---|---|---|---|---|---|---|---
Single echelon | 6.29k | 6.32k | 8.18k | 8.81k | 9.83k | - | 9.07k | -
2 echelons | 9.15k | 7.76k | 9.1k | 9.68k | 6.72k | 9.86k | 9.88k | 10.54k
3 echelons | 8.45k | 7.74k | 7.92k | 8.27k | 4.25k | 10.14k | 8.09k | 9.18k

We analyze algorithm policies by plotting them in Figure 5. Pure IPPO
algorithm fulfill only a small demand portion. When the downstream warehouse
strategy is fixed with BS, the upstream warehouse’s demand fulfillment
improves, enhancing overall performance. This indicates that insufficient
information exchange between upstream and downstream entities results in less
effective multi-layer strategy cooperation.

Figure 5: Policies for cooperation tasks. The demand, replenishment and sale
represent the total quantity encompassing all SKUs.

###  5.5 Non-stationary context

In MABIM, we take into account context factors such as demand, selling price,
procurement cost, lead time, and more. In this experiment, we use demand as
the context and design tests to evaluate the algorithm’s capabilities for
generalization and robustness. In generalization experiments, we apply an
offset to test set demand, creating a new pattern unseen in training. In
robustness experiments, we add random noise to demand in the entire dataset,
testing the model’s ability to handle fluctuations.

As ($s,S$) hindsight algorithm directly optimizes on test data, hence is able
to achieve the best performance. Its result will be used as the denominator to
normalize results of other algorithms for better comparison. See Appendix E
for more details on non-stationary context tasks and results.

We display the relative performance of different algorithms in Figure 6. As
the gap and noise levels increase, each algorithm is impacted to varying
extents. IPPO outperforms other algorithms, whereas the static OR algorithm
fares the worst, particularly in generalization tasks. This result illustrates
that MABIM is capable of effectively measuring the generalization and
robustness of a strategy.

Figure 6: Relative profit of ($s,S$) hindsight.

##  6 Conclusion

In this paper, we introduce a MARL benchmark called MABIM, which can simulate
a diverse range of challenging scenarios based on the inventory management
problem. By utilizing MABIM, we develop various tasks that reveal limitations
in existing MARL algorithms, such as unstable training with numerous agents,
suboptimal performance under limited source, difficulties in cooperation with
upstream and downstream, and the necessity for enhanced generalization and
robustness. These findings highlight the importance of developing advanced
MARL algorithms and demonstrate MABIM’s potential as a valuable MARL
benchmark. We believe that MABIM will significantly contribute to the progress
of both inventory management and MARL research.

In future work, we aim to address the issues found in MABIM and expand its
capabilities to better support MARL research. Potential extensions involve
constructing tree-based or graph-based inventory management structures to
evaluate agent communication abilities. Additionally, we will hide some SKU
features to assess the MARL algorithm performance in partially observable
settings.

## References

  * [1] Richard S Sutton and Andrew G Barto.  Reinforcement Learning: An Introduction.  MIT press, 2018.
  * [2] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of go without human knowledge.  Nature, 550(7676):354–359, 2017.
  * [3] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  Nature, 575(7782):350–354, 2019.
  * [4] Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al.  Starcraft II: A new challenge for reinforcement learning.  arXiv preprint arXiv:1708.04782, 2017.
  * [5] Kun Shao, Yuanheng Zhu, and Dongbin Zhao.  Starcraft micromanagement with reinforcement learning and curriculum transfer learning.  IEEE Transactions on Emerging Topics in Computational Intelligence, 3(1):73–84, 2018.
  * [6] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al.  Dota 2 with large scale deep reinforcement learning.  arXiv preprint arXiv:1912.06680, 2019.
  * [7] Deheng Ye, Guibin Chen, Wen Zhang, Sheng Chen, Bo Yuan, Bo Liu, Jia Chen, Zhao Liu, Fuhao Qiu, Hongsheng Yu, et al.  Towards playing full moba games with deep reinforcement learning.  Advances in Neural Information Processing Systems, 33:621–632, 2020\.
  * [8] SPK Spielberg, RB Gopaluni, and PD Loewen.  Deep reinforcement learning approaches for process control.  In 2017 6th international symposium on advanced control of industrial processes, pages 201–206. IEEE, 2017.
  * [9] Rui Nian, Jinfeng Liu, and Biao Huang.  A review on reinforcement learning: Introduction and applications in industrial process control.  Computers & Chemical Engineering, 139:106886, 2020.
  * [10] Sander Adam, Lucian Busoniu, and Robert Babuska.  Experience replay for real-time reinforcement learning control.  IEEE Transactions on Systems, Man, and Cybernetics, Part C, 42(2):201–212, 2011.
  * [11] ATD Perera and Parameswaran Kamalaruban.  Applications of reinforcement learning in energy systems.  Renewable and Sustainable Energy Reviews, 137:110618, 2021.
  * [12] Andrew Tittaferrante and Abdulsalam Yassine.  Multiadvisor reinforcement learning for multiagent multiobjective smart home energy control.  IEEE Transactions on Artificial Intelligence, 3(4):581–594, 2021\.
  * [13] B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez.  Deep reinforcement learning for autonomous driving: A survey.  IEEE Transactions on Intelligent Transportation Systems, 2021.
  * [14] Rui Zheng, Chunming Liu, and Qi Guo.  A decision-making method for autonomous vehicles based on simulation and reinforcement learning.  In 2013 International Conference on Machine Learning and Cybernetics, volume 1, pages 362–369. IEEE, 2013.
  * [15] Zhenhai Gao, Tianjun Sun, and Hongwei Xiao.  Decision-making method for vehicle longitudinal automatic driving based on reinforcement q-learning.  International Journal of Advanced Robotic Systems, 16(3):1729881419853185, 2019.
  * [16] Petter N Kolm and Gordon Ritter.  Modern perspectives on reinforcement learning in finance.  Modern Perspectives on Reinforcement Learning in Finance. The Journal of Machine Learning in Finance, 1(1), 2020.
  * [17] Arthur Charpentier, Romuald Elie, and Carl Remlinger.  Reinforcement learning in economics and finance.  Computational Economics, pages 1–38, 2021.
  * [18] Yuh-Jong Hu and Shang-Jen Lin.  Deep reinforcement learning for optimizing finance portfolio management.  In 2019 Amity International Conference on Artificial Intelligence, pages 14–20. IEEE, 2019.
  * [19] Xinshi Chen, Shuang Li, Hui Li, Shaohua Jiang, Yuan Qi, and Le Song.  Generative adversarial user model for reinforcement learning based recommendation system.  In International Conference on Machine Learning, pages 1052–1061. PMLR, 2019.
  * [20] Xueying Tang, Yunxiao Chen, Xiaoou Li, Jingchen Liu, and Zhiliang Ying.  A reinforcement learning approach to personalized learning recommendation systems.  British Journal of Mathematical and Statistical Psychology, 72(1):108–135, 2019.
  * [21] Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer.  Cooperative multi-agent control using deep reinforcement learning.  In Autonomous Agents and Multiagent Systems: AAMAS 2017 Workshops, pages 66–83. Springer, 2017.
  * [22] José R Vázquez-Canteli, Jérôme Kämpf, Gregor Henze, and Zoltan Nagy.  CityLearn v1.0: An OpenAI gym environment for demand response with deep reinforcement learning.  In Proceedings of the 6th ACM International Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation, pages 356–357, 2019.
  * [23] Daniel Krajzewicz.  Traffic simulation with sumo–simulation of urban mobility.  Fundamentals of traffic simulation, pages 269–293, 2010.
  * [24] Xiao Yang, Weiqing Liu, Dong Zhou, Jiang Bian, and Tie-Yan Liu.  Qlib: An AI-oriented quantitative investment platform.  arXiv preprint arXiv:2009.11189, 2020.
  * [25] David Rohde, Stephen Bonner, Travis Dunlop, Flavian Vasile, and Alexandros Karatzoglou.  Recogym: A reinforcement learning environment for the problem of product recommendation in online advertising.  arXiv preprint arXiv:1808.00720, 2018.
  * [26] Lucian Buşoniu, Robert Babuška, and Bart De Schutter.  Multi-agent reinforcement learning: An overview.  Innovations in multi-agent systems and applications-1, pages 183–221, 2010.
  * [27] Pablo Hernandez-Leal, Bilal Kartal, and Matthew E Taylor.  A survey and critique of multiagent deep reinforcement learning.  Autonomous Agents and Multi-Agent Systems, 33(6):750–797, 2019\.
  * [28] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang.  Mean field multi-agent reinforcement learning.  In International conference on machine learning, pages 5571–5580. PMLR, 2018.
  * [29] Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson.  Learning to communicate with deep multi-agent reinforcement learning.  Advances in Neural Information Processing Systems, 29, 2016.
  * [30] Tianshu Chu, Sandeep Chinchali, and Sachin Katti.  Multi-agent reinforcement learning for networked system control.  arXiv preprint arXiv:2004.01339, 2020.
  * [31] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta.  Robust adversarial reinforcement learning.  In International Conference on Machine Learning, pages 2817–2826. PMLR, 2017.
  * [32] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  OpenAI Gym.  arXiv preprint arXiv:1606.01540, 2016.
  * [33] Thomas Dietterich, George Trimponias, and Zhitang Chen.  Discovering and removing exogenous state variables and rewards for reinforcement learning.  In International Conference on Machine Learning, pages 1262–1270. PMLR, 2018.
  * [34] Chuheng Zhang, Yitong Duan, Xiaoyu Chen, Jianyu Chen, Jian Li, and Li Zhao.  Towards generalizable reinforcement learning for trade execution.  In IJCAI, 2023.
  * [35] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson.  The starcraft multi-agent challenge.  arXiv preprint arXiv:1902.04043, 2019.
  * [36] Karol Kurach, Anton Raichuk, Piotr Stańczyk, Michał Zając, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al.  Google research football: A novel reinforcement learning environment.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4501–4510, 2020.
  * [37] Ming Zhang, Shenghan Zhang, Zhenjie Yang, Lekai Chen, Jinliang Zheng, Chao Yang, Chuming Li, Hang Zhou, Yazhe Niu, and Yu Liu.  Gobigger: A scalable platform for cooperative-competitive multi-agent interactive simulation.  In The Eleventh International Conference on Learning Representations, 2023.
  * [38] Igor Mordatch and Pieter Abbeel.  Emergence of grounded compositional language in multi-agent populations.  In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
  * [39] Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierre-Alexandre Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson.  Facmac: Factored multi-agent centralised policy gradients.  Advances in Neural Information Processing Systems, 34:12208–12221, 2021.
  * [40] David Ha and Yujin Tang.  Collective intelligence for deep learning: A survey of recent developments.  Collective Intelligence, 1(1):26339137221114874, 2022.
  * [41] Tongzhou Mu, Zhan Ling, Fanbo Xiang, Derek Yang, Xuanlin Li, Stone Tao, Zhiao Huang, Zhiwei Jia, and Hao Su.  Maniskill: Generalizable manipulation skill benchmark with large-scale demonstrations.  arXiv preprint arXiv:2107.14483, 2021.
  * [42] Christian D Hubbs, Hector D Perez, Owais Sarwar, Nikolaos V Sahinidis, Ignacio E Grossmann, and John M Wassick.  Or-gym: A reinforcement learning library for operations research problems.  arXiv preprint arXiv:2008.06319, 2020.
  * [43] Leluc Remi, Kadoche Elie, Bertoncello Antoine, and Gourv enec Sebastien.  Marlim: Multi-agent reinforcement learning for inventory management.  Advances in Neural Information Processing RL4RealLife Workshop, 2022\.
  * [44] Puppala Sridhar, CR Vishnu, and R Sridharan.  Simulation of inventory management systems in retail stores: A case study.  Materials Today: Proceedings, 47:5130–5134, 2021.
  * [45] Sridhar Tayur, Ram Ganeshan, and Michael Magazine.  Quantitative models for supply chain management, volume 17.  Springer Science & Business Media, 2012.
  * [46] John W Toomey.  Inventory management: principles, concepts and techniques, volume 12.  Springer Science & Business Media, 2000.
  * [47] Hartmut Stadtler.  Supply chain management: An overview.  Supply chain management and advanced planning: Concepts, models, software, and case studies, pages 3–28, 2014.
  * [48] Kenneth J Arrow, Theodore Harris, and Jacob Marschak.  Optimal inventory policy.  Econometrica: Journal of the Econometric Society, pages 250–272, 1951.
  * [49] Alan S Blinder.  Inventory theory and consumer behavior.  Harvester Wheatsheaf, 1990.
  * [50] M-A Dittrich and S Fohlmeister.  A deep q-learning-based optimization of the inventory control in a linear process chain.  Production Engineering, 15:35–43, 2021.
  * [51] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson.  Monotonic value function factorisation for deep multi-agent reinforcement learning.  The Journal of Machine Learning Research, 21(1):7234–7284, 2020\.
  * [52] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi.  Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning.  In International conference on machine learning, pages 5887–5896. PMLR, 2019.
  * [53] Y. Zheng, X. Chen, J. Wang, and M. Chen.  A deep reinforcement learning approach for inventory management in retail.  Industrial Management & Data Systems, 2020.
  * [54] Yuandong Ding, Mingxiao Feng, Guozi Liu, Wei Jiang, Chuheng Zhang, Li Zhao, Lei Song, Houqiang Li, Yan Jin, and Jiang Bian.  Multi-agent reinforcement learning with shared resources for inventory management.  In Advances in Neural Information Processing RL4RealLife Workshop, 2022.

##  Appendix A OR Algorithm

In our experiment, we use 2 classical algorithms, base stock policy and
($s,S$) policy.

###  A.1 Base stock policy

The base stock policy is a simple and efficient inventory management strategy,
in which orders are placed to replenish the inventory when the stock quantity
falls below the base stock level. This policy is considered a lower bound due
to its simplicity and speed. The base stock level is calculated through
programming, as demonstrated in Equation A.1.

$\begin{split}{\bf max}\quad o_{i,j}^{t}&=\bar{p}_{i,j}\cdot
S_{i,j}^{t}-\bar{c}_{i,j}\cdot S_{i+1,j}^{t}-\bar{h}_{i,j}\cdot
I_{i,j}^{t+1}-\bar{c}_{i,j}\cdot T_{i,j}^{0}-\bar{c}_{i,j}\cdot I_{i,j}^{0}\\\
{\bf s.t}\quad
I_{i,j}^{t+1}&=I_{i,j}^{t}+S_{i+1,j}^{t-\bar{L}_{i,j}}-S_{i,j}^{t}\\\ \quad
T_{i,j}^{t+1}&=T_{i,j}^{t}-S_{i+1,j}^{t-\bar{L}_{i,j}}+S_{i+1,j}^{t}\\\
S_{i,j}^{t}&=min(I_{i,j}^{t},R_{i,j}^{t})\\\
T_{i,j}^{0}&=\sum_{t=-\bar{L}_{i,j}}^{-1}S_{i+1,j}^{t}\\\
z_{i,j}&=I_{i,j}^{t+1}+S_{i+1,j}^{t}+T_{i,j}^{t}\\\
z_{i,j}&\in\mathbb{R^{+}}\\\ \end{split}$

In the equations mentioned above, $i$, $j$, and $t$ represent the indices of
the warehouse, SKU, and time step, respectively. We also use the mean values
$\bar{p}$, $\bar{c}$, $\bar{h}$, and $\bar{L}$ to denote the average selling
price, procurement cost, holding cost, and lead time, respectively. The
variables $S$, $R$, $I$, and $T$ represent the sale quantity, replenishment
quantity, quantity in stock, and quantity in transit, respectively. Lastly,
$o_{i,j}^{t}$ is the profit as the objective, and $z_{i,j}$ represents the
base stock level, which is independently calculated for each product.

In the static mode, all base stock levels are calculated using historical data
from the training set and consistently applied to the test set. These levels
remain fixed throughout the test period. In the dynamic mode, the base stock
levels are calculated using historical data and are updated at regular
intervals. The levels are recalculated based on the updated historical data.

###  A.2 ($s,S$) Policy

The ($s,S$) policy is an effective inventory management strategy wherein
orders are placed to replenish inventory when the stock quantity reaches or
falls below the base reorder level, denoted as $s$. The policy aims to restore
the inventory to its maximum level, represented by $S$. Due to its efficacy,
the ($s,S$) policy serves as a powerful baseline, and an optimal ($s,S$) pair
is sought for each SKU in the dataset. In static mode, ($s,S$) is searched in
train set and in hindsight mode, ($s,S$) is searched in test set.

##  Appendix B MARL Algorithms

In the training process of the MARL algorithm, some implementation details
include:

  * •

The observation encompasses both SKU features and warehouse states. SKU
features consist of quantity in stock, selling price, procurement cost, mean
and standard deviation of historical demand, holding cost, order cost, and
lead time. Warehouse states include total quantity in stock and remaining
space, total profit in stock, total quantity in transit, and total profit in
transit. All these features are normalized for optimal performance.

  * •

During the training process, state and reward values are normalized using a
rolling average and standard deviation. This approach enhances the model’s
learning and convergence capabilities.

  * •

For replenishment actions, we employ multiples of the average demanded
quantity from the past 21 days, which ensures that inventory levels are
maintained based on recent demand trends, resulting in more effective
inventory management decisions.

Table 7 lists the training-related hyperparameters.

Table 7: Hyperparameters for MARL. Hyperparameter | IPPO | QTRAN
---|---|---
#Epochs | 5020000 | 5020000
Discount rate | 0.985 | 0.985
Optimizer | Adam | Adam
Optimizer alpha | 0.99 | 0.99
Optimizer eps | 1e-5 | 1e-5
Learning rate | 5e-4 | 5e-4
Grad norm clip | 10 | 10
Horizon | 21 | 21
Eps clip | 0.15 | -
Critic coef | 0.5 | -
Entropy coef | 0 | -
Accumulated episodes | 1 | 8

##  Appendix C Details of Tasks Design

#### Standard task

The design principles behind these environment parameters ensure that more
reasonable purchasing strategies yield higher benefits. A reasonable strategy
encompasses the following factors:

  * •

Most products have a purchase frequency of 2 to 10 steps.

  * •

There is no optimal strategy for products without replenishment.

  * •

In most cases, commodities are not purchased in excessive quantities at once
(no more than 30 times the historical average daily sales volume).

  * •

The holding and storage costs account for 10% to 25% of the gross merchandise
volume (GMV) for one year, where
$GMV_{i,j}=\sum_{t=1}^{365}{s_{i,j}^{t}*p_{i,j}^{t}}$.

Based on ($s,S$) policy, we search the following hyperparameter as standard
configuration in Table 8. Rest feature including selling price, procurement
cost, leading time are real dynamic data from external file.

Table 8: Standard configuration. Hyperparameter | value
---|---
#SKU | 200
#Warehouse | 1
Capacity | 20000
Order cost | 10
Holding cost | 0.002 + 0.001
Backlog cost | 0.1 * (selling price - procurement cost)
Overflow cost | 0.5 * procurement cost

#### Total tasks

Based on the standard task, we build-in total of 51 tasks in MABIM. Seen in
Table 9

Table 9: Total tasks. "$+$" indicates the extent to which the challenge is
involved.

Task name | Scaling up | Cooperation | Competition | Generalization | Robustness | More challenge
---|---|---|---|---|---|---
sku50.single_store.standard |  |  |  |  |  |
sku50.2_stores.standard |  | $+$ |  |  |  |
sku50.3_stores.standard |  |  $+$ $+$ |  |  |  |
sku100.single_store.standard |  |  |  |  |  |
sku100.2_stores.standard |  | $+$ |  |  |  |
sku100.3_stores.standard |  |  $+$ $+$ |  |  |  |
sku200.single_store.standard |  |  |  |  |  |
sku200.2_stores.standard |  | $+$ |  |  |  |
sku200.3_stores.standard |  |  $+$ $+$ |  |  |  |
sku500.single_store.standard |  |  |  |  |  |
sku500.2_stores.standard | $+$ | $+$ |  |  |  |
sku500.3_stores.standard | $+$ |  $+$ $+$ |  |  |  |
sku1000.single_store.standard |  |  |  |  |  |
sku1000.2_stores.standard |  $+$ $+$ | $+$ |  |  |  |
sku1000.3_stores.standard |  $+$ $+$ |  $+$ $+$ |  |  |  |
sku2000.single_store.standard |  |  |  |  |  |
sku2000.2_stores.standard |  $+$ $+$ $+$ | $+$ |  |  |  |
sku2000.3_stores.standard |  $+$ $+$ $+$ |  $+$ $+$ |  |  |  |
sku200.single_store.lower_capacity |  |  | $+$ |  |  |
sku200.single_store.lowest_capacity |  |  |  $+$ $+$ |  |  |
sku200.2_stores.lower_capacity |  | $+$ | $+$ |  |  |
sku200.2_stores.lowest_capacity |  | $+$ |  $+$ $+$ |  |  |
sku200.3_stores.lower_capacity |  |  $+$ $+$ | $+$ |  |  |
sku200.3_stores.lowest_capacity |  |  $+$ $+$ |  $+$ $+$ |  |  |
sku200.single_store.dynamic_vlt |  |  |  |  | $+$ |
sku200.2_stores.dynamic_vlt |  | $+$ |  |  | $+$ |
sku200.3_stores.dynamic_vlt |  |  $+$ $+$ |  |  | $+$ |
sku200.single_store.increase_demand |  |  |  | $+$ | $+$ |
sku200.single_store.decrease_demand |  |  |  | $+$ | $+$ |
sku200.single_store.higher_backlog |  |  |  |  |  | higher constraints
sku200.single_store.highest_backlog |  |  |  |  |  | highest constraints
sku200.single_store.higher_holding_cost |  |  | $+$ |  |  |
sku200.single_store.highest_holding_cost |  |  | $+$ |  |  |
sku200.single_store.higher_order_cost |  |  |  |  |  | lower action frequency
sku200.single_store.highest_order_cost |  |  |  |  |  | lowest action frequency
sku200.single_store.low_profit |  |  |  |  |  | low action space
sku200.single_store.high_profit |  |  |  |  |  | high action space
sku200.single_store.higher_overflow_cost |  |  |  |  |  | higher punishment
sku200.single_store.highest_overflow_cost |  |  |  |  |  | highest punishment
sku200.single_store.add_gap_1 |  |  |  | $+$ |  |
sku200.single_store.add_gap_2 |  |  |  | $+$ |  |
sku200.single_store.add_gap_3 |  |  |  |  $+$ $+$ |  |
sku200.single_store.add_gap_4 |  |  |  |  $+$ $+$ |  |
sku200.single_store.add_gap_5 |  |  |  |  $+$ $+$ $+$ |  |
sku200.single_store.add_gap_6 |  |  |  |  $+$ $+$ $+$ |  |
sku200.single_store.add_noise_1 |  |  |  |  | $+$ |
sku200.single_store.add_noise_2 |  |  |  |  | $+$ |
sku200.single_store.add_noise_3 |  |  |  |  |  $+$ $+$ |
sku200.single_store.add_noise_4 |  |  |  |  |  $+$ $+$ |
sku200.single_store.add_noise_5 |  |  |  |  |  $+$ $+$ $+$ |
sku200.single_store.add_noise_6 |  |  |  |  |  $+$ $+$ $+$ |

##  Appendix D Visualization

MABIM displays the status of each product in every warehouse during each step,
along with the overall warehouse status, in the form of a webpage, as shown in
Figure 7. The information provided includes demand, sales, arrivals,
acceptance, replenishment, excess, inventory, items in transit, and profit, as
well as procurement costs, backlog costs, order costs, and holding costs.

Figure 7: States of SKUs.

##  Appendix E Non-stationary tasks and results

Table 10: Result of non-stationary context tasks.

Experiment | Gap level | BS static | BS dynamic | ($s,S$) static | ($s,S$) hindsight | IPPO | QTRAN
---|---|---|---|---|---|---|---
Generalization | 0 (no gap) | 6.29k | 6.32k | 8.18k | 8.81k | 9.83k | 9.07k
1 | 4.6k | 4.2k | 4.54k | 6.01k | 6.89k | 4.46k
2 | 4.94k | 6.26k | 4.54k | 9.74k | 7.54k | 6.88k
3 | 4.31k | 6.5k | -1.96k | 9.89k | 7.75k | 6.9k
4 | 4.56k | 11.28k | -18.66k | 16.31k | 12.66k | 9.24k
5 | 5.69k | 13.21k | -18.43k | 18.74k | 14.51k | 10.65k
6 | 5.48k | 15.85k | -48.52k | 21.72k | 16.14k | 9.68k
Experiment | Noise level | BS static | BS dynamic | ($s,S$) static | ($s,S$) hindsight | IPPO | QTRAN
Robustness | 0(no noise) | 6.29k | 6.32k | 8.18k | 8.81k | 9.83K | 9.07K
1 | 4.22K | 3.83K | 5.11K | 6.01K | 6.47K | 5.96K
2 | 4.48K | 5.25K | 6.64K | 7.85K | 8.02K | 6.51K
3 | 4.36K | 6.62K | 8.1K | 9.89K | 9.81K | 7.31K
4 | 4.92K | 7.57K | 8.3K | 16.31K | 9.2K | 8.1K
5 | 5.01K | 9.31K | 9.31K | 18.74K | 10.01K | 9.44K
6 | 7.26K | 10.48K | 10.14K | 21.72K | 12.15K | 9.84k