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.

  • 1
    $\begingroup$ For $m<n$ there is no 1-stable assignment. Do you assume $m\geq n$? $\endgroup$ – user35593 Feb 9 '15 at 13:41
  • $\begingroup$ @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. $\endgroup$ – R B Feb 9 '15 at 13:48
  • 1
    $\begingroup$ @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. $\endgroup$ – R B Feb 9 '15 at 13:52
  • $\begingroup$ @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). $\endgroup$ – R B Feb 9 '15 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.