Stable matchings when switches have costs

Question

The Gale-Shapley algorithm finds a stable matching in the complete bipartite graph, for any preference matrix. It's also well-known that stable matchings don't always exist in the complete graph (roommates problem), and it seems to be still open whether they almost surely don't exist in a uniformly random instance of the latter. See

http://arxiv.org/pdf/cond-mat/0509221.pdf

Given an instance of the marriage or roommates problem, call a matching \emph{$t$-stable} if there is no unmatched pair $\{x,y\}$ such that $x$ ranks $y$ at least $t$ places higher than his match, and similarly for $y$. There are a couple of obvious motivations for considering this extension: (i) imagine that there is a cost associated with switching partners (e.g.: the time and money it takes to physically move, or the "social cost" incurred to one's reputation as an unreliable roommate, or the cost imposed by the laws of the society - in Ireland, where I'm from, divorce was illegal up to the mid-1990s), (ii) maybe each person has a bounded ability to distinguish beteen alternative partners. Hence, someone won't switch unless the alternative is significantly better.

Now there are some obvious questions one can ask, in particular in the roommates problem, where $1$-stable matchings don't always exist. For example:

Question 1: What is the smallest function $t=t(n)$ such that every instance of the roommates problem on $n$ nodes has a $t$-stable matching ?

Question 2: Determine a threshold function $t=t(n)$ such that a random instance of the roommates problem on $n$ nodes almost surely has a $t$-stable matching when $t \gg t(n)$, and almost surely doesn't when $t \ll t(n)$.

Question 3: Given $t,n$, say $n$ even, describe an algorithm which decides whether an instance of the roommates problem on $K_n$ has a $t$-stable matching or not, and finds one if it has.

I have not been able to locate anything at all on this notion in the literature. Remarks ? By the way, regarding Question 1, I think I can construct an instance on $K_{n^2}$ where there is no $n$-stable matching. Is this best-possible ? Regarding Question 2, since it's not even known if $1$-stable matchings a.s. don't exist, finding the right threshold is probably hard. But can we bound it from above ? Regarding Question 3, Irving's algorithm for $1$-stable matchings doesn't seem to extend trivially to $t$-stability.

Answer 1

As a first approach to answering Question 3 we can consider the following integer programming formulation:

$\sum _{j}x_{i,j}=1\; \; \; \forall i,$

$x_{i,j}+\sum _{l:l<_{j}i}x_{l,j}+\sum _{l:l<_{i}j}x_{i,l}\leq 1\; \; \; \forall i,j,$

$x_{i,j}\in \left \{ 0,1 \right \}\; \; \; \forall i,j.$

See: http://www.columbia.edu/~js1353/marriage.ps p.18

The only difference between the IP formulation of the stable roommates problem (SRP) and its $t$-stable variant is in an interpretation. The expression "$l<_{j}i$" is interpreted as “$j$ prefers $i$ to $l$” or equivalently: “$i$ is higher, in the $j$'s preference list, than $l$” in the SRP. In the $t$-stable variant of the SRP it should be interpreted as “$i$ is at least $t$ positions higher, in the $j$'s preference list, than $l$".

There are some similarities between $t$-stable matchings and weakly stable matchings (as defined in Irving, R. W. and Manlove, D. F. (2002) The stable roommates problem with ties). It is known that deciding whether an instance of stable roommates problem admits a weakly stable matching is NP-complete. Thus, the above IP formulation may not be as bad as it seems at first.