¿Puede la asignación resolver el matrimonio estable?

Question

Esta es una excelente pregunta hecha por uno de mis estudiantes. Me imagino que la respuesta es "no", pero no me parecen tan fácil.

Recordar la puesta en marcha del matrimonio estable problema. Tenemos $n$ hombres y $n$ mujeres. Cada hombre ha ordenado las mujeres en algún orden, de acuerdo a lo mucho que a él le gustan, y cada una de las mujeres también ha clasificado a los hombres. Queremos que a la par de los hombres con las mujeres, de modo que NO existe ningún par $(m,w)$ e $(m', w')$ donde

• $m$ prefiere $w'$ a $w$ y
• $w'$ prefiere $m$ a $m'$.

Es un teorema de Gale y Shapley que tal asignación es siempre posible.

Aquí es un potencial de la forma en que usted puede tratar de encontrar un matching estable. Elija algunas de función $f: \{ 1,2,\ldots, n \}^2 \to \mathbb{R}$. Tomar el bipartito completo gráfico de $K_{n,n}$, con blanco vértices marcados por los hombres de negro y los vértices de las mujeres, y el peso de la arista $(m,w)$ por $f(i,j)$ si $w$ es $m$'s $i$-th preferencia, y $m$ es $w$'s $j$-th preferencia. A continuación encontrará una perfecta coincidencia de peso mínimo, utilizando algoritmos estándar para el problema de la asignación.

¿Hay alguna función de $f$ tal de que este método funciona para todas las listas de preferencia?

Answer 1

David pregunta es bastante más precisa que la cuestión de Donald Knuth mencionadas en la respuesta a continuación. Creo que puede ser contestada en sentido negativo para $n \geq 3$, como sigue.

Deje $\{m_1,m_2,\ldots,m_n\}$ e $\{w_1,w_2,\ldots,w_n\}$ ser los vértices de las partes de nuestro gráfico de $K_{n,n}$. Considere la posibilidad de una opción de preferencias, donde por $i\geq 3$ el hombre $m_i$ y la mujer $w_i$ son de primera selección. Entonces cualquier matrimonio estable debe coincidir uno con el otro.

Consideramos ahora las preferencias de $m_1,m_2,w_1$ e $w_2$. Voy a escribir $m_1 : w_1 \to 1, w_2 \to 3$ para denotar que $w_1$ es $m_1$-th primera opción y $w_2$, es el tercero, etc.

• $m_1 : w_1 \to 1, w_2 \to 2,$

  $m_2 : w_1 \to 2, w_2 \to 3,$

  $w_1 : m_1 \to 2, m_2 \to 3,$

  $w_2 : m_1 \to 1, m_2 \to 2.$

Aquí $m_1w_1, m_2w_2$ es un matching estable y por lo tanto, si la función de $f$ es como se desee, a continuación, debemos tener

$f(1,2)+f(3,2) < f(2,1)+f(2,3),$

donde a la izquierda tenemos el peso de la estable coincidentes y el de la derecha es el peso de la correspondencia $m_1w_2, m_2w_1$.

Pero el izquierdo y el lado derecho de la desigualdad anterior son simétricas y así por el cambio en el $m$'s y $w$'s podemos diseñar otro conjunto de preferencias que implica

$f(2,1)+f(2,3) < f(1,2)+f(3,2).$

De ello se sigue que la función de $f$ como se especifica en la pregunta no puede existir.

Answer 2

Una pregunta relacionada es "programación lineal resolver matrimonio estable?" John H. Vande Vate demostrado en 1989 ("de programación Lineal trae la felicidad conyugal") que la respuesta es "Sí". Él encontró un conjunto de desigualdades lineales cuyos puntos extremos son precisamente los matrimonios estables. Sus resultados fueron generalizadas y simplificado por Uriel Rothblum tres años más tarde ("Caracterización de matchings estables como puntos extremos de un polytope"). Rothblum la caracterización utiliza el estándar del problema de la asignación de restricciones y algunas restricciones adicionales que descartar la inestabilidad de los matrimonios. No se trata exactamente de lo que estás pidiendo, pero es relativa y entonces pensé que podría estar interesado.

Answer 3

A menos que me equivoco o si en el mientras tanto las cosas se han resuelto tu pregunta, parece ser esencialmente el mismo Problema 10 enumeran:

http://books.google.com/books?id=HqyCIky3bHwC&pg=PA64&dq=stable+marriage+assignment+problem&hl=en&ei=_VrdTLvuGsq34gaC0cQu&sa=X&oi=book_result&ct=result&resnum=7&ved=0CFAQ6AEwBg#v=onepage&q=stable%20marriage%20assignment%20problem&f=false

(En caso de que el enlace no funciona: este es el Problema 10, en el libro matrimonio Estable y su relación con otros problemas de combinatoria por Don Knuth)