text:
\section{Introduction}
Let $G := (X \dot{\cup} Y,E)$ be a bipartite graph.
A matching $M\subseteq E$ is called
\emph{perfect} if every vertex of $X \dot{\cup} Y$ is adjacent to exactly one edge of $M$;
it is called
\emph{$X$-saturating} if every vertex of $X$ is adjacent to exactly one edge of $M$.
This paper studies the following relaxation of $X$-saturated matching (where
$X_M$ and $Y_M$ denote the vertices of $X$ and $Y$, respectively, saturated by $M$).
\begin{definition}
\label{def:envy-free}
\label{def:efm}
Let $G := (X \dot{\cup} Y, E)$ be a bipartite graph. A matching $M \subseteq E$ is said to be {\em envy-free w.r.t. $X$} if no vertex in $X \setminus X_M$ is adjacent to any vertex in $Y_M$.
\end{definition}
One may view $X$ as a set of people and $Y$ as a set of houses,
where a person in $X$ is adjacent to all houses in $Y$ which he or she likes.
A matching $M\subseteq E$ denotes an assignment of houses to people who like them.
Throughout the paper, all envy-free matchings are taken w.r.t. $X$. In such a matching, an unmatched person $x \in X\setminus X_M$ does not envy any matched person $x'\in X_M$, because $x$ does not like any matched house $y'\in Y_M$ anyway.

If a matching $M$ is $X$-saturating, then $X_M = X$, and $M$ is clearly envy-free. However, many graphs do not admit an $X$-saturating matching,
yet admit a nonempty envy-free matching; see Figure \ref{fig:efm-examples}(a).
In some graphs, the \emph{only} envy-free matching is the empty matching $\emptyset$ (which is vacuously envy-free). A natural example is
an \emph{odd path} ---
a path with $2k+1$ vertice, for some $k \geq 1$ --- where $X$ is identified with the larger class in the bipartition; see Figure \ref{fig:efm-examples}(b).
\begin{figure}
\begin{center}
\includegraphics[height=3cm,width=12cm]{efm-examples.pdf}
\end{center}
\caption{\label{fig:efm-examples}
(a) this graph has no $X$-saturating matching, but it has a nonempty envy-free matching (bold).
\\
(b), (c)
in these graphs, the only envy-free matching is empty.
}
\end{figure}

These examples invoke the question of whether a given graph admits a nonempty envy-free matching, and moreover, what is a maximum-cardinality envy-free matching in a given graph?

\subsection{Theoretic aspects: envy-free matching and graph structure}
We answer these questions by proving a structure theorem for bipartite graphs.
We prove that in every bipartite graph, there is a unique partition of the vertices into two subsets --- ``good'' and ``bad'': the ``good'' subset is $X$-saturated (and thus contains the largest possible envy-free matching), while the ``bad'' subset has a structure similar to an odd path (and thus contains only an empty envy-free matching). The structure of this ``bad'' subset is defined formally below.
\begin{definition}
\label{def:snake}
A bipartite graph $G := (X \dot{\cup} Y, E)$ is called  \emph{$Y$-path-saturated} if, for some $k\geq 1$, there exist partitions $X = X_0 \dot{\cup} \cdots \dot{\cup} X_k$ and $Y = Y_1 \dot{\cup} \cdots \dot{\cup} Y_k$ where for all $i\geq 1$:
\begin{itemize}
\item There is a perfect matching between vertices of $X_i$ and vertices of $Y_i$;
\item Every vertex in $Y_i$ is adjacent to some vertex in $X_{i-1}$.
\end{itemize}
\end{definition}
Every odd path with $|X|>|Y|$, as in Figure \ref{fig:efm-examples}(b), is $Y$-path-saturated. Figure \ref{fig:efm-examples}(c) shows another example of a $Y$-path-saturated graph; it can be seen that the structure of such a graph resembles that of an odd path.%
\footnote{
Note that the empty graph is $Y$-path-saturated (where $X_i = Y_j = \emptyset$ for all $i\geq 0, j\geq 1$).
Also note that a $Y$-path-saturated graph may have isolated vertices (vertices with degree 0) in $X$ --- such vertices are contained in $X_0$.
}
It can also be proved that, in a $Y$-path-saturated graph, just like in an odd path, the only envy-free matching is $\emptyset$.
Thus the $X$-saturated graphs and the $Y$-path-saturated graphs are two extreme cases.
Our first result is that these two extremes are the building-blocks of \emph{all} bipartite graphs.
Below, $G[X',Y']$ denotes the subgraph of $G$ induced by the vertices $X'\dot{\cup} Y'$.
The number of vertices in the smaller side of $G$ is denoted by $\underline{n} := \min(|X|,|Y|)$, and the number of edges is denoted by $m := |E|$.
\begin{theorem}
\label{thm:structure}
Every bipartite graph $G = (X \dot{\cup} Y, E)$ admits \emph{unique} partitions $X = X_S\dot{\cup} X_L$ and $Y = Y_S\dot{\cup} Y_L$ satisfying the following three conditions:

(a) There are no edges between $X_S$ and $Y_L$;

(b) The subgraph $G[X_S,Y_S]$ is $Y$-path-saturated;

(c) The subgraph $G[X_L,Y_L]$
is $X$-saturated.

\noindent
These partitions can be found within $O(m\sqrt{\underline{n}})$ time. Moreover:

(d) The subgraph $G[X_L,Y_L]$ admits a matching saturating $X_L$, and this matching is envy-free in $G$.

(e) Every envy-free matching in $G$ is contained in $G[X_L,Y_L]$.
\end{theorem}
For example, in Figure \ref{fig:efm-examples}(a), $G[X_S,Y_S]$ contains the two leftmost edges and $G[X_L,Y_L]$ contains the rightmost (bold) edge, and there is one more edge between $X_L$ and $Y_S$%
.
In Figures \ref{fig:efm-examples}(b,c),
the entire graph is $G[X_S,Y_S]$, while $G[X_L,Y_L]$ is empty.
In an $X$-saturated graph,
the entire graph is $G[X_L,Y_L]$, while $G[X_S,Y_S]$ is empty.

As a corollary of Theorem \ref{thm:structure}, one gets several useful conditions on a graph $G$ admitting a nonempty envy-free matching. The first condition is necessary and sufficient; the other two are only sufficient.%
~~Below,
$N_G(X')$ denotes the neighborhood of a subset $X'\subseteq X$ in $G$, i.e.:
$
N_G(X') := \{y'\in Y: \exists x'\in X' \text{~such that~} (x',y')\in E\}
$.

\begin{corollary}
\label{thm:sufficient}
A bipartite graph $G:=(X \dot{\cup} Y, E)$ admits a nonempty envy-free matching ---

(a) if and only if the bipartite graph $(X\dot{\cup} N_G(X), E)$ is not $Y$-path-saturated;

(b) if $G$ admits no matching saturating $N_G(X)$;

(c) if $|N_G(X)|\geq |X|\geq 1$.%
\end{corollary}
Corollary \ref{thm:sufficient}(a) is interesting since it shows that all the ``bad'' graphs (graphs with no nonempty envy-free matching) are a generalisation of the odd-path example.

Compare Corollary \ref{thm:sufficient}(c)
with Hall's theorem \citep{hall1934representation}, which says that
if (and only if)
$|N_G(X')|\geq |X'|$ for \emph{any} subset $X'\subseteq X$, then $G$ admits an $X$-saturating matching.
The strong condition of Hall is sufficient for the strong property of having an $X$-saturating matching; the weaker condition (c) is sufficient for the weaker property of having a nonempty envy-free matching.

The structure theorem and its corollary are proved in \textbf{Section \ref{sec:pre}}.

Once all envy-free matchings are ``captured'' within a specific subgraph, various optimisation problems on them can be easily solved.
\begin{theorem}
\label{thm:algos}
Given a bipartite graph $G = (X \dot{\cup} Y, E)$,

(a) An envy-free matching of maximum cardinality in $G$ can be found within $O(m\root{\underline{n}})$ time.

(b) If $G$ is endowed with an edge weight function $w : E \to \mathbb{R}_{\geq 0}$, then
an envy-free matching of maximum cardinality and minimum total weight can be found within
$O(m\underline{n}+{\underline{n}}^2 \log {\underline{n}})$ time.
\end{theorem}

The algorithms are presented in \textbf{Section \ref{sec:cardinality}}.

\subsection{Practical aspects: envy-free matching in fair division}
\iffalse
Notions similar to the EFM defined here have been considered in the literature, see e.g. \citet{Kuhn1967Games,procaccia2014fair}.%
\footnote{
The term \emph{envy-free matching} is used with different meanings in two other, more specific contexts.
In the context of Fisher markets, EFM is used as a relaxation of \emph{market equilibrium}, in which some items remain unsold in order to increase the seller's revenue \citep{Guruswami2005Profitmaximising,Alaei2012Competitive}.
In the context of assigning doctors to hospitals,
EFM is used as a relaxation of \emph{stable matching},
in which a hospital may have some vacant positions even though some doctor prefers this hospital over his current  employer \citep{wu2018lattice,yokoi2017envy}.
We present EFM as a general graph-theoretic concept.
}
However, the notion of EFM as it appears here has been obfuscated in various definitions using different terminology and never has a systematic study of this notion been conducted.

We provide a systematic study of EFMs from both the combinatorial and algorithmic perspectives. The latter can then be used as subroutines appearing in algorithms for various {\em fair-division problems}.
\fi

A \emph{fair division problem} is a problem of allocating resources among people with different preferences, such that each person conceives his/her share as ``fair'' according to a pre-specified fairness criterion.

The algorithms of Theorem \ref{thm:algos} directly solve two variants of a problem known as \emph{fair house assignment}. In this problem, the resources are indivisible, each
agent must get at most a single resource,  and the fairness criterion is envy-freeness.
Part (a) solves a variant in which the goal is to maximise the number of agents assigned a house that they like, subject to envy-freeness.
Part (b) solves a variant in which each assignment of an agent to a house has a certain cost for society (e.g. the cost of building the house or of moving the agent to the house), and the goal is to minimise the total cost of the assignment, subject to envy-freeness and maximising the number of assigned agents.
In all variants, it is allowed to leave some houses unallocated.

Interestingly, the same algorithms, combined with Corollary \ref{thm:sufficient},
can be used as subroutines in algorithms for various other fair division problems, both of divisible and of indivisible resources, in which \emph{all} resources must be allocated.
Each of these problems
requires its own notation and definitions. The formal definitions are postponed to Section \ref{sec:app}; below results are presented informally.

For a \emph{divisible} resource (``cake''), we
focus on a fairness criterion called \emph{proportionality}, which means that each agent must get a piece worth for it at least a fraction $1/n$ of the total cake value.
There are various algorithms for proportional cake division,
but most of them are not \emph{symmetric} --- the same agent might get a different value when playing first vs. playing second.
This may lead to quarrels regarding who will play first.
\citet{cheze2018don} presented an exponential-time symmetric algorithm for proportional cake division, and asked whether a polynomial-time algorithm exists. The following theorem answers his question.
\begin{theorem}
\label{thm:symmetric}
There is a \emph{symmetric} and \emph{polynomial-time} algorithm that, given a divisible resource (``cake'') and $n$ agents with additive valuations over subsets of the cake,
partitions the \emph{entire} cake among the agents, such that the value of each agent is at least $1/n$ of the total cake value.
\end{theorem}

For \emph{indivisible} objects, we focus on a fairness criterion called \emph{1-out-of-$k$ maximin-share}, which means that each agent weakly prefers its allocated bundle over the outcome of partitioning the objects into $k$ subsets and getting the worst subset.
\citet{procaccia2014fair} proved that a 1-out-of-$n$ maximin-share allocation may not exist for $n\geq 3$ agents, and asked whether a 1-out-of-$(n+1)$ maximin-share allocation exists.
The following theorem makes a step towards an answer.
\begin{theorem}
\label{thm:2n-2}
Given a set of indivisible objects, and $n$ agents with additive valuations over the objects, there is a protocol that partitions \emph{all} the objects among the agents, such that the value of each agent is at least its 1-out-of-$(2n-2)$ maximin-share.
\end{theorem}
The same algorithm may allow each agent to choose between different related fairness criteria, such as $2$-out-of-$(3n-2)$ maximin-share, $2/3$-fraction maximin-share, etc. (see \textbf{Section \ref{sec:app}} for details).
Thus, the main contribution of this paper lies not in solving a specific fair division problem, but rather in presenting a tool --- envy-free matching --- that can be applied as a subroutine in various kinds of fair division problems.

Some open questions for future work are presented in \textbf{Section \ref{sec:future}}.

\section{Envy-free matchings and structure of graphs}
\label{sec:pre}
This section proves Theorem \ref{thm:structure} regarding the structure of bipartite graphs. The main technical tool used is the \emph{alternating sequence}.

\begin{figure}
\begin{center}
\includegraphics[height=4cm,width=7cm]{alternating-sequence-x}
\end{center}
\caption{
\label{fig:alternating-sequence}
A maximal $M$-alternating sequence $\mathcal{S}(M,X_0)$ and the induced partitions.
\\
The heavy vertical edges are edges of the underlying matching $M$.
The heavy diagonal edges are
edges of $G\setminus M$ used in constructing  the alternating sequence.
The light diagonal (gray) edges are
edges of $G\setminus M$ not used in the construction.
}
\end{figure}
\begin{definition}
Let $M$ be a matching in a bipartite graph $G:=(X \dot{\cup} Y, E)$.
Let $X_0\subset X$ be a subset of vertices unmatched by $M$.  An \emph{$M$-alternating sequence starting at $X_0$} is a sequence of pairwise-disjoint subsets of vertices
$
X_0 - Y_1 - X_1 - Y_2 - X_2 - \cdots
$
where for each $i\geq 1$:%
\footnote{
The $M$-alternating sequence is closely related to the \emph{$M$-alternating path} --- a sequence of vertices $x_0 - y_1 - x_1 - ...$ where each even edge is in $M$ and each odd edge is not in $M$ (or vice versa).
The difference is that the elements in an $M$-alternating sequence are \emph{subsets} of vertices rather than single vertices.
}
\begin{itemize}
\item $Y_{i} = N_{G\setminus M} (X_{i-1}) ~ \setminus ~ (\cup_{j<i}Y_j)$;
\item $X_{i} = N_{M} (Y_i)$.
\end{itemize}
\end{definition}

Given $M$ and $X_0$, an $M$-alternating sequence starting at $X_0$ can be easily constructed in linear time. Since the graph is finite, this construction eventually yields an empty subset --- either $X_i$ or $Y_i$ for some $i$. Denote by $\mathcal{S}(M,X_0)$ the maximal $M$-alternating sequence starting at $X_0$ and ending before the first $\emptyset$.
This $\mathcal{S}(M,X_0)$ induces a partition of the graph as follows (See Figure \ref{fig:alternating-sequence}):
\begin{itemize}
\item $X = X_S \dot{\cup} X_L$, where $X_S := \cup_{i\geq 0} X_i$ = the vertices of $X$ participating in the sequence, and $X_L := X\setminus X_S$ = the Leftover vertices.
\item $Y = Y_S \dot{\cup} Y_L$, where $Y_S := \cup_{i\geq 1} Y_i$ and $Y_L := Y\setminus Y_S$.
\end{itemize}
When $M$ has maximum cardinality, its alternating sequences have some useful properties.%
\footnote{
The vertices of $X_L$ are exactly the vertiecs of $X$ that are unreachable from $X_0$ in $M$-alternating paths.
Thus $X_L$ is reminiscent of the ``unreachable'' set in the Dulmage-Mendelsohn decomposition \citep{irving2006rank,pulleyblank1995matchings}.
However, the reachability in the Dulmage-Mendelsohn decomposition is from the set of \emph{all} unsaturated vertices, while the reachability in our case is only from $X_0$ --- the set of unsaturated vertices in $X$.
}

\begin{lemma}
\label{lem:alternating-sequence}
Let $M$ be a maximum-cardinality matching in $G=(X\dot{\cup} Y,E)$ and $X_0$ the subset of $X$ unmatched by $M$.
Consider the partitions $X = X_S \dot{\cup} X_L$ and $Y = Y_S \dot{\cup} Y_L$ induced by the maximal alternating sequence $\mathcal{S}(M,X_0)$. Then:

(a) There are no edges between $X_S$ and $Y_L$;

(b) The subgraph $G[X_S,Y_S]$ is $Y$-path-saturated;

(c) The subgraph $G[X_L,Y_L]$
is $X$-saturated.
\end{lemma}
\begin{proof}
\textbf{Part (a).} By construction, the set $Y_S$ is exactly the set of  neighbors of $X_S$ in $G$.

\textbf{Part (b).} We first prove that $M[X_S,Y_S]$ --- the subset of $M$ contained in $G[X_S,Y_S]$ --- saturates $Y_S$.

\noindent
Indeed, if, for some $i\geq 1$, some vertex $y_i\in Y_i$ were unmatched by $M$, then an $M$-augmenting path could be traced along the edges used in the construction of $\mathcal{S}(M,X_0)$, namely: $y_i - X_{i-1} - Y_{i-1} - \cdots - X_0$, where the last vertex is unmatched. This would contradict the maximality of $M$.
Hence, all vertices of $\cup_{i\geq 1} Y_i = Y_S$ are matched by $M$.
By construction, the set of their matches in $M$ is $\cup_{i\geq 1} X_i\subseteq X_S$.

This implies that the construction of $\mathcal{S}(M,X_0)$ ends at the $X$ side, i.e., it ends at $X_k$ for some $k\geq 0$.
Now, the partitions $X_S = X_0 \dot{\cup} \cdots \dot{\cup} X_k$ and $Y_S = Y_1 \dot{\cup} \cdots \dot{\cup} Y_k$
satisfy the definition of a $Y$-path-saturated graph
(Definition \ref{def:snake}): for every $i\geq 1$, every vertex in $Y_i$ is adjacent to some vertex in $X_{i-1}$,
and there is a perfect matching between $X_i$ and $Y_i$ (along edges of $M$).

\textbf{Part (c).}
We prove that $M[X_L,Y_L]$ --- the subset of $M$ contained in $G[X_L,Y_L]$ --- saturates $X_L$.

\noindent
Indeed,
By the lemma assumption, all vertices of $X$ unmatched by $M$ are contained in $X_0\subseteq X_S$, so all vertices of $X_L$ are matched by $M$. By construction, they must be matched to vertices not in any $Y_i$, so their matches must all lie inside $Y_L$.
\end{proof}

Note that, in the special case in which $G$ is $X$-saturated, the maximum matching $M$ saturates $X$, so $X_0$ is empty and so the $M$-alternating sequence is empty. In this case, $X_L = X$ and $Y_L = Y$.

The following lemma relates the three properties (a),(b),(c) above to envy-free matchings.

\begin{lemma}
\label{lem:enclosure-efm}
Let $G = (X\dot{\cup} Y, E)$, and consider any partitions
$X = X_S \dot{\cup} X_L$ and $Y = Y_S \dot{\cup} Y_L$
satisfying properties (a), (b) and (c) of Lemma \ref{lem:alternating-sequence}.
Then:

(d) The subgraph $G[X_L,Y_L]$ admits a matching saturating $X_L$, and this matching is envy-free in $G$.

(e) Every envy-free matching in $G$ is contained in $G[X_L,Y_L]$.
\end{lemma}
Note that Lemma \ref{lem:enclosure-efm} does not refer to any particular matching $M$ --- it holds for any partitions of $X$ and $Y$ that satisfy the properties (a),(b),(c) above.

\begin{proof}[Proof of Lemma \ref{lem:enclosure-efm}]
~

\textbf{Part (d).}
By property (c), $G[X_L,Y_L]$ admits a matching saturating $X_L$. Denote this matching by $W$. Since $W$ saturates $X_L$, no vertex of $X_L$ is envious.
By property (a), there are no edges between $X_S$ and $Y_L$. Since only vertices of $Y_L$ are matched by $W$, no vertex of $X_S$ is envious. Hence, no vertex of $X$ is envious, so $W$ is an envy-free matching in $G$.

\textbf{Part (e).}
Let $W$ be any envy-free matching in $G$.
Let $X_{SW} := X_S\cap V(W)$ and $Y_{SW} := Y_S \cap V(W)$. We have to prove that both $X_{SW}$ and $Y_{SW}$ are empty.
By property (a), vertices of $X_{SW}$ can only be matched to vertices of $Y_{SW}$, so it is sufficient to prove that $Y_{SW}$ is empty.

The proof is by a counting argument. Let $k_{SW} := |Y_{SW}|$ and assume by contradiction that $k_{SW} > 0$.

By property (b), the graph $G[X_S,Y_S]$ is $Y$-path-saturated; denote the partitions appearing in Definition \ref{def:snake} by
$X_S = X_0 \dot{\cup} \cdots \dot{\cup} X_k$ and $Y_S = Y_1 \dot{\cup} \cdots \dot{\cup} Y_k$.
Let $i\geq 1$ be the smallest index such that a vertex of $Y_i$ is matched by $W$, so that $Y_{SW} \subseteq \cup_{j\geq i} Y_j$.
By Definition \ref{def:snake}, all vertices of $Y_{SW}$ are perfectly matched to vertices of $\cup_{j\geq i} X_j$;
denote their matches by $X_{SW}'$. Note that
$|X_{SW}'| = k_{SW}$.
Every vertex $x\in X_{SW}'$ is adjacent (along an edge of the perfect matching) to a vertex of $Y_{SW}$, which is saturated by $W$. To ensure that $x$ is not envious, $x$ must be saturated by $W$ too.

Let $y'$ be a vertex in $Y_i\cap Y_{SW}$. By Definition \ref{def:snake}, it is adjacent to some vertex $x'\in X_{i-1}$.
To ensure that $x'$ is not envious, $x'$ must be saturated by $W$ too. But $x'\not\in X_{SW}'$ since $X_{SW}'\subseteq \cup_{j\geq i} X_j$.
Hence, there must be at least $k_{SW}+1$ vertices of $X_S$ that are saturated by $W$: the $k_{SW}$ vertices of $X_{SW}'$, plus the vertex $x'$ which is not in $X_{SW}'$.
But this is a contradiction, since vertices of $X_S$ can be matched only to vertices of $Y_S$, and only $k_{SW}$ vertices of $Y_S$ are matched by $W$.
\end{proof}

We now have all the ingredients required to prove Theorem \ref{thm:structure}.

\begin{proof}[Proof of Theorem \ref{thm:structure}]
Given a bipartite graph $G = (X \dot{\cup} Y, E)$,
a maximum matching $M$ in $G$ can be found using the classic algorithm of \citet{HK73}.
\citet{RT12} show that this algorithm runs within $O(m \root{\underline{n}})$ time.
Given $M$, its maximal $M$-alternating sequence can be found in linear time, yielding the partitions $X = X_S \dot{\cup} X_L$ and $Y = Y_S \dot{\cup} Y_L$.

Lemma \ref{lem:alternating-sequence} shows that these partitions satisfy parts (a), (b) and (c) of Theorem \ref{thm:structure}.
Lemma \ref{lem:enclosure-efm} then shows that parts (d) and (e) are satisfied too.

It remains to prove that the partitions are unique.
Consider alternative partitions $X = X_S' \dot{\cup} X_L'$ and $Y = Y_S'\dot{\cup} Y_L'$ satisfying properties (a), (b) and (c).
Applying Lemma \ref{lem:enclosure-efm}(d) to the partition $X_S,X_L,Y_S,Y_L$ implies that there is an envy-free matching in $G$ saturating $X_L$.
Applying Lemma \ref{lem:enclosure-efm}(e) to the partition $X_S',X_L',Y_S',Y_L'$ implies that this matching must be contained in $G[X_L',Y_L']$; in particular, $X_L\subseteq X_L'$.
Analogous arguments imply that $X_L'\subseteq X_L$. Hence $X_L' = X_L$.
Hence also $X_S' = X_S$.
~~
Since $Y_S = N_G(X_S)$
and $Y_S' = N_G(X_S')$, we also have $Y_S' = Y_S$.
Hence also $Y_L' = Y_L$.
\end{proof}

We now apply Theorem \ref{thm:structure} to prove three conditions for existence of nonempty envy-free matchings.

\begin{proof}[Proof of Corollary \ref{thm:sufficient}]
~\\
\textbf{Part (a).}
Consider the unique partitions $X = X_S\dot{\cup} X_L$ and $Y = Y_S\dot{\cup} Y_L$ that exist by Theorem \ref{thm:structure}.
Parts (d,e) of this theorem imply that $G$ admits a nonempty envy-free matching iff $X_L$ is nonempty.
Hence it is sufficient to show that
the graph
$(X\dot{\cup} N_G(X), E)$ is $Y$-path-saturated iff
$X_L$ is empty.

If $X_L$ is empty, then $X = X_S$ and $N_G(X) = Y_S$, so the graph $(X\dot{\cup} N_G(X), E)$ is $Y$-path-saturated.

Conversely, suppose $(X\dot{\cup} N_G(X), E)$ is $Y$-path-saturated, and define $X_S' := X$ and $X_L' := \emptyset$ and $Y_S' := N_G(X)$ and $Y_L' := Y\setminus N_G(X)$.
Then, the partitions $X = X_S' \dot{\cup} X_L'$
and $Y = Y_S' \dot{\cup} Y_L'$ satisfy all three properties (a,b,c) of Theorem \ref{thm:structure}.
The uniqueness of the partition implies that, in particular, $X_L = X_L'$. Hence, $X_L$ is empty.

\textbf{Part (b).} If $G$ admits no matching saturating $N_G(X)$, then $(X, N_G(X))$ cannot be $Y$-path-saturated.
So by part (a), $G$ admits a nonempty envy-free matching.

\textbf{Part (c).} If $|N_G(X)|\geq |X|\geq 1$,
then $(X, N_G(X))$ cannot be $Y$-path-saturated,
since in any such graph the $X$ side is larger than the $Y$ side.
By part (a), $G$ admits a nonempty envy-free matching.
\end{proof}

\section{Algorithms for finding envy-free matchings}
\label{sec:cardinality}
This section
applies the structural results of the previous section to prove Theorem \ref{thm:algos}.

\subsection{Maximum cardinality}
\begin{proof}[Proof of Theorem \ref{thm:algos}(a)]
We claim that Algorithm \ref{alg:cardinality} finds a maximum-cardinality envy-free matching.
Indeed, by Lemmata \ref{lem:alternating-sequence} and
\ref{lem:enclosure-efm},
the matching $M[X_L,Y_L]$ is envy-free and saturates $X_L$, and any other envy-free matching cannot saturate any vertex outside $X_L$. Hence $M[X_L,Y_L]$ is an envy-free matching of maximum cardinality in $G$.
The run-time is dominated by step 1, which can be done using the Hopcroft-Karp algorithm within $O(m\sqrt{\underline{n}})$ time \citep{RT12}.
\end{proof}

\begin{algorithm}[t]
\caption{Finding an envy-free matching of maximum cardinality}
\label{alg:cardinality}
\begin{algorithmic}[1]
\REQUIRE A bipartite graph $G:= (X \dot{\cup} Y,E)$.
\ENSURE An envy-free matching of maximum cardinality in $G$.
\STATE Find a maximum-cardinality matching $M$ in $G$.
\STATE Compute the $M$-alternating sequence $\mathcal{S}(M,X_0)$ and the partitions $X=X_S\dot{\cup} X_L,~Y=Y_S\dot{\cup} Y_L$.
\STATE Return the sub-matching $M[X_L,Y_L]$.
\end{algorithmic}
\end{algorithm}
As an example, when Algorithm \ref{alg:cardinality} runs on the graph of Figure \ref{fig:alternating-sequence}, it returns an envy-free matching of size $2$, containing the two rightmost vertical edges.

\subsection{Minimum weight}
\label{sub:weight}

In this subsection, the graph $G:=(X \dot{\cup} Y,E)$ is endowed with an edge-weighting function $w:E \to \mathbb{R}_{\geq 0}$.
The \emph{weight} of a matching $M\subseteq G$ is defined as $w(M) := \sum_{e\in M} w(e)$.
The goal is to find a matching that minimises $w$ over all envy-free matchings of maximum cardinality in $G$.

Without the envy-freeness constraint, finding a minimum-cost maximum-cardinality matching is known as the \emph{assignment problem}.
Since $X$ and $Y$ may be of different sizes, it is an \emph{unbalanced assignment problem}.
\citet{RT12} provide a comprehensive survey of algorithms for the unbalanced assignment problem.
In particular, they show that the famous Hungarian method can be generalised to unbalanced bipartite graphs, and its run-time is $O(m\cdot \underline{n} + {\underline{n}}^2 \log{\underline{n}})$.

\begin{proof}[Proof of Theorem \ref{thm:algos}(b)]
We claim that Algorithm \ref{alg:weight} finds a maximum-cardinality envy-free matching of minimum total weight.
Indeed, by Theorem \ref{thm:structure},
all envy-free matchings in $G$ are contained in the subgraph $G[X_L,Y_L]$, and all maximum-cardinality matchings in $G[X_L,Y_L]$ saturate $X_L$ and are therefore envy-free.
Hence, the Hungarian method on $G[X_L,Y_L]$ yields a maximum-cardinality envy-free matching of minimum weight in $G$.
Since $|X_L|\leq |Y_L|$, the run-time of the Hungarian method is $O(m\cdot |X_L| + {|X_L|}^2 \log{|X_L|})$ which is in
$O(m\cdot \underline{n} + {\underline{n}}^2 \log{\underline{n}})$.
\end{proof}

\begin{algorithm}[t]
\caption{Finding envy-free matchings of minimum weight}
\label{alg:weight}
\begin{algorithmic}[1]
\REQUIRE A bipartite graph $G:= (X \dot{\cup} Y,E)$ and a function $w : E \to \mathbb{R}_{\geq 0}$.
\ENSURE An envy-free matching of minimum weight.
\STATE Let $M$ be a matching of maximum cardinality in $G$.
\STATE Compute the $M$-alternating sequence $\mathcal{S}(M,X_0)$ and the partitions $X=X_S\dot{\cup} X_L,~Y=Y_S\dot{\cup} Y_L$.
\STATE Find and return a minimum-weight maximum-cardinality matching in $G[X_L,Y_L]$.
\end{algorithmic}
\end{algorithm}

\subsection{Maximum weight}
Algorithm \ref{alg:weight} can be
modified to yield an envy-free matching of \emph{maximum} total weight.
The unbalanced Hungarian method can be easily adapted to find an $X$-saturating matching of maximum weight \citep{RT12}.
The following lemma shows that, in step 3, it is sufficient to consider the $X_L$-saturating matchings.

\begin{lemma}\label{lem:x-saturating}
Let $G:=(X \dot{\cup} Y,E)$ be an $X$-saturated bipartite graph.
Let $W$ be an envy-free matching in $G$.
Then, $W$ is contained in some $X$-saturating matching.
\end{lemma}
\begin{proof}
Let $M$ be an $X$-saturating matching in $G$.
For each vertex $x\in X$, denote by $N_M(x)$ the vertex in $Y$ matched to it by $M$.
Let $M' := \{(x,N_M(x)): x\text{ is unsaturated by }W\}$,

Envy-freeness of $W$ implies that,
for any vertex $x\in X$ unsaturated by $W$, $N_M(x)$ must be unsaturated by $W$ too.
Hence, $W\cup M'$ is a matching. It saturates $X$ and it contains $W$.
\end{proof}
Hence, by taking
Algorithm \ref{alg:weight} and replacing ``minimum-weight'' by ``maximum-weight'',
one gets an algorithm for finding a maximum-weight envy-free matching.
The proof is the same as of Theorem \ref{thm:algos}(b).

\begin{remark}
The above discussion assumes that the weight $w(x,y)$ represent the value of the pairing $(x,y)$ to ``society'' as a whole (or to the social planner). Therefore it appears in the maximisation objective but not in the envy definition.

An alternative interpretation is that $w(x,y)$ represents the subjective value of $y$ to $x$. This interpretation leads to a different definition of envy-freeness. Given an edge-weight-function $w$ and a matching $M$,
define:

\begin{align*}
w(x, M) =
\begin{cases}
w(x,y) & \text{If $(x,y)\in M$}
\\
0 & \text{If $x$ is unmatched by $M$}
\end{cases}
\end{align*}
A matching $M\subseteq E$ is called \emph{$w$-envy-free} if,
for every vertex $x\in X$ and every matched vertex $y'\in Y_M$: $w(x,M) \geq w(x,y')$, i.e, every agent in $X$ weakly prefers his/her own house (if any) to any house assigned to another agent.
This definition reduces to Definition \ref{def:efm} when all edges have the same weight.

The problem of finding a $w$-envy-free matching has been studied in parallel to the present work.
\citet{gan2019envy} present a polynomial-time algorithm for finding
a $w$-envy-free matching that saturates \emph{all} vertices of $X$, if and only if such a matching exists.
\citet{beynier2019local}
solve a similar problem in a more complex setting in which the agents are located on a network, and each agent only envies his/her neighbors in the network.
In contrast to our work,
these two works do not consider partial matchings (matchings that do not saturate $X$).
Therefore, the problem of finding a $w$-envy-free (partial) matching of maximum cardinality and/or maximum weight is still open.
\end{remark}

\begin{remark}
\citet{irving2006rank} present an algorithm for finding a \emph{rank-maximal} matching --- a matching that maximises the number of agents who are matched to their first choice, then the number of agents who are matched to their second choice, etc.
A matching that is rank-maximal among the set of all envy-free matchings can be found by an algorithm similar to Algorithm \ref{alg:weight}: in the last step, instead of solving the unbalanced assignment problem, apply the algorithm of \citet{irving2006rank} to $G[X_L,Y_L]$.
\end{remark}

\section{Related Work and Applications}
\label{sec:app}
Concepts similar to envy-free matching appeared in previous papers related to fair division, but they were ``hidden'' inside proofs of more specific algorithms.
Our presentation of envy-free matching as a stand-alone graph-theoretic concept allows us to both simplify old algorithms and design new ones. This is illustrated below for two kinds of fair division problems: cake-cutting and indivisible object allocation.

\subsection{Envy-free matching in fair cake-cutting}
As far as we know, the earliest concept similar to envy-free matching was presented by \citet{Kuhn1967Games}[unnumbered lemma, page 31]. Kuhn presents the lemma in matrix form. In graph terminology, his lemma says that an envy-free matching exists whenever $|X|=|Y|$ and there is a vertex $x\in X$ for whom $N_G(\{x\}) = |Y|$. This is a special case of our Corollary \ref{thm:sufficient}(c). Kuhn uses this lemma to extend an algorithm of \citet{Steinhaus1948Problem} for \emph{fair cake-cutting}.

In a \emph{fair cake-cutting} problem, there is a heterogeneous and continuous resource $C$ (named  ``the cake''), usually represented by the real interval $[0,1]$. There are $n$ agents. Each agent $i$ has a nonatomic measure $V_i$ on $C$, representing the agent's valuation of different parts of $C$. A \emph{proportional division} of $C$ is a partition into $n$ pieces, $C = Z_1 \dot{\cup} \cdots \dot{\cup} Z_n$, such that for all $i\in[n]: V_i(Z_i)\geq V_i(C)/n$.

There are various algorithms for proportional cake-cutting.
One of them is now called the \emph{Lone Divider} algorithm.
Steinhaus presented it for $3$ agents. Kuhn \citep{Kuhn1967Games} extended it to an arbitrary number of agents.
The cases $n=3$ and $n=4$ are described in detail by \citet{Brams1996Fair}[pages 31-35], and
 the general case is described in detail by \citet{Robertson1998CakeCutting}[pages 83-87].
Using envy-free matching, the Lone Divider algorithm can be presented in a much shorter way; see Algorithm \ref{alg:lone-divider}.

\begin{algorithm}
\caption{
\label{alg:lone-divider}
The Lone Divider algorithm for proportional cake-cutting.
Based on \citet{Kuhn1967Games}.
}
\begin{algorithmic}[1]
\REQUIRE A cake $C$ and a set $X = [n]$ of agents with nonatomic measures $(V_i)_{i=1}^n$ on $C$.
The measures are normalized such that $\forall i\in [n]: V_i(C) = n$.
\ENSURE A partition $C = Z_1\dot{\cup}\cdots\dot{\cup} Z_n$ such that $\forall i\in [n]: V_i(Z_i)\geq 1$.
\STATE
\label{step:ld-cut}
Let $a\in X$ be the agent with the smallest index in $X$. ask $a$ to cut $C$ into $|X|$ disjoint pieces, $(C_j)_{j\in X}$, with $V_a(C_j)\geq 1$ for all $j\in X$.
\STATE
\label{step:ld-graph}
Define a bipartite graph $G$ with the agents of $X$ on the one side and the $|X|$ pieces on the other side. Add an edge between agent $i$ and piece $C_j$ whenever $V_i(C_j)\geq 1$.
\STATE
\label{step:ld-efm}
Using Algorithm \ref{alg:cardinality},
find a maximum-cardinality envy-free matching in $G$.
Give each matched piece to its agent.
\STATE
\label{step:ld-remove}
Remove
the matched agents from $X$
and
the matched pieces from $C$.
\STATE
\label{step:ld-recurse}
If $X\neq\emptyset$,
go back to step \ref{step:ld-cut}.
\end{algorithmic}
\end{algorithm}
To show the correctness of Algorithm \ref{alg:lone-divider},
it is required to show that in step \ref{step:ld-cut}, each agent $a\in X$ can indeed cut $C$ into $|X|$ pieces worth for it at least $1$.
Equivalently, we show that, in each arrival of the algorithm at step \ref{step:ld-cut},
$V_a(C)\geq |X|$ for all $a\in X$.
This is certainly true in the first arrival, since then $|X|=n$ and $V_a(C)=n$ by the input assumptions. Then:

\begin{itemize}
\item In step \ref{step:ld-cut}, $V_a(C)\geq |X|$, so for each piece $Z_i$,  $V_a(Z_i)\geq 1$.
\item In step \ref{step:ld-graph}, agent $a$ is adjacent to all $|X|$ pieces, so $|N_G(X)| \geq |X|$ holds.
\item In step \ref{step:ld-efm},
by Corollary \ref{thm:sufficient}, a nonempty envy-free matching is found.
Each matched agent receives a piece with a value of at least $1$, so the division is proportional for that agent.
\item In step \ref{step:ld-remove},
let $k\geq 1$ be the matching size.
The $k$ matched agents are removed from $X$, so $|X|$ decreases by $k$.
The $k$ matched pieces are removed from $C$, and by envy-freeness, each remaining agent values each removed piece at less than $1$, so the value of $C$ decreases by less than $k$.
Hence, the claim still holds%
 : for each agent $a\in X: V_a(C)\geq |X|$.
\end{itemize}

One may wonder why is the Lone Divider algorithm needed when there are many other algorithms for proportional cake-cutting  \citep{Brams1996Fair,Even1984Note,Robertson1998CakeCutting,Steinhaus1948Problem}?

One reason is that Lone Divider
can be modified to be not only fair but also \emph{symmetric}. A fair division algorithm is called \emph{symmetric} if the value each agent receives depends only on the valuations of the agents, and not on the order in which the algorithm processes them. In other words, if we run the algorithm, permute the agents, and run the algorithm again, every agent will have the same value in both runs.
Most cake-cutting algorithms are not symmetric.
For example, in the Lone Divider algorithm, agent \#1 (the divider) always receives exactly $1/n$ of the total value, while other agents may get more than $1/n$.%
\footnote{
It is assumed here that the agents answer the queries truthfully, based on their real value measure.
}
This might make the agents quarrel over who the divider will be.
Selecting the divider by tossing a coin is not an acceptable solution, since cake-cutting algorithms aspire for fairness ex-post and not just ex-ante (ex-ante fairness can be attained trivially by giving the whole cake to an agent selected uniformly at random).

\citet{Manabe2010MetaEnvyFree} presented deterministic symmetric algorithms for two and three agents.
The case $n\geq 4$ remained open until
\citet{cheze2018don} presented a deterministic symmetric algorithm for any number of agents.
Ch{\`e}ze mentions that the number of arithmetic operations required by his algorithm may be exponential in $n$, and asks whether there exists a deterministic symmetric algorithm in which
the number of arithmetic operations required is polynomial in $n$.
We answer his question in the affirmative by combining his algorithm with our Algorithm \ref{alg:weight} for minimum-weight envy-free matching.
The combined algorithm is shown as Algorithm
\ref{alg:symmetric-proportional}.

\begin{figure}
\begin{center}
\includegraphics[height=3.5cm,width=9cm]{symmetric-algorithm.pdf}
\end{center}
\caption{\label{fig:symmetric-algorithm}
Bipartite agent-piece graph with weights determined by Algorithm \ref{alg:symmetric-proportional}.
\\~
The numbers below the pieces in $Y$ and above the agents in $X$ are their weights.
Each piece has a unique weight, while each agent has a weight that is a 1-to-1 function of its set of neighbors.
The two leftmost agents have the same set of neighbors so they have the same weight (0); the two agents adjacent to them have the same set of neighbors so they have the same weight (1); the rightmost agent has a different set of neighbors.
\\
The numbers on the edges are their weights (due to space constraints, only some of weights are written).
}
\end{figure}
\begin{algorithm}
\caption{
\label{alg:symmetric-proportional}
A symmetric algorithm for proportional cake-cutting.
Based on \citet{cheze2018don}.
}
\begin{algorithmic}[1]
\REQUIRE A cake $C = [0,1]$, and a set $X = [n]$ of agents with nonatomic measures $(V_i)_{i=1}^n$ on $C$.
The measures are normalized such that $\forall i\in [n]: V_i(C) = n$.
\ENSURE A partition $C = Z_1\dot{\cup}\cdots\dot{\cup} Z_n$ such that $\forall i\in [n]: V_i(Z_i)\geq 1$.
\STATE
\label{step:sp-mark}
Ask each agent $i\in X$ to make $n-1$ marks,
$0 < z_{i,1} < \ldots < z_{i,n-1} < 1$, which partition $C$ into $n$ sub-intervals with a value of exactly $1$ for $i$.
\STATE
\label{step:sp-lex}
Choose the vector of marks that is smallest in lexicographic order. Cut $C$ by these marks.
Denote the resulting pieces by $C_{1},\ldots,C_n$.
\STATE
\label{step:sp-graph}
Define a bipartite graph $G$ with the agents of $X$ on the one side and the pieces (denoted by $Y$) on the other side. Add an edge $(i, C_j)$ whenever $V_i(C_j)\geq 1$.
\STATE
\label{step:sp-weight-x}
Assign to each agent $i\in X$ a weight $w(i)\range{0}{n-1}$ that is a function of the set of neighbors $N_G(i)$, such that two agents $i,i'\in X$ have the same weight iff $N_G(i)=N_G(i')$.
\STATE
\label{step:sp-weight-y}
Assign to each piece $C_j\in Y$ a unique weight $w(C_j)\range{0}{n-1}$,
such that the weight of the leftmost piece (adjacent to $0$) is $0$, the weight of the next-leftmost piece is $1$, etc.
\STATE
\label{step:sp-efm}
Assign to each edge $(i, C_j)\in E$
the weight $w(i,C_j) := 2^{n\cdot w(i) + w(C_j)}$.
Using Algorithm \ref{alg:weight},
find a minimum-weight maximum-cardinality envy-free matching $M$ in $G$.
\STATE
\label{step:sp-give}
Let $X_Y\subseteq X$ be the set of all agents that are adjacent to all pieces in $Y$ (i.e., the agents $i\in X$ with $N_G(i) = Y$).
Give each agent in $X_Y$ an arbitrary piece from $N_M(X_Y)$.
\STATE
\label{step:sp-partition}
Let $X_R := X_M \setminus X_Y$.
Partition $X_R$ into subsets of agents with the same weight. I.e., for some $k\geq 1$, find a partition
$X_R = X_1\dot{\cup} \cdots \dot{\cup} X_k$,
where for all $j\in[k]$, for all $i,i'\in X_j$, $w(i)=w(i')$.
\STATE
\label{step:sp-recurse-high}
For all $j\in[k]$, recursively divide the union of pieces in $N_M(X_j)$ among the agents in $X_j$.
\STATE
\label{step:sp-recurse-low}
Recursively divide the union of pieces in $Y\setminus Y_M$ among the agents in $X\setminus X_M$.
\end{algorithmic}
\end{algorithm}

The first change from Lone Divider is that the initial partition should be decided in a way that depends only on the valuations. This is done in step \ref{step:sp-lex} using lexicographic ordering. For example, if Alice cuts the cake at $0.3,0.7$, Bob cuts at $0.4,0.6$ and Carl at $0.2,0.6$, then the initial partition is Carl's partition, so $C_1 = [0,0.2]$ and $C_2=[0.2,0.6]$ and $C_3 = [0.6,1]$.

The second change is in steps
\ref{step:sp-weight-x}--\ref{step:sp-efm}.
Since there may be many different envy-free matchings, one of them must be selected in a way that depends only on the valuations.
One way to select a unique envy-free matching is to assign to each edge, a weight that is a unique power of two. This guarantees that each subset of edges has a unique weight, so there is a unique minimum-weight maximum-cardinality envy-free matching.
However, symmetry requires that the edge weights themselves should depend only on the valuations.
Therefore, edges may have different weights only if they are adjacent to different pieces (since the pieces depend only on the valuations), or to agents with different valuations.
This motivates the weighting scheme in
steps
\ref{step:sp-weight-x}--\ref{step:sp-efm}.
An example of a graph with some edge weights is shown in
Figure \ref{fig:symmetric-algorithm}.

In the special case that each agent has a unique set of neighbors, the agent weights are unique, the edge weights are unique powers of two, each matching has a unique weight, and thus the minimum-weight envy-free matching $M$ found in step \ref{step:sp-efm} is uniquely determined by the valuations.
In this special case,
the algorithm can just proceed as in Algorithm \ref{alg:lone-divider}: give each piece in $Y_M$ to the agent matched to it in $X_M$, and recursively divide the remaining cake --- the union of pieces in $Y\setminus Y_M$ --- among the remaining agents in $X\setminus X_M$.

In the general case, there may be several different
minimum-weight envy-free matchings, and
step \ref{step:sp-efm} returns one of them, in a way that may depend on the agents' order.
Therefore, to preserve symmetry, care must be taken to ensure that the agents' values are not sensitive to the minimum-weight matching selected.
Note that all these minimum-weight matchings have the same set $X_M$ of matched agents --- it is exactly the set $X_L$ defined by the unique partition of Theorem \ref{thm:structure}.
Moreover, by the determination of edge weights, all these matchings have the same set $Y_M$ of matched pieces.
So the sets $X_M$ and $Y_M$ are uniquely determined by the valuations; only the pairing of agents in $X_M$ with pieces in $Y_M$ is not uniquely determined and must be handled in the following steps.

Consider first the set $X_Y$ defined in step \ref{step:sp-give}.
Note that it contains at least one agent --- the agent responsible to the lexicographically-smallest partition selected in step \ref{step:sp-lex}
(in Figure \ref{fig:symmetric-algorithm}, the set $X_Y$ contains the two agents with weight 1).
By envy-freeness of $M$, all agents in $X_Y$ are matched by $M$.
By the determination of edge weights,
all minimum-weight envy-free matchings $M'$ in $G$ have the same set $N_{M'}(X_Y)$, i.e., in all these matchings, the same pieces are allocated to the agents in $X_Y$.
Since all agents in $X_Y$ value all pieces in $Y$ at exactly $1$,
it is possible to give each agent in $X_Y$ an arbitrary piece in $N_M(X_Y)$, for example, based on the agents' indices. This arbitrary choice does not affect the value of any agent; all agents in $X_Y$ are treated symmetrically.

Consider now the sets $X_1,\ldots,X_k$ defined in step \ref{step:sp-partition}
(in Figure \ref{fig:symmetric-algorithm} there are two such sets: the set $X_1$ contains the two leftmost agents whose weight is $0$, and the set $X_2$ contains the rightmost agent whose weight is $2$).
For each $j\in[k]$, all agents in $X_j$ have the same weight, so they have the same set of neighbors.
Hence, by envy-freeness of $M$,
if one agent in a set $X_j$ is matched by $M$, then all agents in $X_j$ must be matched by $M$ too.
By the determination of edge weights,
all minimum-weight envy-free matchings $M'$ in $G$ have the same set $N_{M'}(X_j)$, i.e., in all these matchings, the same pieces are allocated to the agents in $X_j$.
Here, it is not possible to give each agent in $X_j$ an arbitrary piece in $N_M(X_j)$, since each agent in $X_j$ may value the pieces in $N_M(X_j)$ differently.
However, by definition of the graph $G$, all agents in $X_j$ value each piece in $N_M(X_j)$ at least $1$, so they value the union of $N_M(X_j)$
at least $|X_j|$. Therefore,
by recursively dividing the union of
$N_M(X_j)$ among the agents in $X_j$,
each agent in $X_j$ is guaranteed a value of at least $1$. All agents in $X_j$ are treated symmetrically.

Finally, step \ref{step:sp-recurse-low} of Algorithm \ref{alg:symmetric-proportional}
is analogous to step \ref{step:ld-recurse} of Algorithm \ref{alg:lone-divider}:
by envy-freeness of $M$,
the agents in $X\setminus X_M$ value each
piece given away at less than $1$,
so they value the remaining cake at more than
$|X\setminus X_M|$, so the recursive call gives each of them a value of at least $1$.

From the above discussion, it follows that Algorithm \ref{alg:symmetric-proportional} is symmetric, it runs in polynomial time, and it finds a proportional cake-allocation, as claimed in Theorem \ref{thm:symmetric}.

Another application of envy-free matching was recently found in a generalisation of cake-cutting called \emph{multi-cake cutting}. In this problem, the cake is made of $m$ pairwise-disjoint sub-cakes (``islands''), and each agent should be given a piece that overlaps at most $k$ islands, for some fixed integer $k\geq 1$. When $k<m$, it may be impossible to guarantee to each agent $1/n$ of the total value. A natural question is what value \emph{can} be guaranteed, as a function of $k, m, n$. \citet{segalhalevi2018archipelago}
shows an upper bound of $\min({1\over n},{k\over m+n-1})$, as well as several special cases in which this upper bound can be attained. One of these special cases is the case $k=2$. The algorithm for this case uses envy-free matching; see there for details.

\subsection{Envy-free matching in fair allocation of discrete objects}
In \citet{procaccia2014fair}[subsection 3.1],  another concept similar to envy-free matching can be found hiding inside proofs of other lemmata related to fair allocation of discrete objects.\footnote{
This paper has a journal version \citep{kurokawa2018fair} where these lemmata do not appear.
}

In a \emph{fair object allocation} problem, there is a finite set $O$ of objects.
There are $n$ agents. Each agent $i$ has a value measure (i.e, an additive function) $V_i: 2^O \to \mathbb{R}_+$.
Since the objects are discrete, a proportional allocation might not exist. Hence, the following relaxation is used.
For every agent $i\in [n]$ and integers $1\leq l\leq d$,
define the \emph{$l$-out-of-$d$ maximin-share of $i$ from $O$}, denoted $\mms{i}{l}{d}{O}$, as follows:

\begin{align*}
\mms{i}{l}{d}{O} :=
~~
\max_{\mathbf{P}\in \partition{O}{d}}
~~
\min_{Z\in \union{\mathbf{P}}{l}}
~~
V_i(Z)
\end{align*}
where the maximum is over all partitions of $O$ into $d$ subsets, and the minimum is over all unions of $l$ subsets from the partition.
Informally, $\mms{i}{l}{d}{O}$ is the largest value that agent $i$ can get by partitioning $O$ into $d$ piles and getting the worst $l$ piles.
Obviously $\mms{i}{l}{d}{O} \leq \frac{l}{d}V_i(O)$, and equality holds iff $O$ can be partitioned into $d$ subsets with the same value. Thus, $\mms{i}{l}{d}{O}$ can be thought of as $\frac{l}{d}V_i(O)$ ``rounded down to the nearest object''.

The maximin share with $l=1$ was introduced by \citet{budish2011combinatorial}.
The generalisation to arbitrary $l\geq 1$ was done by \citet{Babaioff2017Competitive}.%
\footnote{While the MMS relaxation yields very interesting combinatorial problems, its practical usefulness as a fair division criterion can be challenged. See Sandomirskiy and Segal-Halevi, 2019.}
\citet{budish2011combinatorial} asked whether there always exists a partition of $O$ in which the value of each agent $i$ is at least $\mms{i}{1}{n}{O}$.
For $n=2$, the answer is positive and such an allocation is easily found:
\begin{itemize}
\item Alice partitions $O$ into two piles that she values as at least $\mms{A}{1}{2}{O}$
(in other words, she finds a partition $\mathbf{P}$ attaining the maximum in the definition of $\mms{A}{1}{2}{O}$).
\footnote{%
To find this maximising partition, Alice has to solve the NP-complete problem \textsc{Partition}.
We assume a query model in which agents can answer any query about their individual valuation function in constant time, and the challenge is to compute a fair allocation given the agents' replies.
}
\item Bob chooses the pile he prefers and Alice receives the other pile.
\end{itemize}

For $n\geq 3$, \citet{procaccia2014fair} and \citet{kurokawa2018fair} prove that such allocation might not exist. They present a \emph{multiplicative approximation} algorithm, by which each agent $i$ receives a bundle whose value is at least $\gamma\cdot \mms{i}{1}{n}{O}$, for some fraction $\gamma\in(0,1)$. Their approximation fraction $\gamma$ equals $3/4$ for $n\in\{3,4\}$, and approaches $2/3$ when $n\to\infty$.

They then discuss an \emph{additive approximation} --- a partition in which the value of each agent $i$ is at least $\mms{i}{1}{n+1}{O}$. They say that
\begin{quote}
``We have designed an algorithm that achieves this guarantee for the case of three players (it is already nontrivial).
Proving or disproving the existence of such allocations for a general number of players remains an open problem.''
\end{quote}
They do not present the algorithm for $n=3$.
\footnote{Perhaps they wanted to write it in the margin but the margin was too narrow {\Smiley{}}}
Below we present a slightly more general algorithm using envy-free matching. Algorithm \ref{alg:2n-2} guarantees to each agent $i$ a value of at least  $\mms{i}{1}{2n-2}{O}$, which for $n=3$ coincides with $\mms{i}{1}{n+1}{O}$.

\begin{algorithm}
\caption{
Find a 1-out-of-$(2n-2)$
maximin-share allocation among $n$ agents.
\label{alg:2n-2}
}
\begin{algorithmic}[1]
\REQUIRE A set $O$ of objects and a set $X := [n]$ of agents ($n\geq 2$) with measures $(V_i)_{i=1}^n$ on $O$.
The measures are normalized so that $\forall i\in [n]: \mms{i}{1}{2n-2}{O} = 1$.

\ENSURE A partition $O = Z_1\dot{\cup} \ldots\dot{\cup} Z_n$ such that $\forall i\in [n]: V_i(Z_i)\geq 1$.

\STATE
\label{step:mms-cut}
Arbitrarily pick one agent $a\in X$, and have it
divide $O$ into $|X|$ disjoint bundles $(O_j)_{j\in X}$ with $V_a(O_j)\geq 1$  for all $j\in X$.
\STATE
\label{step:mms-graph}
Define a bipartite graph $G$ with the agents of $X$ in one side, the $|X|$ bundles in the other side, and agent $i\in X$ is adjacent to bundle $O_j$ iff $V_i(O_j)\geq 1$.
\STATE
\label{step:mms-efm}
Find a maximum-cardinality envy-free matching in $G$.
Give each matched bundle to its agent.
\STATE
\label{step:mms-remove}
Remove the matched agents from $X$
and the matched bundles from $O$.
\STATE
\label{step:mms-recurse}
If $X\neq\emptyset$,
go back to step \ref{step:mms-cut}.
\end{algorithmic}
\end{algorithm}
The algorithm starts with a normalisation step. It requires that, before the normalisation, $\mms{i}{1}{2n-2}{O} > 0 $ for all $i\in [n]$.
This does not restrict generality since, if for some $i\in [n]: \mms{i}{1}{2n-2}{O} = 0$,
this $i$ can be given an empty bundle and the algorithm can be applied to the remaining agents.

To prove the correctness of Algorithm \ref{alg:2n-2}, the following combinatorial lemma is needed.
\begin{lemma}
\label{lem:remove}
Let $(v_j)_{j=1}^{n}$
and $(s_j)_{j=1}^{n}$
and $(d_j)_{j=1}^{n}$
be real numbers
such that for all $j\in[n]$:
$v_j\geq 1$ and $s_j\in[0,v_j]$ and  $d_j = v_j-s_j$ ($d$ is the sequence of differences between $v$ and $s$).

If $\sum_{j=1}^{n}s_j \leq k$,
then the sequence of differences
can be partitioned into $\lceil(n-k)/2 \rceil$ subsets, such that the sum of each set is at least $1$.
\end{lemma}
\begin{proof}%
\footnote{
We are grateful to user bof of MathOverflow.com for the proof idea: https://mathoverflow.net/a/334754/34461
}
For each $j\in[n]$, define $t_j := d_j/v_j = 1-s_j/v_j$.
So for all $j\in[n]: t_j\in[0,1]$, and
$\sum_{j=1}^n t_j = n - \sum_{j=1}^n s_j/v_j \geq n-\sum_{j=1}^n s_j \geq n-k$.

Collect the $t_j$ sequentially into subsets, starting
with $t_1$, until the sum of the current subset is at least one.
Continue creating subsets in this way until all the $t_j$-s are arranged in subsets. Let $m+1$ be the number of created subsets, where the sum of the first $m$ subsets is at least $1$ and the sum of the last subset (which may be empty) is less than $1$.
Note that the sum of each of the first $m$ subsets is less than $2$. Therefore, the sum of all subsets is less than $2m+1$. On the other hand, the sum of all $t_j$ is at least $n-k$. Hence
$2m+1 > n-k$
so $2m \geq n-k$
so $m\geq \lceil (n-k)/2\rceil$.

In each subset there are $t_j$ whose sum is at least $1$. The corresponding $d_j$ are at least as large, so their sum is at least $1$ too.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:2n-2}]
We claim that Algorithm \ref{alg:2n-2} finds a 1-of-$(2n-2)$-MMS allocation.

The proof is similar to the correctness proof of the Lone Divider algorithm. It is required to prove that in step \ref{step:mms-cut}, each agent $a\in X$ can indeed partition $O$ into $|X|$ bundles worth for it at least $1$.
Indeed, in the first time the algorithm arrives at step \ref{step:mms-cut}, $|X|=n$.
By definition of the maximin share, each agent in $X$ can partition $O$ into $2n-2\geq n$ piles with a value of at least
$\mms{i}{1}{2n-2}{O}$, so the claim is true by the input assumptions.

Then, the algorithm proceeds as follows.

In Step \ref{step:ld-cut}, by the claim, the $V_a$ of each bundle is at least $1$.

In Step \ref{step:ld-graph}, agent $a$ is adjacent to all $|X|$ bundles, so $|N_G(X)| \geq |X|\geq 1$.

In Step \ref{step:ld-efm},
by Theorem \ref{thm:sufficient}, a nonempty envy-free matching is found.
Each matched agent receives a bundle with a value of at least $1$, so the output requirement holds for these agents.

In Step \ref{step:ld-remove},
the objects in the matched bundles are removed from $O$. By envy-freeness, each remaining agent values each matched bundle at less than $1$.
Let $k$ be the total number of agents matched since the beginning of the algorithm.
So $|X| = n-k$, and for each agent remaining in $X$, the total value of objects removed so far is less than $k$.

Initially, each agent could partition $O$ into $2n-2$ piles with a value of at least $1$. Now, some objects were taken from some of these piles, so their value may be less than $1$. We now show that each agent can re-partition his/her piles into $n-k$ bundles, such that the value of each bundle is at least $1$.
We apply Lemma \ref{lem:remove}
where the numbers $(v_j)_{j=1}^{2n-2}$
are the agent's values to the $2n-2$ original piles,
and the numbers  $(s_j)_{j=1}^{2n-2}$
are the values of objects removed from each pile $j$.
The lemma implies that the agent can partition the remaining piles into bundles with a value of at least $1$, and the number of such bundles is at least
$\lceil(2n-2-k)/2\rceil = (n-1)-\lfloor k/2\rfloor\geq n-k$,
so the claim still holds
when the algorithm goes back to step \ref{step:ld-cut}.
\end{proof}

Algorithm \ref{alg:2n-2} can be modified as to provide various other fairness guarantees (see Appendix \ref{sec:mms-variants}).
For example, it can guarantee $2$-out-of-$(3n-2)$ MMS-fairness.
For some agents, this guarantee may be better than $1$-out-of-$(2n-2)$ MMS. For example, with $n=3$, if $O$ contains $7$ objects and agent $i$ values all of them at $1$, then $\mms{i}{2}{7}{O}=2$ while $\mms{i}{1}{4}{O}=1$.

More generally, for every integer $l\geq 2$, it is possible to guarantee to each agent $i$ at least his $(l-1)$-out-of-$(ln-2)$ maximin share, i.e., $V_i(Z_i)\geq \mms{i}{l-1}{ln-2}{O}$.

The algorithm can also guarantee a multiplicative approximation, giving each agent $i\in[n]$ a value of at least ${2\over 3}\mms{i}{1}{n}{O}$.
The main challenge in proving all these variants is to prove the appropriate analogue of Lemma \ref{lem:remove}; see Appendix \ref{sec:mms-variants} for details.

Algorithm \ref{alg:2n-2} can even make different guarantees to different agents.
The only required change is that in step \ref{step:mms-graph}, in the bipartite graph, each agent $i$ should be adjacent to pile $O_j$ iff $V_i(O_j)$ is above the fairness threshold chosen by agent $i$.

While there are now algorithms that attain better multiplicative approximation factors (see e.g.  \citet{barman2017approximation,ghodsi2018fair}), it is useful to have a simple algorithm using envy-free matching that allows each agent to choose between a multiplicative and various additive approximations.

We were unable to adapt Algorithm \ref{alg:2n-2} to find a $1$-out-of-$(n+1)$ MMS allocation for $n\geq 4$; this problem remains open.

\subsection{A note on terminology}
\label{sub:efm-in-markets}
The term \emph{envy-free matching} is used, in a somewhat more specific sense, in the context of markets, both with and without money.

In a market with money, there are several buyers and several goods, and each good may have a price. Given a price-vector, an ``envy-free matching'' is an allocation of bundles to agents in which each agent weakly prefers his bundle over all other bundles, given their respective prices.
This is a relaxation of a \emph{Walrasian equilibrium}. A Walrasian equilibrium is an envy-free matching in which every item with a positive price is allocated to some agent. In a Walrasian equilibrium, the seller's revenue might be low. This motivates its relaxation to envy-free matching, in which the seller may set reserve-prices (and leave some items with positive price unallocated) in order to increase his expected revenue. See, for example, \citet{Guruswami2005Profitmaximising,Alaei2012Competitive}.

In a market without money, there are several people who should be assigned to positions.
For example, several doctors have to be matched for residency in hospitals.
Each doctor has a preference-relation on hospitals (ranking the hospitals from best to worst), and each hospital has a preference relation on doctors. Each doctor can work in at most one hospital, and each hospital can employ at most a fixed number of doctors (called the capacity of the hospital).     A matching has \emph{justified envy} if there is a doctor $d$ and a hospital $h$, such that $d$ prefers $h$ over his current employer, and $h$ prefers $d$ over one of its current employees.
An ``envy-free matching'' is a matching with no justified envy.
This is a relaxation of a \emph{stable matching}. A stable matching is an envy-free matching which is also non-wasteful ---
there is no doctor $d$ and a hospital $h$, such that $d$ prefers $h$ over his current employer and $h$ has some vacant positions \citep{wu2018lattice}.
When the hospitals have, in addition to upper quotas (capacities), also \emph{lower quotas},
a stable matching might not exist. This motivates its relaxation to envy-free matching, which always exists and can be found efficiently \citep{yokoi2017envy}.

We present envy-free matching as a general graph-theoretic concept, in order to facilitate its use as a subroutine in various settings.

\section{Concluding remarks}
\label{sec:future}

\subsection{Star matchings}
\label{sub:star}
The envy-freeness concept can be generalised from a matching (a set of vertex-disjoint edges)
to an \emph{$r$-star matching} ---
a set of vertex-disjoint copies of the
the star $K_{1,r}$, where the star center is in $X$ and the star leaves are in $Y$.
An \emph{envy-free $r$-star matching} is then an $r$-star matching in which every vertex in $X$ that is not matched (as a center), is disconnected from any vertex in $Y$ that is matched (as a leaf).
Our results can be easily generalised to $r$-star matchings. For example,
the following theorem generalises Theorem \ref{thm:algos}(a) and Corollary \ref{thm:sufficient}(c).
\begin{theorem}
\label{thm:star}
(a)
There is a polynomial-time algorithm that, given any bipartite graph $G=(X \dot{\cup} Y, E)$, finds a maximum-size $r$-star envy-free matching in $G$.

(b)
If $|N_G(X)|\geq r|X|\geq 1$,
then $G$ contains a nonempty envy-free $r$-star matching.
\end{theorem}
\begin{proof}
Given $G$,
construct an auxiliary bipartite graph $G' := (X' \dot{\cup} Y,E')$,
where $X'$ is attained from $X$ by creating $r$ duplicates of every vertex in $X$,
and $E'$ is attained from $E$ by creating an edge from each copy $v^x$ of $x \in X$ to every vertex $y\in N_G(x)$.
For $x \in X$, let $v_1^x,\ldots,v_r^x$ denote the $r$ copies of $x$ in $X'$.
There is a correspondence between
envy-free matchings in $G'$
and
envy-free $r$-star matchings in $G$:

(1) Consider any envy-free matching $W'$ in $G'$.
The subgraph $G'[\{v_1^x,\ldots,v_r^x\}, N_G(x)]$ forms a complete bipartite graph. Hence, if $(v_i^x, y) \in W'$ for some $i \in [r]$, then $W'$ being envy-free in $G'$ means that $W'$ must saturate all of $\{v_1^x,\ldots,v_r^x\}$. All these vertices can only be saturated by $W'$ using edges with one end in $N_G(x)$; all edges thus used by $W'$ (in $G'$) correspond to different edges in $G$ whose one end is $x$ (the ends in $Y$ are distinct).
Collapsing every set $\{v_1^x,\ldots,v_r^x\}$ saturated by $W'$ back to its origin $x$ in $G$ gives an envy-free $r$-star matching in $G$.

(2) Given an envy-free $r$-star matching $W$ in $G$,
create a matching $W'$ in $G'$ by connecting, for each saturated vertex $x\in X$,
each duplicate $v_i^x$ of $x$ to one of the $r$ vertices in $Y$ matched to $x$ in $W$.
Note that, for each saturated vertex $x\in X$, there are $r!$ ways to connect the duplicates of $x$ to its neighbors, so there are many different matchings $W'$ corresponding to $W$.
However, all such matchings have the same cardinality, and every such matching is envy-free in $G'$:
for every vertex $x$ that is matched by $W$, all its duplicates are matched by $W'$ and thus are not envious;
for every vertex $x$ that is unmatched by $W$, all its duplicates are not adjacent to any matched vertex in $Y$, and thus are not envious either.

This correspondence implies the claims.

(a) The size (number of edges) of the matchings $W'$ in $G'$ is exactly $r$ times the size (number of stars) of the matching $W$ in $G$. Hence, applying Algorithm \ref{alg:cardinality} to $G'$ yields a maximum-cardinality $r$-star matching in $G$.

(b) If $|N_G(X)|\geq r|X|\geq 1$, then
$|N_{G'}(X')|\geq |X'|\geq r\geq 1$, so
$G'$ satisfies the premise of
Corollary \ref{thm:sufficient}
and thus admits a nonempty envy-free matching $W'$. It corresponds to an envy-free $r$-star matching $W$ in $G$.
\end{proof}

\begin{remark}
In an $r$-star matching, each vertex in $X$ is matched to either zero or exactly $r$ vertices in $Y$.
One can also consider allocation problems in which each vertex in $X$ can be connected to \emph{any number} of vertices in $Y$ (but each vertex in $Y$ can still be connected to at most one vertex in $X$).
In this setting,
a vertex $x_1\in X$ envies another vertex $x_2\in X$ iff there are more vertices matched to $x_2$ that are adjacaent to $x_1$, then vertices matched to $x_1$.
Finding a maximum-cardinality envy-free allocation in this setting is a question for future work.
\end{remark}

\subsection{Symmetric envy and non-bipartite graphs}
Our definition of an envy-free matching is asymmetric in that it considers the envy of vertices in $X$ only.
One can define a matching as \emph{symmetric-envy-free} if any unmatched vertex in $G$ is not adjacent to any matched vertex in $G$.
This definition extends naturally to non-bipartite graphs.

With this symmetric definition, the algorithmic problems studied here become much easier. It is easy to show that a connected graph admits a symmetric-envy-free matching if and only if it admits a perfect matching.
Then, an arbitrary graph admits a nonempty symmetric-envy-free matching if and only if it has a connected component admitting a perfect matching.
A maximum cardinality (minimum weight) symmetric-envy-free matching is just the union of all perfect matchings (of minimum weight) of such connected components.

\subsection{Other potential extensions}
\begin{enumerate}
\item Since nonempty envy-free matchings might not exist, one may be interested in relaxations.
For example, given a real $\alpha >0$,
a matching $M$ is called \emph{$\alpha$-fraction envy-free} if for every unmatched $x \in X\setminus X_M$:
$
|N_G(x) \cap Y_M| \leq \alpha |N_G(x)|
$.
That is, agents unsaturated by $M$ are willing to ``tolerate'' at most an $\alpha$-fraction of their acceptable houses being assigned to someone else.
Alternatively, given an integer $c\geq 0$,
$M$ is called \emph{$c$-additive envy-free}
if
for every unmatched $x \in X\setminus X_M$:
$
|N_G(x) \cap Y_M| \leq c
$.

\item From a probabilistic perspective, it may be interesting to calculate the probability that a nonempty envy-free matching exists in a random graph. This is related to the problem of calculating the probability that an envy-free allocation exists, which has recently been studied by e.g. \citet{Dickerson2014Computational} and \citet{manurangsi2018envy}.
\end{enumerate}

\newpage


text:
De Pech zijn een volk in Honduras. Naar schatting bestaan er nog 2500 Pech, die hoofdzakelijk in het departement Olancho wonen. Ook bestaan er vier kleine Pech-dorpen nabij Trujillo, en een klein aantal nederzettingen in het natuurreservaat Río Plátano. De nederzettingen buiten Olancho zijn waarschijnlijk ontstaan in de periode dat Honduras werd gefrequenteerd door piraten uit Engeland, Frankrijk en Nederland. De Miskito-indianen hadden een goede verstandhouding met deze piraten en de Pech trokken ter bescherming naar de Miskito-gebieden.

De Pech spreken een eigen taal, die niet verwant is aan het Spaans. Het woord Pech betekent mensen in deze taal. Een woord voor mensen die geen Pech zijn bestaat ook: pech-akuá (andere mensen).

Oorspronkelijk leidden de Pech een nomadisch bestaan. Tegenwoordig bestaan ze met name van de verbouw van yuca en maïs. Hun behuizing beperkt zich nog steeds tot een verhoogde vloer en dak van bamboe, met soms één of twee schutten tegen de wind.

De Pech maken deel uit van de moderne Chibcha.

Indiaans volk in Honduras

redpajama_set_name: RedPajamaWikipedia


As a valued frequent FaceTimer, and to say thankyou for your loyalty, you will earn "Frequent FaceTime Miles" (FFM) with every spend in clinic. Yes, this means you earn Miles on both products AND services! Theres no need to 'sign up', we just take down a few details during check-out (to ensure your miles always go to YOU) and we keep track and manage the rest from there.
For every $10 you spend at FaceTime on products you earn 1 FFM. For example if you purchase a $50 COOLA SPF 30, you will earn 5 FFM.
For every $10 you spend at FaceTime on services, you earn 0.5 FFM. For example if you have a $50 eyelash and brow tint, you will earn 2.5 FFM.
Redeem FaceTimer Miles by saying "Use my miles" during check-out.
1 FFM = $1 of service.
FFM's can be used all year round - yes, even in December!
No cash value and cannot be redeemable for cash.
With Gift Vouchers - Miles will be awarded when the voucher is spent by the lucky recipient, not when the voucher is purchased.


This is Next Door's first perfect score on the state's child care quality rating system!
Members of the Council for a Strong America came to Next Door this week to hold a press conference about the importance of early childhood education. The event drew media attention from Milwaukee's four local TV news stations and the Milwaukee Journal Sentinel.
A recent health fair at Next Door offered the community a variety of child and parent resources to help build strong Milwaukee families.


text:
HomeSan Mateo CountySecrecy surrounding KCSM-TV sale slammed
Secrecy surrounding KCSM-TV sale slammed
The lawyer for a Wall Street-backed firm that subsidized KCSM-TV to keep it running contends the owner, the San Mateo County Community College District, kept a proposal to sell it from both the firm and the public. The dispute is tied to the college district's botched sale of the station's spectrum in an FCC auction last November, in which it could have collected $114 million.
LocusPoint and the district reached an agreement last year before the FCC auction to sell the station in which LocusPoint would pay the district $900,000 a year until the station was sold.
That effort failed. So tonight (Sept. 13), the district board may ratify the purchase of KCSM-TV by KRCB, a PBS-affiliate based in Sonoma County, for $12 million.
The district's process for the recent effort to sell KCSM-TV "was little more than a charade to conceal a predetermined outcome," says LocusPoint Network's lawyer, Andrew Bednark, in a letter to the district.
Bednark's letter, sent Monday, contends that the agreement between KRCB and KCSM-TV, may have been in the works since March.
Overture made
According to an article on Current, a broadcasting news site, the CEO for KRCB, Nancy Dobbs, reached out to other stations who participated in the FCC auction, and discovered that KCSM-TV was not sold. This backs up the statement made in the district's lawsuit against LocusPoint, saying the district was approached about a sale by an unnamed station after the auction.
Bednark says that the district's proposal process was not transparent, as there is no record of the KCSM request for proposals to be found either on the district's website or through a Google search, "calling into question how anyone could find it unless they knew to ask the district specifically for it."
The request for proposals was first issued on June 13, and closed on July 21, according to a report from college district Vice Chancellor Eugene Whitlock. The report also says that the district was not fully satisfied with KRCB's offer of $12 million, a far cry from the $114 million the district could have gotten in the auction.
LocusPoint's argument
Bednark's letter stresses Locus-Point's argument — that the district has been concealing the sale and blunders surrounding the attempted sale of KCSM-TV.
In LocusPoint's April lawsuit, it claims that there were two cover-ups — one when college vice president Jan Roecks signed a document saying she had bid when she didn't, and two, when Chancellor Ron Galatolo failed to disclose that KCSM had been dropped from the FCC auction. Roecks failed to enter a bid on the FCC website at the appropriate time.
As a result, KCSM was dropped from the auction. Roecks told her boss, Galatolo, about the blunder, but for months Galatolo apparently kept the news from the college district's board and Locus-Point. LocusPoint has sued the district over the botched sale and the district has countersued LocusPoint.
Documents sought
Bednark requests in his letter up to 11 types of documents regarding the sale of KCSM-TV. Bednark said yesterday that he had not received a response.
The Post has attempted to contact district spokesman Mitch Bailey numerous times regarding the letter and the sale of KCSM-TV since the board voted to sell the station last week. Bailey has not returned any of the Post's messages.
The district board meets tonight at 7 p.m. at the College of San Mateo, 3401 CSM Drive.
Mizu Makes An Art Out Of Sushi
Ex-cop's consensual sex defense rejected
Community college district plans to end tuition
BY EMILY MIBACH Daily Post Staff Writer The San Mateo County Community College District has board voted to spend $6.75 million to make tuition free. The $6.75 million, approved Wednesday […]
Light shed on college district's $140 million loss
BY EMILY MIBACH Daily Post Staff Writer For months there has been a cloak of secrecy shrouding the botched sale of KCSM-TV by the San Mateo County Community College District, […]
College district will decide whether to televise board meetings
BY EMILY MIBACH Daily Post Staff Writer The San Mateo County Community College District's board tonight (June 12) will debate whether to broadcast its own board meetings. Many boards, city […]

redpajama_set_name: RedPajamaCommonCrawl


text:
Blood Blood Everywhere - Nicu - The Littlest Vampire American-English Edition #3
Nine year-old Florin is a thirsty vampire. The reason? Most of his blood has been sucked out by his friend, Nicu. Florin rampages through the town of Biertan, drinking as much blood as he can. Soon everyone in Biertan is low on blood, and seeking revenge on all vampires. Nicu faces a big challenge. Keeping Florin in check and stopping the angry townspeople from killing vampires.
The spectacular happily ever after of the #1 New York Times bestselling Selection series
Kiera Cass's #1 New York Times bestselling Selection series has captured the hearts of readers from its very first page. Now the end of the journey is here. Prepare to be swept off your feet by The Crown—the eagerly awaited, wonderfully romantic fifth and final book in the Selection series.
In The Heir, a new era dawned in the world of The Selection. Twenty years have passed since America Singer and Prince Maxon fell in love, and their daughter is the first princess to hold a Selection of her own.
Eadlyn didn't think she would find a real partner among the Selection's thirty-five suitors, let alone true love. But sometimes the heart has a way of surprising you…and now Eadlyn must make a choice that feels more difficult—and more important—than she ever expected.
Don't miss The Betrothed, a glittering royal romance sure to captivate Kiera Cass's legion of loyal readers and lovers of courtly intrigue alike!
73 Cool Science Tricks to Wow...
Do you know the secret recipe for the world's most slippery slime? How can you draw a 3-D picture that will mess with your mind? Can you make an instant soap monster in the microwave? Discover the mind-bending, super-weird science that they daren't teach in school! Young readers will love this awesome collection of incredible optical illusions, cool experiments, sneaky hacks, hilarious pranks, and shocking magic tricks. Explore biology, physics, and chemistry from a completely different point of view-one that teachers won't ever tell you about!With a glossary of key scientific terms in the back, this brain-boosting book of fun science is perfect for readers aged 8+.
In the moving and compelling debut novel from Benjamin Zephaniah, a young man's life is completely changed when his face is badly scarred in a car accident.
Martin seems to have it all. He's cool, funny, and he's the undisputed leader of the Gang of Three, who roam their East London estate during the holidays looking for fun. But one night after the Gang leave a late night rap club, Martin accepts a ride from Pete, a Raider's Posse gang member. Too late, he realises that the car is stolen, and that the police are after them.
What happens next will change Martin's life and looks, and show him the true meaning of strength, courage, discrimination and friendship.
Brilliantly written and with a real ear for dialogue, fans of Angie Thomas and Malorie Blackman will love Benjamin Zephaniah's novels for young adult readers:
Refugee Boy
Teacher's Dead
A Curse So Dark and Lonely
Brigid Kemmerer
A New York Times bestseller!
"Has everything you'd want in a retelling of a classic fairy tale." - Jodi Picoult
In a lush, contemporary fantasy retelling of Beauty and the Beast,  Brigid Kemmerer gives readers another compulsively readable romance  perfect for fans of Marissa Meyer.
Fall in love, break the curse.
It once seemed so easy to Prince Rhen, the heir to Emberfall. Cursed by a powerful enchantress to repeat the autumn of his eighteenth year over and over, he knew he could be saved if a girl fell for him. But that was before he learned that at the end of each autumn, he would turn into a vicious beast hell-bent on destruction. That was before he destroyed his castle, his family, and every last shred of hope.
Nothing has ever been easy for Harper. With her father long gone, her mother dying, and her brother barely holding their family together while constantly underestimating her because of her cerebral palsy, she learned to be tough enough to survive. But when she tries to save someone else on the streets of Washington, DC, she's instead somehow sucked into Rhen's cursed world.
Break the curse, save the kingdom.
A prince? A monster? A curse? Harper doesn't know where she is or what to believe. But as she spends time with Rhen in this enchanted land, she begins to understand what's at stake. And as Rhen realizes Harper is not just another girl to charm, his hope comes flooding back. But powerful forces are standing against Emberfall . . . and it will take more than a broken curse to save Harper, Rhen, and his people from utter ruin.


Saints Row 4 Steamless Crackinstmank. f35aea7a9c 4 3 2 1 2010 German 720p BluRay x264-Encounters: 12.08.2011 16:52Uhr: 3GB: 104. Counter Strike Source Steamless Multi5-SteamL [.] 13.04.2011 16:29Uhr: 1GB: 189. steamless. 4. . Saints Row: The Third. MAGIX Movie Edit Pro 2014 Plus 13.0.4.4. Saints Row IV Game of the Century Edition . Red Faction Armageddon-SteamLESS: 23.06.2011 21:00Uhr: 2GB: 99. SAINTS ROW 2 UNCUT PAL iNT XBOX360-GXC. Scream 4 DVDRip Line Dubbed German REPACK Xvi killing floor save;. GTA IV Save Editor is an advanced save editor for Grand Theft Auto IV. Saints Row: The Collection is for saints row 2; Super street fighter 4 pc crack online;. Css steamless patch; Anthrax judge dredd patch; Windows 2003 Vlk Keygen 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k . Saints Row 3 gets the new Genkibowl DLC which is free to anyone who purchased the season pass and around seven bucks for everyone else. Mass Effect 3 PC Steamless is compatible with Windows platforms. UpdateStar has been tested to meet all of the technical requirements to be compatible with Windows 10, 8.1, Windows 8. Ik Ben Nummer Vier - Collectie 4 Boeken (basp) DISPOSE - Saints Row II (basp) DISPOSE. Portal Multi5 steamless (basp) DISPOSE - Cake Mania. sz val szanasz t hackelt steamless az eg sz, m gis komoly buggal nem tal lkoztam. hogy kuk ba dobjam a cuccot. J n ki 3 j Tekken, a Saints Row 3. [Pc] Game of Thrones Episode 4: Sons of Winter. Multi ENG SteamLESS [Pc] Half-Life 2. Related story. Are you sure. Are you sure you want to delete your account? You'll lose everything, forever. Of course not! Yes, delete it. Are you sure. Are you sure you want to change your username? Changing your username will break existing story embeds, meaning older stories embedded on other Web sites will no longer appear. Of course not! Yes, change it. You are about to permanently delete this story. This cannot be undone. To confirm this action, please enter the title of the story below. Are you sure. Are you sure you want to flag this story. No, cancel Yes, flag it.


We provide lots of information to help you measure your children's feet at home and ensure the shoes fit correctly. You can find this information by clicking on 'sizing info' above.
Start-rite boys' black leather school shoes with riptape fastening for adjustability and a comfortable fit, and leather linings to absorb moisture and help keep feet dry. The shoes have a flexible rubber sole for durability and comfort, and a padded ankle for comfort and support.


A Unique signature of Phothalai Offering you with a special massage, combines traditional Thai massage, Indian and Chinese Technique, Focusing on the Plexuses, the whole body from scalp to toes .The pressure point manage and stretching movements, tension and strong disappear to be replaced with a feeling of energy and relaxation.
An exclusive unique massage concentrated blends of essential oils extracted from plants release their soothing properties into the skin during the face, scalp and body massage. The technique eases muscle tension, releases energy with acupressure movements, and the perfect to relieve stress.
Thai Touch Massage was developed from Thai Meridian Massage combined with The Touch of Phothalai. A perfect transformed To a unique signature of Phothalai.
Combines deep head, neck and shoulder massage with a facial lymphatic massages, this massage is designed to clear your mind of all stress and tension.
A highly effective Leg and Foot relax massage that helps subdue muscle tension and restore moisture for softer, smoother skin.
This treatment focuses on the problem's body with oil and acupressure massage a long with yoga positioning and stretching techniques. The treatment stimulates blood circulation and lymph, ease muscle stiffness and relax muscles.
This exclusive traditional treatment begins with a selection of essential oil applied to the body and follow with the full Thai Herbal compress technique. Invigorating oil soothes all aches and unblocks all stiffness, easing your muscles into relaxation and flexibility.
Asian Blend is the combination of ancient Thai, Chinese and Indian massages. By massaging along the 10 major lines of the body combining with the stretching, your joints will be improved.
This treatment system focuses on the relationship of being one with all elements. No oil is used using deep tissue and acupressure massage a long with yoga positioning and stretching techniques. The treatment stimulates blood circulation and lymph, improves energy flow, relieves tension, ease muscle stiffness and promote relaxation.
This method of stimulating compress areas on the feet that relate to and affect the structure and functions of the human body , the foot is compressed with warm special Black Sesami pack on the area that need healing. Its result is to stimulate the function of some aspect of human physiology.
A superb body scrub treatment, exfoliate the accumulation of deed skin cells which dull the skill, Its result is to smooth the skin, healthy and soft.
This treatment begins with a coffee scrub, follow by detoxifying massage . The metabolic process by which the toxic qualities of a poison or toxin are reduced by the body.
* Steam and refreshment 30 mins.
* Thai Meridian Massage 90 mins.
* Head and Shoulders Massage 30 mins.
* Herbal Compression Massage 30 mins.
The perfect facial treatment Phothalai style to cleanse your skin. An extremely relaxing facial to eliminate stress and fatigue. The treatment is suitable for skin types.
The perfect facial treatment to deep cleanse and exfoliate to smooth skin texture and encourage skin renewal. Hydrating and rejuvenating Perfection lift Care with Neutralon combined with a relaxing facial pressure point massage will combat areas most affected by the aging process. Treatment is delicated to increase moisture to your skin and appearances of wrinkles and loss of firmness. The treatment is suitable for all skin types.
The focus of this facial is the mask of special care massage cream which provide the necessary of skin element for balancing toning and vitalizing your skin. This mark cream brings supplement and comforts to the skin.
A deluxe treatment to help detoxify your system and rebalance body and mind. This treatment features the application of a triple tea Scrub (white tea,green tea and black tea) and encourages detoxification and the reduction of fluid retention. After this you will be body massage and wrapped in triple tea to stimulate new cell growth and to moisturize the skin.
This is contrary to the recipe massage, and to cover his nose with rice with values from pure Vitamin A and vitamin E can help shift rice exfoliating out to prevent the wrinkles before age helped slow down the deterioration of skin cells and skin care, soft white community is a natural admiration.
Polishing skin Program with a Clarin world-class product as well as the massage techniques fit proportion of removal of waste water to reduce swelling, smooth skin.
The Face Lift fit with radio wave (Radiofrequency) to solve the problem wrinkles double chin dropping to lean face-face, slender with small modern innovations and safety without surgery with maintenance with maximum values of wild plants from stem cell to create a stimulating, to be well-versed in genuine leather floor slowing age.
Programs that use radio waves (Radiofrequency), so that the distribution of body fat a lump under your skin effectively together with the frequency band ultrasound to break up the fat cells and has been driving down the number of out of your body so your skin stays smooth fit together with a massage to adjust shape.
The proportion of damage to fit anti-cellulite and eliminate fast excess fat with radio frequency technology to massage removes toxic underlayer of broken cells and anti-cellulite burn up for those who want to reduce quickly.
The technology brings oxygen into skin cells to increase food, Pure Water spray skin cells can help shift your skin with a gentle vitamin C helps to clean white skin, reduce acne and clogged.


Who knew Active Support could be so much fun?
Scout4x4 is a Scout Active Support Unit, which means anyone over 18 can join in and get involved.
We are a group of 4x4 enthusiasts who take pride in using our vehicles to benefit Scouting, having fun and learning new skills.
Our membership is made of up people from across England.
As a Scout4x4 member, there are many activities and different challenges to partake in. Our main goal is to support Scouting and we do this in many ways, these 'service' activities take up most of our programme but we try to have a couple of weekends away and day trips where we like to explore the vast network of byways.
This get us out and about and means out members can meet and enjoy our 4x4 passion. We aim to run at least 1 dedicated training weekend a year where members can practice skills and scenarios and learn new ones too. All our driving activities offer the chance to learn and try new things too!
To keep members updated we use traditional e-mail and we have a members Facebook group. We also use Google calendar which members can sync with, so they have event information to hand on all devices.
We are always on the lookout for members who enjoy using their 4x4 for Scouting and want to be part of an ever-growing team and learn new skills, help others and above all have fun. It can be incredibly hard work but its rewarding, good fun with great people.
Click to e-mail your interest - we will send you a membership form.


text:
Amy Carlberg
Danny Green and Russell Peters just showed up at an iconic burger joint in Brampton
A basketball player and a comedian walk into a burger joint...
It may sound like the beginning of a cheesy joke, but it's actually a real thing that happened when Danny Green and Russell Peters headed to Sonny's Drive-In in Brampton for some equally cheesy late night eats.
The Bramptonist reports the two dined on poutine and milkshakes at the picnic benches sitting outside the classic establishment. It would seem they were also accompanied by a photographer and a cameraperson, so maybe the visit was for some other unclear purpose.
Peters is a Brampton native, so it's unsurprising if he's a long-time fan, and Green may have become a patron of Sonny's during his time in Toronto playing for the Raptors.


I had lost my original tesla in a tree at sipapu disc golf center in taos nm. I was 5 under at the time. My new one is a dream and flies forever. Thanks.
The disc is exactly what I had hoped and is in use every round since I got it. The ordering experience and service were also 5 stars.
This disc does almost exactly what the flight numbers you find say it does. Almost, I say because I feel the fade is less than a 2 yet more than the 1 that the axiom insanity is.. Still this disc bombs. Even at the light weights it's flight pattern remains the same, as I've found with every mvp disc I've used so far.
The plasma plastic feels great in the hand and I only hope MVP releases more molds in this plastic.
If you have a bigger arm of suggest a different disc as this will be far too understable. But, I'd like me, you're on the weaker side looking for an easy to grip disc with a natural S flight and great control you need to give this a try.


Easter Weekend 2019 in Reno has a lot to offer for events, dining and more. Enjoy an Easter Sunday brunch in Reno or check out one of the family friendly events for Easter. Be sure to check out the local Reno Nevada events guide to find the perfect plans for Easter Weekend.
Ask your Friends what they are doing for Easter Weekend when you LIKE this page!
If you are looking for things to do for Easter in Reno, then check out the 775area Reno Guide. You can find events, restaurants, recreation and more. There are plenty of Events and Things to Do in Reno for Easter Weekend. Know of events in your area that are not listed below, then post events on the website to help others looking for things to do.
All logos and trademarks in this site are property of their respective owner.	The comments and listings are property of their posters. All the rest Copyright © 2019 by 775area.com. All Rights Reserved.


In this section we will study the guitar style of the Rolling Stones' Keith Richards. This includes 5 lessons in the style of Keith Richards, from Open G Tuning to 2 song lessons including Honky Tonk Woman and Brown Sugar.
in this lesson we will discuss basic tone, tunings, and playing style of Keith Richards.
In this lesson we will cover some of the basic chord forms used most often by Richards in open G tuning.
In this lesson we will study some standard tuning techniques used by Richards in such songs as Satisfaction.


"Graceful Divorce Solutions" – the Book!
Ask your question, in confidence, by clicking here.
Or you may email us at ask@nullgracefuldivorcesolutions.com.
We'll answer your question in upcoming issues!
Domestic Violence — It's Everybody's Business!
Graceful Divorce Solutions is a thorough walk through various models of dispute resolution that will help your clients seriously consider alternatives to fighting in Court. The book is well written and clear. Each chapter offers a look at a different model, but the entire book is packed with helpful and thought provoking information for our clients who are confused, overwhelmed, and fearful of making bad choices.


Provides boys and girls with disabilities the opportunity to experience the emotional development and the fun of playing baseball.
Provides a positive environment for youth and their parents for learning the basic skills of baseball. Typically starts play first Saturday of June.
Teaches baseball fundamentals through a series of practices and games (coach-pitch).
Prepares players for Minor league by teaching more baseball-specific skills and strategy. Machine and player-pitch. No standings or playoffs.
Player-pitch and the introduction of competition, standings, playoffs.
Strategy and competition come together as teams play exclusively at our beautiful Empire Park facility, "The Home of Webster Baseball."
Junior 13-14 yrs old The first taste of the big/regulation size baseball field (60/90), playing "real baseball" rules! Home games played at D'Amico Park. League will include play versus other towns' teams.
The highest level of in-house Little League baseball for players age 15-16. Home games played at D'Amico Park. League will include play versus other towns' teams.
1 or 2 teams of 16-18 year olds that play against teams from other towns (home and away).


Chapter 4: "Wake of the Watcher"
No one goes to Illmarsh. An ugly town, unfriendly to strangers and squatting amid the nastiest stretch of swamp in Ustalav, Illmarsh seems to breed rumor and madness, and those who speak of it always whisper of strange disappearances, misshapen shadows, and sacrifices to things terrible and forgotten. But when the trail of the death cultists known as the Whispering Way leads to Illmarsh, it's up to the PCs to learn the secrets of the sickly village. There they'll find a desperate people, caught in a war between beings from beneath the seas and invaders from the darkest corners of the cosmos. Can the heroes save Illmarsh from its tradition of terror? Or will they be the next victims of the horror from beyond the stars?


Jesus said that to enter the kingdom of heaven a person must be "born again" (John 3:3). This consists of an act of the heart in believing Jesus Christ as Lord and Savior. When we were born into the world physically, we were born spiritually dead, and therefore we need a spiritual birth. The spiritual birth involves two facets.
The first is to realize that we cannot make it on our own. We are sinners who need help. What is a sinner? A sinner is someone who is separated from God, has chosen to go his own way and cannot get back to God on his own because of sin.
Sin can be simply characterized as our own self-centered pride and selfishness. More specifically, sin is the violation of a holy god's standard of righteousness.
Thus, we must own up to the fact that we need a Savior, someone who will accomplish all that God requires. The only person ever to do this was Jesus Christ. He lived the only life that was acceptable to God.
He died as a substitute on the cross for our sins, because we have no chance of pleasing God on our own merit. Thus the initial step is to realize that we all have sinned, broken God's law, and deserve judgment as a result. The Bible says, "The wages of sin is death" (Romans 6:23, KJV).
Once a person sees his hopeless condition and realizes that Jesus Christ offers an answer, the next step is to receive that offer personally, for "the gift of God is eternal life through Jesus Christ our Lord" (Romans 6:23, KJV). When a person receives Christ as his Savior by accepting God's gift, at that moment he becomes born again.
It is so easy a child can do it, but it is hard because we first have to realize that we cannot do it on our own. Jesus said that to enter the kingdom of heaven a person must be willing to humble himself as a child, and only then will God receive him (Matthew 18:3).
One thing that is important to note, though, is that it is not the reciting of the above words that makes the difference. There is nothing magical in them; anyone can repeat a sentence. It is the attitude of your heart and your desire when you pray and trust Christ that makes the difference.
Excerpts taken from Answers to Tough Questions Skeptics Ask About the Christian Faith. Josh McDowell and Don Stewart. Tyndale House Publishers, 1980.


text:
Q: ApolloClient readFragment returns empty object Accordingly to the docs this is all it takes to query something from apollo cache but it isn't working and the console.log() is showing an empty object. The first image show that I have the entity cached.

*

*change optimistic to false doesn't change the result

*change the id to "141" change the return from empty object to 'null'

*import gql from "graphql-tag";

*"apollo-client": "^2.6.8",

*"graphql-tag": "^2.10.0",
onClick: p => {
  const readFragment = apolloClient.readFragment({
    id: 141,
    fragment: gql`
      fragment myMarca on Marca {
        id
      }
    `,
    optimistic: true,
  });
  console.log(readFragment);
}

A: The problem was that I was passing id: 141. The right way is Marca:141. Found it from this answer inside Apollo Spectrum Community.

redpajama_set_name: RedPajamaStackExchange