El problema de emparejamiento estable, en su forma más básica, toma como entrada números iguales de dos tipos de participantes (n solicitantes de empleo y n empleadores, por ejemplo), y un orden para cada participante que da su preferencia sobre a quién emparejar entre los participantes del otro tipo. Un emparejamiento empareja a cada participante de un tipo con un participante del otro tipo. Un emparejamiento no es estable si:

1. Hay un elemento A del primer conjunto emparejado que prefiere algún elemento B dado del segundo conjunto emparejado sobre el elemento con el que A ya está emparejado, y
2. B también prefiere A al elemento con el que ya coincide B.

En otras palabras, un emparejamiento es estable cuando no existe un par (A, B) en el que ambos participantes se prefieran mutuamente a sus compañeros emparejados. Si existe tal pareja, el emparejamiento no es estable, en el sentido de que los miembros de esta pareja preferirían abandonar el sistema y emparejarse entre sí, dejando posiblemente a otros participantes sin emparejar. Siempre existe un emparejamiento estable, y el problema algorítmico que resuelve el algoritmo de Gale-Shapley es encontrarlo.^[3]​

El problema del emparejamiento estable también se ha denominado problema del matrimonio estable, utilizando una metáfora del matrimonio entre hombres y mujeres, y muchas fuentes describen el algoritmo de Gale-Shapley en términos de propuestas de matrimonio. Sin embargo, esta metáfora ha sido criticada por sexista y poco realista: los pasos del algoritmo no reflejan con exactitud el comportamiento humano típico o incluso estereotipado.^[4]​^[5]​

En 1962, David Gale y Lloyd Shapley demostraron que, para cualquier número igual de participantes de cada tipo, siempre es posible encontrar un emparejamiento en el que todas las parejas sean estables.^[6]​^[7]​ En 1984, Alvin E. Roth observó que, en esencia, el mismo algoritmo ya se utilizaba en la práctica desde principios de la década de 1950, como el «algoritmo Boston Pool» utilizado por el Programa Nacional de Emparejamiento de Residentes.^[1]​^[8]​

El algoritmo de Gale-Shapley implica una serie de «rondas» (o «iteraciones»). En términos de solicitantes de empleo y empleadores, puede expresarse del siguiente modo:^[9]​

• En cada ronda, uno o varios empleadores con puestos vacantes hacen una oferta de trabajo al candidato que prefieran, de entre los que aún no hayan hecho una oferta.
• Cada candidato que ha recibido una oferta la evalúa en relación con su puesto actual (si lo tiene). Si el candidato aún no está empleado, o si recibe una oferta de un empleador que le gusta más que su empleador actual, acepta la mejor oferta nueva y queda emparejado con el nuevo empleador (posiblemente dejando a un empleador anterior con un puesto vacante). En caso contrario, rechazan la nueva oferta.
• Este proceso se repite hasta que todas las empresas cubren sus vacantes o agotan sus listas de candidatos.

Para aplicar el algoritmo de forma eficaz, cada empleador debe ser capaz de encontrar rápidamente a su siguiente candidato, y cada candidato debe ser capaz de comparar rápidamente los empleadores. Una forma de hacerlo es numerar a cada candidato y a cada empleador de 1 a ${\displaystyle n}$ , donde ${\displaystyle n}$  es el número de empleadores y candidatos, y almacenar las siguientes estructuras de datos:^[10]​

• Un conjunto de empleadores con puestos vacantes
• Una matriz unidimensional indexada por empleadores, especificando el índice de preferencia del siguiente candidato al que el empleador enviaría una oferta, inicialmente 1 para cada empleador.
• Una matriz unidimensional indexada por candidatos, especificando su empleador actual, inicialmente un valor centinela como 0 indicando que están desempleados.
• Una matriz bidimensional indexada por un candidato y un empleador, que especifica la posición de ese empleador en la lista de preferencias del candidato.
• Una matriz bidimensional indexada por un patrón y un número ${\displaystyle i}$  de 1 a ${\displaystyle n}$  nombrando al solicitante que es el empleador de cada preferencia ${\displaystyle i}$  .

Configurar estas estructuras de datos requiere ${\displaystyle O(n^{2})}$  tiempo. Con estas estructuras es posible encontrar un empleador con un puesto sin cubrir, hacer una oferta de ese empleador a su siguiente candidato, determinar si la oferta es aceptada y actualizar todas las estructuras de datos para reflejar los resultados de estos pasos, en tiempo constante por oferta. Una vez que el algoritmo termina, la correspondencia resultante se puede leer de la matriz de empleadores para cada candidato. Puede haber ${\displaystyle O(n^{2})}$  ofertas antes de que cada empleador se quede sin ofertas que hacer, por lo que el tiempo total es de ${\displaystyle O(n^{2})}$ . ^[10]​

Aunque este límite de tiempo es cuadrático en el número de participantes, puede considerarse como tiempo lineal cuando se mide en términos del tamaño de la entrada, dos matrices de preferencias de tamaño ${\displaystyle O(n^{2})}$ .^[11]​

Este algoritmo garantiza que:

Al final, no puede haber ni un candidato ni un empleador sin emparejar. Un empleador que no haya sido seleccionado al final del proceso debe haber hecho una oferta a todos los candidatos. Pero un candidato que recibe una oferta permanece empleado durante el resto del proceso, por lo que no puede haber candidatos desempleados. Dado que el número de candidatos y de ofertas de empleo es igual, tampoco puede haber puestos vacantes.^[9]​

Ningún candidato X y ningún empleador Y pueden preferirse mutuamente a su pareja final. Si Y hace una oferta a X, entonces X sólo rechazaría a Y después de recibir una oferta aún mejor, por lo que X no puede preferir a Y a su pareja final. Y si Y deja de hacer ofertas antes de llegar a X en su lista de preferencias, Y no puede preferir a X a su pareja final. En cualquier caso, X e Y no forman una pareja inestable.^[9]​

Puede haber muchos emparejamientos estables para el mismo sistema de preferencias. Esto plantea la siguiente pregunta: ¿qué emparejamiento devuelve el algoritmo de Gale-Shapley? ¿Es el mejor emparejamiento para los candidatos, para los empresarios o uno intermedio? Resulta que el algoritmo de Gale-Shapley, en el que los empresarios hacen ofertas a los candidatos, siempre da como resultado el mismo emparejamiento estable (independientemente del orden en que se hagan las ofertas de trabajo), y su elección es el emparejamiento estable que es el mejor para todos los empresarios y el peor para todos los candidatos entre todos los emparejamientos estables.^[9]​

En una forma inversa del algoritmo, cada ronda consiste en que los candidatos desempleados escriben una única solicitud de empleo a su empleador preferido, y el empleador acepta la solicitud (posiblemente despidiendo a un empleado existente para hacerlo) o la rechaza. De este modo, se obtiene una coincidencia que es la mejor para todos los solicitantes y la peor para todos los empresarios entre todas las coincidencias estables. Estos dos emparejamientos son los elementos superior e inferior de la red de emparejamientos estables.^[12]​

En ambas formas del algoritmo, un grupo de participantes propone emparejamientos, y el otro grupo decide si acepta o rechaza cada propuesta. El emparejamiento siempre es mejor para el grupo que hace las propuestas, y peor para el grupo que decide cómo tratar cada propuesta.^[12]​

El algoritmo de Gale-Shapley es un mecanismo veraz desde el punto de vista del proponente. Esto significa que ningún proponente puede obtener un emparejamiento mejor falseando sus preferencias. Además, el algoritmo de Gale-Shapley es incluso a prueba de estrategia de grupo para los proponentes, es decir, ninguna coalición de proponentes puede coordinar una tergiversación de sus preferencias de modo que todos los proponentes de la coalición salgan estrictamente beneficiados.^[13]​ Sin embargo, es posible que alguna coalición tergiverse sus preferencias de modo que algunos proponentes salgan beneficiados y los demás mantengan la misma pareja.^[14]​

El algoritmo Gale-Shapley no es veraz para los participantes que no proponen. Cada uno puede tergiversar sus preferencias y conseguir una pareja mejor.^[15]​ Una forma particular de manipulación es el truncamiento: presentar sólo las alternativas superiores, dando a entender que las alternativas inferiores no son aceptables en absoluto. Con información completa, basta con considerar tergiversaciones en forma de estrategias de truncamiento. Sin embargo, para que la tergiversación tenga éxito es necesario conocer las preferencias de los demás agentes; sin ese conocimiento, la tergiversación puede dar a un agente una asignación peor. Además, incluso después de que un agente vea el emparejamiento final, no puede deducir una estrategia que garantice un mejor resultado en retrospectiva. Esto convierte al algoritmo de Gale-Shapley en un mecanismo de veracidad sin arrepentimiento. Además, en el algoritmo de Gale-Shapley, decir la verdad es la única estrategia que garantiza la ausencia de arrepentimiento. El algoritmo de Gale-Shapley es el único mecanismo sin arrepentimiento en la clase de mecanismos de emparejamiento cuantílico-estable.^[16]​

En su trabajo original sobre el problema, Gale y Shapley consideraron una forma más general del problema de emparejamiento estable, adecuada para la admisión en universidades y escuelas superiores. En este problema, cada universidad o facultad puede tener su propia cuota, un número objetivo de estudiantes a admitir, y el número de estudiantes que solicitan la admisión puede diferir de la suma de las cuotas, lo que necesariamente provoca que algunos estudiantes se queden sin emparejar o que algunas cuotas se queden sin cubrir. Además, las listas de preferencias pueden estar incompletas: si una universidad omite a un estudiante de su lista, significa que preferiría dejar su cupo sin cubrir que admitir a ese estudiante, y si un estudiante omite a una universidad de su lista, significa que preferiría seguir sin ser admitido que ir a esa universidad. No obstante, es posible definir emparejamientos estables para este problema más general, demostrar que los emparejamientos estables siempre existen y aplicar el mismo algoritmo para encontrar uno.^[6]​

Una forma del algoritmo de Gale-Shapley, realizada a través de un protocolo del mundo real en lugar de calculado en ordenadores, se ha utilizado para coordinar las admisiones a la educación superior en Francia desde 2018, a través del sistema Parcoursup. En este proceso, en el transcurso del verano antes del inicio de la escuela, los solicitantes reciben ofertas de admisión, y deben elegir en cada ronda del proceso si aceptan cualquier nueva oferta (y, en ese caso, rechazan cualquier oferta anterior que hayan aceptado). El método se complica con restricciones adicionales que hacen que el problema que resuelve no sea exactamente el problema de emparejamiento estable. Tiene la ventaja de que los estudiantes no tienen que comprometerse con sus preferencias al principio del proceso, sino que pueden determinar sus propias preferencias a medida que avanza el algoritmo, basándose en comparaciones directas entre las ofertas que han recibido. Es importante que este proceso realice un número reducido de rondas de propuestas, de modo que finalice antes de la fecha de inicio de las escuelas, pero aunque en teoría pueden producirse un número elevado de rondas, en la práctica no suelen ocurrir.^[17]​ Se ha demostrado teóricamente que, si el algoritmo de Gale-Shapley debe finalizar antes de tiempo, tras un número reducido de rondas en las que cada puesto vacante realiza una nueva oferta, produce, no obstante, emparejamientos que tienen una elevada proporción de participantes emparejados con respecto a los pares inestables.^[18]​

Shapley y Roth fueron galardonados con el Premio Nobel de Ciencias Económicas de 2012 «por la teoría de las asignaciones estables y la práctica del diseño de mercados». Gale había fallecido en 2008, por lo que no podía optar al premio.^[19]​