# Approximate decomposition of a many-to-one assignment

Suppose we have $$n$$ items and $$n$$ agents and we want to assign one item to each agent. We have a probability matrix $$P$$ such that $$p_{i,j}$$ is the probability that agent $$i$$ gets item $$j$$. If $$\sum_j p_{i,j} = 1$$ for every agent $$i$$ and $$\sum_i p_{i,j} = 1$$ for every item $$j$$, then we can decompose $$P$$ into a probability distribution on deterministic assignments, such that the resulting lottery respects the probabilities in $$P$$. (see Birkhoff's algorithm)

Now, suppose we have $$m$$ items and $$n$$ agents and we want to assign a subset of items to each agent (such that the subsets are pairwise disjoint). We have a a probability matrix $$P$$ such that $$p_{i,S}$$ is the probability that agent $$i$$ gets subset $$S$$. Suppose $$\sum_S p_{i,S} = 1$$ for every agent $$i$$, and $$\sum_i \sum_{S\ni j} p_{i,S} = 1$$ for every item $$j$$. Can we decompose the matrix into probability distributions on deterministic allocations, such that the resulting lottery respects the probabilities in $$P$$?

• In general, the answer is no. For example, suppose there are 2 agents and 4 items (w,x,y,z). Suppose $$p_{1, wx} = p_{1,yz} = 1/2$$ and $$p_{2, wy} = p_{2,xz} = 1/2$$. Then in any decomposition, at least one of these probabilities would be 0.

I am interested in an approximate decomposition: is there any notion of a decomposition that approximates $$P$$ in some sense?

For example, suppose the agents have submodular utility functions over subsets of items, so that the original matrix $$P$$ gives each agent $$i$$ a certain expected utility $$u_i$$. Is there a decomposition of $$P$$ into a distribution on deterministic allocations, in which the utility of each agent $$i$$ is close to $$u_i$$?