# Max-min one-to-two matching

There are some $$n$$ people and $$2 n$$ items. Each person assigns a positive value to each item. The items should be allocated to the people, giving exactly 2 items to each person. The value of a person is the sum of values of the two allocated items. The goal is to maximize the minimum value of a person. For example, suppose $$n=2$$ and the values are:

• Alice: w=1, x=2, y=3, z=4
• Bob: w=5, x=6, y=7, z=8

Then the max-min partition is giving y,z to Alice and w,x to Bob, as the minimum value is 3+4=7, and this is the largest possible minimum value.

If there is only 1 item per person, then the problem can be solved in polynomial time by reduction to maximum matching.

In contrast, if there are 3 items per person, then the problem is NP-hard, by reduction from the 3-partition problem.

The case of 2 items per person is in between, so I do not know: is it NP-hard? Or is it solvable in polynomial time?

Consider the case where each person $$i \in [n]$$ has a "value score" $$v_i$$, each item $$j$$ has a "value score" $$w_j \in [2n]$$, and the value person $$i$$ has for items $$j$$ is $$v_i/2 + w_j$$. In particular, the total value person $$i$$ has for the pair of items $$(j, k)$$ is $$v_i + w_j + w_k$$, and in any assignment of pairs of items to people, the total value among all people will be exactly $$V = \sum_{i \in [n]} v_i + \sum_{j \in [2n]} w_j$$.
Now, the maximal possible minimal value is at most $$V/n$$. It will equal $$V/n$$ iff the 3-partition problem with the set of weights $$\{v_i\} \cup \{w_j\}$$ is solvable (technically, this is a slight variant of the 3-partition problem where you must choose one element from the first set and two elements from the second set, but you can easily reduce this to the original 3-partition problem by simply adding a large constant $$C$$ to all $$v_i$$). Since you can embed any 3-partition problem in this way, the original problem is also NP-hard.