# Assign items from inventory to people maxmizing the number of satisfied people

We have a set of people, and each person has a list of wished items (not unique, they could want multiple copies of each item). We have an inventory of items that we want to assign to the people. We want to maximize the number of people who receive all the items on their list. The inventory may not have enough items to satisfy all the wishes.

To give an example:
Alice - wants: 1 apple
Bob - wants: 3 bananas, 1 cherry
Charlie - wants: 2 apples, 1 banana

Inventory: 1 apple, 3 bananas, 2 cherries

One optimal solution is:
Alice - gets: 1 apple
Bob - gets: 3 bananas, 1 cherry
Charlie - gets: 1 cherry

Alice and Bob are satisfied, and it doesn't matter what Charlie gets.

Here is what I tried so far:
I tried searching for a similar problem, but the only thing I could find are variations of the assignment problem, or the matching problem, all of which do not quite match the one at hand. I don't think the assignment problem applies, because it has a cost function for each assignment, which is independent of the other assignments, but here we have global cost function. We could model the situation similar to a matching problem where we would have a bipartiate graph of vertices one side being the people and the other being the items with edges representing the wishes (we could have multiple edges for a pair of person and item to represent the amount) and have a "capacity" on each item to represent the inventory. Then we could find some sort of matching which satisfies the constraints. But I am not sure which algorithm could be used for that.

• this reminds me of the scene in the movie "the beautiful mind" where John Nash came up with the equilibrium theory to get everyone get laid Commented Jan 4, 2023 at 1:49