# IBIS soluble linear groups

###### Abstract.

Let $G$ be a finite permutation group on $\Omega.$ An ordered sequence
$(\omega_{1},\dots,\omega_{t})$ of elements of $\Omega$ is an irredundant base
for $G$ if the pointwise stabilizer is trivial and no point is fixed by the
stabilizer of its predecessors. If all irredundant bases of $G$ have the same
cardinality, $G$ is said to be an IBIS group. In this paper we give a
classification of quasi-primitive soluble irreducible IBIS linear groups, and
we also describe nilpotent and metacyclic IBIS linear groups and IBIS linear
groups of odd order.

Andrea Lucchini1 and Dmitry Malinin2 11footnotetext:  Dipartimento di
Matematica “Tullio Levi-Civita”, Università degli Studi di Padova, Via Trieste
63, 35121, Padova, Italy; email address<EMAIL_ADDRESS>22footnotetext:  Dipartimento di Matematica “Tullio Levi-Civita”, Università
degli Studi di Padova, Via Trieste 63, 35121, Padova, Italy; email address:
<EMAIL_ADDRESS>

##  1\. Introduction

Let $G\leq\operatorname{Sym}(\Omega)$ be a finite permutation group. A subset
$\mathcal{B}$ of $\Omega$ is a _base_ for $G$ if the pointwise stabilizer
$G_{(\mathcal{B})}$ is trivial and we denote by $b(G)$ the minimal size of a
base for $G$. An ordered sequence of elements of $\Omega$,
$\Sigma:=(\omega_{1},\dots,\omega_{t})$, is _irredundant_ for $G$ if no point
in $\Sigma$ is fixed by the stabiliser of its predecessors. Moreover $\Sigma$
is an _irredundant base_ of $G$, if it is a base and it is irredundant. In
particular, such an irredundant base provides the following stationary chain

$G>G_{\omega_{1}}>G_{(\omega_{1},\omega_{2})}>\dots>G_{(\omega_{1},\dots,\omega_{t-1})}>G_{(\omega_{1},\dots,\omega_{t})}=1,$

where the inclusion of subgroups are strict.

Irredundant bases for a permutation group possess some of the features of
bases in a vector space. Indeed, $\mathcal{B}$ is a basis for a vector space
$V$ if and only if it is an irredundant base for the general linear group
$\operatorname{GL}(V)$ in its natural action on $V.$ However, some familiar
properties of bases in vector spaces do not extend to bases for permutation
groups: irredundant bases for groups in general are not preserved by
reordering, and they can have different sizes.

In [6], Cameron and Fon-Der-Flaass showed that all irredundant bases for a
permutation group $G$ have the same size if and only if all the irredundant
bases for $G$ are preserved by re-ordering. Groups satisfying one of the
previous equivalent properties are called _Irredundant Bases of Invariant Size
groups_ , _IBIS groups_ for short. Moreover, Cameron and Fon-Der-Flaass [6]
also proved that for a permutation group $G$ to be IBIS is a necessary and
sufficient for the irredundant bases of $G$ to be the base of a combinatorial
structure known with the name of matroid. If this condition hold, then $G$
acts geometrically on the matroid and when $G$ acts primitively and is not
cyclic of prime order, then the matroid is geometric (see [6] for more
details). This brought Cameron to ask for a possible classification of the
IBIS groups. As explained by Cameron himself in [5, Section 4-14], there is no
hope for a complete classification of IBIS groups, when the cardinalities of
the bases are large. But it might be reasonable to pose this question for
primitive groups. The first attempt of classifying finite primitive IBIS
groups has been done in [12]. Their approach is via the O’Nan-Scott
classification of primitive groups.

######  Theorem 1.1.

[12, Theorem 1.1] Let $G$ be a primitive IBIS group. Then one of the following
holds:

  1. (1)

$G$ is of affine type,

  2. (2)

$G$ is almost simple,

  3. (3)

$G$ is of diagonal type.

Moreover, G is a primitive IBIS group of diagonal type if and only if it
belongs to the infinite family of diagonal groups
$\\{\operatorname{PSL}(2,2^{f})\times\operatorname{PSL}(2,2^{f})|f\in\mathbb{N},f\geq
2\\}$ having degree $|\operatorname{PSL}(2,2^{f})|=2^{f}(4^{f}-1).$

In the light of this result, the problem of understanding finite primitive
IBIS groups is reduced to affine groups and to almost simple groups. There is
some hope for dealing with the second family. Indeed, suppose that $G$ is an
almost simple primitive IBIS group with $b(G)=2.$ In particular, all bases of
$G$ have cardinality 2. Thus, for any two distinct points $\alpha$ and $\beta$
in the domain of $G$ we have $G_{\alpha}\cap G_{\beta}=1.$ Therefore $G$ is a
Frobenius group, contradicting the fact that $G$ is almost simple. Thus, if
$G$ is an almost simple primitive IBIS group, then $b(G)\geq 3$ and one can
get useful information from the work of Burness, O’Brien, Liebeck, Saxl,
Shalev and Wilson on the base size of primitive permutation groups (see for
instance [1], [2], [3], [4]). A first result in this direction has been
obtained in [11], where the authors determine the almost simple primitive IBIS
groups having socle an alternating group.

Dealing with the primitive groups of affine type seems very difficult. In this
case $G$ is a semidirect product $G=V\rtimes X,$ where $X$ is an irreducible
subgroup of $\operatorname{GL}(V)$. It follows immediately from the definition
that $G$ is an IBIS permutation group if and only if $X$ induces an IBIS
permutation group on the set $V\setminus\\{0\\}$, in which case we will say
that $X$ is a linear IBIS group, or more precisely, that $X$ is an IBIS
subgroup of $\operatorname{GL}(V).$

In this paper we are interested in collecting information on the IBIS
irreducible linear groups that are soluble. Given $G\leq\operatorname{GL}(V)$,
we will denote by $b(G)$ the smallest cardinality of a base for the action of
$G$ on $V\setminus\\{0\\}.$ By the main result in [14], $b(G)\leq 3$ for any
soluble irreducible linear group $G.$ Notice that $b(G)=1$ if and only if $G$
has a regular orbit on $V$ and that in this case $G$ is IBIS if and only if it
is a Frobenius complement in $V\rtimes G$, i.e. if and only if $G$ acts fixed-
point-freely on $V.$ In a very resent paper Yang, Vasil’ev and Vdovin [13]
proved that an irreducible quasi-primitive soluble subgroup of
$\operatorname{GL}(V)$ which is not metacylic has a regular orbit, except for
a few “small” cases. These cases have been completely classified in a
subsequent paper by Holt and Yang [8], and so it is possible to produce with
MAGMA the list of all the primitive irreducible non-metacyclic groups $G$ that
are IBIS with $b(G)\neq 1.$ More precisely we can state the following results:

######  Theorem 1.2.

If $G$ is a soluble irreducible quasi-primitive IBIS subgroup of
$\operatorname{GL}(V),$ then one of the following occurs:

  1. (1)

$G$ is metacyclic;

  2. (2)

$G$ is a Frobenius complement;

  3. (3)

$G$ is one of the 39 exceptional linear groups listed in Table 1.

The metacyclic case is investigated in Section 3. If $V$ is a finite vector
space of dimension $n$ over $\operatorname{GF}(q),$ where $q$ is a prime
power, we denote by $\Gamma(q^{n})=\Gamma(V)$ the semilinear group of $V,$
i.e.

$\Gamma(q^{n})=\\{x\mapsto ax^{\phi}\mid
x\in\operatorname{GF}(q^{n}),a\in(\operatorname{GF}(q^{n}))^{*},\phi\in\operatorname{Gal}(\operatorname{GF}(q^{n})/\operatorname{GF}(q))\\}.$

This group has a normal cyclic subgroup $N$ of order $q^{n}-1$ (a so called
Singer cycle) consisting of those elements with $\phi=1.$ The subgroup $N$
acts regularly on $V\setminus\\{0\\},$ and $\Gamma(q^{n})/N$ is cyclic of
order $n.$ Our main result is the following:

######  Theorem 1.3.

Suppose that $G\leq\Gamma(q^{n}),$ with $n>1$ and $|G/G\cap N|=n.$ If $G$ is
IBIS, then either $G$ is a Frobenius complement or there exists a prime
divisor $s$ of $n$ such that, for every $v\in V\setminus\\{0\\},$ the
stabilizer $G_{v}$ has order $s.$ More precisely, if $\phi$ is the
automorphism of $\operatorname{GL}(q^{n})$ sending to $f$ to $f^{q}$ and $\phi
b\in G$ for some $b\in N,$ then $G$ is IBIS if and only if there exists a
divisor $r$ of $n$ such that:

  1. (1)

$N^{q^{r}-1}\leq G;$

  2. (2)

for every proper divisor $t$ of $r,$ $b^{(q^{t}-1)/(q-1)}\notin
N^{q^{t}-1}(N\cap G).$

  3. (3)

one of the following occurs:

    1. (a)

$s=n/r$ is a prime and $b^{(q^{r}-1)/(q-1)}\in N\cap G;$

    2. (b)

$n=r$.

In case (a) the stabilizers in $G$ have order $s,$ in case (b) $G$ is a
Frobenius complement.

In Section 3, we will apply the previous theorem to produce some non-trivial
examples of IBIS metacyclic linear groups. Two interesting corollaries of
Theorem 1.3 are the following:

######  Corollary 1.4.

Suppose $n>1.$ Then $\Gamma(q^{n})$ is IBIS if and only if $n$ is a prime.

######  Corollary 1.5.

Suppose that $G\leq\Gamma(q^{n}),$ with $n$ a prime and $|G/G\cap N|=n.$ Then
$G$ is IBIS if and only if one of the following occurs:

  1. (1)

$G=(N\cap G)\langle\phi\rangle,$ with $N^{q-1}\leq G;$

  2. (2)

$G=(N\cap G)\langle\phi b\rangle,$ for some $b\in N$ such that $b\notin
N^{q-1}(N\cap G).$

For example consider the subgroup $G$ of $\Gamma(5^{2})$ generated by $\phi$
and $a\in N$ with $|a|=3:$ since $|N^{4}|=6,$ $G$ is not IBIS.

The study of the IBIS property in the case of imprimitive soluble linear
groups is much more difficult. Apparently there is no strategy for a reduction
from the imprimitive to primitive case. However we are able to solve the
problem in the particular case of nilpotent irreducible linear groups. First
we describe two families of irreducible linear groups that are IBIS. The
following is a consequence of Corollary 1.5.

######  Proposition 1.6.

Let $r=2^{b}-1$ be a Mersenne prime. Consider the following two subgroups of
$\Gamma(r^{2})=N\langle\phi\rangle:$ $P_{1}=O_{2}(N)\langle\phi\rangle$ (a
semidihedral group of size $2^{b+2}$) and
$P_{2}=(O_{2}(N))^{2}\langle\phi\rangle$ (a dihedral group of size $2^{b+1}$).
If $G=PC\leq\Gamma(r^{2})$ with $P\in\\{P_{1},P_{2}\\}$ and $C\leq
O_{2^{\prime}}(N),$ then $G$ is an irreducible nilpotent IBIS subgroup of
$\Gamma(r^{2})$ and $b(G)=2.$

######  Proposition 1.7.

Let $W$ be the additive group of a finite field $F$ and let $H$ be the
multiplicative group of $F$, acting on $W$ by scalar multiplication and
consider the wreath product $X=H\wr S_{2}$ in its imprimitive action on
$V=W^{2}.$ Let $G$ be a subgroup of $X$ satisfying the following conditions:

  1. (1)

$\langle(1,2),(h,h^{-1})\mid h\in H\rangle\subseteq G$ for every $h\in H$;

  2. (2)

$(k,1)\in G$ for some $1\neq k\in H.$

Then $G$ is an irriducible IBIS subgroup of $\operatorname{GL}(V),$ with
$b(G)=2.$ In particular if $H$ is a 2-group, then $G$ is a nilpotent
irreducible IBIS linear group.

Now we may state our result on nilpotent irreducible IBIS linear groups.

######  Theorem 1.8.

If $G$ is a nilpotent IBIS irreducible subgroup of $\operatorname{GL}(V),$
then one of the following occurs:

  1. (1)

$G$ acts fixed-point-freely on $V.$

  2. (2)

$G$ is as in Proposition 1.6.

  3. (3)

$G$ is as in Proposition 1.7.

In Section 5 we consider the case of IBIS linear groups of odd order.

######  Theorem 1.9.

Let $G$ be an IBIS irreducible subgroup of $\operatorname{GL}(V)$. If $|G|$ is
odd, then either $G$ acts fixed-point-freely on $V$ or $G$ is a primitive
metacyclic group.

######  Corollary 1.10.

Assume that $G$ is a soluble primitive permutation group of degree $n$ and odd
order. If $G$ is an IBIS permutation group, then either $G$ is a Frobenius
group or $G\leq\operatorname{A\Gamma L}(1,n).$

Acknowledgements. The authors are grateful to Pablo Spiga for the computations
performed for finding exceptional IBIS groups using MAGMA.

The second author is grateful for the research grant from the University of
Padova.

##  2\. The 39 exceptions in Theorem 1.2

In Table 1 we collect the quasi-primitive solvable groups that do not have a
regular orbit and that are IBIS. Here we give some information in how to read
Table 1. Essentially, we follow the notation in Table 4.1 in the work of Holt
and Yang [8]. We have divided Table 1 in 9 columns. The first column is the
same “No. column” as in [8] and simply denotes the line numbering (in our case
restricted to the cases where some IBIS group does exist) for the files in the
supplementary matherial in [8]. The ${\bf e}$, ${\bf p}$, ${\bf d}$, ${\bf
a}$, ${\bf b}$ have the same meaning as the respective columns in [8, Table
4.1] and this meaning is explained in [8, page 141]. The Nr. indicates the
number of groups that are IBIS in the corresponding line and the Grp. ordrs.
indicates the respective orders. In the Cmmts. column we are giving the
position in the corresponding file of the IBIS groups: the first two rows also
indicate whether the groups are of type $E^{+}$ or $E^{-}$, as indicated in
[8].

No. | ${\bf e}$ | ${\bf p}$ | ${\bf d}$ | ${\bf a}$ | ${\bf b}$ | Nr. | Grp. ordrs. | Cmmnts | Bs. Sz.
---|---|---|---|---|---|---|---|---|---
19 | 4 | 3 | 4 | 1 | 1 | 4 |  $640$, $192$, $320$, $160$ | 2,3,5, 6 $E^{-}$ | 2, 2, 2, 2
19 | 4 | 3 | 4 | 1 | 1 | 4 |  $1152$, $1152$, $576$, $192$ | 2,4,5, 14 $E^{+}$ | 3, 3, 3, 2
48 | 3 | 2 | 6 | 2 | 1 | 1 | $648$ | 3 | 3
62 | 2 | 3 | 2 | 1 | 1 | 2 |  $48$, $24$ | 1, 2 | 2, 2
63 | 2 | 5 | 2 | 1 | 1 | 2 |  $96$, $48$ | 1, 2 | 2, 2
64 | 2 | 7 | 2 | 1 | 1 | 2 |  $144$, $72$ | 1, 2 | 2,2
65 | 2 | 3 | 4 | 2 | 1 | 7 |  $48$, $96$, $96$, $96$ |  | 2, 2, 2, 2
|  |  |  |  |  |  |  $96$, $192$, $192$ | 3,4,5,7,8,10, 11 | 2, 2, 2
66 | 2 | 11 | 2 | 1 | 1 | 2 |  $240$, $48$ | 1, 2 | 2, 2
67 | 2 | 13 | 2 | 1 | 1 | 2 |  $288$, $144$ | 1, 2 | 2, 2
68 | 2 | 17 | 2 | 1 | 1 | 3 |  $384$, $96$, $192$ | 1, 2, 3 | 2, 2, 2
69 | 2 | 19 | 2 | 1 | 1 | 2 |  $432$, $144$ | 1, 2 | 2, 2
71 | 2 | 5 | 4 | 2 | 1 | 6 |  $576$, $144$, $288$ |  | 2, 2, 2
|  |  |  |  |  |  |  $288$, $288$, $576$ | 2,5,8,11,12, 13 | 2, 2, 2
72 | 2 | 3 | 6 | 3 | 1 | 2 |  $1872$, $936$ | 1, 2 | 2, 2
Table 1. Parameters of IBIS quasi-primitive solvable groups that do not have a
regular orbit.

The computational work to produce the table has been organized as follows:

  1. (1)

Exhaustive search of bases having size 2. All cases where small enough, so
this step was easy and only a matter of time.

  2. (2)

For the groups having a base of size 2 (the most frequent sitation) we started
a random search for bases having size 3. In all cases where this was
successful, the group was not IBIS and hence it could be omitted from further
analysis.

  3. (3)

For the groups passing the previous step, if these groups are small, we
checked extensively for bases having 3. If the groups are large, for each
orbit we constructed the action of $G$ on this orbit and checked extensively
for bases having size 3 in this action.

  4. (4)

Similarly, for the few cases where there is no base of size 2, we check the
existence of bases of size 4.

##  3\. Metacyclic groups

######  Lemma 3.1.

Suppose that $G\leq\Gamma(q^{n}),$ with $n>1$ and $|G/G\cap N|=n.$ If $G$ is
IBIS, then either $G$ is a Frobenius complement or, for every $v\in
V\setminus\\{0\\},$ the stabilizer $G_{v}$ has order prime order.

###### Proof.

Let $\Gamma=\Gamma(q^{n}).$ We identify the elements of $N$ and the elements
of $W:=V\setminus\\{0\\}$ with the non-zero elements of the field
$\operatorname{GF}(q^{n}).$ Notice that, for every $a\in W,$ we have
$\Gamma_{a}=\langle\phi a^{1-q}\rangle.$ Moreover, if $m$ divides $n,$ then
$(\phi a^{1-q})^{m}=\phi^{m}a^{1-q^{m}}.$ Suppose that $G$ is IBIS, but not a
Frobenius complement. Let $a\in W.$ We want to prove that the stabilizer
$G_{a}$ of $a$ in $G$ has prime order. Since $G_{a}$ coincides with the
stabilizer of 1 in the subgroup $G^{a^{-1}}$ of $\Gamma$ obtained by
conjugation with $a^{-1},$ we may assume $a=1.$ Hence there exists a proper
divisor $r$ of $n$ with $G_{1}=\langle\phi^{r}\rangle$. Let $s=|G_{1}|=n/r.$
Notice that if $N=\langle c\rangle,$ then
$\Gamma_{c}\cap\langle\phi\rangle=1.$ So in particular $G_{c}\cap G_{1}=1,$
and $(1,c)$ is an irredundant base. Suppose that $s$ is not a prime, and write
$s=tu,$ with $t,u>1.$ Then $n=rs=rtu$, so $q^{rt}-1$ divides $q^{n}-1$ and if
$d\in N$ has order $q^{rt}-1,$ then $\phi^{rt}$ is a non-trivial element of
$G_{d}$, while $\phi^{rt}\notin G_{c}.$ But then also $(1,d,c)$ is an
irredundant base, in contradiction with the fact that $G$ is IBIS. ∎

######  Lemma 3.2.

Suppose that $G\leq\Gamma(q^{n}),$ with $n>1$ and $|G/G\cap N|=n.$ If $G$ is
IBIS, then either $G$ is a Frobenius complement or there exists a prime $s$
such that $|G_{v}|=s$ for every $v\in V\setminus\\{0\\}.$

###### Proof.

Suppose that $G$ is IBIS, but not a Frobenius complement. By the previous
lemma, $|G_{1}|=s_{1}$ for some prime $s_{1}.$ Let now $a\in
V\setminus\\{0\\}$, and assume $|G_{a}|=s_{2}.$ Let $r_{1}=n/s_{1}$ and
$r_{2}=n/s_{2}$. Notice that $g_{1}=\phi^{r_{1}}$ and
$g_{2}=\phi^{r_{2}}a^{1-q^{r_{2}}}$ belong to $G.$ Let $d=(r_{1},r_{2})$.
There exist $x,y\in\mathbb{Z}$ with $d=xr_{1}+yr_{2}.$ Hence, setting
$t=1+q^{r_{2}}+\dots+q^{r_{2}(y-1)}$ and $u=t(1-q^{r_{2}})/(1-q^{d}),$ we have

$g_{1}^{x}g_{2}^{y}=\phi^{d}a^{(1-q^{r_{2}})t}=\phi^{d}(a^{u})^{1-q^{d}}\in
G_{a^{u}}.$

Hence $n/d$ divides $|G_{a^{u}}|$ and therefore, by Lemma 3.1, $n/d$ is a
prime. This is possible only if $d=r_{1}=r_{2}$, i.e. if $s_{1}=s_{2}.$ ∎

###### Proof of Theorem 1.3.

The first part of the statement follows from Lemma 3.2.

Assume that $G$ is an IBIS subgroup of $\Gamma=\Gamma(q^{n})$ and that $\phi
b\in G$ for some $b\in N.$ We identify the elements of $N$ and the elements of
$W:=V\setminus\\{0\\}$ with the non-zero elements of the field
$\operatorname{GF}(q^{n})$ and we set $H=G\cap N.$ Either $G$ is a Frobenius
complement or there exists a prime $s$ such that all the stabilizers in $G$
have order $s.$ We set $r=n$ in the first case, $r=n/s$ in the second. If $G$
is a Frobenius complement, then $N^{q^{r}-1}=N^{q^{n}-1}\in G.$ Otherwise
$G_{1}=\langle\phi^{r}\rangle$ and therefore $\phi^{r}\in G=H\langle\phi
b\rangle,$ which implies $b^{(q^{r}-1)/(q-1)}\in H.$ Moreover, for every $a\in
W,$ $G_{a}=\langle\phi^{r}a^{1-q^{r}}\rangle\leq G$. This implies in
particular that $N^{q^{r}-1}\leq H.$ Finally notice that in any case, if $t$
is a proper divisor of $r$ then, for every $a\in V\setminus\\{0\\},$
$\phi^{t}a^{1-q^{t}}\notin\Gamma_{a}\setminus G$: this means

$\phi^{t}a^{1-q^{t}}\neq(\phi b)^{t}=\phi^{t}b^{(q^{t}-1)/(q-1)}\mod H,$

for every $a\in N$, or equivalently $b^{(q^{t}-1)/(q-1)}\notin
N^{q^{t}-1}(G\cap N).$

Conversely, if $G=H\langle\phi b\rangle$ satisfies conditions (1), (2) and
(3), then $|G_{a}|=n/r$ for every $a\in V\setminus\\{0\\}$, and therefore $G$
is IBIS. ∎

Consider for example the following subgroup of $\Gamma(q^{4})$: $G=\langle\phi
a,a^{q+1}\rangle$, with $|a|=q^{4}-1.$ We have $N^{q^{2}-1}\leq G.$ Moreover,
if $q$ is odd, then $a\notin N^{q-1}(G\cap N)=N^{q-1}N^{q+1}=\langle
a^{2}\rangle.$ But then it follows from Theorem 1.3 that if $q$ is odd, then
$G$ is an IBIS linear group of order $4(q^{3}-q^{2}+q-1),$ in which the
stabilizer of every nonzero vector has order 2.

##  4\. Nilpotent irreducible IBIS linear groups

A result useful to investigate the IBIS irreducible linear groups $G$ with
$b(G)=2$ is the following:

######  Proposition 4.1.

Let $G$ be an IBIS irreducible subgroup of $\operatorname{GL}(V)$. If $b(G)=2$
and $V\cong W^{n}$ is an imprimitive decomposition for the action of $G$, then
the stabilizer $H$ of $W$ in $G$ acts transitively on $W\setminus\\{0\\}.$

###### Proof.

We may identify $G$ with a subgroup of the wreath product $H\wr S_{n}.$ Assume
that $H$ is not transitive on $W\setminus\\{0\\}.$ Then there exists an orbit
$\Omega$ for the action of $H$ on $W\setminus\\{0\\},$ with
$|\Omega|\leq(|W|-1)/2.$ Take $u\in\Omega$ and let $\alpha=(u,0,\dots,0)\in
V=W^{n}.$ For any $2\leq i\leq n$ and $w\notin\Omega\cup\\{0\\},$ let

$\beta_{i,w}=(0,\dots,0,w,0,\dots,0){\text{ and
}}\gamma_{i,w}=(u,0,\dots,0,w,0,\dots,0)$

(where $w$ is the entry in the $i$-position). If $y\in G_{\gamma_{i,w}},$ then
$y=(h_{1},\dots,h_{n})\sigma,$ with $uh_{1}=u,wh_{i}=w$ and $1\sigma=1,$
$i\sigma=i.$ In particular $G_{\gamma_{i,w}}=G_{\alpha}\cap G_{\beta_{i,w}}.$
Since $b(G)=2,$ $G_{v}\neq 1$ for every $v\in V,$ and since $G$ is IBIS, if
$G_{v_{3}}=G_{v_{2}}\cap G_{v_{1}},$ then $G_{v_{1}}=G_{v_{2}}=G_{v_{3}}.$ So
$G_{\alpha}=G_{\beta_{i,w}},$ for any $w\notin\Omega\cup\\{0\\},$ and any
$i\geq 2.$ In particular, if $g\in G_{\alpha},$ then $g=(x,y_{2},\dots,y_{n})$
with $x\in H_{u}$ and $y_{j}\in G_{w}$ for every $w\notin\Omega.$ But then the
number of vectors in $W$ fixed by $y_{j}$ is at least $(|W|+1)/2,$ and
therefore $y_{j}=1$ by [9, Theorem 1]. This implies that there exists $1\neq
K\leq H$ such that $G_{\alpha}=\\{(k,1,\dots,1)\mid k\in K\\}.$ On the other
hand, $G$ contains an elements $z=(h_{1},\dots,h_{n})\tau$ with $1\tau=2$ and
$K_{\alpha}^{z}=\\{(1,k^{h_{1}},1,\dots,1)\mid k\in K\\}\leq G_{\alpha},$ a
contradiction. ∎

######  Theorem 4.2.

[7, Theorem 1.1] $b(G)\leq 2$ for every irreducible nilpotent subgroup of
$\operatorname{GL}(V).$

###### Proof of Proposition 1.7.

Let $A=\\{(h,0)\mid h\in H\\}\cap G,B=\\{(0,h)\mid h\in H\\}\cap G$ and let
$v=(w_{1},w_{2})\neq(0,0)\in V.$ If $w_{1}=0,$ then $G_{v}=A,$ if $w_{2}=0,$
then $G_{v}=B$ and if neither $w_{1}=0$ nor $w_{2}=0,$ then
$G_{v}=\langle(h,h^{-1})(1,2)\rangle$ where $h$ is the unique element of $H$
with $v_{1}h=v_{2}.$ In the last case $|G_{v}|=2$ and $G_{v}\cap A=G_{v}\cap
B=1.$ Hence, if $v_{1}$ and $v_{2}$ are non-zero elements of $V$, then either
$G_{v_{1}}=G_{v_{2}}$ or $G_{v_{1}}\cap G_{v_{2}}=1.$ ∎

###### Proof of Theorem 1.8.

If $G$ has a regular orbit on $V$, then (1) holds. So assume that $G$ does not
have a regular orbit on $V.$ By Theorem 4.2, $b(G)=2.$

If $G$ is primitive, then by [10, Theorem 2.4] (see also [10, Remark 2.6]) $G$
is as in Proposition 1.6.

So we may assume that $V$ has an imprimitive decomposition
$V=W_{1}\times\dots\times W_{n}$, with $W\cong W_{i}$ for $1\leq i\leq n$, and
that $G$ permutes primitively the factors $W_{1},\dots,W_{n}.$ Let $H$ be the
nilpotent, irreducible subgroup of $\operatorname{GL}(W)$ induced by the
action on $W_{1}$ of the setwise stabilizer of $W_{1}$ in $G$ and $T$ the
nilpotent primitive permutation group induced by the permutation action of $G$
on the set $\\{W_{1},\dots,W_{n}\\}$. It must be that $n$ is a prime and
$T=\langle\sigma\rangle$, with $\sigma=(1,2,\dots,n)$, and $G\leq
H\wr\langle\sigma\rangle.$ Let $X:=G\cap H^{n}$. Notice that $X$ is a
subdirect product of the base subgroup $H^{n}$, i.e., if $\pi_{i}:X\to H$ is
the projection on the $i$-th component, then $X^{\pi_{i}}=H$ for each
$i=1,\dots,n$. For any $w\in W,$ let $v_{w}=(w,0,\dots,0)\in V.$ If $w\neq 0,$
then $G_{v_{w}}\leq X$ and $(G_{v_{w}})^{\pi}=H_{w}.$ In particular if
$(w_{1},\dots,w_{t})$ is an irredundant base for the action of $H$ on
$W\setminus\\{0\\},$ then $(v_{w_{1}},\dots,v_{w_{t}})$ is an irredundant base
for the action of $G$ on $V\setminus\\{0\\}.$ Hence the assumption that $G$ is
an IBIS subgroup of $\operatorname{GL}(V)$ implies that $H$ is an IBIS
subgroup of $\operatorname{GL}(W).$ By Theorem 4.2, $b(H)=2.$ So we
distinguish two cases:

a) $b(H)=1.$ Fix $0\neq w\in W$, let $\beta_{i}=(w,\dots,w,0,w,\dots,w)\in V$,
with $0$ in the $i$-th position, and $\gamma_{i}=(0,\dots,0,w,0,\dots,0)\in V$
with $w$ in the $i$-th position. As we are assuming that $G$ is IBIS with
$b(G)=2$, $G_{\beta_{i}}\neq 1$. As $H_{w}=1$, we have
$G_{\beta_{i}}=\\{(1,\dots,1,s,1,\dots,1)|s\in S_{i}\\}$ for some nontrivial
subgroup $S_{i}$ of $H$. Moreover, if $g\in G_{\gamma_{i}},$ then $g\in H^{n}$
and $g^{\pi_{i}}=1.$ If $n\geq 3$ then $1\neq G_{\beta_{3}}\leq
G_{\gamma_{1}}\cap G_{\gamma_{2}}<G_{\gamma_{1}}$, as $G_{\beta_{2}}\leq
G_{\gamma_{1}}$ and $G_{\beta_{2}}\not\leq G_{\gamma_{2}}$. This contradicts
the fact that $G$ is IBIS and $b(G)=2$. Hence $n=2.$ By Proposition 4.1, the
action of $H$ on $W\setminus\\{0\\}$ is transitive. Moreover, since $H$ is
IBIS and $b(H)=1,$ this action is also regular. So we may identify $W$ with
the additive group of the field $F$ with $r^{k}$ elements, being $r$ a prime,
and $H$ with the multiplicative group of this field. Let $f$ be a non-zero
element of $F$ and $v=(1,f)\in W^{2}.$ Since $b(G)=2,$ we have
$1\neq(t_{1},t_{2})\sigma\in G_{v}$ for some $t_{1},t_{2}\in H,$ with
$\sigma=(1,2).$ This implies $t_{1}=f,$ $t_{2}=f^{-1}$ and therefore
$(f,f^{-1})\sigma\in G.$ But now let $u=(f,f)\in V.$ Again we have
$1\neq(u_{1},u_{2})\sigma^{j}\in G_{u}$ for some $u_{1},u_{2}\in H$ and
$j\in\\{0,1\\}.$ The only possibility is $u_{1}=u_{2}=1$ and $j=1.$ So
$\langle(1,2),(h,h^{-1})\mid h\in H\rangle\subseteq G$. Since $G$ is
nilpotent, $\langle(1,2),(h,h^{-1})\mid h\in H\rangle$ is also nilpotent, and
this implies that $r^{k}-1$ is a 2-power. Finally let $z=(0,1)\in V.$ Again
$G_{z}\neq 1,$ and this is possible only if $(h,1)\in G$ for some $1\neq h\in
H.$ We have so proved that $G$ is as described in Proposition 1.7.

b) $b(H)=2.$ Let $0\neq w\in W$. There exists a nontrivial element $h\in H$
such that $w^{h}=w$. Since $X^{\pi_{1}}=H$, there exist $h_{2},\dots,h_{n}\in
H$ such that $(h,h_{2},\dots,h_{n})\in X$. Assume that $h_{2}=\dots=h_{n}=1$.
Then, as $\langle\sigma\rangle$ acts transitively on $H_{1},\dots,H_{n},$
there exists a nontrivial element $t\in H$ such that $(1,t,1,\dots,1)\in X$.
Take $u\in W$ such that $u^{h}\neq u$ and let
$\beta=(w,0\dots,0),\gamma=(u,0,\dots,0)$. Then $1\neq G_{\beta}\cap
G_{\gamma}<G_{\gamma}$, as $1\neq(1,t,1,\dots,1)\in G_{\beta}\cap G_{\gamma}$
and $(h,1,\dots,1)\in G_{\beta}\setminus G_{\gamma}$. This is in contradiction
with the fact that $G$ is IBIS. Thus there exists $i$ such that $h_{i}\neq 1$.
Let $z\in W$ be such that $z^{h_{i}}\neq z$. Assume that $n\neq 2$. Let
$\delta=(w,z_{2},\dots,z_{n})\in V$, where $z_{i}=z$ and $z_{j}=0$ if $j\neq
i$. Then $G_{\delta}\leq X$. As $G$ is an IBIS group and $b(G)\neq 1,$ we have
that $G_{\delta}\neq 1$. Moreover $1\neq G_{\delta}=X_{\delta}<X_{\beta}$, as
$(h,h_{2},\dots,h_{n})\in X_{\beta}\setminus X_{\delta}$, but this gives again
a contradiction. We have so proved that $n=2$. Moreover, repeating the
argument above, we deduce that $X$ contains no nontrivial elements of the type
$(h,1)$, with $h\in H$. As $X$ is a subdirect product of $H^{2}$, there exists
an automorphism $\alpha$ of $H$ such that $X=\\{(h,h^{\alpha})|\,h\in H\\}$.
Moreover there exists $g=(1,k)\sigma\in G$ and
$\alpha\in\operatorname{Aut}(G)$ such that $G=\\{(h,h^{\alpha})\mid h\in
H\\}\langle g\rangle.$

By Proposition 4.1, $H$ is transitive on $W\setminus\\{0\\},$ and consequently
$H$ is a primitive irreducible subgroup of $\operatorname{GL}(W).$ By [10,
Theorem 2.4] $H$ is as is Proposition 1.6. In particular $W$ can be identified
with the additive subgroup of the field $F$ with $r^{2}$ elements, where $r$
is a Mersenne prime and $H$ can be identified with a subgroup of
$\Gamma=\Gamma(r^{2}).$ Let $0\neq f\in F.$ We have $\Gamma_{f}\cong C_{2}$.
On the other hand, since $b(H)=2,$ $H_{f}\neq 1,$ and therefore
$H_{f}=\Gamma_{f}.$ By the transitivity of $H$ on $F\setminus\\{0\\},$ it
follows $H=\Gamma.$ Suppose that there exists $h\in H$ such that
$hh^{\alpha}k\neq 1$. There exists $0\neq v\in W$ with $hh^{\alpha}k\in
H_{v}.$ Let $w=v^{h}$ and $y=(h,h^{\alpha})(1,k)\sigma.$ Then $y\in G_{(v,w)}$
and $|y|>2.$ In particular $y^{2}=(hh^{\alpha}k,h^{\alpha}kh)\in G_{(v,w)}\cap
G_{(v,0)}.$ Since $G$ is IBIS, we must have $\\{(t,t^{\alpha})\mid t\in
H_{v}\\}=G_{(v,0)}=G_{(v,w)},$ in contradiction with the fact that
$|G_{(v,0)}|=|H_{v}|=2$ and $|G_{(v,w}|\geq|y|>2.$ But then
$h^{\alpha}=(kh)^{-1}$ for any $h\in H.$ This implies $k=1$ and
$h^{\alpha}=h^{-1}$ for every $h\in H$. However this would implies that
$\Gamma=H$ is abelian. This final contradiction implies that the case $b(H)=2$
cannot occur. ∎

##  5\. IBIS primitive permutations groups of odd order

######  Proof of Theorem 1.9.

By [14, Theorem 1.3], $b(G)\leq 2.$ If $b(G)=1,$ then $G$ acts fixed-point-
freely on $V$. So we may assume $b(G)=2.$ This implies that $G_{v}\neq 1$ for
every $0\neq v\in V,$ and if $0\neq v_{1},v_{2},$ then either
$G_{v_{1}}=G_{v_{2}}$ or $G_{v_{1}}\cap G_{v_{2}}=1.$ Assume, by
contradiction, that $G$ is not primitive. Then $G\leq H\wr S_{n},$ with
$H\leq\operatorname{GL}(W)$ and $V\cong W^{n}$ and $n\geq 2.$ Fix $0\neq u\in
W$ and let $\alpha=(u,0,\dots,0).$ For any $2\leq i\leq n$ and $0\neq w\in W,$
let $\beta_{i,w}=(0,\dots,0,w,0,\dots,0)$ and
$\gamma_{i,w}=(u,0,\dots,0,w,0,\dots,0)$ (where $w$ is the entry in the
$i$-position). If $g\in G_{\gamma_{i,w}},$ then $g=(h_{1},\dots,h_{n})\sigma,$
with $\\{1,i\\}\sigma=\\{1,i\\}.$ Since $|G|$ is odd, also $|\sigma|$ is odd.
Thus $1\sigma=1,$ $i\sigma=i$ and consequently $u^{h_{1}}=u,w^{h_{i}}=w$ and
$1\neq G_{\gamma_{i,w}}=G_{\alpha}\cap G_{\beta_{i,w}}.$ Hence
$G_{\alpha}=G_{\beta_{i,w}},$ for any $0\neq w$ and any $i\geq 2.$ But then
there exists $1\neq X\leq H$ such that $G_{\alpha}=\\{(x,1,\dots,1)\mid x\in
X\\}.$ On the other hand $G$ contains an elements $z=(y_{1},\dots,y_{n})\tau$
with $1\tau=2$ and $(G_{\alpha})^{z}=\\{(1,x^{y_{1}},1,\dots,1)\mid x\in
X\\}\leq G_{\alpha},$ a contradiction. Finally, if $G$ is primitive, then it
follows from Theorem 1.2 that $G$ is metacyclic. ∎

To give an example of an IBIS linear group of odd order, choose an odd prime
$r$ and consider the subgroup $G$ of $\Gamma(q^{r})$ generated by $\phi$ and
an element of $N$ of order $(q^{r}-1)/(q-1)$. Then $|G|=r(q^{r}-1)/(q-1)$ is
odd and $G$ is IBIS by Corollary 1.5. Another example can be obtained taking
the subgroup $G:=\langle\phi a^{2},a^{2c}\rangle$ of $\Gamma(7^{9})$ with
$|a|=7^{9}-1$ and $c=1+7+49=57.$ We have that $|G|=3185811$ and $G$ is IBIS by
Theorem 1.3.

###### Proof of Corollary 1.10.

Let $V=\operatorname{soc}(G).$ Then $|V|=n$ and a point-stabilizer
$G_{\omega}$ is an IBIS irreducible subgroup of $\operatorname{GL}(V)$ of odd
order. If $G_{\omega}$ acts fixed-point-freely on $V$, then $G$ is a Frobenius
group. Otherwise, by [14, Theorem 2.12], $G_{\omega}\leq\operatorname{\Gamma
L}(1,n)$ and consequently $G\leq\operatorname{A\Gamma L}(1,n).$ ∎

## References

  * [1] T. C. Burness, R. M. Guralnick, J. Sax, On base sizes for symmetric groups, Bull. London Math. Soc. 43 (2011), 386–391.
  * [2] T. C. Burness, On base sizes for actions of finite classical groups, J. London Math. Soc. 75 (2007), 545–562.
  * [3] T. C. Burness, M. W. Liebeck, A. Shalev, Base sizes for simple groups and a conjecture of Cameron, Proc. London Math. Soc. 98 (2009), 116–162.
  * [4] T. C. Burness, E. A. O’Brien, R. A. Wilson, Base sizes for sporadic simple groups, Israel J. Math. 177 (2010), 307–334.
  * [5] P. J. Cameron, Permutation Groups, London Mathematical Society Student Texts. Cambridge University Press, 1999.
  * [6] P. J. Cameron and D. G. Fon-Der-Flaas, Bases for Permutation Groups and Matroids, Europ. J. Combin. 16 (1995), 537–544.
  * [7] Z. Halasi, K. Podoski, Every coprime linear group admits a base of size two, Trans. Amer. Math. Soc. 368 (2016), no. 8, 5857–5887.
  * [8] D. Holt and Y. Yang, Regular orbits of finite primitive solvable groups, the final classification, J. Symbolic Comput. 116 (2023), 139–145.
  * [9] R. Guralnick, K. Magaard, On the minimal degree of a primitive permutation group, J. Algebra 207 (1998), no. 1, 127–145.
  * [10] B. B. Hargraves, The Existence of Regular Orbits for Nilpotent Groups, J. Algebra 72 (1981), 54–100.
  * [11] M. Lee and P. Spiga, A classification of finite primitive IBIS groups with alternating socle, arXiv:2206.01456
  * [12] A. Lucchini, M. Morigi and M. Moscatiello, Primitive permutation IBIS groups, J. Combin. Theory Ser. A 184 (2021), Paper No. 105516, 17 pp.
  * [13] Y. Yang, A Vasil’ev and E. Vdovin, Regular orbits of finite primitive solvable groups, III. J. Algebra 590 (2022), 139–154.
  * [14] A. Seress, The minimal base size of primitive solvable permutation groups, J. London Math. Soc. (2) 53 (1996), no. 2, 243–255.


# Online voluntary mentoring: Optimising the assignment of students and
mentors

Péter Biró and Márton Gyetvai
Institute of Economics, CERS, and
Corvinus University of Budapest
<EMAIL_ADDRESS>
###### Abstract

After the closure of the schools in Hungary from March 2020 due to the
pandemic, many students were left at home with no or not enough parental help
for studying, and in the meantime some people had more free time and
willingness to help others in need during the lockdown. In this paper we
describe the optimisation aspects of a joint NGO project for allocating
voluntary mentors to students using a web-based coordination mechanism. The
goal of the project has been to form optimal pairs and study groups by taking
into the preferences and the constraints of the participants. In this paper we
present the optimisation concept, and the integer programming techniques used
for solving the allocation problems. Furthermore, we conducted computation
simulations on real and generated data for evaluate the performance of this
dynamic matching scheme under different parameter settings.

Keywords: assignment, resource allocation, matching under preferences, integer
programming computational simulation.

##  1 Introduction

In Hungary, after the escalation of the COVID-19 virus, the government
announced the closure of all schools on 13 March 2020 (Friday evening) with
effect from 16 March, and they requested all the schools (both primary and
secondary schools for students at ages between 6 and 18) to start
online/distance education immediately. There was no central recommendation
about the technology and methodology used, so this was decided mainly by the
board of each school using a wide range of online platforms (e.g. Google
Classroom, MS Teams, etc) or just sending the weekly assignments by post.

A large number of students had difficulties to follow the distance education,
partly because of the lack of equipment or internet connection, but also
because the parents were not be able to help them at home, due to their lack
of knowledge in special subjects or just because of being at work (e.g.,
including those parents working intensively in health care). At the same time,
many people, especially the elderly ones had to stay at home with spare time.
Furthermore, in Hungary there is also a scheme for secondary school students
for voluntary work, which they can get credit for (that counts extra points at
the centralised university admission), and very few possibilities remained for
such services under the strict social distancing rules imposed. Therefore,
there was both a large need for mentoring, and also a significant amount of
potential mentors, both elderly and young.

A project was proposed in early April and then officially started with the
opening of a web-application (onkentesmentoralas.hu) in early May in a
cooperation of three parties. On behalf of the Institute of Economics of CERS,
the Mechanism Design and the Education Economics research groups offered their
help in designing a mechanism for allocating students to mentors. The
Hungarian Reformat Church Aid is a humanitarian organisation, which had a link
to a governmental action group devoted to coordinate the voluntary help in
Hungary. The third party in the project was #school, a private company
providing an online teaching platform, that became used by 100k registered
users soon after the online education started. The latter two parties have had
a related collaboration in the past, where they organised the mentoring of
highly disadvantaged children.

The design approach was rather complex, taking into account the preferences of
both sides, and also allowing the formation of study groups, besides the
mentor-student pairs. The basic requirement of creating a pair is to have a
subject (e.g. Math at year 7) that is both requested by a student and offered
by a mentor. However, the students can request several subjects listing them
according to their preferences and whether they are willing to study in groups
or only in pairs. The mentors can specify their preferences over the subjects
they offer to teach, whether they are willing to supervise groups (or only
individuals), and they can also set preferences over some characteristics of
the students, such as their age, their performance level in that subject
measured by their grades, and their social status (i.e. whether the mentor
prefer to teach highly disadvantaged students).

In the optimisation we carefully considered several potential goals and we
implemented a combination of them, such as maximising the number of students
matched, the overall volume of the teaching hours, the preferences of both the
students and mentors, and the coherence of the study groups. After
implementing our approach we conducted matching runs on a week from early May
until the end of the academic year, that is mid-June in Hungary.

The first period of this application was very short, and we had an
unexpectedly high number of mentors volunteered, but also an unexpectedly low
number of students registered. Therefore the allocation problem was rather
straightforward. Nevertheless, we used the data from this early period to
generate instances that are realistic, and we present the simulations
conducted on that data in this paper.

The pandemic situation has became critical again in Hungary by October due to
the second wave of infections, so on 6 November 2020 all the secondary schools
and universities have been closed again, and thus we open again our allocation
service to link volunteering mentors with students in need.

The pandemic situation has been similar around the world, and especially
critical since April in the USA, an early report on the American schools’
responses to COVID-19 can be found in [21].

In this paper we describe the optimisation aspects of our aforementioned joint
NGO project of allocating voluntary mentors to students with presenting also
computational simulations on realistic instances. We believe that this paper
provides an interesting case study with an advanced OR solution that could be
used everywhere in the world to help allocating the volunteers to people in
need in an efficient and fair way.

###  1.1 Related literature

Matching problems under preferences in two-sided matching markets have been
widely studied both in mathematics, computer science and economics, see e.g. a
recent book on the algorithmic aspects of this topic by Manlove [24]. Beside
the theoretical studies, practical applications have been designed and
implemented in many areas, see a recent survey on this [9].

When both sides of the application have preferences, then the concept of
stable matchings was proposed in the seminal paper of Gale and Shapley [18]
and has been used since in many applications, such as resident allocation,
college admission and school choice. However, there can be some special
features that can make the stable matching problem computationally hard to
solve. In this case one robust approach to tackle these problems is (mixed)
integer linear programming, that has been used recently for the
hospital–resident problem with couples [11], ties [22, 17], college admissions
with lower and common quotas [4], and stable project allocation under
distributional constraints [5]. In this paper we also use MILP technique for
solving the underlying optimisation problem.

There are also many application, where preference of one or both sides do
matter, but the solution is not necessarily stable or fair in some sense, but
rather optimal. Examples are the allocation of papers to reviewers [19],
course allocation [15], or arranged marriages [16]. Scheduling problems are
also closely related, see a paper linking the two lines of researches [12].

In our application of allocating mentors to students we can observe a dynamic
nature, so the literature on online matching is also related. Natural
applications for online matching with preferences are deceased organ
allocation [25], [3], allocation in social housing [23], [14], electric
vehicle charging [20], or lending decisions [28].

There are also applications, which are dynamic in nature, but instead of
online matching protocols, batch allocations are also used. An important
example is refugee allocation, where preferences of one or both sides may be
taken into account, together with some objective goals of maximising the
likelihood of successful settlement of the refugee families, see [29], [6],
[8]. Similar approaches are used in the allocation of foodbanks [26].

Finally, an important example for an application where optimisation is used
for the allocation are the kidney exchange programmes (KEPs), where kidney
patients with incompatible donors may exchange their willing donor among
themselves. Seminal work on IP models for KEP’s is presented in [1] and [27],
a recent survey is [7], and the European optimisation practices are summarised
in [13]. It is interesting to note that online matching is used in the US,
partly because of the competition in between multiple national programmes [2].
However, in Europe the national programmes use batch allocations, by
conducting the matching runs in 3-4 months regular intervals [10].

###  1.2 Our contributions

We describe the allocation mechanism that we designed with our partners and
implemented in the applications. The design is complex, it takes into account
the preferences of both sides, and also some objective factors. The main
novelty and challenge in our solution concept is that besides mentor-student
pairs we also seek to form study groups, that makes the underlying
optimisation problem more elaborate.

Our main theoretical contribution is an IP formulation that accommodates all
the complex constraints and objectives of our model.

These results are complemented by computational experiments, where the
generation of the instances is based on the real data that we collected in the
first period of the application. In our simulation we analyse the effect of
some optimisation policy decisions with regard to various performance
measures. We also test the effects of having shorter or longer matching
periods, and the possibility of giving priority based on the waiting time. The
results of the simulation have been used to refine the design and optimisation
policy of the application.

##  2 Preliminaries

When describing the formal model, first we give a general description, then we
specify the variables for the solution, and finally we describe the input data
for the preferences, priorities and further objective factors.

### General description

We have a set of students $A=\\{a_{1},a_{2},\dots,a_{k}\\}$, mentors
$B=\\{b_{1},b_{2},\dots,b_{l}\\}$, and subjects
$S=\\{s_{1},s_{2},\dots,s_{m}\\}$, the latter being specified with the year as
well (e.g., year 10 - Chemistry). We would like to form pairs (each consisting
of one student and one mentor) and groups (each consisting of a set of
students and one mentor) so that the online mentoring is conducted in these
pairs and groups in weekly periods. For every pair and group formed we also
specify the subjects that they are going to study and the amount of time that
they are supposed to spend with each subject during a week.

As the input of the problem the students give the list of subjects that they
need mentoring in a preference order, specifying also the amount of time they
wish to spend with a mentor per week (integer number between 1 and 3) for each
subject. So a student may ask 2 hours of mentoring in Maths and 1 hour in
Physics with higher preference for the former. The students can give
information on why they need mentoring (e.g., being a child of a single mother
who works in a hospital as a nurse), and about their objective circumstances
with regard to their social background, such as the number of children/parent
at home, etc, that can result in additional priority for them. Furthermore,
they also provide information on the class they attend and whether they have
ongoing online education from that subject, if they are weak, medium or good
students (by giving their final grade in the last semester), and whether they
are willing to accept mentoring in groups or only in pairs. Finally, we ask
what equipment they have at home (PC, tablet, smartphone).

Regarding the mentors, we ask in which subjects they are willing to mentor
students (including the years), and whether they have preference over the
subjects, and some characteristic of the students, such as their age, how
strong the students are in the subject, and their social status (some mentors
can be especially keen to teach socially disadvantaged or weak-performing
students, some might not). We ask the total number of hours that they wish to
spend with mentoring per week and whether they are willing to do mentoring in
groups.

The organisers of this project decided that some of the above mentioned
priorities will only apply for such mentors that express their agreement. For
instance, every mentor can tell whether she wishes to teach highly
disadvantaged students, and if they say no then no priority is given for those
students when considering to allocate them to this mentor. However, if the
mentor states that she would be happy to teach highly disadvantaged students
then a high weight is added. If the mentor is ignorant about this aspect, then
a small weight is added for this priority factor. The same applies for the
criterion whether the student is a weak student with low grades from the last
semester. If a mentor expresses that she does not want to teach weak students
then no priority is given for these pairs, but if she wishes to teach weak
students then extra weight is given. Thus we take the preferences of the
mentors into accounts for some of these controversial priorities, but for some
others, e.g., number of children/parents in the family, we always give an
extra priority. In this way the pairs and group resulted are more likely to be
mutually satisfying.

### Notations: basic elements of the solution

As the basic building block of the optimisation model we have the set of
possible paired mentoring activities $E$, where each _activity_ $e$ consists
of a triple $e=(a_{i},b_{j},s_{k})$. Activity $e$ is possible if student
$a_{i}$ requested subject $s_{k}$ and mentor $b_{j}$ also offered $s_{k}$.

Let $S(a_{i})$ and $S(b_{j})$ denote the set of requested subjects by student
$a_{i}$ and offered subjects by mentor $b_{j}$, respectively. Furthermore,
student $a_{i}$ requested $q(a_{i},s_{k})$ hours per week in subject $s_{k}$
and mentor $b_{j}$ offered $Q(b_{j})$ hours per week in total. We write that
$(a_{i},s_{k})\in e$ if there is $b_{j}\in B$ such that
$e=(a_{i},b_{j},s_{k})$, and similarly, we write that $(b_{j},s_{k})\in e$ if
there is $a_{i}\in A$ such that $e=(a_{i},b_{j},s_{k})$.

In the description of a solution, let $x_{e}$ denote the amount of hours
scheduled for activity $e$ in a pair, and let $y_{e}$ be a binary variable
denoting whether activity $e$ is performed in a pair, i.e. $y_{e}=1\iff
x_{e}>0$. In our practical application we restrict
$x_{e}\in\\{0,1,2,3\\}$.111One can consider to set these variables to be
continuous in the interval $[0,3]$. However, because of the study groups, we
might get fractional values in an optimal solution, which is not allowed in
practice. Let $P$ denote the set of pairs formed, i.e., $P=\\{e\in
E:y_{e}=1\\}$.

Besides pairs, we also allow the formation of groups, whose final set in the
solution will be denoted by $G$. Each _group_ $g\in G$ consists of a triple
$g=(A^{g},b_{j},s_{k})$, where $A^{g}\subset A$ is the subset of students
involved in group $g$ with mentor $b_{j}$ and subject $s_{k}$. Here $x_{g}$
denotes the amount of time scheduled for group $g$, $x_{g}\in\\{2,3\\}$, if
$g$ is formed. (Note that $x_{g}$ is not a variable in our MILP model, we use
that only to describe our solution.)

In our model and application, for simplicity, we assume that every mentor can
have at most five groups to supervise in a subject. Thus, for every mentor
$b_{j}$ who is willing to teach groups in subject $s_{k}$, we create five
_potential groups_ $g_{j}^{k,1}$, $g_{j}^{k,2}$, $\dots$, $g_{j}^{k,5}$ with
capacity $c_{j}^{k}$ each. We introduce a binary variable $y_{j}^{k,t}$ to
denote whether the potential group $g_{j}^{k,t}$ is realised, in which case
there are at least two and at most $c_{j}^{k}$ students involved. Let
$x_{j}^{k,t}$ denote the number of hours allocated for its weekly operation,
where $x_{j}^{k,t}\in\\{0,2,3\\}$. Note that $y_{j}^{k,t}$ and $x_{j}^{k,t}$
are the variables of our mixed integer programming formulation.

For every activity $e=(a_{i},b_{j},s_{k})$, we create a binary indicator
variable $y_{e}^{t}$ denoting whether this mentoring activity is performed in
potential group $q_{j}^{k,t}$. Therefore the set of students involved in this
group will be $A^{g}=\\{a_{i}\in A:e=(a_{i},b_{j},s_{k}),y_{e}^{t}=1\\}$. The
following formula summarises the feasibility condition for realising potential
group $q_{j}^{k,t}$.

$y_{j}^{k,t}=1\iff 2\leq\sum_{e:(b_{j},s_{k})\in e}y_{e}^{t}\leq c_{j}^{k}$

For example, a potential group $g_{j}^{k,1}$ for mentor $b_{j}$ can be on
7-year Maths ($s_{k}$) for at most 5 students ($c_{j}^{k}=5$). If this group
is realised ($y_{j}^{k,1}=1$), a mentoring group $g=(A^{g},b_{j},s_{k})$ will
be formed where $2\leq|A^{g}|\leq 5$ with $x_{g}=x_{j}^{k,1}$ hours per week.

Regarding the personal mentoring hours in a group, as students in a group may
have different requests, we estimate the actual mentoring hours by variable
$x_{e}^{t}$, where we assume that $x_{e}^{t}\leq q_{j}^{k,t}$ and
$x_{e}^{t}\leq q(a_{i},s_{k})$, where $e=(a_{i},b_{j},s_{k})$.

### Preferences, priorities and further objective factors

Here we describe the input more formally listing the information provided by
the users with regard to their attributes and preferences.

#### Students’ attributes and preferences

For every student $a_{i}$, we collect the following attributes and
preferences:

  * •

$year_{i}\in\\{1,2,\dots 12\\}$: which year of study she attends.

  * •

$class_{i}$: exact class she attends in the school (text).

  * •

$PA_{i}$: preference list consisting of the subjects she requested mentoring
(e.g., Math, Physics, History). Let $rank_{i}(s_{k})$ denote the rank of
$s_{k}$ in $PA_{i}$ for $s_{k}\in S(a_{i})$.

  * •

$RA_{i}$: number of requested hours for each requested subjects in the order
of preferences. Note that in our LP model $q(a_{i},s_{k})$ denotes this
constant for each subject $s_{k}\in S(a_{i})$.

  * •

$grades_{i}$: her grades from the last semester in the subjects requested, let
$gr(a_{i},s_{k})$ denote the grade of $a_{i}$ in subject $s_{k}$, that is a
value in between 1 and 5 in Hungary (5 being the best, and 1 meaning Failed).

  * •

$group_{i}\in\\{0,1\\}$: the value is 1 if $a_{i}$ is willing to accept
mentoring in groups.

  * •

$equipment_{i}\in\\{0,1\\}$: the value is 0 if she has a smartphone or tablet
and the value is 1 is she (also) has a laptop.

  * •

$help_{i}\in\\{0,1,2\\}$: self-reported neediness, whether $a_{i}$ has help at
home (0= yes, 1= limited, 2= no)

When forming the groups, the similarities between the students can be
important, therefore for those students willing to get mentoring in groups we
define the following values for each pair of students $a_{i}$ and
$a_{i^{\prime}}$.

  * •

$sc_{i,i^{\prime}}$: the value is 1 if they attend the very same class and 0
otherwise.

  * •

$dr_{i,i^{\prime}}^{k}=|q(a_{i},s_{k})-q(a_{i^{\prime}},s_{k})|$: the
difference between the requested amounts of time in subject $s_{k}$.

  * •

$dg_{i,i^{\prime}}^{k}=|gr(a_{i},s_{k})-gr(a_{i^{\prime}},s_{k})|$: the
difference between their last year’s grades in subject $s_{k}$.

  * •

$de_{i,i^{\prime}}=|equipment_{i}-equipment_{i^{\prime}}|$: this value is 0 if
they have the same equipment and 1 if they have different ones.

Furthermore, for those students wishing to get priority, we also ask question
about her social background and circumstances, based on which we award the
following scores for student $a_{i}$.

  * •

$SD_{i}\in\\{0,1,2,3\\}$: a measure showing how socially disadvantaged is the
student (3 being the maximum value).

  * •

$NH_{i}$: an index for not enough help at home with a value between 0.5 and
2.5 showing how many children are for one parent at home. Thus its value is a
half-integer between 0.5 and 2.5.

  * •

$WS_{i}\in\\{0,1,2,3\\}$: showing how weak is the student based on her grades
and repeated years.

  * •

$CY_{i}\in\\{0,1,2\\}$: how critical the year is for the student, i.e, for
last year of studies $=2$, and for one before the last year $=1$.

#### Mentors’ preferences

Here we describe what preferences the mentors provide on the subjects and
students.

  * •

$PM_{j}$: preference list of $b_{j}$ on the subjects she offers for mentoring
(e.g., Math, Physics, History). Let $rank_{j}(s_{k})$ denote the rank of
$s_{k}$ in $PM_{j}$ for $s_{k}\in S(b_{j})$. Note that this may be set
differently for the three different age-categories, years 1-4, 5-8, 9-12.

  * •

$YM_{j}\in\\{0,1,2\\}$: most preferred age of the student for $b_{j}$ (0= Year
1-4, 1= Year 5-8, 2= Year 9-12).

  * •

$DM_{j}\in\\{0,1,3\\}$: whether $b_{j}$ is willing to mentor socially
disadvantaged students (0= rather not, 1= does not matter, 3= would be very
keen).

  * •

$GPM_{j}$: grade-preference, $=N$ if no preference is given, $=W$ for weak,
$=M$ for medium, and $=S$ for strong students. From this information, we
create the following constants: $PM_{j}=0$ if $GPM_{j}=N$ and $PM_{j}=1$ if
$GPM_{j}\neq N$; $SM_{j}=0$ if $GPM_{J}\in\\{M,S\\}$, $SM_{j}=1$ if
$GPM_{J}=N$ and $SM_{j}=3$ if $GPM_{J}=W$; finally $WM_{j}=0$ if $GPM_{J}=N$,
$WM_{j}=1.5$ if $GPM_{J}=W$, $WM_{j}=3$ if $GPM_{J}=M$, and $WM_{j}=4.5$ if
$GPM_{J}=S$. Here, $PM_{j}$ is an indicator whether $b_{j}$ has grade-
preferences; $SM_{j}$ show how willing $b_{j}$ is to mentor a weak student;
finally, $WM_{j}$ is the best average grade of the student according to
$b_{j}$’s preference.

##  3 Optimisation with MILP technique

In this section we show how we can formulate our problem as a mixed integer
linear program.

First we describe the basic constraints for the feasibility of a solution. We
summarise the feasibility requirements as follows.

Feasibility constraints:

  1. 1.

Only use mutually acceptable paired mentoring activities in the solution
(i.e., the subject should be requested by the student and offered by the
mentor linked).

  2. 2.

Only those mentors can have groups and only those students can be assigned to
groups who expressed their willingness to teach or study in groups,
respectively.

  3. 3.

Have at least two and at most a limited number ($c_{j}^{k}$) of students in
each group.

  4. 4.

We obey the weekly capacities of the mentors.

  5. 5.

The mentoring hours of a pair in a subject should not exceed the requested
amount by the student, and never be more than 3. The mentoring hours per week
for an active group is either 2 or 3.

  6. 6.

Every student can be mentored by at most one mentor in each subject that she
requested.

The first two conditions are automatically satisfied, since we only work with
mentoring activities, where the subjects are mutually acceptable by both
parties (i.e., requested by students and offered by mentors). Similarly, we
only create potential groups for those mentors who are willing to teach in
groups and we only have variables $y_{e}^{t}$ and $x_{e}^{t}$ for those
students who are willing to study in group.

Regarding the pairs, the connection between $x_{e}$ and $y_{e}$ can be
established with the following formula.

$y_{e}\leq x_{e}\leq 3\cdot y_{e}\mbox{ for every }e\in E$ (1)

A similar formula is added for each potential group, but with the minimum
number of hours being 2.

$2\cdot y_{j}^{k,t}\leq x_{j}^{k,t}\leq 3\cdot y_{j}^{k,t}\mbox{ for every
}b_{j}\in B,s_{k}\in S(b_{j}),t\in\\{1,2,3\\}$ (2)

For the realisation of potential groups, we set the following conditions.

$2\cdot y_{j}^{k,t}\leq\sum_{e:(b_{j},s_{k})\in e}y_{e}^{t}\leq c_{j}^{k}\cdot
y_{j}^{k,t}$ (3)

Every activity can be used either in a pair or in a group:

$y_{e}+\sum_{t}y_{e}^{t}\leq 1\mbox{ for every }e\in E$ (4)

The above constraint is also enforced by the more general requirement that
every student can have at most one mentor in each subject:

$\sum_{e:(a_{i},s_{k})\in e}\left(y_{e}+\sum_{t}y_{e}^{t}\right)\leq 1\mbox{
for every }s_{k}\in S(a_{i}),a_{i}\in A$ (5)

For later usage in the objective function, we introduce some new variables
$\beta_{i}^{k}$ indicating whether student $a_{i}$ is involved in mentoring
activity in subject $s_{k}$ and $\gamma_{i}$ indicating whether student
$a_{i}$ is involved in any mentoring activity. We link these variables with
the basic variables as follows:

$\beta_{i}^{k}=\sum_{e:(a_{i},s_{k})\in
e}\left(y_{e}+\sum_{t}y_{e}^{t}\right)\mbox{ for every }s_{k}\in
S(a_{i}),a_{i}\in A,$

and let

$\gamma_{i}\leq\sum_{s_{k}\in S(a_{i})}\beta_{i}^{k}\leq
M\cdot\gamma_{i}\mbox{ for every }a_{i}\in A,$

where $M$ is a large enough number, e.g., the number of subjects any student
can possibly request mentoring (5 in our case).

The weekly capacity of the mentors should not be exceeded:

$\sum_{s_{k}\in S(b_{j})}\left(\sum_{e:(b_{j},s_{k})\in
e}x_{e}+\sum_{t=\\{1,\dots,5\\}}x_{j}^{k,t}\right)\leq Q(b_{j})\mbox{ for
every }b_{j}\in B$ (6)

The mentoring hours of a pair in a subject should not exceed the requested
amount by the student:

$x_{e}\leq q(a_{i},s_{k})\mbox{ for every }e\in E,(a_{i},s_{k})\in e$ (7)

When computing the volume of a solution, for groups we assume that the actual
mentoring hours for a student ($x_{e}^{t}$) is upper bounded by her original
request in this subject, and by the number of mentoring hours of the group.
This can be formalised with the following constraints

$x_{e}^{t}\leq q(a_{i},s_{k})\mbox{ for every }e\in E,(a_{i},s_{k})\in
e,t=\\{1,\dots,5\\}$ (8)

$x_{e}^{t}\leq x_{j}^{k,t}\mbox{ for every }e\in E,(a_{i},s_{k})\in
e,t=\\{1,\dots,5\\}$ (9)

Now, we turn our attention to the objectives.

### Possible objectives

  1. 1.

Maximising the number of students getting a mentor.

  2. 2.

Maximising the number of pairs and groups realised with different weights for
pairs and groups.

  3. 3.

Maximising the number of mentoring hours realised with different weights for
pairs and groups.

  4. 4.

Satisfying the preferences of the students and mentors as well with regard to
the subjects.

  5. 5.

When forming groups, we improve cohesion if we have students a) from the same
class, b) with the same type of equipment, c) their former grades being as
close as possible, and d) the number of scheduled hours for the group to be
close to what the assigned students requested in that subject.

  6. 6.

Giving priority to certain students in needs (depending on the preferences of
the mentors for some criteria, such as social status and student past
performance).

  7. 7.

When the same mentor-student pair can be involved in paired mentoring
activities in multiple subjects then this is preferable.

We note that additionally one might wish to consider the genders of the
mentor-student pairs, or whether they live in the same city, geographic area,
or maybe if they attend the same school in the case of student mentors.

Let $w^{g}$ denote the discount for a mentoring activity being realised in a
group, as opposed to a pair. In our default setting, we use $w^{g}=0.7$, which
means that each mentoring hour in a group counts 0.7 hour in a pair. This is a
crucial parameter, since it highly affects the share of groups in the final
solution.

Now we explain the rational behind each of the above listed objectives and we
formulate the corresponding linear terms for the objective function of the
linear program. The relative weights of these terms in the objective function
were up to the expert choices by the organisers of this application. Note that
the relative weights sum up to 100, so they can be interpreted as percentages
showing the importance of the objective criteria.

  1. 1.

Number of students allocated. Allocating mentors to as many students as
possible.
_Rational pros:_ We would like to involve as many students as possible in the
mentoring, even if for one subject requested.
_Rational cons:_ If this objective is dominating then we would have many
mentoring activities with 1 hour only that can be inefficient for both
students and mentors.
_Relative importance in the application:_ 0 (i.e., this criterion was decided
not to be considered as objective, only monitored)
_Linear term:_ With the usage of variables $\gamma_{i}$, we can simply express
this objective as follows.

$\sum_{a_{i}\in A}\gamma_{i}$

  2. 2.

Number of pairs and groups created. Maximising the number of pairs and groups
realised with different weights for pairs and groups.
_Rational pros:_ We would like to create as many pairs and groups as possible,
to create the links between the parties.
_Rational cons:_ If this objective is dominating then we would have many
mentoring activities with 1 hour only for pairs and 2 hours for groups that
can be inefficient for both students and mentors.
_Relative importance in the application:_ 0 (i.e., this criterion was decided
not to be considered as objective, only monitored)
_Linear term:_ Similar to the formula for $\beta_{i}$, we express this
objective as follows.

$\sum_{e\in E}\left(y_{e}+\sum_{t}w^{g}\cdot y_{e}^{t}\right)$

  3. 3.

Volume. Maximising the number of mentoring hours realised with different
weights for pairs and groups.
_Rational pros:_ The number of mentoring hours is the most important measure.
_Rational cons:_ The solution might be unbalanced, some students may get many
hours while some others may get none.
_Relative importance in the application:_ 50
_Linear term:_ Similar to the previous formula we now use the hours rather
than the indicator variables, resulting in the volume of the solution.

$\sum_{e\in E}\left(x_{e}+\sum_{t}w^{g}\cdot x_{e}^{t}\right)$

As the volume will be the main objective in our optimisation, we will set the
relative weights for each mentoring activity accordingly. Let $w_{e}$ denote
the final weight of activity $e$ in a pair and let denote $w_{e}^{g}$ is the
final weight of an activity in a group. We suppose that $w_{e}^{g}=w_{e}\cdot
w^{g}=w_{e}\cdot 0.7$ in our case. The final weight $w_{e}$ will be a sum of
weights with respect to different objectives. The first objective is the
volume, that we weighted 50 for all activities, so let $w_{e}^{w}=50$ for
every activity $e$.

  4. 4.

Preferences. Satisfying the preferences of the students with regard to the
subjects, and the preferences of the mentors on the subjects and on the ages
of students.
_Rational:_ The higher the need of the student for a subject the more
important for her to get help, and the preference of the mentor should also be
taken into account for the subject and the age of the student supervised.
_Relative importance in the application:_ 10
_Linear term:_ Each activity $e=(a_{i},b_{j},s_{k})$ will get an additional
weight according to the preferences of the students and mentors as follows,
that we denote by $w_{e}^{p}$. Let
$w_{e}^{p}=(6-rank_{i}(s_{k}))+(6-rank_{j}(s_{k}))+3*agepref_{i}^{j}$, where
each of the first two terms gives a value between 1 to 5, depending on how
preferable this subject is for the student/mentor, and the last term gives 3
if the age of the student is preferred by the mentor (among years 1-4, 5-8, or
9-13).

  5. 5.

When forming groups, we shall preferably have students from the same class,
with the same type of equipment, have their former grades as close as
possible, and have the number of scheduled hours to be close to what the
assigned students requested in that subject.
_Rational:_ Two students from the very same class are favorable to be put into
the same mentoring group, as they receive the same distance education from
their home school. Forming groups for students with similar strength can
improve the efficiency of mentoring. Finally, the requested hours by the
students in a group should be close to the scheduled hours. Regarding the
equipment, if one student in a group has a laptop and another only a tablet or
smartphone then the possible interactions can be limited between them and the
mentor (we consider tablets and smartphones to be equally useful).
_Relative importance in the application:_ 15
_Linear term:_ For any two students $a_{i}$ and $a_{i^{\prime}}$ who are both
willing to accept mentoring let us introduce a binary variable
$z_{i,i^{\prime}}^{p}$ for every potential group $p=(b_{j},s_{k},t)$, where
both $a_{i}$ and $a_{i^{\prime}}$ could belong to, i.e., if there exist
$e=(a_{i},b_{j},s_{k})$ and $e^{\prime}=(a_{i^{\prime}},b_{j},s_{k})$ The
indicator variable $z_{i,i^{\prime}}^{p}=1$ if both $a_{i}$ and
$a_{i^{\prime}}$ are assigned to $p$ in the solution. This can be achieved
with the following new constraints.

$z_{i,i^{\prime}}^{p}\geq y_{e}^{t}+y_{e^{\prime}}^{t}-1\mbox{ for every
}p=(b_{j},s_{k},t),e=(a_{i},b_{j},s_{k}),e^{\prime}=(a_{i^{\prime}},b_{j},s_{k})$
(10)

$z_{i,i^{\prime}}^{p}\leq y_{e}^{t}\mbox{ for every
}p=(b_{j},s_{k},t),e=(a_{i},b_{j},s_{k})$ (11)

$z_{i,i^{\prime}}^{p}\leq y_{e^{\prime}}^{t}\mbox{ for every
}p=(b_{j},s_{k},t),e^{\prime}=(a_{i^{\prime}},b_{j},s_{k})$ (12)

Furthermore let $z_{i,i^{\prime}}^{k}=\sum_{p:s_{k}\in
p}z_{i,i^{\prime}}^{p}$, where $z_{i,i^{\prime}}^{k}$ is the indicator
variable showing whether $a_{i}$ and $a_{i^{\prime}}$ are in the same group
for subject $s_{k}$.

The accumulated weight of group coherence criteria is

$GC(z)=\sum_{a_{i},a_{i^{\prime}}\in A}\sum_{s_{k}\in S}(10\cdot
sc_{i,i^{\prime}}-2\cdot
de_{i,i^{\prime}}-dg_{i,i^{\prime}}^{k}-dr_{i,i^{\prime}}^{k})\cdot
z_{i,i^{\prime}}^{k}$

  6. 6.

Giving priority to certain students in needs (depending on the preferences of
the mentors for some criteria, such as social status and student past
performance).
_Rational:_ Social welfare can improve if the students in need receive the
mentors. However, the criteria of being socially disadvantaged or being a weak
student can be controversial for some mentors, so we allow them to express
their willingness to get paired with such students.
_Relative importance in the application:_ 20
_Implementation with weights:_

The combined social priority weight of $e=(a_{i},b_{j},s_{k})$, denoted by
$w_{e}^{s}$, is as follows:

$w_{e}^{s}=3\cdot SD_{i}\cdot DM_{j}+WS_{i}\cdot
SM_{j}+(1.5-|gr(a_{i},s_{k})-WM_{j}|)\cdot PM_{j}+2\cdot
CY_{i}+(NH_{i}+help_{i})$

  7. 7.

When the same mentor-student pair can be involved in paired mentoring
activities in multiple subjects then this is preferable.
_Rational:_ It can be useful if not too many different mentors supervise the
same student.
_Relative importance in the application:_ 5
_Linear term:_ We introduce a new binary variable $m_{i}^{j}$ to denote
whether $a_{i}$ is mentored by $b_{j}$ in any subject in a pair with the
following constraints.

$m_{i}^{j}\leq\sum_{e:(a_{i},b_{j})\in e}y_{e}\leq 5\cdot m_{i}^{j}$ (13)

We shall minimise the number of mentoring pairs with a weight $w^{m}$, that is
let

$MP(y)=w^{m}\sum_{i,j}m_{i}^{j}$

where we set $w^{m}=5$ in our application.

### Final objective function

For $w_{e}=w_{e}^{w}+w_{e}^{p}+w_{e}^{s}$ (and $w_{e}^{g}=w_{e}\cdot w^{g})$,
the final objective function is:

$\sum_{e\in E}w_{e}\cdot x_{e}+\sum_{t}w_{e}^{g}\cdot x_{e}^{t}+GC(z)-MP(y)$
(14)

To summarise, the main objective is to maximise the volume of the mentoring
activities with considering the preferences and the social priorities of the
students, improving the group cohesion, and decreasing the number of mentors
per students.

##  4 Simulations: data generation

During the first operating time of the allocation scheme (1 May to 15 June
2020), the number of students who registered at the webpage was 14, while the
number of mentors was 56. Because of the low number of student’s registration,
we could not observe the true potential of the model and application.
Therefore we decided to conduct computational experiments on partly generated
data.

Because of the low amount of observations, the main goal of our simulation was
to test our MILP model, rather than to give accurate prediction on the
performance of the scheme. However, we still tried to use the data available
to get as realistic generated data as possible.

We computed the correlations amongst the mentor variables, but, we only found
weak correlations. Hence we generated the variables independently, by rolling
a biased dice independently for each variable and observation (student and
mentor). We used the available data to estimate these biases. In this section,
we describe the way we generated each variable.

###  4.1 Students

  * •

School-ratio: There were 14 students registered, out from 9 different schools.
Therefore in the simulator, we considered the student-school ratio to at most
67%. So when we considered 100 students, we generated 67 schools, and for each
student, we selected a school with replacement.

  * •

Number of subjects: The average number of subjects requested per student was
2, with four as maximum. We used the following distribution for the amount of
subjects: (1: 50 %; 2: 30 %; 3: 10%; 4: 10%).

  * •

Time ($q(a_{i};s_{k})$): The average time required by the students for
mentoring per week in a subject was around 2 hours with a minimum of 1 and
maximum of 4. We used the distribution of (1: 33%; 2: 33%; 3: 25%; 4: 9%).

  * •

Grades: For the distribution of grades, we got almost every possibility from
the data, except grade 1, which means Failed in Hungary. In the simulation, we
generated all types of grades uniformly with the addition of 0, where 0 means
the student left the bracket blank (which was 25% of the real cases).

  * •

Group: 9 out of 14 students selected the possibility of getting mentoring in
groups. Hence we set $\frac{2}{3}$ for the probability of a student accepting
group-mentoring.

  * •

Help: For the three possible values we received 5-5-4 responses, respectively.
Therefore, we decided to generate these values randomly with equal
probability.

  * •

Equipment: All of the participants chose 0. We left this parameter out in the
simulation because it is not crucial for the optimisation model.

  * •

Year: Most of the registered students were from years 4-8 (92%), only one
student was in year 11. Since the programme started at the end of the spring
semester and after the matriculation exam, we assume that the secondary school
students were underrepresented in the application. Therefore we generated the
students’ years uniformly from year 4 to 12.

  * •

Prior1 ($SD_{i}$): 13 students out of 14 chose option 0, and the last
remaining student chose option 1. Therefore we generated higher ration of
underprivileged students by using the (0: 65%; 1: 20%; 2: 10%; 3: 5%)
distribution for this variable.

  * •

Prior2 ($NH_{i}$): In the generator, we used the result of a 2016 census of
the Hungarian Central Statistical Office
(http://www.ksh.hu/thm/2/indi2_1_4.html?lang=hu) to generate the data.
According to this census the ratio of the single-parent family is $18.3\%$.
For the number of children, we generated the data according to the table 1
(for the 4 or more we considered simply 4).

Number of children | probability
---|---
1 | 69.2%
2 | 23.9%
3 | 5.2%
4 or more | 1.7%
Table 1: Families by number of children,
(http://www.ksh.hu/thm/2/indi2_1_4.html?lang=hu)

Therefore, for each student, we generated the number of parents and the number
of siblings independently, according to the above described statistics.

  * •

Prior3 ($WS_{i}$): In the real data, $64\%$ of the students had 0 points,
$28\%$ had two and only one student had 3 points (no student got 1 point for
this variable). We approximated the values of this variable with the Poisson
distribution, where we set the expected value equal to the mean of the real
data ($0.786$).

  * •

Prior4 ($CY_{i}$): This point depends directly on the year of the student, so
it is computed accordingly.

  * •

Matriculation: This depends on the year of the student. Therefore we only
considered this variable when the student was from year 11 or 12. Most
students officially take the matriculation exam in year 12 in Hungary,
however, there is an option to advance some exams to previous years. Hence we
randomised this value for the students from year 11, by assuming that 40% of
them do not want to practice for the matriculation exams (so they got the
”N”-letter, meaning no matriculation), 40% going for the base exam and 20% of
them selecting advanced exam.

###  4.2 Mentors

When we generated the characteristics of the mentors, we used the
distributions taken from the real data. Since 56 mentors registered into the
program, we have not made as many assumptions as in the case of the students.

  * •

Group: 54% of the mentors agreed to the possibility of mentoring in groups.

  * •

Time ($Q(b_{j})$): For the time capacity of the mentors, first we generated
ranges with a distribution, and then we choose uniformly the exact value from
the range selected. The time-range of a mentor was 1-3 hours with 40%
probability, 4-6 hours with 40% probability, and 7-10 hours with 20%
probability.

  * •

Social ($DM_{j}$): We used the (0: 50%; 1: 40%; 3: 10%) distribution,
reflecting the real data.

  * •

Weak ($GPM_{j}$): Here 85% of the mentors chose option N, therefore we also
used 85% for generating option N and 5% for each the other three options.

  * •

Student-Age ($YM_{j}$): We used the (0: 5%; 1: 20%; 2: 15%; N: 60% (no
preference given)) distribution, reflecting the real data.

###  4.3 Subjects

Overall, there were 15 different subjects offered for selection. We generated
the distribution of the requested subjects according to the distribution of
the subjects offered by the mentors. The assumption behind this is that the
demands and the supply of the subjects shall be balanced in the long run.
However, we also added a random noise to modify the distribution for every
instance.

Not all of the subjects are for each year. Therefore the distributions are
normalised for each year with regard to the subjects available. A student can
request mentoring in multiple subjects. According to the data, the maximum
number of subjects requested was 4 with an average of two. As we already
described, we used the (1= 50%, 2 = 30%, 3= 10%, 4 = 10%) distribution to
generate the number of subjects requested by each student, and then with the
consideration of the student’s year, we picked the subjects randomly with a
distribution that is close to distribution of the subjects offered by the
mentors.

The mentors can also have multiple classes. In the data, the average number of
subjects per mentor was 2.9. However, the maximum number of the subjects was 9
for some mentors. Therefore some extreme values have increased the average a
lot. We generated the number of subjects of each mentor with respect to their
total time offered. If the mentor’s total time was less than 4 hours then we
generated 1-3 subjects uniformly. If the total time was less than or equal to
6, then we generated 1-4 subjects uniformly. Finally, in the case of time at
least 7, we generated 1-5 subjects. Whenever we allocated a subject to a
mentor, we assumed that the mentor is willing to teach students of all age in
this subject.

###  4.4 Comparison of generated and real data

To compare the simulated data to the real data, we generated 1000 instances
with the same amount of mentors (56) and students (14) as in the real data.
Then we checked whether the values of the real data are within the
interquartile range of the values of the generated data.

Regarding the evaluation measures, only the Social-points were not inside this
range with any type of objective value. This is reasonable since in the real
data, we have not received enough values (see, for example, Prior 1 and 2).
Therefore we adjusted the distributions. Hence the generated data got in
average higher results than in reality.

Also, when we considered the group-weight of 1 in the objective function,
several other measures were also outside the interquartile range. The reason
behind this instability is the few numbers of students in the real data.

##  5 Simulations: single run

In this section first we describe how we simplified the evaluation measures by
clustering them based on one-shot simulations, and then we also present the
performance analyses with regard to some basic parameters.

###  5.1 Generation of instances

For the basic setting we generated 100 large instances with 80 students and 40
mentors in each, and we conducted a single match run for each of them. This
setup differs from the real data, since the student/mentor ratio is much
higher in the generated data. Our aim was to analyse the effect of using
different objective functions when the programme has an ideal student/mentor
ratio.

Then we adjusted the main parameters to create alternative solutions, as
follows.

#### Alternative parameters

  * •

we modify $w^{g}$ from 0.7 to 0.5, 0.6, 0.8, 0.9, 1

  * •

for $w^{g}=0.7$ we modified the preference based weights from the default
setting of a)
$w_{e}^{p}=(6-rank_{i}(s_{k}))+(6-rank_{j}(s_{k}))+3*agepref_{i}^{j}$
to b)
$w_{e}^{p}=(6-rank_{i}(s_{k}))^{2}+(6-rank_{j}(s_{k}))+3*agepref_{i}^{j}$,
and to c)
$w_{e}^{p}=(6-rank_{i}(s_{k}))^{2}+(6-rank_{j}(s_{k}))^{2}+3*agepref_{i}^{j}$

Thus we generated five times 100 instances by varying $w^{g}$ and another two
times 100 instances by changing the preference based weights. So altogether we
considered 800 instances. The run time for solving the MILP model for these
instances was relatively short, the average run time was 167 seconds with a
maximum of 3 hours and 12 minutes.

###  5.2 Clustering the evaluation measures

Besides the seven objectives given in Section 3, we considered the following
five performance measures in the evaluation of solutions.

#### Evaluation measures

  1. 1.

Number of paired mentoring hours and group mentoring hours separately.

  2. 2.

Number of pairs and number of groups separately.

  3. 3.

Total capacity of the mentors used.

We analysed how the above described five evaluation measures behave together
with the seven different objective functions, that we presented earlier.
However, for the evaluation of the different objective functions, we decided
to reduce the dimension of the twelve measures. So, we calculated the
similarities between the various measures with hierarchical clustering. All of
the results were considered in the estimation. Figure 1 presents the
dendrogram of the measures.

Figure 1: The dendrogram of the measures. The measures are described in
section 3
Number_students: Objective 1 Number_Pairs_Groups: Objective 2; Volume:
Objective 3; Preference: Objective 4; Group_connection: Objective 5; Social:
Objective 6; Mentor_pairs: Objective 7; Solo_time/Group_time: Evaluation
measure 1; Solo_number/Group_number: Evaluation measure 2; Mentor_capacity:
Evaluation measure 3;

We decided to reduce the dimension of the 12 measures to 6 (as the red
rectangles show in Figure 1). We chose the six dimensions, because according
to Principal component analysis, with 6 component 96% of the total information
can be saved. Additional component only increased the saved information with
less than 2%.

According to the hierarchical clustering, we evaluated the Number_students,
Preference and Social measures independently from the other measures.

From the Mentor_capacity, Solo_time, Mentor_pairs and Solo_number measures
with using Factor analysis method, we created a factor variable. We covered
84% of the total information in this factor. We named this factor as _solo-
factor_ because it is related to the measures of the non-group classes. For
every measure a higher value increase the accumulated factor score.
Interestingly the number of Mentor-student pairs (Objective 7) has a behavior
very similar to the solo-class time and number.

We created another factor for the measures of Group_connection, Group_time,
and the Group_number. We named this factor as _Group-factor_. We could cover
73% of the total information inside one factor. Higher Group_connection value
decreases the Group-factor’s score, while for the other two measures higher
value will increase it.

Finally, from the Number_Pairs_Groups and Volume we created the so-called
_Quantity-factor_. For all of these measures higher values increase the
factor’s score. We could cover 81% information within this factor.

Figure 2: The distribution of the 3 factors and the Number of students,
Preference and the Social measures.

###  5.3 Analyses of one-shot simulations

Figure 2 presents the distributions of the three factors as well as the Number
of students, Social and Preference scores of the different objective
functions.

On the graphs of the Solo-factor and Group-factor, the influence of group-
weight ($w^{g}=WG$) is clearly visible. As the group-weight increases, the
Solo-score decreases and the Group-score increases. The two quadratic-
preference models had very similar results in these cases compared to the
original WG_0.7 model, although there was a small decrease in the group-score.

The Quantity factor’s score increases with the group-weight. Therefore if the
number of pairs and groups, or the volume is more important in the
optimisation, then the usage of higher group-weights seems to be more
appropriate.

Group-weight also increases a bit the number of matched students. However, the
best solution for this measure is when the preference of the students was
considered quadratically.

Naturally the Preference measure is very high for the two quadratic preference
cases. However, it seems that the group-weight parameter did not have any
effect on this measure.

Social points appear to be very stable, the group-weight does not have much
effect on the social aspect of the programme. However, the quadratic
preference cases have a slightly worse result for this measure.

##  6 Simulations: dynamic allocation

We investigated also how the frequency of the matching runs affects the
results in a dynamic setting. We considered the first 300 days of the
programme, by generating a registration date for each student and mentor. We
assumed that both the students and mentors joined the application uniformly
random in the period considered. We also generated a leaving day for each
applicant as follows. Presumably, if a student does not get any mentor within
a reasonable time in this programme, then he or she may well seek mentors
using other channels. We assumed that the students stay in this programme for
an average of two weeks, with two days of standard deviation with the
assumption of the normal distribution (but they remain at least seven days).
The mentors may also leave a programme if they do not get any student soon
enough after registration, however, we assumed that they are be more patient
than the students. Hence they leave the programme 3 weeks after registration
in average (with a minimum of two weeks). Again we used normal distribution
with setting two days for the standard deviation.

We also extended the stay of those students and mentors, who got matched. For
any student, who was in a solution of a matching run, we added seven more days
to their leaving time. We extended the staying time of the matched mentors
with 14 days. Figure 3 presents the flow of a matching run.

Figure 3: Flow of a matching run

First, we set up the pool of students and mentors of a matching run. A pool of
students consists of those students who have already registered into the
programme, but have not left it yet and have demand for some subject. The pool
of the mentors are those who have time for teaching, and already registered
but have not left the pool yet.

Then we calculate the optimal matching according to the policy setting and we
remove the satisfied subject from the list of the demanded subjects of each
selected student. For the allocated mentors, we decrease their total time
offered for teaching with the allocated time.

Then we increase the remaining time of stay of the allocated students and
mentors, with 7 and 14 days, respectively.

We considered four different frequencies for the matching-runs: 1, 2, 7 and 14
days. We evaluated 100 generated instances according to these four
frequencies. In the optimisation model, we considered the Final objective
function (14) with the default group-weight $w^{g}=0.7$.

Since we had no access to the registration dates and duration of stays of the
students and mentors, we generated two different set of instances with regard
to the frequency of the arrivals. We considered instances where 1 and 4 were
the average number of students joining the programme per day. Therefore, for
an instance of type 1, we generated 300 students, and for an instance of type
4, we generated 1200 students for the period of 300 days. The students
register into the programme uniformly at random, hence 1 and 4 students
register daily on average, respectively.

In each case, we assumed that the mentors arrive half as frequently as the
students. Hence in instances of type 1, one mentor arrives in every two days,
in instance of type 4, two mentors are expected to join the programme every
day in average.

Figure 4 presents the solo-groups formed in different examples.

Figure 4: The formed solo-groups

In both cases, more frequent runs resulted in more solo classes. Between the 1
and 2 daily runs, the difference is not large, however as the matching runs
became less frequent, the difference is visible. Figure 5 presents the results
of the number of groups formed.

Figure 5: The formed groups

In both cases, less frequent runs resulted in more groups. Therefore
independently from the sizes of the matching problems, more frequent runs were
better with respect to paired-mentoring, and less frequent runs were better
for forming more groups.

How about the qualities of the solutions of each frequency? In the previous
figures, we focused on the number of pairs and groups. For the quality of
matchings, first we considered the Social aspect of the programme. Figure 6
presents the sum of the Social points in each type of matching runs.

Figure 6: The sum of social scores in each example

The Social score did not depend on the frequency of the matching runs that
much when in average one student registers per day. A small decrease is
noticeable as runs become less frequent in this case.

However, when the average number of daily student registration is four, then
the trend changes. The reason behind the change of trend is the higher number
of groups.

Figure 7: Volume

Figure 7 presents the volumes of optimal solutions. With fewer students,
forming a group is more complicated. Hence more frequent runs have better
social points, because of the solo-groups. With a larger pool, more groups can
be formed, therefore we see an increase in the Volume, as well as in the
Social score.

###  6.1 Consideration of the waiting-time

As in other dynamic allocation systems with bounded length duration of stays
(e.g., organ allocation) one may try to improve the solutions with a
prioritisation based of _waiting times_.

In the following part we investigate how the results change if we prioritise
those students and mentors, who registered earlier to the programme. It may
decrease the social-scores and the preference-scores of the matchings, but
there may be less early quits from the programme and also less unmatched
participants.

Therefore we modified the weight of the activities, to
$w_{e}=w_{e}^{w}+w_{e}^{p}+w_{e}^{s}+w_{e}^{t}$, where

$w_{e}^{t}=WT\bigg{(}(t^{r}-t^{0}_{i})+(t^{r}-t^{0}_{j})\bigg{)}\quad(a_{i},b_{j})\in
e$ (15)

Here $t^{r}$ denotes the day of the matching run, $t^{0}_{i}$ is the
registration date of the student $a_{i}$ and $t^{0}_{j}$ is the registration
date of the mentor $b_{j}$. We also use a weight for the days passed, that we
denote by $WT$.

To test how the prioritisation by waiting time changes the solutions, we
considered a 300 days period again with an average of three students
registering into the programme in every day. We set 0,1,2 and 10 for the
weight of the waiting time priority regarding all the match-frequencies that
we investigated earlier.

Figure 8 presents the Solo-groups’ and groups’ distributions of the results.

Figure 8: The Solo and Group results with 0,1,2,10 weight on the waiting time

With the increase in the weight of the waiting time priority, the number of
pairs increased, but the number of groups decreased. We can observe a similar
trend for each match-frequency, hence giving priority for the waiting time is
good for forming more pairs.

However, overall, we can notice a small decrease in the Volume, as Figure 9
presents. For WT=1 and 2 this reduction is negligible, but for WT=10 it is
significant. Thus giving priority by the waiting time, we loose more mentoring
time with the decreased number of groups than what we gain with more pairs.

The same figure presents the change in the number of students as well. In
every run-frequency, a higher WT resulted in a decrease in the number of
students allocated.

Figure 9: The Volume and Number of students results with 0,1,2,10 weight on
the waiting time

Figure 10 presents the Preference and Social scores. In both cases, higher WT
resulted in a relapse. It is connected to the decrease in Volume since fewer
mentoring hours in general means worse Preference and Social scores.

Figure 10: The Preference and Social results with 0,1,2,10 weight on the
waiting time

Hence the prioritisation by the waiting time increase only the number of pairs
and decrease many other aspects of the programme. The setback in these values
is caused by the multiple demands and offers. For example, a student may have
two different subjects requested. If there is a match for her first subject
then she remains in the programme with her second remaining subject with an
extended duration of stay, and so in a later run she may well receive a mentor
for her second subject as well due to her increased priority instead of
allocating a freshly registered student for her first subject. In fact, the
freshly registered student can even have higher Social score, or other scores
can also be better for her, but the high waiting time priority for the
aforementioned student overrules these scores. Thus the freshly registered
student may not even get a mentor, whilst the earlier matched student will get
multiple mentors. Therefore there is a setback in both match quality and
somewhat also in quantity.

To reduce the setback, caused by the multiple demands and offers by the
members, we also investigated how the solution would change, if we only
consider the extra priority on the waiting time for the first preferred
subjects of the students. Figure 11 presents the results of these models, with
the same setups as earlier.

Figure 11: The results with weights 0,1,2,10 for the waiting time regarding
the first preferred subjects only

In the pairs and groups, the effect was similar to the earlier investigated
case. The weight on the waiting time of the first subject also increased the
number of pairs and decreased the number of groups. However, the change is
noticeably smaller. Therefore the Volume appears to be more stable, but still
has a slight reduction as the WT increases. However, the trend in the number
of students changed. In this case, a higher weight on the waiting time of the
first subject increased the number of students matched. Because each student
has one subject with this weight, those students who have not been selected
yet has a higher chance to get matched than before.

Regarding the preferences, we can notice a small increase when the runs occur
in every day or in every two days. However, the score decreases when the runs
happen less frequently. The reason behind the change in the trend is maybe
because of the reduction in the number of groups. In general, more frequent
runs resulted in more pairs and fewer number of groups. The weights for the
waiting time also increased the number of pairs and reduced the possibility to
form a group. More pairs with higher preferences increased the preference
score, but having fewer groups decreased it.

The Social score decreased for every run frequency as we increased the WT.
However, the effect is much smaller compared to the case when every subject
was weighted.

##  7 Conclusion

In this paper we have described the optimisation aspect of a joint NGO project
for allocating voluntary mentors to students. By taking the participants’
preferences into account we aimed to create desirable pairs and study groups
by using integer programming techniques for solving the dynamic allocation
problem in the real application and also for generated data. We believe that
the lessons learned can be useful for other countries and for similar
applications.

As a future work we are going to conduct a follow-up analyses on the data that
we are now gathering in the Hungarian application since the latest lockdown
for secondary schools in the 2020/2021 winter and spring period.

## Acknowledgement

We thank our colleagues, Dániel Horn and Zoltán Hermann for helping designing
the application on behalf of our Institute, Dávid Burka and his company for
developing the website of the application (onkentesmentoralas.hu), and our
collaborators in the two partner organisations, the Hungarian Reformat Church
Aid and #school. Biró and Gyetvai are supported by the Hungarian Scientific
Research Fund – OTKA (no. K129086).

## References

  * [1] David J. Abraham, Avrim Blum, and Tuomas Sandholm.  Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges.  In Proceedings of the 8th ACM Conference on Electronic Commerce, EC ’07, pages 295–304, New York, NY, USA, 2007. ACM.
  * [2] Nikhil Agarwal, Itai Ashlagi, Eduardo Azevedo, Clayton R Featherstone, and Ömer Karaduman.  Market failure in kidney exchange.  American Economic Review, 109(11):4026–70, 2019.
  * [3] Nikhil Agarwal, Itai Ashlagi, M Rees, P Somaini, and D Waldinger.  Equilibrium allocations under alternative waitlist designs: Evidence from deceased donor kidneys.  Econometrica, forthcoming, 2020.
  * [4] Kolos Csaba Ágoston, Péter Biró, and Iain McBride.  Integer programming methods for special college admissions problems.  Journal of Combinatorial Optimization, 32(4):1371–1399, 2016.
  * [5] Kolos Csaba Ágoston, Péter Biró, and Richárd Szántó.  Stable project allocation under distributional constraints.  Operations Research Perspectives, 5:59–68, 2018.
  * [6] Tommy Andersson, Lars Ehlers, and Alessandro Martinello.  Dynamic refugee matching.  2018\.
  * [7] Itai Ashlagi and Alvin E Roth.  Kidney exchange: an operations perspective.  Working paper, 2020.
  * [8] Kirk Bansak, Jeremy Ferwerda, Jens Hainmueller, Andrea Dillon, Dominik Hangartner, Duncan Lawrence, and Jeremy Weinstein.  Improving refugee integration through data-driven algorithmic assignment.  Science, 359(6373):325–329, 2018.
  * [9] Péter Biró.  Applications of matching models under preferences.  2017\.
  * [10] Péter Biró, Bernadette Haase-Kromwijk, Joris van de Klundert, and et al.  Building kidney exchange programmes in Europe – an overview of exchange practice and activities.  Transplantation, 103(7):1514–1522, 2019a.
  * [11] Péter Biró, David F Manlove, and Iain McBride.  The hospitals/residents problem with couples: Complexity and integer programming models.  In International Symposium on Experimental Algorithms, pages 10–21. Springer, 2014.
  * [12] Péter Biró and Eric McDermid.  Matching with sizes (or scheduling with processing set restrictions).  Discrete Applied Mathematics, 164:61–67, 2014.
  * [13] Péter Biró, Joris van de Klundert, David Manlove, William Pettersson, Tommy Andersson, Lisa Burnapp, Pavel Chromy, Pablo Delgado, Piotr Dworczak, Bernadette Haase, Aline Hemke, Rachel Johnson, Xenia Klimentova, Dirk Kuypers, Alessandro Nanni Costa, Bart Smeulders, Frits Spieksma, María O. Valentín, and Ana Viana.  Modelling and optimisation in european kidney exchange programmes.  European Journal of Operational Research, 2019b.
  * [14] Francis Bloch, David Cantala, and Damián Gibaja.  Matching through institutions.  Games and Economic Behavior, 2020.
  * [15] Eric Budish, Gérard P Cachon, Judd B Kessler, and Abraham Othman.  Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation.  Operations Research, 65(2):314–336, 2017.
  * [16] Nguyen Vi Cao, Emmanuel Fragniere, Jacques-Antoine Gauthier, Marlene Sapin, and Eric D Widmer.  Optimizing the marriage market: An application of the linear assignment model.  European Journal of Operational Research, 202(2):547–553, 2010\.
  * [17] Maxence Delorme, Sergio García, Jacek Gondzio, Jörg Kalcsics, David Manlove, and William Pettersson.  Mathematical models for stable matching problems with ties and incomplete lists.  European Journal of Operational Research, 277(2):426–441, 2019\.
  * [18] David Gale and Lloyd S Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [19] Naveen Garg, Telikepalli Kavitha, Amit Kumar, Kurt Mehlhorn, and Julián Mestre.  Assigning papers to referees.  Algorithmica, 58(1):119–136, 2010.
  * [20] Enrico Gerding, Alvaro Perez-Diaz, Haris Aziz, Serge Gaspers, Antonia Marcu, Nicholas Mattei, and Toby Walsh.  Fair online allocation of perishable goods and its application to electric vehicle charging.  2019\.
  * [21] Douglas N Harris, Lihan Liu, Daniel Oliver, Cathy Balfe, Sara Slaughter, and Nicholas Mattei.  How america’s schools responded to the covid crisis.  National Center for Research on Education Access and Choice & Education Research Alliance for New Orleans. https://educationresearchalliancenola. org/files/publications/20200713-Technical-Report-Harris-etal-How-Americas-Schools-Responded-to-the-COVID-Crisis. pdf, 2020.
  * [22] Augustine Kwanashie and David F Manlove.  An integer programming approach to the hospitals/residents problem with ties.  In Operations Research Proceedings 2013, pages 263–269. Springer, 2014.
  * [23] Jacob Leshno.  Dynamic matching in overloaded waiting lists.  Available at SSRN 2967011, 2019.
  * [24] David Manlove.  Algorithmics of matching under preferences, volume 2.  World Scientific, 2013.
  * [25] Nicholas Mattei, Abdallah Saffidine, and Toby Walsh.  Fairness in deceased organ matching.  In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 236–242, 2018.
  * [26] Canice Prendergast.  The allocation of food to food banks.  EAI Endorsed Trans. Serious Games, 3(10):e4, 2016.
  * [27] Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver.  Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences.  American Economic Review, 97(3):828–851, June 2007.
  * [28] Mee Chi So, Lyn C Thomas, and Bo Huang.  Lending decisions with limits on capital available: The polygamous marriage problem.  European Journal of Operational Research, 249(2):407–416, 2016\.
  * [29] Andrew C Trapp, Alexander Teytelboym, Alessandro Martinello, Tommy Andersson, Narges Ahani, et al.  Placement optimization in refugee resettlement.  Technical report, 2018.