9
$\begingroup$

I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching".

Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that the weight is given by a profit function $p:{V\choose 2}\to \mathbb N$. Given a matching $M$, denote by $M(v)$ the profit of the edge $v$ is matched with.

A matching $M$ is a fair matching iff, for any two vertices $u,v\in V$: $$(\forall w\in V:\ \ p(\{w,v\})\geq p(\{w,u\}))\to M(v)\geq M(u)$$

That is, if for any vertex $w\in V$, matching $w$ to a vertex $v$ gives higher profit than matching it to a vertex $u$, a fair matching must suffice $M(v)\geq M(u)$.

Can we find a maximum weight fair matching efficiently?


An interesting case is when the graph is bipartite and the fairness only applies to one side, that is assume that $G=(L\cup R,L\times R)$, and we are given a profit function $p:L\times R\to \mathbb N$.

A Fair Bipartite Matching is a matching in $G$ such that for any two vertices $u,v\in L$: $$(\forall w\in R:\ \ p(\{v,w\})\geq p(\{u,w\}))\to M(v)\geq M(u)$$

How fast can we find a maximum weight fair bipartite matching?


The motivation for this problem comes from the bipartite special case. Assume you have $n$ workers and $m$ tasks, and worker $i$ can produce $p_{i,j}$ profit from work $j$. To problem here is to design a reasonable (in a sense workers will not feel "ripped-off''), while maximizing the total payoffs. (There is a tradeoff here between the power of the assignment mechanism and the social benefit).

If we define the social-welfare (or the factory profit) of the assignment of workers to jobs as the sum of profits.

Looking at different scenarios for the power of the job assigner, we get the following results:

  • If we are allowed to assign any worker to any job, we can optimize the factory efficiently (just find a maximal-weight matching).

  • If every worker chooses a task on his own, assuming that his work will be selected (only a single work can be selected for each job) should he be the most qualified worker that chose the task, workers will converge into the ''greedy'' equilibrium. The reason is that the worker that could earn the most ($i=\mbox{argmax}_i \max_j p_{i,j}$) will choose the most profitable job, and so on. By the approximation rate of the greedy algorithm for matching, this should give a 2-approximation of the maximal social-welfare possible.

I'm looking for something in-between. Let's assume we could assign workers to jobs, but have to promise them that no "less-qualified" worker earns more than them.

How can we find a maximal weight matching promising "fairness" to employees efficiently?

$\endgroup$
  • $\begingroup$ Tangentially, for the second (bipartite) case, it seems easy to construct examples where every "fair" matching gives the first worker profit 1, and the rest zero, even though there are "unfair" matchings giving the first worker profit $1−2\epsilon$ and everybody else profit $1−\epsilon$. Similarly, examples where the maximum-weight fair matching gives each worker profit $2/n$, even though there are unfair matchings giving each worker profit in $\{1-\epsilon,1-2\epsilon\}$. $\endgroup$ – Neal Young Jul 3 '18 at 3:38
  • $\begingroup$ @NealYoung - am I correct to assume that these scenarios cannot exist if the profits are distinct? $\endgroup$ – R B Jul 3 '18 at 13:14
  • $\begingroup$ It seems like a standard issue in game theory where the inability to distinguish between alternatives significantly lowers the social welfare. $\endgroup$ – R B Jul 3 '18 at 13:15
  • $\begingroup$ Whoops, I take back my comment -- I'm not sure those examples are realizable after all! $\endgroup$ – Neal Young Jul 3 '18 at 16:50
1
$\begingroup$

I believe "maximum weight fair bipartite matching" as you've defined it is NP-hard. Even more, determining the existence of a fair bipartite matching is NP-hard.

Before I give a proof sketch, for intuition, consider the following small instance. Take $G'=(L, R, E'=L\times R)$ where $L=\{a,b\}$, $R=\{c,d,e,f\}$. Take $p$ such that $p(u,w) = 0$ for $u\in L$ and $w\in\{c,d\}$, while $p(u,w) = 1$ for $u\in L$ and $w\in\{e,f\}$. Then $a$ and $b$ are equivalent, in the sense that $p(a, w) = p(b, w)$ for all $w\in R$, so any fair matching must give $a$ and $b$ the same profit. Hence, the only fair matchings either match $a$ and $b$ to $c$ and $d$, or they match $a$ and $b$ to $e$ and $f$. Using this kind of gadget, we can force coordination of the edges in the matching. This is the basis of the reduction.

Here's an attempt at a proof. It's a bit involved. Probably there are some mistakes, but hopefully any mistakes can be fixed.

Lemma 1. Given $G'=(L, R, E'=L\times R)$ and $p:E'\rightarrow\mathbb{R}_+$ as described in the problem, determining whether $G'$ contains a fair matching is NP-hard.

Proof sketch. The proof is by reduction from Independent Set in cubic graphs. Let $(G=(V,E),k)$ be a given instance of Independent Set where $G'$ is a cubic graph (every vertex has degree 3). We describe how to construct a graph $G'=(L, R, E'=L\times R)$ and profit function $p:E'\rightarrow\mathbb{R}_+$ such that $G'$ has a fair bipartite matching if and only if $G$ has an independent set of size $k$.

The vertices in $L$ will come in pairs, called partners. Likewise for the vertices in $R$. For each vertex $v\in L\cup R$, we let $v'$ denote the partner of $v$. Each vertex $\ell\in L$ and its partner $\ell'\in L$ will be equivalent, meaning that we will make $$p(\ell, r) = p(\ell', r) \text{ for all } r\in R.$$ Consequently, any fair matching must assign the same profit to $\ell$ and $\ell'$. In what follows, we use $\pi(\ell, r)$ to denote the value of $p(\ell,r) = p(\ell', r)$.

Further, for each pair $\ell$ in $L$, and each pair of partners $r, r'$ in $R$, either we make $$\pi(\ell, r) = \pi(\ell, r')$$ or we make $$\pi(\ell, r) \ne \pi(\ell, r').$$ In the former case, we say we allow $\ell$ and $\ell'$ to be matched to $r$ and $r'$ (because doing so would assign the same profit to $\ell$ and $\ell'$, as required). In the latter case, we say we prevent $\ell$ and $\ell'$ from being (both) matched to $r$ and $r'$ (because doing so would not assign the same profit to $\ell$ and $\ell'$).

As the given graph $G=(V,E)$ is cubic, it satisfies $3|V|=2|E|$, and any independent set $I$ of size $k$ in $G$ is incident to exactly $3k$ edges. Assume for ease of notation that $V=\{1,2,\ldots,n\}$.

For each edge $\{i, j\}\in E$, do the following.

  1. Add a pair of partner vertices $r(\{i,j\}), r'(\{i,j\})$ to $R$.

  2. For endpoint $i$, add a pair of partner vertices $\ell(i,j), \ell'(i,j)$ to $L$. Set $$\pi(\ell(i,j), r(\{i,j\})) = \pi(\ell(i,j), r'(\{i,j\}))= i,$$ allowing $\ell(i,j)$ and $\ell'(i,j)$ to be matched to $r(\{i,j\})$ and $r'(\{i,j\})$.

  3. Symmetrically, for the other endpoint $j$: add another pair of partner vertices $\ell(j,i), \ell'(j,i)$ to $L$, and set $$\pi(\ell(j,i), r(\{i,j\}) = \pi(\ell(j,i), r'(\{i,j\}))= j,$$ allowing $\ell(j,i)$ and $\ell'(j,i)$ to be matched to $r(\{i,j\})$ and $r'(\{i,j\})$.

For every $\ell\in L$ and $r\in R$ added so far, if the pair $\ell, \ell'$ is not explicitly allowed (above) to be matched to $r, r'$, then prevent the match by assigning $\pi(\ell, r)$ and $\pi(\ell, r')$ each some unique number.

Next, add $3(|V|-k)$ pairs of filler vertices to $R$. For each filler vertex $r$ and each $\ell(i,j)\in L$, set $\pi(\ell(i,j), r) = 0$.

Finally, add two vertices $L_0$ and $L'_0$ (partners) to $L$, along with a two vertices $R_0$ and $R'_0$ (also partners) to $R$. Set $\pi(L_0, R_0) = \pi(L_0, R'_0) = 1$, allowing $L_0$ and $L'_0$ to be matched to $R_0$ and $R'_0$. For every other vertex $r\in R$, set $\pi(L_0, r)$ to some unique number. (Hence, any fair matching must match $L_0$ and $L'_0$ to $R_0$ and $R'_0$.) For every $i\in V$, for every incident edge $\{i,j\}\in E$, set $\pi(\ell(i,j), R_0) = i$ and $\pi(\ell(i,j), R'_0) = |V|-i+1$.

That completes the reduction. To finish, we prove it is correct.


First consider for what pairs of vertices $\ell(i,j),\ell(i',j')\in L$ the latter dominates the former, that is, $$(\forall r\in R)~\pi(\ell(i,j),r) \le \pi(\ell(i',j'), r).$$

Considering the profits assigned to edges incident to $R_0$ and $R'_0$, this condition can only be met if $i=i'$, and, inspecting the definition of $\pi$ for the remaining edges, the condition $i=i'$ is sufficient. Hence a matching is fair if and only if it assigns $L_0$ and $L'_0$ to $R_0$ and $R'_0$, and also, for each $i\in V$, gives the same profit to all vertices in $$N(i) = \{\ell(i,j) : \{i,j\}\in E\} \cup \{\ell'(i,j) : \{i,j\}\in E\}.$$


First, assume that $G$ has an independent set $I$ of size $k$. Obtain a fair matching for $G'$ from $I$ as follows.

Match $L_0$ and $L'_0$ to $R_0$ and $R'_0$.

For each vertex $i\in I$, let $\{i,j_1\}, \{i,j_2\}, \{i,j_3\}$ be its three incident edges. For each edge $\{i, j_h\}$, match vertex $\ell(i,j_h)$ and its partner $\ell'(i,j_h)$ to $r(\{i,j_h\})$ and $r'(\{i, j_h\})$. This gives all vertices in $N(i)$ profit $i$.

For each of the $|V|-k$ vertices $i\in V\setminus I$, for each of the three edges $\{i,j\}$ incident to $i$, match $\ell(i,j)$ and its partner $\ell'(i,j)$ to some unique pair of filler vertices $r$ and its partner $r'$. This gives all vertices in $N(i)$ profit $0$.

Hence, this matching is fair.


Next, assume that $G'$ has a fair matching $M$.

$M$ must match $L_0$ and $L'_0$ to $R_0$ and $R'_0$. For each $i\in V$, the matching must give each of the vertices in $N(i)$ the same profit. For each $\ell(i,j)\in N(i)$, its partner $\ell'(i,j)$ is also in $N(i)$. So, by inspection of the reduction, the profit of each such vertex must be either $i$ (in which case all six vertices in $N(i)$ are matched to vertices $r(\{i,j\})$ and their partners) or zero (in which case all six vertices in $N(i)$ are matched to filler vertices in $R$). Let $I$ be the set of vertices for which the former case holds. For each edge $\{i,j\}$, the vertex $r(\{i,j\})$, and its partner, are each matched to one vertex. It follows that $I$ is an independent set. Since the number of filler vertices is $6(|V|-k)$, the size of $I$ must be at least $k$.

QED (?)


I think it's basically correct, if a bit convoluted. Let me know if you see any mistakes, or a way to simplify the proof.

The reduction above assumes it's okay to take $|R|>|L|$. If that's undesirable, then I'd guess we can pad $L$ with $|R|-|L|$ filler vertices, assigning profit 0 to all of their edges except the edges to $R_0$ and $R'_0$. We can assign profits to the latter edges to ensure the filler vertices are not dominated by (nor dominate) any other vertex.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.