Auction algorithm for assignment problem with “singles”

Question

Consider the following variant of the assignment problem. There are $I$ men and $J$ women. Each man can stay single or be assigned to a woman, and vice versa. Each potential match has value $u_{ij}$. The value of being single is $u_{i0}$ and $u_{0j}$ for men and women, respectively. Let $\mu_{ij}$ be an indicator equals one if $i$ is matched with $j$. $\mu_{i0}$ and $\mu_{0j}$ are the euqivalent indicator for singels. Each man can be matched with one woman only or stay single, and likewise for women.

$$ \mu_{i0} + \sum_{i=1}^{I} \mu_{ij} = 1 \quad \forall i$$

$$ \mu_{0j} + \sum_{j=1}^{J} \mu_{ij} = 1 \quad \forall j$$

The problem is to find a feasible assignment that maximizes the total value

$$ Max_{\mu}(\sum_{i=1}^{I}\sum_{j=1}^{J}u_{ij} \mu_{ij} + \sum_{i=1}^{I} u_{i0} \mu_{i0} + \sum_{j=1}^{J} u_{0j} \mu_{0j}) $$

My question is whether someone knows of a reference for an article that develops the auction algorithm for this case. I didn’t find it in Bertsekas (1998) or in a search on Google Scholar, but maybe I'm using the wrong terminology.

Edit: I posted a potential algorithm, but I would still appreciate references, so I won't need to reinvent the wheel.

Answer 1

I'm not aware of a reference and I doubt there is one, as this can be trivially solved using standard algorithms for the assignment problem. For each man $m$, add another artificial woman $a_m$ who can only be paired with $m$; the pair $(m,a_m)$ corresponds to $m$ remaining single. Then solve the resulting unbalanced assignment problem.

Answer 2

I'm thinking now about the following extension of the auction algorithm (still need to check if it works)

Normalize the surplus of singles to 0. Let $u_{ij}$ be the (normalized) joint surplus and $m_{ij}$ the meetings ($i$ and $j$ can be matched only if $m_{ij}=1$).

1. Start with an empty assignment $S$, a vector of initial prices $w_i = 0$, and some $\epsilon >0$

2. Iterate on the two following phases

a) Bidding Phase

Let $J(S)$ be a nonempty subset of women $j$ that are unassigned under the assignment $S$. For each woman $j \in J(S)$

• Find a ``best'' man $i_j$ having maximum value, i.e.,

$$ i_j = \text{arg} \max_{i \in m(j) } u_{ij} - w_i$$
and the corresponding value

$$ v_j = \max_{i \in m(j) } u_{ij} - w_i$$ and find the best value offered by men other than $ i_j $ $$q_j = \max_{i \in m(j) , i \ne i_j } u_{ij} - w_i$$

• If $v_j > 0$, woman $j$ makes a ``bid'' for man $i_j$.

• The bid is given by: $$b_{ij} = w_{i_j} + v_j - q_j + \epsilon$$
  b) Assignment Phase

For each man $i$, let $B(i)$ be the set of women from which $i$ received a bid.

• If $B(i)$ is non-empty, increase $w_i$ to the highest bid:

$$ w_i = \max_{j \in B(i)} b_{ij}$$

• Assign $i$ to the woman in $B(i)$ attaining the maximum above

3. Terminate when no new assignment is made