# Fair Robust Assignment using Redundancy

Matthew Malencia1,2, Vijay Kumar1, George Pappas1, and Amanda Prorok2
Manuscript received: October 15, 2020; Revised: January 11, 2021; Accepted:
February 19, 2021.This paper was recommended for publication by Editor M. Ani
Hsieh upon evaluation of the Associate Editor and Reviewers’ comments.This
work was supported by ARL Grant DCIST CRA W911NF-17-2-0181, NSF Grant
CNS-1521617, ARO Grant W911NF-13-1-0350, ONR Grants N00014-20-1-2822 and ONR
grant N00014-20-S-B001, and Qualcomm Research. The first author acknowledges
support from the National Science Foundation Graduate Research Fellowship
under Grant No. DGE-1845298.1The first three authors are with GRASP
Laboratory, University of Pennsylvania, Philadelphia, PA 19104-6228.
<EMAIL_ADDRESS>first and fourth authors
are respectively co-affiliated and affiliated with University of Cambridge,
William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD, UK.
<EMAIL_ADDRESS>Object Identifier (DOI): see top of this
page.

###### Abstract

We study the consideration of fairness in redundant assignment for multi-agent
task allocation. It has recently been shown that redundant assignment of
agents to tasks provides robustness to uncertainty in task performance.
However, the question of how to fairly assign these redundant resources across
tasks remains unaddressed. In this paper, we present a novel problem
formulation for fair redundant task allocation, which we cast as the
optimization of worst-case task costs under a cardinality constraint. Solving
this problem optimally is NP-hard. We exploit properties of supermodularity to
propose a polynomial-time, near-optimal solution. In supermodular redundant
assignment, the use of additional agents always improves task costs.
Therefore, we provide a solution set that is $\alpha$ times larger than the
cardinality constraint. This constraint relaxation enables our approach to
achieve a super-optimal cost by using a sub-optimal assignment size. We derive
the sub-optimality bound on this cardinality relaxation, $\alpha$.
Additionally, we demonstrate that our algorithm performs near-optimally
without the cardinality relaxation. We show simulations of redundant
assignments of robots to goal nodes on transport networks with uncertain
travel times. Empirically, our algorithm outperforms benchmarks, scales to
large problems, and provides improvements in both fairness and average
utility.

###### Index Terms:

Multi-Robot Systems, Task Planning, Fairness, Submodular Optimization, Ethics
and Philosophy.

##  I Introduction

Fairness in algorithms has received increasing attention in both research [3,
4, 31] and policy [9, 27, 32]. Multi-agent task allocation algorithms
distribute resources among human-centric tasks, thus requiring the
consideration of fairness. Bias in these systems has myriad sources, such as
design choices [18], models and data [17], and interpretation of results [8].
In this paper, we focus on the fairness of the objective function. We
reevaluate the objective function of redundant multi-agent task allocation
under the consideration of fairness and propose an algorithm for solving for
this fair objective.

Multi-agent task allocation is studied across domains ranging from operations
research to robotics [10, 20, 35]. Because finding optimal allocations in this
combinatorial problem is challenging, most approaches assume deterministic
costs. However, real-world costs are uncertain. For example, in assigning
agents to spatially located goals, travel times and agent locations are not
deterministic [25]. To account for this uncertainty, previous approaches
define risk-based objective functions [37] or use risk constraints [35]. In
recent work, Prorok shows that redundant assignment provides robustness
against uncertainty and is complementary to existing approaches [24]. For
example, in time-sensitive applications such as rescue scenarios and robots
delivering life saving supplies [1], redundancy improves performance because
tasks are completed by the first robot to arrive based on the first-come
first-to-serve principle [24].

Figure 1: Redundant assignment answers the question, which task should receive
extra resources? Given an existing non-redundant assignment and respective
cost distributions (top right), a single redundant robot, Robot 2, can be
assigned to either task. Utilitarian approaches assign Robot 2 to Person 0
because of the higher improvement in cost (plot A), whereas fair approaches
assign Robot 2 to Person 1 because of their higher need (plot B).

The redundant assignment problem is classified as Single-Task Robots, Multi-
Robot Tasks with Instantaneous Assignment (ST-MR-IA) because each robot can
complete all tasks (ST) and multiple robots can be assigned to the same task
(MR) [12]. This problem can be cast as a set-partitioning problem which has
been proven to be strongly NP-hard [11]. ST-MR-IA problems require a global
optimization function. Traditional methods that optimize utilitarian welfare
[13] (the expected sum of costs) provide no guarantees for individual fairness
[26]. Figure 1 shows that utilitarian approaches seek the best absolute
improvement in task cost without accounting for individual task needs. In
human-centric applications such as rescue scenarios, delivery systems, and
ride-sharing, disparities in task performance yield disparities in the
treatment of individual people. This unfairness in utilitarian assignments
makes the system unfit with respect to broader social structures and causes a
lack of trust in the system. For this reason, it is crucial to consider _fair_
optimization objectives.

Fairness in redundant assignment is an especially important consideration
because the tasks served in these allocation problems are often both human-
centric and high-risk. For example, in rescue scenarios such as robots
delivering life saving supplies, the choice of how robots are allocated
impacts how long different individuals must wait for the life saving supplies.
This allocation strategy stems directly from the objective function chosen by
the system designer.

There exist many definitions of fair objectives [6, 19, 36]. For example,
proportional division seeks assignments that provide agents with equal
proportional utility but has no guarantees for indivisible resources [29], and
envy-freeness seeks assignments such that no agent prefers another agent’s
assignment over its own [2]. While fair objectives are often intra-personal
comparisons, where agents evaluate others’ assignments according to their own
utility function, experimental work shows that human behavior is better
predicted by inter-personal comparisons, where agents compare outcomes [14].
For redundant assignment, we seek to minimize the maximum cost among the set
of tasks. Specifically, we answer the question: how can we find a redundant
assignment that is fair to the worst-off task? Hence, we define an inter-task
criteria based on John Rawls’ veil of ignorance [26].

The ‘veil of ignorance’ thought experiment for the example of emergency supply
delivery is as follows. Imagine you get to choose the assignment of delivery
robots and you will be on the receiving end of this assignment, i.e., one of
the humans in need of life-saving supplies. However, you are ignorant of your
location. Rawls concludes that, under this veil of ignorance, the rational
conclusion is to choose an assignment that benefits the person with the
longest waiting time, since this person could be you. This definition of
fairness is often formulated as a minimax or maximin problem [36]. We cast
this problem as the optimization of worst-case expected task cost.

###  I-A Related Work

Noise and uncertainty in real-world applications require managing risk (known
unknowns) [5, 7, 16]. A common risk measure is Conditional Value at Risk
(CVaR), which is the expectation of the tail of a distribution. Wilder [33]
and Zhou et. al [37] use CVaR in approaches to submodular optimization. In
addition to risk measures, redundancy provides robustness to uncertainty.
Prorok [24] shows that redundant assignment improves task performance under
uncertainty and is complementary to traditional risk measures. We leverage
redundancy in this work to maintain the guarantees for satisfying all
constraints of the assignment problem while not precluding the incorporation
of traditional risk measures.

Most assignment problems, as well as many problems in robotics, optimize the
average expected utility. This default objective is mathematically convenient
but has been questioned under considerations such as fairness. Zhang and Shah
[36] define four maximin fairness criteria for multi-agent Markov Decision
Processes. These definitions of fairness are based on the Rawlsian theory of
justice [26]. The fairness criteria in this paper similarly applies Rawlsian
justice to redundant assignment. Mathematically, this definition is similar to
providing robustness to a worst-case objective. Therefore, we look to insights
from prior work solving minimax problems.

Minimax problems are difficult to solve because they are highly nonlinear and
combinatorial in nature. Uncertainty adds additional complexity to this
problem. Because it is NP-hard to solve these problems optimally, approaches
exploit mathematical properties of problem formulations to produce polynomial-
time, near-optimal solutions. One such property is supermodularity, the
property of diminishing returns (see Appendix -A). Supermodular objectives (or
in many cases, submodular) can be solved using simple greedy algorithms with a
$\frac{1}{2}$ bound on optimality [21]. Many objective functions are naturally
supermodular, such as information gain [28] and real-world monetary costs
[22]. Submodularity has also been exploited to create robustness to worst-case
objectives [15] and arises naturally in redundant task assignments as it
captures the attribute of diminishing returns [24].

In a closely related work, Krause [15] defines the Robust Submodular
Observation Selection problem, where the goal is to select an observation set
that is robust against the worst-case of multiple objective functions. This
work is grounded in the example of sensor placement for monitoring an
environmental process. The problem involves finding a set of sensor locations,
$\mathcal{A}$, that is a subset of all possible sensor locations, $V$. There
exists a set of $J_{j}(\mathcal{A})$ that measure the variance reduction at
locations $j$. The objective is to choose $k$ sensor locations that maximize
the minimum variance reduction (equivalent to minimizing the maximum
variance). This problem is formulated as $\max_{\mathcal{A}\subseteq
V}\quad\min_{j}J_{j}(\mathcal{A})\quad\text{s.t.}\quad|\mathcal{A}|\leq k$ ,
where each $J_{1},\ldots,J_{M}$ are normalized monotonic submodular functions.

To solve this problem, Krause [15] proposes the Saturate algorithm, which
finds an approximate solution by relaxing the cardinality constraint, with
guarantees on this relaxation. Powers et. al [23] extend this work for any
matroid constraint. They propose the Generalized Saturation algorithm to solve
this problem by relaxing the objective. They guarantee that only a fraction of
the set of objective functions exceed a threshold. In contrast to these works,
we solve a problem under both assignment constraints and a cardinality
constraint whereby our algorithm relaxes the constraint on cardinality.

###  I-B Contributions

We propose a novel problem formulation that (for the first time) formalizes
the fair redundant task allocation problem. Redundancy serves to improve
performance under risk. An assumption of supermodularity enables performance
guarantees. Notably, we are the first to develop an algorithm for solving a
fair redundant assignment problem. Our main contributions are as follows:

  * •

We define the Fair Supermodular Redundant Assignment Problem as the
minimization of the maximum expected cost across tasks under assignment
constraints and cardinality constraints.

  * •

We propose an efficient algorithm to solve the Fair Supermodular Redundant
Assignment problem approximately by relaxing the cardinality constraint.

  * •

We prove a bound on this relaxation and the computational complexity of our
approach.

We analyze our algorithm in simulation, showcasing our theory empirically,
demonstrating that our algorithm outperforms benchmarks, and analyzing a case
study to compare the fairness of our algorithm to prior work.

##  II Preliminaries

The problem space in this paper is represented by a graph
$\mathcal{B}=(\mathcal{U},\mathcal{F},\mathcal{C})$. The set of vertices
$\mathcal{U}$ is partitioned into two disjoint sets $\mathcal{U}_{a}$ and
$\mathcal{U}_{t}$, the sets of agent nodes and task nodes, respectively. The
edge set
$\mathcal{F}=\left\\{(i,j)\;|\;i\in\mathcal{U}_{a},j\in\mathcal{U}_{t},\;\forall\;i,j\right\\}$
defines all possible agent-task pairings available for assignment. For each
$(i,j)$ pair in $\mathcal{F}$, there exists a corresponding cost
$\mathcal{C}_{i,j}$, which is a random variable. The set of all
$\mathcal{C}_{i,j}$ is the cost set, $\mathcal{C}$. While specific instances
of this problem can constrain $\mathcal{C}$, we make no assumptions on the
form, independence, or correlations of the elements of $\mathcal{C}$.

There are $M$ tasks and $N$ agents, and a total deployment size, $N_{d}$,
specified as an input. Each task $j$ has a corresponding cost function
$J_{j}(\cdot)$ mapping the cost set $\mathcal{C}$ to a real number.111We later
assume that all $J_{j}(\cdot)$ are supermodular. For example, $J_{j}(\cdot)$
could be the sum, minimum, or product of the costs $\mathcal{C}_{i,j}$ for
agents $i$ assigned to task $j$. These cost functions represent how a set of
redundant agents complete a task; the functions map a subset of the assignment
to a real valued cost. In this paper we consider the minimum operator,
representing the first-come first-to-serve principle [24].

Fair assignment seeks a pairing of agents to tasks that minimizes the maximum
task cost, where agents cannot be assigned multiple tasks, tasks must be
assigned at least one agent, and the number of agents is no more than $N_{d}$.
This problem is formulated as finding a subset of the ground set that
minimizes the maximum cost:
$\min_{\mathcal{A}\subseteq\mathcal{F}}\;\max_{j}J_{j}(\mathcal{A})$. This
assignment, $\mathcal{A}$, has a constrained cardinality of $|\mathcal{A}|\leq
N_{d}$, and assignment constraints per agent and task. The optimization is
formulated with the introduction a second decision variable $\xi$ and
constraint of all $J_{j}(\mathcal{A})$ by $\xi$. Finding the minimum $\xi$
such that all $J_{j}(\mathcal{A})\leq\xi$ equivalently minimizes
$\max_{j}J_{j}(\mathcal{A})$.

######  Definition 1.

_Fair Assignment:_ Given N agents and M tasks with uncertain agent-task
assignment costs, find an assignment $\mathcal{A}\subseteq\mathcal{F}$ no
larger than $N_{d}\geq M$ and minimum cost bound $\xi\in\mathbb{R}$, such that
no costs $J_{j}(\mathcal{A})$ exceed $\xi$. Formally:

$\displaystyle\min_{\xi,\mathcal{A}\subseteq\mathcal{F}}$ $\displaystyle\xi$
(1) s.t. $\displaystyle J_{j}(\mathcal{A})\leq\xi,\quad\forall j$
$\displaystyle|\mathcal{A}|\leq N_{d}$
$\displaystyle\forall\;i,\;|\\{j\;|\;(i,j)\in\mathcal{A}\\}|\;\leq 1$
$\displaystyle\forall\;j,\;|\\{i\;|\;(i,j)\in\mathcal{A}\\}|\;\geq 1$

Fair assignment is a set-partitioning problem and has been shown to be
strongly NP-hard [11]. Approaches that solve similar problems do not have
guarantees on all of these constraints [37, 38]. To ensure that both
assignment constraints are met and to reduce uncertainty through redundancy,
we define the Fair Supermodular Redundant Assignment problem.

##  III Problem Statement

Consider a system of $M$ tasks and $N$ agents, where each agent-task pairing
has random cost, represented by an arbitrary probability
distribution.222Specific instances of this problem can restrict these
distributions, but we make no assumptions on their form, independence, or
correlations. For each of the $M$ tasks, a cost function is defined. Our goal
is to find an assignment that:

  * •

minimizes the maximum task cost,

  * •

uses at most $N_{d}$ agents,

  * •

assigns each agent to at most one task, and

  * •

ensures no task is unassigned ($N_{d}\geq M$).

Redundant assignment, where multiple agents can be assigned the same task,
provides robustness against uncertainty and improvements to expected
performance of tasks [24]. If tasks have deterministic costs, this problem
simplifies to the linear bottleneck assignment problem which can be solved
using the thresholding algorithm [30]. The presence of uncertainty, however,
requires a new approach to this optimization.

This section describes a flexible mathematical formulation of fair assignment
under two assumptions:

Assumptions. (1) all cost functions, $J_{j}(\cdot)$, must be
supermodular,333$J_{j}(\cdot)$ can each be different functions but should be
similarly scaled so that comparisons among different cost functions are
meaningful. and (2) a prior non-redundant assignment exists.

The first assumption is that all cost functions are supermodular, i.e., they
have the property of diminishing return. However, we are solving for the
maximum of a set of supermodular functions, which is generally not
supermodular (see Appendix -A). Therefore, the greedy algorithm has no
performance guarantees for this problem. Simple examples, as shown by Krause,
prove that the greedy algorithm applied to this problem can perform
arbitrarily badly [15].

The second assumption requires an initial non-redundant assignment exists,
denoted $\mathcal{O}$, such as one found through standard assignment methods
(e.g., threshold algorithm for the linear bottleneck assignment problem). This
assumption guarantees that all tasks are assigned at least one agent, thus
eliminating this constraint. Additionally, this assumption enables
tractability and ensures the supermodularity of cost functions (e.g.,
unassigned tasks potentially have infinite cost, breaking supermodularity).
With this assumption, we focus strictly on assigning the redundant agents.
Therefore, the ground set becomes $\mathcal{F}\backslash\mathcal{O}$, denoted
$\mathcal{F}_{\mathcal{O}}$. Cost functions remain denoted
$J_{j}(\mathcal{A})$ though they are a function of $\mathcal{A}$ given
$\mathcal{O}$.

These two assumptions on Definition 1 yield Problem 1, the Fair Supermodular
Redundant Assignment problem. The constraint in Definition 1 that all tasks be
completed is guaranteed by the initial assignment (Assumption 2), and
therefore omitted. All cost functions, $J_{j}(\mathcal{A})$, are assumed to be
supermodular and are a function of $\mathcal{A}$ given $\mathcal{O}$.

######  Problem 1.

_Fair Supermodular Redundant Assignment:_ Given N agents, M tasks with
uncertain agent-task assignment costs, and an initial assignment
$\mathcal{O}$, find an assignment
$\mathcal{A}\subseteq\mathcal{F}_{\mathcal{O}}$ and minimum cost bound
$\xi\in\mathbb{R}$, such that no cost $J_{j}(\mathcal{A})$ exceeds $\xi$,
assuming all functions $J_{j}(\mathcal{A})$ are supermodular. Formally:

$\displaystyle\min_{\xi,\mathcal{A}\subseteq\mathcal{F}_{\mathcal{O}}}$
$\displaystyle\xi$ (2) s.t. $\displaystyle
J_{j}(\mathcal{A})\leq\xi,\quad\forall j$ $\displaystyle|\mathcal{A}|\leq
N_{d}-M$
$\displaystyle\forall\;i,\;|\\{j\;|\;(i,j)\in\mathcal{A}\cup\mathcal{O}\\}|\;\leq
1$

This formulation is general and flexible enough to be applied to many
assignment problems, as long as the cost functions are supermodular. One such
example is the assignment of agents with uncertain travel times to spatially
located tasks. In this example, the cost at each node is defined as the
expected waiting time,
$J_{j}(\mathcal{A})=\underset{c}{\mathbb{E}}\left[\min_{i}\left\\{C_{ij}|(i,j)\in\mathcal{A}\cup\mathcal{O}\right\\}\right]$.
The minimum operator here represents the first-come first-to-serve principle
introduced by Prorok [24], who showed that this function is supermodular.

##  IV Approach

The algorithm presented in this section provides an approximate solution,
$\mathcal{A}_{f}$, to the Fair Supermodular Redundant Assignment problem. The
solution is approximate because we relax the cardinality constraint for
tractability purposes: the solution $\mathcal{A}_{f}$ can be $\alpha$ times
larger than the size of the optimal assignment (this section elaborates on the
bound on $\alpha$). By relaxing the size of the solution, this assignment is
guaranteed to have a maximum cost that is at most equal to the maximum cost of
the optimal solution $\mathcal{A}^{*}$. That is, the approximate solution
$\mathcal{A}_{f}$ has a cost that is less than that of $\mathcal{A}^{*}$ but a
size that is larger. This section outlines the algorithm, a bound on the
cardinality relaxation $\alpha$, the limits on the deployment size $N_{d}$,
and the computational complexity of this approach.

###  IV-A The Relaxed Fair Supermodular Redundant Assignment Problem

The basic premise of our approach to solving Problem 1 is to conduct half-
interval search on possible values of $\xi$ and to solve a sub-problem to
determine which half-interval cannot contain the target solution. Suppose
there exists an algorithm that finds the smallest assignment that yields a
maximum task cost of at most $\xi$, which is given as an input:

$\displaystyle\underset{\mathcal{A}\subseteq\mathcal{F}_{\mathcal{O}}}{\text{argmin}}$
$\displaystyle|\mathcal{A}|$ (3) s.t. $\displaystyle
J_{j}(\mathcal{A})\leq\xi,\quad\forall j$
$\displaystyle\forall\;i,\;|\\{j\;|\;(i,j)\in\mathcal{A}\cup\mathcal{O}\\}|\;\leq
1$

This sub-problem returns a candidate solution $\mathcal{A}_{s}$. If
$\mathcal{A}_{s}$ has a cardinality that is at most $N_{d}-M$, then
$\mathcal{A}_{s}$ and the given value of $\xi$ are feasible for Problem 1. If
$|\mathcal{A}_{s}|>N_{d}-M$, then $\mathcal{A}_{s}$ and the $\xi$ value are
not feasible. Solving this sub-problem determines whether a given value of
$\xi$ is feasible. Therefore, half-interval search can find the optimal
(minimum feasible) value of $\xi$. Given a starting range of possible $\xi$
values, the midpoint is tested for feasibility. If feasible, the half-interval
below the midpoint contains the optimal value and thus becomes the new range
of possible $\xi$ values. Otherwise, the higher half-interval becomes the new
range. This procedure repeats until convergence, at which point the returned
$\mathcal{A}_{s}$ and $\xi$ are guaranteed to be optimal.

However, Krause proves with Theorem 3 [15] that unless $P=NP$, there cannot
exist any polynomial time approximation algorithm for Problem 1. In other
words, unless $P=NP$, the sub-problem in equation (3) cannot be solved in
polynomial time. To enable a polynomial time approximation algorithm for
Problem 1, the cardinality constraint is relaxed by $\alpha$. This results in
the relaxed Fair Supermodular Redundant Assignment problem, with $\alpha>1$:

$\displaystyle\min_{\xi,\mathcal{A}\subseteq\mathcal{F}_{\mathcal{O}}}$
$\displaystyle\xi$ (4) s.t. $\displaystyle
J_{j}(\mathcal{A})\leq\xi,\quad\forall j$
$\displaystyle|\mathcal{A}|\leq\alpha(N_{d}-M)$
$\displaystyle\forall\;i,\;|\\{j\;|\;(i,j)\in\mathcal{A}\cup\mathcal{O}\\}|\;\leq
1$

This relaxed problem can now be solved with the aforementioned half-interval
procedure. Given a value $\xi$, the sub-problem of the relaxed Fair
Supermodular Redundant Assignment problem is still equation (3). However, the
relaxation on the cardinality constraint changes the update step of the half-
interval search. We begin with a range of values $[\xi_{min},\xi_{max}]$,
where $\xi_{min}=0$ because costs are strictly positive and $\xi_{max}$ is the
worst waiting time after the initial assignment, $\max_{j}J_{j}(\emptyset)$.
Given the mid-point of this range, the sub-problem returns a candidate
solution $\mathcal{A}_{s}$. Previously, the cardinality of $\mathcal{A}_{s}$
was compared to $N_{d}-M$ to determine its feasibility. Because of the
cardinality relaxation, the cardinality of $\mathcal{A}_{s}$ now informs
either the infeasibility of the original problem or the feasibility of the
relaxed problem, adjusting the respective bounds:

  * •

If $|\mathcal{A}_{s}|>\alpha(N_{d}-M)$, then $\xi$ is not a feasible solution
to the original problem.444Or if there does not exist a feasible
$\mathcal{A}_{s}$. Set $\xi_{min}=\xi$.

  * •

If $|\mathcal{A}_{s}|\leq\alpha(N_{d}-M)$, then $\xi$ is a feasible solution
to the relaxed problem. Set $\xi_{max}=\xi$.

To guarantee a solution, the number of agents used after the relaxation,
$\alpha(N_{d}-M)$, must not exceed the number of agents available, $N-M$.
Thus, set $N_{d}\leq\frac{N-M}{\alpha}+M$.

Through this point, we have assumed that there exists an approach to solving
the sub-problem defined in equation (3) above. We have also assumed that this
solution satisfies the relaxed cardinality constraint $\alpha$. The rest of
this section describes both an algorithm that solves this sub-problem and the
bound on the cardinality relaxation $\alpha$.

###  IV-B Algorithm Details

We seek an algorithm to sub-problem (3) that finds the smallest set
$\mathcal{A}$ such that all cost functions $J_{j}(\mathcal{A})$ are below a
given cost budget $\xi$. We build on the prior work of Prorok on optimal
matching of redundant agents under a cost budget [24]. Leveraging this work
requires two challenges to be addressed. First, Prorok uses a single
supermodular function constraint while we constrain a set of $M$ supermodular
functions. Second, the relaxation of this sub-problem must hold for all
iterations of the half-interval search.

We transform equation 3 to have a single supermodular cost constraint. Let
$\hat{J}_{j}(\mathcal{A})$ be the truncated function
$\max\\{J_{j}(\mathcal{A}),\xi\\}$ and form a single constraint of the average
of the set of $\hat{J}_{j}(\mathcal{A})$. This constraint is equivalent to the
original set of cost constraints. The average of truncated cost functions less
than $\xi$ implies that all cost functions are less than $\xi$. Additionally,
truncation and the average function preserves supermodularity. Because the
average of the truncated cost functions has a minimal value of $\xi$, the
inequality constraint becomes an equality constraint.

$\displaystyle\underset{\mathcal{A}\subseteq\mathcal{F}_{\mathcal{O}}}{\text{argmin}}$
$\displaystyle|\mathcal{A}|$ (5) s.t.
$\displaystyle\frac{1}{M}\sum_{j}\hat{J}_{j}(\mathcal{A})=\xi$
$\displaystyle\forall\;i,\;|\\{j\;|\;(i,j)\in\mathcal{A}\cup\mathcal{O}\\}|\;\leq
1$

Prorok’s greedy algorithm [24] is shown to solve this problem in polynomial
time with a bound (which we call $\alpha$) on the ratio of the solution set
size to the optimal solution set size. However, to use this approximation
algorithm in the half-interval search, the bound on $\alpha$ must be
independent of $\xi$. Theorem 1 below details a $\xi$-independent bound on
$\alpha$.

We solve Problem 1 with Algorithm 1, Fair Supermodular Redundant Assignment.
After initialization, Algorithm 1 conducts a half-interval search over $\xi$.
For each value of $\xi$, Prorok’s Greedy Redundant Assignment (GRA) with
dynamic programming [24] greedily assigns agent-task pairs until either all
costs are below $\xi$ or all agents are assigned. The output of GRA is then
used to update the range of $\xi$ to continue the half-interval search until
convergence.

Algorithm description. The inputs required are $M$ cost functions $J_{j}$ that
are all supermodular, a deployment size $N_{d}\geq M$, a relaxation constant
$\alpha\geq 1$, and an initial non-redundant assignment $\mathcal{O}$ that can
be found using traditional methods such as the thresholding algorithm for the
linear bottleneck assignment problem. Lines 1-3 initialize the range of $\xi$
and the output solution $\mathcal{A}_{f}$. The while loop beginning at line 5
is the half-interval search, whose interval bounds are updated in lines 8-13.
Given a value $\xi$ (line 6) and the average truncated cost function defined
in line 1, the sub-problem in equation 5 is solved (line 7). The solution of
this sub-problem, $\mathcal{A}_{s}$, is then used to update the half-interval
search range. If $|\mathcal{A}_{s}|\leq\alpha(N_{d}-M)$, $\xi$ is a feasible
approximate solution to Problem 1. $\xi_{max}$ is updated and
$\mathcal{A}_{s}$ is kept as the best candidate solution, $\mathcal{A}_{f}$.
If $|\mathcal{A}_{s}|>\alpha(N_{d}-M)$, there is no feasible solution to
Problem 1 for the given value of $\xi$, and $\xi_{min}$ is updated. For every
iteration of the half-interval search, $\xi_{min}$ is guaranteed to be
infeasible, i.e., lower than minimum $\xi$ in Problem 1. Therefore, the half-
interval search converges to $\xi\leq\xi^{*}$ and the returned solution
$\mathcal{A}_{f}$ is guaranteed to satisfy
$|\mathcal{A}_{f}|\leq\alpha(N_{d}-M)$.

Theorem 1 states that the Fair Supermodular Redundant Assignment algorithm
returns a solution $\mathcal{A}_{f}$ with a cost that is at worst equivalent
to the cost achieved by $\mathcal{A}^{*}$ but a solution size that is up to
$\alpha$ time larger, as defined in equation (6). The algorithm works for any
value of $\alpha\geq 1$, but values differing from that defined in equation
(6) will not have the guarantees stated in Theorem 1.

######  Theorem 1.

The Fair Supermodular Redundant Assignment algorithm guarantees that

$\max_{j}J_{j}(\mathcal{A}_{f})\leq\min_{|\mathcal{A}|\leq
N_{d}}\max_{j}J_{j}(\mathcal{A})\quad\text{and}\quad|\mathcal{A}_{f}|\leq\alpha
N_{d}$

for a given $N_{d}$ and $\alpha=1+\log(\max_{j}J_{j}(\emptyset)-1)$. The
number of function evaluations is

$O\Big{(}(1+\log_{2}(M\max_{j}J_{j}(\emptyset))\;(N_{d}-M)NMS\Big{)}$

where $S$ is the number of samples taken from the cost distributions.

###### Proof.

Let $\bar{J}(\mathcal{A})=\frac{1}{M}\sum_{j}\hat{J}_{j}(\mathcal{A})$.
Prorok’s Proposition 3 [24] shows that for our sub-problem,
$\alpha=1+\log\frac{\bar{J}(\emptyset)-\xi}{\bar{J}\left(\mathcal{A}_{k-1}\right)-\xi}$,
where $\mathcal{A}_{k-1}$ is the set chosen by the greedy algorithm in its
penultimate step (i.e., the next assignment by the greedy algorithm achieves
$\xi$). Because $\bar{J}\left(\mathcal{A}_{k-1}\right)$ can be arbitrarily
close to $\xi$, the bound can tend towards infinity, preventing a
$\xi$-independent bound on $\alpha$. Assuming $J_{j}(\mathcal{A})$ only takes
integer values, though, limits $\bar{J}\left(\mathcal{A}_{k-1}\right)-\xi$ to
minimum value of one, and ensures $\xi\geq 1$ because costs are strictly
positive, thus yielding a $\xi$-independent bound of

$\alpha=1+\log(\max_{j}J_{j}(\emptyset)-1)\geq 1+\log(\bar{J}(\emptyset)-\xi)$
(6)

This result is similar to that derived by Wolsey [34]. Additionally, Krause
builds on Wolsey’s result to show in Section 7.1 [15] that integer objective
functions can be easily extended to take rational values by rounding by their
highest order bits, allowing a small additive approximation error. Simulations
in Section V show near-optimal performance without the need for this rounding.

The computational complexity comes from the number of times the half-interval
search runs $(1+\log_{2}(M\max_{j}J_{j}(\emptyset))$ [15] and the
$(N_{d}-M)NMS$ evaluations in the inner loop sub-problem [24]. ∎

Algorithm 1 Fair Supermodular Redundant Assignment

0: $J_{1},...,J_{M},N_{d},\alpha,\mathcal{O}$

0: Set of fair redundant assignments, $\mathcal{A}_{f}$

1: Define
$\bar{J}(\mathcal{A},\xi)=\frac{1}{M}\sum_{j}\max\\{J_{j}(\mathcal{A}),\xi\\}$

2: $\xi_{min}\xleftarrow{}0$

3: $\xi_{max}\xleftarrow{}\max_{j}J_{j}(\emptyset)$

4: $\mathcal{A}_{f}\xleftarrow{}\emptyset$

5: while $\xi_{max}-\xi_{min}\geq\frac{1}{M}$ do

6: $\xi\xleftarrow{}\frac{\xi_{min}+\xi_{max}}{2}$

7: $\mathcal{A}_{s}\xleftarrow{}\mathrm{GRA}(\bar{J},\xi,\mathcal{O})$

8: if $|\mathcal{A}_{s}|\leq\alpha(N_{d}-M)$ then

9: $\xi_{max}\xleftarrow{}\xi$

10: $\mathcal{A}_{f}\xleftarrow{}\mathcal{A}_{s}$

11: else

12: $\xi_{min}\xleftarrow{}\xi$

13: end if

14: end while

15: return $\mathcal{A}_{f}$

##  V Evaluation

We present Algorithm 1 as it applies the case study of robots with uncertain
travel times assigned to spatially located tasks, such as in emergency supply
delivery. The cost at each node is defined as the expected waiting time,
$J_{j}(\mathcal{A})=\underset{c}{\mathbb{E}}\left[\min_{i}\left\\{C_{ij}|(i,j)\in\mathcal{A}\cup\mathcal{O}\right\\}\right]$.
The minimum operator here represents the first-come first-to-serve principle
[24]. In other words, all robots have the emergency supplies (e.g., water or
medicine) to delivery to any task, and whichever robot arrives to a task
location first provides the supply thus accomplishing the task. This case
study seeks to minimize expected waiting time of the worst task while ensuring
the total deployment size (initial plus redundant assignment) is less than
$N_{d}$. Our case study includes three sets of simulations.

The first two sets of simulations use random bipartite graphs to empirically
showcase Theorem 1 and to demonstrate that Algorithm 1 outperforms benchmark
algorithms. The bipartite graphs in these simulations are abstract
representations of any problem that uses the first-come first-to-serve
principle. The last set of simulations uses a random transport network to
analyze a use case of Algorithm 1 and highlight the unfairness that can arise
from utilitarian assignment.

###  V-A Empirical Display of Theorem 1

In this section, we display and visualize Theorem 1 empirically by showcasing
that Algorithm 1 yields assignments with more-than-optimal cost when using the
cardinality relaxation of $\alpha=1+\log(\max_{j}J_{j}(\emptyset)-1)$ and near
optimal cost when $\alpha=1$. The former achieves super-optimality by using a
deployment size that is larger than the desired deployment size, while the
latter respects the desired deployment size but has no theoretical guarantees
on performance (though empirically near-optimal in most cases).

Cost of Algorithm 1 Compared to Optimal

Figure 2: Top. The percent difference in cost between the optimal assignment
and the assignments produced by Algorithm 1 displays our above proof that the
$\alpha$ value proven in Theorem 1 (left) yields super-optimal cost by using
larger than optimal assignments,and shows that $\alpha=1$ (right) yields near
optimal results. Note that positive values are sub-optimal (top) because the
problem is a minimization. Outliers are omitted. Bottom. The comparison of the
actual deployment size to the deployment size constraint shows that super-
optimality is achieved by relaxing the constraint, yielding larger assignments
and that $\alpha=1$ respects the deployment size constraint.

To show these results, Algorithm 1 must be compared to the optimal assignment.
Finding the optimal is extremely computationally expensive because it requires
brute force search over the power set. Therefore, this simulation set is
constrained to small examples. We represent a problem with 18 agents, 2 tasks,
and deployment sizes $[3,4,5,6,7]$ as a random bipartite graph,
$\mathcal{B}=(\mathcal{U},\mathcal{F},\mathcal{C})$. The small number of tasks
and deployment sizes are chosen for computational tractability of the optimal
solution, and the number of agents is chosen to allow for the cardinality
relaxation.

The set of vertices $\mathcal{U}$ is partitioned into two disjoint sets
$\mathcal{U}_{a}$ and $\mathcal{U}_{t}$, the set of agent nodes (size 18) and
task nodes (size 2), respectively. The graph is fully connected, i.e., every
node in $\mathcal{U}_{a}$ is connected to all nodes in $\mathcal{U}_{t}$. Each
edge has a corresponding cost random variable: a truncated Gaussian
distribution.555Algorithm 1 does not rely on any Gaussian assumption. Any
arbitrary distribution, discrete or continuous, can be used. These edges
represent the distribution of travel times from the agent location to the task
location (e.g., in minutes). Means are uniformly sampled from the range
$[15,~{}20]$, standard deviations uniformly sampled from the range
$[5,~{}10]$, and all distributions are truncated at 5 (restricting the minimum
travel time between any agent and task to 5).

Using these parameters, we create 1000 random bipartite graphs and implement
Algorithm 1 using $\alpha=1+\log(\max_{j}J_{j}(\emptyset)-1)$ and $\alpha=1$,
then calculate the brute force optimal solution. Figure 2 shows the aggregate
results over the 1000 trials. Because
$\alpha=1+\log(\max_{j}J_{j}(\emptyset)-1)$ depends on the problem instance,
the value of $\alpha$ is not constant among trials and ranges from
$[3.8,4.2]$. The left plots show that the cardinality relaxation yields
assignment sizes that are larger than the desired size but costs that are
better than optimal. On the right, using $\alpha=1$ respects the desired
deployment size while achieving near-optimal performance empirically. 666The
majority of trials using $\alpha=1$ are optimal; only the unshown outliers are
sub-optimal, which lie within 10% of optimal in these simulations.

Benchmark Comparisons of Algorithm 1

Figure 3: Fair redundant assignment yields the largest improvement in maximum
task cost compared to benchmarks. The plots above shows the improvement in
cost for random redundant assignment, repeated threshold assignment, and fair
redundant assignment. The data show the percent difference between the
respective assignment and the initial non-redundant assignment. Left. $M=10$
tasks, $N=40$ agents, and varying $N_{d}$ deployment sizes (x-axis). Right.
$M=10$ tasks with varying number of agents, where the deployment size equals
the number of agents, $N=N_{d}$.

###  V-B Comparing Algorithm 1 to Benchmarks

In the following, we show that Algorithm 1 with $\alpha=1$ outperforms three
benchmarks: (1) non-redundant assignment using the thresholding algorithm, (2)
random assignment of redundant agents, (3) repeated iterations of the
thresholding algorithm for redundant assignment. We use $\alpha=1$ since it is
shown above to be near optimal without the need for cardinality relaxations.
The results in Figure 3 show that redundant agents improve the performance of
non-redundant assignments and that Algorithm 1 outperforms all three
benchmarks.

We create 1000 random bipartite graphs with the cost random variable
parameters listed above. Because calculating the optimal is not needed in
these simulations, larger graphs are studied.777Graphs with tens of agents and
tasks are shown in this paper, but the algorithm has been run on examples with
hundreds of agents and tasks. We first consider 40 agents and 10 tasks, with
increasing deployment sizes. These trials restrict the deployment size such
that some agents are unused. Next, we consider 10 tasks with varying number of
agents where all available agents are deployed, i.e., $N=N_{d}$. These two
different problem setups are chosen to show that Algorithm 1 performs well in
scenarios when partial and full deployment is desired. In both cases,
Algorithm 1 outperforms the benchmarks. 888Not shown here is Algorithm 1 with
the $\alpha$ from equation (6), which is guaranteed perform at least as good
as $\alpha=1$, but comes at the cost of larger assignments. In the right of
Figure 3, both $\alpha$ values perform equally because there are no available
agents to be used by the cardinality relaxation.

###  V-C Random Transport Network Case Study

We instantiate 500 random transport networks with 32 agents and 16 tasks
randomly located at different nodes where the travel time along each edge is
represented by a Gaussian random variable truncated at zero with mean
uniformly sampled from the range $[10,~{}20]$ and standard deviation uniformly
sampled from the range $[5,~{}10]$. Assignments of size 20 are found using
Algorithm 1 and the utilitarian approach.999Both algorithms require an initial
non-redundant assignment. To compare the results on the same footing, both
algorithms are given the same initial assignment: Hungarian assignment on mean
travel times.

Figure 4 shows that the utilitarian approach nearly uniformly helps tasks,
while Algorithm 1 focuses the redundant agents on helping tasks most in need
(those with the highest task cost). Additionally, for more than half the
trials, the utilitarian approach does not help the worst-off task. All
redundant assignment is guaranteed to improve the average task cost because
the redundant agents improve the performance of their assigned tasks. While
utilitarian redundant assignment better improves the average task cost, it
does not necessarily improve the maximum cost. Fair redundant assignment is
guaranteed to improve both the maximum and the average task cost.

Improvements of Tasks Due to Redundancy

Figure 4: Left. The frequency at which different tasks are improved by
redundant assignment under the utilitarian and fair algorithms across 500
examples. The tasks are ordered by increasing expected cost after the initial
assignment, showing that the fair approach always helps the tasks that are
worse off while the greedy approach more uniformly helps tasks. Right. The
percent improvement in the average and maximum task cost compared to those of
the initial assignment shows that the fair assignment does not improve the
average as much as does the utilitarian assignment but strongly outperforms in
improvement of the maximum cost.

##  VI Discussion

This work is inspired by robotic applications such as rescue and medical or
emergency supplies delivery. The objectives of such applications focus on task
completion time and omit other costs (e.g., energy used). While previous work
focuses on average performance, we observe that the human-centric nature of
these applications requires considerations of fairness. While our work
contributes to fairness in redundant assignment by improving the objective
function, we acknowledge that fairness is more than a mathematical formulation
and we welcome discussions of the broader impact of these algorithms.

For practitioners, note the similarity of our problem formulation and approach
to works on providing robustness to a worst-case objective. This formulation
is flexible in that it has few assumptions, such as the supermodularity of the
cost functions. Thus far, work in redundant assignment has focused on the
first-come first-to-serve principle. However, Algorithm 1 can be applied to
many multi-agent problems where uncertainty impacts task performance,
requiring new collaboration functions, $J_{j}(\mathcal{A})$.

When studying other applications, scalability must be considered. Theorem 1
shows that the complexity of Algorithm 1 is dominated by the greedy term,
which scales linearly with the dominant term, $N$, because the number of
tasks, $M$, and degree of redundancy, $N_{d}$ are small. In instances where
both $N_{d}$ and $N$ are large, the scaling is approximately quadratic. In
such cases, our centralized approach is less tractable, and therefore could be
adapted via hierarchical approaches or by developing new decentralized
algorithms.

Last, we note that existing approaches in redundant assignment, including this
work, assume an initial non-redundant assignment. Therefore, no theoretical
guarantees have been proven for the full assignment of initial and redundant
agents thus far. Doing so will require new algorithms that do not rely on the
initial assignment to maintain supermodularity and that ensure that all tasks
are assigned at least one agent.

##  VII Conclusions

Redundant assignment provides robustness against uncertainty and improves task
performance. While redundancy comes at the cost of using more robots, it is
beneficial in time sensitive scenarios such as rescue or emergency delivery.

Inspired by the human-centric nature of these application spaces (e.g.,
rescue), we build on previous work in redundant assignment to consider
fairness; notably, we are first to formalize fairness in this space. Using a
Rawlsian approach to fairness, we formulate fair redundant task allocation as
the optimization of worst-case task cost with a cardinality constraint, a
problem that is NP-Hard. We exploit the natural supermodularity of the problem
to propose a tractable solution.

Algorithm 1 is a binary search where the target value is determined by
greedily solving the relaxed sub-problem shown in equation 5. This algorithm
converges to an approximate solution: an assignment that is $\alpha$ times
larger than the cardinality constraint. We prove performance guarantees of
this algorithm, showing that the returned approximate solution has a cost that
is less than that of the optimal solution but a solution size that is $\alpha$
times larger. Theorem 1 proves bounds on this $\alpha$ value.

Additionally, we show empirically that Algorithm 1 with $\alpha=1$ (meaning
the cardinality constraint remains satisfied) provides near optimal results,
despite having no theoretical guarantees. Simulated experiments show that this
approach outperforms benchmarks, scales to large problem instances, and
provides both increased fairness and increased utilitarian social welfare over
non-redundant assignments.

###  -A Supermodularity

Supermodularity implies that adding an element $x$ to a set $\mathcal{A}$
results in a larger or equal marginal decrease than when $x$ is added to a
superset of $\mathcal{A}$. This is known as the property of diminishing
returns; there are diminishing returns from an added element $x$ as the set it
is added to grows larger. Below are the formal definitions of supermodularity
[24].

######  Definition 2.

Marginal Decrease. For a finite set $\mathcal{F}$ and a given set function
$J:2^{\mathcal{F}}\mapsto\mathbb{R},$ the marginal decrease of $J$ at a subset
$\mathcal{A}\subseteq\mathcal{F}$ with respect to an element
$x\in\mathcal{F}\backslash\mathcal{A}$ is:

$\Delta_{J}(x|\mathcal{A})\triangleq J(\mathcal{A})-J(\mathcal{A}\cup\\{x\\})$
(7)

######  Definition 3.

Supermodularity. Let $J:2^{\mathcal{F}}\mapsto\mathbb{R}$ and
$\mathcal{A}\subseteq\mathcal{B}\subseteq$ $\mathcal{F}.$ The set function $J$
is supermodular101010Note, a supermodular function $J$ implies $-J$ is
submodular. if and only if for any $x\in\mathcal{F}\backslash\mathcal{B}$

$\Delta_{J}(x|\mathcal{A})\geq\Delta_{J}(x|\mathcal{B})$ (8)

######  Lemma 1.

The maximum of a set of supermodular functions is not supermodular.

###### Proof.

Consider an assignment set $\mathcal{A}$ and an element $x$ to be added. Let
$x$ decrease the value of $J_{1}(\mathcal{A})$. Here, $x$ is an assignment of
a new agent to task 1, thus decreasing the expected cost of task 1. If $J_{1}$
is not the maximum of the all $J_{j}$, the addition of $x$ to $\mathcal{A}$
has no effect on $\max_{j}(J_{j}(\mathcal{A}))$. In other words, its marginal
decrease of $\max_{j}(J_{j}(\mathcal{A}))$ with respect to $x$ is zero. By
Definition 3, $\max_{j}(J_{j})$ is only supermodular if the marginal decrease
of $\max_{j}(J_{j})$ with respect to $x$ is also zero for all supersets of
$\mathcal{A}$.

Let $\mathcal{B}$ be a superset of $\mathcal{A}$ that improves upon all task
costs except task 1, such that the maximum cost of $\mathcal{B}$ is $J_{1}$.
Here $\mathcal{B}\supseteq\mathcal{A}$ such that
$\max_{j}(J_{j}(\mathcal{B}))=J_{1}(\mathcal{B})=J_{1}(\mathcal{A})$.111111This
is feasible because the cost distributions are unconstrained. Since the
assignment $x$ decreases the value of $J_{1}(\mathcal{A})$, it decreases the
value of $\max_{j}(J_{j}(\mathcal{B}))$. Therefore, the marginal decrease of
adding $x$ to $\mathcal{B}$ is nonzero, meaning $\max_{j}(J_{j})$ is not
supermodular. ∎

## References

  * [1] E. Ackerman and E. Strickland “Medical delivery drones take flight in east africa” In _IEEE Spectrum_ 55.1, 2018, pp. 34–35
  * [2] C. Arnsperger “Envy-freeness and distributive justice” In _Journal of Economic Surveys_ 8.2, 1994, pp. 155–186
  * [3] S. Barocas, M. Hardt and A. Narayanan “Fairness in machine learning” In _NIPS Tutorial_ 1, 2017
  * [4] R.. Bellamy et al. “AI Fairness 360: An extensible toolkit for detecting and mitigating algorithmic bias” Publisher: IBM In _IBM Journal of Research and Development_ 63.4, 2019, pp. 4–1
  * [5] V. Borkar and R. Jain “Risk-constrained Markov decision processes” In _IEEE Transactions on Automatic Control_ 59.9, 2014, pp. 2574–2579
  * [6] S.. Brams and A.D. Taylor “Fair Division: From cake-cutting to dispute resolution” Cambridge University Press, 1996
  * [7] S.. Chaves, J.. Walls, E. Galceran and R.. Eustice “Risk aversion in belief-space planning under measurement acquisition uncertainty” In _2015 IEEE/RSJ Intl. Conference on Intelligent Robots and Systems (IROS)_ IEEE, 2015, pp. 2079–2086
  * [8] M.. Cummings and S. Li “Subjectivity in the Creation of Machine Learning Models” In _Journal of Data and Information Quality, in press._ , 2020
  * [9] L. Edwards and M. Veale “Slave to the algorithm: Why a right to an explanation is probably not the remedy you are looking for” In _Duke L. & Tech. Rev._ 16, 2017, pp. 18
  * [10] D. Gale “The theory of linear economic models” University of Chicago press, 1989
  * [11] M.. Garey and D.. Johnson “"Strong" NP-Completeness Results: Motivation, Examples, and Implications” In _Journal of the ACM (JACM)_ 25.3, 1978, pp. 499–508
  * [12] B.. Gerkey and M.. Matarić “A formal analysis and taxonomy of task allocation in multi-robot systems” In _The International journal of robotics research_ 23.9, 2004, pp. 939–954
  * [13] J.. Harsanyi “Bayesian decision theory and utilitarian ethics” In _The American Economic Review_ 68.2, 1978, pp. 223–228
  * [14] D.. Herreiner and C.. Puppe “Envy freeness in experimental fair division problems” In _Theory and decision_ 67.1, 2009, pp. 65–100
  * [15] A. Krause, H.. McMahan, C. Guestrin and A. Gupta “Robust submodular observation selection” In _Journal of Machine Learning Research_ 9, 2008, pp. 2761–2801
  * [16] A. Majumdar and M. Pavone “How should a robot assess risk? Towards an axiomatic theory of risk in robotics” In _Robotics Research_ Springer, 2020, pp. 75–84
  * [17] N. Mehrabi et al. “A survey on bias and fairness in machine learning” In _arXiv preprint arXiv:1908.09635_ , 2019
  * [18] B.. Mittelstadt et al. “The ethics of algorithms: Mapping the debate” In _Big Data & Society_ 3.2, 2016, pp. 2053951716679679
  * [19] H. Moulin “Fair division and collective welfare” MIT press, 2004
  * [20] C. Nam and D.. Shell “Analyzing the Sensitivity of the Optimal Assignment in Probabilistic Multi-Robot Task Allocation” In _IEEE Robotics and Automation Letters_ 2.1, 2017, pp. 193–200
  * [21] G.. Nemhauser, L.. Wolsey and M.. Fisher “An analysis of approximations for maximizing submodular set functions—I” In _Mathematical programming_ 14.1, 1978, pp. 265–294
  * [22] A.. Pigou “The laws of diminishing and increasing cost” In _The Economic Journal_ 37.146, 1927, pp. 188–197
  * [23] T. Powers et al. “Constrained robust submodular optimization” In _NIPS OPT2016 workshop_ , 2016
  * [24] A. Prorok “Robust Assignment Using Redundant Robots on Transport Networks With Uncertain Travel Time” In _IEEE Transactions on Automation Science and Engineering_ 17.4, 2020, pp. 2025–2037
  * [25] A. Prorok and V. Kumar “Privacy-preserving vehicle assignment for mobility-on-demand systems” In _IEEE/RSJ Intl. Conference on Intelligent Robots and Systems (IROS)_ , 2017, pp. 1869–1876
  * [26] J. Rawls “A theory of justice” Harvard university press, 2009
  * [27] K. Shahriari and M. Shahriari “IEEE standard review — Ethically aligned design: A vision for prioritizing human wellbeing with artificial intelligence and autonomous systems” In _IEEE Canada Intl. Humanitarian Technology Conference (IHTC)_ , 2017, pp. 197–201
  * [28] N. Srinivas, A. Krause, S.. Kakade and M.. Seeger “Information-theoretic regret bounds for gaussian process optimization in the bandit setting” In _IEEE Transactions on Information Theory_ 58.5, 2012, pp. 3250–3265
  * [29] W. Suksompong “Asymptotic existence of proportionally fair allocations” In _Mathematical Social Sciences_ 81, 2016, pp. 62–65
  * [30] W. Szpankowski “On The Bottleneck and Capacity Assignment Problems”, 1988
  * [31] S. Verma and J. Rubin “Fairness Definitions Explained” In _IEEE/ACM Intl. Workshop on Software Fairness (FairWare)_ , 2018, pp. 1–7
  * [32] S. Wachter, B. Mittelstadt and L. Floridi “Why a right to explanation of automated decision-making does not exist in the general data protection regulation” In _Intl. Data Privacy Law_ 7.2, 2017, pp. 76–99
  * [33] B. Wilder “Risk-Sensitive Submodular Optimization.” In _AAAI_ , 2018, pp. 6451–6458
  * [34] L.. Wolsey “An analysis of the greedy algorithm for the submodular set covering problem” In _Combinatorica_ 2.4, 1982, pp. 385–393
  * [35] F. Yang and N. Chakraborty “Algorithm for optimal chance constrained linear assignment” In _2017 IEEE International Conference on Robotics and Automation (ICRA)_ IEEE, 2017, pp. 801–808
  * [36] C. Zhang and J.. Shah “On fairness in decision-making under uncertainty: Definitions, computation, and comparison”, 2015
  * [37] L. Zhou and P. Tokekar “An approximation algorithm for risk-averse submodular optimization” In _Intl. Workshop on the Algorithmic Foundations of Robotics_ Springer, 2018, pp. 144–159
  * [38] L. Zhou and P. Tokekar “Sensor assignment algorithms to improve observability while tracking targets” In _IEEE Transactions on Robotics_ 35.5, 2019, pp. 1206–1219


# A Construction for Variable Dimension
Strong Non-Overlapping Matrices

Elena Barcucci University of Florence
Italy<EMAIL_ADDRESS>University of Florence
ItalyUniversity of Florence
ItalyUniversity of Florence
Italy Antonio Bernini University of Florence
Italy<EMAIL_ADDRESS>University of Florence
ItalyUniversity of Florence
Italy Stefano Bilotta University of Florence
Italy<EMAIL_ADDRESS>University of Florence
Italy Renzo Pinzani University of Florence
Italy<EMAIL_ADDRESS>
###### Abstract

We propose a method for the construction of sets of variable dimension strong
non-overlapping matrices basing on any strong non-overlapping set of strings.

##  1 Introduction

Intuitively, two matrices do not overlap if it is not possible to move one
over the other in a way such that the corresponding entries match. In some
recent works ([3],[4],[5]) the matrices are constructed by imposing some
constraints on their rows which must avoid some particular consecutive
patterns or must have some fixed entries in particular positions. The matrices
of the sets there defined have the same fixed dimension.

In the present paper, we deal with matrices having different dimensions and we
construct them by means a different approach: we move from any strong non-
overlapping set $W$ of strings, defined over a finite alphabet, and, in a very
few words, the strings of $W$ becomes the rows of our matrices. The method is
general and once the cardinality of the strings of $W$ with a same length is
known, the cardinality of the set of matrices is straightforward.

This work could fit in the theory of bidimensional codes, as well as non
overlapping sets of strings do in the theory of codes. Moreover, if the latter
have been used in telecommunication systems both theory and engineering [2,
14], the matrices of our sets could be useful in the field of digital image
processing, and a possible (future) application of this kind of sets is in the
template matching which is a technique to discover if small parts of an image
match a template image.

##  2 Preliminaries

Let $\mathcal{M}_{m\times n}$ be the set of all the matrices with $m$ rows and
$n$ columns. Given a matrix $A\in\mathcal{M}_{m\times n}$, we consider a block
partition

$A=(A_{i,j})=\begin{bmatrix}A_{11}&\ldots&A_{1k}\\\ \vdots&\ldots&\vdots\\\
A_{h1}&\ldots&A_{hk}\end{bmatrix}\ .$ (1)

Let us define $fr(A_{ij})$ the _frame_ of a block $A_{ij}$ of $A$.
Intuitively, it is a set tracking the borders of the block which lie on the
top ($t$), left ($l$), right ($r$) and bottom ($b$) border of the matrix $A$.
More precisely, the set $fr(A_{i,j})$ is a subset of $\\{t,b,l,r\\}$ defined
as follows:

######  Definition 1.

$fr(A_{i,j})\supseteq\begin{cases}t,&\text{if }i=1\\\ b,&\text{if }i=h\\\
l,&\text{if }j=1\\\ r,&\text{if }j=k\\\ \end{cases}\ \ \ \ \ .$

For example, if $A=\begin{bmatrix}A_{11}&A_{12}&A_{13}\end{bmatrix}$ ($h=1$
and $k=3$) then $fr(A_{11})=\\{t,b,l\\}$, $fr(A_{12})=\\{t,b\\}$, and
$fr(A_{13})=\\{t,b,r\\}$ since $i=h=1$. But if

$A=\begin{bmatrix}A_{11}&A_{12}&A_{13}\\\ A_{21}&A_{22}&A_{23}\\\
A_{31}&A_{32}&A_{33}\end{bmatrix}$

then $fr(A_{11})=\\{t,l\\}$, $fr(A_{12})=\\{t\\}$, $fr(A_{13})=\\{t,r\\}$ and
similarly for the other blocks. Note that in this case $fr(A_{22})=\emptyset$.

######  Definition 2.

Given two matrices $A\in\mathcal{M}_{m\times n}$ and
$B\in\mathcal{M}_{m^{\prime}\times n^{\prime}}$, they are said _overlapping_
if there exist two suitable block partitions $A=(A_{ij})$ ,
$B=(B_{i^{\prime}j^{\prime}})$, and some $i,j,i^{\prime},j^{\prime}$ such that

  * •

$A_{i,j}=B_{i^{\prime}j^{\prime}}$, and

  * •

$fr(A_{ij})\cup fr(B_{i^{\prime}j^{\prime}})=\\{t,l,r,b\\}$.

In the case $A=B$, the matrix is said _self-overlapping_.

To illustrate the definition, the following examples are given:

  * •

Given the two matrices

$A=\left[\begin{array}[]{cc|cc|c}1&2&1&1&2\\\ 0&1&0&3&0\\\ \hline\cr
3&2&1&0&2\\\ 0&1&3&1&3\\\ \end{array}\right]\quad\mbox{and}\quad
B=\left[\begin{array}[]{cc}2&1\\\ \hline\cr 1&1\\\ 0&3\\\ \end{array}\right]\
,$

they overlap since the entries of the blocks $A_{12}$ and $B_{21}$ coincide.
Moreover, we have $fr(A_{12})=\\{t\\}$, $fr(B_{21})=\\{l,b,r\\}$ so that
$fr(A_{12})\cup fr(B_{21})=\\{l,t,b,r\\}$.

  * •

If $B=\left[\begin{array}[]{c|cc}3&1&2\\\ 2&0&1\\\ \end{array}\right]$ the
matrix $A$ (as before) and the matrix $B$ again overlap since $A_{11}=B_{12}$
and $fr(A_{11})\cup fr(B_{12})=\\{l,r,b,t\\}$ being $fr(A_{11})=\\{l,t\\}$ and
$fr(B_{12})=\\{t,r,b\\}$.

  * •

Note that if $B=\left[\begin{array}[]{cc|c}1&2&3\\\ 0&1&2\\\
\end{array}\right]$, even if $A_{11}=B_{11}$, we have $fr(A_{11})=\\{l,t\\}$
and $fr(B_{11})=\\{l,t,b\\}$ so that $fr(A_{11})\cup
fr(B_{11})=\\{l,b,t\\}\neq\\{l,t,b,r\\}$. Nevertheless, the two matrices are
overlapping since, considering the block partitions
$B=\left[\begin{array}[]{cc}B_{11}&B_{12}\\\ B_{21}&B_{22}\\\
\end{array}\right]=\left[\begin{array}[]{c|cc}1&2&3\\\ \hline\cr 0&1&2\\\
\end{array}\right]$ and

$A=\begin{bmatrix}A_{11}&A_{12}\\\ A_{21}&A_{22}\\\
\end{bmatrix}=\left[\begin{array}[]{cc|ccc}1&2&1&1&2\\\ \hline\cr 0&1&0&3&0\\\
3&2&1&0&2\\\ 0&1&3&1&3\\\ \end{array}\right]\ ,$

we have $A_{11}=B_{22}$ and $fr(A_{11})\cup fr(B_{22})=\\{l,t,b,r\\}$.

  * •

As a further example we consider the particular case where $A=[A_{11}]$ and
$B=\begin{bmatrix}B_{11}&B_{12}&B_{13}\\\ B_{21}&B_{22}&B_{23}\\\
B_{31}&B_{32}&B_{33}\end{bmatrix}$ with $B_{22}=A_{11}$. Here, we have
$fr({A_{11}})\cup fr(B_{22})=\\{t,b,l,r\\}\cup\\{\emptyset\\}=\\{t,b,l,r\\}$
and the two matrices are overlapping.

  * •

We conclude this list of examples showing two matrices $A$ and $B$ such that,
even if they have two equal blocks ($A_{11}=B_{11}$), they are not overlapping
since the second condition on the frames of the blocks of Definition 2 is not
fulfilled $(\mbox{since}\ fr({A_{11}})\cup
fr(B_{11})=\\{t,l\\}\neq\\{t,b,l,r\\})$:

$A=\left[\begin{array}[]{cc|cc|c}1&2&1&1&2\\\ 0&1&0&3&0\\\ \hline\cr
3&2&1&0&2\\\ 0&1&3&1&3\\\ \end{array}\right]\quad\mbox{,}\quad
B=\left[\begin{array}[]{cc|c}1&2&3\\\ 0&1&1\\\ \hline\cr 1&0&3\\\
\end{array}\right]\ .$

From these examples, it should be clear that if two matrices are overlapping,
then the common block naturally induces a block partition $(A_{i,j})$ for $A$
(and a block partition $(B_{i,j})$) such that the number of blocks in each its
row and column can be not larger than $3$. Figure 1 shows two examples of the
least fine block partitions for two overlapping matrices $A$ and $B$ induced
by the (gray) common block. Therefore, the block partitions 1 involved in
Definition 2 are such that $h,k\in\\{1,2,3\\}$.

Figure 1: The least fine block partition in two examples of two overlapping
matrices

We note that if a matrix is completely contained in the other, then the two
matrices are overlapping according to Definition 2, as in the second to last
example of the above list. In the context of strings, the scenario is
different, as illustrated in the following. Two strings are said _overlapping_
if there is a proper prefix of one that is equal to a proper suffix of the
other. Consequently, they are said to be _non-overlapping_ if there is no a
proper prefix of one that is equal to a proper prefix of the other (these
definitions are more formally recalled, later in this section). It can happen
that, given two non-overlapping strings, one of them is an inner factor of the
other, as in the case of the two binary strings $1111000$ and $10$. If this is
not allowed, then the strings are said _strong non-overlapping_ (i.e. two
strings are strong non-overlapping if they are non-overlapping and if one of
them is not an inner factor of the other), as in the case of the two binary
strings $1111000$ and $10100$. In short, being non-overlapping strings or
strong non-overlapping strings are different concepts.

In our framework, if two matrices $A$ and $B$ are not overlapping then it can
not happen that one of them (say $B$) is completely contained in the other.
Indeed, if this were the case, then the smaller matrix $B$ could be trivially
partitioned in one block $B=B_{11}$ so that $fr(B_{11})=\\{t,b,l,r\\})$.
Moreover, it would be $B_{11}=A_{ij}$ for some block $A_{ij}$ of the matrix
$A$, and the matrices $A$ and $B$ would be overlapping, whatever the block
$A_{i,j}$.

Therefore, when two matrices are not overlapping, we prefer to call them
strong non-overlapping matrices (instead of simply non-overlapping matrices),
in order to emphasize that certainly neither is contained in the other. Then,
we give the following formal definitions characterizing two such matrices and
a set of strong non-overlapping matrices:

######  Definition 3.

The matrices $A$ and $B$ are said _strong non-overlapping_ if there does not
exist any block partition for $A$ and $B$, and any $i,j,i^{\prime},j^{\prime}$
such that $A_{i,j}=B_{i^{\prime},j^{\prime}}$ or, if such block partitions
exist, then $fr(A_{ij})\cup fr(B_{i^{\prime}j^{\prime}})\neq\\{t,l,r,b\\}$.

######  Definition 4.

A set $\mathcal{P}$ of matrices is said to be _strong non-overlapping_ if each
matrix is self non-overlapping and if for any two matrices in $\mathcal{P}$
they are strong non-overlapping.

For completeness, let us recall some notions about non-overlapping and strong
non-overlapping sets of strings.

Given a finite alphabet $\Sigma$, a string $v\in\Sigma^{*}$ is said to be
_self non-overlapping_ (often said _unbordered_ or equivalently _bifix-free_)
if any proper prefix of $v$ is different from any proper suffix of $v$ (for
more details see [12]).

Two self non-overlapping strings $v$, $v^{\prime}\in\Sigma^{*}$ are said to be
_non-overlapping_ (or equivalently _cross bifix-free_) if any proper prefix of
$v$ is different from any proper suffix of $v^{\prime}$, and vice versa. A set
of strings is said to be a _non-overlapping set_ (or _cross bifix-free set_)
of strings if each element of the set is slef non-overlapping and if any two
strings are non-overlapping.

######  Definition 5.

Two non-overlapping strings $v$ and $v^{\prime}$ are said to be _strong non-
overlapping_ if there do not exist $\alpha,\beta\in\Sigma^{*}$, with $\alpha$
and $\beta$ not both empty, such that $v^{\prime}=\alpha v\beta$ (or $v=\alpha
v^{\prime}\beta$).

In other words, the strong non-overlapping property requires that the shortest
string between $v$ and $v^{\prime}$ (if any) does not occur as an inner factor
in the other one ([7, 13]). For example, if $v=1100$ and
$v^{\prime}=1\mathbf{1100}100$, then $v$ and $v^{\prime}$ are non-overlapping
but they are not strong non-overlapping since $v^{\prime}$ contains an
occurrence of $v$ (in bold).

######  Definition 6.

A set of strings is said to be a _strong non-overlapping set_ if any two
strings of the set are strong non-overlapping.

##  3 Construction of the set of matrices

Let $\mathcal{V}_{n}=\displaystyle\bigcup_{s\leq n}V^{s}$ be a variable
dimension strong non-overlapping set of strings where each $V^{s}$ is a non-
overlapping set of strings of length $s$, for $s_{0}\leq s\leq n$, where
$s_{0}\geq 2$ is the minimum string length. We now define a set of variable
dimension matrices, using strings of a same length $s$ of $V^{s}$ as rows of a
matrix. In the following, the two matrices $C$ and $D$ of dimension
$m_{1}\times s$ and $m_{2}\times t$, respectively, are constructed with the
rows $C_{i}^{s}\in V^{s}$ and $D_{j}^{t}\in V^{t}$, with $i=1,2,\ldots,m_{1}$
and $j=1,2,\ldots,m_{2}$.

$C=\left(\begin{matrix}C_{1}^{s}\\\ C_{2}^{s}\\\ \vdots\\\ \vdots\\\
C_{m_{1}}^{s}\end{matrix}\right)\hskip
28.45274ptD=\left(\begin{matrix}D_{1}^{t}\\\ D_{2}^{t}\\\ \vdots\\\
D_{m_{2}}^{t}\end{matrix}\right)$

It is not difficult to show that if $C$ and $D$ have a different number of
columns (then $s\neq t$) they can not be overlapping (see next proposition).

Unfortunately, in the case $C$ and $D$ have the same number of columns
($s=t$), then the two matrices can present a “vertical” overlap. More
precisely:

  * •

the matrix $D$ could be equal to a sub-matrix of $C$ constituted by $m_{2}$
consecutive rows of $C$ (or vice versa):

$C=\begin{bmatrix}C_{11}\\\ C_{12}\\\
C_{13}\end{bmatrix}=\begin{bmatrix}C_{11}\\\ D\\\ C_{13}\end{bmatrix}$

(with either blocks $C_{11}$ or $C_{13}$ possibly empty).

  * •

the first (last) $\ell$ rows of $D$ could be equal to the last (first) $\ell$
rows of $C$ (or vice versa):

$C=\begin{bmatrix}C_{11}\\\
C_{12}\end{bmatrix}=\left[\begin{array}[]{c}C_{11}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ D_{1}^{t}\vspace{.07cm}\\\
D_{2}^{t}\vspace{.07cm}\\\ \vdots\\\ D_{\ell}^{t}\end{array}\right]\hskip
28.45274ptD=\begin{bmatrix}D_{11}\\\ D_{12}\\\
\end{bmatrix}=\left[\begin{array}[]{c}D_{1}^{t}\\\ D_{2}^{t}\\\ \vdots\\\
D_{\ell}^{t}\vspace{.1cm}\\\ \hline\cr\vspace{-.3cm}\hfil\\\
D_{12}\end{array}\right]\ .$

In order to avoid the situations described above, we introduce a constraint
for the first and the last row of each matrix: all the matrices with the same
number $s$ of columns must have the same first row $T^{s}\in V^{s}$ and the
same last row $B^{s}\in V^{s}$, with $T^{s}\neq B^{s}$. Also, these two
selected rows cannot appear as inner rows of any other matrix with that number
$s$ of columns. In other words, we force:

  * •

the top row $T^{s}$ of all the matrices with the same number $s$ of columns to
be the same;

  * •

the bottom row $B^{s}$ of all the matrices with the same number $s$ of columns
to be the same;

  * •

$T^{s}\neq B^{s}$;

  * •

the rows $T^{s}$ and $B^{s}$ not to occur in any other line of the matrix.

Formally, the matrices $C$ with the same number $s$ of columns must have the
following structures:

$C=\left(\begin{matrix}T^{s}\\\ \\\ C_{2}^{s}\\\ \vdots\\\ \vdots\\\
C_{m_{1}-1}^{s}\\\ \\\ B^{s}\end{matrix}\right)$

with $C_{j}^{s}\neq T^{s},B^{s}$, for $j=2,3,\ldots,m_{1}-1$, and
$C_{j}^{s},T^{s},B^{s}\in V^{s}$.

We can now define the set $\mathcal{V}_{m\times n}^{(\leq)}$ of variable-
dimension matrices as follows:

######  Definition 7.

Let $\mathcal{V}_{n}=\displaystyle\bigcup_{s\leq n}V^{s}$ be a variable
dimension strong non-overlapping set of strings where each $V^{s}$ is a non-
overlapping set of strings of length $s$, for $s_{0}\leq s\leq n$, where
$s_{0}\geq 2$ is the minimum string length. Moreover, let

$\mathcal{V}_{m\times n}^{(\leq)}=\bigcup M$

be the union of the matrices $M$ where $M\in\mathcal{M}_{h\times s}$, with
$2\leq h\leq m$ and $s_{0}\leq s\leq n$, such that

$M=\left\\{\begin{pmatrix}T^{s}\\\ A_{2}^{s}\\\ \vdots\\\ A_{h-1}^{s}\\\
B^{s}\end{pmatrix}\right\\}$

with $A_{j}^{s},T^{s},B^{s}\in V^{s}\ \mbox{and}\ A_{j}^{s}\neq T^{s},B^{s}\
\mbox{for}\ j=2,3,\ldots,h-1\ .$

The matrices $M\in\mathcal{V}_{m\times n}^{(\leq)}$ have at most $m$ rows and
$n$ columns. They are constructed by means of $h\leq m$ strings of length
$s\leq n$ belonging to $\mathcal{V}_{n}$. All the matrices $M$ with the same
number $s$ of columns have the same bottom row $B_{s}$ and the same top row
$T_{s}$, which are not the same. Moreover, each inner row is different from
$T_{s}$ and $B_{s}$.

We have the following proposition:

######  Proposition 1.

The set $\mathcal{V}_{m\times n}^{(\leq)}$ is a strong non-overlapping set of
variable-dimension matrices.

###### Proof.

Let $C,D\in\mathcal{V}_{m\times n}^{(\leq)}$ and suppose that $C$ and $D$ are
two overlapping matrices: then there exists a block matrix
$E\in\mathcal{M}_{r\times c}$ such that $E=C_{i,j}=D_{i^{\prime},j^{\prime}}$
fore some two blocks $C_{i,j}$ and $D_{i^{\prime}j^{\prime}}$ in two suitable
block partitions of $C$ and $D$, and with $fr(C_{i,j})\cup
fr(D_{i^{\prime}j^{\prime}})=\\{l,t,r,b\\}$. We have

$E=\left(\begin{matrix}e_{11}&\ldots&e_{1c}\\\ \vdots&\ldots&\vdots\\\
e_{r1}&\ldots&e_{rc}\end{matrix}\right)\ \ .$

For each row $e_{\ell}$, with $\ell=1,2,\ldots,r$, there exist two rows
$C_{i},D_{j}\in\mathcal{V}_{n}$ such that one of the following cases occurs:

  * •

$C_{i}=ue_{\ell}v$ and $D_{j}=e_{\ell}$, with either $u$ or $v$ possibly
empty, where $u,v\in\Sigma^{*}$;

  * •

$C_{i}=ue_{\ell}$ and $D_{j}=e_{\ell}v$;

  * •

$C_{i}=e_{\ell}v$ and $D_{j}=ue_{\ell}$.

In any case, the strings $C_{i}$ and $D_{j}$ are not strong non-overlapping
strings (since they overlap over $e_{\ell}$) against the hypothesis
$C_{i},D_{j}\in\mathcal{V}_{n}$ . ∎

We note that in the case $\mathcal{V}_{n}$ is a variable dimension non-
overlapping set of strings (i.e. the non-overlapping property is not required
to be strong), the resulting matrices are not strong non-overlapping according
to Definition 2, since it is possible that one of the two matrices is
completely contained in the other one as a suitable block. If we did not
contemplate this possibility in Definition 2, then two matrices constructed
with such a $\mathcal{V}_{n}$ could be considered still non-overlapping
(according to a different definition of non-overlapping matrices).

Moreover, if $\mathcal{V}_{n}$ contains strings all of the same lengths, then
Proposition 1 still holds: the matrices will have all the same number of
columns.

Finally, if $|V^{s}|$ denotes the cardinality of the non-overlapping set
$V^{s}$, it is straightforward to deduce the following formula for the
cardinality of $\mathcal{V}_{m\times n}^{(\leq)}$:

$|\mathcal{V}_{m\times n}^{(\leq)}|=\sum_{h\leq m}\ \sum_{s\leq
n}(|V^{s}|-2)^{h-2}\ .$ (2)

The two terms $-2$ in the above formula take into account that the first and
the last row in the matrices with $s$ columns are fixed and can not occur as
inner rows.

For the sake of clearness, we propose an example for the construction of a set
of variable dimension strong non-overlapping matrices. Let
$V^{3}=\\{110,210,310,320\\}$ and $V^{5}=\\{22000,23000,33000\\}$ be two sets
of non-overlapping strings over the alphabet $\Sigma=\\{0,1,2,3\\}$. It is
easily seen that $V^{3}\cup V^{5}$ is a strong non-overlapping code. Then, we
construct

$\mathcal{V}_{4\times 5}^{(\leq)}=\mathcal{M}_{2\times
3}^{(\leq)}\cup\mathcal{M}_{3\times 3}^{(\leq)}\cup\mathcal{M}_{4\times
3}^{(\leq)}\cup\mathcal{M}_{2\times 5}^{(\leq)}\cup\mathcal{M}_{3\times
5}^{(\leq)}\cup\mathcal{M}_{4\times 5}^{(\leq)}$

where:

$\mathcal{M}_{2\times 3}=\left\\{\left(\begin{matrix}1&1&0\\\
3&2&0\end{matrix}\right)\right\\}$

$\mathcal{M}_{3\times 3}=\left\\{\left(\begin{matrix}1&1&0\\\ 2&1&0\\\
3&2&0\end{matrix}\right),\left(\begin{matrix}1&1&0\\\ 3&1&0\\\
3&2&0\end{matrix}\right)\right\\}$

$\mathcal{M}_{4\times 3}=\left\\{\left(\begin{matrix}1&1&0\\\ 2&1&0\\\
2&1&0\\\ 3&2&0\end{matrix}\right),\left(\begin{matrix}1&1&0\\\ 2&1&0\\\
3&1&0\\\ 3&2&0\end{matrix}\right),\left(\begin{matrix}1&1&0\\\ 3&1&0\\\
2&1&0\\\ 3&2&0\end{matrix}\right),\left(\begin{matrix}1&1&0\\\ 3&1&0\\\
3&1&0\\\ 3&2&0\end{matrix}\right)\right\\}$

$\mathcal{M}_{2\times 5}=\left\\{\left(\begin{matrix}2&2&0&0&0\\\
3&3&0&0&0\end{matrix}\right)\right\\}$

$\mathcal{M}_{3\times 5}=\left\\{\left(\begin{matrix}2&2&0&0&0\\\ 2&3&0&0&0\\\
3&3&0&0&0\end{matrix}\right)\right\\}$

$\mathcal{M}_{4\times 5}=\left\\{\left(\begin{matrix}2&2&0&0&0\\\ 2&3&0&0&0\\\
2&3&0&0&0\\\ 3&3&0&0&0\end{matrix}\right)\right\\}$

The reader can easily check that $\mathcal{V}_{4\times 5}^{(\leq)}$ is a set
of variable dimension strong non-overlapping matrices having cardinality 10
according to (2).

##  4 Conclusions

The paper provides a simple and general method to generate a set of strong
non-overlapping matrices over a finite alphabet, once a strong non-overlapping
set of strings (over the same alphabet) is at our disposal. The crucial point
is the constraint on the first and last rows which must be the same for all
the matrices with the same number of columns.

Using the variable length strong non-overlapping sets of strings defined in
[13] and [7], two different set of strong non-overlapping matrices arise which
could be compared in terms of cardinality or its asymptotic behaviour.

Moreover, the construction we proposed, in the case of fixed dimension
matrices, gives the possibility to list them in a Gray code sense, following
the studies started in [3, 6, 8, 9, 10, 11] where different Gray codes are
defined for several set of strings and matrices.

In this case, we generate the matrices moving from a set of non-overlapping
strings $V^{s}$ of length $s$ and we suppose that there exists a Gray code
$GV^{s}$ for $V^{s}$:

$GV^{s}=\\{w_{1},w_{2}.\ldots,w_{t},w_{t+1},w_{t+2}\\}\text{ with }t>0\ .$

Note that we require $|V^{s}|\geq 3$. We choose two strings from $GV^{s}$.
Without loss of generality, we choose $w_{t+1}$ and $w_{t+2}$ and we define
the set of matrices $M_{h+2,s}$ with $h+2$ rows and $s$ columns where the
first and last rows are, respectively, the strings $w_{t+1}$ and $w_{t+2}$:

$M_{h+2,s}=\left\\{\begin{pmatrix}w_{t+1}\\\ C_{1}^{s}\\\ \vdots\\\
C_{h}^{s}\\\ w_{t+2}\end{pmatrix}\Bigg{|}\ C_{i}^{s}\in
V^{s}\setminus\\{w_{t+1},w_{t+2}\\}\right\\}\ .$

Let $N_{h,s}$ be the set of matrices obtained by $M_{h+2,s}$ removing the
first and last rows:

$N_{h,s}=\left\\{\begin{pmatrix}C_{1}^{s}\\\ \vdots\\\ C_{h}^{s}\\\
\end{pmatrix}\Bigg{|}\ C_{i}^{s}\in
V^{s}\setminus\\{w_{t+1},w_{t+2}\\}\right\\}\ .$

Clearly, the cardinality of $N_{h,s}$ and $M_{h+2,s}$ is the same and denoting
it by $q$ it is $q=t^{h}$.

We now recursively define a Gray code $GN_{h,s}$ for the set $N_{h,s}$. If
$h=1$, then the list $GN_{1,s}=(w_{1}),(w_{2}),\ldots,(w_{t})$ is a Gray code
(since it is obtained by $GV^{s}$ where the strings are read as matrices of
dimension $1\times s$). Suppose now that $GN_{h,s}=A_{1},A_{2},\ldots,A_{q}$
is a Gray code where $h\geq 1$ and $A_{i}\in N_{h,s}$, for $i=1,2,\ldots,q$.
The following list $GN_{h+1,s}$of matrices, defined as block matrices,

$GN_{h+1,s}=\left[\begin{array}[]{c}w_{1}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ A_{1}\\\
\end{array}\right]\cdots\left[\begin{array}[]{c}w_{1}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ A_{q}\\\
\end{array}\right]\left[\begin{array}[]{c}w_{2}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ A_{q}\\\
\end{array}\right]\cdots\left[\begin{array}[]{c}w_{2}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ A_{1}\\\
\end{array}\right]\cdots\cdots\left[\begin{array}[]{c}w_{t}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ A_{\ell}\\\
\end{array}\right]\cdots\left[\begin{array}[]{c}w_{t}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ A_{q+1-\ell}\\\ \end{array}\right]\ \ ,$

where

$\ell=\begin{cases}q,&\text{if }t\text{ is even}\\\ 1,&\text{if }t\text{ is
odd}\end{cases}\ \ ,$

is easily seen to be a Gray code since the lists $A_{1},A_{2},\ldots,A_{q}$
and $w_{1},w_{2},\ldots,w_{t}$ are Gray codes for hypothesis.

Finally, adding the strings $w_{t+1}$ and $w_{t+2}$, respectively, as first
and last rows to all the $q$ matrices $A_{1},A_{2},\ldots,A_{q}$ of $GN_{h,s}$
we obtain a Gray code $GM_{h+2,s}$ for the set $M_{h+2,s}$:

$GM_{h+2,s}=\left[\begin{array}[]{c}w_{t+1}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ A_{1}\\\ \hline\cr\vspace{-.3cm}\hfil\\\
w_{t+2}\end{array}\right]\cdots\cdots\cdots\left[\begin{array}[]{c}w_{t+1}\vspace{.1cm}\\\
\hline\cr\vspace{-.3cm}\hfil\\\ A_{q}\\\ \hline\cr\vspace{-.3cm}\hfil\\\
w_{t+2}\end{array}\right]\ \ .$

## References

  * [1]
  * [2] D. Bajic & J. Stojanovic (2004): _Distributed sequences and search process_.  In: 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577), 1, pp. 514–518, 10.1109/ICC.2004.1312542.
  * [3] E. Barcucci, A. Bernini, S. Bilotta & R. Pinzani (2015): _Cross-bifix-free sets in two dimensions_.  Theoret. Comput. Sci. 664, pp. 29–38, 10.1016/j.tcs.2015.08.032.
  * [4] E. Barcucci, A. Bernini, S. Bilotta & R. Pinzani (2017): _Non-overlapping matrices_.  Theoret. Comput. Sci. 658, pp. 36–45, 10.1016/j.tcs.2016.05.009.
  * [5] E. Barcucci, A. Bernini, S. Bilotta & R. Pinzani (2018): _A 2D non-overlapping code over a q-ary alphabet_.  Cryptogr. Commun. 10, pp. 667–683, 10.1007/s12095-017-0251-8.
  * [6] E. Barcucci, A. Bernini & R. Pinzani (2018): _A Gray code for a regular language_.  In: GASCom 2018, CEUR Workshop Proceedings, 2113, pp. 87–93.  Available at https://ceur-ws.org/Vol-2113/paper8.pdf.
  * [7] E. Barcucci, A. Bernini & R. Pinzani (2021): _A Strong non-overlapping Dyck Code_.  In: DLT 2021, Lecture Notes in Comput. Sci., 12811, pp. 43–53, 10.1007/978-3-030-81508-0_4.
  * [8] A. Bernini, S. Bilotta, R. Pinzani, A. Sabri & V. V. Vajnovszki (2014): _Prefix partitioned Gray codes for particular cross-bifix-free sets_.  Cryptogr. Commun. 6, pp. 359–369, 10.1007/s12095-014-0105-6.
  * [9] A. Bernini, S. Bilotta, R. Pinzani, A. Sabri & V. V. Vajnovszki (2015): _Gray code orders for q-ary words avoiding a given factor_.  Acta Inform. 52, pp. 573–592, 10.1007/s00236-015-0225-2.
  * [10] A. Bernini, S. Bilotta, R. Pinzani & V. V. Vajnovszki (2015): _A trace partitioned Gray code for q-ary generalized Fibonacci strings_.  J. Discrete Math. Sci. Cryptogr. 18, pp. 751–761, 10.1080/09720529.2014.968360.
  * [11] A. Bernini, S. Bilotta, R. Pinzani & V. V. Vajnovszki (2017): _A Gray code for cross-bifix-free sets_.  Math. Structures Comput. Sci. 27, pp. 184–196, 10.1017/S0960129515000067.
  * [12] J. Berstel & D. Perrin (1985): _Theory of codes_.  Academic Press, Orlando.
  * [13] S. Bilotta (2017): _Variable-length non-overlapping codes_.  IEEE Trans. Inform. Theory 63, pp. 6530–6537, 10.1109/TIT.2017.2742506.
  * [14] A. J. de Lind van Wijngaarden, T. J. & Willink (2000): _Frame synchronization using distributed sequences_.  IEEE Trans. Comm 48, pp. 2127–2138, 10.1109/26.891223.


# Subtractive spaces of semirings

Amartya Goswami  [1] Department of Mathematics and Applied Mathematics,
University of Johannesburg, P.O. Box 524, Auckland Park 2006, South Africa.
[2] National Institute for Theoretical and Computational Sciences (NITheCS),
South Africa<EMAIL_ADDRESS>
###### Abstract.

Using the closure operator that defines a subtractive ideal of a semiring $S$,
in this note we introduce a topology on the set of all ideals of $S$ induced
by that operator. We show that the corresponding subtractive space is $T_{0}$
and every nonempty irreducible closed set has a unique generic point, whereas
the restricted subspace of subtractive ideals is $T_{1}$. Using a semiring
homomorphism, we obtain a continuous map between the corresponding subtractive
spaces.

###### Key words and phrases:

semiring, subtractive ideal, generic point

###### 1991 Mathematics Subject Classification:

16Y60

##  1\. Introduction and Preliminaries

Since the introduction of semirings in [5], it is natural to compare and
extend results from rings to semirings. One may think that semirings can
always be extended to rings, but [6] gives examples of semirings that can not
be embedded in rings. Furthermore, the lack of ‘subtraction’ in a semiring
makes the behaviour of ideals substantially different from that of rings. To
minimize this gap, the notion of a ‘$k$-ideal’ (also called a subtractive
ideal in [1]) has been introduced in [2]. There is a natural closure operator
that defines a subtractive ideal. The aim of this note is to introduce a
topology on the set of all ideals of a semiring induced by this closure
operator. We study a few topological properties of these spaces.

A (commutative) _semiring_ is a system $(S,+,0,\cdot,1)$ such that $(S,+,0)$
is a commutative monoid, $(S,\cdot,1)$ is a commutative monoid, $0\cdot
x=0=x\cdot 0$ for all $x\in S,$ and $\cdot$ distributes over $+$. We shall
write $xy$ for $x\cdot y.$ A _semiring homomorphism_ $\phi\colon S\to
S^{\prime}$ is a map such that $\phi(x+y)=\phi(x)+\phi(y),$
$\phi(xy)=\phi(x)\phi(y),$ and $\phi(1)=1$ for all $x,$ $y\in S.$ An _ideal_
$I$ of a semiring $S$ is an additive submonoid of $S$ such that $rx\in I$ for
all $x\in I$ and $r\in S.$ An ideal $I$ is called _proper_ if $I\neq S.$ We
also use the symbol $0$ to denote the zero ideal of $S$.

Recall from [1] that a _subtractive ideal_ $I$ of $S$ is an ideal of $R$ such
that $x,$ $x+y\in I$ imply $y\in I$. Equivalently, an ideal $I$ of $S$ is
called a $k$-ideal if $x+y\in I$ implies either $x,$ $y\in I$ or $x,$ $y\notin
I.$ Surely, the zero ideal is subtractive and is contained in every $k$-ideal
of $S$. We denote the set of all ideals and all subtractive ideals of $S$ by
$\mathcal{I}\\!\textit{dl}(S)$ and
$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S)$
respectively. The notion of a subtractive ideal can also be characterized in
terms of a closure operator endowed on $\mathcal{I}\\!\textit{dl}(S)$. Suppose
$I\in\mathcal{I}\\!\textit{dl}(S)$. A _subtractive closure_ (also known as
$k$-closure, see [4, Lemma 2.2]) operator
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}$ is defined by

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)=\\{r\in S\mid r+x\in
I\;\text{for some}\;x\in I\\}.$ (1.1)

######  Lemma 1.1.

Let $I$, $\\{I_{\lambda}\\}_{\lambda\in\Lambda}$, and $J$ be ideals of a
semiring $S$. Then $\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}$ has the
following properties.

  1. (1)

$I\subseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I).$

  2. (2)

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(0)=0.$

  3. (3)

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(S)=S.$

  4. (4)

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I))=\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I).$

  5. (5)

$I\subseteq J$ implies
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\subseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(J).$

  6. (6)

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I\cup
J)\supseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\cup\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(J).$

  7. (7)

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}\left(\bigcap_{\lambda\in\Lambda}I_{\lambda}\right)=\bigcap_{\lambda\in\Lambda}\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{\lambda}).$

  8. (8)

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)$ is the smallest
subtractive ideal containing $I$.

  9. (9)

$I$ is a subtractive if and only if
$I=\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I).$

###### Proof.

The proofs of (1)–(7) are straightforward. For (8), see [3, Proposition 3.1],
whereas for (9), we refer to [4, Lemma 2.2]. ∎

It is obvious from from Lemma 1.1(5) that
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\subseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(\sqrt{I})$
for all $I\in\mathcal{I}\\!\textit{dl}(S).$ Note that we may use Lemma 1.1(9)
as an alternative definition of a subtractive ideal of a semiring. From (8),
it follows that a $\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}$ is indeed a
map

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}\colon\mathcal{I}\\!\textit{dl}(S)\to\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S)$

defined by (1.1). Considering the inclusion map
$\iota\colon\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S)\to\mathcal{I}\\!\textit{dl}(S)$,
it is easy to see the following.

######  Proposition 1.2.

The pair $(\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}},\iota)$ forms a
Galois connection.

######  Lemma 1.3.

If $I$ and $J$ are two subtractive ideals of a semiring $S$, then their
product $IJ$ is also a subtractive ideal of $R$, and $IJ\subseteq I\cap J.$

###### Proof.

Suppose $x,$ $x+y\in IJ$. Then $x=ij$ and $x+y=i^{\prime}j^{\prime}$ for some
$i,$ $i^{\prime}\in I$ and $j,$ $j^{\prime}\in J.$ Since $I$ is an ideal,
$ij,$ $i^{\prime}j^{\prime}\in I$, that is, $x,$ $x+y\in I$. Since $I$ is also
a subtractive ideal, this implies $y\in I.$ Similarly, we can show that $y\in
J.$ Hence, $y\in IJ,$ and this proves that $IJ$ is a subtractive ideal.

Let $r\in IJ$. Then there exists an $x\in IJ$ such that $r+x\in IJ.$ Since $I$
and $J$ are ideals of $S$, we definitely have $IJ\subseteq I\cap J$, which
implies that $r+x,$ $x\in I\cap J$. Since $I$ and $J$ are also subtractive
ideals, we must have $r\in I\cap J$, as required. ∎

If $\\{I_{\lambda}\\}_{\lambda\in\Lambda}$ is a family of subtractive ideals,
then their intersection $\bigcap_{\lambda\in\Lambda}I_{\lambda}$ is also a
subtractive ideal. Note that the sum of two subtractive ideals of a semiring
need not be a subtractive ideal. Recall from [1, Example 6.19] that
$2\mathds{N}$ and $3\mathds{N}$ are subtractive ideals of the semiring
$\mathds{N}$, however $2\mathds{N}+3\mathds{N}=\mathds{N}\setminus\\{1\\}$ is
not a subtractive ideal of $\mathds{N}$, however it is so in a lattice ordered
semiring (cf. [1, Corollary 21.22]). The lattice of all ideals of a ring is
modular, whereas the same is not true for a semiring. Nevertheless, we have
the following result that announced in [2]. For a proof, see [1, Proposition
6.38].

######  Proposition 1.4.

Let $S$ be a semiring. Then
$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S)$ is a modular
lattice.

##  2\. Subtractive spaces

From Lemma 1.1(1)–(5), we observe that a closure operator
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}$ satisfies the axioms of an
algebraic closure operators. However, it is not true in general that
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}$ is closed under finite
unions, and hence, it is not a Kuratowski closure operator. Considering the
subsets
$\\{\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\\}_{I\in\mathcal{I}\\!\textit{dl}(S)}$
of $S$ as subbasic closed sets, nevertheless, induce a topology on
$\mathcal{I}\\!\textit{dl}(S)$, which we call a _subtractive topology_ and
denote by $\tau_{s}$. For a semiring $S$, the set
$\mathcal{I}\\!\textit{dl}(S)$ endowed with a subtractive topology is called a
_subtractive space_ , and instead of
$(\mathcal{I}\\!\textit{dl}(S),\tau_{s})$, we denote the space also by
$\mathcal{I}\\!\textit{dl}(S)$.

######  Lemma 2.1.

The subbasic closed sets of a subtractive space $\mathcal{I}\\!\textit{dl}(S)$
are the subtractive ideals of $S$.

###### Proof.

The proof follows from (8) and (9)) of Lemma 1.1. ∎

If $I,$ $I^{\prime}\in\mathcal{I}\\!\textit{dl}(S)$ and $I\neq I^{\prime}$,
then it is easy to see that
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\neq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I^{\prime})$,
and hence we have

######  Lemma 2.2.

Every subtractive space is $T_{{\scriptscriptstyle 0}}.$

Recall that a nonempty closed subset $D$ of a topological space is
_irreducible_ if $D\neq D_{\scriptscriptstyle 1}\cup D_{\scriptscriptstyle 2}$
for any two proper closed subsets $D_{\scriptscriptstyle 1}$ and
$D_{\scriptscriptstyle 2}$ of $D$. A point $x$ in a closed subset $D$ is
called a _generic point_ of $D$ if $D=\overline{\\{x\\}}.$

######  Proposition 2.3.

Every nonempty subbasic closed set of a subtractive space is irreducible.

###### Proof.

We show that
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)=\overline{\\{I\\}}$ for all
$I\in\mathcal{I}\\!\textit{dl}(S).$ Since $\overline{\\{I\\}}$ is the smallest
closed set containg $I$, it follows from Lemma 1.1(1) that
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\supseteq\overline{\\{I\\}}$.
To have the other inclusion, first consider the trivial case of
$\overline{\\{I\\}}=\mathcal{I}\\!\textit{dl}(S).$ For this we have

$\mathcal{I}\\!\textit{dl}(S)=\overline{\\{I\\}}\subseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\subseteq\mathcal{I}\\!\textit{dl}(S),$

and hence
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\subseteq\overline{\\{I\\}}.$
Now suppose

$\overline{\\{I\\}}=\bigcap_{\lambda\in\Lambda}\left(\bigcup_{i=1}^{n_{\lambda}}\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{i\lambda})\right).$

This means that
$I\subseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{i\lambda})$ for
some $i$ and each $\lambda\in\Lambda$. But that implies

$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)\subseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}\left(\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{\lambda
i})\right)=\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{\lambda
i})\subseteq\bigcap_{\lambda\in\Lambda}\left(\bigcup_{i=1}^{n_{\lambda}}\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{i\lambda})\right),$

and hence we have the desired inclusion. ∎

######  Corollary 2.4.

$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S)$ is the
largest $T_{{\scriptscriptstyle 1}}$-subspace of a subtractive space
$\mathcal{I}\\!\textit{dl}(S)$.

###### Proof.

If $I\in\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S),$ then
by Proposition 2.3, we have
$I=\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)=\overline{\\{I\\}}.$ ∎

######  Theorem 2.5.

Every nonempty irreducible closed subset of a subtractive space has a unique
generic point.

###### Proof.

Suppose $D$ is a nonempty irreducible closed subset of a subtractive space
$\mathcal{I}\\!\textit{dl}(S)$. Then
$D=\bigcap_{\lambda\in\Lambda}\mathcal{E}_{\lambda}$, where each
$\mathcal{E}_{\lambda}$ is a finite union of subbasic closed sets of
$\tau_{s}.$ Since $D$ is irreducible, for every $\lambda\in\Lambda$, there
exists an $I_{\lambda}\in\mathcal{I}\\!\textit{dl}(S)$ such that

$D\subseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{\lambda})\subseteq\mathcal{E}_{\lambda},$

and this implies

$D=\bigcap_{\lambda\in\Lambda}\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{\lambda})=\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}\left(\bigcap_{\lambda\in\Lambda}I_{\lambda}\right)=\overline{\left\\{\bigcap_{\lambda\in\Lambda}I_{\lambda}\right\\}},$

where, the last equality follows from Proposition 2.3. This proves the
existence of the generic point, whereas the uniqueness of it follows from
Lemma 2.2. ∎

Using a semiring homomorphism, our aim in this section is to construct a
continuous map between the corresponding subtractive spaces and study some of
the properties of these maps. The main difference compared to Zariski topology
is that we have to use subbasic-closed-set formulation to study these maps.

######  Lemma 2.6.

If $\phi\colon S\to S^{\prime}$ is a semiring homomorphism and
$J\in\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S^{\prime})$.
Then the following hold.

  1. (1)

$\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(J)$ is a subtractive
ideal of $S$. In particular, $\mathrm{ker}\phi$ is a subtractive ideal of $S$.

  2. (2)

$\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(J)=\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(J)).$

###### Proof.

For the first part of (1), it is well-known that
$\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(J)\in\mathcal{I}\\!\textit{dl}(S).$
Suppose $x,$ $x+y\in\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(J).$
Then $\phi(x),$ $\phi(x+y)=\phi(x)+\phi(y)\in J$. Since
$J\in\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S^{\prime}),$
we must have $\phi(y)\in J,$ and hence
$y\in\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(J).$ For the second
part of (1), let $x,$ $x+y\in\mathrm{ker}\phi.$ This implies
$\phi(y)=\phi(x)+\phi(y)=\phi(x+y)=0,$ and hence $y\in\mathrm{ker}\phi.$ The
proof of (2) follows immediately from (1). ∎

######  Proposition 2.7.

Suppose $\phi\colon S\to S^{\prime}$ is a semiring homomorphism.

  1. (1)

The map $\phi$ induces a continuous map
$\phi_{!}\colon\mathcal{I}\\!\textit{dl}(S^{\prime})\to\mathcal{I}\\!\textit{dl}(S)$
defined by
$\phi_{!}(J)=\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(J)$, where
$J\in\mathcal{I}\\!\textit{dl}(S^{\prime}).$

  2. (2)

If $\phi$ is surjective, then the subtractive spaces
$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S^{\prime})$ and
$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S)$ are
homeomorphic.

###### Proof.

To show (1), let $\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)$ be a
subbasic closed set of the subtractive space $\mathcal{I}\\!\textit{dl}(S)$,
and for us it is sufficient to show that
$\phi(\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I))\subseteq\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(\langle\phi(I)\rangle).$
Let $s^{\prime}\in\phi(\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)).$
This implies
$\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(s^{\prime})\in\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I),$
and hence

$\phi\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(s^{\prime})+\phi(i)\in\phi(I)\subseteq\langle\phi(I)\rangle,$

for some $i\in I.$ From this we conclude that
$s^{\prime}\in\phi\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(s^{\prime})\in\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(\langle\phi(I)\rangle).$

For (2), it is easy to see that the map $\phi_{!}$ is injective. Since by
hypothesis $\phi_{!}$ is surjective and by (1), $\phi_{!}$ is continuous, what
remains is to show that $\phi_{!}$ is closed. Notice that if
$\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I)$ is a subbasic closed
subset of
$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S^{\prime})$,
then by Lemma 2.6(2),
$\phi_{!}(\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I))$ is also a
subbasic closed set of
$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S^{\prime}).$
Now if $K$ is a closed subset of
$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S^{\prime})$,
then there exists a collection
$\\{I_{j\lambda}\mid\lambda\in\Lambda,1\leqslant j\leqslant m_{\lambda}\\}$ of
subtractive ideals of $S^{\prime}$ such that

$\displaystyle\phi_{!}(K)$
$\displaystyle=\phi_{!}\left(\bigcap_{\lambda\in\Lambda}\left(\bigcup_{j\,=1}^{m_{\lambda}}\mathcal{C}_{\scriptscriptstyle{\mathrm{sub}}}(I_{j\lambda})\right)\right)$
$\displaystyle=\phi_{!}\left(\bigcap_{\lambda\in\Lambda}\left(\bigcup_{j\,=1}^{m_{\lambda}}I_{j\lambda}\right)\right)$
$\displaystyle=\bigcap_{\lambda\in\Lambda}\bigcup_{j=1}^{m_{\lambda}}\phi^{\raisebox{0.60275pt}{$\scriptscriptstyle-1$}}(I_{j\lambda}),$

a closed subset of
$\mathcal{I}\\!\textit{dl}_{\scriptscriptstyle{\mathrm{sub}}}(S).$ ∎

## References

  * [1] J. S. Golan, Semirings and their applications, Springer, 1999.
  * [2] M. Henriksen, Ideals in semirings with commutative addition, Amer. Math. Soc. Notices, 6(3) 31 (1958), 321.
  * [3] J. Jun, S. Ray, and J. Tolliver, Lattices, spectral spaces, and closure operators on idempotent semirings, J. Algebra, 594 (2022), 313–363.
  * [4] M. K. Sen and M. R. Adhikari, On $k$-ideals of semirings, Internat. J. Math. & Math. Sci., 15(2) (1992), 347–350.
  * [5] H. S. Vandiver, Note on a simple type of algebra in which the cancellation law of addition does not hold, Bull. Am. Math. Soc., 40(12) (1934), 914–920.
  * [6] H. S. Vandiver, On some simple types of semi-rings, Am. Math. Monthly, 46(1) (1939), 22–26.