# Continual Match Based Training in Pommerman: Technical Report

Peng Peng* * Equal contribution. Inspir.ai, Beijing, China  Liang Pang*
Institute of Computing Technology, CAS, Beijing, China  Yufeng Yuan  Beijing
Normal University, Beijing, China  Chao Gao  Inspir.ai, Beijing, China

###### Abstract

Continual learning is the ability of agents to improve their capacities
throughout multiple tasks continually. While recent works in the literature of
continual learning mostly focused on developing either particular loss
functions or specialized structures of neural network explaining the episodic
memory or neural plasticity, we study continual learning from the perspective
of the training mechanism. Specifically, we propose a COnitnual Match BAsed
Training (COMBAT) framework for training a population of advantage-actor-
critic (A2C) agents in Pommerman, a partially observable multi-agent
environment with no communication.

Following the COMBAT framework, we trained an agent, namely, _Navocado_ , that
won the title of the top 1 learning agent in the NeurIPS 2018 Pommerman
Competition. Two critical features of our agent are worth mentioning. Firstly,
our agent did not learn from any demonstrations. Secondly, our agent is highly
reproducible. As a technical report, we articulate the design of state space,
action space, reward, and most importantly, the COMBAT framework for our
Pommerman agent. We show in the experiments that Pommerman is a perfect
environment for studying continual learning, and the agent can improve its
performance by continually learning new skills without forgetting the old
ones. Finally, the result in the Pommerman Competition verifies the robustness
of our agent when competing with various opponents.

##  I Introduction

Pommerman [17] is a multi-agent environment based on the classic console game
Bomberman. Every battle starts on a randomly drawn symmetric 11x11 grid with
four agents each initially located in one of the four corners. On every turn,
each agent can execute one of the six actions: _Stop, Up, Down, Left, Right
and Lay a bomb_. Besides the agents, each cell on the grid can be a passage, a
wooden wall, or rigid walls. Both rigid and wooden walls are impassible,
whereas wooden walls are destructible with the bomb explosion. After a wooden
wall was destroyed, there is a 50% for it to become a passage and another 50%
for it to reveal one of the hidden power-ups. There are three kinds of power-
ups in games: _Extra Ammo, Extra Range and Can Kick_ which increases the
agent’s current ammo by one, increases its bomb blast range by one and enables
an agent to kick a bomb, respectively. There are three variants of the
Pommerman environment, i.e., FFA(Free For All), Team and Team Radio. The
NeurIPS 2018 Pommerman Competition is about the Team environment, where each
participant controls two agents initially located in the corner at the same
diagonal as a team, and each agent only observes a 7x7 area centered on its
position.

There are several challenges for learning an agent in the Pommerman
environment. First of all, the variance of the game episode length is high. A
battle can have as many as several hundred steps when two matched teams play
against each other, whereas it may also end shortly with dozens of steps if
two teams are badly mismatched. Secondly, the reward signal obtained at the
end of each battle is particularly sparse and delayed. Since the Team
environment is an environment mixed of the competitive and cooperative agents,
the usual way of learning from such sparse and delayed reward signal is far
away from enough. Thirdly, the features of partially observable and no
communication in the Team environment makes it hard for an agent to plan
without the full view of the game. Fourth and most importantly, there are so
many skills that an agent can learn in such a complex environment in order to
play well against different types of opponents. Therefore, we regard the
Pommerman environment as a good test field of continual learning [15, 22, 5].

In this paper, we propose a COnitnual Match BAsed Training (COMBAT) framework
for continual learning in Pommerman. The idea is inspired by the Population
Based Training (PBT) [6], where a population of agents is optimized
asynchronously in parallel with a fixed budget of computational resources.
Similar to PBT, COMBAT is a meta-optimization technique, which balances the
use of computational resources between exploring new hyperparameters and
exploiting the best agent. However, there are two significant differences
between COMBAT and PBT. On the one hand, unlike PBT, COMBAT does not evaluate
each agent’s performance in the population independently. Specifically, COMBAT
uses a round-robin method to generate a schedule of matches, according to
which each agent in the population competes with a specified opponent. We
update the ELO score [1] to evaluate each agent according to the match results
and the ranking list are updated accordingly. As time evolves, only the agents
at the top of the ranking list have an opportunity to learn continually,
whereas those at the bottom of the ranking list will be eliminated from the
population. Through such a competition based training mechanism, agents with
better hyperparameters stand out, and the population of agents evolved into a
more and more competitive community over time. On the other hand, COMBAT stops
exploiting strong agents with the same group of hyperparameters after the
performance of these agents was converged for a certain amount of period, but
continue to train them by exploring new hyperparameters and reward functions.
The intuition behind is that for any complex problem such as Pommerman, the
convergence of a particular partially observable Markov decision making
(POMDP) [4, 12] or stochastic game (SG) [11, 13] of the problem does not mean
the problem has been solved. Instead, by updating hyperparameters and reward
functions, it is possible for the agent to retain the hope of reaching the
global optimal solution of the problem.

The hyperparameter fine-tuned in our implementation is the discount factor,
which is crucial for our agent to keep on improving when the convergence of
local optimal is met. Since the goal of optimization is the exponentially
decayed sum of future rewards, weighted by the exponentially decayed discount
factor, the value of the discount factor is closely related to the objective
of the optimization algorithm. More specifically, the discount factor
determines how long the future rewards reach its half-life. For example, when
the discount factor is 0.9, the future reward in after $7$ steps is a half-
life of its original value; when the discount factor is 0.99, the future
reward after $68$ steps is a half-life of its original value. Empirically, we
found that with different discount factors, Pommerman agents are prone to
learn different skills. The agent with a relatively smaller discount factor is
inclined to learn the reactive skills such as escaping from the bomb
explosion, while the agent with a relatively larger discount factor is prone
to learn the non-reactive skills such as navigating to pick up a power-up.
Meanwhile, the reward function should also match the use of discount factor.
During the period when the agent learned a particular skill, the corresponding
reward function should also be highlighted.

The roadmap of this report is as follows. In Section II, we give the problem
definition. Next, we present the details of our agent and the COMBAT framework
in Section III. In Section IV, we review related work on continual learning
and hyperparameter search. In Section VI, we further discuss some interesting
results in Pommerman and COMBAT. Finally, the experimental results are shown
in Section V.

##  II Problem Definition

Even though the Pommerman environment is partially observable, since the
vision of a Pommerman agent (7x7) is relatively large compared with the size
of the map (11x11) and the focus of this work is not about partial
observability, we consider the problem as a Markov Decision Process (MDP) [16,
20], a widely used sequential decision-making model. An MDP is composed of
states, actions, rewards, policy, and transitions, and represented by a tuple
$\langle S,A,T,R,\pi\rangle$.

  * •

States $S$ is a set of discrete or continuous states

  * •

Actions $A$ is a discrete set of actions that an agent can take. The actions
available may depend on the state $s$, denoted as $A(s)$.

  * •

Transition $T$ is the state transition function $s_{t+1}=T(s_{t},a_{t})$ which
specifies a function which maps a state $s_{t}$ into a new state $s_{t+1}$ in
response to the action selected $a_{t}$.

  * •

Reward $R(s,a)$ is the immediate reward.It gives the immediate reward of
taking action $a$ at state $s$.

  * •

Policy $\pi(a|s)$ describes the behaviors of an agent, which is a probability
distribution over the possible actions. $\pi$ is usually optimized to decide
how to move around in the state space to optimize the long term return.

The agent and environment interact at each of a sequence of discrete time
steps, $t=0,1,2,\cdots$. At each time step $t$ the agent receives some
representation of the environment’s state, $s_{t}\in S$, and on that basis
selects an action $a_{t}\in A(s_{t})$, where $A(s_{t})$ is the set of actions
available in state $s_{t}$. One time step later, in part as a consequence of
its action, the agent receives a numerical reward, $r_{t+1}\in R$ and finds
itself in a new state $s_{t+1}=T(s_{t},a_{t})$.

The agent’s goal is to find a policy that maximizes the return at every single
step. So, we define an objective function $J$ that allows us to score an
arbitrary policy parameter.

$\displaystyle J_{\theta}(\pi_{\theta})$
$\displaystyle=\int_{\mathcal{S}}\rho^{\pi}(s)\int_{\mathcal{A}}pi_{\theta}(a|s)Q^{\pi}(s,a)$
(1)

By using the policy gradient algorithm [21], the gradient of the objective
function $J$ with respect to parameter $\theta$ can be written as:

$\displaystyle\nabla_{\theta}J_{\theta}(\pi_{\theta})$
$\displaystyle=\int_{\mathcal{S}}\rho^{\pi}(s)\int_{\mathcal{A}}\nabla_{\theta}\pi_{\theta}(a|s)Q^{\pi}(s,a)dads$
(2)
$\displaystyle=E_{s\sim\rho^{\pi},a\sim\pi_{\theta}}[\nabla_{\theta}\log\pi_{\theta}(a|s)Q^{\pi}(s,a)]$

##  III Methods

Training Infrastructure We first present the infrastructure of COMBAT in
Figure 1. COMBAT consists of six modules. The population module stores the
indexes and the parameters of a population of agents. Given the agent
population, the match scheduler uses a round-robin method to generate a series
of matches between any two agents in the population. Then, the evaluator
module deploys multiple workers in parallel to run the matches generated by
the match scheduler, i.e., launching the same number of battles between those
designated agents in the game environment accordingly. The matches run on the
evaluators are collected asynchronously: the trajectories of these matches are
gathered and trained by the optimizer, while the ranking list assembles the
results of these matches. Next, the population updater is used to update the
indexes of the agent population according to the results on the updated
ranking list (i.e., the _removable_ function in the pseudo-code), and update
the parameters of the agents in the population according to the outputs of the
optimizers. Lastly, the agent population module is synchronized based on the
population updater.

Algorithm 1 gives the pseudo-code for more details. The _trainable_ function
is used to check whether an agent is trainable since some agents may be rule-
based non-trainable. The _removable_ function is used to check whether an
agent should be removed from the population. $\alpha$ is a hyperparameter to
anneal the discount factor. We assume that a maximum number of $T$ pickups is
chosen for each worker. Also, we omit the computation for $p_{j},p_{k},p_{l}$
in the pseudo-code, which is exactly the same as $p_{i}$.

COMBAT is also suitable for multiple people to work collaboratively, where
each participant trains its own agent and compete with both the other
trainable agents and the rule-based strong agents. With the ranking list
telling which agents are performing better, we know which one’s setting is
working well. During the Pommerman competition, we exactly followed this way
to communicate with each other, finding out the right way to tuning
hyperparameters or trying different reward functions.

Figure 1: The COMBAT infrastructure Algorithm 1 Continual Match Based Training
(COMBAT)

1:procedure Train($\mathcal{P}$)$\triangleright$ Initial population
$\mathcal{P}$

2: initialize $\mathcal{R},\alpha,\\{\gamma_{i}\\}_{p_{i}\in\mathcal{P}}$

3: for t:=1 to T (asynchronously in parallel) do

4: Pick four agents $p_{i},p_{j},p_{k},p_{l}$ from $\mathcal{P}$

5: Play a match between $p_{i},p_{j},p_{k},p_{l}$

6: Update $\mathcal{R}$

7: if  _trainable_($p_{i}$) then

8: Update $p_{i}$

9: if $p_{i}$ is converged then

10: $\gamma_{i}\leftarrow\gamma_{i}+(1-\gamma_{i})*\alpha$

11: else if  _removable_($p_{i},\mathcal{R}$) then

12: Remove $p_{i}$ from $\mathcal{P}$

13: Return $\mathcal{P},\mathcal{R}$

State space The original state space of Pommerman consists of three 11x11
matrices, respectively representing the position of different objects, bomb
blast strength, and bomb life. However, such information is not available and
covered by fog outside the purview of the current agent. Besides that, there
are several scalars indicating teammate, enemies, ammo, blast strength and
kick. To fit such state information with a convolutional neural network model,
We encode all the state information in a 11x11x11 matrix with each channel
representing different objects and their states. To make the states more
precise, we also fix the bomb blast strength and the remaining time of its
explosion for each bomb when it can be affected by the other bombs nearby.

Action space The original action space of Pommerman consists of six discrete
actions: _Stop, Up, Down, Left, Right and Lay a bomb_. One limitation of this
kind of action space is that a local optimum arises where the agent avoids
exploding itself by learning never to use the bomb action. Instead, the action
space of our model is the board position plus bomb action, where the board
position indicate the destination the agent predicts and bomb action indicates
whether to lay a bomb at the current position. Therefore, we define an action
space with 122 dimensions, where the first 121 dimensions are the flattened
board positions, and the last one is the bomb action. Since the predicted
positions are usually out of the reach of one step, Dijkstra algorithm is used
to find the path to the destination.

Network Structure For each agent, the neural network structure is illustrated
in Figure 2. After generating the square state space through the preprocessing
step from the raw Pommerman frames, it is used as the input of the neural
network. The first three hidden layers convolves 16, 32, and 64 3x3 filters
with stride 1 of the input, all of which apply a rectifier nonlinearity [7,
14], respectively. Then, the output of the third hidden layer is flattened,
and it is connected to a fully-connected linear layer with the _hyperbolic
tangent_ as the activation function. The final outputs to either the action
distribution or the value are connected with a fully-connected layer with
their corresponding output sizes.

Optimization Algorithm We use A2C as the optimization algorithm for the
Pommerman agent. Denote by the TD-loss $\delta=R(s,a)+\gamma\cdot
V_{\phi}(s^{\prime})-V_{\phi}(s)$. The gradient of the actor network and the
critic network are written as:

$\displaystyle\nabla_{\theta}J_{\theta}(\pi_{\theta})$
$\displaystyle=\frac{1}{M}\sum_{s,a,s^{\prime}\in
D}\delta\cdot\frac{\partial\log\pi_{\theta}(a|s)}{\partial\theta}$ (3)
$\displaystyle\nabla_{\phi}J_{\phi}$
$\displaystyle=\frac{1}{M}\sum_{s,a,s^{\prime}\in D}\delta\cdot\frac{\partial
V_{\phi}(s)}{\partial\phi}$ (4)

where $s,a,s^{\prime}$ is a sequential state-action sample collected online,
and $M$ is the size of a mini-batch.

Following the spirit of continual learning, we adopt a policy-based algorithm
advantage-actor-critic (A2C) as the basic infrastructure. The reason why A2C
is a good fit for continual learning is on two-fold. First, the agent’s policy
represented by the actor network is independent of either the reward function
or the hyperparameters used in the training phase. It can be used as the basis
of generating meaningful behavior data, while we do not need to update its
network structure when the reward function or the hyperparameters change.
Second, since the output of the critic network acts as the baseline when
performing the policy update, the inaccuracy of estimating the critic network
in A2C does not introduce any bias but related to the degree of variance
reduction. Theoretically, the variance is maximally reduced when the critic
network approximates the expected cumulative reward. Therefore, when the
reward function changes, the critic network should be updated to approximate
the updated expected cumulative reward. Empirically, it does not bring
significant effects to the learning results.

Figure 2: The neural network structure

##  IV Related work

Pommerman [17] is a multi-agent environment, which is stylistically similar to
Bomberman. There are four agents traversing a grid world, and their goals are
to have their team be the last remaining. They can move and lay bombs which,
upon expiration, destroy any destructible objects in their ranges. Adversarial
and cooperative elements are both encouraged in this environment. The Free-
For-All (FFA) variant has at most one winner out of four agents, which fosters
research on handling the non-equivalent Nash payoffs. The team variant
encourages research on cooperation between two teammates with and without
explicit communication channels. Based on Pommerman, learning-based methods
and search-based methods have been proposed to tackle the problems.

Backplay [18] is proposed to increase the sample efficiency of RL in sparse
reward settings. With a single demonstration, the curriculum for a given task
can be constructed. The agent learns from the states at the end of each
demonstration. During the training process, the starting point is being moved
backward until the initial state is reached. Their experiment in Pommerman
shows that Backplay provides significant gains in sample complexity with a
stark advantage in sparse reward setting. Hybrid Search Agent [25] focused on
search-based methods in Pommerman with resource-intensive forward models.
Their result shows that heuristic agent using depth-limited tree search can
slightly outperform hand-made heuristics. The depth-limited tree search agent
with exploration-driven node selection can play significantly better than the
provided _SimpleAgent_.

Continual learning [15], also known as lifelong learning, with neural network
has been studied for quite a long time in the literature. The idea of
continual learning is to learn a neural network to complete multiple tasks
continually. The major difficulty in continual learning is the phenomenon of
catastrophic forgetting when learning on new tasks. Existing work either
define novel neural network structures or propose a more general regularizer
in the loss function to maintain the elasticity of agents. However, when the
experience exposed to the agent are correlated, the events of catastrophic
forgetting are not exhibited frequently during the time of learning on new
tasks. In Pommerman, suppose that we define each task as a particular skill
that an agent is expected to learn such as the task of learning to pick up a
power-ups, or the task of learning to kick a bomb. Then, these tasks are
highly correlated and may appeared together in a single battle. As a result,
pommerman itself is a natural environment for lifelong learning without
suffering from catastrophic forgetting.

Hyperpamater search is a mature topic in the literature, where bayesian
optimization and meta-learning are the most dominated methods. Next, we
highlight some of the novel techniques published in recent years below.
Population based training (PBT) [6] can be regarded as a type of meta learning
[9], where humans do not interfere with the learning process in general. The
hyperparameter search in PBT requires no sequential runs, and used few
computational resources than traditional grid search or sequential
optimization methods. However, while PBT stabilizes the training process based
on the complete set of hyperparameters, COMBAT concerns more about the
hyperparameters that are essential for continual or lifelong learning. The
discount factor, considered in Pommerman, is a typical example of this kind:
different settings may lead to completely different results of convergence.
Self-play learning [19] is a popular technique of making the competitive
environment always stays in a suitable level of difficulty for training
agents. While the self-play framework provides a natural curriculum for
training agents, it also leads to a more non-stationary environment, where the
goal of optimization is changing all the time along the training process.
OpenAI proposed to choose opponents randomly from the historically saved
models to stablize the training process [2]. Likely, COMBAT consider a similar
strategy, simultaneously training multiple agents and allow them to compete
with each other. Meta-gradient reinforcement learning [24] considered a
gradient-based method to optimize the RL-related hyperparameters such as the
discount factor and the number of steps to bootstrap. In our current
implementation of COMBAT, we only consider the discount factor in our
hyperparameter optimization, while in the future work we may consider the
other RL-related hyperparameters.

##  V Experiments: COMBAT in Pommerman

We apply A2C with COMBAT to perform the maximization of cumulative reward in
the Team environment. Although the optimization of a particular POMDP is
sensitive to hyperparameters, including learning rate, minibatch size,
discount factor, and coefficients of policy loss, value loss, and entropy
regularizer, COMBAT makes the final results more stable in a long-term
training process.

###  V-A Experimental Setup

Hyperparameters COMBAT is only used to fine-tune the discount factor $\gamma$
in learning our Pommerman agent. The initial discount factor is $0.5$ and it
will be increased gradually during the learning process. We used the same
network structure as Figure 2. For other hyperparameters, the coefficient of
value loss is set to $0.5$ and the coefficient of entropy regularizer is set
to $0.01$, which is then linearly decayed to $0.05$. The learning rate is
$0.0005$ during the whole learning process without any annealing schedule. The
minibatch of each agent is collected every $256$ timesteps. An agent is
updated by gradient descent using Adam optimizer [8] per $10$ seconds, where
the gradient update formula is provided by A2C.

Match Schedule The match scheduler is fundamental in COMBAT. The population of
agents comprises two kinds of agents, the trainable agents, and the rule-based
agents. Each trainable agent is a deep neural network, while the rule-based
agents include _SimpleAgent_ and _SuperAgent_. Rule-based agents play an
essential role of out training: it is not only a good opponent for the
trainable agents but also a reference in the ranking list for the trainable
agents. _SimpleAgent_ , an officially provided rule-based agent, is initially
placed in the population. _SuperAgent_ , an augmented version of _SimpleAgent_
implemented by ourselves, is added to the population in the later training
phase. We have a population of $9$ agents when participating in the
competition, where there are $8$ trainable agents and $1$ rule-based agent. A
round-robin method is used to generate the competition schedule, but it is not
a pure round-robin since we gave the rule-based agent a much higher
probability to be chosen as one of the participants.

Distributed Asynchronous Parallel System To run the COMBAT framework, we used
220 CPU cores and 32 GPU cores. Our asynchronous distributed parallel system
is explained in Figure 3. From the systematic perspective, we divide our
system into two parts: the rollout generators and the policy optimizers. The
rollout generators run many game simulators in parallelism, generating samples
that are transmitted to the policy optimizer. The policy optimizer is
responsible for computing the gradient and updating the parameters of the
agents. Both of them have been built as Docker containers and deployed by the
Kubernetes [3]. With this methods, we reduce the cost of paralleling multiple
tasks across the computational resources.

Moreover, since the agents need to be stored and shared persistently, the Ceph
[23] was chosen as our distributed block storage solution, which was
configured as a shared model pool. All the checkpoints generated by the
training tasks can be stored in this pool and loaded by tasks on the other
processes to initialize the training tasks. The system will relaunch when the
error encountered, and restore all the tasks with the latest checkpoint.

Figure 3: The framework of our distributed asynchronous parallel system

###  V-B Experimental Results

Figure 4: The experimental results of training the _Navocado_ agent

Figure 4 presents the learning curve of our agent _Navocado_ which won the top
1 learning agent in the NeurIPS 2018 Pommerman competition. The upper sub-
figure in Figure 4 shows the curve of reward, and the lower one in Figure 4
shows the curve of Game Episode length. The x-axis of both sub-figures is
referred to the number of training iterations. The learning process can be
divided into four stages. In the first stage, only one single agent was
trained, and we used the default reward function. During this period, the
agent learned to hide from the bomb explosions, while picking up power-ups
that have been unfolded. In the second stage, we added an extra reward of
picking power-ups. During this period, the agent learned to explode wooden
walls actively and collected power-ups more efficiently. Notice that in both
stages, we set a _SimpleAgent_ as its teammate. Then, in the third stage, we
started the team training process where the _SimpleAgent_ teammate is replaced
by a trainable agent such that the agents at the same team are trained
collectively, but we did not allow the agent to kick the bomb at this stage.
During this period, it takes a much longer time to finish a match, and the
agent learned a better skill of escaping from the bomb explosion. Lastly, in
the fourth stage, we allow both agents in the team to kick the bomb. During
this period, we found that the agents learned to attack more progressively.
Notice that during this period, the Game Episode Length gradually decreased
dramatically from 500 to 400.

###  V-C Examples

In the following, we summarize some skills of the agent we observed when the
agent is playing against other agents. In Figure 5, the agent reveals its
ability to pick up a number of power-ups actively. We can see that the agent
was taking the shortest path to pick up the items. Also, when the agent found
that an enemy is close to an item, it chose to move backward and pick the item
that is far away from the opponent agent. In Figure 6, we show a scenario that
the agent can hide from the bomb explosion. Note that the agent stayed close
to the bomb until the bomb explodes. In Figure 7, the agent learns to kick the
bomb laid by the opponent to the direction where the opponent locates. By
staying close to the bomb, the agent makes the opponent, which attempted to
lay a bomb close to it, more likely to be destroyed by the bomb explosion.

Figure 5: The Pickup Movement: the agent can navigate with the shortest path
to pick up various power-ups. Figure 6: The Hide-from-bomb Movement: the agent
stays close to the bomb and hides from the bomb explosion. Figure 7: The kick-
bomb Movement: the agent can kick the bomb to the direction where the opponent
locates.

##  VI Discussion

We also observed some interesting results during the process of training our
agents. Firstly, the agents learned the skill of escaping from a bomb
explosion at the beginning of the learning process, but it becomes much slower
for them to learn other skills. The early period of fast learning is similar
to the developmental theory discovered in human learning [10], where infants
have a critical period of learning fast from their experiences. Secondly, the
agents learned to kick the bomb laid by the opponent more actively than its
own bomb. Since the bomb explosion is indistinguishable, the action of “lay a
bomb” is not only the most effective way for an agent to attack actively but
also a dangerous behavior that may kill the agent itself. Thus, a smart agent
should lay a bomb in the right place. From this perspective, our agent may
intend to “place” the opponent’s bomb in the right place by kicking the bomb.
Thirdly, we found that if the agent did not learn the basic skill such as
laying a bomb near the wooden wall in the early stage, when the discount
factor is tuned, the agent can still learn the advanced skills such as kicking
a bomb or tempting the opponent to killed by its bomb. However, the basic
skill just cannot be learned anymore even if we tuned the discount factor back
to the initial value at the later stage. This result may indicate that a
complete set of basic skills should be learned before we tuned the
hyperparameters for the advanced skills which are related to the long-term
planning.

##  VII Conclusions

In the paper, we present a COMBAT framework for training Pommerman agents for
participating the NeurIPS 2018 Pommerman Competition. We use A2C for updating
the deep neural network of the Pommerman agents, while a we design a match
scheduling method for better training strong agents in a long-term learning
process. Empirically, the agent kept on improving its performance as long as
dozens of days and won the top 1 learning agent in the Pommerman Competition.

There is still a huge space for our agent to improve in the future. Without
considering the feature of partial observability, it is hard for our agent to
learn how to collaborate with its teammate when its teammate is out of its
sight. The basic idea is to model the problem as a multi-agent POMDP rather
than an MDP.

## References

  * [1] David Balduzzi, Karl Tuyls, Julien Perolat, and Thore Graepel.  Re-evaluating evaluation.  arXiv preprint arXiv:1806.02643, 2018.
  * [2] Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch.  Emergent complexity via multi-agent competition.  arXiv preprint arXiv:1710.03748, 2017.
  * [3] David Bernstein.  Containers and cloud: From lxc to docker to kubernetes.  IEEE Cloud Computing, 3:81–84, 2014.
  * [4] Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein.  Dynamic programming for partially observable stochastic games.  In AAAI, volume 4, pages 709–715, 2004.
  * [5] Demis Hassabis, Dharshan Kumaran, Christopher Summerfield, and Matthew Botvinick.  Neuroscience-inspired artificial intelligence.  Neuron, 95(2):245–258, 2017.
  * [6] Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, Iain Dunning, Karen Simonyan, et al.  Population based training of neural networks.  arXiv preprint arXiv:1711.09846, 2017.
  * [7] Kevin Jarrett, Koray Kavukcuoglu, Yann LeCun, et al.  What is the best multi-stage architecture for object recognition?  In Computer Vision, 2009 IEEE 12th International Conference on, pages 2146–2153. IEEE, 2009.
  * [8] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [9] Christiane Lemke, Marcin Budka, and Bogdan Gabrys.  Metalearning: a survey of trends and technologies.  Artificial intelligence review, 44(1):117–130, 2015.
  * [10] Eric H Lenneberg and Elizabeth Lenneberg.  Foundations of language development: a multidisciplinary approach.  Academic Press, 2014.
  * [11] Michael L Littman.  Markov games as a framework for multi-agent reinforcement learning.  In Machine Learning Proceedings 1994, pages 157–163. Elsevier, 1994\.
  * [12] Michael L Littman.  A tutorial on partially observable markov decision processes.  Journal of Mathematical Psychology, 53(3):119–125, 2009.
  * [13] Roger B Myerson.  Game theory.  Harvard university press, 2013.
  * [14] Vinod Nair and Geoffrey E Hinton.  Rectified linear units improve restricted boltzmann machines.  In Proceedings of the 27th international conference on machine learning (ICML-10), pages 807–814, 2010.
  * [15] German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter.  Continual lifelong learning with neural networks: A review.  arXiv preprint arXiv:1802.07569, 2018.
  * [16] Martin L Puterman.  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons, 2014.
  * [17] Cinjon Resnick, Wes Eldridge, David Ha, Denny Britz, Jakob Foerster, Julian Togelius, Kyunghyun Cho, and Joan Bruna.  Pommerman: A multi-agent playground.  arXiv preprint arXiv:1809.07124, 2018.
  * [18] Cinjon Resnick, Roberta Raileanu, Sanyam Kapoor, Alex Peysakhovich, Kyunghyun Cho, and Joan Bruna.  Backplay:” man muss immer umkehren”.  arXiv preprint arXiv:1807.06919, 2018.
  * [19] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al.  Mastering chess and shogi by self-play with a general reinforcement learning algorithm.  arXiv preprint arXiv:1712.01815, 2017.
  * [20] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [21] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In Advances in neural information processing systems, pages 1057–1063, 2000.
  * [22] Sebastian Thrun and Tom M Mitchell.  Lifelong robot learning.  In The biology and technology of intelligent autonomous agents, pages 165–196. Springer, 1995.
  * [23] Sage A Weil, Scott A Brandt, Ethan L Miller, Darrell DE Long, and Carlos Maltzahn.  Ceph: A scalable, high-performance distributed file system.  In Proceedings of the 7th symposium on Operating systems design and implementation, pages 307–320. USENIX Association, 2006.
  * [24] Zhongwen Xu, Hado van Hasselt, and David Silver.  Meta-gradient reinforcement learning.  arXiv preprint arXiv:1805.09801, 2018.
  * [25] Hongwei Zhou, Yichen Gong, Luvneesh Mugrai, Ahmed Khalifa, Andy Nealen, and Julian Togelius.  A hybrid search agent in pommerman.  In Proceedings of the 13th International Conference on the Foundations of Digital Games, page 46. ACM, 2018.


# Irreducibility of Generalized Permutohedra, Supermodular Functions, and
Balanced Multisets

Milan Haiman  and  Yuan Yao

###### Abstract.

We study generalized permutohedra and supermodular functions. Specifically we
analyze decomposability and irreducibility for these objects and establish
some asymptotic behavior. We also study a related problem on irreducibility
for multisets.

##  1\. Introduction

A _permutohedron_ in $\mathbb{R}^{n}$ is the $(n-1)$-dimensional polytope
obtain by taking the convex hull of all $n!$ points obtained by permuting the
coordinates a point $(x_{1},\dots,x_{n})\in\mathbb{R}^{n}$. In [8], Postnikov
introduced the _generalized permutohedron_ , which is a deformation of a
permutohedron obtained by translating the hyperplanes bounding each face.
Generalized permutohedra were also further studied in [9]. In [8], Postnikov
derives a volume formula for generalized permutohedra as a polynomial in the
defining parameters. The proof of the formula requires a decomposition of some
generalized permutohedra into weighted Minkowski sums of coordinate simplices.
However, not all generalized permutohedra can be written in this form.
Therefore, it is natural to ask whether all generalized permutohedra can be
written as a weighted Minkowski sum of a some fixed set of polytopes.

We define a generalized permutohedron to be _irreducible_ if it cannot be
written as a weighted Minkowski sum of generalized permutohedra in a
nontrivial way (any convex polytope is a Minkowski sum of smaller copies of
itself). Then all generalized permutohedra can be decomposed as a Minkowski
sum of irreducible generalized permutohedra.

In this paper we aim to understand the class of irreducible generalized
permutohedra. We make use of connections to related problems.

Generalized permutohedra in $\mathbb{R}^{n}$ are strongly related to
supermodular functions on subsets of $[n]$, which are a discrete analog of
convex functions. Supermodular functions are an important object in
optimization and other fields (see [2]).

There is a direct bijection between irreducible generalized permutohedra and
irreducible supermodular functions, which have been studied by several authors
([13, 10]). In [10], Promislow and Young determined the irreducible
supermodular functions for $n\leq 4$ and conjectured a simple
characterizations for $n>4$. However, this conjecture was shown to be false by
Živný, Cohen, and Jeavons in [13], and we further show that this
characterization is far from capturing all irreducible supermodular functions.

To understand irreducible supermodular functions, we first study a related
(and simpler) problem involving irreducibility. Given a multiset $\mathcal{M}$
of subsets of $[n]$, we say that $\mathcal{M}$ is _balanced_ if each element
of $[n]$ appears the same number of times in $\mathcal{M}$. We denote the
number of times each element appears by the _complexity_ $m=m(\mathcal{M})$.
The conditions for irreducibility generalized permutohedra and supermodular
functions can be formulated as a modification of that of irreducible balanced
multisets.

We derive bounds on the complexity of irreducible balanced multisets and
enumerate the number of irreducible balanced multisets up to lower order
terms. Using similar ideas, we provide double-exponential upper bounds for
complexity and number of irreducible generalized permutohedra. We also obtain
double-exponential lower bounds by relating a subclass of supermodular
functions to matroids. The key asymptotic results are the following.

######  Theorem 1.1.

The number of irreducible supermodular functions, up to equivalence, is
bounded above by $2^{O(n2^{n})}$ and bounded below by
$2^{\Omega(2^{n}/n^{3/2})}$.

We also study a simple subclass of irreducible supermodular functions, which
we enumerate precisely.

The paper is structured as follows. In Section 2 we establish the preliminary
definitions related to generalized permutohedra and supermodular functions. In
Section 3 we establish some conditions for a supermodular function to be
irreducible. In Section 4 we explore the related problem of irreducible
balanced multisets. In Section 5 we obtain upper bounds on the number and
complexity of irreducible supermodular functions. In Section 6 we obtain lower
bounds on the number of irreducible supermodular functions. In Section 7, we
study supermodular functions with supermodularities on only two layers.

##  2\. Preliminaries

There are several equivalent ways to define a generalized permutohedron, and
here we present the one that is the most convenient for our purposes. For a
subset $I\subseteq[n]$, we let $1_{I}$ denote the vector whose $i$-th
coordinate is $1$ if $i\in I$ and $0$ otherwise.

######  Definition 2.1.

A _generalized permutohedron_ in $\mathbb{R}^{n}$ is a polytope of the form

$\\{x\in\mathbb{R}^{n}\colon x\cdot 1_{I}\geq z_{I},x\cdot 1_{[n]}=z_{[n]}\\}$

for reals $z_{I}$ satisfying the _supermodularity condition_ :

$z_{I\cap J}+z_{I\cup J}\geq z_{I}+z_{J}$

for all $I,J\subseteq[n]$ (we set $z_{\varnothing}=0$).

This definition includes all ordinary permutohedra: for $x_{1}\leq
x_{2}\leq\dots\leq x_{n}$, we can recover the permutohedron with vertices that
are permutations of $(x_{1},\dots,x_{n})$ by taking
$z_{I}=x_{1}+\dots+x_{\left|I\right|}$ for each $I\subseteq[n]$.

The supermodularity conditions $z_{I\cap J}+z_{I\cup J}\geq z_{I}+z_{J}$
guarantees that a generalized permutohedron has the same face structure as a
permutohedron, up to degeneracies that reduce the dimension of faces. In
particular, we still have that all edges are parallel to $e_{i}-e_{j}$ for
some $i,j$.

We define the _Minkowski sum_ of two subsets $P$ and $Q$ of $\mathbb{R}^{n}$
to be the set $P+Q=\\{x+y\colon x\in P,y\in Q\\}$. Note that the set of
generalized permutohedra is closed under Minkowski sums, since taking a
Minkowski sum simply results in adding the corresponding $z_{I}$ parameters.

######  Definition 2.2.

We say that a generalized permutohedron $P$ is _irreducible_ if whenever $P$
is written as a Minkowski sum $Q_{1}+Q_{2}$ of generalized permutohedra,
$Q_{1}$ and $Q_{2}$ are both copies of $P$ up to scaling and translation.

We can view the set of generalized permutohedra as a subset of
$\mathbb{R}^{2^{n}-1}$ by considering the vector of corresponding $z_{I}$
parameters. This subset is a cone bounded by the hyperplanes corresponding to
the supermodularity conditions. Then the irreducible generalized permutohedra
correspond to the extreme rays of this cone. In particular, because we have
finitely many conditions, there are finitely many irreducible generalized
permutohedra, up to scaling and translation. So every generalized
permutohedron can be written as a weighted Minkowski sum of irreducible
generalized permutohedra. For example, a permutohedron is a weighted Minkowski
sum of $\binom{n}{2}$ line segments between the standard basis vectors in
$\mathbb{R}^{n}$.

Since the problem of determining the irreducible generalized permutohedra is
equivalent to determining the extreme rays of a high-dimensional cone, we can
apply standard algorithms to determine the answer for small $n$. For $n=3$
there are $5$ irreducible supermodular functions. As generalized permutohedra,
two of these are equilateral triangles (with opposite orientations), and the
other three are are line segments.

For $n=4$ there are $37$ irreducible supermodular functions. Ignoring lower
dimensional examples and symmetries, we have $5$ new irreducible generalized
permutohedra, pictured below.

For $n=5$ there are $117978$ irreducible generalized permutohedra. Even
accounting for lower dimensional examples and symmetries, we have many new
polytopes that do not follow a clear pattern. Thus we aim to understand the
number and complexity of irreducible generalized permutohedra for general $n$
instead of a precise characterization.

######  Definition 2.3.

A function $f:2^{[n]}\to\mathbb{R}$ is _supermodular_ if $f(I\cap J)+f(I\cup
J)\geq f(I)+f(J)$ for all $I,J\subseteq[n]$. It is _modular_ if $f(I\cap
J)+f(I\cup J)=f(I)+f(J)$ for all $I,J\subseteq[n]$.

Given a generalized permutohedron, we immediately obtain a supermodular
function by taking $f(I)=z_{I}$. In the other direction, any supermodular
function $f$ with $f(\emptyset)=0$ gives a generalized permutohedron. Thus
generalized permutohedra and supermodular functions are essentially the same
object. In particular, note that modular functions correspond to a single
point as a generalized permutohedron.

######  Definition 2.4.

We say that two supermodular functions are _equivalent_ if they differ by a
modular function. We say that a supermodular function $f$ is _irreducible_ if
it is not modular and whenever $f=g_{1}+g_{2}$ for supermodular functions
$g_{1}$ and $g_{2}$, $g_{1}$ and $g_{2}$ are each equivalent to a function of
the form $cf$ for $c\in\mathbb{R}_{\geq 0}$.

Note that each equivalence class of irreducible supermodular functions has a
representative $f$ with the following properties:

  * •

$f(I)=0$ for $\left|I\right|\leq 1$

  * •

$f$ takes nonnegative integer values with greatest common divisor $1$.

As before, we see that the irreducible supermodular functions generate all
supermodular functions by taking nonnegative linear combinations.
Additionally, irreducible generalized permutohedra correspond to irreducible
supermodular functions.

##  3\. Analyzing Irreducible Supermodular Functions

As a motivating example, we first consider _nondecreasing_ functions on
subsets of $[n]$, that is, functions $f\colon 2^{[n]}\to\mathbb{R}$ where
$f(I)\geq f(J)$ whenever $I\supseteq J$.

For a set $S$ and $i\in S$, let $\partial_{i}$ be the _discrete derivative
operator_ mappings functions $f\colon 2^{S}\to\mathbb{R}$ to functions
$\partial_{i}f\colon 2^{S\setminus\\{i\\}}\to\mathbb{R}$, defined by
$(\partial_{i}f)(I)=f(I\cup\\{i\\})-f(I)$. It is clear that $f$ is
nondecreasing if and only if $(\partial_{i}f)(I)\geq 0$ for every $i\in[n]$
and $I\subseteq[n]\setminus\\{i\\}$. We also have that $f$ is supermodular if
and only if $(\partial_{i}\partial_{j}f)(I)\geq 0$ for every pair of distinct
$i,j\in[n]$ and $I\subseteq[n]\setminus\\{i,j\\}$. Thus we can think of
supermodular functions as having nonnegative second derivatives everywhere,
which makes the case of nondecreasing functions (nonnegative first
derivatives) natural.

Motivated by this parallel, we can define equivalence and irreducibility for
nondecreasing functions.

######  Definition 3.1.

We say two nondecreasing functions are _equivalent_ if their difference is a
constant function. A nondecreasing function $f$ is _irreducible_ if it is not
constant and not a nontrivial sum of nondecreasing functions. That is, if
$f=g_{1}+g_{2}$ for nondecreasing functions $g_{1}$ and $g_{2}$, then $g_{1}$
and $g_{2}$ are each equivalent to a nonnegative multiple of $f$.

We can precisely characterize the irreducible nondecreasing functions. Given
an nonempty antichain $\mathcal{A}$ of subsets of $[n]$, we define the up
function of $\mathcal{A}$ to be $u_{\mathcal{A}}(I)=1$ if $I\supseteq J$ for
some $J\in\mathcal{A}$ and $u_{\mathcal{A}}(I)=0$ otherwise.

######  Lemma 3.2.

A nondecreasing function is irreducible if and only if it is equivalent to a
function of the form $cu_{\mathcal{A}}$ for some nonempty antichain
$\mathcal{A}$ of subsets of $[n]$ and some $c\in\mathbb{R}_{\geq 0}$.

###### Proof.

First we show the “if” direction. Let $\mathcal{A}$ be a nonempty antichain of
subsets of $[n]$. We will show that $u_{\mathcal{A}}$ is irreducible. Let
$f_{1}$ and $f_{2}$ be nondecreasing functions such that
$u_{\mathcal{A}}=f_{1}+f_{2}$. Now consider sets $I\subseteq J$ such that
$u_{\mathcal{A}}(I)=u_{\mathcal{A}}(J)$. We have that $f_{i}(I)\leq f_{i}(J)$
by nondecreasingity. However

$u_{\mathcal{A}}(I)=f_{1}(I)+f_{2}(I)\leq
f_{1}(J)+f_{2}(J)=u_{\mathcal{A}}(J).$

Thus we must have equality, so $f_{1}(I)=f_{1}(J)$ and $f_{2}(I)=f_{2}(J)$.

This fact implies that $f_{i}(I)=f_{i}([n])$ whenever $I\supseteq A$ for some
$A\in\mathcal{A}$, and $f_{i}(I)=f_{i}(\emptyset)$ otherwise. Thus

$f_{i}(I)=f_{i}(\emptyset)+(f_{i}([n])-f_{i}(\emptyset))u_{\mathcal{A}}.$

This shows that $u_{\mathcal{A}}$ is irreducible.

Now we show the converse. Suppose that $f$ is a nondecreasing function not
equivalent to a multiple of $u_{\mathcal{A}}$ for any antichain $\mathcal{A}$.
Consider the family $\mathcal{F}$ of subsets $I\subseteq[n]$ for which
$f(I)>f(\emptyset)$. Since $f$ is not constant, $\mathcal{F}$ is nonempty. Let
$\mathcal{A}$ be the family of minimal sets in $\mathcal{F}$. Note that
$u_{\mathcal{A}}$ takes the value $1$ on elements of $\mathcal{F}$ and $0$
elsewhere. Now, for sufficiently small $c>0$, we have $f(I)>c+f(\emptyset)$.
Thus $f-cu_{\mathcal{A}}$ is nondecreasing for some $c>0$. But $f$ is not
equivalent to $cu_{\mathcal{A}}$. So $f$ is reducible. ∎

The number of antichains of subsets of $[n]$ is at least $2^{\binom{n}{n/2}}$
by choosing only subsets of size $\binom{n}{n/2}$. In fact such antichains
describe most possibilities [5, 7].

Given this understanding of nondecreasing functions, we can attempt to use it
to understand supermodular functions. If $f$ is supermodular, then
$\partial_{i}f$ is nondecreasing. So we can construct supermodular functions
by taking $n$ nondecreasing functions $g_{1},\dots,g_{n}$ with $g_{i}\colon
2^{[n]\setminus\\{i\\}}\to\mathbb{R}$. However, we are restricted by the fact
that

$\partial_{i}g_{j}=\partial_{i}\partial_{j}f=\partial_{j}\partial_{i}f=\partial_{j}g_{i}.$

Therefore supermodular functions can be heuristically described as $n$
weighted sums of antichains with a compatibility condition between the sums.

Another way to understand supermodular functions is to consider the
supermodularity condition on certain pairs of $I$ and $J$.

######  Definition 3.3.

We say that an unordered pair of subsets $\\{I,J\\}$ of $[n]$ is _close_ if
$\left|I\right|=\left|J\right|=\left|I\cap J\right|+1=\left|I\cup J\right|-1$.
Let $\mathcal{P}_{n}$ be the set of all close pairs. Note that
$|\mathcal{P}_{n}|=\binom{n}{2}2^{n-2}$.

Given a supermodular functions $f$, for each close pair $\\{I,J\\}$, let the
_supermodularity value_ of this pair be

$s_{I,J}=f(I\cap J)+f(I\cup J)-f(I)-f(J).$

Clearly, $\\{I,J\\}$ is a close pair if and only if $1_{I}$, $1_{J}$,
$1_{I\cap J}$, $1_{I\cup J}$ are the vertices of a square face in the boolean
hypercube, so we will treat square faces and close pairs interchangeably.

It is sufficient to define $s_{I,J}$ only when $\\{I,J\\}$ is a close pair
because of the following lemma. Let
$T\colon\mathbb{R}^{2^{[n]}}\to\mathbb{R}^{\mathcal{P}_{n}}$ denote the linear
map sending $f$ to $s$.

######  Lemma 3.4.

Let $f\colon 2^{[n]}\to\mathbb{R}$ and let $s=Tf$. Then $f$ is supermodular if
and only if $s_{I,J}\geq 0$ for each close pair $\\{I,J\\}$.

###### Proof.

The “only if” direction is clear.

For the “if” direction, let $f\colon 2^{[n]}\to\mathbb{R}$ and supppose $s=Tf$
satisfies $s_{I,J}\geq 0$ for each close pair $\\{I,J\\}$. We will show that

$f(I\cap J)+f(I\cup J)-f(I)-f(J)\geq 0$

for all $I,J\subseteq[n]$.

Fix subsets $I,J\subseteq[n]$ and let $I\setminus
J=\\{i_{1},\dots,i_{\ell_{I}}\\}$, $J\setminus
I=\\{j_{1},\dots,j_{\ell_{J}}\\}$. Let $K(a,b)=(I\cap
J)\cup\\{i_{1},\dots,i_{a},j_{1},\dots,j_{b}\\}$ for $0\leq a\leq\ell_{I}$ and
$0\leq b\leq\ell_{J}$. Note that $\\{K(a,b-1),K(a-1,b)\\}$ is a close pair for
$a,b>0$. Additionally we have that

$0\leq s_{K(a,b-1),K(a-1,b)}=f(K(a,b))+f(K(a-1,b-1))-f(K(a,b-1))-f(K(a-1,b)).$

Now we sum inequality over all $1\leq a\leq\ell_{I}$ and $1\leq
b\leq\ell_{J}$. Most terms on the RHS cancel, leaving us with

$0\leq
f(K(\ell_{I},\ell_{J}))+f(K(0,0))-f(K(\ell_{I},0))-f(K(0,\ell_{J}))=f(I\cup
J)+f(I\cap J)-f(I)-f(J).$

Thus $f$ is supermodular. ∎

Note that the kernel of $T$ is the space of modular functions, which has
dimension $n+1$. Thus the image of $T$ has dimension $2^{n}-n-1$.

We can determine the image of $T$ in $\mathbb{R}^{\mathcal{P}_{n}}$ by a set
of $\binom{n}{2}2^{n-2}-2^{n}+n+1$ linear conditions on $s$. The possible
vectors $s$ obtained from supermodular functions are just the vectors
satisfying these conditions with nonnegative entries. So the relevant subset
of vectors is the intersection of $\operatorname{im}T$ with the positive
orthant, which is a cone. The irreducible supermodular functions then
correspond to the extreme rays of this cone.

We now characterize the linear conditions determining $\operatorname{im}T$.
Given a permutation $\sigma=(\sigma_{1},\dots,\sigma_{n})\in S_{n}$, we let
$I_{r}(\sigma)=\\{\sigma_{1},\dots,\sigma_{r}\\}$ and
$J_{r}(\sigma)=\\{\sigma_{2},\dots,\sigma_{r+1}\\}$, for each $1\leq r\leq
n-1$. Also let $I_{n}(\sigma)=[n]$ and $J_{0}(\sigma)=\emptyset$, so that
$I_{r}\cup J_{r}=I_{r+1}$ and $I_{r}\cap J_{r}=J_{r-1}$. We define the _path
sum_ of $s$ along $\sigma$ to be

$P_{\sigma}(s)=\sum_{r=1}^{n-1}s_{I_{r},J_{r}}.$

Here $\sigma$ corresponds to a maximal chain in the poset of square faces of
the hypercube ordered by the relation $\\{I,J\\}<\\{I^{\prime},J^{\prime}\\}$
when one of $I^{\prime}$ and $J^{\prime}$ contains both of $I$ and $J$ and the
other contains at least one of $I$ and $J$. Additionally, we say that the path
corresponding to $\sigma$ has _color_ $\sigma_{1}$.

######  Example 3.5.

When $n=4$ and $\sigma=(2,4,1,3)$, we obtain the following path on square
faces. The color of the path is $\sigma_{1}=2$, which can be seen by each
square face having a pair of opposite edges in the direction $1_{\\{2\\}}$.

The following theorem explains the relevance of the color of a path and uses
path sums to describe $\operatorname{im}T$.

######  Theorem 3.6.

The following are equivalent for any $s\in\mathbb{R}^{\mathcal{P}_{n}}$:

  1. (1)

$s\in\operatorname{im}T$.

  2. (2)

There exist $m_{1},\dots,m_{n}$ such that $P_{\sigma}(s)=m_{\sigma_{1}}$ for
all $\sigma\in S_{n}$. The value of $m_{i}$ will be referred to as the
_weight_ of color $i$.

  3. (3)

For all distinct $i,j,k\in[n]$ and $I\subseteq[n]\setminus\\{i,j,k\\}$,

$s_{I\cup\\{i\\},I\cup\\{j\\}}+s_{I\cup\\{i,j\\},I\cup\\{j,k\\}}=s_{I\cup\\{i\\},I\cup\\{k\\}}+s_{I\cup\\{i,k\\},I\cup\\{j,k\\}}.$

###### Proof.

We will show that $(1)\implies(2)\implies(3)\implies(1)$.

We first show $(1)\implies(2)$. Let $f$ be a function with $Tf=s$. We claim
that

$m_{i}=f([n])+f(\emptyset)-f(\\{i\\})-f([n]\setminus\\{i\\})=\partial_{i}f([n]\setminus\\{i\\})-\partial_{i}f(\emptyset)$

satisfies condition (2).

Consider an arbitrary $\sigma\in S_{n}$. Note that

$s_{I_{r},J_{r}}=\partial_{\sigma_{1}}\partial_{\sigma_{r+1}}f(I_{r}\cap
J_{r})=\partial_{\sigma_{1}}\partial_{\sigma_{r+1}}f(J_{r-1})=\partial_{\sigma_{1}}f(J_{r})-\partial_{\sigma_{1}}f(J_{r-1}).$

Thus the sum in $P_{\sigma}(s)$ telescopes to
$\partial_{\sigma_{1}}f(J_{n-1})-\partial_{\sigma_{1}}f(J_{0})=m_{\sigma_{1}},$
as desired.

Next we show that $(2)\implies(3)$. Fix distinct $i,j,k\in[n]$ and
$I\subseteq[n]\setminus\\{i,j,k\\}$. Let $t=\left|I\right|$. Choose a
$\sigma\in S_{n}$ such that $\sigma_{1}=i$, $J_{t}(\sigma)=I$,
$\sigma_{t+2}=j$, and $\sigma_{t+3}=k$. Let $\sigma^{\prime}\in S_{n}$ be such
that $\sigma_{r}^{\prime}=\sigma_{r}$ for $r\neq t+2,t+3$ and
$\sigma_{t+2}^{\prime}=k$, $\sigma_{t+3}^{\prime}=j.$ Then we have that
$I_{r}(\sigma)=I_{r}(\sigma^{\prime})$ except when $r=t+2$ and
$I_{r}(\sigma)=I_{r}(\sigma^{\prime})$ except when $r=t+1$. Since
$\sigma_{1}=\sigma_{1}^{\prime}$, we have
$P_{\sigma}(s)=P_{\sigma^{\prime}}(s)$. Cancelling the common terms from the
sum gives

$s_{I_{t+1}(\sigma),J_{t+1}(\sigma)}+s_{I_{t+2}(\sigma),J_{t+2}(\sigma)}=s_{I_{t+1}(\sigma^{\prime}),J_{t+1}(\sigma^{\prime})}+s_{I_{t+2}(\sigma^{\prime}),J_{t+2}(\sigma^{\prime})}.$

After substituting for $I_{r}$ and $J_{r}$ we obtain

$s_{I\cup\\{i\\},I\cup\\{j\\}}+s_{I\cup\\{i,j\\},I\cup\\{j,k\\}}=s_{I\cup\\{i\\},I\cup\\{k\\}}+s_{I\cup\\{i,k\\},I\cup\\{j,k\\}},$

as desired.

Finally we show $(3)\implies(1)$. Let $s$ be a function satisfying $(3)$. We
will construct an $f$ such that $Tf=s$. To construct $f$ we define $f(J)$
inductively based on $\left|J\right|$. If $\left|J\right|<2$ we let $f(J)=0$.

Now suppose that we have defined $f(J)$ for all $J$ with $\left|J\right|<t$,
for some $t\in[2,n]$. Fix a $J$ with $\left|J\right|=t$. Choose $i,j\in J$
arbitrarily let $I=J\setminus\\{i,j\\}$. We define

$f(J)=s_{I\cup\\{i\\},I\cup\\{j\\}}+f(I\cup\\{i\\})+f(I\cup\\{j\\})-f(I).$

This inductive procedure defines some function $f\colon 2^{[n]}\to\mathbb{R}$.
We claim that the choices of $i,j\in J$ do not affect the function $f$ defined
by the procedure.

We prove that $f(J)$ is uniquely determined by induction on $\left|J\right|$.
This is clear for $\left|J\right|\leq 2$. Now suppose we know that $f(J)$ is
uniquely determined for all $J$ with $\left|J\right|\leq t$ for some
$J\in[2,n]$. Fix a $J$ with $\left|J\right|=t$. It suffices to show that for
any distinct $i,j,k\in J$ we obtain the same value for $f(J)$ be recursing
with $\\{i,j\\}$ or $\\{i,k\\}$, because applying this fact twice connects any
two pairs $\\{i,j\\}$ and $\\{i^{\prime},j^{\prime}\\}$.

Applying condition $(3)$ with $i,j,k$ and $I=J\setminus\\{i,j,k\\}$ we obtain
that

$s_{I\cup\\{i\\},I\cup\\{j\\}}+s_{I\cup\\{i,j\\},I\cup\\{j,k\\}}=s_{I\cup\\{i\\},I\cup\\{k\\}}+s_{I\cup\\{i,k\\},I\cup\\{j,k\\}}.$

By the inductive hypothesis we have that

$s_{I\cup\\{i\\},I\cup\\{j\\}}=f(I\cup\\{i,j\\})+f(I)-f(I\cup\\{i\\})-f(I\cup\\{j\\}).$

Similarly, we have that

$s_{I\cup\\{i\\},I\cup\\{k\\}}=f(I\cup\\{i,k\\})+f(I)-f(I\cup\\{i\\})-f(I\cup\\{k\\}).$

Substituting these values into condition (3) gives

$s_{I\cup\\{i,j\\},I\cup\\{j,k\\}}+f(I\cup\\{i,j\\})-f(I\cup\\{j\\})=s_{I\cup\\{i,k\\},I\cup\\{j,k\\}}+f(I\cup\\{i,k\\})-f(I\cup\\{k\\}).$

Adding $f(I\cup\\{j,k\\})$ to both sides gives that the two potential values
for $f(J)$ in question are in fact equal. ∎

By the above theorem, we know that we can describe $\operatorname{im}T$ using
linear conditions of the form $s\cdot v=0$, where $v$ has all entries $0$
except for $2$ entries of $+1$ and $2$ entries of $-1$. We will use this fact
to understand the complexity of irreducible supermodular functions.

##  4\. Irreducibility of Balanced Multisets

For each square face of the hypercube, we have an associated supermodularity
value $s_{I,J}$. Additionally, we have some subset of our $n!$ paths passing
through this face. Our only condition on the supermodularity values is that
their sum along each path of a given “color” is fixed.

So, choosing a supermodular functions is equivalent to choosing a weight for
each square face (and thus the corresponding set of paths) such that the each
path of a given “color” has a fixed total weight. This is equivalent to
choosing a collection of subsets of a set of size $n!$ subject to the sum of
the collection having a nice form, which is the same as our simplified
irreducibility problem with two modifications. First, we are only allowed to
use certain subsets in our collection (i.e., those corresponding to a square
face). Second, the sum of the collection doesn’t have to be a perfect multiple
of the set of all $n!$ paths; it only has to be count paths of each color the
same number of times.

######  Definition 4.1.

A multiset $\mathcal{M}$ of subsets of $[N]$ is _balanced_ with _complexity_
$m$ if each $i\in[N]$ appears in exactly $m$ sets in $\mathcal{M}$. We say
that a balanced multiset is _$\mathbb{Z}$ -irreducible_ if no proper nonempty
subset is balanced.

######  Example 4.2.

When $N=4$, the multiset
$\mathcal{M}=\\{\\{1\\},\\{1\\},\\{2,3\\},\\{2,4\\},\\{3,4\\}\\}$ is balanced
with complexity $2$ and is $\mathbb{Z}$-irreducible.

Given a multiset $\mathcal{M}$ of subsets of $[N]$, we can construct a vector
$v=v(\mathcal{M})\in\mathbb{R}^{2^{[N]}}$ such that $v_{I}$ is the number of
times $I$ appears in $\mathcal{M}$. Then we have that $\mathcal{M}$ is
balanced (of complexity $m$) if and only if $B_{N}v(\mathcal{M})=m1_{[N]}$,
where $B_{N}$ is the $N\times 2^{N}$ matrix with columns $1_{I}$ for each
$I\subseteq[N]$. This allows us to extend the definition of balanced multisets
to all vectors $v\in\mathbb{R}^{2^{[N]}}$ with nonnegative entries.

######  Definition 4.3.

A vector $v\in\mathbb{R}_{\geq 0}^{2^{[N]}}$ is _balanced_ if
$B_{N}v=m1_{[N]}$ for some $m\in\mathbb{R}$. A balanced vector $v$ is
_irreducible_ if whenever $v=u_{1}+u_{2}$ for balanced $u_{1}$ and $u_{2}$,
both $u_{1}$ and $u_{2}$ are real multiples of $v$. Equivalently, $v$ is
irreducible if it lies on an extreme ray of the cone of all balanced vectors
in $\mathbb{R}^{2^{[N]}}$.

Given a nonzero balanced vector $v\in\mathbb{R}^{2^{[N]}}$ we can construct a
balanced multiset $\mathcal{M}$ by scaling $v$ to have integer entries not
sharing a common factor. We define the complexity of a balanced $v$ to be the
complexity of the multiset $\mathcal{M}$ obtained in this way. We also say
that a multiset $\mathcal{M}$ is _irreducible_ if it is obtained from an
irreducible $v$ in this way.

Note that if $\mathcal{M}$ is irreducible, then it is also
$\mathbb{Z}$-irreducible. However, the reverse does not hold. For example, the
multiset $\mathcal{M}=\\{1234,4,12,135,235,45\\}$ is $\mathbb{Z}$-irreducible
but not irreducible by Lemma 4.5.

To analyze irreducibility for balanced multisets and vectors, we will use some
results from random matrix theory. Let $M_{N}$ be the $N\times N$ matrix with
uniform and independent $\pm 1$ entries. In [12], Tikhomirov showed that
$M_{N}$ is singular with probability $(1/2+o(1))^{N}$. We will only need that
$M_{N}$ is invertible with probability $1-o(1/N)$

By Hadamard’s inequality, $\left|\det M_{N}\right|\leq n^{n/2}$. Equality is
attained when $M_{N}$ is a Hadamard matrix. Additionally, in [11], Tao and Vu
showed that $\left|\det M_{N}\right|\geq(cn)^{n/2}$ with probability $1-o(1)$
for fixed $c<1/e$.

For our applications, we will need the following lemma, which follows by
applying row operations to $M_{N}$.

######  Lemma 4.4.

Let $A$ be a uniformly random $N\times N$ matrix with $\\{0,1\\}$ entries and
let $A_{i}$ be $A$ with the $i$-th column replaced with all $1$’s. Then the
distribution of $\left|\det A\right|$ is $2^{-N}$ times the distribution of
$\left|\det M_{N+1}\right|$ and the distribution of $\left|\det A_{i}\right|$
is $2^{-N+1}$ times the distribution of $\left|\det M_{N}\right|$.

###### Proof.

We first show the second claim. From $A_{i}$, replace each column $j\neq i$
with column $i$ minus twice column $j$ to obtain a matrix $A_{i}^{\prime}$. We
have that $\det A_{i}^{\prime}=(-2)^{N-1}\det A_{i}$, and $A_{i}^{\prime}$ has
$\pm 1$ entries. Next independently negate each row of $A_{i}^{\prime}$ with
probability $1/2$ to obtain $A_{i}^{\prime\prime}$. Then $\left|\det
A_{i}^{\prime\prime}\right|=\left|\det A_{i}^{\prime}\right|$ and
$A_{i}^{\prime\prime}$ is distributed identically to $M_{N}$. So the
distribution of $\left|\det A_{i}\right|$ is $2^{-N+1}$ times the distribution
of $\left|\det M_{N}\right|$.

Now we show the first claim. Consider the $(N+1)\times(N+1)$ matrix
$A^{\prime}$ with $A$ in the bottom right $N\times N$ block, all $1$’s in the
first column, and all $0$’s in the rest of the top row. Then $\det
A^{\prime}=\det A$. Now, we construct a new matrix $A^{\prime\prime}$,
obtained from $A^{\prime}$ as follows. Independently, for each $i>1$, with
probability $1/2$, either keep column $i$ the same or replace column $i$ with
column $1$ minus column $i$. Then $\left|\det
A^{\prime\prime}\right|=\left|\det A^{\prime}\right|$ and $A^{\prime\prime}$
is distributed the same as $A_{1}$ in the second claim with $N$ replaced by
$N+1$. So the distribution of $\left|\det A\right|$ is $2^{-N}$ times the
distribution of $\left|\det M_{N+1}\right|$. ∎

Now we analyze irreducible balanced vectors. First we prove the following
lemma.

######  Lemma 4.5.

Let $v$ be an irreducible balanced vector in $\mathbb{R}^{2^{[N]}}$. Then the
set of vectors $\\{1_{I}\colon v_{I}>0\\}$ is linearly independent.

###### Proof.

Suppose this is not the case. Let $\\{I_{1},\dots,I_{\ell}\\}=\\{1_{I}\colon
v_{I}>0\\}$. Then there exists $\alpha_{i}$ not all $0$ such that
$\sum_{i=1}^{\ell}\alpha_{i}1_{I_{i}}=0.$

Now, let

$t=\min\left\\{\frac{v_{I_{i}}}{\left|\alpha_{i}\right|}\colon 1\leq
i\leq\ell,\alpha_{i}\neq 0\right\\}.$

Define $v^{+}$ by $v_{I_{i}}^{+}=v_{I_{i}}+t\alpha_{i}$ and $v_{I}^{+}=0$ if
$v_{I}=0$. Similarly define $v^{-}$ by $v_{I_{i}}^{-}=v_{I_{i}}-t\alpha_{i}$
and $v_{I}^{-}=0$ if $v_{I}=0$.

By definition of $t$, $v^{+}$ and $v^{-}$ have nonnegative entries and
$v^{+}+v^{-}=2v$. Additionally, there exists $i$ such that $v_{I_{i}}^{+}=0$
or $v_{I_{i}}^{-}=0$ but $v_{I_{i}}\neq 0$. Thus $v^{+}$ and $v^{-}$ cannot
both be real multiples of $v$. So $v$ is reducible. ∎

We are now ready to bound the complexity of irreducible balanced vectors. The
key idea is to consider the support of such a vector and think about solving
for the values of the nonzero entries.

######  Theorem 4.6.

Let $v$ be an irreducible balanced vector in $\mathbb{R}^{2^{[N]}}$ with
complexity $m$. Then

$m\leq\max_{A\in\\{0,1\\}^{N\times N}}\det A\leq(N+1)^{(N+1)/2}/2^{N}.$

###### Proof.

Without loss of generality scale $v$ so that it has relatively prime integer
entries. In particular we have $B_{N}v=m1_{[N]}$.

Let $\\{I_{1},\dots,I_{\ell}\\}=\\{1_{I}\colon v_{I}>0\\}$. Note that
$\ell\leq N$ by Lemma 4.5. If $\ell<N$ choose $N-\ell$ more sets
$J_{\ell+1},\dots,J_{N}$ such that the set of vectors
$\\{1_{I_{1}},\dots,1_{I_{\ell}},1_{J_{\ell}+1},\dots,1_{J_{N}}\\}$ is
linearly independent.

Let $x$ be the $N\times 1$ column vector with $i$-th entry $v_{I_{i}}$ for
$i\leq\ell$ and all other entries $0$. Let $A$ be the $N\times N$ matrix with
$i$-th column $v_{I_{i}}$ for $i\leq\ell$ and $i$-th column $v_{J_{i}}$ for
$i>\ell$. Then we have that

$Ax=m1_{[N]}.$

Now, consider solving for $x$ by treating this as a linear system in the
entries of $x$. By Cramer’s rule, we have that
$v_{I_{i}}=x_{i}=m\det(A_{i})/\det(A)$, where $A_{i}$ is the matrix $A$ with
the $i$-th column replacing by $1_{[N]}$. Since the values $x_{i}$ are
positive integers that are collectively relatively prime, we must have that

$m=\frac{\det(A)}{\gcd(\det(A_{1}),\dots,\det(A_{\ell}),\det(A))}\leq\det(A).$

Now by Hadamard’s inequality and Lemma 4.4, we have that
$m\leq(N+1)^{(N+1)/2}/2^{N}$, as desired. ∎

We can extend this result to $\mathbb{Z}$-irreducibility using Carathéodory’s
Theorem, losing a negligible factor of $2^{N}$.

######  Theorem 4.7.

Let $\mathcal{M}$ be a $\mathbb{Z}$-irreducible multiset with complexity $m$.
Then $m\leq(N+1)^{(N+1)/2}$.

###### Proof.

Let $v=v(\mathcal{M})$. By Carathéodory’s Theorem, we can write $v$ as a
positive linear combination of irreducible balanced vectors
$v_{1},\dots,v_{r}$ with $r\leq 2^{N}$. Without loss of generality, each
$v_{j}$ has relatively prime integer entries.

Now, let $v=\sum_{j=1}^{r}\lambda_{j}v_{j}$ for some reals $\lambda_{j}\geq
0$. Note that $\lambda_{j}<1$ because otherwise we could reduce $\mathcal{M}$
from $v=v_{j}+(v-v_{j})$.

Now we have that

$m(\mathcal{M})1_{[N]}=m(v)1_{[N]}=B_{N}v=B_{N}\sum_{j=1}^{r}\lambda_{j}v_{j}=\sum_{j=1}^{r}\lambda_{j}B_{N}v_{j}=\sum_{j=1}^{r}\lambda_{j}m(v_{j})1_{[N]}.$

So, by Theorem 4.6 we have that

$m(v)=\sum_{j=1}^{r}\lambda_{j}m(v_{j})<r(N+1)^{(N+1)/2}/2^{N}\leq(N+1)^{(N+1)/2}.$

∎

To construct a lower bound on the largest possible complexity $m$, it suffices
to construct a matrix $A$ with large determinant such that the gcd factor is
small. It is unlikely that all matrices $A$ with large determinant also give a
large gcd factor, but we have not established this yet. We expect that a lower
bound is possible losing at most a factor of $c^{N}$ for some
$c\in\mathbb{R}$.

######  Theorem 4.8.

The number of distinct irreducible balanced vectors is $(1-o(1))2^{N^{2}}/N!$.

###### Proof.

Recall that each irreducible balanced vector is supported on most $N$ distinct
sets. For each choice of $N$ distinct sets, we can solve for the unique
irreducible balanced vector supported on a subset those sets. So we have an
upper bound of

$\binom{2^{N}}{N}=(1-o(1))\frac{2^{N^{2}}}{N!}.$

Now, consider sampling a matrix $A$ from all matrices $N\times N$ matrices
with $\\{0,1\\}$ entries, uniformly at random. Then construct matrices $A_{i}$
for $1\leq i\leq N$ by replacing the $i$-th column of $A$ with $\vec{1}_{N}$.

Since $M_{N}$ and $M_{N+1}$ are singular with probability $o(1/N)$, by Lemma
4.4, we have that $A,A_{1},\dots,A_{N}$ are each singular with probability at
most $(\frac{1}{2}+o(1))^{-N+1}$. So by a union bound we have that all of
$A,A_{1},\dots,A_{N}$ are invertible with probability $1-o(1)$. Now we focus
on the $(1-o(1))2^{N^{2}}$ matrices $A$ for which this holds.

When we solve $Ax=\vec{1}_{N}$, all entries of $x$ will be nonzero. This gives
us a irreducible sequence with exactly $n$ distinct sets. Over all matrices
$A$, we will obtain each such sequence exactly $N!$ times, giving a lower
bound of $(1-o(1))\frac{2^{N^{2}}}{N!}$ ∎

This also shows that almost all irreducible sequences have exactly $N$
distinct sets. Also note that we can obtain a smaller error term by using the
full strength of Tikhomirov’s result in [12].

Obtaining an upper bound for the number of $\mathbb{Z}$-irreducible sequences
is more difficult. We can obtain a weak bound by counting all possible
sequences with $m\leq(N+1)^{(N+1)/2}$ or via Carathéodory’s Theorem, but this
unlikely to be tight.

##  5\. Upper Bounds for Irreducible Supermodular Functions

In this section we analyze irreducible supermodular functions. We consider the
vector of supermodularity values $s\in\mathbb{R}^{\mathcal{P}_{n}}$, indexed
by square faces of the hypercube. We have that $s$ lies in a fixed subspace of
dimension $2^{n}-n-1$ given the restrictions from Section 3. For $s$ to be
irreducible, it must lie on an extreme ray of the cone $s\geq 0$ in this
subspace. In particular, any irreducible $s$ must satisfy $2^{n}-n-2$ linearly
independent conditions of the form $s_{I,J}=0$. These conditions allow us to
solve for $s$ up to a scaling factor. So, we obtain the following theorem.

######  Theorem 5.1.

There are at most $\binom{n^{2}2^{n}}{2^{n}}$ irreducible supermodular
functions up to equivalence.

###### Proof.

For each irreducible $s$, take $2^{n}-n-2$ linearly independent conditions of
the form $s_{I,J}=0$ that determine $s$. Thus the number of possible
irreducible $s$ is at most

$\binom{\binom{n}{2}2^{n-2}}{2^{n}-n-2}\leq\binom{n^{2}2^{n}}{2^{n}}$

∎

This bound is clearly not tight. However, as we see in Section 6 the true
growth rate is in fact exponential in $2^{n}$.

As in the previous section, we can also obtain a bound on complexity. In this
case, we define the _complexity_ of an irreducible supermodular $f$ as the
maximum weight of a color of $s=Tf$ (defined in Theorem 3.6) after scaling $s$
to have relatively prime integer entries.

######  Theorem 5.2.

Let $f$ be an irreducible supermodular function. Then the complexity of $f$ is
at most $2^{n^{2}2^{n}}$.

###### Proof.

As in the proof of Theorem 4.6, we consider solving for $s$. Pick $2^{n}-n-2$
pairs ${I,J}$ with $s_{I,J}=0$ which allow us to determine $s$. Now consider
the matrix $A$ in which the top $\binom{n}{2}2^{n-2}-(2^{n}-n-2)$ rows
determine the subspace $\operatorname{im}T$, the next $2^{n}-n-2$ rows enforce
$s_{I,J}=0$, and the last row has all $1$’s to account for scaling. For an
irreducible $s$ with integer entries, we have that $As$ is a vector with all
$0$ entries except the last entry.

As in the proof of Theorem 4.6, it suffices to bound the determinant of $A$.
The first $\binom{n}{2}2^{n-2}-(2^{n}-n-2)$ rows each have norm $2$. The next
$2^{n}-n-2$ rows have norm $1$. The last row has norm at most $n2^{n/2}$. So
by Hadamard’s inequality we have that the determinant of $A$ is at most

$2^{\binom{n}{2}2^{n-2}-(2^{n}-n-2)}n2^{n/2}\leq 2^{n^{2}2^{n}}.$

∎

##  6\. Lower bounds for irreducible supermodular functions

In this section we prove a double-exponential lower bound on the number of
irreducible supermodular functions. We do this by relating a special class of
supermodular functions to matroids.

######  Definition 6.1.

We say that a supermodular function $f$ is _simple_ if the nondecreasing
function $\partial_{i}f$ is irreducible or constant for each $i\in[n]$.

######  Lemma 6.2.

Let $f$ be a simple supermodular function. If $f$ is not irreducible, then
there exists a partition $[n]=S_{1}\cup S_{2}$ and simple functions
$g_{1}\colon 2^{S_{1}}\to\mathbb{R}$ and $g_{2}\colon 2^{S_{2}}\to\mathbb{R}$
such that $f(I)=g_{1}(I\cap S_{1})+g_{2}(I\cap S_{2})$ for all $I$.

###### Proof.

Suppose that $f=g_{1}+g_{2}$. WLOG each of $f,g_{1},g_{2}$ are standard. For
each $i$, $\partial_{i}f=\partial_{i}g_{1}+\partial_{i}g_{2}$. Since
$\partial_{i}f$ is irreducible as a nondecreasing function, one of
$\partial_{i}g_{1}$ and $\partial_{i}g_{2}$ is $0$. Then we can take
$S_{1}=\\{i\colon\partial_{i}g_{2}=0\\}$ and $S_{2}=[n]\setminus S_{1}$. ∎

Recall that a _matroid_ $M$ consists of a ground set of elements $E$ and a
collection of bases $\mathcal{B}\subseteq 2^{E}$ satisfying the following
exchange axiom: for each pair of bases $A,B\in\mathcal{B}$ and $a\in
A\setminus B$, there exists $b\in B\setminus A$ such that
$A\cup\\{b\\}\setminus\\{a\\}\in\mathcal{B}$.

We will work with matroids $M$ on the ground set $E=[n]$. Recall that each
matroid has a rank $r$ which is the size of every base. Additionally, we can
define a rank function on subsets $I$ of $E$ by
$\operatorname{rank}(I)=\min_{B\in\mathcal{B}}\left|I\cap B\right|$. We also
have the nullity function given by
$\operatorname{null}(I)=\left|I\right|-\operatorname{rank}(I)$. We say that
$I$ is an independent set if $\operatorname{null}(I)=0$.

Recall that a loop is an element of $E$ that is in no bases, and a coloop is
an element that is in every base. We also say that a matroid $M$ is
_reducible_ is we can partition the ground set $E$ into two nonempty sets
$E_{1}$ and $E_{2}$ and construct matroids $M_{i}$ on $E_{i}$ with bases
$\mathcal{B}_{i}$ such that

$\mathcal{B}=\\{B_{1}\cup B_{2}\colon
B_{1}\in\mathcal{B}_{1},B_{2}\in\mathcal{B}_{2}\\}.$

If there does not exist such a decomposition of $M$, we say that $M$ is
_irreducible_. Note that if a matroid on a ground set of at least $2$ elements
has a loop or a coloop, then it is reducible.

Next, we define a polytope associated with a matroid. Given a matroid $M$ on
$[n]$, its matroid polytope is the convex hull of the indicator vectors for
its bases. We use the following result of Gelfand, Goresky, MacPherson, and
Serganov [3].

######  Theorem 6.3 (Gelfand, Goresky, MacPherson, and Serganov).

Let $P$ be a polytope in $\mathbb{R}^{n}$ with vertices in $\\{0,1\\}^{n}$
such that each edge is a translate of $e_{i}-e_{j}$ for some $i,j\in[n]$. Then
$P$ is the matroid polytope of some matroid $M$ on $[n]$.

######  Theorem 6.4.

There exists a bijection between equivalence classes of simple supermodular
functions and loopless matroids on $[n]$. Furthermore, irreducible functions
correspond to irreducible matroids.

###### Proof.

Let $M$ be a matroid on $[n]$. Then we can construct a supermodular function
$f$ by defining $f(I)=\operatorname{null}(I)$. Since $M$ is loopless, we have
$\operatorname{null}(I)=0$ for $\left|I\right|\leq 1$. So, $f$ is the standard
representative for its equivalence class. Additionally $f$ is simple since for
any $i\in[n]$, $\partial_{i}f$ takes values in $\\{0,1\\}$.

Now suppose we have a simple function $f$ that is the standard representative
for its equivalence class. We will construct a matroid $M$ on $[n]$ with
$f(I)=\operatorname{null}(I)$. Consider the generalized permutohedron $P$
corresponding to $f$. Let $x$ be a vertex of $P$. Since $f$ takes integer
values, $x$ must have integer entries (otherwise we could perturb $x$ along a
line while keeping it inside $P$). We have $x_{i}\geq f(\\{i\\})=0$, and
$x_{i}\leq f([n])-f([n]\setminus\\{i\\})\in\\{0,1\\}$. So,
$x_{i}\in\\{0,1\\}$.

Now, consider an edge of $P$. It is parallel to $e_{i}-e_{j}$ for some
$i,j\in[n]$. Since the vertices of $P$ are in $\\{0,1\\}^{n}$, the edge must
be a translate of $e_{i}-e_{j}$. Thus by Theorem 6.3 we have that $P$ is the
matroid polytope of a matroid $M$. This gives that $M$ maps to $f$ by our map
above.

By Lemma 6.2, a matroid $M$ is irreducible exactly when the corresponding
supermodular function $f$ is irreducible. ∎

Let $m_{n}$ be the number of matroids on $[n]$. The following bounds for the
asymptotics of $m_{n}$ are known (all logarithms are in base $2$).

######  Theorem 6.5 (Bansal–Pendavingh–van der Pol [1]).

$\log\log m_{n}\leq n-\frac{3}{2}\log n+\frac{1}{2}\log\frac{2}{\pi}+1+o(1).$

######  Theorem 6.6 (Knuth [4]).

$\log\log m_{n}\geq n-\frac{3}{2}\log n+\frac{1}{2}\log\frac{2}{\pi}-o(1).$

######  Theorem 6.7 (Mayhew–Newman–Welsh–Whittle [6]).

The number of matroids on $[n]$ with a loop or a coloop is $o(m_{n})$.

Using these results, we easily obtain the following.

######  Theorem 6.8.

There are at least $2^{\left(\sqrt{2/\pi}-o(1)\right)2^{n}/n^{3/2}}$
irreducible supermodular functions.

###### Proof.

It suffices to lower bound the number of irreducible matroids. The number of
reducible matroids on $[n]$ is at most the number of matroids on $[n]$ with a
loop or coloop plus

$\sum_{t=2}^{\left\lfloor n/2\right\rfloor}\binom{n}{t}m_{t}m_{n-t}\leq
2^{n}m_{n-2}m_{\left\lfloor n/2\right\rfloor}\leq o(m_{n}).$

Here we used Theorem 6.5 and Theorem 6.6. So, with Theorem 6.7 we have that
the number of reducible matroids is $o(m_{n})$. Thus the number of irreducible
matroids is at least

$(1-o(1))m_{n}\geq 2^{\left(\sqrt{2/\pi}-o(1)\right)2^{n}/n^{3/2}}.$

∎

##  7\. Supermodularities on two layers

In this section, we analyze irreducible supermodular functions which are
nearly modular, for some notion of “nearly”. Let $\mathcal{P}_{n,t}$ denote
the set of close pairs $\\{I,J\\}$ with $\left|I\right|=\left|J\right|=t$, for
$t\in[n-1]$.

Suppose that $f$ is a supermodular function and let $s=Tf$ as in Section 3.
Suppose that $s$ is supported only on $\mathcal{P}_{n,t}$ for some fixed
$t\in[n-1]$. Then by iterating condition (3) of Theorem 3.6, we have that
$s_{I,J}$ is constant over $\mathcal{P}_{n,t}$. In particular, there is only
equivalence class of irreducible supermodular functions with supermodularities
supported on a single layer. As a generalized permutohedron, this corresponds
to the hypersimplex $\Delta_{n,n-t}$. Let
$\alpha_{n,t}=\max(0,\left|I\right|-t)$ be the corresponding standard
supermodular function.

A natural next step is to consider the case when $s$ is supported only on
$\mathcal{P}_{n,t}\cup\mathcal{P}_{n,t+1}$ for some fixed $t\in[n-2]$. Here we
allow the supermodularities to lie on two layers of the hypercube instead of
just one. Let $\mathcal{K}_{n,t}$ denote the set of standard irreducible
supermodular functions of this form.

The hypersimplices $\Delta_{n,n-t}$ and $\Delta_{n,n-t-1}$ correspond to the
elements $\alpha_{n,t},\alpha_{n,t+1}\in\mathcal{K}_{n,t}$ as seen above.
Additionally, we can lift the hypersimplex $\Delta_{n-1,n-t+1}$ in $n$
different ways to obtain a supermodular function in $\mathcal{K}_{n,t}$.
Specifically, for each $k\in[n]$, the corresponding function is

$\beta_{n,t,k}(I)=\max(0,\left|I\cap([n]\setminus\\{k\\})\right|-t).$

We will use the $n+2$ functions
$\mathcal{B}_{n,t}=\\{\alpha_{n,t},\alpha_{n,t+1},\beta_{n,t,1},\dots,\beta_{n,t,n}\\}$
to describe $\mathcal{K}_{n,t}$.

######  Theorem 7.1.

The elements of $\mathcal{K}_{n,t}$ other than $\alpha_{n,t}$ and
$\alpha_{n,t+1}$ are in bijection with subsets $S\subseteq[n]$ with
$\left|S\right|\in\\{1,n-1\\}$ or

$\min(t+1,n-t)<\left|S\right|<\max(t+1,n-t).$

The bijection is given by the map

$S\mapsto\sum_{k\in
S}\beta_{n,t,k}-\max(0,\left|S\right|-(t+1))\alpha_{n,t}-\max(0,\left|S\right|-(n-t))\alpha_{n,t+1}.$

###### Proof.

First, notice the identity

$\sum_{k\in[n]}\beta_{n,t,k}=(n-t-1)\alpha_{n,t}+t\alpha_{n,t+1}.$ (1)

Additionally, this is the only linear dependence in $\mathcal{B}_{n,t}$. Thus
$\dim\operatorname{span}\mathcal{K}_{n,t}\geq n+1.$

In fact, we claim that this is an equality. By Theorem 3.6, for any
$f\in\mathcal{K}_{n,t}$, we can solve for $s=Tf$ from the color path sums
$m_{1},\dots,m_{n}$ and any fixed supermodularity value on
$\mathcal{P}_{n,t}$, since each path sum has only two nontrivial terms. Since
$f$ is standard, we can solve for $f$ from $s$. Thus
$\dim\operatorname{span}\mathcal{K}_{n,t}=n+1.$

Now, let $f\in\mathcal{K}_{n,t}$ with $f\neq\alpha_{n,t},\alpha_{n,t+1}$ and
let $s=Tf$. By Equation 1, we can write $f$ as a linear combination of
$\mathcal{B}_{n,t}$ such that each $\beta_{n,t,k}$ has a nonnegative
coefficient $x_{k}$ and at least one of these coefficients is $0$. Now, note
that there must exist a close pair $\\{I,J\\}\in\mathcal{P}_{n,t}$ with
$s_{I,J}=0$. Otherwise, we could subtract a multiple of $\alpha_{n,t}$ from
$f$ while leaving a supermodular function. Thus the coefficient of
$\alpha_{n,t}$ is determined by the coefficients $x_{k}$; it is the minimum
supermodularity value of $\sum_{k\in[n]}x_{k}\beta_{n,t,k}$ on
$\mathcal{P}_{n,t}$. Note that $\beta_{n,t,k}$ is supermodular on a close pair
$\\{I,J\\}\in\mathcal{P}_{n,t}$ if and only if $k\not\in I\cup J$. So we
obtain that the coefficient of $\alpha_{n,t}$ is

$y_{1}=-\min_{\\{I,J\\}\in\mathcal{P}_{n,t}}\sum_{k\not\in I\cup
J}x_{k}=-\min_{\left|K\right|=t+1}\sum_{k\not\in K}x_{k}.$

Similarly, we obtain that the coefficient of $\alpha_{n,t+1}$ is

$y_{2}=-\min_{\\{I,J\\}\in\mathcal{P}_{n,t+1}}\sum_{k\in I\cap
J}x_{k}=-\min_{\left|K\right|=t}\sum_{k\in K}x_{k}.$

Next, we show that the coefficients $x_{k}$ only have one distinct nonzero
value. Consider $y_{1}$ and $y_{2}$ as functions of $\vec{x}=\\{x_{k}\\}$.
Note that both are piecewise linear. In particular, given $\vec{x}$ and
$\vec{x}^{\prime}$ with coordinates sharing a (weak) relative order, we have
that $y_{1}(\vec{x}+\vec{x}^{\prime})=y_{1}(\vec{x})+y_{1}(\vec{x}^{\prime})$.
Now, let $S\subseteq[n]$ consist of all $k$ such that $x_{k}$ is maximal. Let
$x_{k}^{\prime}=1$ for $k\in S$ and $x_{k}^{\prime}=0$ for $k\not\in S$. Then
have that

$g=\left(\sum_{k\in
S}\beta_{n,t,k}+y_{1}(\vec{x}^{\prime})\alpha_{n,t}+y_{2}(\vec{x}^{\prime})\alpha_{n,t+1}\right)$

is supermodular, and for sufficiently small $\varepsilon>0$, $f-\varepsilon g$
is supermodular. Thus $f$ must be a multiple of $g$. In particular, we can
assume $x_{k}=x_{k}^{\prime}\in\\{0,1\\}$ for each $k$. Then
$y_{1}=-\max(0,\left|S\right|-(t+1))$ and
$y_{2}=-\max(0,\left|S\right|-(n-t))$. Thus we have that each
$f\in\mathcal{K}_{n,t}$ with $f\neq\alpha_{n,t},\alpha_{n,t+1}$ corresponds to
an $S\subseteq[n]$ as claimed. It suffices to check with choices of $S$ give
an irreducible $f$. By symmetry, we only need to consider $\left|S\right|$.

First, we consider the case $\left|S\right|\leq\min(t+1,n-t)$. If
$\left|S\right|=0$, then $f=0$, so it is not irreducible. If
$\left|S\right|=1$, then $f=\beta_{n,t,k}$ for some $k$, so it is irreducible.
Otherwise, note that $y_{1}=y_{2}=0$, so we already have a decomposition of
$f$. So, $f$ is not irreducible.

Next, we consider the case $\left|S\right|\geq\max(t+1,n-t)$. If
$\left|S\right|=n$, then $f=0$ by Equation 1, so it is not irreducible. Now
assume $\left|S\right|<n$. By the above calculations for $y_{1}$ and $y_{2}$,
we have that for each $\ell\in[n]$,

$\gamma_{n,t,\ell}=\sum_{k\in[n]\setminus\\{\ell\\}}\beta_{n,t,k}-(n-t-2)\alpha_{n,t}-(t-1)\alpha_{n,t+1}$

is supermodular. We claim that $f=\sum_{\ell\in[n]\setminus S}\gamma_{\ell}.$
This follows by applying Equation 1 and comparing coefficients. So, if
$\left|S\right|<n-1$, then $f$ is not irreducible.

It remains to check that $f$ is irreducible if $\left|S\right|=n-1$ or

$\min(t+1,n-t)<\left|S\right|<\max(t+1,n-t).$

Now, since we know all possible elements of $\mathcal{K}_{n,t}$, we just need
to show that none of the claimed elements can be decomposed using the other
claimed elements. It suffices to check that for each ordered pair of claimed
elements, there exists a close pair on which the first is strictly
supermodular while the second is modular. This is a simple calculation, and we
omit the details.

∎

##  8\. Acknowledgements

We would like to thank Ashwin Sah and Mehtaab Sawhney for helpful comments on
random matrix theory. This research was conducted at SPUR at MIT in Summer
2022. We would like to thank the SPUR Directors David Jerison and Ankur Moitra
for organizing SPUR and for helpful conversations throughout the project.

## References

  * [1] Nikhil Bansal, Rudi A. Pendavingh, and Jorn G. van der Pol.  On the number of matroids.  Combinatorica, 35(3):253–277, Apr 2015.
  * [2] Satoru Fujishige.  Submodular Functions and Optimization.  Elsevier, 2005.
  * [3] I.M Gelfand, R.M Goresky, R.D MacPherson, and V.V Serganova.  Combinatorial geometries, convex polyhedra, and schubert cells.  Advances in Mathematics, 63(3):301–316, 1987.
  * [4] Donald E Knuth.  The asymptotic number of geometries.  Journal of Combinatorial Theory, Series A, 16(3):398–400, 1974\.
  * [5] A. D. Korshunov.  O chise monotonnykh bulevykh funktsii.  Probl. Kibern., 38:5–108, 1980.
  * [6] Dillon Mayhew, Mike Newman, Dominic Welsh, and Geoff Whittle.  On the asymptotic proportion of connected matroids.  European Journal of Combinatorics, 32(6):882–890, 2011.  Matroids, Polynomials and Enumeration.
  * [7] H. Pippenger.  Entropy and enumeration of boolean functions.  IEEE Transactions on Information Theory, 45(6):2096–2100, 1999\.
  * [8] Alexander Postnikov.  Permutohedra, associahedra, and beyond, 2005.
  * [9] Alexander Postnikov, Victor Reiner, and Lauren Williams.  Faces of generalized permutohedra, 2006.
  * [10] S. Promislow and Virginia Young.  Supermodular functions on finite lattices.  Order, 22, 11 2005.
  * [11] Terence Tao and Van Vu.  On random $\pm 1$ matrices: Singularity and determinant.  2004\.
  * [12] Konstantin Tikhomirov.  Singularity of random bernoulli matrices, 2018.
  * [13] Stanislav Živný, David A. Cohen, and Peter G. Jeavons.  The expressive power of binary submodular functions.  Discrete Applied Mathematics, 157(15):3347–3358, aug 2009.