fancyproblem[2][]

#2
---

# Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items
under a Common Preference Graph

Nina Chiarelli  FAMNIT, University of Primorska, Koper, Slovenia  IAM,
University of Primorska, Koper, Slovenia  Clément Dallard  Department of
Informatics, University of Fribourg, Fribourg, Switzerland  Andreas Darmann
Department of Operations and Information Systems, University of Graz, Austria
Stefan Lendl  Department of Operations and Information Systems, University of
Graz, Austria  Martin Milanič  FAMNIT, University of Primorska, Koper,
Slovenia  IAM, University of Primorska, Koper, Slovenia  Peter Muršič  FAMNIT,
University of Primorska, Koper, Slovenia  Ulrich Pferschy  Department of
Operations and Information Systems, University of Graz, Austria

###### Abstract

We consider the task of allocating indivisible items to agents, when the
agents’ preferences over the items are identical. The preferences are captured
by means of a directed acyclic graph, with vertices representing items and an
edge $(a,b)$, meaning that each of the agents prefers item $a$ over item $b$.
The dissatisfaction of an agent is measured by the number of items that the
agent does not receive and for which it also does not receive any more
preferred item. The aim is to allocate the items to the agents in a fair way,
i.e., to minimize the maximum dissatisfaction among the agents. We study the
status of computational complexity of that problem and establish the following
dichotomy: the problem is NP-hard for the case of at least three agents, even
on fairly restricted graphs, but polynomially solvable for two agents. We also
provide several polynomial-time results with respect to different underlying
graph structures, such as graphs of width at most two and tree-like structures
such as stars and matchings. These findings are complemented with fixed
parameter tractability results related to path modules and independent set
modules. Techniques employed in the paper include bottleneck assignment
problem, greedy algorithm, dynamic programming, maximum network flow, and
integer linear programming.

Keywords: fair division, partial order, preference graph, dissatisfaction,
polynomial time algorithm, computational complexity

MSC (2020): 91B32, 90C27, 90C47, 68Q25, 05C85, 05C20, 68Q27 90B10 06A06

##  1 Introduction

Partitioning resources or allocating indivisible items to a set of agents is a
widely studied research topic in Operations Research and in particular in
discrete optimization (see, e.g., [2, 9, 41, 29, 16]). In many scenarios
agents can voice their preferences over the set of available items.
Frequently, this is done by assigning a profit value to every item. Under the
commonly applied additivity assumption (e.g., [32, 38]), the total utility or
gain that an agent obtains from a certain subset of items is simply given by
the sum of the corresponding profit values.

However, it is often pointed out that individuals would be overwhelmed with
choosing meaningful numerical values for a larger set of items (cf. [1, 5]).
Moreover, cardinal evaluations entail certain drawbacks compared to ordinal
evaluations as widely discussed in theoretical economics, see, e.g., [25].
Instead, it would be easier to ask agents for pairwise comparisons and the
resulting orders as in [3]. For highly heterogenous items a total order may
also be hard to find since certain items could well be incomparable to each
other. Thus, one often settles for partial orders to represent preferences of
agents. It is also fairly natural to consider agents discussing their opinions
of items, in particular if these are not so well known, and reaching a
consensus valuation expressed by means of a common preference graph. The
setting of agents expressing common, i.e., identical, preferences has been
considered in the literature on fair division of indivisible items in several
works, including the ones by Bouveret and Lang [10], Brams and Fishburn [11],
and Freeman et al. [20].

In this contribution we consider a set of $k$ agents denoted by
$K=\\{1,\ldots,k\\}$ and a set $V$ of $n$ items. The aforementioned preference
structure of the considered problem is described by a single preference graph,
i.e., a directed acyclic graph $G$. This is the crucial difference of the
current contribution from its predecessor paper [15], where each agent had its
own preference graph. Every item is identified with a vertex of $G$. An arc
$(a,b)$ in $G$ means item $a$ is preferred over item $b$. Assuming
transitivity of the preferences, arcs $(a,b)$ and $(b,c)$ imply that the
agents also prefer item $a$ over item $c$, regardless of whether the arc
$(a,c)$ is contained in the graph or not. Obviously, $G$ induces a partial
order over the set of items.

The allocation of items is performed by a central decision maker who assigns
every item to at most one agent. Now a crucial question arises: What is the
happiness or satisfaction of an agent receiving a certain subset of items
under the given partial preference order?

We will consider a new measure for expressing the _dissatisfaction_ of an
agent with its allocated subset of items which was recently introduced in our
earlier work [15]. The underlying rationale states that an item received makes
all lesser ranked items irrelevant. However, an item not assigned to a certain
agent causes dissatisfaction if this agent does not receive any other more
preferred item. The overall dissatisfaction of an agent is therefore given by
the total number of items causing dissatisfaction.

The global goal, then, would be a fair allocation. In that respect, in order
to evaluate the quality of an allocation, we take into account a very natural
and basic fairness criterion: we aim at making the worst-off agent as good as
possible, i.e., our problem CG Min-Max Dissatisfaction (see Section 2 for a
precise definition) deals with minimizing the maximum dissatisfaction value of
an agent for a common preference graph. Thus, in principle, we are concerned
with maximizing egalitarian social welfare on the basis of the agents’
preferences as considered, e.g., by Bezáková and Dani [7], Baumeister et al.
[6], and Roos and Rothe [40]. Egalitarian social welfare as a fairness measure
has a long-standing tradition (see Rawls [39]), and has been applied in
various settings (see, e.g., Golovin [24], Kawase and Sumita [28], Darmann et
al. [17] and Nguyen et al. [36]).

From a graph theoretic perspective, an allocation for an agent $i\in K$ is
evaluated by the number of vertices in $G=(V,A)$ which are dominated by the
allocated items, i.e., items which can be reached from an allocated vertex by
a directed path in $G$. The total number of these dominated items, together
with the allocated items, can be seen as the satisfaction level of agent $i$.
Obviously, for each agent satisfaction and dissatisfaction add up to the
number of vertices in $G$.

###  1.1 Our contribution

In Section 3, we prove NP-hardness of CG Min-Max Dissatisfaction for any
constant number of agents $k\geq 3$. This hardness result even holds for the
relatively basic class of preference graphs, namely graphs with no directed
path of length two and no vertex of in-degree larger than two. Therewith we
provide a dichotomy for the computational complexity of CG Min-Max
Dissatisfaction with respect to the number of agents, as the problem is
solvable in polynomial time in the case of two agents. Moreover, we show that
in contrast to the above-mentioned hardness result for graphs of “height” two,
CG Min-Max Dissatisfaction can be solved in polynomial time in graphs of width
at most two, for any number of agents involved.

Turning to tree-like structures (Section 4), we then show that CG Min-Max
Dissatisfaction is solvable in polynomial time not only for directed matchings
but also, more generally, when the preference graph is a collection of out-
stars. In addition, for a constant number of agents, the polynomial-time
result for out-stars can be generalized to out-forests.

In Section 5, we then provide a fixed parameter tractability (FPT) result for
a bounded number of agents when the preference graph can be decomposed into
path modules and independent set modules. For the case of a decomposing into
independent set modules only, fixed parameter tractability holds for an
arbitrary number of agents.

The algorithms employed in this paper encompass a broad spectrum of classical
ingredients, such as bottleneck assignment problem, greedy algorithm, dynamic
programming, maximum network flow, and integer linear programming.

It should be noted that a generalization from the common preference graph to
the setting where each agent has its own preference graph makes the problem
much harder in terms of computational complexity. As shown in [15], for
individual preference graphs the problem of minimizing the maximum
dissatisfaction can be solved in polynomial time if each preference graph is a
path, as well as for any constant number of agents if the underlying
undirected graph of the union of the preference graphs has bounded treewidth
(see [15, Remark 18] for details). Note that this result implies that for any
constant number of agents, CG Min-Max Dissatisfaction is solvable in
polynomial time if the underlying graph of the preference graph has bounded
treewidth.

On the other hand, it was also shown in [15] that for individual preference
graphs, the problem of minimizing the maximum dissatisfaction remains NP-
complete in each of the following cases:

  1. (1)

for two agents, even if the two sets of items are the same,

  2. (2)

if each preference graph is an out-star,

  3. (3)

if each preference graph is a directed matching, and

  4. (4)

if each preference graph consists of at most two paths containing at most five
items in total.

As a consequence of the results of the present paper, all of these intractable
cases turn out to be solvable in polynomial time in the case of a common
preference graph.

Finally, we point out that the graph classes for which our polynomial-time
results hold cover rather natural and basic ways of expressing preferences.
For practical purposes, these might be easier to state than, e.g., a strict
ranking over all the available items. For instance, a directed matching
represents the situation in which the agents’ preferences are expressed over
disjoint pairs of items only; i.e., the agents prefer, for each $i$, item
$a_{i}$ over $b_{i}$, with no additional preferences stated between the items.
An out-star covers the scenario in which each agent prefers a dedicated item
to several other items, with no further preferences between the remaining
items. And an out-forest, as it is a collection of out-stars, (potentially)
contains several such scenarios.

Some of the results of this paper were included or announced in the
proceedings paper [14].

##  2 Preliminaries

For the sake of consistency, definitions and notation mostly follow those from
[15]. We consider graphs that are finite and do not contain loops or multiple
edges. For brevity, we often say graph when referring to a directed graph.
When undirected graphs are used, this will be explicitly stated.

Consider a directed graph $G=(V,A)$ with $n:=|V|$. For $a=(u,v)\in A$, vertex
$u$ is called the _tail_ of $a$ and vertex $v$ is the _head_ of $a$. The in-
degree of a vertex $u$ is the number of arcs in $A$ for which $u$ is the head
and the out-degree of $u$ is the number of arcs in $A$ for which $u$ is the
tail. The degree of a vertex $u$ is the number of arcs in $A$ for which $u$ is
either head or tail. A vertex with in-degree $0$ is called source. A vertex
with out-degree $0$ is called sink.

A sequence $p=(v_{0},v_{1},v_{2},\ldots,v_{\ell})$ with $\ell\geq 0$ and
$(v_{i},v_{i+1})\in A$ for each $i\in\\{0,\ldots,\ell-1\\}$ is called a walk
of length $\ell$ from $v_{0}$ to $v_{\ell}$; it is a path (of length $\ell$
from $v_{0}$ to $v_{\ell}$) if all its vertices are pairwise distinct. A walk
from $v_{0}$ to $v_{\ell}$ is closed if $v_{0}=v_{\ell}$. A cycle is a closed
walk of positive length in which all vertices are pairwise distinct, except
that $v_{0}=v_{\ell}$.

A directed acyclic graph is a directed graph with no cycle. Observe that in a
directed acyclic graph there is always at least one source and at least one
sink. An out-tree is a directed acyclic graph $G=(V,A)$ with a specified
vertex $r$ (called root) such that for each vertex $v\in V\setminus\\{r\\}$
there is exactly one path from $r$ to $v$. An out-star is an out-tree in which
each such path is of length at most $1$. An out-forest is a disjoint union of
out-trees.

Let $G=(V,A)$ be a directed acyclic graph. An _antichain_ in $G$ is a set of
vertices that are pairwise unreachable from each other. The _width_ of $G$,
denoted by $w(G)$, is the maximum cardinality of an antichain in $G$. A
_chain_ in $G$ is a set $C$ of vertices such that for every two vertices
$x,y\in C$, the graph $G$ contains either an $x,y$-path or a $y,x$-path. A
_chain partition_ of $G$ is a family $\mathcal{C}$ of vertex-disjoint chains
in $G$ such that every vertex of $G$ belongs to precisely one chain in
$\mathcal{C}$.

A directed acyclic graph $G=(V,A)$ induces a binary relation $\succ$ over $V$,
by setting $u\succ v$ if and only if $u\neq v$ and there is a directed path
from $u$ to $v$ in $G$; in such a case, we say that the agents prefer $u$ to
$v$. In particular, the transitive closure of a directed acyclic graph induces
a strict partial order over $V$.

Let ${\it\textnormal{pred}}(v)$ denote the set of predecessors of $v$ in graph
$G$, i.e., the set of all vertices $u\neq v$ such that there is a path from
$u$ to $v$ in $G$. In addition, let ${\it\textnormal{succ}}(v)\subseteq V$
denote the set of successors of $v$ in graph $G$, i.e., the set of all
vertices $u\neq v$ such that there is a path from $v$ to $u$ in $G$. We denote
by $\textnormal{pred}[v]$ the set $\textnormal{pred}(v)\cup\\{v\\}$; similarly
we denote by $\text{succ}[v]$ the set $\text{succ}(v)\cup\\{v\\}$. For $u,v\in
V$ we say that item $u$ is dominated by item $v$ if
$v\in{\textnormal{pred}}[u]$.

For a directed acyclic graph $G=(V,A)$ and a vertex $v\in V$, we denote by
$N^{-}(v)$ the set of all in-neighbors of $v$, formally $N^{-}(v)=\\{u\in
V\colon(u,v)\in A\\}$, and similarly by $N^{+}(v)$ the set of all out-
neighbors of $v$, that is $N^{+}(v)=\\{u\in V\colon(v,u)\in A\\}$.

As stated before, a set of $k$ agents is denoted by $K=\\{1,\ldots,k\\}$. An
allocation $\pi$ is a function $K\rightarrow 2^{V}$ that assigns to the agents
pairwise disjoint sets of items, i.e., for $i,j\in K$, $i\not=j$, we have
$\pi(i)\cap\pi(j)=\emptyset$.

To measure the attractiveness of an allocation we will count the number of
items that an agent does not receive and for which it receives no other more
preferred item. Formally, for an allocation $\pi$ the dissatisfaction
${\delta}_{\pi}(i)$ of agent $i$ is defined as the number of items in $G$ not
dominated by any item in $\pi(i)$. If $\pi$ allocates a vertex $v$ to agent
$i$, it will not change the dissatisfaction ${\delta}_{\pi}(i)$ if any
vertices in $\text{succ}(v)$ are allocated to $i$ in addition to $v$. Thus, we
say that if $v\in\pi(i)$, then agent $i$ dominates all vertices in
$\text{succ}[v]$. It will also be convenient to define the satisfaction
$s_{\pi}(i)$ of agent $i$ with respect to allocation $\pi$ as the number of
items in $V$ that are dominated by $i$.

Continuing the work of [15] we consider the minimization of the maximum
dissatisfaction among the agents. As a decision problem, this task is
formulated as follows.

Min-Max Dissatisfaction with a Common Preference Graph Input: A set $K$ of
agents, a set $V$ of items, a directed acyclic graph $G=(V,A)$, and an integer
$d$. Question: Is there an allocation $\pi$ of items to agents such that the
dissatisfaction ${\delta}_{\pi}(i)$ is at most $d$ for each agent $i\in K$?

We abbreviate the above decision problem as CG Min-Max Dissatisfaction.
Observe that minimizing the maximum dissatisfaction of an agent is equivalent
to maximizing the minimum satisfaction. We will often use this fact in some of
our proofs, without explicitly referring to it. As pointed out in [15] this
equivalence does not hold anymore if each agent has its own preference graph.

By optimal allocation and optimal solution value we refer to the optimization
version of CG Min-Max Dissatisfaction, i.e., the task of actually determining
an allocation that minimizes the maximum dissatisfaction among agents and the
corresponding maximum dissatisfaction value $\delta$. (For the equivalent
problem of maximizing the minimum satisfaction among agents the minimum
satisfaction is $n-\delta$.) For the polynomial-time results in this paper we
provide constructive proofs, i.e., our results also yield that a respective
optimal allocation can be found in polynomial time. It is easy to see that if
there are fewer items than agents, then there must be at least one agent
receiving no item at all and thus reaching the worst possible dissatisfaction
$n=|V|$.

######  Observation 1.

If $k>n$, then CG Min-Max Dissatisfaction has a canonical solution independent
of $G$.

Based on Observation 1 we will asume $k\leq n$ for the remainder of the paper.

A classical theorem of Dilworth states that the width of $G$ equals the
minimum number of chains in a chain partition of $G$ [19]. Moreover, by
applying the approach of Fulkerson [21], a minimum chain partition of $G$ can
be computed efficiently by solving a maximum matching problem in a derived
undirected bipartite graph having $2n$ vertices (see [37]). This can be done
in time $\mathcal{O}(n^{5/2})$ using the algorithm of Hopcroft and Karp [27].

Many of our proofs will make use of the following general lemma on the
solutions to CG Min-Max Dissatisfaction.

######  Lemma 2.

When solving CG Min-Max Dissatisfaction for a preference graph $G$ with $n$
vertices and any set $K$ of $k$ agents such that $k\leq n$, we may without
loss of generality restrict our attention to allocations $\pi$ such that for
each agent $i\in K$, the set of items allocated to agent $i$ forms a nonempty
antichain in $G$.

###### Proof.

If there exists an agent $i\in K$ such that $\pi(i)$ is not an antichain in
$G$, we can simply remove any item allocated to agent $i$ that is dominated by
some other item in $\pi(i)$, without affecting the dissatisfaction of agent
$i$. Repeating this procedure if necessary, we obtain an allocation $\pi$ such
that for each agent $i\in K$, the set of items allocated to agent $i$ forms an
antichain in $G$.

Let us now argue why we may assume that all these antichains are nonempty. For
any allocation $\pi$ in which some agent $i\in K$ receives no items, the
dissatisfaction of this agent is equal to $n$, and hence the maximum
dissatisfaction equals $n$. On the other hand, since $k\leq n$, there exists
an allocation in which every agent receives at least one item. Any such
allocation results in the maximum dissatisfaction at most $n-1$ and is thus
strictly preferred to any allocation assigning no items to some agent. ∎

The classical Linear Sum Assignment problem asks for a perfect matching with
minimum total weight in a bipartite graph, and the Linear Bottleneck
Assignment problem seeks a perfect matching in a weighted bipartite graph such
that the largest weight of a matching edge is as small as possible. Both
problems can be solved in polynomial time (see [12, Sec. 6.2]). For our
purposes we will require an assignment restricted to $k$ matching edges. This
variant was considered in [18] for the sum case (i.e., minimizing the total
weight). Moreover, it is easy to see that the $k$-cardinality restriction can
be obtained by adding $n-k$ dummy vertices to each set of the bipartition.
Without going into details of this exercise we state the result for the min-
max case.

######  Lemma 3 (folklore).

Given a bipartite graph $G=(V=A\sqcup B,E)$ having a perfect matching, an edge
weight function $w:E\to\mathbb{R}_{+}$, and an integer $k\leq|V|/2$, the
following problem can be solved in polynomial time: Compute a matching in $G$
with cardinality $k$ such that the largest weight of a matching edge is as
small as possible.

##  3 General results for CG Min-Max Dissatisfaction

Our first result states that for two agents, CG Min-Max Dissatisfaction can be
solved in polynomial time.

######  Theorem 4.

For $k=2$ and any preference graph $G=(V,A)$, CG Min-Max Dissatisfaction can
be solved in $\mathcal{O}(|V|+|A|)$ time.

###### Proof.

Let $S$ be the set of sources of $G$ (these correspond to items that are not
dominated by any other item). Let $G^{\prime}$ be the graph $G-S$ and let
$S^{\prime}$ be the set of sources of $G^{\prime}$. Furthermore, let $S_{1}$
be any subset of $S$ with cardinality $\left\lfloor\frac{|S|}{2}\right\rfloor$
and $S_{2}=S\setminus S_{1}$. We denote by $S_{1}^{\prime}$ the vertices in
$S^{\prime}$ that are not dominated by any vertex in $S_{1}$, and, similarly,
by $S_{2}^{\prime}$ the vertices in $S^{\prime}$ that are not dominated by any
vertex in $S_{2}$. More formally,
$S_{1}^{\prime}=S^{\prime}\setminus\\{{\it\textnormal{succ}}(v)\colon v\in
S_{1}\\}$ and
$S_{2}^{\prime}=S^{\prime}\setminus\\{{\it\textnormal{succ}}(v)\colon v\in
S_{2}\\}$. The four sets $S_{1}$, $S_{2}$, $S_{1}^{\prime}$, and
$S_{2}^{\prime}$ can be computed in time linear in the size of the graph by a
simple graph traversal. Moreover, we claim that they are pairwise disjoint.
The disjointness of any pair follows immediately from the definitions, except
for $S_{1}^{\prime}$ and $S_{2}^{\prime}$. Suppose for a contradiction that
there exists a vertex $u\in S_{1}^{\prime}\cap S_{2}^{\prime}$. Then $u$
belongs to $S^{\prime}$ and, hence, is a source in $G-S$. Since $u$ is not a
source in $G$, it must have a predecessor $v$ in $G$. Furthermore, since $u$
is a source in $G-S$, vertex $v$ must belong to $S$; in particular, we must
have $v\in S_{i}$ for some $i\in\\{1,2\\}$. However, this implies that
$u\not\in S_{i}^{\prime}$, a contradiction.

Since the sets $S_{1}\cup S_{1}^{\prime}$ and $S_{2}\cup S_{2}^{\prime}$ are
disjoint, setting $\pi(1)=S_{1}\cup S^{\prime}_{1}$ and $\pi(2)=S_{2}\cup
S^{\prime}_{2}$ defines a valid allocation of items to the two agents. The
undominated items for agent $1$ (agent $2$) are exactly the items in $S_{2}$
(in $S_{1}$). Clearly, $\pi$ can be computed in linear time and the
corresponding dissatisfaction of the two agents is
$\delta_{\pi}(1)=|S_{2}|=\left\lceil\frac{|S|}{2}\right\rceil$ and
$\delta_{\pi}(2)=|S_{1}|=\left\lfloor\frac{|S|}{2}\right\rfloor$. To complete
the proof, we show that $\pi$ in fact optimally solves CG Min-Max
Dissatisfaction problems for the given input instance $G^{*}$.

Note that under allocation $\pi$, the dissatisfaction of each agent is at most
$\left\lceil\frac{|S|}{2}\right\rceil$. Since for any allocation $\pi^{*}$ we
have $\delta_{\pi^{*}}(1)+\delta_{\pi^{*}}(2)\geq|S|$ and consequently
$\max\\{\delta_{\pi^{*}}(1),\delta_{\pi^{*}}(2)\\}\geq\left\lceil\frac{|S|}{2}\right\rceil$,
the allocation $\pi$ is indeed optimal for CG Min-Max Dissatisfaction. ∎

The result of Theorem 4 is best possible regarding the number of agents,
unless P = NP. Indeed, we show next that CG Min-Max Dissatisfaction is NP-
complete for $k$ agents for any $k\geq 3$, even if the graph has no directed
path of length two.

######  Theorem 5.

For each $k\geq 3$, CG Min-Max Dissatisfaction is NP-complete. This result
holds even if the preference graph has no directed path of length two and no
vertex of in-degree larger than 2.

###### Proof.

Membership in NP is clear. We provide a reduction from $k$-Colorability, which
is the following decision problem: “Given an undirected graph $H$, is $H$
$k$-colorable?” This problem is well known to be NP-complete for every $k\geq
3$ (Garey et al. [23]). We proceed as follows. Given an instance of the above
problem, we create a directed graph $G$ from $H$ by doing the following for
each edge $e=\\{u,v\\}$ of $H$: delete the edge $e$ and add a new vertex
$w_{e}$ and arcs $(u,w_{e}),(v,w_{e})$. In words, subdivide every edge of $H$
and orient the edges of the so-obtained graph towards the new vertices. Let
the graph $kG$ be made up of $k$ disjoint copies of $G$. Below we show that
$H$ is $k$-colorable if and only if the graph $kG$ admits an allocation for
$k$ agents such that each agent has dissatisfaction of at most
$\textit{diss}:=k|V(G)|-\sum_{v\in V(G)}|\textnormal{succ}[v]|$.

Assume that such an allocation $\pi$ for $kG$ exists. Observe that for each
copy of $G$, the total dissatisfaction (i.e., sum over all agents’
dissatisfaction) of any allocation is _at least_ diss: without being
allocated, each vertex $v\in V(G)$ creates a unit of dissatisfaction for each
agent (hence the term $k|V(G)|$ in diss); if vertex $v$ is allocated to an
agent, the total dissatisfaction value is reduced by at most
$|\textnormal{succ}[v]|$. A reduction by _exactly_ $|\textnormal{succ}[v]|$ is
achieved if none of the successors of $v$ has a predecessor allocated to the
same agent. Summing up over all $v\in V(G)$ yields the lower bound of diss.

By our assumption, allocation $\pi$ yields a total dissatisfaction over all
$k$ agents of at most $k\cdot\textit{diss}$. It follows from above that $kG$
contributes at least $k\cdot\textit{diss}$ to the total dissatisfaction.
Therefore, equality must hold. As indicated above, for such an allocation
$\pi$ with total dissatisfaction exactly $k\cdot\textit{diss}$ it must hold
for every vertex $w_{e}$ arising from an edge $e=\\{u,v\\}$ that $w_{e}$ and
its predecessors $u$ and $v$ are assigned to three different agents. Thus,
identifying colors with agents, a $k$-coloring for $H$ results from $\pi$
restricted to an arbitrary copy of $G$ in the graph $kG$.

Conversely, a $k$-coloring for $H$ can be extended to an allocation for $kG$
as follows. Pick a copy of $G$ in $kG$. In that copy, identify colors with
agents and allocate each vertex of color $h$ to agent $h$. In addition, for
each edge $e\in E(H)$, allocate the item $w_{e}$ to any of the $k-2$ agents
that did not receive an endpoint of $e$. Such an allocation for $G$ has a
total dissatisfaction of $k|V(G)|-\sum_{v\in
V(G)}|\textnormal{succ}[v]|=\textit{diss}$, since no vertex assigned to an
agent $h$ is dominated by another vertex allocated to $h$. The extended
allocation for $kG$ can be obtained by “cycling” the agents in each copy: If a
vertex belongs to agent $i$ in copy $j$ of $G$, then this vertex should belong
to agent $i+\ell\pmod{k}$ in copy $j+\ell\pmod{k}$ of $G$. The total
dissatisfaction in $kG$ is hence $k\cdot\textit{diss}$. Note that every agent
gets the same dissatisfaction due to the cycling, hence the individual
dissatisfaction equals to diss for each agent. This completes the reduction. ∎

In contrast to the intractability results for CG Min-Max Dissatisfaction on
graphs with “height” two as shown by Theorem 5, we now provide an efficient
algorithm for the problem on graphs of _width_ at most two (see Figure 1 for
an example).

Figure 1: Illustration of a graph of width $2$.

######  Theorem 6.

CG Min-Max Dissatisfaction is solvable in polynomial time for any number $k$
of agents if the preference graph $G$ has width at most $2$.

###### Proof.

Let $G=(V,A)$ be a directed acyclic graph of width at most $2$. Let us
associate to $G$ an undirected bipartite graph $\widehat{G}=(\widehat{V},E)$
defined as follows:

  1. 1.

The vertex set of $\widehat{G}$ is $\widehat{V}=V\cup V^{\prime}$ where
$V^{\prime}=\\{v^{\prime}\colon v\in V\\}$ is a set of new vertices.

  2. 2.

There are two types of edges in $\widehat{G}$: edges of the form
$\\{x,y\\}\subseteq V$, where $\\{x,y\\}$ is an antichain in $G$ with size
two, and edges of the form $\\{v,v^{\prime}\\}$, where $v\in V$.

Note that $\widehat{G}$ is bipartite. Indeed, if $G$ has width one, then each
of $V$ and $V^{\prime}$ is an independent set in $\widehat{G}$ and their union
is $\widehat{V}$. If $G$ has width two, then by Dilworth’s theorem there
exists a chain partition $\\{P,Q\\}$ of $G$ with size two, and the sets
$P\cup\\{v^{\prime}\colon v\in Q\\}$ and $Q\cup\\{v^{\prime}\colon v\in P\\}$
are independent sets in $\widehat{G}$ with union $\widehat{V}$. Furthermore,
the edges of the form $\\{v,v^{\prime}\\}$, where $v\in V$, form a perfect
matching in $\widehat{G}$.

We now assign nonnegative weights to the edges of $\widehat{G}$ as follows.
For each edge $e=\\{x,y\\}\subseteq V$ corresponding to an antichain in $G$
with size two, we define the weight to $e$ to be the dissatisfaction of an
agent $i\in K$ under any allocation $\pi$ such that $\pi(i)=\\{x,y\\}$, that
is, the total number of vertices in $G$ that are not reachable by a path from
$\\{x,y\\}$. Similarly, for each edge of the form $\\{v,v^{\prime}\\}$ where
$v\in V$, we define the weight to $e$ to be the dissatisfaction of an agent
$i\in K$ under any allocation $\pi$ such that $\pi(i)=\\{v\\}$, that is, the
total number of vertices in $G$ that are not reachable by a path from $v$.
Clearly, this weight function can be computed in polynomial time given $G$.

When solving the CG Min-Max Dissatisfaction problem for $G$ and $K$, Lemma 2
implies that each agent $i\in K$ will be allocated either only one item or two
items forming an antichain. To each such allocation $\pi$ we can associate a
matching $M_{\pi}$ in $\widehat{G}$ as follows. For each agent $i\in K$
receiving only one item, say $\pi(i)=\\{v\\}$ for some $v\in V$, we include in
$M_{\pi}$ the edge $\\{v,v^{\prime}\\}$. For each agent $i\in K$ receiving
some antichain $\\{x,y\\}\subseteq V$ of size two, i.e., $\pi(i)=\\{x,y\\}$,
we include in $M_{\pi}$ the edge $\\{x,y\\}$. Since the sets of items assigned
to different agents are pairwise disjoint, the obtained set $M_{\pi}$ is
indeed a matching. Furthermore, since for each of the $k$ agents, the set of
items allocated to the agent forms a _nonempty_ antichain in $G$, we can
associate to each agent $i\in K$ a unique edge $e_{i}\in M_{\pi}$; in
particular, $M_{\pi}$ has cardinality $k$. By construction, the weight of the
edge $e_{i}$ equals to the dissatisfaction of agent $i$ with respect to the
allocation $\pi$. Note that the above procedure can be reversed: to any
matching $M=\\{e_{i}\colon i\in K\\}$ of cardinality $k$ in $\widehat{G}$, we
can associate an allocation $\pi_{M}$ of items in $G$ to the $k$ agents such
that the dissatisfaction of agent $i$ under $\pi_{M}$ equals the weight of the
edge $e_{i}$.

It follows that the CG Min-Max Dissatisfaction problem for $G$ and $K$ can be
reduced in polynomial time to the problem of computing a matching in
$\widehat{G}$ with cardinality $k$ such that the maximum weight of a matching
edge is as small as possible. By Lemma 3, this problem can be solved in
polynomial time. ∎

##  4 Polynomially solvable cases on out-forests

Starting with the simplest meaningful case of an out-forest, we consider the
case where $G$ is a directed matching, i.e., a collection of disconnected
edges. It is easy to see that for this case CG Min-Max Dissatisfaction can be
solved by a greedy strategy, even if the number of agents $k$ is unbounded. It
suffices to assign all heads of directed matching edges as equally as possible
to the agents. Then one can iteratively assign tails to agents with lowest
score (avoiding assigning both ends of an edge to the same agent). In this
way, the difference between the dissatisfactions of any two agents can be at
most one. However, we can also extend this approach to the more general
setting of out-stars.

######  Theorem 7.

For any number $k$ of agents, CG Min-Max Dissatisfaction can be solved in
polynomial time if the preference graph $G$ is a collection of out-stars.

###### Proof.

To the input graph $G$ we associate a sorted sequence of integers $a_{1}\geq
a_{2}\geq\dots\geq a_{\ell}\geq 1$ corresponding to the numbers of leaves of
the _nontrivial_ out-stars (that is, out-stars with at least one edge), where
$r_{i}$ is the root of a star with $a_{i}$ leaves, and an integer $a\geq 0$
denoting the number of trivial out-stars consisting of a single vertex. Note
that in the whole proof those are treated as leaves. We show how to solve the
optimization variant of the max-min satisfaction problem, which is equivalent
to CG Min-Max Dissatisfaction. For the case $k=2$ the result follows
immediately from Theorem 4. Let us consider $k\geq 3$.

We start by assigning the roots of the stars using the following greedy
strategy. First, we process the nontrivial stars and assign their roots only.
For each $i\in\\{1,\ldots,\ell\\}$, denoting by $\pi^{\prime}$ the partial
allocation right before assigning the root $r_{i}$, we select a least
satisfied agent $j\in\arg\min\\{s_{\pi^{\prime}}(j)\colon j\in K\\}$ and
extend $\pi^{\prime}$ by assigning root $r_{i}$ to agent $j$. Second, we
distribute the leaves of the stars by applying the same greedy idea as for the
roots, paired with an exchange argument. Consider a least satisfied agent $j$.
If there is still an unassigned leaf of a star that is either trivial or whose
root has not been assigned to $j$, assign such a leaf to $j$. Otherwise, if
all trivial stars (i.e., singletons) are assigned and every unassigned leaf is
adjacent to a root assigned to $j$, then, as we will show below, there exists
an agent $h\neq j$ who has received a leaf $w$ of a star that is either
trivial or whose root was not assigned to $j$. Given such an agent $h$, we
pick an unassigned leaf $v$ (whose root was assigned to $j$) and perform an
exchange by assigning $v$ to $h$ and, in turn, reallocating $w$ to $j$. In
this way, the satisfaction of $h$ remains unchanged, while an additional leaf
is assigned to $j$. Therefore, as long as there are unassigned leaves, it is
always possible to assign a leaf to the least satisfied agent.

We now show that such an agent $h\neq j$ for the above exchange does indeed
exist for $k\geq 3$. Suppose, for the sake of contradiction, that such an
agent does not exist. Then all leaves of stars whose roots are assigned to
agents other than $j$ and all singletons must already be assigned to $j$ and
$j$ is assigned at least one root. Hence, the least satisfied agent $j$
dominates all leaves of the nontrivial stars and all singletons and every
agent in the generated allocation $\pi$ has satisfaction at least
$1+a+\sum_{i=1}^{\ell}a_{i}$. As we will now show, this can only be the case
if there are just two agents, contradicting our assumption of $k\geq 3$.
Observe that the total sum of agent satisfactions is at most
$\ell+a+2\sum_{i=1}^{\ell}a_{i}$. Since every agent has satisfaction at least
$1+a+\sum_{i=1}^{\ell}a_{i}$, we have that the total satisfaction is at least
$k\left(1+a+\sum_{i=1}^{\ell}a_{i}\right)$, thus

$\displaystyle\sum_{j\in K}s_{\pi}(j)\geq
k\left(1+a+\sum_{i=1}^{\ell}a_{i}\right)\geq 3+3a+3\sum_{i=1}^{\ell}a_{i}=$
$\displaystyle=3+3a+\sum_{i=1}^{\ell}a_{i}+2\sum_{i=1}^{\ell}a_{i}>a+\ell+2\sum_{i=1}^{\ell}a_{i}\geq\sum_{j\in
K}s_{\pi}(j),$

a contradiction. Hence, agent $h$ must exist.

At the end of this process, which clearly can be performed in polynomial time,
all vertices of $G$ are assigned. In the remainder of the proof we show
optimality of the allocation by distinguishing two cases.

Case 1. _Every agent receives at most one root by the greedy algorithm._ Let
$S^{*}$ be the (unknown) optimal value of the optimization problem of
maximizing the minimum satisfaction among the agents. Let $R^{*}:=\\{i\mid
a_{i}\geq S^{*}-1,i\in\\{1,\ldots,\ell\\}\\}$ denote the set of indices of
roots giving, when assigned, a satisfaction at least $S^{*}$. W.l.o.g. we will
assume that $|R^{*}|<k$, because otherwise assigning each agent one root from
$R^{*}$ (as it would also be done by the greedy algorithm) already gives a
partial allocation with optimal minimum satisfaction.

Let $k^{\prime}:=k-|R^{*}|$. Note that in any allocation, at least
$k^{\prime}$ agents do not receive any roots from $R^{*}$. In any optimal
allocation, the total satisfaction remaining without the allocation of roots
in $R^{*}$ has to suffice to give at least those $k^{\prime}$ agents a
satisfaction of at least $S^{*}$. Hence, we get the following:

$\sum_{i=1}^{\ell}(2a_{i}+1)+a-\sum_{i\in R^{*}}(a_{i}+1)\geq k^{\prime}\cdot
S^{*}\,.$ (1)

Now consider the partial greedy allocation $\pi^{\prime}$ produced by the
greedy algorithm after having assigned all the roots. Let $A^{\prime}$ denote
the set of agents for which the satisfaction with respect to $\pi^{\prime}$ is
less than $S^{*}$, i.e., $A^{\prime}=\\{j\in K\colon
s_{\pi^{\prime}}(j)<S^{*}\\}$. We have $|A^{\prime}|=k-|R^{*}|=k^{\prime}$,
since the greedy algorithm gives $|R^{*}|$ agents satisfaction at least
$S^{*}$ by assigning them the roots in $R^{*}$, while all other agents receive
at most one root by the assumption of this first case, and thus fail to reach
$S^{*}$ in $\pi^{\prime}$.

We argue that our greedy algorithm yields an optimal solution by showing that
the number of unassigned leaves and singletons suffices to give all agents in
$A^{\prime}$ satisfaction of at least $S^{*}$.

To do so, we calculate, for all agents in $A^{\prime}$, the total number $c$
of leaves and singletons required to reach $S^{*}$ by subtracting the
satisfaction reached through the allocated root vertices from the desired
target satisfaction. We obtain:

$\displaystyle c$ $\displaystyle=$ $\displaystyle\sum_{j\in
A^{\prime}}\left(S^{*}-\sum_{r_{i}\in\pi^{\prime}(j)}(a_{i}+1)\right)$ (2)
$\displaystyle=$ $\displaystyle|A^{\prime}|\cdot S^{*}-\sum_{j\in
A^{\prime}}\sum_{r_{i}\in\pi^{\prime}(j)}(a_{i}+1)$ $\displaystyle=$
$\displaystyle k^{\prime}\cdot S^{*}-\sum_{j\in
A^{\prime}}\sum_{r_{i}\in\pi^{\prime}(j)}(a_{i}+1)$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{\ell}(2a_{i}+1)+a-\sum_{i\in
R^{*}}(a_{i}+1)-\sum_{j\in A^{\prime}}\sum_{r_{i}\in\pi^{\prime}(j)}(a_{i}+1)$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{\ell}a_{i}+a$ (3)

where (2) follows from plugging in (1) and (3) is given by the fact that every
root is either in $R^{*}$ or it was allocated to an agent in $A^{\prime}$.

But this upper bound is exactly the number of leaves and singletons that are
available to be distributed by the greedy algorithm. By the exchange argument
these leaves and singletons can be evenly distributed in a way that the
satisfaction of each agent reaches $S^{*}$ in the allocation $\pi$ generated
by the greedy algorithm.

Case 2. _At least one agent receives more than one root by the greedy
algorithm._ Note that this implies $\ell>k$. For each
$i\in\\{1,\ldots,\ell\\}$, we denote by $\pi_{i}$ the partial greedy
allocation after assigning the first $i$ roots, let $K_{i}$ be the set of
agents who were assigned in $\pi_{i}$ at least two roots, let
$\underaccent{\bar}{s}_{i}=\min\\{s_{\pi_{i}}(j)\colon j\in K\\}$ and let
$\bar{s}_{i}=\max\\{s_{\pi_{i}}(j)\colon j\in K_{i}\\}$.

We first show that for all $i\in\\{k+1,\ldots,\ell\\}$, we have

$\bar{s}_{i}-\underaccent{\bar}{s}_{i}\leq a_{k+1}+1$ (4)

holds. We prove this by induction on $i$. For $i=k+1$, when assigning the
$(k+1)$-st root in the greedy algorithm, we may assume without loss of
generality that this root is assigned to the agent that received the $k$-th
root and in this partial assignment we have
$\bar{s}_{k+1}=(a_{k}+1)+(a_{k+1}+1)$ and $\underaccent{\bar}{s}_{k+1}\geq
a_{k}+1$. Hence $\bar{s}_{k+1}-\underaccent{\bar}{s}_{k+1}\leq a_{k+1}+1$. Now
let $k+1\leq i<\ell$ and assume that
$\bar{s}_{i}-\underaccent{\bar}{s}_{i}\leq a_{k+1}+1$. Note that after every
further root is assigned, the minimum satisfaction value never decreases, that
is, $\underaccent{\bar}{s}_{i+1}\geq\underaccent{\bar}{s}_{i}$. When assigning
the root $r_{i+1}$ (recall that $a_{i+1}\leq a_{k+1}$), the root is assigned
to an agent with satisfaction at least $\underaccent{\bar}{s}_{i}$. Note that
$K_{i}\subseteq K_{i+1}$ and therefore $\bar{s}_{i}\leq\bar{s}_{i+1}$. If
$\bar{s}_{i+1}=\bar{s}_{i}$, then using the induction hypothesis we
immediately obtain that $\bar{s}_{i+1}-\underaccent{\bar}{s}_{i+1}\leq
a_{k+1}+1$. If $\bar{s}_{i+1}>\bar{s}_{i}$, then the least satisfied agent
with respect to $\pi_{i}$ becomes the most satisfied agent in $K_{i+1}$ and
its satisfaction with respect to $\pi_{i+1}$ is
$\bar{s}_{i+1}=\underaccent{\bar}{s}_{i}+a_{i+1}+1$. Therefore,

$\bar{s}_{i+1}-\underaccent{\bar}{s}_{i+1}=\underaccent{\bar}{s}_{i}+a_{i+1}+1-\underaccent{\bar}{s}_{i+1}\leq
a_{i+1}+1\leq a_{k+1}+1\,.$

This proves (4). In particular, the partial assignment $\pi_{\ell}$ after
assigning all roots satisfies $\bar{s}_{\ell}-\underaccent{\bar}{s}_{\ell}\leq
a_{k+1}+1$.

Let $K^{\prime}=K\setminus K_{\ell}$ be the set of agents that are assigned
exactly one root in $\pi_{\ell}$. Let $K^{\prime\prime}=\\{j\in
K^{\prime}\colon s_{\pi_{\ell}}(j)\leq\bar{s}_{\ell}\\}$. Observe that the
preference graph, since $\ell>k$, contains at least $(k+1)\cdot a_{k+1}$
leaves. Using the fact that $k+1>|K|\geq|K^{\prime\prime}\cup K_{\ell}|$ and
(4) we infer that

$(k+1)\cdot a_{k+1}>(|K^{\prime\prime}\cup
K_{\ell}|)(\bar{s}_{\ell}-\underaccent{\bar}{s}_{\ell}-1)\,.$

These leaves are then distributed greedily to the agents, starting with the
agents in $K^{\prime\prime}\cup K_{\ell}$. Since the satisfaction of each of
these agents is at least $\underaccent{\bar}{s}_{\ell}$, the total number of
leaves suffices for lifting the satisfaction of every agent in
$K^{\prime\prime}\cup K_{\ell}$ to $\bar{s}_{\ell}-1$. Since in the procedure
above we showed that these leaves can be assigned so that the least satisfied
agent receives an additional leaf in every step, in the end the difference in
satisfaction between any two agents in $K^{\prime\prime}\cup K_{\ell}$ is at
most $1$.

Hence, our greedy strategy leads to an allocation $\pi$ which, when restricted
to the agents in $K^{\prime\prime}\cup K_{\ell}$, is an optimal allocation for
the reduced instance resulting from removing the roots assigned to some agents
in $K^{\prime}\setminus K^{\prime\prime}$. But then $\pi$ must also be optimal
for our original instance, since each agent in $K^{\prime}\setminus
K^{\prime\prime}$ receives only one root, and has satisfaction at least as
high as the minimum satisfaction among the agents in $K^{\prime\prime}\cup
K_{\ell}$. ∎

It might be noted that the greedy strategy with exchanges stated above for the
general case $k\geq 3$ does not work for the special case $k=2$. This can be
shown by means of a simple example with $a_{1}=10,a_{2}=a_{3}=a_{4}=1,a=0$.
The general greedy strategy assigns root 1 to agent 1 and all the other roots
to agent 2, resulting in satisfactions 16 and 14. An optimal solution would
give roots 1 and 2 to agent 1 and roots 3 and 4 to agent 2 resulting in a
satisfaction of 15 for both agents.

For a constant number of agents, we can also give a polynomial-time algorithm
for general out-forests. This generalizes considerably the result for out-
stars given in Theorem 7, but at the cost of restricting $k$.

######  Theorem 8.

For any constant number $k$ of agents, CG Min-Max Dissatisfaction can be
solved in polynomial time if the preference graph $G$ is an out-forest.

###### Proof.

We denote by $n$ the number of vertices of $G$. For a vertex $v$, we denote by
$T_{v}$ the out-tree rooted at $v$, that is, the subgraph of $G$ induced by
$v$ and all its successors. A dissatisfaction profile is a $k$-tuple
$(d_{i}\colon i\in K)$ with $d_{i}\in\mathbb{N}_{0}$ for all $i\in K$ such
that there is an allocation $\pi$ with ${\delta}_{\pi}(i)=d_{i}$ for each
$i\in K$. Let ${\it DP}[v]$ be the set of all dissatisfaction profiles for
$T_{v}$. Since a dissatisfaction profile is a vector of length $k$ whose
elements have values between $0$ and $n$, the set ${\it DP}[v]$ contains at
most $(n+1)^{k}$ profiles.

The _depth_ of a vertex $v$ is the number of vertices on the unique maximal
directed path in $G$ ending at $v$. We observe that one can preprocess the
input out-forest $G$ by only considering the vertices at depth at most $k$ in
each out-tree. To verify this, observe that as a consequence of Lemma 2 we can
assume that each agent receives at most one item from each path in $G$ in an
optimal allocation $\pi$. We can iteratively strictly decrease the number of
vertices with maximum depth $>k$ that are assigned to some agent (if such
vertices exist) without making any agent worse off: take such a vertex $w$
assigned to some agent $i$ and the path $p$ from the root to $w$. On $p$, by
the above property, there must be at least one vertex $v\not=w$ that is not
assigned to any agent; now, modify $\pi$ by allocating $v$ to agent $i$ and
removing all items of $\text{succ}(v)$ from the set $\pi(i)$.

Furthermore, note that if a vertex is not assigned to any agent in some
solution, then assigning this vertex to any agent would also yield a solution.

Fix a vertex $u$ of $G$. Let $v_{1},\dots,v_{q}$ be the out-neighbors of $u$,
let $\pi_{u}$ be an arbitrary allocation for $T_{u}$ and let $d_{u}$ be the
dissatisfaction profile of $\pi_{u}$. We may assume that $u$ is assigned to
some agent $j$ with respect to $\pi_{u}$, that is, $u\in\pi_{u}(j)$, and that
no other vertex in $T_{u}$ is assigned to agent $j$; otherwise, we can remove
this item from $\pi_{u}(j)$ without changing the dissatisfaction of any agent.
The dissatisfaction for agent $j$ with respect to $\pi_{u}$ is $0$, since
$u\in\pi(j)$ and $u$ is the most preferred item in $T_{u}$. Moreover, for
every agent $j^{\prime}\neq j$, its dissatisfaction with respect to $\pi_{u}$
corresponds to the sum of the agent’s dissatisfactions over all of the
subtrees $T_{v_{i}}$ plus $1$, since $u\notin\pi_{u}(j^{\prime})$. Hence, we
obtain that $d_{u}[j]=0$ and, for all $j^{\prime}\in K$ such that
$j^{\prime}\neq j$, $d_{u}[j^{\prime}]=1+\sum_{i=1}^{q}d_{v_{i}}[j^{\prime}]$,
where $d_{v_{i}}$ corresponds to the dissatisfaction profile of the out-tree
$T_{v_{i}}$ with respect to $\pi_{u}$.

We claim that ${\it DP}[u]$, the set of all dissatisfaction profiles for
$T_{u}$, can be computed in polynomial time assuming that ${\it DP}[v_{i}]$ is
known for all out-neighbors $v_{i}$ of $u$. The procedure is as follows. If
$u$ is a leaf, that is, $u$ has no out-neighbor, then ${\it DP}[u]$ is the set
containing exactly $k+1$ profiles such that each profile is a vector of length
$k$ with at most one element equal to $0$ and the other elements are equal to
$1$; this assumes that $d\geq 1$, otherwise either $k=1$ and the problem
becomes trivial or there is no solution. On the other hand, if $u$ is not a
leaf, then let $S=\\{0\\}^{k}$, that is, $S$ contains a unique vector of
length $k$ all of whose elements are $0$. Then, for each out-neighbor $v_{i}$
of $u$, we add to $S$ the profiles $d_{S}+d_{i}$ for all $d_{S}\in S$ and all
$d_{i}\in{\it DP}[v_{i}]$. We can detect duplicate profiles in $S$ in constant
time, for instance by using a Boolean array $B$ with $(n+1)^{k}$ cells, where
each cell corresponds to a dissatisfaction profile, such that a
dissatisfaction profile $d_{i}$ belongs to $S$ if and only if the cell
corresponding to profile $d_{i}$ in $B$ is set to $true$. Hence, each time a
new profile is computed, we can detect and ignore duplicates in $S$, which
implies that at every step of the procedure, $|S|\leq(n+1)^{k}$. For each
neighbor $v_{i}$, since $|S|$ and $|{\it DP}[v_{i}]|$ have size at most
$(n+1)^{k}$, it takes $\mathcal{O}(|S|\cdot|{\it
DP}[v_{i}]|)=\mathcal{O}((n+1)^{2k})$ time to update $S$. Hence, once all
neighbors of $u$ have been considered, it takes at most $\mathcal{O}({\it
deg}^{+}(u)(n+1)^{2k})$ time to compute $S$, where ${\it deg}^{+}(u)$ denotes
the out-degree of $u$. Note that, at the end of the procedure, $S$ corresponds
exactly to the dissatisfaction profiles of the out-forest obtained from
$T_{u}$ by removing $u$. Now, we explain how to construct the set ${\it
DP}[u]$ of all dissatisfaction profiles for $T_{u}$. We iterate over $j\in K$
and for each $d_{S}\in S$, we create a profile $d_{u}$ such that
$d_{u}[\ell]=d_{S}[\ell]+1$ if $\ell\neq j$, and $d_{u}[j]=0$. Clearly,
$d_{u}$ is a dissatisfaction profile for $T_{u}$ corresponding to an
allocation $\pi_{u}$ such that $u\in\pi_{u}(j)$. At the end of this loop,
${\it DP}[u]$ contains exactly all dissatisfaction profiles for $T_{u}$. Thus,
if ${\it DP}[v_{i}]$ is known for all out-neighbors $v_{i}$ of $u$, then ${\it
DP}[u]$ can be obtained in time $\mathcal{O}((n+1)^{2k+1})$.

Using a dynamic programming approach, we can compute the set ${\it DP}[v]$ for
all vertices $v$ of $G$ in time
$\mathcal{O}(n(n+1)^{2k+1})=\mathcal{O}((n+1)^{2k+2})$. Then, to decide
whether there exists a solution for $G$, it suffices to compute the set of all
dissatisfaction profiles for $G$ with a similar approach as the one we
described to compute ${\it DP}[u]$ for a fixed $u$ and check the existence of
a profile whose values are all at most $d$. Thus, CG Min-Max Dissatisfaction
can be solved in $\mathcal{O}((n+1)^{2k+2})$ time. ∎

The above theorem follows also as a special case of the general result for
graphs of bounded treewidth stated in Theorem 17 and Remark 18 in [15].
However, for self-containment we gave an explicit construction of an
elementary dynamic programming algorithm.

##  5 Fixed parameter tractability based on modular partitions

The following result modifies the graph concept of bounded neighborhood
diversity introduced by Lampis [30]. In a (directed) graph $G=(V,A)$ a set
$X\subseteq V$ is a _module_ if each vertex in $V\setminus X$ has a
homogeneous relationship to $X$, i.e., for all $x,y\in X$ it holds that
$N^{-}(x)\cap(V\setminus X)=N^{-}(y)\cap(V\setminus X)$ and
$N^{+}(x)\cap(V\setminus X)=N^{+}(y)\cap(V\setminus X)$. A partition of the
vertex set $V$ of a graph $G=(V,E)$ into modules $X_{1},\dots,X_{d}$, i.e.,
the $X_{i}$ are pairwise disjoint and $\bigcup_{1\leq i\leq d}X_{i}=V$, is
called a _modular partition_ of $G$. We call $d$ the _size_ of the modular
partition. Typically, one restricts the types of induced subgraphs $G[X_{i}]$
to obtain modular partitions into certain module types. One well-studied
example is partitioning the vertex set of an undirected graph into clique
modules and independent set modules, as in the definition of the neighborhood
diversity. We look at a partition into _path modules_ and independent set
modules, hence the subsets $X_{i}$ in the definition above are either
independent sets or directed paths. Clearly, cliques are not very meaningful
in the setting of preferences and partial orders. However, ordered paths are a
decisive element of expressing preferences and fit well into the concept of
modular partition.

The following theorem shows that such a partition is unique and can be
computed efficiently.

######  Theorem 9.

A partition of a graph $G=(V,A)$ into a minimum number of path modules and
independent set modules is unique and can be computed in
$\mathcal{O}(|V|+|A|)$ time.

###### Proof.

We use the unique modular decomposition tree of the graph $G=(V,A)$, which can
be obtained in linear time using the algorithm of McConnell and Montgolfier
[35]. Observe that both path modules and independent set modules uniquely
decompose into singletons in the modular decomposition. (Clearly, no proper
subset of at least two path vertices, adjacent or not, can be a module to the
other vertices of the ordered path.) Hence, using the modular decomposition
tree, we obtain our partition into path modules and independent set modules by
iterating over all leaves of the modular decomposition tree which correspond
to the singleton sets. If the parent module of such a singleton is a path
module or an independent set module, we add this module to our partition.
Otherwise, we add the singleton module to the partition. The uniqueness and
minimality of this partition follows from the uniqueness of the modular
decomposition tree and the above observation that path modules and independent
set modules only decompose into singleton modules. ∎

######  Theorem 10.

CG Min-Max Dissatisfaction is fixed parameter tractable with respect to $k+d$,
where $k$ is the number of agents and $d$ is the minimum number of path
modules and independent set modules partitioning $V(G)$.

###### Proof.

After computing the partition of $V(G)$ according to Theorem 9 we first
consider the path modules. Since every agent will receive at most one vertex
from every path module (by Lemma 2), we can limit all paths to have at most
$k$ vertices and ignore additional vertices. For paths with fewer than $k$
vertices we add dummy vertices whose allocation to an agent represents the
fact that no vertex of this path is allocated to this agent. For each path
module we guess one of the $k\,!$ orderings of the agents. Each such guess
represents the ordering in which all the $k$ path vertices are assigned to the
agents in a top-down way (dummy vertices mean that no vertex of that path is
assigned to the corresponding agent). Considering all guesses over all at most
$d$ path modules yields $\mathcal{O}((k!)^{d})$ possibilities for the
allocation of path vertices.

Next, we consider the $d^{\prime}\leq d$ independent set modules and guess for
each of them and for each agent whether that agent is assigned at least one
vertex of that module. Clearly, there are at most $(2^{k})^{d}$ possible
guesses.

For each independent set module $M_{i}$, $i=1,\ldots,d^{\prime}$, let
$k(M_{i})\leq k$ denote the number of agents receiving at least one vertex by
the current guess. Each of these $k(M_{i})$ agents is allocated an arbitrary
single vertex of $M_{i}$, if this is possible. By the module property, the
actual choice is irrelevant.

Thus, together with the allocation of path vertices, every guess results in a
partial allocation which may also include assignments of dominated vertices.
Since we restrict our computation to antichains (cf. Lemma 2), we remove all
dominated vertices to obtain a valid candidate consisting of a partial
allocation with a satisfaction value $\sigma_{j}$ for every agent $j\in K$. It
remains to distribute the remaining vertices from all independent set modules
in order to maximize the minimum satisfaction value. This objective value is
determined by iterating over all possible target satisfaction values $\sigma$.
Note that an allocation by guessing is out of the question since the size of a
module $M_{i}$ can be $\Theta(|V(G)|)$. Instead, the completion of the partial
allocation is done by means of the following auxiliary maximum network flow
model.

The network starts with a source node $s$ connected to all nodes
$a_{1},\ldots,a_{k}$ with $a_{j}$ representing agent $j$. Each arc $(s,a_{j})$
has capacity $\sigma-\sigma_{j}$ (agents with satisfaction
$\sigma_{j}\geq\sigma$ are omitted in the flow model). For every independent
set module $M_{i}$, $i=1,\ldots,d^{\prime}$, we add a node $b_{i}$ connected
to a sink node $t$ where the capacity of the arc $(b_{i},t)$ equals the number
of unassigned vertices in $M_{i}$, i.e., $|M_{i}|-k(M_{i})$. Every agent node
$a_{j}$ is connected (with infinite capacity) to every module node $b_{i}$ if
$j$ already receives vertices from $M_{i}$ in the current guess (which implies
that additional vertices from $M_{i}$ could be assigned to $j$). If the
maximum $s,t$-flow in this network has a value equal to
$\sum_{j=1}^{k}(\sigma-\sigma_{j})$, i.e., all arcs leaving the source $s$ are
saturated, then the flow value on each arc $(a_{j},b_{i})$ corresponds to the
number of (arbitrarily chosen) vertices from the independent set $M_{i}$
allocated to agent $j$. The resulting allocation has satisfaction value
$\sigma$ for each agent. Iterating over $\sigma$ (or performing binary search)
one can find the best possible satisfaction reachable by the current guess.
Evaluating all guesses will solve CG Min-Max Dissatisfaction. ∎

With our current techniques it does not seem to be possible to get rid of the
exponential dependence on $k$ in the running time of the algorithm. In fact,
the complexity of CG Min-Max Dissatisfaction is open even in the case when $G$
consists of three paths, with no connections between them (see Section 6). But
if we consider a partition into independent set modules only, we are able to
obtain an FPT algorithm for an arbitrary number of agents. Note that such a
partition can be computed in linear time using the same techniques as used in
the proof of Theorem 9. In the case of undirected graphs, maximal independent
set modules were studied by Heggernes, Meister, and Papadopoulos [26] and by
Lozin and Milanič [33] (under the name _similarity classes_).

######  Theorem 11.

For any number $k$ of agents, CG Min-Max Dissatisfaction is fixed parameter
tractable with respect to $d$, where $d$ is the minimum number of independent
set modules partitioning $V(G)$.

###### Proof.

Let $\mathcal{I}$ be the family of independent sets obtained by the partition
of $V(G)$ into the minimum number of independent set modules. A nonempty set
$S\subseteq\mathcal{I}$ is said to be _assignable_ if it holds for all pairs
$I,I^{\prime}\in S$, $I\neq I^{\prime}$, that there is no directed path in $G$
from a vertex in $I$ to a vertex in $I^{\prime}$; in other words, if the set
$\bigcup_{I\in S}I$ is a nonempty antichain in $G$. We denote by
$\mathcal{A}\subseteq 2^{\mathcal{I}}$ the set of assignable sets. Note that
$|\mathcal{A}|\leq 2^{d}$. For an assignable set $S\in\mathcal{A}$ we call an
agent an _$S$ -agent_ if it is only assigned vertices from $\bigcup_{I\in S}I$
and for each independent set $I\in S$ at least one vertex from $I$ is assigned
to the agent. Recall that by Lemma 2 we may restrict our attention to
allocations in which the set of vertices allocated to each agent is a nonempty
antichain. For any such allocation, each agent is an $S$-agent where $S$ is
the set of independent sets containing vertices assigned to the agent, and is
not an $S^{\prime}$-agent for any set
$S^{\prime}\in\mathcal{A}\setminus\\{S\\}$.

As a first step we guess a subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$
of assignable sets. This guess corresponds to the case when for each
$S\in\mathcal{A}^{\prime}$ at least one $S$-agent exists and for all
$S\in\mathcal{A}\setminus\mathcal{A}^{\prime}$ no $S$-agent exists. We then
iterate over all dissatisfaction thresholds $t$ and check if a feasible
allocation to all $k$ agents exists that is consistent with the guess
$\mathcal{A}^{\prime}$ and gives a dissatisfaction at most $\delta$ for all
agents. Clearly, for the optimal dissatisfaction value also, such an
allocation must exist for some guess of assignable sets. We introduce an
integer programming model that performs exactly such a check for a given
$\mathcal{A}^{\prime}$ and $\delta$.

For every $S\in\mathcal{A}^{\prime}$ let $d_{S}$ be the number of vertices of
$G$ not dominated by any $v\in\bigcup_{I\in S}I$, i.e., the guaranteed
dissatisfaction of every $S$-agent. We introduce integer variables $x_{S}$ for
each $S\in\mathcal{A}^{\prime}$ that count how many agents are $S$-agents. In
addition, we introduce integer variables $y_{S,I}$ for each
$S\in\mathcal{A}^{\prime}$ and $I\in S$ that count how many vertices of $I$
are assigned to $S$-agents. Expressed in terms of these variables, the
dissatisfaction of every $S$-agent is at most

$d_{S}+\left|\bigcup_{I\in S}I\right|-\left\lfloor\sum_{I\in
S}\frac{y_{S,I}}{x_{S}}\right\rfloor,$ (5)

since the $\sum_{I\in S}y_{S,I}$ vertices out of the independent sets in $S$
assigned to the $S$-agents can be distributed evenly among them. The upper
bound in (5) must be smaller or equal to the given threshold value $\delta$.
Note that by integrality of $\delta$ the floor function in (5) can be dropped
in this condition, yielding

$\delta\geq d_{S}+\left|\bigcup_{I\in S}I\right|-\sum_{I\in
S}\frac{y_{S,I}}{x_{S}}\,.$ (6)

We multiply (6) by $x_{S}\geq 1$ to obtain the following equivalent linear
inequality:

$\delta\,x_{S}\geq d_{S}\,x_{S}+\left|\bigcup_{I\in S}I\right|x_{S}-\sum_{I\in
S}y_{S,I}$

Hence, the following integer programming decision formulation checks if the
dissatisfaction threshold $t$ can be reached by an allocation to $k$ agents
that is consistent with our guess $\mathcal{A}^{\prime}$.

$\displaystyle\delta\,x_{S}$ $\displaystyle\geq
d_{S}\,x_{S}+\left|\bigcup_{I\in S}I\right|x_{S}-\sum_{I\in S}y_{S,I}$
$\displaystyle\forall S\in\mathcal{A}^{\prime}$ (7)
$\displaystyle\sum_{S\in\mathcal{A}^{\prime}}x_{S}$ $\displaystyle=k$ (8)
$\displaystyle\sum_{S\in\mathcal{A}^{\prime}\colon\,I\in S}y_{S,I}$
$\displaystyle\leq|I|$ $\displaystyle\forall I\in\mathcal{I}$ (9)
$\displaystyle x_{S}$ $\displaystyle\geq 1$ $\displaystyle\forall
S\in\mathcal{A}^{\prime}$ (10) $\displaystyle y_{S,I}$ $\displaystyle\geq
x_{S}$ $\displaystyle\forall S\in\mathcal{A}^{\prime},I\in S$ (11)
$\displaystyle x_{S},y_{S,I}$ $\displaystyle\in\mathbb{N}$
$\displaystyle\forall S\in\mathcal{A}^{\prime},I\in S$ (12)

Note that the nonzero coefficients of this integer program are either constant
($\pm 1$) or polynomial in the input size (namely $\delta$, $d_{S}$,
$\left|\bigcup_{I\in S}I\right|$, and $k$), and the number of variables and
constraints is bounded by a function of $d$. Hence, using Lenstra’s algorithm
[31] the solution of this integer program is fixed parameter tractable with
respect to parameter $d$.

Taking over all guesses $\mathcal{A}^{\prime}$ the minimum value of $\delta$
that allows a feasible solution of (7)–(12) gives an allocation with optimal
dissatisfaction value. Thus, CG Min-Max Dissatisfaction is fixed parameter
tractable with respect to $d$. ∎

##  6 Conclusions

In this paper we study the fair allocation of items to agents, when
preferences are expressed by a mutually agreed preference graph. Fairness is
represented by the maximum dissatisfaction experienced by any agent. The
setting with individual preferences was treated in a related paper [15]. For
general graphs, CG Min-Max Dissatisfaction is efficiently solvable when we are
dealing with $2$ agents and turns out to be NP-complete for $k\geq 3$ agents.
However, for $k\geq 3$ agents, when we restrict the preference graph to out-
stars, the problem can be solved in polynomial time. Polynomiality can be
shown also for out-forests, if the number of agents $k$ is a constant. For
graphs allowing certain bounded modular partitions, fixed parameter
tractability results can be derived.

As an interesting open problem for CG Min-Max Dissatisfaction and an arbitrary
number of agents, we suggest the case where $G$ consists only of out-paths.
W.l.o.g. paths can be restricted to have $k$ vertices. Note that the problem
is trivial for shorter paths and in the case of two out-paths, where we can
just assign the items to agents in increasing, respectively decreasing, order
on the two paths to reach an optimal solution for the optimization version of
CG Min-Max Dissatisfaction.

For the special case of three out-paths each of $k$ vertices, an optimal
solution can be given as shown in Figure 2. Note that one has to distinguish
the cases of $k$ being even or odd, and that the allocation described there
satisfies the lower bound $3\cdot(k-1)/2$. However, CG Min-Max Dissatisfaction
remains open for three out-paths of arbitrary length.

$1$$2$$\vdots$$\frac{k-1}{2}$$\frac{k+1}{2}$$\frac{k+3}{2}$$\vdots$$k-1$$k$$k-1$$k-3$$\vdots$$2$$k$$k-2$$\vdots$$3$$1$$k$$k-2$$\vdots$$3$$1$$k-1$$\vdots$$4$$2$$1$$2$$\vdots$$\frac{k-2}{2}$$\frac{k}{2}$$\frac{k+2}{2}$$\vdots$$k-2$$k-1$$k$$k$$k-2$$k-4$$\vdots$$2$$k-1$$k-3$$\vdots$$3$$1$$k$$k-1$$k-3$$\vdots$$3$$1$$k-2$$\vdots$$4$$2$$k$
odd$k$ even Figure 2: If paths have length (at least) $k$, then the natural
lower bound $3(k-1)/2$ obtained by summing up all dissatisfaction values over
all vertices, which gives $3k(k-1)/2$, and dividing this value by $k$, can be
obtained by the above construction based on the parity of $k$.

Considering a more difficult problem, it would be interesting to establish the
complexity of CG Min-Max Dissatisfaction for general out-forests with an
arbitrary number of agents $k$. This would close the gap between Theorem 7
(out-stars for arbitrary $k$) and Theorem 8 (out-forest for constant $k$).

Recall that CG Min-Max Dissatisfaction can be solved in polynomial time if the
graph has width $2$ (see Theorem 6). In a more general direction, we point to
the question of the complexity of CG Min-Max Dissatisfaction on preference
graphs of bounded width, which were recently studied in a number of papers [4,
8, 13, 22, 34]. Note that if both the width $w$ and the number of agents $k$
is bounded, it is easy to obtain in linear time a kernel of size $k\cdot w$ by
reducing the preference graph to the top $k$ levels, implying fixed parameter
tractability in $k+w$.

A different objective would consider the sum of dissatisfaction values over
all agents, instead of the maximum. The resulting minimization follows a
utilitarian approach and maximizes the overall efficiency of the allocation.
This setting was already introduced in [14] and will be subject of our future
work.

#### Acknowledgements.

The work of this paper was done in the framework of a bilateral project
between University of Graz and University of Primorska, financed by the OeAD
(SI 13/2023) and the Slovenian Research and Innovation Agency (BI-
AT/23-24-009). The authors acknowledge partial support by the Slovenian
Research and Innovation Agency (I0-0035, research programs P1-0285 and
P1-0404, and research projects N1-0102, N1-0160, N1-0210, J1-3001, J1-3002,
J1-3003, J1-4008, and J1-4084), by the research program CogniCom (0013103) at
the University of Primorska, and by the Field of Excellence “COLIBRI” at the
University of Graz.

## References

  * [1] J.A. Aloysius, F.D. Davis, D.D. Wilson, A. Ross Taylor, and J.E. Kottemann.  User acceptance of multi-criteria decision support systems: The impact of preference elicitation techniques.  European Journal of Operational Research, 169(1):273–285, 2006\.
  * [2] H. Aziz.  Developments in multi-agent fair allocation.  In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI’20), pages 13563–13568. AAAI, 2020.
  * [3] H. Aziz, S. Gaspers, S. Mackenzie, and T. Walsh.  Fair assignment of indivisible objects under ordinal preferences.  Artificial Intelligence, 227:71–92, 2015.
  * [4] J. Balabán and P. Hliněný.  Twin-width is linear in the poset width.  In 16th International Symposium on Parameterized and Exact Computation, volume 214 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 6, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., 2021\.
  * [5] C.A. Bana e Costa and J.-C. Vansnick.  MACBETH – an interactive path towards the construction of cardinal value functions.  International Transactions in Operational Research, 1(4):489–500, 1994.
  * [6] D. Baumeister, S. Bouveret, J. Lang, T. Nguyen, J. Rothe, and A. Saffidine.  Positional scoring-based allocation of indivisible goods.  Autonomous Agents and Multi-Agent Systems, 31:628–655, 2017.
  * [7] I. Bezáková and V. Dani.  Allocating indivisible goods.  ACM SIGecom Exchanges, 5(3):11–18, 2005.
  * [8] É. Bonnet, E.J. Kim, S. Thomassé, and R. Watrigant.  Twin-width I: Tractable FO model checking.  Journal of the ACM, 69(1):Art. 3, 46, 2022.
  * [9] S. Bouveret, Y. Chevaleyre, and N. Maudet.  Fair allocation of indivisible goods.  In F. Brandt et al., editor, Handbook of Computational Social Choice, chapter 12. Cambridge University Press, 2016.
  * [10] S. Bouveret and J. Lang.  Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity.  Journal of Artificial Intelligence Research, 32:525–564, 2013.
  * [11] S.J. Brams and P.C. Fishburn.  Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity.  Social Choice and Welfare, 17:247–267, 2000.
  * [12] R. Burkard, M. Dell’Amico, and S. Martello.  Assignment Problems.  Society for Industrial and Applied Mathematics, 2012.
  * [13] M. Cáceres, M. Cairo, B. Mumey, R. Rizzi, and A.I. Tomescu.  A linear-time parameterized algorithm for computing the width of a DAG.  In Graph-theoretic concepts in computer science, volume 12911 of LNCS, pages 257–269. Springer, 2021.
  * [14] N. Chiarelli, C. Dallard, A. Darmann, S. Lendl, M. Milanič, P. Muršič, U. Pferschy, and N. Pivač.  Allocating indivisible items with minimum dissatisfaction on preference graphs.  In Proceedings of the 7th International Conference on Algorithmic Decision Theory (ADT’21), volume 13023 of LNCS, pages 243–257. Springer, 2021.
  * [15] N. Chiarelli, C. Dallard, A. Darmann, S. Lendl, M. Milanič, P. Muršič, U. Pferschy, and N. Pivač.  Allocation of indivisible items with individual preference graphs.  Discrete Applied Mathematics, 334:45–62, 2023.
  * [16] D. Cornilly, G. Puccetti, L. Rüschendorf, and S. Vanduffel.  Fair allocation of indivisible goods with minimum inequality or minimum envy.  European Journal of Operational Research, 297(2):741–752, 2022\.
  * [17] A. Darmann, C. Klamler, and U. Pferschy.  Maximizing the minimum voter satisfaction on spanning trees.  Mathematical Social Sciences, 58(2):238–250, 2009.
  * [18] M. Dell’Amico and S. Martello.  The $k$-cardinality assignment problem.  Discrete Applied Mathematics, 76(1-3):103–121, 1997.
  * [19] R.P. Dilworth.  A decomposition theorem for partially ordered sets.  Annals of Mathematics. Second Series, 51:161–166, 1950.
  * [20] R. Freeman, E. Micha, and N. Shah.  Two-sided matching meets fair division.  In Proceedings of the 30th International Joint Conference on Artificial Intelligence, IJCAI’21, pages 203–209, 2021.
  * [21] D.R. Fulkerson.  Note on Dilworth’s decomposition theorem for partially ordered sets.  Proceedings of the American Mathematical Society, 7:701–702, 1956\.
  * [22] J. Gajarský, P. Hliněný, D. Lokshtanov, J. Obdržálek, S. Ordyniak, M.S. Ramanujan, and S. Saurabh.  FO model checking on posets of bounded width.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, pages 963–974. IEEE Computer Society, 2015\.
  * [23] M.R. Garey, D.S. Johnson, and L. Stockmeyer.  Some simplified NP-complete graph problems.  Theoretical Computer Science, 1(3):237–267, 1976.
  * [24] D. Golovin.  Max-min fair allocation of indivisible goods.  Technical report, School of Computer Science, Carnegie Mellon University, 2005.
  * [25] P.J. Hammond.  Interpersonal comparisons of utility: Why and how they are and should be made, pages 200–254.  Cambridge University Press, 1991.
  * [26] P. Heggernes, D. Meister, and C. Papadopoulos.  Graphs of linear clique-width at most 3.  Theoretical Computer Science, 412(39):5466–5486, 2011.
  * [27] J.E. Hopcroft and R.M. Karp.  An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs.  SIAM Journal on Computing, 2:225–231, 1973.
  * [28] Y. Kawase and H. Sumita.  Online max-min fair allocation.  In Algorithmic game theory, volume 13584 of Lecture Notes in Comput. Sci., pages 526–543. Springer, Cham, 2022.
  * [29] D.M. Kilgour and R. Vetschera.  Two-player fair division of indivisible items: Comparison of algorithms.  European Journal of Operational Research, 271(2):620–631, 2018\.
  * [30] M. Lampis.  Algorithmic meta-theorems for restrictions of treewidth.  Algorithmica, 64:19–37, 2012.
  * [31] H.W. Lenstra Jr.  Integer programming with a fixed number of variables.  Mathematics of Operations Research, 8(4):538–548, 1983.
  * [32] R.J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In EC’04: Proceedings of the 5th ACM conference on Electronic commerce, pages 125–131. ACM, 2004.
  * [33] V. Lozin and M. Milanič.  On the maximum independent set problem in subclasses of planar graphs.  Journal of Graph Algorithms and Applications, 14(2):269–286, 2010\.
  * [34] V. Mäkinen, A.I. Tomescu, A. Kuosmanen, T. Paavilainen, T. Gagie, and R. Chikhi.  Sparse dynamic programming on DAGs with small width.  ACM Transactions on Algorithms, 15(2):Art. 29, 1–21, 2019.
  * [35] R.M. McConnell and F. De Montgolfier.  Linear-time modular decomposition of directed graphs.  Discrete Applied Mathematics, 145(2):198–209, 2005.
  * [36] N. Nguyen, T. Nguyen, M. Roos, and J. Rothe.  Computational complexity and approximability of social welfare optimization in multiagent resource allocation.  Autonomous Agents and Multi-Agent Systems, 28(2):256–289, 2014\.
  * [37] S.C. Ntafos and S.L. Hakimi.  On path cover problems in digraphs and applications to program testing.  IEEE Transactions on Software Engineering, 5(5):520–529, 1979.
  * [38] A.D. Procaccia and J. Wang.  Fair enough: guaranteeing approximate maximin shares.  In Proceedings of the 15th AAAI Conference on Artificial Intelligence (AAAI’14), pages 675–692. AAAI, 2014.
  * [39] J. Rawls.  A theory of justice.  The Belknap Press of Harvard University Press, Cambridge, Massachusetts, 1971.
  * [40] M. Roos and J. Rothe.  Complexity of social welfare optimization in multiagent resource allocation.  In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’10), pages 641–648, 2010.
  * [41] W. Thomson.  Introduction to the theory of fair allocation.  In F. Brandt et al., editor, Handbook of Computational Social Choice, chapter 11, pages 261–283. Cambridge University Press, 2016.