Algorithm for allocating resources; one resource per one user who accepts it

Question

I am looking for an algorithm for the following problem:

I have a set of users and a set of books.

Every user has their own set of favorite books, which may be empty, and is a subset the set of books.

We can assume that every book is a favorite book of at least one user.

Ideally I want to distribute ONE book to every user that has at least one favorite book.

A user may only receive one of its favorite books.

Sometimes it's not possible to distribute one book to every user, because there are more users than books, or because a user has no favorite books, or due to the specific details of users, books and favorite books.

One book cannot be distributed to more than one user.

Distribution A is better than distribution B if A distributes more books than B.

An "acceptable distribution" is one that follows the rules above, and cannot be improved without reallocating a book, i.e. taking a book away from a user that already got a book.

An "optimal distribution" is an acceptable distribution that distributes a maximum number of books.

I do not have a formal analysis whether this problem can be accurately solved in a polynomial time. So maybe the best polynomial-time alternative there is out there is something such as a probabilistic algorithm.

Ideally I would like to have a polynomial-time algorithm that would always find an optimal distribution.

If it's not possible to have such an algorithm, then I would like to have an alternative polynomial-time algorithm that would find an acceptable distribution that in high probability is quite close to an optimal distribution.

Answer 1

Create a bipartite graph $G = (B+U, E)$, where $B$ is the set of books and $U$ is the set of users. The set $E$ contains an edge $(b,u)$ for every pair $(b,u) \in B \times U$ such that $b$ is one of the favorite books of $u$.

To find an optimal solution, you just need to find a maximum cardinality matching of $G$.

A way to do this is to modify $G$ as follows: direct the edges of $G$ towards $B$, add two new vertices $s,t$, add all edges $(s,b)$ for $b \in B$, and finally add all edges $(u,t)$ for $u \in U$. Now you can find a maximum flow $f$ between $s$ and $t$ using any polynomial-time algorithm and unitary edge capacities. An optimal matching contains all edges $(b,u) \in E$ such that $f(b,u)=1$.