# A cute allocation problem

In the spirit of something I already did, I'm going to discuss a cute problem that suggested itself spontaneously over dinner, except this time I will study its complexity from a theoretical angle.

The problem is as follows. You applied to a number of companies, and each company's board issued a list of the candidates ranked by their order of preference. You know, for each company, how many people they will hire, and you know that they will take the highest ranked people who accept the job. Your hope is to get a job at any of the companies. Maybe you are ranked sufficiently high at some company to be sure to get a job there, in which case you've won; but maybe you aren't, and you hope that some of the people ranked higher than you will not accept their offer(s) so that you can be selected instead.

Of course, you always have some hope that everyone will desist and that you
will get what you want. A harder question is: *can you be sure that you will
get a position, even though you are not ranked well enough to be sure to have
any position?* If you think about it, the answer is clearly yes in some
situations, assuming that other candidates can only accept at most one position.
If some super-strong candidate is ranked first at all positions, then they'll take only
one of them at most, so if there are two positions where you're the first
candidate below the bar, then you're sure to get one of them no matter what
happens.

The problem is now to decide this algorithmically. Given as input the list of candidates that beat you at each company, given the number of people recruited by each company, can you decide efficiently whether you are sure to get a job at any of the companies?

It might seem that this problem is NP-hard (computationally intractable) because it looks a lot like the set cover problem or the Boolean satisfiability problem, but actually you can determine in polynomial time whether you are sure to get some job.

The method is to encode the problem as a flow problem. Build a
graph that has a source vertex s, a target vertex
t, one vertex c_{i}
for each candidate i, one vertex l_{j} for each list j, and
consider the graph with one edge from s to every c_{i} (with capacity 1), one edge from each c_{i} to the lists l_{j} where candidate i
appears before you (with capacity 1), and one edge from each l_{j} to t whose capacity
is the number of positions offered by company j (in
other words, the number of candidates that need to accept a position at this
company for you not to get the job).

Now, we ask whether the maximal flow of this graph saturates all the edges to
t. If it does, and if the flow is integral, then
observe that the flow gives you a way to allocate candidates to lists so that
you do not get any job (the one saturated edge leaving c_{i} tells you which job candidate i accepts). Conversely, if there is such an allocation, then
there is a maximal flow saturating all edges to t. But
now, the integral
flow theorem ensures that there is always a maximal flow that is integral.
It remains to observe that the maximum flow
problem can be solved in polynomial time to conclude that the same is true
of our problem.

This implies the tractability of the following (equivalent) rephrasing of
this problem in terms of satisfiability. You have a set of variables (x_{i}) which can each be assigned a value from a
domain D_{i} (so, multivalued variables). You
have a conjunction of clauses which are sets of equalities between such
variables and a constant from their domain. For each clause C_{j} you have a number n_{j} and you say that the clause is true if at
least n_{j} of its litterals are true. This is
of course much worse than the usual NP-hard Boolean satisfiability problem,
except that you require that the same equality (between a variable and a
constant) can never occur in two different clauses. Now, by the above, this
restriction makes the satisfiability problem tractable.