# When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods.

We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no actual bidding involved).

We may assume all of the entries in $V$ are distinct.

An assignment is a function $A:[n]\to [m]$. Denote $A^{-1}(j)=\{i\in[n]:A(i)=j\}$. Each good is then divided equally amongst the buyers it is assigned to, which value the good within $r$ factor of the highest valuation. A stable assignment is an assignment where no player would benefit from deviating from it to a different good (i.e. the current good assigned to him is in his best-response). Next I'll write it mathematically, but this paragraphs pretty much says it all.

For an assignment $A$, and a good $j\in[m]$, define by $c_j$ the maximum valuation of a user assigned to $j$ and by $B_j$ the set of buyers which value the good at most $r\cdot c_j$, i.e. $$c_j = \max_{i\in A^{-1}(j)} V_{i,j}$$ $$B_j = \{i\in [n]: V_{i,j}\geq r\cdot c_j\}$$

An $r$-stable (for some $r\in(0,1]$) assignment is a function $A:[n]\to [m]$ such that:

• Each player $i$, earns $U_i=\frac{V_{i,A(i)}}{|B_{A(i)}\cap A^{-1}(A(i))|}$ if $i\in B_{A(i)}$ or $0$ otherwise.
• No buyer has an incentive to "deviate" to a different good (in which he would get a positive payoff), i.e. if a buyer $i$ got a payoff of $x$, then: $$\forall i\in[n], j:i\in B_j:x\geq \frac{V_{i,j}}{|B_j\cap A^{-1}(j)|+1}$$

The questions are:

• Is there always a $r$-stable assignment (for every values of $r$ and $V$)?

• If we remove the "deviation" requirement (the second one), how much better could we be, in terms of the sum of payoffs to the buyers?

Notice that the special case of $r=1$ can be solved somewhat easily:

Consider a bipartite graph, where the buyers on one side and the goods on the other. Run the greedy maximum weight matching algorithm (every time, match the maximum value buyer-good pair such that neither the buyer or the good were matched yet).

This gives a $1$-stable assignment and it provides a $2$-approximation to the optimal maximum weight matching which does not consider the "deviation" constraint.

• For $m<n$ there is no 1-stable assignment. Do you assume $m\geq n$? – user35593 Feb 9 '15 at 13:41
• @user35593 - good point, I need to think whether to define it only for $m\geq n$ or to allow buyers without assigned goods. Will edit the question shortly. – R B Feb 9 '15 at 13:48
• @user35593 - actually, in my application I allow $m\geq n$, but if a user valuation is less than $r$ times the highest valuation, he gets payoff of $0$. Wondering what would be the best way to write it. – R B Feb 9 '15 at 13:52
• @user35593 - I've edited the question. The case of $n>m$ is allowed, but $n-m$ buyers would then get utility of $0$ (and will have no incentive to deviate). – R B Feb 9 '15 at 15:07