3
$\begingroup$

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$?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.