text: Alocações, estabilidade e otimização
  uma introdução passo a passo
  Aline Guarnieri Gubitoso
  Vinicius Cifú Lopes
  
  SciELO Books / SciELO Livros / SciELO Libros
  GUBITOSO, G., and LOPES, V. C. Alocações, estabilidade e otimização: uma introdução passo a passo
  [online]. São Bernardo do Campo, SP: Editora UFABC, 2017, 142 p. ISBN: 978-85-6857-682-3.
  https://doi.org/10.7476/9788568576823.
  
  All the contents of this work, except where otherwise noted, is licensed under a Creative Commons Attribution 4.0
  International license.
  Todo o conteúdo deste trabalho, exceto quando houver ressalva, é publicado sob a licença Creative Commons Atribição
  4.0.
  Todo el contenido de esta obra, excepto donde se indique lo contrario, está bajo licencia de la licencia Creative
  Commons Reconocimento 4.0.
  
  ALOCAÇÕES,
  ESTABILIDADE
  E OTIMIZAÇÃO
  
  uma introdução passo a passo
  
  i
  
  Universidade Federal do ABC
  Prof. Dr. Klaus Werner Capelle - Reitor
  Prof. Dr. Dácio Roberto Matheus - Vice-Reitor
  Editora da UFABC
  Profª. Drª. Adriana Capuano de Oliveira - Coordenação
  Cleiton Fabiano Klechen
  Natalia Gea
  
  ii 
  
  Aline Guarnieri Gubitoso
  Vinicius Cifú Lopes
  
  ALOCAÇÕES,
  ESTABILIDADE
  E OTIMIZAÇÃO
  uma introdução passo a passo
  
  1ª Edição
  
  São Bernardo do Campo - SP
  2017
  
   iii
  
  © Copyright by Editora da Universidade Federal do ABC (EdUFABC)
  Todos os direitos reservados.
  Revisão
  Gerusa Bondan
  Projeto gráfico e diagramação
  Rita Motta, sob coordenação da Gráfica e Editora Copiart.
  Impressão
  Gráfica e Editora Copiart
  
  CATALOGAÇÃO NA FONTE
  SISTEMA DE BIBLIOTECAS DA UNIVERSIDADE FEDERAL DO ABC
  Responsável: Tatiana Hyodo CRB: 8ª/7392
  
  Alocações, estabilidade e otimização: uma introdução passo a passo / Aline
  Guarnieri Gubitoso e Vinicius Cifú Lopes — São Bernardo do Campo, SP : EdUFABC,
  2017.
  vi, 142 p. : il.
  A obra é resultado de projeto de pesquisa desenvolvido em iniciação científica.
  ISBN: 978-85-68576-60-1
  
  1. Teoria do emparelhamento. 2. Algoritmo de Gale-Shapley 3. Matemática –
  estudo e ensino. I. Gubitoso, Aline Guarnieri. II. Lopes, Vinicius Cifú.
  CDD 22 ed. – 519
  
  iv 
  
  Sumário
  
  Apresentação................................................................................................ 1
  
  1 O algoritmo de Gale-Shapley............................................................... 5
  1.1 Conceitos de estabilidade e bloqueio............................................ 5
  1.2 O mecanismo da aceitação postergada.......................................... 7
  1.3 O conceito de otimalidade........................................................... 16
  1.4 Programação de um computador................................................. 19
  
  2 Três extensões do problema............................................................... 23
  2.1 Trabalhando com indiferenças..................................................... 23
  2.2 Trabalhando com números diferentes de indivíduos.................. 31
  2.3 Permitindo poligamia................................................................... 38
  2.4 Recapitulação............................................................................... 45
  
  3 Resolução por programação linear.................................................... 47
  3.1 Programação linear...................................................................... 47
  3.2 Programação linear pelo Excel.................................................... 54
  3.3 Otimização linear no problema do casamento............................ 61
  3.4 Emparelhamento estável igualitário........................................... 77
  3.5 Discussão..................................................................................... 79
  
  4 Manipulação e trapaças....................................................................... 81
  4.1 Como ocorre a trapaça................................................................. 82
  4.2 Coalizões...................................................................................... 87
  4.3 Evitando a trapaça........................................................................ 89
  
  v
  
  5 O problema das admissões em universidades.................................... 91
  5.1 Exemplo com Gale-Shapley........................................................ 92
  5.2 Incertezas na prática descentralizada......................................... 94
  5.3 Semelhança e distinção com o problema do casamento............... 94
  5.4 Casos reais: residência médica e escolas públicas..................... 99
  
  6 O problema dos colegas de quarto.................................................. 107
  6.1 Algoritmo para resolução........................................................... 108
  6.2 Relação com o problema do casamento..................................... 120
  
  7 A matrícula em disciplinas na UFABC.............................................. 123
  7.1 O método contemporâneo......................................................... 124
  7.2 Nossa proposta........................................................................... 126
  Bibliografia comentada.......................................................................... 137
  
  vi 
  
  Apresentação
  Como podemos casar homens e mulheres de modo que não
  surjam amantes?
  A correspondência um a um entre homens e mulheres é chamada emparelhamento e, além disso, é estável quando não existirem
  homem e mulher que se prefiram simultaneamente aos respectivos
  cônjuges.
  David Gale e Lloyd Shapley reconheceram essa condição em
  1962 e, ao mesmo tempo, perceberam que um emparelhamento estável pode ser obtido por um procedimento passo a passo: uma versão organizada de propostas de casamento feitas pelos homens e
  comparadas pelas mulheres. Gale e Shapley ainda colocaram outro
  problema na mesma perspectiva de alocação por preferências: o da
  admissão em universidades.
  Duas décadas depois, Alvin Roth reconheceu que o procedimento descrito já era aproximadamente utilizado na seleção de médicos
  residentes pelos hospitais dos Estados Unidos, investigou as condições de funcionamento do procedimento e desenvolveu diversas variantes com fins específicos. O corpo de conhecimento resultante, a
  “teoria do emparelhamento”, também teve forte colaboração da brasileira Marilda Sotomayor e, devido à sua ampla aplicabilidade e sucesso na alocação de recursos, foi uma das inovações comemoradas
  em 2012 com a concessão do Nobel em economia a Shapley e Roth.
  Pretendemos, neste livro, trazer o assunto ao público escolar,
  com uma apresentação lusófona dos primeiros conceitos e técnicas envolvidos, para que o próprio estudante possa aplicá-los em
  situações similares que encontre e adquira entusiasmo por alguns
  tópicos de ciências econômicas, ciência da computação e matemática.
  1
  
  Esta exposição é voltada aos jovens no ensino médio ou ingressantes no ensino superior, como uma opção de assunto para estudo
  paralelo ao currículo obrigatório, seja orientado ou individual. Procuramos, portanto, adotar um discurso informal e detalhado que explica também algumas técnicas simples de raciocínio matemático,
  como: a introdução de objetos adicionais para equiparar quantidades diferentes de elementos; a resolução de questões de indiferença
  com uma extensão artificial da ordem; a metodologia de elementos
  notacionais auxiliares; o uso de variáveis booleanas na escrita de
  equações. Incluímos, enfim, um ou outro exercício de prática ou reflexão, mas sem pretender a compleição de um livro didático.
  Tivemos a preocupação de não apenas apresentar as “receitas” para atingir cada objetivo proposto – especialmente os algoritmos
  Gale-Shapley e Simplex (reduzido) –, mas, também, comentar por que
  funcionam e por que terminam (ou seja, obtêm seu objetivo após um
  número finito de passos), mesmo que de modo informal. Incluímos,
  também, uma apresentação pormenorizada de como montar problemas de otimização linear para resolução no programa Excel, de modo
  que o estudante poderá adaptá-la a qualquer situação.
  Mantemos a nomenclatura tradicional de exposição, que fala
  em “casar grupos de homens e mulheres, com os homens fazendo
  propostas de casamento e as mulheres avaliando suas melhores
  opções”. Apesar de extremamente machista, esse vocabulário é
  imediatamente claro para o leitor iniciante e tem, mesmo, a vantagem de usar seu aspecto machista para elucidar pontos importantes
  da teoria. Contudo, em momento algum fazemos apologia do machismo ou da cultura patriarcalista!
  Começamos com a descrição dos conceitos relevantes e do algoritmo de Gale-Shapley, para grupos de homens e mulheres com o
  mesmo número de indivíduos. Depois, tratamos de três expansões:
  listas de preferência com possíveis indiferenças; números diferentes
  de homens e mulheres; poligamia. Consideramos, então, outra teoria,
  a programação linear, ilustrando um processo manual de resolução e
  o uso do Excel, para, então, verificar como o problema do casamento
  pode ser formulado para esse tipo de otimização. Um capítulo relata
  2  aline guarnieri gubitoso | vinicius cifú lopes
  
  brevemente a possibilidade de qualquer procedimento de emparelhamento ser trapaceado através da prestação de falsas preferências e
  quais pontos de apoio existem para inibir esse mau comportamento.
  Outro capítulo trabalha sobre o problema de admissão em universidades, com mais detalhes do que a redução poligâmica oferece, e
  relata o caso concreto da residência médica americana.
  Apresentamos, também, o problema dos colegas de quarto,
  que requer o emparelhamento de indivíduos pertencentes a um único grupo e que ordenam segundo suas preferências, portanto, todos
  os demais participantes. A solução utiliza o algoritmo Gale-Shapley
  em uma primeira etapa, mas requer passos adicionais e uma alocação estável não é mais sempre possível.
  Finalmente, descrevemos, como um objeto de pesquisa, o sistema de matrícula em disciplinas na Universidade Federal do ABC,
  que é um problema de alocação por excelência e bastante complicado em vista da liberdade curricular característica da instituição e
  da necessária limitação de oferta de disciplinas e horários. Também
  em um formato adequado ao nosso público, propomos uma solução
  baseada nessas técnicas históricas.
  Incluímos uma bibliografia comentada, permitindo-nos utilizar
  mais esse espaço para a apresentação de informações adicionais.
  Queremos incentivar, portanto, o leitor a estudar, ainda essas últimas páginas.
  Este trabalho é produto da iniciação científica da primeira autora, sob orientação do segundo autor na UFABC, de agosto de 2014
  a julho de 2015. Ambos os autores contribuíram igualmente para a
  redação de todos os capítulos.
  Agradecemos a Rodrigo Lima e Clarissa Felippe por discutirem versões anteriores do projeto de pesquisa e a Renata Coelho
  por nos apresentar o sistema de matrículas em disciplinas da Graduação na UFABC. Agradecemos, também, ao CNPq, pelo apoio em
  forma de bolsa de iniciação científica para a primeira autora.
  São Bernardo do Campo
  Abril de 2016
  alocações, estabilidade e otimização  3
  
  1
  O algoritmo de Gale-Shapley
  Em vários problemas cotidianos, os preços não podem ser um
  mecanismo de alocação de recursos. Por exemplo, a atribuição de órgãos humanos a pacientes para transplante, por motivos éticos, não
  pode ser regulada por pagamentos financeiros, dando prioridade a
  quem possa pagar mais.
  Nós estudaremos a questão de estabilidade nas resoluções desses problemas. Exemplo de sua aplicação é a promoção, de forma abstrata, de pares perfeitos (envolvendo, assim, dois conjuntos de agentes), como de uniões entre homens e mulheres, estudada a partir do
  questionamento: “Como deve ser combinada uma mesma quantidade
  de homens e mulheres da melhor forma possível, respeitando suas
  preferências individuais?”.
  A solução encontrada por David Gale e Lloyd Shapley (1962)
  foi a utilização de regras pré-estabelecidas segundo um algoritmo,
  ou procedimento formado por passos ou etapas. Esse algoritmo baseia-se no “princípio da aceitação postergada” (em inglês deferred
  acceptance), isto é, as propostas de casamento somente serão definitivamente aceitas ao final do processo.
  
  1.1 Conceitos de estabilidade e bloqueio
  Vamos considerar a situação em que, havendo dois conjuntos
  de indivíduos ou agentes, estes devam ser combinados uns com os
  
  5
  
  outros da melhor forma possível, formando uma bijeção (correspondência um a um) entre os dois conjuntos, chamada emparelhamento.
  Definição: O emparelhamento é instável se houver um agente A pareado a um agente X, mas que preferiria estar com um
  agente Y, que também o preferiria. Nessa situação, há um “ganho inexplorado”, uma vez que, se A se unisse a Y, ambos estariam em uma melhor situação segundo suas preferências.
  Definição: O emparelhamento é estável se não for instável.
  No seguinte exemplo, temos 3 homens e 3 mulheres: Xavier (X);
  Yuri (Y); Zé (Z); Ana (A); Beatriz (B) e Carolina (C). Cada indivíduo tem uma lista de preferências, em que ordena os indivíduos do
  grupo oposto (com a utilização do símbolo “>”):
  Xavier:
  Yuri:
  Zé:
  
  B>C>A
  A>C>B
  B>C>A
  
  Ana:
  Beatriz:
  Carolina:
  
  X>Z>Y
  X>Y>Z
  Y>X>Z
  
  Isso significa que Xavier prefere Beatriz, depois Carolina, e,
  por último, Ana.
  A partir desses elementos, quais combinações entre homens e
  mulheres seriam possíveis? Quais desses emparelhamentos seriam
  adequados segundo a descrição acima de estabilidade?
  Contamos três opções de esposa para o primeiro homem, sobrando duas para o segundo, e, depois, uma para o terceiro, de modo que,
  multiplicando esses números, há seis emparelhamentos possíveis:
  (1) X – A; Y – B; Z – C
  (2) X – A; Y – C; Z – B
  (3) X – B; Y – A; Z – C
  
  (4)
  (5)
  (6)
  
  X – B; Y – C; Z – A
  X – C; Y – A; Z – B
  X – C; Y – B; Z – A
  
  Dentre essas seis possibilidades, podemos verificar pareamentos instáveis e estáveis, de acordo com a ideia de ganhos perdidos
  ou não.
  6  aline guarnieri gubitoso | vinicius cifú lopes
  
  As alocações que reúnem dois agentes que se preferem mutuamente são a 3 e a 4; isso porque as demais alocações não combinam Xavier e Beatriz, agentes que precisam, necessariamente,
  estar juntos porque se preferem mutuamente. Logo, o par (Xavier,
  Beatriz) bloqueia a formação de qualquer combinação de casais que
  não o una.
  Definição: Um par de bloqueio é, como (A,Y) na definição
  de instabilidade acima, um par de agentes que preferiria estar pareado entre si a seus respectivos pares.
  Além disso, um emparelhamento pode ser considerado bloqueado por um agente se, para ele, tal alocação for absolutamente
  inaceitável, isto é, pior do que continuar sem combinação. No caso
  do problema do casamento, trata-se da preferência por permanecer
  solteiro, uma variação do problema que estudaremos mais à frente,
  no próximo capítulo.
  
  1.2 O mecanismo da aceitação postergada
  Foi em busca de soluções estáveis aos problemas cotidianos
  que o algoritmo de Gale-Shapley foi estudado, testado empiricamente e, até mesmo, aplicado no mundo real, ainda que sua aplicação difira deste ideal em alguns pontos.
  As operações para a promoção do casamento estável a partir deste algoritmo podem ser utilizadas tanto pelos homens, sendo quem propõe o casamento, como pelas mulheres, propondo-o ao
  grupo oposto. Ainda assim, o resultado das uniões não precisa ser
  necessariamente igual nas duas formas para que as alocações sejam
  consideradas estáveis, uma vez que qualquer alocação formada por
  este algoritmo é provada estável.
  Quando temos situações com uma quantidade muito grande
  de elementos, como o número de vestibulandos procurando universidades, não é viável procurarmos todas as combinações possíveis
  alocações, estabilidade e otimização  7
  
  entre os agentes e, depois, dentre estas, as que são estáveis (isto
  é, que não sofrem bloqueio e não são instáveis). Logo, a utilização do algoritmo será extremamente vantajosa para a descoberta
  mais rápida e eficiente de uma alocação estável, ainda que seu
  resultado seja somente a apresentação de uma única combinação
  possível de estabilidade dentre várias possíveis. Se é necessária a
  descoberta de todas as opções estáveis de alocação, teríamos que
  usar um segundo algoritmo para a resolução do problema, além do
  que apresentaremos.
  Para expor esse raciocínio pelo qual se desenvolve o algoritmo
  de Gale-Shapley, segue uma demonstração do processo de alocação
  de casais em atribuições estáveis. A título de exemplo, tomamos o
  universo de 5 homens e 5 mulheres, sendo eles: Victor (V); Wilson
  (W); Xavier (X); Yuri (Y); Zé (Z); Ana (A); Beatriz (B); Carolina (C);
  Débora (D); Érica (E).
  A fim de seja respeitada a preferência individual de cada uma
  dessas pessoas, cada uma deve listar os membros do outro grupo de
  acordo com uma ordem de preferência para a escolha de seu parceiro
  de casamento. Assim, o primeiro passo do algoritmo é que as pessoas
  de ambos os grupos listem as pessoas do grupo oposto segundo uma
  ordem de preferência.
  Notação: Para denotar a preferência de A por X antes de
  Y, utilizamos o símbolo “>”, da seguinte forma: X >AY, que
  significa que A prefere X a Y. Além disso, utilizamos o mesmo
  sinal com o sentido oposto < na forma de Y <AX para, também,
  denotar que Y é menos preferível que X por A.
  Começando pelos homens, Victor determina sua lista de preferência da seguinte forma: ele prefere Ana a Carolina, mas prefere
  Carolina a Débora. Senão, prefere Débora a Érica e, por fim, Érica é
  mais preferível que Beatriz. Sendo assim, sua primeira opção é Ana
  e sua última opção é Beatriz, ou seja:
  Victor: A > C > D > E > B
  8  aline guarnieri gubitoso | vinicius cifú lopes
  
  Já Wilson ao fazer sua própria lista, ordena suas próprias preferências, de modo que escolhe Ana como a mulher mais preferível
  para se casar, preferindo-a a Débora. Admite, porém, que preferiria
  Débora a Érica e Érica a Beatriz, ainda que preferisse Beatriz a
  Carolina, de forma que Beatriz fosse sua penúltima opção, enquanto Carolina fosse a última, ou seja:
  Wilson: A > D > E > B > C
  Dessa forma, seguem-se as listas de preferência de cada indivíduo:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A>C>D>E>B
  A>D>E>B>C
  D>C>B>A>E
  A>D>B>E>C
  C>D>A>B>E
  
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  Z>W>V>Y>X
  V>X>Y>Z>W
  Z>W>V>X>Y
  V>W>Y>X>Z
  W>Z>X>Y>V
  
  O segundo passo é a proposta de um grupo ao outro, segundo
  a lista de preferência de cada pessoa do grupo que faz alguma coisa. Nós identificaremos os homens como agentes proponentes e as
  mulheres, que somente poderão escolher dentre as propostas recebidas, como agentes seletores.
   Notação: Para denotar quem propõe a quem, usaremos
  uma flecha especial “⇝”, da seguinte forma: X, Y, ... ⇝ A que
  significa que X, Y, ... propõem para A. A escolha por este símbolo em especial é motivada pelo fato de que é utilizada em
  física para indicar transferência ou envio de informação, o que
  corresponde à situação de fazer uma proposta de casamento.
  Para indicar quando ninguém propõe a A, usaremos o símbolo
  de vazio: ∅ ⇝ A.
  
  Assim, os homens propõem às mulheres de que mais gostam,
  de forma a escolher a primeira em cada lista de preferência.
  alocações, estabilidade e otimização  9
  
  Notação: Para denotar o parceiro correspondente de cada
  indivíduo, utilizaremos a moldura ⎕ ao redor desse parceiro
  na lista do indivíduo.
  As propostas da primeira rodada começam com:
  1ª Rodada – propostas
  Victor:
  
  Wilson:
  
  Xavier:
  
  Yuri:
  Zé:
  
  A >C>D>E>B
  
  A >D>E>B>C
  
  D >C>B>A>E
  
  A >D>B>E>C
  
  C >D>A>B>E
  
  V⇝A
  
  W⇝A
  X⇝D
  Y⇝A
  
  Z⇝C
  
  A preferência de Victor, Wilson e Yuri é por Ana, de forma que
  todos eles propõem a ela, enquanto Xavier escolhe propor a Débora
  e Zé a Carolina, uma vez que são elas as mulheres de que eles mais
  gostam.
  Em sequência, as mulheres que receberam pedidos ou propostas de casamento (se houver alguma) escolhem o parceiro que acreditam ser a opção mais atrativa, rejeitando as outras propostas.
  Notação: Para indicar a escolha de um indivíduo a um outro, como a escolha de uma mulher por um homem, utilizaremos o símbolo “:”, de forma que A: X significa que A escolhe a
  proposta de X.
  Assim, cada mulher, ao analisar as propostas que recebeu (se
  recebeu alguma), escolhe, dentre os homens que lhe propuseram,
  aquele que é o mais preferível em sua lista de preferência rejeitando
  as demais propostas (se houver).
  
  10  aline guarnieri gubitoso | vinicius cifú lopes
  
  1ª Rodada – escolhas
  V, W, Y ⇝ A Ana:
  ∅ ⇝ B Beatriz:
  
  Z ⇝ C Carolina:
  X ⇝ D Débora:
  ∅ ⇝ E Érica:
  
  Z> W >V>Y>X
  V>X>Y>Z>W
  
  Z >W>V>X>Y
  V>W>Y> X >Z
  W>Z>X>Y>V
  
  ∴ A:W
  
  ∴ C:Z
  
  ∴ D:X
  
  No caso de Ana, entre Victor, Wilson e Yuri, segundo sua
  lista de preferência, o preferido Wilson. Assim, ela escolhe Wilson.
  Já Carolina, por somente receber a proposta de Zé, escolhe-o automaticamente. Também Débora escolhe Xavier, porque é o único que lhe propõe. Portanto, na primeira rodada de propostas, as
  escolhas são feitas de tal modo, que Wilson é escolhido por Ana,
  Zé por Carolina e Xavier por Débora, enquanto Victor e Yuri são
  rejeitados por Ana.
  Atenção: É importante registrar a rejeição por cada mulher nas listas dos homens pretendentes, para executar o algoritmo de forma
  manual. No papel, podemos optar por riscar as sucessivas opções,
  mas, aqui, adotaremos uma notação específica. Além disso, também
  é natural riscar as listas das mulheres, mas veremos que não há necessidade nesse caso.
  Notação: Para denotar que A rejeitou V, marcaremos um
  circunflexo em Â na lista de V.
  Contudo, o processo continua com a segunda rodada de escolhas a partir de novas propostas feitas às mulheres pelos homens que
  foram rejeitados, de forma que os homens rejeitados façam, então,
  uma nova proposta, dessa vez, às mulheres que acreditam ser a segunda melhor opção.
  
  alocações, estabilidade e otimização  11
  
  2ª Rodada – propostas
  Victor:
  
  Â>C >D>E>B
  
  Wilson:
  
  A >D>E>B>C
  
  Xavier:
  
  D >C>B>A>E
  
  Yuri:
  
  Â>D>B>E>C
  
  Zé:
  
  C >D>A>B>E
  
  V⇝C
  
  W⇝A
  
  X⇝D
  
  Y⇝D
  Z⇝C
  
  No caso de Victor, ao ser rejeitado por Ana, ele decide propor a Carolina, enquanto Yuri, também rejeitado por Ana, propõe
  a Débora. Os homens que foram escolhidos na rodada anterior
  continuam a propor às mesmas mulheres que os escolheram.
  Dadas as novas propostas, as mulheres analisam suas novas
  opções, assim como as que haviam escolhido na etapa anterior, e
  escolhem uma delas cada, rejeitando as demais.
  2ª Rodada – escolhas
  W⇝A
  
  Ana:
  
  X, Y ⇝ D
  
  Débora:
  
  ∅⇝B
  
  Beatriz:
  
  ∅⇝E
  
  Érica:
  
  V, Z ⇝ C
  
  Carolina:
  
  Z>W >V>Y>X
  
  ∴ A:W
  
  V>X>Y>Z>W
  
  Z >W>V>X>Y
  
  ∴ C:Z
  
  V>W> Y >X>Z
  
  ∴ D:Y
  
  W>Z>X>Y>V
  
  Ana, por não receber nenhuma nova proposta, continua com
  Wilson, ao passo que Carolina, mesmo recebendo uma nova proposta por parte de Victor, continua a escolher Zé. Entre Xavier e a nova
  proposta de Yuri, Débora prefere Yuri, escolhendo, assim, trocar de
  parceiro. Consequentemente, Victor e Xavier são os homens rejeitados.
  Uma vez que esse processo continua até que todos os homens
  sejam escolhidos por alguma mulher ou rejeitados por todas elas,
  dado que nenhum homem volta a propor a uma mulher que já o
  rejeitou (porque, uma vez rejeitado, ele a elimina de sua lista), a
  terceira rodada do algoritmo continua com novas propostas:
  
  12  aline guarnieri gubitoso | vinicius cifú lopes
  
  3ª Rodada – propostas
  Victor:
  
  Â>Ĉ>D >E>B
  
  Xavier:
  
  D>C >B>A>E
  
  Wilson:
  Yuri:
  Zé:
  
  A >D>E>B>C
  ^
  
  Â>D >B>E>C
  
  C >D>A>B>E
  
  V⇝D
  
  W⇝A
  
  X⇝C
  
  Y⇝D
  Z⇝C
  
  Xavier, que foi rejeitado por Débora, decide, nesta rodada,
  propor a Carolina, enquanto Victor, que foi rejeitado tanto por Ana
  como por Carolina, propõe agora a Débora. Ao mesmo tempo, as
  propostas anteriores bem-sucedidas mantêm os parceiros, como as
  uniões de Wilson e Ana, Yuri e Débora, Zé e Carolina.
  Feitas as novas propostas, as mulheres que as receberam,
  Débora e Carolina, comparam tais pedidos, enquanto que as demais
  mulheres continuam com o companheiro escolhido anteriormente:
  3ª Rodada – escolhas
  W⇝A
  
  ∅⇝B
  
  Z, X ⇝ C
  
  Y, V ⇝ D
  
  ∅⇝E
  
  Ana:
  
  Z>W>V>Y>X
  
  Beatriz:
  
  V>X>Y>Z>W
  
  Carolina:
  
  Z >W>V>X>Y
  
  Débora:
  
  V >W>Y>X>Z
  
  Érica:
  
  W>Z>X>Y>V
  
  ∴ A:W
  
  ∴ C:Z
  
  ∴ D:V
  
  Ao não receber nenhuma nova proposta, Ana continua com
  Wilson. Simultaneamente, Carolina também continua a escolher o
  mesmo parceiro da rodada anterior, Zé, ainda que tenha recebido
  uma proposta de Xavier. Contudo, Débora prefere trocar seu parceiro anterior, Yuri, ao escolher Victor como seu novo parceiro. Em
  conformidade com tais decisões, na terceira rodada de escolhas,
  temos Ana emparelhada a Wilson, Carolina com Zé e Débora com
  Victor, sendo as propostas de Xavier e Yuri as rejeitadas.
  
  alocações, estabilidade e otimização  13
  
  Por isso, na quarta rodada, Xavier e Yuri, os homens rejeitados na rodada anterior, fazem novas propostas, segundo a ordem de
  suas listas de preferência:
  4ª Rodada – propostas e escolhas
  Cada homem propõe à primeira mulher, em sua lista, que não
  o rejeitou:
  V ⇝ D; W ⇝ A; X,Y ⇝ B; Z ⇝ C.
  
  Cada mulher opta pelo melhor homem, em sua lista, que lhe
  propôs (agora ou na rodada anterior):
  D : V; A : W; B : X; C : Z.
  Dessa maneira, de acordo com o processo descrito, após essa
  nova rodada de propostas e escolhas, obtemos:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  Â>Ĉ>D >E>B
  A>D>E>B>C
  D>Ĉ>B >A>E
  ^
  
  ^
  
  ^
  
  Â>D>B>E >C
  C >D>A>B>E
  
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  Z>W>V>Y>X
  V>X >Y>Z>W
  Z >W>V>X>Y
  V >W>Y>X>Z
  W>Z>X>Y >V
  
  Devido ao de fato de que Beatriz, até então, não havia recebido
  nenhuma proposta, ao receber simultaneamente as propostas de
  Xavier e Yuri, ela decide que, entre eles, prefere Xavier. Dessa forma, Yuri é o único homem ainda rejeitado.
  Portanto, na quinta rodada, somente Yuri faz uma nova proposta:
  5ª Rodada – propostas e escolhas
  V ⇝ D; W ⇝ A; X ⇝ B; Y ⇝ E; Z ⇝ C.
  D : V; A : W ; B : X; E : Y; C : Z.
  14  aline guarnieri gubitoso | vinicius cifú lopes
  
  Mais uma vez ocorre uma mudança nas alocações a partir da
  nova proposta dessa rodada, feita por Yuri a Érica, após ser rejeitado três vezes. Ela aceita-o automaticamente por ser a única proposta que recebe:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  Â>Ĉ> D >E>B
  A >D>E>B>C
  ^
  D>Ĉ> B >A>E
  ^
  ^
  Â>D>B> E >C
  C >D>A>B>E
  
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  Z>W>V>Y>X
  V>X >Y>Z>W
  Z >W>V>X>Y
  V >W>Y>X>Z
  W>Z>X> Y >V
  
  Finalmente, não é mais preciso continuar o processo, porque,
  nesta última rodada, nenhum homem foi rejeitado, de forma que todos os homens e mulheres estão agora casados em um emparelhamento considerado estável (não há nenhuma mulher que preferisse
  estar com algum homem que também preferisse estar com ela, ao
  invés de sua parceira).
  Por exemplo, se Victor não é casado com Ana, mesmo que a preferisse como sua primeira opção ao invés de Débora (sua esposa),
  é porque, no passado, ele propôs a Ana, mas foi rejeitado em favor
  de alguém de que ela gostava mais, no caso, Wilson (e, caso Ana
  depois rejeitasse Wilson, seria por Zé, ainda melhor). Portanto, o
  par (V, A) não é um par de bloqueio e o mesmo raciocínio se aplica
  a qualquer outro par.
  Note que o algoritmo sempre termina, isto é, sua execução
  chega a um término, porque: cada lista de preferência é finita; o
  número de agentes proponentes é finito; nenhum deles repete uma
  proposta após rejeição.
  Nos próximos capítulos, teremos mais oportunidades de acompanhar o desenvolvimento do algoritmo Gale-Shapley passo a passo.
  A próxima seção contém exercícios que o leitor já pode efetuar, bastando que ignore a comparação dos emparelhamentos obtidos.
  
  alocações, estabilidade e otimização  15
  
  1.3 O conceito de otimalidade
  Nesse mecanismo de alocações que distribui de maneira estável os indivíduos, há uma configuração específica nos resultados
  que impõe o algoritmo como mais favorável a um dos grupos, dos homens ou das mulheres, especificadamente àquele que faz as propostas. Isto porque quem faz as propostas, como os homens, no exemplo
  acima, começa sempre com a possibilidade de unir-se à sua melhor
  opção, por fazer o pedido a quem mais gosta, porém, se não for escolhido por ela, ainda tem chance de propor à sua segunda melhor
  opção e, se for rejeitado mais uma vez, pode fazer o pedido à sua
  terceira opção, e assim por diante, até que seja escolhido por uma
  ou rejeitado por todas. Consequentemente, como mostra a movimentação de sua moldura ⎕ da esquerda para a direita, o homem
  termina o processo de alocação com a melhor opção possível de
  parceira que também o prefira.
  Ao passo que uma mulher, ao depender dos pedidos dos homens, somente consegue escolher a melhor opção dentre as que recebe e não a que viria ser sua melhor opção na lista de preferências,
  pois, se o homem que mais lhe agrada não lhe propor, não poderá
  escolhê-lo. A partir da primeira proposta que recebe, pode escolher
  um parceiro e trocá-lo conforme receber uma proposta melhor a
  cada rodada, mas não é garantido que chegue até sua melhor opção,
  especialmente se receber somente uma proposta. Assim, suas escolhas, motivadas por suas preferências individuais, representadas
  pela moldura ⎕, deslocam-se da direita para a esquerda, no sentido
  oposto ao dos homens. Concluímos que as mulheres obtêm suas piores opções possíveis.
  Exemplo disso é o pareamento de Beatriz com Xavier, sua
  segunda melhor opção, no desenvolvimento da seção anterior:
  para isso, ela rejeitou a proposta de Yuri, mas, mesmo assim, não
  alcançou o que considera o melhor pareamento, uma vez que Victor,
  sua primeira escolha, não lhe fez nenhuma proposta.
  Em vista disso, os economistas identificam a seguinte classificação:
  
  16  aline guarnieri gubitoso | vinicius cifú lopes
  
  Definição: Uma alocação é ótima para um conjunto de
  agentes se, nessa alocação, cada um obtém o melhor par que
  poderia obter em qualquer alocação.
  Esse é o caso do emparelhamento realizado pelo algoritmo
  quando os homens propõem, sendo ótimo para o conjunto de todos
  os homens, dentre os demais emparelhamentos estáveis.
  Para cada agente, o melhor par possível (ou seu “ótimo”) não é,
  necessariamente, o primeiro em sua lista de preferência (em nosso
  exemplo, para Xavier, o melhor possível é Beatriz, e, não, Débora).
  É com esse cuidado que a literatura técnica faz tal referência e que
  também falaremos neste livro.
  Observação: Nosso raciocínio com as molduras se deslocando, acima, sugere que o emparelhamento obtido é ótimo para o conjunto de
  agentes proponentes; porém, não constitui uma demonstração, que
  precisa considerar qualquer outro emparelhamento potencialmente
  melhor, não obtido pelo método descrito. Esse cuidado também será
  necessário no Capítulo 4, que versa sobre estratégias.
  Para fazer a demonstração, suponha que um homem X pode
  casar, em um segundo emparelhamento pretensamente estável,
  com uma mulher A que prefere à esposa atribuída pela execução de
  Gale-Shapley com os homens proponentes. Então, A o rejeitou durante esta execução em nome de Y, a quem prefere. Dentre todas as
  situações, vamos trabalhar, portanto, com a primeira vez que uma
  tal A rejeita um tal X. Nesse caso, Y ainda não foi rejeitado, durante
  esta execução, por mulheres com quem poderia se casar num outro
  emparelhamento estável. Concluímos que todas as suas “esposas viáveis” são, digamos, B, C, ... ≤Y A. Em particular, naquele segundo emparelhamento pretensamente estável, Y casa-se com alguma B <Y A,
  então (Y, A) forma um par de bloqueio ao segundo emparelhamento,
  que não pode ser estável.
  Outra característica do algoritmo é dada pelo fato de que,
  no desenvolver do mecanismo, utilizado tanto na forma de homens
  
  alocações, estabilidade e otimização  17
  
  propondo como na de mulheres, a partir das mesmas listas de preferência, nem sempre os casais formados serão os mesmos nas duas
  situações, o que não impede que sejam considerados estáveis. Assim,
  caso sejam as mulheres a realizar propostas, podemos obter um outro
  emparelhamento, ótimo para as mulheres e péssimo para os homens.
  Nesse caso, é possível comparar todos os emparelhamentos estáveis
  e mostrar que se situam entre esses dois extremos, o ótimo para os
  homens e o ótimo para as mulheres.
  No entanto, também é possível ocorrer situações, dependendo
  das listas de preferência, em que sejam formados casais iguais nos
  dois processos. Nessas situações, como qualquer outro emparelhamento estável deve estar entre os dois ótimos, concluímos que existe
  somente essa alocação estável, que é ótima para todos. Para os indivíduos envolvidos não há nenhuma outra alocação que os beneficie
  mais, sem comprometer a condição de estabilidade.
  
   Exercícios
  1) Aplique o algoritmo, a partir das mesmas listas de preferência do
  exemplo acima, do ponto de vista da proposta feita pelas mulheres,
  verificando a existência de emparelhamento ótimo para todos (com
  resultado igual ao exemplo acima). Repetimos as listas abaixo:
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  Z>W>V>Y>X
  V>X>Y>Z>W
  Z>W>V>X>Y
  V>W>Y>X>Z
  W>Z>X>Y>V
  
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A>C>D>E>B
  A>D>E>B>C
  D>C>B>A>E
  A>D>B>E>C
  C>D>A>B>E
  
  Resultado: O emparelhamento é ótimo para todos, pois, em ambos os processos,
  obtemos os pares V – D; W – A; X – B; Y – E e Z – C.
  
  2) A partir das seguintes listas de preferência, determine os emparelhamentos feitos tanto quando os homens propõem como quando as
  mulheres propõem e analise se ocorre uma alocação ótima para todos:
  18  aline guarnieri gubitoso | vinicius cifú lopes
  
  Otávio (O):
  Pedro (P):
  Rodrigo (R):
  Sérgio (S):
  Thiago (T):
  
  J>L>N>I>M
  I>J>L>M>N
  I>M>J>L>N
  J>L>M>I>N
  M>J>I>L>N
  
  Isabella (I):
  Joana (J):
  Laura (L):
  Marina (M):
  Natália (N):
  
  T>O>R>S>P
  T>S>R>O>P
  T>P>O>R>S
  P>R>S>T>O
  R>O>S>P>T
  
  Resultado: Os pares formados quando os homens propõem são: O – N, P – L, R – I, S – J,
  T – M. Os pares formados quando as mulheres propõem são: I – R, J – T, L – P, M – S,
  N – O. Consequentemente, não há um emparelhamento ótimo para todos, porque
  as alocações diferem e os pares Sérgio–Joana e Thiago–Marina são trocados.
  
  1.4 Programação de um computador
  Esta seção é voltada ao leitor interessado na programação do
  algoritmo Gale-Shapley em um computador; em outras palavras,
  como o mesmo pode ser implementado em uma linguagem de programação sequencial.
  A importância da noção de algoritmo e de ter algoritmos para
  resolver problemas é que tais métodos são totalmente especificados em uma sequência de passos ou etapas, não deixando nenhum
  procedimento ou escolha a critério de quem os utiliza. Desse modo,
  primeiramente, tais procedimentos podem ser delegados a máquinas que trabalham muito rápido, mas sem nenhuma criatividade:
  os computadores.
  Em segundo lugar, se duas pessoas seguirem o mesmo algoritmo para resolver um mesmo problema (com as mesmas informações),
  elas deverão obter o mesmo resultado, ainda que trabalhem de modo
  independente. (Algoritmos podem, sim, utilizar fontes aleatórias de
  informação, com fins de simular um mesmo experimento ou montagem muitas vezes e variadamente, mas produzirão o mesmo resultado toda vez que a mesma sequência de informação for utilizada.)
  O resultado obtido com o algoritmo, por sua vez, é definido pelo
  método e passível de estudo formal, como vimos ao identificar a otimalidade de Gale-Shapley para os agentes proponentes, o que não
  seria possível para uma escolha arbitrária de emparelhamento estável, nem demonstrável sem conhecer o funcionamento do método.
  alocações, estabilidade e otimização  19
  
  A principal diferença desta seção em relação à apresentação
  anterior, que já é “procedural”, consiste na representação apropriada das informações no computador, mas, fazemos, também, uma
  pequena modificação no procedimento em que, antes, as mulheres
  avaliavam todas as propostas recebidas, inclusive aquela selecionada na rodada anterior, enquanto agora avaliarão cada proposta
  assim que for recebida. Essa alteração pode diminuir o número de
  rodadas ou antecipar a rodada de rejeição para cada homem, mas
  mantém o mesmo resultado.
  Utilizamos alguns raciocínios e estruturas presentes em Knuth
  (1997), especialmente sua Aula 6. Porém, não o seguimos totalmente;
  utilizamos alguma redundância e trabalhamos com nossa hipótese
  atual de um mesmo número de homens e mulheres, digamos n.
  O programa representará tanto os homens como as mulheres
  como números de 1 a n. A primeira tarefa é ler e armazenar suas
  listas de preferência. Começamos com uma matriz ListasHomens,
  cuja posição (i,j) registra a j-ésima opção do homem i em ordem decrescente. Desse modo, ListasHomens é semelhante à listagem que
  fizemos no texto:
  para i de 1 a n:
  		para j de 1 a n:
  			leia k (identificação da mulher);
  			armazene k em ListasHomens (i,j).
  As listas das mulheres serão armazenadas de um modo diferente, para facilitar a comparação das propostas recebidas: a posição (i,j)
  da matriz NotasMulheres identificará, para a mulher i, qual é a “nota”
  do homem j em sua lista, de modo que o primeiro homem tem nota n o
  segundo tem nota n – 1 e assim por diante, até o último, que tem nota 1.
  Observe que os homens mais preferidos têm notas mais altas. Essa
  lista requer cuidado em seu carregamento, a partir das listas, como
  feitas nos exemplos:
  		 para i de 1 a n:
  				 para k de 1 a n:
  					leia j (identificação do homem);
  					armazene n + 1 – k em NotasMulheres (i,j).
  20  aline guarnieri gubitoso | vinicius cifú lopes
  
  Agora precisamos criar um registro de onde está a moldura
  nas listas dos homens e das mulheres. Para os homens, registraremos a posição da moldura, mas, para as mulheres, registraremos
  o conteúdo da moldura. Usaremos, para começar, o número 0, mas
  pode ser necessário adotar outro número ou símbolo, dependendo
  do uso dos índices acima na linguagem de programação. Também
  precisamos saber quem está rejeitado ou sem propostas.
  para i de 1 a n:
  		
  armazene 0 em MoldurasHomens(i) e NoivosMulheres(i);
  		
  armazene SIM em HomensLivres(i) e MulheresLivres(i);
  Agora, fazemos com que cada homem realize sua proposta e
  seja avaliado pela mulher eleita, que pode ou não o substituir em
  detrimento do anterior (se houver). Ela fará isso em uma cadeia de
  condicionais “se–caso contrário”:
  (*) para i de 1 a n:
  se HomensLivres(i) = SIM então:
  		
  aumente MoldurasHomens(i) uma unidade;
  		
  armazene MoldurasHomens(i) em j;
  		
  se MulheresLivres(j) = SIM então:
  				 armazene i em NoivosMulheres(j)
  				 armazene NÃO em MulheresLivres(j) e HomensLivres(i).
  		
  caso contrário, se
  			 NotasMulheres (j,i) > Notas Mulheres(j), NoivosMulheres(j)
  		 então:
  				 armazene SIM em HomensLivres(NoivosMulheres(j);
  				 armazene NÃO em HomensLivres(i);
  				 armazene i em NoivosMulheres(j).
  Devemos verificar se algum homem foi rejeitado, o que requer
  uma nova rodada de propostas:
  		 para i de 1 a n:
  				 se HomensLivres(i) = SIM então:
  					
  retorne ao ponto (*).
  alocações, estabilidade e otimização  21
  
  No caso de um número distinto de homens e mulheres, veremos, futuramente, que se deve incluir nessa condição o teste de
  ainda não ter percorrido toda a sua lista de preferência.
  Finalmente, podemos imprimir os casais formados:
  		 para i de 1 a n:
  				 escreva “i casado com MoldurasHomens(i)”.
  Uma preocupação moderna com algoritmos é sobre sua eficiência, isto é, o número de passos ou operações que o algoritmo requer que o computador faça, especialmente em função do tamanho
  do problema especificado, aqui, o número n de homens ou mulheres.
  Mesmo com os últimos avanços da tecnologia, preocupações com o
  tempo de execução e com o espaço necessário (tamanho da memória)
  são cotidianos, porque as dimensões dos problemas a serem tratados na prática também crescem rapidamente.
  Informações mais apropriadas sobre eficiência, sua definição e
  seu cálculo, constituem um tema da ciência da computação e podem
  ser inicialmente obtidas em Knuth (1997) e Gusfield; Irving (1989).
  Aqui, relatamos apenas que Gale-Shapley, na forma desta seção,
  pode requerer passos da ordem de até n2 para terminar; por “ordem”,
  aqui, entende-se que esse número de passos, em função de n, é um
  polinômio de segundo grau ou é limitado por um tal polinômio; para
  valores muito grandes de n, o termo de segundo grau domina os demais. Note que também a entrada de dados, isto é, a leitura das listas
  de preferência, já requer 2n2 operações de leitura simples; então, é
  significativo que o procedimento em si não supere essa ordem.
  
  22  aline guarnieri gubitoso | vinicius cifú lopes
  
  2
  Três extensões do problema
  Nossa apresentação do algoritmo de Gale-Shapley, no capítulo
  anterior, concentrou-se em um caso particular: mesmo número de
  homens (agentes proponentes) e mulheres (agentes seletores), com
  listas de preferência estritamente ordenadas e cada homem ou mulher sendo emparelhado a um único parceiro.
  Agora, relaxaremos cada uma dessas condições, trabalhando,
  também, com situações de indiferença, números diferentes de homens e mulheres e casos de poligamia. Veremos que algumas dessas situações podem ser resolvidas por métodos novos, ainda que
  inspirados no original.
  Porém, destacaremos que as três situações podem ser reduzidas ao cenário já estudado e resolvidas com o mesmo algoritmo.
  Uma redução de um problema B a um problema A é simplesmente
  uma transcrição da situação de B na linguagem e no contexto de A.
  Desse modo, resolvendo o problema assim transcrito com o método
  de A, obtemos uma solução de B invertendo a transcrição feita.
  Nós veremos mais reduções nos capítulos seguintes, especialmente a de emparelhamento ao problema geral de otimização linear.
  Também introduziremos a operação com listas incompletas de
  preferência, que adotaremos no restante do livro.
  
  2.1 Trabalhando com indiferenças
  Na situação-problema descrita e utilizada no capítulo anterior, tanto os homens como as mulheres, ao listarem uma ordem de
   23
  
  preferência pelos indivíduos do grupo oposto segundo seus gostos,
  sempre esclareceram quais eram estas preferências. Entretanto,
  nem sempre uma determinada pessoa tem preferência sobre outras:
  assim, é necessário discutir situações em que há indiferença.
  Definição: Utilizamos o conceito de indiferença para denotar situações em que dois ou mais elementos não são um mais
  preferido que o outro por alguém, em uma lista de preferência.
  Dessa forma, mais uma vez, a título de exemplo para essa
  nova situação-problema, o universo foi determinado de forma aleatória como de homens e mulheres, sendo eles: Victor (V); Wilson
  (W); Xavier (X); Yuri (Y); Zé (Z); Ana (A); Beatriz (B); Carolina (C);
  Débora (D); Érica (E).
  Como no exemplo anterior, cada uma dessas pessoas deve listar os membros do outro grupo de acordo com uma ordem de preferência para a escolha de seu parceiro de casamento, porém com a
  ressalva de que, agora, pode exprimir a equivalência entre alguns
  indivíduos, se houver.
  Notação: Para denotar que A é indiferente, isto é, não tem
  preferência por X ou Y, utilizaremos o símbolo “≡”, de modo que
  X ≡A Y significa: para A, o indivíduo X não é mais ou menos
  preferível a Y, ou seja, ambos são equivalentes.
  Assim, o primeiro passo é que as pessoas de ambos os grupos
  listem as pessoas do grupo oposto segundo uma ordem de preferência ou indiferença:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A≡C>D>E>B
  A>D>E>B≡C
  C≡D>B>E≡A
  A>D≡B>E>C
  D≡C>A≡B≡E
  
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  24  aline guarnieri gubitoso | vinicius cifú lopes
  
  Z>V≡W>Y>X
  V>X≡Y≡Z>W
  Z>W≡V>X>Y
  V>W≡Y≡X≡Z
  W>Z>X>Y≡V
  
  Uma vez esclarecidas as preferências e indiferenças de cada
  pessoa, começam as propostas dos homens às mulheres de que mais
  gostam, seja cada uma determinada (se há somente uma preferida),
  seja escolhida aleatoriamente (dentre as equivalentes).
  Precisamos explicitar uma nova regra: se uma pessoa recebe
  uma nova proposta e, para ela, são equivalentes o novo candidato e
  quem ela havia escolhido na rodada anterior, então ela não trocará
  de parceiro, pois não haveria um ganho ao trocar o que “já tem” por
  algo que é “igual”.
  Observação: Substituindo o símbolo “≡” pelo símbolo “>”, obtemos
  listas estritamente ordenadas com as quais já sabemos trabalhar.
  Suponha que conhecemos um emparelhamento estável de acordo
  com essas novas listas: então, não há um homem e uma mulher que
  se prefiram aos seus respectivos pares, ou seja, se temos os casais
  I – P e J – Q então P >I Q ou J >Q I. Desse modo, segundo as listas
  originais, P >I Q ou P ≡I Q ou J >Q I ou J≡Q I. Como supomos que um
  agente não troca parceiros equivalentes, mesmo que haja ganho estrito para outro agente, o emparelhamento obtido é estável também
  segundo as listas originais.
  Essa observação nos mostra que o caso de indiferença pode ser
  prontamente reduzido ao caso de preferências estritas.
  Contudo, faremos uma execução do algoritmo considerando diretamente as listas com indiferença e a hipótese de não substituição
  de equivalentes.
  Também é importante esclarecer que, nessa situação, quando
  estudada em trabalhos práticos como em simulações computacionais, a indiferença entre parceiros pode ser removida artificialmente, após a formação das listas de preferência, por uma escolha aleatória pelo agente no momento de criar sua lista ou pelo computador
  ao identificar o primeiro indivíduo (ou um outro) entre os equivalentes. Dessa forma, durante a execução deste exemplo, utilizaremos
  a escolha aleatória sempre pelo indivíduo que aparecer primeiro
  na lista de preferência de um agente indiferente. Contudo, existe a possibilidade de formar outros arranjos pela escolha de outro
  
  alocações, estabilidade e otimização  25
  
  indivíduo dentre os equivalentes, por exemplo, sempre a última pessoa ou uma sorteada. Portanto, a tomada de decisão dependerá de
  quais regras serão estabelecidas para orientar o processo artificial
  de escolha aleatória. Tal como na vida real, quando um indivíduo é
  obrigado a escolher, mesmo que por itens em indiferença, alguma
  característica influenciará sua decisão. Para denotar a escolha aleatória de um agente por um dentre os indivíduos equivalentes, ainda
  utilizaremos a moldura ⎕.
  Em resumo, quando um agente faz uma proposta ou seleciona
  dentre propostas sem ter uma anterior, escolherá aquela que ocupa
  a melhor posição na lista; quando seleciona dentre propostas equivalentes, inclusive uma anterior, manterá esta oferta mais antiga.
  De acordo com as listas de preferência, as propostas da primeira rodada começam com:
  1ª Rodada – propostas
  Victor:
  
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A ≡C>D>E>B
  
  A >D>E>B≡C
  C ≡D>B>E≡A
  
  A >D≡B>E>C
  D ≡C>A≡B≡E
  
  V⇝A
  
  W⇝A
  X⇝C
  Y⇝A
  
  Z⇝D
  
  Como Victor é indiferente quanto à sua primeira escolha ser
  Ana ou Carolina, uma possível alocação, escolhida de forma artificial e aleatória para o exemplo, é a proposta dele a Ana. Porém, Wilson e Yuri também propõem a Ana, por ser ela sua primeira opção
  determinada. Semelhantemente, Xavier, que também se encontra
  em uma situação de indiferença, faz uma proposta a Carolina e Zé
  faz uma proposta a Débora.
  Como o passo seguinte é a análise que cada mulher faz das
  propostas que recebeu (se recebeu alguma) para, assim, escolher a
  que acredita ser a mais atrativa ou escolher aleatoriamente entre
  dois homens que não são um mais preferível que o outro, temos:
  26  aline guarnieri gubitoso | vinicius cifú lopes
  
  1ª Rodada – escolhas
  V,W,Y ⇝ A
  
  Ana:
  
  Z⇝D
  
  Débora:
  
  ∅⇝B
  
  Beatriz:
  
  ∅⇝E
  
  Érica:
  
  X⇝C
  
  Carolina:
  
  Z>V ≡W>Y>X
  V>X≡Y≡Z>W
  
  Z>W≡V>X>Y
  V>W≡Y≡X≡Z
  
  W>Z>X>Y≡V
  
  ∴ A:V
  
  ∴ C:X
  
  ∴ D:Z
  
  Ana, ao ter de escolher entre Victor, Wilson e Yuri, sendo indiferente a Victor ou Wilson segundo sua lista de preferências, escolhe Victor segundo nossa convenção e rejeita Wilson (equivalente
  a Victor, mas listado depois dele) e Yuri (cuja proposta é inferior).
  As outras mulheres recebem uma ou nenhuma proposta e seguem o
  procedimento usual.
  Na segunda rodada de escolhas, a partir das escolhas da tabela anterior, são feitas novas propostas:
  2ª Rodada – propostas e escolhas
  V⇝A
  
  X⇝C
  
  W,Y,Z ⇝ D
  
  ∴A:V
  
  ∴C:X
  
  ∴D:Z
  
  Neste momento, Débora recebeu as novas propostas de Wilson
  e Yuri para comparar com a de Zé, que ela já tinha. Contudo, as três
  opções lhe são equivalentes, de modo que ela prefere continuar com
  Zé, mesmo Wilson sendo o primeiro listado entre eles. Foi importante, aqui, Zé ter “chegado antes” a Débora.
  Dessa forma, obtemos as seguintes tabelas:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A ≡C>D>E>B
  ^
  Â>D>E>B≡C
  C ≡D>B>E≡A
  ^
  Â>D≡B>E>C
  D ≡C>A≡B≡E
  
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  Z> V ≡W>Y>X
  V>X≡Y≡Z>W
  Z>W≡V> X >Y
  V>W≡Y≡X≡ Z
  W>Z>X>Y≡V
  
  alocações, estabilidade e otimização  27
  
  Na continuação do processo, a terceira rodada inicia-se com:
  3ª Rodada – propostas e escolhas
  V ⇝ A; W ⇝ E; X ⇝ C; Y ⇝ B; Z ⇝ D.
  
  Com isso, temos:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A ≡C>D>E>B
  ^
  Â>D> E >B≡C
  C ≡D>B>E≡A
  ^
  Â>D≡ B >E>C
  D ≡C>A≡B≡E
  
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  Z> V ≡W>Y>X
  V>X≡ Y ≡Z>W
  Z>W≡V> X >Y
  V>W≡Y≡X≡ Z
  W >Z>X>Y≡V
  
  Isso conclui o processo de emparelhamento.
  Logo, todos os homens e mulheres estão agora pareados de
  maneira estável, isto é, não há nenhuma mulher que preferisse estar com algum homem que também preferisse estar com ela, ao invés de sua parceira. Note que Wilson preferiria estar com Débora,
  mas, para ela, seu atual parceiro Zé é equivalente a Wilson e, portanto, a substituição não valeria a pena.
  Portanto, emparelhamentos estáveis são possíveis inclusive
  quando ocorrem casos de indiferença, que pressupõem a escolha
  aleatória entre escolhas equivalentes, visto que, nessa situação,
  mesmo quando um dos indivíduos é indiferente a uma escolha, ele
  ainda tem de fazê-la (ainda que seja aleatória e artificialmente). Desse
  modo, a indiferença, na verdade, é eliminada, tornando a lista com
  indiferença uma lista sem indiferença (dentre várias possíveis), uma
  vez que continuam a serem feitas escolhas entre os indivíduos. Modificando essas escolhas quando há equivalência, porém, obtemos
  resultados diferentes, todos constituindo emparelhamentos estáveis
  para as listas de equivalência deste exemplo, como veremos no primeiro exercício a seguir.
  Porém, podem não existir mais emparelhamentos que sejam
  ótimos para os homens ou para as mulheres, conforme destacam
  Roth; Sotomayor (1990, ex. 2.15).
  
  28  aline guarnieri gubitoso | vinicius cifú lopes
  
  Observação: Para os agentes proponentes, essa convenção de usar
  o primeiro da lista corresponde à substituição do símbolo “≡” pelo
  símbolo “>”, como observamos no início. Então, se I tem a lista de
  preferências
  I: P > Q ≡ R ≡ S > T,
  na verdade, nós trabalhamos com a lista
  I: P > Q > R > S > T.
  Para os agentes seletores, não temos como fazer essa conversão de antemão, porque precisamos saber quem faz cada proposta.
  Porém, obtemos tal informação durante a execução do algoritmo.
  Suponha, então, que P tem a lista de preferências
  P: I > J ≡ K ≡ L > M
  e que, dentre J, K e J (um grupo de equivalentes entre si), P receba primeiro a proposta de K, rejeitando depois as de J e L se houver. Nesse
  caso, o comportamento de P é como se K >p J, L e obtemos uma lista
  estrita para P escolhendo uma relação arbitrária entre J e L, assim:
  P: I > K > J > L > M.
  Essa lista é a utilizada por P na execução do algoritmo, para
  todos os efeitos.
  Ter montado listas estritas para todos os agentes, de modo
  que a execução do algoritmo corresponda ao preceito de não substituição de equivalentes, mostra que também essa formulação produz
  emparelhamentos estáveis.
   Exercícios
  1) Mostre que as listas de preferência do exemplo acima podem ser
  tornadas iguais às listas de preferência estrita que utilizamos como
  
  alocações, estabilidade e otimização  29
  
  exemplo no primeiro capítulo, com uma ordenação adequada das
  opções equivalentes. Confira, por outro lado, que o emparelhamento
  que obtivemos aqui difere daquele resultado.
  2) Aplique o algoritmo, a partir das mesmas listas de preferência
  acima, agora do ponto de vista da proposta feita pelas mulheres,
  utilizando as regras de proposta à primeira opção e escolha (dentre equivalentes) pela opção anterior, se houver, ou então pela primeira opção. Repetimos as listas a seguir:
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  Z>V≡W>Y>X
  V>X≡Y≡Z>W
  Z>W≡V>X>Y
  V>W≡Y≡X≡Z
  W>Z>X>Y≡V
  
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A≡C>D>E>B
  A>D>E>B≡C
  C≡D>B>E≡A
  A>D≡B>E>C
  D≡C>A≡B≡E
  
  Resposta: O emparelhamento obtido é bem diferente, somente tendo o casal Victor e Ana em comum: A – V; B – X; C – Z; D – W e E – Y.
  
  3) A partir das listas de preferência abaixo, aplique novamente o
  algoritmo com as regras apresentadas em ambas as situações: homens proponentes e mulheres proponentes.
  Otávio (O):
  Pedro (P):
  Roberto (R):
  Sérgio (S):
  Thiago (T):
  
  N>M>I>J≡L
  N≡J>I>M>L
  L>I≡N>J>M
  I>M>N≡L≡J
  L>J≡I>M>N
  
  Isabella (I):
  Joana (J):
  Laura (L):
  Marina (M):
  Natália (N):
  
  O>P≡S>T>R
  O≡T≡S>R>P
  R>S≡T≡O≡P
  O≡P≡R>T>S
  S≡O≡R>T≡P
  
  Resposta: Com a proposta dos homens às mulheres, obtemos os seguintes resultados:
  O – N; P – M; R – L; S – I e T – J. Neste caso, a regra de indiferença é utilizada
  quando I não troca S por P. Com as mulheres sendo quem propõe, os pares formados são: I – P; J – T; L – R; M – O e N – S.
  
  4) Verifique que, com as listas do exercício anterior e substituindo
  imediatamente o símbolo “≡” pelo símbolo “>”, obtemos casais diferentes quando o emparelhamento é realizado segundo as propostas
  dos homens: O – N; P – I; R – L; S – M e T – J.
  
  30  aline guarnieri gubitoso | vinicius cifú lopes
  
  2.2 Trabalhando com números diferentes de indivíduos
  O algoritmo também pode ser utilizado para tratar de situações de alocações com números desiguais de, por exemplo, homens
  e mulheres. Veremos como acomodar essa diferença em três momentos: com a adição de novos agentes “curingas” nas listas de
  preferência; sem o uso de curingas, reformulando as condições de
  conclusão do algoritmo (isto é, quando sabemos que o procedimento chegou ao final); com a consideração de listas incompletas de
  preferência, que é o tratamento mais geral e do qual nos serviremos no restante do livro.
  Solução com curingas
  Acrescentar um “curinga” ou um novo objeto à estrutura existente é um artifício ubíquo em raciocínios matemáticos. O curinga será
  considerado um novo agente, terá uma lista de preferência própria e
  deverá ser incluído nas listas de preferência dos agentes originais.
  Para realizar isso, se o indivíduo não informa nada a não ser a
  listagem de uma ordem de preferência pelas pessoas do outro grupo,
  o curinga é colocado no final de sua lista de preferência. Por outro
  lado, se essa pessoa informar (ou o sistema acomodar essa informação), o curinga pode ir em qualquer lugar na ordem de preferência
  desse indivíduo, separando quem essa pessoa gostaria de casar de
  quem ela não aceitaria. Esse curinga pode, inclusive, ir no começo
  de uma lista de preferência ao ser também utilizado como uma preferência pelas pessoas que escolhem ficar sozinhas a parear-se com
  quaisquer pessoas do outro grupo. Porém, se um indivíduo for alocado a um curinga sem que esta fosse sua preferência, significa que
  todas as pessoas do grupo oposto rejeitaram sua proposta, de modo
  que, ao ser alocado a um curinga, esta pessoa fica solteira.
  Em razão dessa possibilidade, finalmente iremos tratar de ocorrências em que um agente acredita que determinada alocação é pior
  do que continuar sem combinação, no caso, continuar solteiro; porém,
  descobriremos uma imperfeição nesse procedimento, relacionada à
  assimetria entre quem propõe e quem apenas seleciona propostas.
  alocações, estabilidade e otimização  31
  
  Notação: Para denotar o curinga, utilizaremos o símbolo ■.
  Para ilustrar essa problemática, o universo foi montado como
  de 5 homens e 4 mulheres, sendo eles: Victor (V); Wilson (W); Xavier
  (X); Yuri (Y); Zé (Z); Beatriz (B); Carolina (C); Débora (D); Érica (E) .
  Deste modo, mais uma vez é iniciado o processo com a listagem que cada uma dessas pessoas faz dos membros do outro grupo de acordo com uma ordem de preferência para a escolha de seu
  parceiro de casamento; com a diferença, entretanto, de que, agora,
  eles podem incluir o curinga em sua lista de preferência quando e
  se preferirem ficar solteiros a escolher alguma das opções que ainda
  não listaram.
  Incluímos uma lista de indiferença para o curinga, de modo a
  contemplá-lo no algoritmo.
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  C>D>■>E>B
  B>E>C>D>■
  B>C>E>D>■
  C>B>D>E>■
  D>B>C>E>■
  
  Beatriz:
  Carolina:
  Débora:
  Érica:
  ■:
  
  Y>X>Z>V>W
  W>X>Y>V>Z
  X>Z>Y>V>W
  W>Z>X>Y>V
  V≡W≡X≡Y≡Z
  
  A partir da listagem dessas preferências, de acordo com o processo já explicado anteriormente, começam as rodadas de propostas
  dos homens às mulheres que acreditam ser as mais preferíveis e
  subsequentes escolhas de cada mulher pelo melhor homem dentre
  os que lhe propõe.
  1ª Rodada – propostas
  Victor:
  
  Wilson:
  
  Xavier:
  Yuri:
  Zé:
  
  C >D>■>E>B
  
  B >E>C>D>■
  
  B >C>E>D>■
  
  C >B>D>E>■
  
  D >B>C>E>■
  
  32  aline guarnieri gubitoso | vinicius cifú lopes
  
  V⇝C
  
  W⇝B
  
  X⇝B
  Y⇝C
  
  Z⇝D
  
  1ª Rodada – escolhas
  W, X ⇝ B
  
  B:
  
  Y> X >Z>V>W
  
  C:
  
  W>X> Y >V>Z
  
  D:
  
  X> Z >Y>V>W
  
  ∅⇝E
  
  E:
  ■:
  
  W>Z>X>Y>V
  V≡W≡X≡Y≡Z
  
  V, Y ⇝ C
  Z⇝D
  
  ∴B:X
  ∴C:Y
  
  ∴D:Z
  
  Conforme as decisões desses indivíduos, na rodada seguinte
  temos:
  2ª Rodada – propostas e escolhas
  Victor:
  
  Ĉ>D>■>E>B
  
  Beatriz:
  
  Y> X >Z>V>W
  
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  B> E >C>D>■
  B >C>E>D>■
  C >B>D>E>■
  D >B>C>E>■
  
  Carolina:
  Débora:
  Érica:
  ■:
  
  W > X > Y > V >Z
  X> Z >Y>V>W
  W >Z>X>Y>V
  V≡W≡X≡Y≡Z
  
  ^
  
  ^
  
  Na terceira rodada, Victor, como o único homem rejeitado, faz
  uma nova proposta:
  3ª Rodada – propostas e escolhas
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  Ĉ>D> ■ >E>B
  ^
  B> E >C>D>■
  B >C>E>D>■
  C >B>D>E>■
  D >B>C>E>■
  ^
  
  Beatriz
  Carolina:
  Débora:
  Érica:
  ■:
  
  Y> X >Z>V>W
  W > X > Y > V >Z
  X> Z >Y>V>W
  W >Z>X>Y>V
  V ≡W≡X≡Y≡Z
  
  Logo, o processo termina aqui, quando todos os agentes estão
  ou pareados com alguém do grupo oposto ou solteiros.
  Esse exemplo é particular, no sentido de que o número de mulheres é exatamente um a menos que o de homens, de modo que
  
  alocações, estabilidade e otimização  33
  
  algum homem ficaria solteiro (não haveria mulheres o suficiente
  para todos os homens). Entretanto, nenhum homem foi alocado a
  um curinga por ter suas propostas rejeitadas por todas as mulheres, devido ao fato de que Victor, de livre e espontânea vontade
  (ou seja, segundo sua lista de preferências), escolheu ficar sozinho.
  Isso porque, para ele, se ele não casasse com Carolina ou Débora, não haveria nenhuma outra mulher com quem ele aceitaria se
  casar; assim, ao ser sua terceira opção continuar solteiro, Victor
  esclarece que, para ele, qualquer casamento com as demais mulheres (Érica ou Beatriz) seria inaceitável, isto é, seria pior do que
  continuar solteiro.
  Contudo, se Victor tivesse uma lista de preferência diferente,
  em que preferisse Érica e Beatriz à opção de ficar solteiro (ou seja,
  ficar solteiro seria sua última opção), ele ainda seria o homem solteiro da alocação (agora forçado), uma vez que, com a continuação do
  processo, suas propostas a Érica e Beatriz seriam ambas rejeitadas.
  Outras listas de preferência, é claro, podem levar a situações
  distintas.
  Em geral, podemos usar mais curingas, de modo que sua
  quantidade corresponda à diferença exata entre os totais dos grupos, sendo que, em cada lista de preferência, eles devem estar contíguos e ser equivalentes (por motivos de lógica). Por exemplo, se
  forem 5 homens e 3 mulheres, teremos dois curingas em sequência
  na lista de preferências fornecida por cada homem.
  
   Exercício
  1) Aplique o algoritmo do ponto de vista da proposta feita pelas
  mulheres, a partir das mesmas listas de preferências acima, verificando qual dos homens ficaria solteiro e se seria de forma forçada
  (rejeitado por todas as mulheres) ou por opção (propondo ao curinga
  antes de alguma mulher). Repetimos as listas abaixo:
  
  34  aline guarnieri gubitoso | vinicius cifú lopes
  
  Beatriz:
  Carolina:
  Débora:
  Érica:
  ■:
  
  Y>X>Z>V>W
  W>X>Y>V>Z
  X>Z>Y>V>W
  W>Z>X>Y>V
  V≡W≡X≡Y≡Z
  
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  C>D>■>E>B
  B>E>C>D>■
  B>C>E>D>■
  C>B>D>E>■
  D>B>C>E>■
  
  Resposta: Ao verificarmos que os pares formados são B – Y, C – X, D – Z, E – W,
  percebemos que Victor continua a ser o homem que fica solteiro, de forma forçada,
  uma vez que nenhuma mulher lhe propõe. Note que, neste caso, há menos agentes
  proponentes que receptores.
  
  Observação: Nossa conclusão sobre curingas servirem para separar
  opções “aceitáveis” e “inaceitáveis” é natural e válida para os agentes
  proponentes (homens), devido ao fato de suas molduras deslocarem-se
  sempre da opção mais preferida para a menos preferida durante a
  execução de Gale-Shapley. Porém, o deslocamento contrário para os
  agentes seletores (mulheres) inviabiliza essa manobra.
  Tentar resolver esse problema só gera confusão: por exemplo,
  se pusermos as opções inaceitáveis antes do curinga e as aceitáveis
  depois, contrariamente ao próprio espírito de ordenação das listas
  de preferência, nem assim obteremos uma solução.
  Não devemos pensar nisso como um defeito do artifício de usar
  curingas, que tem o mérito de destacar essa confusão assim que se
  pensa no caso, mas como um reflexo do exagero no seu uso.
  Para o problema inicial de números diferentes de indivíduos,
  os curingas podem ser utilizados sem problemas, sempre ao final
  das listas de preferência originais; no entanto, procuraremos, também, uma solução diferente.
  Depois retomaremos a questão das opções inaceitáveis (na literatura, o curinga pode aparecer, em uma lista de preferência, usado
  para tão somente delimitar as opções aceitáveis e as inaceitáveis).
  Solução sem curingas
  Como visto acima, a utilização do curinga é um facilitador para
  a resolução de problemas com diferentes números de indivíduos.
  
  alocações, estabilidade e otimização  35
  
  Entretanto, existe uma outra forma de tornar esta situação-problema resolvível através da modificação das condições de encerramento do algoritmo.
  Note que, nas explicações e exemplos até aqui, definimos que o
  algoritmo chegava ao fim quando todos os agentes que faziam as propostas estavam pareados a agentes do outro conjunto. Então, acordamos que o processo continua enquanto algum proponente ainda tiver,
  em sua lista de preferência, alguns candidatos seletores a quem propor. Ou seja, o processo termina quando, após uma rodada completa
  de propostas e escolhas, cada proponente ou está pareado a algum
  seletor ou foi rejeitado por todos, terminando solteiro.
  
   Exercício
  1) Quais alterações são necessárias no programa de computador
  descrito na Seção 1.4 para acomodar essa nova condição de parada
  e os números diferentes de homens e mulheres?
  No caso específico de o número de agentes proponentes ser menor
  que o de seletores, digamos h homens e m mulheres com h ≤ m, o
  encerramento do processo pode ser descrito de outro modo: é quando h mulheres diferentes estão pareadas. Porém, essa descrição não
  será válida no caso de listas incompletas, que adotaremos a seguir.
  Listas incompletas de preferência
  Uma solução que comporta a manifestação de opções aceitáveis ou inaceitáveis é, simplesmente, não listar as opções inaceitáveis nas listas de preferência, isto é, cada homem listará somente as
  mulheres com as quais aceita se casar e cada mulher listará somente
  os homens que considera aceitáveis. Naturalmente, as listas podem
  ter números variados de integrantes e deverão ser tratadas com a
  formulação do algoritmo que trata números diferentes de indivíduos.
  36  aline guarnieri gubitoso | vinicius cifú lopes
  
  O novo procedimento sempre encontrará uma solução estável, em um
  número finito de etapas, mas poderá acontecer que agentes (possivelmente todos) resultem solteiros.
  Por exemplo, A: X > Y significa que A prefere X e depois Y, mas
  se não for emparelhado com nenhum dos dois, A prefere não admitir nenhum outro agente. Analogamente, a lista X: A significa que X
  prefere o agente A mas se não conseguir tal resultado, então prefere
  não ter nenhum outro. (Alguns autores exprimem que tal agente será
  “alocado a si mesmo”.)
  Nessa situação, os agentes rejeitam automaticamente as propostas vindas de quem não está em suas listas, de modo que, para
  acelerar o procedimento, podemos previamente remover A da lista
  de X se X não está na lista de A (porque A não aceitaria X), no caso
  de X propor e A selecionar. Também, após a montagem das listas de
  preferência, podemos retirar do procedimento quem já não aceita
  ninguém como parceiro.
  É com esta formulação em mente que trabalharemos a partir
  de agora, ao expressar as listas de preferência dos nossos exemplos.
  
   Exercícios
  1) Aplique o algoritmo às listas de preferência seguintes, em que há
  duas mulheres a menos, tanto da perspectiva dos homens propondo,
  como quando as mulheres propõem:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A
  A>C>B
  B>C>A
  A>B
  C>A>B
  
  Ana:
  Beatriz:
  Carolina:
  
  Z>W>V>Y>X
  V>X>Y>Z>W
  Z>W>V>X>Y
  
  Resposta: Em ambas as situações, Victor e Yuri permanecem solteiros, enquanto
  se formam os casais W – A, X – B e Z – C.
  
  alocações, estabilidade e otimização  37
  
  2) Aplique o algoritmo às listas de preferência seguintes, em que há
  duas mulheres a menos, tanto da perspectiva dos homens propondo,
  como quando as mulheres propõem:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  C
  A>B>C
  A>C>B
  C>A>B
  B>C>A
  
  Ana:
  Beatriz:
  Carolina:
  
  Z>Y>X>V
  Y>X>W>V
  X>V>Y
  
  Resposta: Quando os homens propõem, formam-se os casais X – C, Y – A e Z – B.
  Quando as mulheres propõem, formam-se os casais A – Z, B – Y e C – X. Em ambas
  as situações, Victor e Wilson permanecem solteiros.
  
  2.3 Permitindo poligamia
  O algoritmo, além de conseguir tratar de situações com indiferença e com números desiguais de homens e mulheres, também
  pode ser adaptado para uma análise das situações em que ocorre
  pareamento de um indivíduo com mais de um único elemento do
  outro grupo. Ou seja, iremos discutir agora a situação em que, por
  exemplo, um homem deseja ter mais de uma companheira.
  Faremos isso criando “vagas” ou “slots” para múltiplas mulheres na “carteira” de cada homem.
  Procedimento: Para denotar que X escolhe ter 3 parceiras,
  utilizaremos índices numéricos da seguinte forma: X1, X2, X3,
  que significa dizer que cada Xi corresponde a uma das “vagas”
  para parceira de X.
  Para ilustrar essa ocorrência, o universo foi determinado de
  forma aleatória como de 2 homens e 7 mulheres, sendo eles: Xavier
  (X); Yuri (Y); Ana (A); Beatriz (B); Carolina (C); Débora (D); Érica
  (E); Flávia (F); Glória (G). Acrescentamos que Xavier deseja ter três
  
  38  aline guarnieri gubitoso | vinicius cifú lopes
  
  parceiras e Yuri procura por duas parceiras. Em consequência disso, Xavier tem três “vagas” para companheira, enquanto que Yuri
  tem duas “vagas”, com um total de cinco vagas, e duas mulheres
  ficarão solteiras. Débora e Glória, porém, aceitam somente um homem cada. Os agentes têm as seguintes preferências:
  Xavier: D > F > C > B > A > G > E
  Yuri: C > D > B > G > E > A > F
  
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  Flávia:
  Glória:
  
  Y>X
  X>Y
  X>Y
  Y
  X>Y
  Y>X
  X
  
  Dessa forma, o processo de listagem das preferências que cada
  uma dessas pessoas faz em relação aos membros do outro grupo é o
  mesmo. Porém, agora, cada homem tem uma lista para cada “vaga”.
  Para a execução do algoritmo, as vagas são consideradas como “pessoas diferentes”. Por outro lado, todas as listas de preferência das
  vagas de um mesmo homem devem ser as mesmas e idênticas às preferências desse homem. Finalmente, tais vagas são equivalentes nas
  listas das mulheres, porque correspondem ao mesmo homem:
  X1 : D > F > C > B > A > G > E
  X2 : D > F > C > B > A > G > E
  X3 : D > F > C > B > A > G > E
  Y1 : C > D > B > G > E > A > F
  Y2 : C > D > B > G > E > A > F
  
  A: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  B: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  C: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  D: Y1 ≡ Y2
  E: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  F: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  G: X1 ≡ X2 ≡ X3
  
  À medida que as rodadas se desenvolvem, os homens fazem
  propostas às mulheres de que mais gostam, escolhendo a primeira
  
  alocações, estabilidade e otimização  39
  
  mulher em sua lista de preferência com cada uma de suas “vagas”.
  Desse modo, suas vagas, por serem consideradas como pessoas distintas, irão todas propor à mesma mulher, a qual escolhe sempre a
  primeira opção como uma possível escolha artificial (já discutida no
  problema de indiferenças) dentre as que são equivalentes.
  1ª Rodada – propostas e escolhas
  Olhando as preferências dos homens em suas listas e a consequente escolha das mulheres quanto às propostas que recebem, temos que X1, X2 e X3 propõem a Débora, que não os aceita; Y1 e Y2 propõem a Carolina, que seleciona Y1 e rejeita Y2, escolhendo, das duas
  vagas equivalentes, apenas uma. Assim, a execução desse processo
  nada difere das anteriores.
  X1 : D > F > C > B > A > G > E
  ^
  X2 : D > F > C > B > A > G > E
  ^
  X3 : D > F > C > B > A > G > E
  Y1 : C > D > B > G > E > A > F
  ^
  
  Y2 : Ĉ > D > B > G > E > A > F
  
  A: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  B: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  C: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  D: Y1 ≡ Y2
  E: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  
  F: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  G: X1 ≡ X2 ≡ X3
  
  Como os homens têm algumas de suas “vagas” rejeitadas, novas propostas são feitas de modo que se modifique as tabelas:
  2ª Rodada – propostas e escolhas
  Y2 ⇝ D
  
  X1, X2, X3 ⇝ F
  Y1 ⇝ C
  
  ∴ D: Y2
  ∴ F: X1
  
  ∴ C: Y1
  
  Com as novas propostas, obtemos:
  
  40  aline guarnieri gubitoso | vinicius cifú lopes
  
  X1 : D > F > C > B > A > G > E
  ^
  ^
  X2 : D > F > C > B > A > G > E
  ^
  ^
  X3 : D > F > C > B > A > G > E
  Y1 : C > D > B > G > E > A > F
  Y2 : Ĉ > D > B > G > E > A > F
  ^
  
  A: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  B: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  C: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  D: Y1 ≡ Y2
  E: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  F: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  G: X1 ≡ X2 ≡ X3
  
  Como ainda há rejeições, no caso de X2 e X3, ocorre uma terceira rodada:
  3ª Rodada – propostas e escolhas
  X1 : D > F > C > B > A > G > E
  ^
  ^
  X2 : D > F > C > B > A > G > E
  ^
  ^
  X3 : D > F > Ĉ > B > A > G > E
  Y1 : Ĉ > D > B > G > E > A > F
  Y2 : Ĉ > D > B > G > E > A > F
  ^
  
  A: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  B: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  C: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  D: Y1 ≡ Y2
  E: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  F: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  G: X1 ≡ X2 ≡ X3
  
  É importante destacar que, como as listas de preferência de
  cada “vaga” de um mesmo homem têm a mesma ordenação das
  mulheres, as propostas a uma mesma mulher serão frequentes.
  Quando a vaga faz uma proposta, a mulher escolhida já pode estar
  alocada com outra vaga do mesmo homem, o que resulta na permanência da vaga original, segundo nosso critério de não trocar equivalentes. Exemplo disso é que Débora rejeitará Y1 porque já está
  alocada com Y2:
  
  alocações, estabilidade e otimização  41
  
  4ª Rodada – propostas e escolhas
  X1 : D > F > C > B > A > G > E
  ^
  ^
  X2 : D > F > C > B > A > G > E
  ^
  ^
  X3 : D > F > Ĉ > B > A > G > E
  ^
  Y1 : Ĉ > D > B > G > E > A > F
  Y2 : Ĉ > D > B > G > E > A > F
  ^
  
  A: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  B: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  C: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  D: Y1 ≡ Y2
  E: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  F: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  G: X1 ≡ X2 ≡ X3
  
  5ª Rodada – propostas e escolhas
  X1 : D > F > C > B > A > G > E
  ^
  ^
  X2 : D > F > C > B > A > G > E
  ^
  ^
  X3 : D > F > Ĉ > B > A > G > E
  ^
  ^
  Y1 : Ĉ > D > B > G > E > A > F
  Y2 : Ĉ > D > B > G > E > A > F
  ^
  
  A: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  B: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  C: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  D: Y1 ≡ Y2
  E: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  F: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  G: X1 ≡ X2 ≡ X3
  
  6ª Rodada – propostas e escolhas
  X1 : D > F > C > B > A > G > E
  ^
  ^
  X2 : D > F > C > B > A > G > E
  ^
  ^
  X3 : D > F > Ĉ > B > A > G > E
  ^
  ^
  Y1 : Ĉ > D > B > Ĝ > E > A > F
  Y2 : Ĉ > D > B > G > E > A > F
  ^
  
  A: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  B: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  C: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  D: Y1 ≡ Y2
  E: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  F: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  G: X1 ≡ X2 ≡ X3
  
  42  aline guarnieri gubitoso | vinicius cifú lopes
  
  7ª Rodada – propostas e escolhas
  X1 : D > F > C > B > A > G > E
  ^
  ^
  X2 : D > F > C > B > A > G > E
  ^
  ^
  X3 : D > F > Ĉ > B > A > G > E
  ^
  ^
  Y1 : Ĉ > D > B > Ĝ > E > A > F
  Y2 : Ĉ > D > B > G > E > A > F
  ^
  
  A: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  B: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  C: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  D: Y1 ≡ Y2
  E: X1 ≡ X2 ≡ X3 > Y1 ≡ Y2
  F: Y1 ≡ Y2 > X1 ≡ X2 ≡ X3
  G: X1 ≡ X2 ≡ X3
  
  Segundo a tabela, Xavier consegue então se unir a Beatriz,
  Carolina e Flávia, enquanto Yuri se estabelece com Débora e Érica.
  Consequentemente, por não haver mais “vagas” disponíveis, Ana é
  forçada a ficar solteira, ao passo que Glória fica solteira por escolha
  própria, por preferir isso a ser pareada com Yuri.
  A partir desses resultados, percebemos que não há nenhuma
  ocorrência de instabilidade, mesmo quando expandimos esse algoritmo a situações em que o emparelhamento ocorre entre mais do
  que um indivíduo com um outro. Isso porque, ao repetirmos as listas
  de preferências, ao invés de modificarmos o algoritmo, transformamos os polígamos Xavier e Yuri em X1, X2, X3, Y1 e Y2, de modo que
  utilizamos nessa resolução tanto a repetição da lista dos polígamos
  como o algoritmo Gale-Shapley.
  Note que outros conjuntos de listas de preferência podem resultar em agentes polígamos sem preencher todas as suas “vagas”.
   Exercícios
  1) Aplique o algoritmo, agora do ponto de vista da proposta feita pelas mulheres, às mesmas listas de preferência, reproduzidas a seguir:
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  Flávia:
  Glória:
  
  Y>X
  X>Y
  X>Y
  Y
  X>Y
  Y>X
  X
  
  Xavier (3 vagas): D > F > C > B > A > G > E
  Yuri (2 vagas): C > D > B > G > E > A > F
  
  alocações, estabilidade e otimização  43
  
  Resposta: Novamente obtemos X – {B, C, F} e Y – {D, E}, enquanto Ana é forçada
  a ficar solteira e Glória o faz por opção (Yuri a preferiria a Érica).
  
  2) Aplique o algoritmo, uma vez para propostas feitas pelos homens,
  outra pelas mulheres, às listas de preferência abaixo, verificando
  quais mulheres ficam solteiras e se de forma forçada (rejeitadas por
  todos os homens) ou não:
  R (3 vagas): D > A > F > G > C > E > B > H
  S (1 vaga): G > B > C > A > F > D > E > H
  T (2 vagas): G > E > A > F > C > D > B > H
  
  A: T > S > R
  B: S > R > T
  C: R > T > S
  D: T > S
  E: R > S > T
  F: S > T > R
  G: T > R
  H: R
  
  Resultado: Com os homens propondo, obtemos R – {A, C, F}, S – B e T – {E, G},
  enquanto D fica solteira por opção e H porque ninguém lhe propõe. Com as mulheres propondo, a situação das solteiras é a mesma, porém, R – {C, E, F}, S – B e
  T – {A, G}.
  
  Solução sem multiplicações
  O procedimento descrito acima para tratar a poligamia é muito
  ineficiente, ao fazer várias vagas atuarem como pessoas e proporem
  repetidamente a um mesmo indivíduo, mesmo quando este já rejeitou uma vaga semelhante ou está alocado a outra vaga semelhante.
  Podemos, tanto nestes exemplos pequenos como na prática
  computacional, trabalhar com as listas originais e manter, também, registros dos totais de vagas para cada agente e as respectivas
  quantidades de vagas ainda disponíveis ou não preenchidas. Com
  esse formato, mantemos, para cada “carteira”, uma listagem temporária de “associados” e, quando completa, substituímos os associados menos preferidos por aqueles que estão ingressando.
  Por exemplo, suponha que X tenha três vagas, todas preenchidas pelos associados B > A > C. Suponha, também, que X é um agente
  44  aline guarnieri gubitoso | vinicius cifú lopes
  
  seletor, que recebe propostas. Ele somente aceitará uma proposta
  de D caso D > C; depois da substituição, a listagem temporária será
  ordenada novamente segundo as preferências de X, podendo ser
  B > D > A, por exemplo, e deixando A em situação de potencial substituição. Por outro lado, na situação de ser X quem faz propostas, ele
  somente proporá a algum agente quando A, B ou C abandonarem-no
  em prol de outra oferta mais interessante e, em caso de aceitação,
  preencherá a vaga aberta.
  No caso de um número arbitrário de vagas abrindo-se, portanto, tomamos em conjunto os “associados” e as novas propostas, selecionamos os candidatos mais preferidos, dentre todos, e rejeitamos
  os demais que excederem o número de vagas disponíveis.
  Novamente, o processo termina quando cada agente proponente estiver alocado ou houver sido rejeitado por cada agente seletor.
  O resultado final será o mesmo que obtivemos com o procedimento exemplificado. Trataremos assim um pequeno exemplo na
  Seção 5.1.
  
  2.4 Recapitulação
  Buscamos explicar e exemplificar o algoritmo Gale-Shapley
  para obter emparelhamentos estáveis de casais e indicar sua adaptabilidade mesmo a situações com falta de preferência, números desiguais de indivíduos a serem pareados, listas incompletas e uniões
  de um único agente com vários outros.
  Isso foi possível contando com algumas estratégias comuns em
  raciocínio lógico, como a utilização de curingas e repetição de listas,
  permitindo aplicar novamente o mesmo procedimento, realizando a
  redução desses problemas mais complexos à primeira versão mais
  simples que estudamos.
  Importante: Reflita e constate que essa solução também pode ser
  aplicada em situações ainda mais complexas, em que ocorram todos
  os problemas supracitados simultaneamente.
  
  alocações, estabilidade e otimização  45
  
  Adotamos a figura do casamento para explicar os exemplos
  tradicionais, mas, nos próximos capítulos, veremos que o algoritmo
  é considerado tanto na academia como no mundo real cotidiano, nas
  questões de admissão de alunos nas universidades e escolas e de
  emparelhamento de colegas de quarto.
  
  46  aline guarnieri gubitoso | vinicius cifú lopes
  
  3
  Resolução por
  programação linear
  A primeira investigação geral do problema do casamento
  foi a teoria de Gale; Shapley (1962), isto é, o algoritmo de deferred
  acceptance, seguida de seu desenvolvimento pelos trabalhos dos próprios David Gale e Lloyd Shapley e, também, Alvin Roth, Marilda
  Sotomayor e outros pesquisadores.
  Entretanto, a própria execução uma a uma das rodadas de
  propostas, descrita no capítulo anterior, não foi a única solução
  encontrada. Sendo assim, outro método de resolução, interessante
  para nossa discussão, é a formulação desse problema na forma de
  otimização linear.
  Nossa apresentação será baseada no trabalho de John Vande
  Vate – como exposto em Gusfield; Irving (1989), mas, para tanto,
  faremos uma introdução breve à programação linear, sobre a qual o
  leitor encontrará maiores detalhes em Lins; Calôba (2006) e Brown;
  Sherbert (1984).
  
  3.1 Programação linear
  O exercício 37 de Brown; Sherbert (1984, p. 118) requer fazer
  e vender bolos, tortas e dúzias de biscoito de acordo com a seguinte
  proporção de ingredientes:
  
   47
  
  ingrediente
  maçãs
  xícaras de açúcar
  xícaras de farinha
  
  produto
  
  bolo
  
  torta
  
  3
  1
  2
  
  10
  2
  3
  
  dúzia de
  biscoitos
  1
  3
  1
  
  Para isso, temos à disposição 840 maçãs, 630 xícaras de açúcar e 450 xícaras de farinha.
  Por outro lado, os bolos são vendidos por R$ 8, as tortas por
  R$ 6 e os pacotes de uma dúzia de biscoitos por R$ 5. De modo a
  melhor utilizar os ingredientes, desejamos maximizar o valor das
  vendas, o que significa que desejamos maximizar a função objetivo
  V = 8x + 6y + 5z, sendo:
  x = número de bolos;
  y = número de tortas;
  z = número de dúzias de biscoitos.
  Observação: O valor total das vendas é a soma das quantidades
  vendidas multiplicadas pelos respectivos valores unitários. (Note
  que, se tivéssemos os custos unitários dos ingredientes, poderíamos calcular o custo total e subtraí-lo do valor das vendas, para
  tentar maximizar apenas o lucro líquido.)
  Essa função V está definida em um domínio, isto é, uma região
  do espaço tridimensional Oxyz delimitada pelas seguintes inequações, devido ao fato de que, para produzirmos tais alimentos, estamos sujeitos às quantidades disponíveis dos ingredientes:
  3x + 10y + 1z ≤ 840
  1x + 2y + 3z ≤ 630
  2x + 3y + 1z ≤ 450
  e, por uma questão de lógica,
  x, y, z ≥ 0.
  48  aline guarnieri gubitoso | vinicius cifú lopes
  
  A partir dessas equações, montamos uma matriz chamada
  “tableau”, que explicamos a seguir:
  1
  0
  0
  0
  
  –8
  3
  1
  2
  
  –6
  10
  2
  3
  
  –5
  1
  3
  1
  
  0
  1
  0
  0
  
  0
  0
  1
  0
  
  0
  0
  0
  1
  
  0
  840
  630
  450
  
  A 1ª coluna é fixa; as 2ª, 3ª e 4ª colunas correspondem às proporções de uso dos ingredientes disponíveis em cada produto, respectivamente, bolos, tortas e dúzias de biscoito; as 5ª, 6ª e 7ª colunas
  correspondem às possíveis sobras de maçãs, açúcar e farinha, ou
  seja, são as quantidades adicionais (também consideradas como
  variáveis) necessárias para transformar as desigualdades em
  equações; a 8ª coluna considera o total de ingredientes disponíveis.
  Dessa forma, na 1ª linha, os valores se referem à função objetivo,
  mas com os sinais trocados porque, de fato, V – 8x – 6y – 5z = 0,
  enquanto que a 2ª linha é uma relação das informações sobre as
  maçãs; a 3ª com as informações sobre o açúcar e a 4ª com as informações sobre a farinha.
  As variáveis que identificam as sobras dos ingredientes adquirem nomes variados na literatura, como “variáveis de folga” ou
  slack variables.
  Uma vez montado o tableau, utilizamos o algoritmo Simplex
  para resolução do problema. É preciso notar que tanto o tableau
  que montamos como a descrição das etapas do Simplex são específicas a esse tipo de problema. Outras questões de otimização linear
  são resolvidas de modo diferente.
  1º passo: Procurar pela entrada “mais negativa” na primeira linha
  e selecioná-la; chamamos sua coluna de “coluna pivô”. Notamos que
  o número – 8 é a entrada mais negativa, por isso sua coluna será a
  “coluna pivô”:
  
  alocações, estabilidade e otimização  49
  
  1
  0
  0
  0
  
  –8
  3
  1
  2
  
  –6
  10
  2
  3
  
  –5
  1
  3
  1
  
  0
  1
  0
  0
  
  0
  0
  1
  0
  
  0
  0
  0
  1
  
  0
  840
  630
  450
  
  2º passo: Em separado, dividir as entradas da última coluna pelas entradas positivas da “coluna pivô” e procurar o menor quociente. Assim:
  840 ÷ 3 = 280
  630 ÷ 1 = 630
  450 ÷ 2 = 225
  A linha do menor quociente obtido é, então, identificada como
  “linha pivô”, sendo que a célula de interseção desta linha com a “coluna pivô” será chamada de pivô. Notamos que o quociente 225 é o
  menor, de forma que, sendo ele o quociente de 450 por 2, a última
  linha será a “linha pivô”, assim como o número 2 é o pivô ao estar
  na célula em que a “coluna pivô” é interceptada pela “linha pivô”:
  1
  0
  0
  0
  
  –8
  3
  1
  2
  
  –6
  10
  2
  3
  
  –5
  1
  3
  1
  
  0
  1
  0
  0
  
  0
  0
  1
  0
  
  0
  0
  0
  1
  
  0
  840
  630
  450
  
  3º passo: Em seguida, dividimos a linha pelo valor do pivô e usamos
  as operações de escalonamento para zerar o restante da coluna. Isto
  é, na 1ª linha, somamos a ela a multiplicação da nova 4ª linha por 8;
  na 2ª linha, subtraímos dela a multiplicação da nova 4ª linha por 3,
  enquanto que, na 3ª linha, somente subtraímos dela a nova 4ª linha:
  1
  0
  0
  0
  
  0
  0
  0
  1
  
  6
  5,5
  0,5
  1,5
  
  –1
  –0,5
  2,5
  0,5
  
  0
  1
  0
  0
  
  50  aline guarnieri gubitoso | vinicius cifú lopes
  
  0
  0
  1
  0
  
  4
  –1,5
  –0,5
  0,5
  
  1800
  165
  405
  225
  
  Esses passos são repetidos até que não haja mais entradas
  negativas na primeira linha. No caso deste exemplo, ainda há uma
  entrada negativa – 1, localizada na 4ª coluna (nova “coluna pivô”).
  Então procuramos a nova “linha pivô”, dividindo os valores da última coluna pelos positivos da nova “coluna pivô”:
  405 ÷ 2,5 = 162
  225 ÷ 0,5 = 450
  Como o menor quociente é 162, notamos que o novo pivô é 2,5.
  1
  0
  0
  0
  
  0
  0
  0
  1
  
  6
  5,5
  0,5
  1,5
  
  –1
  –0,5
  2,5
  0,5
  
  0
  1
  0
  0
  
  0
  0
  1
  0
  
  4
  –1,5
  –0,5
  0,5
  
  1800
  165
  405
  225
  
  Dessa forma, o próximo passo é dividir a nova “linha pivô”
  pelo valor do pivô 2,5 e, utilizando escalonamento, zerar os demais
  valores dessa coluna. Assim, na 1ª linha, somamos a nova 3ª linha;
  na 2ª linha, somamos o quociente da nova 3ª linha por 2, enquanto
  que, na 4ª linha, subtraímos o quociente da nova 3ª linha por 2.
  Temos, então:
  1
  0
  0
  0
  
  0
  0
  0
  1
  
  6,2
  5,6
  0,2
  1,4
  
  0
  0
  1
  0
  
  0
  1
  0
  0
  
  0,4
  0,2
  0,4
  –0,2
  
  3,8
  –1,6
  –0,2
  0,6
  
  1962
  246
  162
  144
  
  Com base neste último tableau, como não temos mais entradas negativas na primeira linha, chegamos à tabela final. Sua
  interpretação é a seguinte: sua última coluna contém o valor máximo de V e os valores das variáveis x, y, z, identificadas a partir
  das colunas que formam a matriz identidade, sendo que as demais
  variáveis são nulas.
  
  alocações, estabilidade e otimização  51
  
  Neste exemplo, descobrimos que, ao maximizar as vendas,
  ganhamos R$ 1962 (brutos). Para isso, fazemos e vendemos 144
  bolos: percebemos que na 2ª coluna, dos bolos, ocorre somente uma
  única vez o número 1; a interseção de sua linha com a última coluna determina a quantidade de bolos feitos. Também fazemos e
  vendemos 162 dúzias de biscoito: percebemos que, na 4ª coluna dos
  biscoitos, ocorre somente uma única vez o número 1; a interseção
  de sua linha com a última coluna determina a quantidade de dúzias de biscoito feitas.
  Entretanto, não fazemos nenhuma torta, dado que sua coluna
  (3ª coluna) não é composta por zeros e um único 1. Contudo, a 5ª
  coluna, das sobras de maçãs, tem esse formato. Consequentemente,
  a interseção da linha restante (2ª linha) com a última coluna determina o saldo de 246 maçãs, isto é, que sobraram.
  Como funciona e quando não funciona
  O algoritmo Simplex é só quinze anos mais velho que o de
  Gale-Shapley e tem sido estudado profusamente. Faremos somente
  um resumo de considerações sobre seu funcionamento, mas, para
  entender melhor o mecanismo, veja textos especializados como Lins;
  Calôba (2006, caps. 4 e 5). (Cumpre notar que textos diferentes se
  servem de formulações diversas em que o processo é análogo, mas
  não idêntico. Por exemplo, Lins e Calôba preferem a linha da função
  objetivo como última no tableau. Autores que buscam minimizar
  a função objetivo podem formulá-la inversamente e usar entradas
  positivas para determinar a “coluna pivô”.)
  Note, no exemplo, que cada tableau (seja o inicial ou após uma
  rodada completa dos três passos) também pode ser interpretado
  como fizemos com o último; obtemos, respectivamente:
  • 0 bolos, 0 tortas e 0 dúzias de biscoitos, restando 840 maçãs,
  630 xícaras de açúcar e 450 xícaras de farinha.
  • 225 bolos, 0 tortas e 0 dúzias de biscoitos, restando 165 maçãs,
  405 xícaras de açúcar e 0 xícaras de farinha. (Confira que esses
  bolos são feitos precisamente com os ingredientes subtraídos
  das quantidades originais.)
  52  aline guarnieri gubitoso | vinicius cifú lopes
  
  • 144 bolos, 0 tortas e 162 dúzias de biscoitos, restando 246 maçãs, 0 xícaras de açúcar e 0 xícaras de farinha. (Desistimos de
  fazer tantos bolos, consumindo menos maçãs e mais açúcar
  para fazer biscoito.)
  Por outro lado, ao delimitarmos a região do espaço tridimensional Oxyz pelas inequações lineares do problema, obtemos um poliedro convexo (sólido com faces e arestas planas e sem concavidade) do
  qual os pontos (0,0,0), (225,0,0) e (144,0,162) são alguns dos vértices.
  Para entendermos a relevância dos vértices, note, primeiramente, que V = 8x + 6y + 5z está definida em todo o espaço Oxyz; no
  cálculo básico universitário, mostra-se que V cresce mais rapidamente na direção e sentido do vetor (8,6,5), chamado ∇V (“gradiente de V”). Podemos imaginar, então, uma pequena bolinha presa
  dentro do poliedro delimitado pelas restrições do problema linear,
  mas sobre a qual atua uma força identificada com esse vetor. Assim
  como se sujeita à força gravitacional, a bolinha tenderia a ir para o
  ponto mais baixo de um recipiente; naquela situação, ela também
  tende a deslocar-se para os “últimos” pontos do poliedro, em que
  o valor de V seja o mais alto. E, assim como no caso do recipiente,
  cujo fundo pode ser chato ou em forma de uma cunha, esses pontos
  podem constituir toda uma face ou uma aresta do poliedro, mas,
  forçosamente, incluem um vértice.
  O Simplex foi elaborado, portanto, para procurar o ponto de
  otimização entre os vértices. Em cada tableau, o algoritmo apresentou-nos um desses vértices e, em sequência, foi ao próximo vértice
  enquanto o valor da função objetivo V progressivamente aumentou.
  De fato, na primeira linha, ao eliminarmos as entradas negativas, a
  última entrada em geral aumenta e nunca diminui (às vezes, pode
  não aumentar, caso em que o pivô sendo trabalhado é chamado degenerado). Como essa linha corresponde à equação formada pela
  definição de V, sua última entrada é o valor correspondente de V
  nesse momento.
  (A escolha da entrada “mais negativa” na primeira linha busca aumentar o valor de V o mais rápido possível em uma pivotagem,
  alocações, estabilidade e otimização  53
  
  embora isso não aconteça necessariamente e outras técnicas possam ser usadas.)
  Nesse ínterim, a escolha do menor quociente positivo mantém
  a última coluna não negativa, subtraindo de cada entrada original
  um valor menor (nas linhas com quociente positivo) ou somando
  propriamente (nas linhas com quociente negativo, como a da função objetivo). Isso preserva a factibilidade das variáveis em estudo.
  Se remontarmos o sistema a partir do tableau, veremos que quaisquer outros valores não negativos para as variáveis acabarão por
  subtrair algo de V, de modo que o valor obtido realmente é máximo.
  Porém, duas possibilidades podem atrapalhar a execução do
  Simplex: não encontrarmos um pivô, ou encontrarmos o mesmo
  tableau duas vezes.
  O primeiro caso é quando uma coluna pivô não tem entradas
  positivas. Nesse caso, é possível mostrar que a variável correspondente a essa coluna fica livre, ou seja, pode ter um valor positivo
  arbitrário; então, o poliedro definido pelas inequações é um sólido
  ilimitado e, portanto, a função V também é ilimitada.
  No segundo caso, o valor de V não aumentou entre as duas
  repetições do mesmo tableau (afinal, esse valor é parte do tableau) e
  os pivôs envolvidos são todos degenerados. Há casos em que não há
  outra escolha de pivôs e o método falha.
  
  3.2 Programação linear pelo Excel
  O procedimento de otimização linear nem sempre é factível
  manualmente, dado que, em geral, seus problemas já envolvem
  uma quantidade muito grande de equações dentro do sistema, como
  é o caso dos problemas de alocação aqui descritos. Por exemplo, um
  pequeno problema de casamento com somente 6 pessoas (3 casais)
  já envolverá 15 inequações. Dessa forma, é interessante utilizar ferramentas que agilizem a resolução do sistema linear.
  Portanto, incluímos, aqui, um exemplo de resolução de sistemas lineares por meio de planilhas eletrônicas. A título de exemplo,
  
  54  aline guarnieri gubitoso | vinicius cifú lopes
  
  trabalharemos o problema anterior de programação linear, em que
  tivemos que produzir bolos, tortas e biscoitos de modo a maximizar
  sua receita bruta.
  O primeiro passo é montar a tabela com todos os dados e cálculos necessários na planilha. Para facilitar, criamos um “cabeçalho” nas 1ª e 2ª linhas, em que deixamos a 1ª célula vazia (as células
  que não serão preenchidas mostraremos em cinza nas figuras) e, na
  2ª célula, inserimos “coeficiente de x” ou “coef. x” (que determina a
  quantidade do produto “bolo” a ser produzida, como determinamos
  na Seção 3.1), seguido de “coeficiente de y” ou “coef. y” (que determina a quantidade do produto “torta” a ser produzida) na célula
  seguinte e, depois, de “coeficiente de z” ou “coef. z” (que determina
  a quantidade de “dúzias de biscoito” a ser produzida). Mantemos
  as próximas duas células vazias, para, então, na seguinte (7ª célula), inserirmos “total utilizado” ou “tot. utilizado” e, na subsequente
  (8ª célula), “total disponível” ou “tot. disponível”.
  
  Uma vez feito o “cabeçalho”, inserimos a função objetivo
  V = 8x + 6y + 5z na 3ª linha da tabela, ou seja, em sua 1ª célula
  inserimos “objetivo” para identificarmos a qual função estamos fazendo referência. Em seguida, incluímos os valores que constituem
  os coeficientes, de forma que, na 2ª célula, inserimos o número 8, na
  3ª célula o número 6 e, na 4ª célula, o número 5, sem trocar o sinal.
  
  Após a elaboração destas duas primeiras linhas, pulamos uma
  linha e começamos a preencher o restante da planilha. Assim, na
  coluna A, iniciamos com a inserção do nome do primeiro ingrediente na 5ª linha, “Maçãs”; na 6ª linha, inserimos o nome do segundo
  alocações, estabilidade e otimização  55
  
  ingrediente, “Açúcar”, e, na 7ª linha, o nome do terceiro ingrediente,
  “Farinha”.
  Ao passo que, na coluna B, inserimos a quantidade de cada
  ingrediente para a fabricação de bolo, ou seja, em sua 5ª linha inserimos a quantidade necessária de 3 maçãs para a produção de
  um bolo, enquanto que na 6ª linha inserimos a quantidade também
  necessária de 1 xícara de açúcar para se produzir um bolo e na 7ª
  linha inserimos a quantidade necessária de 2 xícaras de farinha à
  produção de um bolo.
  Consequentemente, na coluna C inserimos as respectivas
  quantidades de maçãs, xícaras de açúcar e xícaras de farinha para
  a produção de uma torta, assim como na coluna D inserimos as respectivas quantidades de maçãs, xícaras de açúcar e xícaras de farinha para a produção de uma dúzia de biscoito. Dessa forma, temos:
  
  Em seguida, pulamos as colunas E, F e G e completamos a coluna “tot. disponível” (coluna H) com os valores determinados pelas
  inequações da Seção 3.1, ou seja, a partir da 5ª linha da coluna H
  inserimos a quantidade total de 840 maçãs que possuímos, assim
  como na 6ª linha a quantidade total de 630 xícaras de açúcar e, na
  7ª linha, a quantidade total de 450 xícaras de farinha à disposição.
  
  56  aline guarnieri gubitoso | vinicius cifú lopes
  
  Agora, pulamos a 8ª linha e, na linha seguinte (9ª linha), inserimos “x =” na coluna B, ao passo que inserimos “y =” na coluna
  C e “z =” na coluna D. As células abaixo desses elementos, na 10ª
  linha, são o local onde serão apresentados os valores de cada um
  desses coeficientes em sua forma mais eficiente, isto é, para se alcançar a maximização da receita bruta. Os valores nestas células
  irão variar com a execução do Solver, porém, é preciso completar a
  planilha para iniciar o processo. Para tanto, inserimos o número 1
  nestas células.
  
  Depois, incluímos as fórmulas para o cálculo da otimização
  na coluna G: na 3ª linha dessa coluna inserimos a fórmula = B3 *
  B10 + C3 * C10 + D3 * D10 que realiza a multiplicação dos números
  contidos nas células B3, C3 e D3 com os números correspondentes
  contidos nas células B10, C10 e D10 e, depois, somados entre si. Depois, na 5ª linha, inserimos a fórmula = B5 * B10 + C5 * C10 + D5
  * D10, que determina a quantidade de maçãs usada na fabricação
  de bolos, tortas e dúzias de biscoito. Assim, fazemos o mesmo nas
  linhas seguintes, de forma que na 6ª, seja inserida a fórmula = B6 *
  B10 + C6 * C10 + D6 * D10 para a quantidade de xícaras de açúcar
  e, na 7ª, a fórmula = B7 * B10 + C7 * C10 + D7 * D10 para a quantidade de xícaras de farinha.
  O leitor com prática no Excel experimentará selecionar a
  célula G5, clicar no quadrado que aparece no seu canto inferior
  direito e “arrastar” para as demais células para completamento
  automático; contudo, é preciso cuidado e verificar que os índices
  alocações, estabilidade e otimização  57
  
  10 serão indevidamente também modificados. Um jeito de resolver
  isso é através do uso do cifrão $ ao escrever a fórmula em G5: esse
  símbolo fixa a identificação da linha ou coluna que o seguir, por
  exemplo, em B$10 ou $B$10, quando copiamos para todo um grupo
  de células. Porém, no exemplo de emparelhamento, veremos como
  realizar todas as somas com uma única operação matricial.
  Por conseguinte, as fórmulas determinam o valor 19 na célula
  G3, 14 na célula G5 e 6 nas células G6 e G7 (enquanto o Solver ainda não foi executado).
  
  O passo seguinte é utilizar a ferramenta Solver do programa
  Excel, que pode ser encontrada na aba “Ferramentas” ou na aba
  “Dados”, juntamente com outras ferramentas de análise.
  Se for necessário instalá-lo, vá ao menu principal do Excel,
  item “Ferramentas” ou “Opções”, subitem “Add-ins” ou “Suplementos”, procure por “solver” e proceda com as instruções na tela. Essa
  operação pode não funcionar, informando que o arquivo “solver.
  xlam” não está presente. Nesse caso, rode a reinstalação do Office
  para incluir o item “Ferramentas Compartilhadas do Office”, subitem “Aplicação Básica Visual” e refaça a operação.
  Uma vez disponível e selecionado o Solver, acompanhe o
  preenchimento de seu “quadro de diálogo” na próxima figura.
  O primeiro passo é determinar a “Célula de Destino”, isto é, a
  célula que acumula o valor calculado da função objetivo, que, neste
  caso, é a célula G3, cuja fórmula soma os produtos dos coeficientes de x, y e z pelos valores dessas variáveis. Para selecioná-la,
  
  58  aline guarnieri gubitoso | vinicius cifú lopes
  
  podemos clicar no botão disponível à direita do campo de preenchimento; o quadro de diálogo será substituído por outro, menor,
  que o usuário pode ignorar e optar por selecionar a célula desejada
  diretamente na própria planilha; de imediato, o quadro de diálogo
  será restaurado com o campo preenchido. (Estes cifrões serão inseridos pelo próprio programa para fixar a identificação das células.)
  Em seguida, como desejamos maximizar a renda bruta, selecionamos a opção “Máx.”. As “Células Variáveis” serão as células
  B10, C10 e D10 que identificam os valores dos coeficientes que irão
  mudar de acordo com a execução do Solver; elas também podem ser
  selecionadas, como um intervalo de células, com o uso do botão à
  direita do campo.
  
  alocações, estabilidade e otimização  59
  
  Por fim, inserimos as restrições no quadro de diálogo, de modo
  que, por uma questão de lógica, os valores de B10, C10 e D10 devem
  ser maiores ou iguais a zero e os valores de G5, G6 e G7 ser menores
  ou iguais aos valores de H5, H6 e H7, respectivamente. Podemos tratar as duas situações do mesmo modo, mas, também, selecionar, especificamente, a opção que aparece mais abaixo, “Tornar Variáveis
  Irrestritas Não Negativas”, para tratar o primeiro conjunto de
  condições, que é muito comum. Para as outras restrições, clicamos
  o botão “Adicionar” e selecionamos os intervalos de células no novo
  quadro de diálogo, assim como a relação de desigualdade entre eles.
  Uma vez incluídos os elementos de análise, selecionamos “LP
  Simplex” como modelo de solução e, então, clicamos em “Resolver”.
  Em vista disso, o Solver começa a ser executado e, se ele encontrar
  uma solução, automaticamente substituirá os valores na tabela por
  novos, os quais maximizam a receita bruta. Logo, temos a seguinte
  tabela reformulada pelo Solver:
  
  Isso significa que o valor da função objetivo é de R$ 1962 (brutos), devido aos 144 bolos (na célula B10) e 162 dúzias de biscoitos (na
  célula D10) produzidos. Entretanto, não fazemos nenhuma torta, dado
  que a célula C10 está zerada.
  Além disso, podemos notar que todas as quantidades de xícaras de açúcar e de xícaras de farinha disponíveis foram utilizadas,
  ao passo que somente 594 maçãs foram utilizadas, o que resulta
  num saldo de 246 maçãs.
  Portanto, se voltarmos à primeira seção, verificaremos que
  os resultados obtidos pela programação linear no Excel coincidem
  
  60  aline guarnieri gubitoso | vinicius cifú lopes
  
  com a resolução manual do sistema. Dessa forma, utilizaremos essa
  técnica para a resolução de problemas do casamento.
  
  3.3 Otimização linear no problema do casamento
  Para que o problema do casamento possa ser resolvido pela programação linear, devemos, primeiramente, expressá-lo em um sistema de equações e inequações lineares. Para isso, os primeiros elementos a serem considerados são o número de pessoas no problema,
  o que determina a quantidade de equações necessárias, e se ocorre
  ou não a formação de um casal entre um homem H e uma mulher M.
  Definição e notação: Para denotar o pareamento entre
  H e M, utilizaremos a variável booleana XHM ou X(H,M), que
  pode assumir somente dois valores: 0 (falso) quando H e M
  não estão casados ou 1 (verdadeiro) quando H – M. Note que
  sempre temos X(H,M) ≥ 0.
  Demonstramos o processo de alocação estável de casais a seguir, com um exemplo, utilizando o Excel com o Solver. A título
  de exemplo, tomamos o universo de 5 homens e 5 mulheres, sendo
  eles: Victor (V); Wilson (W); Xavier (X); Yuri (Y); Zé (Z); Ana (A);
  Beatriz (B); Carolina (C); Débora (D); Érica (E).
  As pessoas de ambos os grupos continuam a listar as pessoas
  do grupo oposto segundo uma ordem de preferência; utilizamos,
  aqui, as mesmas listas de preferências que em nosso primeiro exemplo, na Seção 1.2:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A>C>D>E>B
  A>D>E>B>C
  D>C>B>A>E
  A>D>B>E>C
  C>D>A>B>E
  
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  Z>W>V>Y>X
  V>X>Y>Z>W
  Z>W>V>X>Y
  V>W>Y>X>Z
  W>Z>X>Y>V
  
  alocações, estabilidade e otimização  61
  
  Com o intuito de montar as equações, notaremos que, de acordo
  com o número 2n de agentes envolvidos no problema (10 pessoas, 5
  de cada grupo), são necessárias 2n + n2 equações. Ao substituirmos n
  por 5 descobrimos o número total de 35 equações para este problema.
  Destas 35 equações, as 10 primeiras equações dirão respeito
  a cada um dos indivíduos, em que se determinam todos os possíveis
  pares que ele pode fazer com as pessoas do grupo oposto. As demais
  25 equações dirão respeito às preferências dos parceiros sob cada possível emparelhamento.
  Lembre que:
  
  Dessa forma, montamos, primeiramente, as equações de cada
  indivíduo de um dos grupos, como dos homens, em que cada homem
  tem uma equação que soma todos os pares que ele forma com cada
  uma das mulheres do problema. Além disso, essas equações devem
  ser igualadas a 1, pois temos a certeza de que existe a possibilidade
  de formação de algum desses pares, isto é, para cada agente algum
  par pode ser formado e deverá ser único. Assim:
  
  S
  Para cada mulher M, temos a equação S
  
  • Para cada homem H, temos a equação
  
  M
  
  X(H, M) = 1.
  
  •
  
  H
  
  X(H, M) = 1.
  
  Justificativa: Como cada variável XHM só pode valer 0 ou
  1, a soma de todas as variáveis para cada agente deve igualar
  1, o que garante que, dessas variáveis, somente uma valha 1
  (correspondendo ao casamento realizado) e as outras valham
  0 (casamentos não realizados).
  Por exemplo, a equação de Victor deve conter os potenciais
  pares dele com Ana (VA), Beatriz (VB), Carolina (VC), Débora (VD),
  e Érica (VE),com sua soma igualada a 1:
  Victor: XVA + XVB + XVC + XVD + XVE = 1
  62  aline guarnieri gubitoso | vinicius cifú lopes
  
  Depois, fazemos o mesmo procedimento com o outro grupo,
  das mulheres. Por exemplo, a equação de Ana deve conter seus pares com Victor (VA), Wilson (WA), Xavier (XA), Yuri (YA), e Zé (ZA)
  com soma igual a 1:
  Ana: XVA + XWA + XXA + XYA + XZA = 1
  Assim, ao final, temos as seguintes equações de cada pessoa:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  Ana:
  Beatriz:
  Carolina:
  Débora:
  Érica:
  
  XVA + XVB + XVC + XVD + XVE
  
  =1
  
  XWA + XWB + XWC + XWD + XWE
  
  =1
  
  XYA + XYB + XYC + XYD + XYE
  
  =1
  
  XVA + XWA + XXA + XYA + XZA
  
  =1
  
  XVC + XWC + XXC + XYC + XZC
  
  =1
  
  XVE + XWE + XXE + XYE + XZE
  
  =1
  
  XXA + XXB + XXC + XXD + XXE
  
  =1
  
  XZA + XZB + XZC + XZD + XZE
  
  =1
  
  XVB + XWB + XXB + XYB + XZB
  
  =1
  
  XVD + XWD + XXD + XYD + XZD
  
  =1
  
  Em seguida, montamos um outro tipo de equações (as 25 restantes), mais propriamente desigualdades, em que contemplamos
  cada possível par entre homens e mulheres. Para formação desse
  segundo tipo de equações, primeiro somamos os pares que a mulher
  da equação acredita serem piores do que o parceiro emparelhado
  com ela (isto é, os pares com homens que estão depois de seu par em
  sua lista de preferência). Depois, subtraímos os pares que o homem
  da equação prefere à sua parceira (ou seja, os pares com as mulheres mais preferíveis que sua parceira em sua lista de preferência).
  Ou seja, para o par (H, M), temos:
  
  alocações, estabilidade e otimização  63
  
  Justificativa: Essa desigualdade é montada de modo, que o
  par (H, M) não possa ser um par de bloqueio. De fato, se H e M
  forem casados, ambas as somas são nulas. Caso contrário, como
  cada soma vale 0 ou 1, se M estiver pareada a um homem H’ que
  considere inferior a H (a soma esquerda é 1), então H deverá
  estar pareado a uma mulher M’ que considere superior a M (a
  soma direita será 1); por outro lado, se H estiver pareado a uma
  mulher que considere inferior a M (a soma direita é 0), então M
  deverá estar pareada a um homem que considere superior a H
  (a soma esquerda será 0).
  Dessa forma, primeiro selecionamos um homem e uma mulher para, então, montar uma equação para este par. Por exemplo,
  notamos que o par Victor e Ana tem a seguinte equação: Ana considera Yuri e Xavier como menos preferíveis que Victor, enquanto
  que, na segunda parte, Victor considera que não há ninguém mais
  preferível que Ana. Ou seja:
  VA: (XYA + XXA) – (0) ≤ 0
  Continuamos a montar as equações de cada par. A fim de facilitar, montamos primeiro todos os possíveis pares de Victor, isto
  é, Victor e Ana; Victor e Beatriz; Victor e Carolina; Victor e Débora;
  Victor e Érica:
  VA:
  VB:
  VC:
  VD:
  VE:
  
  (XYA + XXA) – (0)
  (XXB + XYB + XZB + XWB ) – (XVA + XVC + XVD + XVE )
  (XXC + XYC) – (XVA)
  (XWD + XYD + XXD + XZD ) – (XVA + XVC)
  (0) – (XVA + XVC + XVD)
  
  ≤0
  ≤0
  ≤0
  ≤0
  ≤0
  
  Em seguida, todos os possíveis pares de que Wilson pode fazer
  parte, isto é, Wilson e Ana; Wilson e Beatriz; Wilson e Carolina;
  Wilson e Débora e Wilson e Érica:
  
  64  aline guarnieri gubitoso | vinicius cifú lopes
  
  WA:
  WB:
  WC:
  WD:
  WE:
  
  (XVA + XYA + XXA) – (0)
  (0) – (XWA + XWD + XWE )
  (XVC + XXC + XYC) – (XWA + XWD + XWE + XWB )
  (XYD + XXD + XZD) – (XWA)
  (XZE + XXE + XYE + XVE) – (XWA + XWD)
  
  ≤0
  ≤0
  ≤0
  ≤0
  ≤0
  
  Assim como os pares em que Xavier é contemplado, isto é,
  Xavier e Ana; Xavier e Beatriz; Xavier e Carolina; Xavier e Débora
  e Xavier e Érica:
  XA:
  XB:
  XC:
  XD:
  XE:
  
  (0) – (XXD + XXC + XXB)
  (XYB + XZB + XWB ) – (XXD + XXC)
  (XYC) – (XXD)
  (XZD) – (0)
  (XYE + XVE) – (XXD + XXC + XXB + XXA + XXB)
  
  ≤0
  ≤0
  ≤0
  ≤0
  ≤0
  
  Agora, os pares de Yuri, isto é, Yuri e Ana; Yuri e Beatriz;
  Yuri e Carolina; Yuri e Débora e Yuri e Érica:
  YA:
  YB:
  YC:
  YD:
  YE:
  
  (XXA) – (0)
  (XZB + XWB) – (XYA + XYD)
  (0) – (XYA + XYD + XYB + XYE)
  (XXD + XZD) – (XYA)
  (XVE) – (XYA + XYD + XYB)
  
  ≤0
  ≤0
  ≤0
  ≤0
  ≤0
  
  E, por fim, os pares em que Zé está presente, isto é, Zé e Ana;
  Zé e Beatriz; Zé e Carolina; Zé e Débora e Zé e Érica:
  ZA:
  ZB:
  ZC:
  ZD:
  ZE:
  
  (XWA + XVA + XYA + XXA) – (XZC + XZD)
  (XWB) – (XZC + XZD + XZA )
  (XWC + XVC + XXC + XYC) – (0)
  (0) – (XZC)
  (XXE + XYE + XVE) – (XZC + XZD + XZA + XZB)
  
  ≤0
  ≤0
  ≤0
  ≤0
  ≤0
  
  alocações, estabilidade e otimização  65
  
  Notamos que todos os possíveis pares que cada mulher pode
  ter também estão contemplados nas equações, dado que cada mulher é parte de um dos pares que cada homem tem.
  Ainda não falamos da função objetivo, que construiremos
  mais tarde.
  Observação: Via de regra, na programação linear geral, o Simplex
  oferece resultados que são números reais. As equações que montamos tratam as variáveis X(H,M) como variáveis booleanas e garantem seus valores como 0 ou 1 a partir da hipótese de serem inteiros.
  Esta condição, por sua vez, é garantida por um teorema de Vande
  Vate: todos os vértices do poliedro delimitado pelas restrições usadas têm coordenadas que são todas números inteiros. (Gusfield;
  Irving, 1989, s. 3.7.2; Roth; Sotomayor, 1990, s. 3.2.4.)
  
   Exercícios
  1) Podemos usar o mesmo sistema de equações e inequações para
  simular as propostas realizadas pelas mulheres?
  Resposta: As equações são as mesmas por simetria, enquanto cada inequação
  
  equivale à das mulheres propondo
  
  (note, para tanto, e usando as equações ΣH X(H,M) = 1 e SM X(H,M) = 1, que a
  diferença dos membros esquerdos é (1 – X (H,M)) – (1 – X (H,M)) = 0, ou seja, são
  iguais).
  
  66  aline guarnieri gubitoso | vinicius cifú lopes
  
  2) Mostre que essas inequações equivalem, ainda, à seguinte:
  
  que é apresentada em Roth; Sotomayor (1990, p. 70).
  Resposta: Note que o primeiro e o terceiro termos do membro esquerdo, depois de
  somados, igualam
  .
  
  3) Como devem ser as equações e inequações para tratar um caso
  de listas incompletas e números diferentes de homens e mulheres?
  Resposta: Devemos formar agora as inequações ΣH X(H,M) ≤ 1 e ΣM X(H,M) ≤ 1,
  impor X(H,M) = 0 para qualquer par em que algum dos dois não aceite o outro (ou,
  equivalentemente, remover essa variável de todo o sistema) e acrescentar a desigualdade do exercício anterior somente para pares (H,M) mutuamente aceitáveis.
  (Roth; Sotomayor, 1990, p. 77, devido a Rothblum)
  
  Montagem da planilha e formulação do objetivo
  Uma vez estabelecidas todas as equações necessárias, o passo
  seguinte para a resolução do problema é seguir os passos do Simplex no Excel. Para isso, temos que inserir todas essas informações
  numa planilha. Também montaremos a função objetivo.
  Assim, primeiro criamos um cabeçalho: Na 1ª linha, inserimos
  “equação \ variável” ou “eq. \ var.” que significa, respectivamente, os rótulos das equações e rótulos das variáveis nas equações.
  Na célula seguinte, inserimos o par “VA”, na subsequente “VB”,
  e assim em diante; quando todos os pares de Victor forem inseridos, começamos a inserir os pares de Wilson, e, então, de Xavier,
  Yuri e Zé, até inserir “ZE”, na 27ª célula (coluna AA). Em seguida,
  diminuímos a célula seguinte numa menor largura e, nas nas 29ª
  e 30ª células (colunas AC e AD) inserimos “variáveis” e também
  diminuímos a largura da 31ª e 32ª células. Depois, na 33ª célula
  (coluna AG), inserimos “totais” e na 34ª célula (coluna AH), inserimos “disponível” ou “dispon.”. A figura abaixo mostra isso, estando
  dividida em duas partes para melhor compreensão:
  alocações, estabilidade e otimização  67
  
  Após a elaboração do cabeçalho, diminuímos a espessura da 2ª
  linha e montamos um outro cabeçalho, agora vertical, na 1ª coluna
  a partir da 3ª linha. Inserimos “objetivo” na 3ª linha (em referência à função objetivo de que ainda trataremos). Na linha seguinte,
  também diminuímos sua espessura, e, então, na 5ª linha, iniciamos
  a inserção das equações: inserimos “Victor” ou “V”. linha seguinte,
  inserimos “Wilson” ou “W”; na subsequente, “Xavier” ou “X”, e assim
  por diante. Quando todos os homens forem incluídos, inserimos, na
  linha seguinte, as mulheres, começando por “Ana” ou “A”, seguida
  pelas demais mulheres. Por fim, depois que todas forem incluídas,
  inserimos os pares, começando com “VA”, depois “VB” na seguinte, e
  assim por diante. Mostramos essa coluna em quatro partes:
  
  Uma vez esclarecidos os rótulos (informações dos cabeçalhos
  horizontal e vertical), inserimos os valores da função objetivo: o primeiro par é VA, sendo assim, temos de verificar qual é a posição de
  A na lista de preferências de V; como A é sua 1ª opção, inserimos o
  número 1 na interseção da 3ª linha com a coluna VA; em seguida,
  temos o par VB, de forma que, como B é a 5ª opção de V, inserimos o
  número 5 na célula D3 e continuamos fazendo o mesmo procedimento
  com cada um dos pares. Explicaremos essa função mais à frente.
  Ao final, temos a seguinte função objetivo – quando são os homens que propõem (somente exibimos o começo da linha):
  
  68  aline guarnieri gubitoso | vinicius cifú lopes
  
  O passo seguinte é inserir os coeficientes das equações feitas
  acima. Assim, na 5ª linha, como para Victor qualquer pareamento
  com ele e alguma das mulheres é possível, insere-se o número 1 nas
  células C5 a G5 (porque estão nas colunas dos pares em que Victor
  está presente), enquanto que nas demais células até a célula da coluna AA dessa linha inserimos 0 porque Victor não consta em mais
  nenhum par. Ademais, como a equação de Victor é igualada a 1, inserimos esse número na coluna “dispon.” (coluna AG) na linha desta
  equação (5ª linha). Aqui estão as duas partes dessa linha:
  
  Consequentemente, na 6ª linha, que se refere a Wilson, somente
  nas células de H6 a I6 inserimos o número 1, de forma que, nas células restantes até a coluna AA, inserimos o número 0, mas, também,
  depois, inserimos o número 1 na coluna AG. O mesmo é feito com as
  equações de cada um dos homens (na imagem, demonstramos apenas
  até o par XE):
  
  Depois, o mesmo é feito com as mulheres. Por exemplo, na 10ª
  linha, que se refere a Ana, inserimos o número 1 somente nas células das colunas em que ela é um dos parceiros, sendo elas C10, H10,
  M10, R10 e W10, além de inserirmos na coluna AG. Na 11ª linha,
  que se refere a Beatriz, somente inserimos o número 1 nas células
  D11, I11, N11, S11 e X11 e na coluna AG; depois, fazemos o mesmo
  com Carolina, Débora e Érica (na imagem, demonstramos apenas
  até o par XE):
  alocações, estabilidade e otimização  69
  
  A partir da 15ª linha, os coeficientes são 1, 0 ou –1 e analisamos as inequações dos casais da seguinte maneira: os pares que
  estão dentro da primeira somatória recebem o número 1, enquanto
  que os que estão na segunda somatória, devido ao sinal de subtração, tornam-se –1, e os demais pares, que não aparecem em nenhum
  dos parênteses, recebem o número 0, assim como as células da coluna AG, uma vez que essas expressões são sempre menores ou iguais
  a 0. Por exemplo, VA tem a seguinte equação:
  VA: (XYA + XXA) – (0) ≤ 0
  Logo, na linha deste par (15ª linha) procuramos a célula que
  faz interseção com a coluna de YA, no caso R15, e inserimos o número 1. Também procuramos a interseção com XA, no caso M15, e
  inserimos o número 1. Como não há mais nenhum par explícito, nas
  demais células, inserimos o número 0.
  Na linha seguinte, temos o par VB, com a seguinte inequação:
  VB: (XXB + XYB + XZB + XWB ) – (XVA + XVC + XVD + XVE) ≤ 0
  Assim, procuramos as interseções com os emparelhamentos do
  primeiro parêntese, no caso I16, N16, S16, X16, e inserimos o número 1. Depois procuramos as interseções com os pares do segundo
  parêntese, no caso C16, E16, F16 e G16, e inserimos o número – 1,
  enquanto que, nas demais células da linha, inserimos o número zero.
  Fazemos isso com cada inequação referente a um par e obtemos a seguinte tabela (na imagem, demonstramos apenas até a
  coluna do par XE):
  
  70  aline guarnieri gubitoso | vinicius cifú lopes
  
  alocações, estabilidade e otimização  71
  
  O próximo passo é inserir os pares na coluna “Variáveis”, (colunas AC e AD), como referência ao rótulo das variáveis propriamente ditas, de forma que, na célula AC9, inserimos “VA”. Na célula
  abaixo, inserimos “VB” e assim em diante; depois, nas células ao
  lado (na coluna AD), inserimos o número 1, simplesmente para completar a planilha, uma vez que os valores nestas células irão variar
  com a execução do Solver (aqui mostramos em duas partes):
  
  Em seguida, inserimos as fórmulas para o cálculo da otimização na coluna AG: Selecionamos da 5ª linha até a 39ª linha dessa
  coluna, pressionamos a tecla “F2”, inserimos a fórmula
  = MATRIZ.MULT (C5: AA39; AD9: AD33)
  e pressionamos, simultaneamente, “Ctrl”, “Shift” e “Enter”. A fórmula calcula o produto da matriz das células de C5 até a célula AA39 com o vetor da coluna AD da 9ª linha até a 33ª linha.
  Trata-se de uma fórmula cujo resultado deve preencher todo um
  intervalo de células e o procedimento indica isso para o programa.
  Após o procedimento, o Excel exibe essa fórmula entre chaves para
  destacar essa particularidade. Em AG3, pomos:
  = MATRIZ.MULT (C3: AA3; AD9: AD33),
  72  aline guarnieri gubitoso | vinicius cifú lopes
  
  que calcula a função objetivo com os parâmetros na coluna AD, da
  9ª à 33ª linha. Enquanto não executamos o Solver, essas fórmulas
  calculam números que só depois serão otimizados. (O leitor deve
  experimentar o uso das fórmulas matriciais também no exemplo da
  seção anterior.)
  Portanto, o próximo passo é executar o Solver. Para isso, selecionamos a aba “Ferramentas” ou “Dados” do menu principal do
  Excel e, em seguida, selecionamos Solver. Assim, primeiramente
  temos de determinar a “Célula de Destino”, isto é, a célula que
  acumula o valor calculado da função objetivo, que, neste caso, é a
  célula AG3. Para obter uma alocação mais favorável aos homens,
  selecionamos, então, a opção “Mín.”, como explicaremos a seguir.
  Depois, selecionamos as “Células Variáveis”, isto é, os valores dos
  coeficientes que irão mudar de acordo com a execução do Solver,
  sendo eles as células da coluna AD da 9ª linha até a 33ª linha. Por
  fim, inserimos as restrições no quadro de diálogo, de modo que,
  como montamos as equações e inequações, os valores de AG5 até
  AG14 devem ser iguais aos valores de AH5 até AH14 e os valores
  de AG15 até AG39 devem ser menores ou iguais aos valores de
  AH15 até AH39, respectivamente, enquanto as variáveis incógnitas devem ser não negativas.
  
  alocações, estabilidade e otimização  73
  
  Uma vez incluídos os elementos de análise, selecionamos “LP
  Simplex” como modelo de solução e, então, clicamos em “Resolver”.
  Em vista disso, o Solver começa a ser executado, com os homens
  sendo os mais favorecidos. Na solução encontrada, observamos, primeiro, os pares formados nas colunas AC e AD, sendo eles os pares
  que, na coluna AD, pela otimização do Solver, obtiveram o número 1.
  Portanto, temos: Victor e Debora (VD); Wilson e Ana (WA); Xavier e
  Beatriz (XB); Yuri e Érica (YE); e Zé e Carolina (ZC). Notamos que
  esse resultado é exatamente igual ao que obtivemos manualmente
  na Seção 1.2.
  A próxima figura exibe a planilha completa que montamos.
  
  74  aline guarnieri gubitoso | vinicius cifú lopes
  
  alocações, estabilidade e otimização  75
  
  Explicação da função objetivo
  Também devemos observar, nesta tabela final, o valor da função objetivo, que significa a otimização da soma das posições dos
  pares de todos os homens.
  Notação: Para denotar a posição de M na lista de preferência de H, utilizamos a expressão PH (M). Ao passo que, para denotar a posição de H na lista de preferência de M, utilizamos
  a expressão PM (H).
  A função objetivo que minimizamos é simplesmente:
  
  Justificativa: Essa somatória adiciona o termo exibido,
  simultaneamente, para todos os homens e mulheres. Porém,
  para cada homem H, somente uma variável X(H,M) vale 1 e as
  demais valem 0, então, somente um fator PH (M) é efetivamente adicionado e é o que corresponde à esposa de H, enquanto
  os demais termos são anulados.
  Dessa forma, o número 12, na célula AG, significa a soma das
  3 posições que Victor tem em sua lista de preferências até sua parceira, Débora, com mais 1 posição da lista de Wilson até Ana; além
  de mais 3 posições na lista de Xavier; 4 posições na lista de Yuri e 1
  posição na lista de Zé:
  Victor:
  Wilson:
  Xavier:
  Yuri:
  Zé:
  
  A>C> D >E>B
  A >D>E>B>C
  D>C> B >A>E
  A>D>B> E >C
  C >D>A>B>E
  
  posição 3
  posição 1
  posição 3
  posição 4
  posição 1
  
  76  aline guarnieri gubitoso | vinicius cifú lopes
  
  total 12
  
  Desse modo, na prática, instruímos o Solver a procurar pela
  menor soma das distâncias das mulheres nas listas de seus parceiros. Se desejamos uma alocação mais favorável às mulheres, selecionamos “Máx.”, porque esta procura pela maior soma das distâncias das mulheres nas listas de seus parceiros, lembrando que o pior
  pareamento para os homens significa o melhor pareamento para as
  mulheres. Logo, não é necessário que modifiquemos a função objetivo, uma vez que selecionar “Máx.” já significa inverter os sinais de
  todas as equações como se invertêssemos os papéis dos dois grupos
  de agentes.
  
  3.4 Emparelhamento estável igualitário
  Na formulação acima, explicitamos que, ao utilizarmos a programação linear para resolução do problema do casamento, deveríamos optar ou por minimizar a função objetivo, favorecendo,
  então, o grupo que faz as propostas, ou maximizar essa função, de
  forma a favorecer o grupo que recebe as propostas. Entretanto,
  alguns avanços já foram feitos, de forma que esse mecanismo não
  se restrinja a tais opções.
  Assim, é possível a descoberta de emparelhamentos mais
  igualitários entre os homens e as mulheres a partir da inclusão de
  “pesos” de preferência ao invés de somente uma lista ordenada.
  Por exemplo, podemos tratar homens e mulheres simetricamente e igualmente a partir de uma função objetivo que os contemple dessa forma:
  
  Essa expressão, na reunião entre homens e mulheres, considera simultaneamente os pesos das preferências de ambos, de acordo com a posição de seu parceiro em sua lista de preferência.
  alocações, estabilidade e otimização  77
  
  Dessa forma, é possível formular uma nova função objetivo,
  com a qual obteremos um resultado de emparelhamento igualitário
  quando é minimizada.
  A Seção 3.6 de Gusfield; Irving (1989) dá três definições de
  emparelhamentos mais simétricos entre proponentes e seletores, inclusive a somatória acima, e algoritmos eficientes para encontrá-los,
  utilizando princípios teóricos subjacentes a Gale-Shapley em vez da
  programação linear geral.
  Uma dessas definições permite maior flexibilidade na formulação de listas de preferência, em que cada agente atribui “pontuações” àqueles que deve comparar, em lugar de simples “posições”. Por
  exemplo, o agente X pode expressar o quanto A >X B atribuindo valores reais PX (A) e PX (B) que devem apenas satisfazer PX (A) < PX (B)
  (note que, quanto menor a pontuação ou nota, melhor a opção).
  É possível, até mesmo, estabelecer um “passeio” partindo do
  emparelhamento ótimo dos homens e chegando ao das mulheres,
  para escolhermos qualquer ponto entre eles: para t ∈ [0,1], defina
  
  O parâmetro t pode ser identificado em uma célula adicional
  da planilha que montamos e usado na fórmula da função objetivo
  V (t) (que é função das variáveis XHM). Então, V (0) é a função objetivo que, minimizada, induz o emparelhamento ótimo dos homens; V
  (1) é aquela ótima para as mulheres; corresponde à primeira somatória acima, exceto por um fator de escala, e tem os mesmos pontos
  de máximo e de mínimo.
  Além de possibilidades como essas, Gusfield; Irving (1989,
  p. 219) propõem tornar a soma das “pontuações” dos homens
  PH (M) ⋅ X(H,M) a mais próxima possível à soma das “pontuaH,M
  ções” das mulheres H,M PM (H) ⋅ X(H,M). Em Knuth (1997, p. 51),
  minimiza-se não a somatória, mas uma função de máximo:
  
  S
  
  S
  
  78  aline guarnieri gubitoso | vinicius cifú lopes
  
  3.5 Discussão
  Apresentamos e exemplificamos a resolução de problemas do
  casamento a partir da otimização linear e do algoritmo Simplex, com
  a aplicação da ferramenta Solver no Excel.
  Como a programação linear pôde, também, resolver um problema envolvendo maçãs, farinha, bolos e tortas, assim como é cotidianamente utilizada na indústria, observamos que expressar o
  problema do casamento em um sistema de equações e inequações
  lineares foi mais um exemplo de redução, agora do problema do
  casamento aos problemas de otimização linear. Nós o utilizamos,
  também, para apresentar algumas melhorias, especialmente para a
  busca por emparelhamentos estáveis igualitários.
  Destacamos, porém, que esse mecanismo de resolução não é
  o mais eficiente, porque o de Gale-Shapley requer menos passos e
  cálculos. Também Gusfield; Irving (1989, s. 3.7.1) apresentam uma
  redução mais eficiente à programação linear, mas concedem (p. 147)
  que o sistema de Vande Vate é mais elegante e não requer uma
  solução preliminar, nem o conceito de rotações que estudaremos somente no problema dos colegas de quarto.
  
  alocações, estabilidade e otimização  79
  
  4
  Manipulação e trapaças
  Um problema de sistemas de seleção e alocação é, na realização prática, a preocupação dos candidatos em entender o processo
  a que serão submetidos e atuar de modo a obter o melhor resultado
  possível.
  No modelo de alocação que consideramos, com propostas e escolhas, perceberemos a possibilidade de um candidato rejeitar uma
  proposta que prefira e escolher uma outra que considere pior, a fim
  de alcançar um resultado melhor no final do processo. Dessa forma,
  o agente apresentaria erroneamente suas preferências com o propósito de obter resultados diferentes, realmente preferíveis.
  Assim, ao discutirmos a aplicação do algoritmo Gale-Shapley
  e dos programas desenvolvidos para situações do cotidiano, é necessário examinar a questão da manipulação dos dados, principalmente a partir da apresentação falsa das preferências. O ponto de partida para essa análise é o questionamento: é do interesse de todos os
  agentes envolvidos indicar suas verdadeiras preferências?
  Verifica-se que a resposta é negativa, porque o interesse mútuo de todos os agentes em falar a verdade não ocorre em nenhum
  procedimento que produza soluções estáveis. (Roth; Sotomayor,
  1990, p. 87) Como observamos na Seção 1.3, será necessário considerar qualquer possível procedimento, não apenas Gale-Shapley,
  e demonstrações formais no caso deste, não apenas nossa intuição
  com a movimentação das “molduras”.
   81
  
  4.1 Como ocorre a trapaça
  Como um exemplo, adaptado com modificações de Roth; Sotomayor (1990, p. 81), tomamos o seguinte conjunto de preferências:
  Victor (V):
  Wilson (W):
  Xavier (X):
  Yuri (Y):
  Zé (Z):
  
  A>B>C>D
  D>B>A>C
  D>C>B>A
  A>D>C>B
  A>B>D>C
  
  Ana (A):
  Beatriz (B):
  Carolina (C):
  Débora (D):
  
  W>X>V>Y>Z
  X>V>W>Y>Z
  Z>Y>V>W>X
  V>W>Y>Z>X
  
  A partir dessas preferências, obtemos as seguintes alocações
  quando os homens propõem: V – A, W – D, X – B, Y solteiro, Z – C.
  Entretanto, se Ana muda sua lista de preferências, de modo
  a apresentar uma ordenação falsa em que diz preferir Yuri e Zé a
  Victor, isto é:
  Ana (A): W > X > Y > Z > V,
  obtemos outra formação de casais: V – D, W – A, X – B, Y solteiro,
  Z – C.
  com preferências verdadeiras
  A: W > X > V > Y > Z
  B: X > V > W > Y > Z
  C: Z > Y > V > W > X
  D: V > W > Y > Z > X
  
  com preferências falsas
  A: W > X > Y > Z > V
  B: X > V > W > Y > Z
  C: Z > Y > V > W > X
  D: V > W > Y > Z > X
  
  Assim, ao apresentar erroneamente suas preferências, Ana
  melhora sua situação, pois se aloca ao homem que prefere verdadeiramente, enquanto que, antes, estava alocada ao seu terceiro homem mais preferível.
  Além disso, Débora também é beneficiada indiretamente pela
  trapaça de Ana, dado que foi promovida de seu segundo homem
  mais preferível para o primeiro.
  82  aline guarnieri gubitoso | vinicius cifú lopes
  
  Logo, para Ana, é um comportamento estratégico apresentar
  falsas preferências a fim de manter-se junto a um homem menos
  preferível dentre as propostas que recebe, para que, em alguma
  etapa posterior do processo, receba a proposta de um homem mais
  preferível que, se não fosse pela trapaça, não chegaria a lhe propor.
  
   Exercício
  1) Aplique o algoritmo Gale-Shapley aos dois conjuntos de preferências e confira o exemplo.
  Porém, para que a manipulação ocorra e seja bem-sucedida,
  Ana teria que saber as preferências das demais pessoas a fim de
  realizar simulações do processo e descobrir como suas preferências
  falsas poderiam impor novas escolhas. As propostas inéditas a ela
  por seus candidatos mais preferíveis ocorrem quando as mulheres
  a quem eles propuseram, antes, rejeitaram-nos em favor de novas
  opções de parceiros e estes, por sua vez, fazem tais propostas devido
  às rejeições de Ana.
  Assim, para trapacear e ser favorecida, ou Ana tem de ter
  acesso às listas de preferências das demais pessoas ou as propostas têm de ser rodadas mais de uma vez, de forma que, a partir da
  observação das propostas e escolhas, Ana tenha, pelo menos, um
  esboço das preferências.
  Definição: Estratégia é uma decisão sobre o conjunto de
  ações a realizar, como uma postura ou raciocínio para apresentação de informações e decisões, qualquer que seja. Cada
  manipulação das preferências, condicionada ou não às preferências alheias, é uma estratégia, mas ser honesto quanto a
  suas preferências também é uma estratégia.
  Definição: A estratégia dominante de um agente é a estratégia que melhor responde às possíveis estratégias que possam
  alocações, estabilidade e otimização  83
  
  ser adotadas pelos demais agentes. As razões para tal estratégia, que deverá ser seguida pelo agente, acabam por esclarecer que não há nenhum incentivo a ele para que atue de forma
  diferente.
  Assim, em uma situação-problema em geral, é importante determinar qual é a estratégia dominante de cada agente.
  Viabilidade da manipulação
  Para verificarmos quando a trapaça é possível, destacamos alguns resultados e informações de Roth; Sotomayor (1990, p. 87-90),
  referentes a um “mercado”, ou conjunto de agentes, no qual as preferências são estritas e existe mais de uma alocação estável.
  Ao analisar a escolha de cada agente por sua estratégia dominante, Roth constatou que não existe nenhum mecanismo de alocação estável em que indicar as preferências verdadeiras seja a estratégia dominante para todos os agentes. Essa observação ficou então
  conhecida como o Teorema da Impossibilidade de Roth. Depois, por
  consequência, concluiu-se que não existe nenhum mecanismo de
  alocação estável em que indicar as preferências verdadeiras seja
  a melhor estratégia para todos os agentes quando todos os outros
  agentes indicam suas verdadeiras preferências, ou seja, pelo menos
  um agente pode se beneficiar ao apresentar erroneamente suas preferências, assumindo que os outros contaram a verdade.
  Adaptamos, aqui, o exemplo da demonstração dada por Roth
  e Sotomayor:
  Xavier (X):
  Yuri (Y):
  
  A>B
  B>A
  
  Ana (A):
  Y>X
  Beatriz (B): X > Y
  
  Só há dois emparelhamentos possíveis e ambos são estáveis:
  (1º) X – A, Y – B, ótimo para os homens, e (2º) X – B, Y – A, ótimo para
  
  84  aline guarnieri gubitoso | vinicius cifú lopes
  
  as mulheres. Se Ana mudar sua lista para Y > ■, então somente o
  segundo pode ser obtido, qualquer que seja o mecanismo, garantindo sua melhor escolha. Analogamente, qualquer agente (Xavier,
  Yuri ou Beatriz) pode impôr que somente um emparelhamento seja
  possível e, então, obtido pelo mecanismo, contanto que os demais
  três mantenham suas listas originais.
  
   Exercício
  1) Verifique a estabilidade dos dois emparelhamentos e o sucesso
  das estratégias dos quatro agentes.
  Gale e Sotomayor mostraram como, em uma dada situação,
  ao menos um agente pode trapacear: se há ao menos dois emparelhamentos estáveis, o mecanismo produz – um que é distinto ou do
  ótimo dos homens ou do ótimo das mulheres; um desses agentes,
  portanto, não atinge seu ótimo possível e beneficia-se ao remover de
  sua lista todos os indivíduos que considera piores que esse ótimo.
  Entretanto, note que os agentes que apresentam preferências
  falsas são aqueles que recebem as propostas, enquanto que os agentes que propõem têm como melhor estratégia, ou estratégia dominante, indicar suas verdadeiras preferências, dado que o resultado
  é sempre o melhor possível para eles.
  Por exemplo, considerando as seguintes listas de preferência
  para o uso de Gale-Shapley:
  Xavier:
  Yuri:
  Zé:
  
  A>C>B
  A>B>C
  C>B>A
  
  Ana:
  Beatriz:
  Carolina:
  
  Y>X>Z
  X>Z>Y
  Y>X>Z
  
  Com o desenrolar do processo, terminamos, na última rodada, com:
  
  alocações, estabilidade e otimização  85
  
  Xavier:
  Yuri:
  Zé:
  
  A> C >B
  A >B>C
  C> B >A
  
  Ana:
  Beatriz:
  Carolina:
  
  Y >X>Z
  X> Z >Y
  Y> X >Z
  
  Como vimos no Capítulo 1, percebe-se, pelo próprio movimento das molduras, que o homem sempre propõe primeiro à melhor
  opção possível disponível e, se modificar sua lista de preferências,
  será, então, pareado à primeira mulher preferível que o aceitar, da
  mesma forma que ocorre quando se falar a verdade.
  
   Exercício
  1) Aplique o algoritmo de Gale-Shapley e confira esse exemplo.
  Se, nesta situação, tanto Xavier como Zé, os homens que não
  estiveram com sua primeira opção, inverterem suas listas de qualquer forma, vão continuar com Carolina e Beatriz como suas melhores opções possíveis, respectivamente, dado que a primeira opção de
  Xavier está bloqueada pelo par Ana e Yuri, que se preferem mutuamente, e, por conseguinte, a primeira opção de Zé está bloqueada
  pelo par Xavier e Carolina. Zé e Beatriz, mesmo cada um não sendo
  a primeira opção do outro, preferem-se mutuamente, pois seus parceiros “ideais” (Ana e Yuri, respectivamente) já formam um par de
  bloqueio, que não pode ser desfeito para que o resultado continue a
  ser estável. Logo, não há incentivos para eles falsearem sua lista de
  preferência para serem alocados a uma outra parceira.
  Isso em razão de que, sendo os homens que propõem, a situação de cada um apenas pode “piorar” em termos de sua lista de
  preferência. Quando o processo termina, o homem conseguiu sua
  parceira mais preferível possível sem manipular o mecanismo, porque, se escolher alguém menos preferível numa rodada, não haverá
  como, posteriormente, escolher uma parceira mais preferível.
  Logo, a manipulação de um homem em sua lista de preferência,
  quando são eles que propõem, não pode ser bem-sucedida, porque o
  86  aline guarnieri gubitoso | vinicius cifú lopes
  
  resultado será para ele tão bom quanto o resultado original de suas
  preferências verdadeiras.
  Por isso, Dubins e Freedman, assim como Roth, concluíram que
  o mecanismo que resulta na melhor alocação estável para os homens
  (nos termos de preferências indicadas) faz com que a estratégia dominante para cada homem seja indicar suas verdadeiras preferências.
  Ademais, é importante ressaltar que, quando são as mulheres que
  propõem, por simetria, ser verdadeira também é a estratégia dominante de todas elas. Portanto, de forma geral, para o grupo que faz as
  propostas, a melhor estratégia é sempre ser verdadeiro.
  Observações: Até aqui, porém, nossas conclusões estão condicionadas a duas hipóteses: 1) Somente tratamos homens monogâmicos. Um agente proponente com várias “vagas” pode constituir uma
  “coalizão” dessas vagas e obter vantagens, como destacaremos na
  próxima seção. 2) Ademais, não estamos considerando possíveis
  “externalidades”, isto é, incentivos como propinas para que um homem altere sua lista de preferências. Assumimos que os agentes
  proponentes, nesse raciocínio, somente agem em seu próprio benefício e somente em vista da alocação obtida.
  
  4.2 Coalizões
  Vimos que, para todo agente que faz as propostas, a melhor
  política é a honestidade, já que não há necessidade de esses agentes
  modificarem suas preferências para obterem resultados melhores.
  Também é possível mostrar que, considerando os agentes que
  propõem, uma coalizão deles (isto é, um subconjunto) também não
  obtém incentivos o suficiente para desejar manipular suas preferências, porque não há uma alocação que todos os integrantes da coalizão prefiram, de modo que a melhor estratégia é ser verdadeiro.
  (Roth; Sotomayor, 1990, p. 92, devido a Dubins e Freedman)
  Definição: Coalizões são reuniões de dois agentes ou
  mais que agem em conjunto a fim de alterar o resultado das
  alocações.
  alocações, estabilidade e otimização  87
  
  Portanto, para qualquer agente do grupo que propõe, a melhor
  estratégia, tanto individual como de coalizão, é ser verdadeiro.
  Entretanto, como falsear suas preferências pode ser uma estratégia dominante para algumas pessoas do grupo que recebe as propostas, também pode ser estratégico para uma coalização de indivíduos
  deste grupo, de forma que seus indivíduos escolham a trapaça como
  sua estratégia dominante.
  Por exemplo, as mulheres podem negociar entre si a escolha
  de um emparelhamento estável qualquer, até mesmo aquele que é
  ótimo para elas, e, então, cada mulher apresentar uma lista incompleta de preferência, consistindo apenas do homem que lhe cabe
  nesse emparelhamento. Dessa maneira, qualquer mecanismo de
  alocação estável, mesmo Gale-Shapley com propostas feitas pelos
  homens, produzirá, precisamente, esse emparelhamento (Roth;
  Sotomayor, 1990, teo. 4.15 devido a Gale e Sotomayor). Ou, em
  nosso primeiro exemplo, Débora solicitar a Ana que manipule sua
  lista de preferência, em benefício de si mesma, mas, também, ajudando à primeira.
  Quando a coalizão provê algo mais
  Até aqui, a noção que temos de uma coalizão é a de um mero
  conjunto de agentes. É preciso considerar, todavia, que uma coalizão, como um clube exclusivo, também possa oferecer a seus membros benefícios externos ao mercado em questão.
  Assim, um homem (como agente proponente) pode, apresentando listas incompletas, alterar significativamente o resultado final sem se prejudicar. Se uma coalizão de outros homens se interessar nisso e subornar este homem, pode, então, construir resultados
  mais favoráveis a si mesma. (Roth; Sotomayor, 1990, s. 4.3.1.)
  Essa situação é especialmente relevante no casamento poligâmico, porque indica que as vagas proponentes (de um mesmo homem)
  podem realizar uma coalizão. Veremos um exemplo disso na Seção
  5.3, que demonstra uma universidade A que pode melhorar de situação, mesmo quando universidades propõem. (Lá, poderá usar a lista
  88  aline guarnieri gubitoso | vinicius cifú lopes
  
  W > Y > V > X, cf. Roth; Sotomayor, 1990, teo. 5.14.) Os candidatos,
  sendo monogâmicos, porém, não têm motivo para trapacear quando
  propõem. (op. cit., teo. 5.16, e nossa discussão)
  
  4.3 Evitando a trapaça
  Face a toda essa discussão, qualquer projeto prático de mecanismo para alocações estáveis deve ter, em sua concepção, a preocupação de induzir os agentes ao comportamento honesto, ou limitar o
  incentivo à trapaça. Podemos, a partir da observação dos exemplos
  e técnicas descritos, esboçar algumas regras heurísticas:
  A primeira é impedir que os agentes submetam listas de
  preferência muito curtas ou sequer incompletas, consistindo somente de suas opções mais preferíveis. Naturalmente, com uma
  lista assim, o agente assume, também, o risco de não ser alocado
  (ou “ficar solteiro”).
  Outra é, em situação de poligamia ou oferta de vagas que
  constituem coalizões, fazer com que os agentes poligâmicos formem
  o grupo seletor e não o proponente.
  O sistema pode incluir um mecanismo de desfavorecimento dos
  agentes quando trapaceiam e a trapaça não é bem-sucedida ou é detectável e existe um elemento fiscalizador (ou externo ou formado por
  um grupo de agentes). Isso torna a ação de trapacear desnecessária
  ou prejudicial e deixa de “valer a pena”. Um exemplo disso pode ser
  formulado entre estudantes e universidades: caso uma universidade
  admita alunos com notas baixas demais para seu padrão, sua credibilidade e imagem exterior acabarão prejudicadas perante toda a
  comunidade. Consequentemente, ela poderá deixar de receber inscrição de novos candidatos devido à desconfiança, de forma que, num
  futuro próximo, tenha dificuldade para admitir estudantes.
  Além disso, pode-se impor a condição de que cada agente está
  preocupado com sua própria alocação, de forma a não se interessar em
  ajudar outros agentes. Porém, para que isso assim seja, não deve haver externalidades, como incentivos financeiros de um agente ao outro,
  alocações, estabilidade e otimização  89
  
  para que um agente não seja convencido por outro a trapacear, mesmo
  que sua alocação continue a mesma enquanto que aquele que o incentivou melhore de situação (em razão da qual oferece o incentivo). Esta
  é outra necessidade de fiscalização externa ao mercado.
  Costuma-se, em geral, atribuir o papel de proponente ao grupo de agentes que deva ser melhor alocado, para obter seu ótimo.
  Sem dúvida, essa estratégia se particulariza às questões de manipulação, porque será oportuno identificar esse grupo como o que
  também seja mais difícil de fiscalizar, enquanto os agentes seletores
  possam ser orientados apenas com base em sua reputação.
  Outro mecanismo utilizado para se evitar a trapaça é a realização do processo de alocação uma única vez para evitar que, ao
  estudar os resultados, os agentes mudem suas estratégias para obter
  melhores resultados numa tentativa posterior.
  Finalmente, descobriu-se, também, que os benefícios da trapaça são limitados e minimizados quando o mercado é suficientemente grande e cada participante interage com poucos agentes do
  outro grupo. Esse é um exemplo de resultado primeiramente indicado por simulações computacionais e, depois, explicado teoricamente. (Royal Swedish Academy of Sciences, 2012b, p. 14;
  Roth; Peranson, 1999 [resumo])
  
  90  aline guarnieri gubitoso | vinicius cifú lopes
  
  5
  O problema das admissões
  em universidades
  A discussão do problema do casamento não abrange a maioria
  dos problemas enfrentados na economia contemporânea, mesmo aqueles sem mecanismo de preços, devido ao fato de que nesses mercados
  do mundo real não são estruturadas somente alocações entre dois conjuntos de agentes que se combinam em pares.
  Assim, consideraremos, agora, os dilemas de situações mais
  complexas, como o intitulado problema das admissões em universidades, em que alocamos a uma única universidade mais do que
  um único estudante, pois cada curso universitário busca obter uma
  determinada quantidade máxima de alunos matriculados.
  Dessa forma, temos dois grupos, universidades e estudantes,
  de modo que os estudantes buscam ser admitidos nas universidades, enquanto as universidades procuram admitir uma certa quantidade de estudantes (na literatura: “quota”), escolhidos a partir de
  uma avaliação das qualificações destas inscrições. Um exemplo de
  elemento considerado para a ordenação das preferências pode ser a
  nota em uma prova, de modo que os estudantes escolhidos são aqueles com as maiores notas (assumindo que não há nenhum aluno com
  notas iguais, ou que há critérios de desempate).
  Ademais, semelhantemente ao problema do casamento, o conceito de estabilidade, nessas situações, diz respeito à inexistência
  de bloqueios, ou seja, não há um curso e um estudante que não
   91
  
  estejam alocados entre si, ainda que assim o preferissem, ou um
  estudante ou universidade que esteja alocado com um membro do
  grupo oposto considerado inaceitável. Logo, uma alocação é estável
  se não é bloqueada por nenhum agente individual (estudante ou
  universidade) ou por qualquer “par” de universidade e estudante.
  Consequentemente, se não há inscrições suficientes de estudantes aceitáveis, qualquer universidade pode escolher manter
  quaisquer vagas sem serem ocupadas, assim como se qualquer estudante não conseguir ser aceito em nenhuma de suas opções aceitáveis de universidade ou se desejar não entrar em nenhuma universidade, ele pode permanecer sem ser alocado a uma universidade.
  (Essas considerações podem não ser válidas, ou ser limitadas, por
  normatizações públicas ou internas.)
  
  5.1 Exemplo com Gale-Shapley
  Para expor o raciocínio pelo qual se desenvolve essa alocação
  por Gale-Shapley, segue uma demonstração do processo. A título
  de exemplo, tomamos o universo de 5 estudantes e 2 universidades, cada uma com uma quota de 2 vagas (em um único curso ou
  ciclo básico), sendo eles: Victor (V); Wilson (W); Xavier (X); Yuri (Y);
  Zé (Z); Universidade Alfa (A); Universidade Beta (B).
  Primeiramente, os estudantes ordenam as universidades segundo a ordem de suas preferências (podendo omitir aquelas em
  que não desejam estudar em hipótese alguma) e inscrevem-se em
  suas primeiras opções.
  Em seguida, as inscrições são enviadas às universidades,
  que, por sua vez, listam as inscrições recebidas em uma ordem
  de preferência, podendo rejeitar as inscrições que não aceitam de
  forma alguma.
  Para nosso exemplo, temos as seguintes listas de preferência:
  
  92  aline guarnieri gubitoso | vinicius cifú lopes
  
  Victor (V):
  Wilson (W):
  Xavier (X):
  Yuri (Y):
  Zé (Z):
  
  A>B
  A>B
  B>A
  B>A
  B>A
  
  Alfa (A) (2 vagas): V > X > Z > W
  Beta (B) (2 vagas): X > Y > W > Z
  
  No primeiro passo, como q = 2 em ambas as universidades,
  Alfa admite Victor e Wilson, enquanto que Beta admite Xavier e
  Yuri, mas rejeita Zé:
  Victor (V):
  Wilson (W):
  Xavier (X):
  Yuri (Y):
  Zé (Z):
  
  A >B
  A >B
  B >A
  B >A
  ^
  B>A
  
  Alfa (A) (2 vagas):
  Beta (B) (2 vagas):
  
  V >X>Z> W
  X > Y >W>Z
  
  Os estudantes rejeitados enviam sua inscrição à sua segunda
  universidade escolhida e mais uma vez cada universidade escolhe
  as melhores q inscrições dentre as novas inscrições que recebe e
  aquelas que já estavam na turma preliminar, formando, então, uma
  nova turma e rejeitando o resto. O processo termina quando todo estudante está ou em uma turma preliminar ou foi rejeitado por todas
  as universidades que deseja. Neste ponto, todas as universidades
  admitem todos os alunos em suas turmas.
  Como Zé foi rejeitado, ele envia sua inscrição para Alfa, que
  o prefere a Wilson. Na terceira rodada, Wilson envia sua inscrição
  a Beta, mas esta também o rejeita, porque já completou sua quota
  com Xavier e Yuri, que prefere a ele.
  Por fim, não há mais envio de inscrições, de forma que o processo termina com as admissões de Victor e Zé na universidade Alfa,
  enquanto que a universidade Beta também completa suas vagas ao
  admitir Xavier e Yuri.
  Neste exemplo, nenhuma universidade permaneceu com vagas ociosas, mas isso é possível, tal qual no problema do casamento
  com poligamia.
  alocações, estabilidade e otimização  93
  
  5.2 Incertezas na prática descentralizada
  Em um mercado sem um sistema de seleção centralizado, como
  o Sisu, no Brasil, a quota de vagas de uma universidade pode não
  ser satisfeita, mesmo que a universidade aprove a mesma quantidade q de inscrições, pois não há como assumir que todos os alunos que
  são admitidos aceitarão a oferta; de fato, é incerto se um estudante enviou suas inscrições simultaneamente a outras universidades,
  como ele ordenou as universidades de sua preferência e se outras
  universidades também irão aceitá-lo, situações essas que poderiam
  afetar as escolhas do candidato.
  Por outro lado, para o estudante, o mesmo processo também é
  incerto devido à possibilidade de ele ser classificado na lista de espera de uma universidade pouco depois do último estudante contemplado dentro da quota desta universidade, o que significa que, mesmo
  ele não sendo admitido, ele pode vir a ser futuramente se ocorrer uma
  desistência.
  Em consequência de ambas as perspectivas, o cenário das admissões torna-se problemático: uma pessoa admitida em uma universidade, mas também na lista de espera de outra, que prefere,
  pode matricular-se na universidade em que é admitido e desistir
  dela se for chamado pela outra, o que introduz problemas quanto à
  vaga dele, agora disponível na primeira universidade.
  Na Seção 5.4, mesmo com sistemas centralizados, conheceremos problemas semelhantes de colapso e congestão do mercado, um
  fenômeno em que os agentes participantes não conseguem conhecer
  uns aos outros e interagir, apesar de sua disponibilidade.
  
  5.3 Semelhança e distinção com o problema do casamento
  A admissão de mais de um aluno em cada universidade pode
  ser vista como a escolha dos homens por mais de uma mulher (poligamia), através de um mecanismo em que cada universidade reparte sua capacidade de admissão em “vagas” assim como vimos,
  na Seção 2.3, os homens fazerem para cada uma de suas mulheres.
  94  aline guarnieri gubitoso | vinicius cifú lopes
  
  Assim, ao invés de pensar na universidade com capacidade
  para ingressantes, podemos considerar suas vagas A1, A2, ..., An
  como diferentes agentes, mas com preferências idênticas às de A.
  Simultaneamente, substituímos A nas listas de preferências dos estudantes pelas vagas A1, A2, ..., An, estipulando que eles preferem
  A1 > A2 > ... > An para uniformizar a escolha entre vagas equivalentes.
  Esse mecanismo foi, de fato, utilizado por Gale e Sotomayor
  em um estudo teórico (Roth, 1985, p. 282): esses autores compararam o problema de admissão e o problema do casamento formulado
  a partir dele, verificando que os emparelhamentos possíveis em um
  cenário correspondem aos emparelhamentos possíveis no outro e,
  também, que existe essa correspondência entre os emparelhamentos estáveis de um e do outro.
  Roth destacou que ainda existem os ótimos para universidades
  e para estudantes, como Gale e Shapley indicaram (Roth; Sotomayor, 1990, cor. 5.9 a respeito de hospitais e médicos residentes).
  Propriedade: Gale, Sotomayor e Roth também notaram
  que, em um mesmo cenário de listas de preferência estrita, todas as possíveis alocações estáveis compartilham as seguintes
  características:
  • Toda universidade preenche sempre o mesmo número
  de vagas.
  • Toda universidade que não completa suas vagas obtém
  sempre os mesmos estudantes.
  • Os estudantes não alocados, se houver, são sempre os
  mesmos.
  Referências: Roth; Sotomayor (1989, teos. 1 e 2; 1990, teos. 5.12 e
  5.13) e Gusfield; Irving (1989, teo. 1.6.3).
  Entretanto, como o próprio título de Roth (1985) declara, “o
  problema das admissões em universidades não é equivalente ao
  problema do casamento”. A explicação para isso requer um conceito
  adicional, o de “otimalidade fraca de Pareto”:
  Definição: Uma alocação é ótima no sentido fraco de Pareto
  para um grupo de agentes se não existe outra alocação, seja
  alocações, estabilidade e otimização  95
  
  estável ou instável, em que todos os membros desse grupo tenham alocação estritamente melhor.
  Na Seção 1.3, explicamos que o emparelhamento monogâmico conduzido pelo algoritmo de Gale-Shapley com propostas feitas
  pelos homens é ótimo para os homens, dentre os emparelhamentos estáveis, mas não o comparamos imediatamente com todos os
  possíveis emparelhamentos, inclusive os instáveis. Ainda assim, é
  possível expandir o raciocínio para mostrar que o resultado de Gale-Shapley é ótimo no sentido fraco de Pareto, ou seja, mesmo nessa comparação mais geral, em qualquer outro emparelhamento algum homem não melhora sua associação. (Roth; Sotomayor,
  1990, teo. 2.27)
  Ao desmembrar as universidades em suas vagas, tratamos cada vaga como um agente diferente. Portanto, ao aplicarmos
  Gale-Shapley, a vaga será atribuída a um estudante e, em qualquer
  tentativa de substituí-lo por outro estritamente melhor, outra vaga
  terá que abrigar um estudante de desempenho inferior ou, pelo menos, continuar com o que tem.
  Contudo, a universidade ainda pode ter interesse nessa troca, caso não se importe com qual estudante preenche qual vaga e,
  sim, com a turma ingressante formada como um todo. Roth concluiu
  que o algoritmo Gale-Shapley produz uma alocação estável entre
  universidades e estudantes, a melhor possível (dentre as estáveis)
  do ponto de vista do grupo que faz as propostas, mas não necessariamente ótima no sentido fraco de Pareto. Para vermos como isso
  ocorre, precisamos esclarecer como as universidades podem comparar turmas:
  Definição: Universidades têm preferências responsivas quando, dentre duas turmas que diferem somente pela substituição
  de um aluno por outro, preferem a turma que contém o melhor
  desses dois alunos. (Roth, 1985, p. 282; Roth, Sotomayor,
  1990, p. 128)
  
  96  aline guarnieri gubitoso | vinicius cifú lopes
  
  A fim de exemplificar essa situação, tomamos o exemplo de
  Roth (1985, p. 283), em que temos um universo de universidades
  (com a quota de cada uma entre parênteses) e estudantes, sendo
  eles: Alfa (A) (2 vagas); Best (B) (1 vaga); Century (C) (1 vaga);
  Victor (V); Wilson (W); Xavier (X); Yuri (Y), com as seguintes listas
  de preferência:
  Victor (V):
  Wilson (W):
  Xavier (X):
  Yuri (Y):
  
  C>A>B
  B>A>C
  A>C>B
  A>B>C
  
  Alfa (A) (2):
  V>W>X>Y
  Beta (B) (1):
  V>W>X>Y
  Century (C) (1): X > V > W > Y
  
  Logo, a partir destas preferências, obtemos a seguinte alocação por Gale-Shapley quando as universidades fazem as propostas:
  A (2):
  B (1):
  C (1):
  
  V>W> X > Y
  V> W >X>Y
  X> V >W>Y
  
  V:
  W:
  X:
  Y:
  
  C
  B
  A
  A
  
  >A>B
  >A>C
  >C>B
  >B>C
  
  Esse resultado é considerado ótimo (dentre os estáveis) para
  as universidades. Vemos que A está emparelhada com suas 3ª e
  4ª melhores inscrições, B e C estão cada uma com sua 2ª melhor
  inscrição, ao passo que os estudantes estão todos com sua 1ª opção
  de universidade. Em razão disso, resultaria o mesmo se os estudantes fizessem as propostas, e concluímos que se trata da única
  alocação estável.
  Contudo, podemos, manualmente, formar uma nova alocação
  em que temos:
  A (2):
  B (1):
  C (1):
  
  V> W >X> Y
  V >W>X>Y
  X >V>W>Y
  
  V:
  W:
  X:
  Y:
  
  C>A> B
  B> A >C
  A> C >B
  A >B>C
  
  alocações, estabilidade e otimização  97
  
  Dessa forma, B e C obtiveram um resultado melhor ao estarem cada uma emparelhada com o estudante que era sua 1ª escolha,
  enquanto que A também melhora, uma vez que, agora, substituiu o
  3º estudante pelo 2º, embora mantenha o 4º. (Como vimos no capítulo anterior, com Roth, 1985, p. 286, note que A poderia manipular o
  resultado e obter essa alocação como proponente, publicando a lista
  falsa de preferência W > Y > V > X.)
  Cabe citar um resultado de Roth; Sotomayor (1989, p. 567;
  1990, teo. 5.26): com preferências responsivas e estritas entre estudantes, uma universidade pode comparar estritamente as turmas
  que obteria em diferentes alocações estáveis.
  No mundo real, universidades privilegiam notas como critério
  de admissão, mas podem desejar grupos mais heterogêneos de estudantes, com diversidade de gênero, classes sociais, origem geográfica e internacionalização.
  
   Exercícios
  1) Confira que o algoritmo Gale-Shapley produz o resultado indicado conforme as listas de preferência dadas, tanto com universidades
  propondo, como com estudantes propondo.
  2) Verifique que o emparelhamento alternativo, apresentado por
  Roth, é instável.
  Resposta: O par (A,X) bloqueia a alocação, porque X >A Y e A > X C. Para satisfazê-lo,
  porém, Y teria que ir para C, o que pioraria a situação desta instituição.
  
  3) As preferências responsivas permitem comparar quaisquer duas
  turmas? Dada a lista de alunos W > X > Y > Z, compare as seis possíveis turmas de dois alunos cada.
  Resposta: Não há como comparar {W,Z} com {X,Y} (Roth, 1985, p. 285). Para que
  a preferência seja responsiva, temos somente:
  
  {W,X} > {W,Y} > {W,Z} ? {X,Y}> {X,Z} > {Y,Z}
  
  98  aline guarnieri gubitoso | vinicius cifú lopes
  
  4) Equipes sempre têm preferências responsivas?
  Resposta: Não, porque uma empresa ou clube esportivo pode procurar, para sua
  equipe, profissionais que trabalhem melhor juntos, de modo que substituir um
  membro por outro mais qualificado ainda pode prejudicar o desempenho de seu
  parceiro e da equipe.
  A teoria de alocação entre estudantes e universidades tem amplo interesse porque pode modelar também a formação de vínculo empregatício não só entre médicos residentes e hospitais, mas, em geral, entre trabalhadores e firmas. Contudo,
  é necessário incluir a questão de salários e, também, a hipótese de substitutabilidade que o exercício identifica: esse é o tema do Capítulo 6 de Roth; Sotomayor
  (1990).
  
  5.4 Casos reais: residência médica e escolas públicas
  A importância do algoritmo de Gale-Shapley e suas extensões
  é sua aplicação no mundo real. Um dos principais exemplos é a criação de um sistema de alocação de residentes em hospitais nos Estados Unidos, o NIMP (National Intern Matching Program), hoje
  chamado NRMP (National Resident Matching Program). Fazemos,
  aqui, uma apresentação do desenvolvimento desse sistema, baseada em Roth, Sotomayor (1990, p. 2-5), com detalhes extraídos dos
  artigos especializados Roth (1984) e Roth; Peranson (1999).
  Depois, citamos alguns aspectos da alocação de estudantes em escolas públicas também em cidades americanas, com
  base nos artigos da premiação Nobel: Royal Swedish Academy of
  Sciences (2012a) e (2012b).
  O mercado da residência médica
  No começo do século XX, quando as residências em hospitais
  foram instituídas como forma de pós-graduação médica, existiam
  mais vagas que candidatos, de modo que o processo de escolha dos
  residentes pelos hospitais era muito competitivo. A primeira solução encontrada pelos hospitais nos Estados Unidos, a fim de obter
  os melhores estudantes, foi adiantar cada vez mais as propostas aos
  futuros residentes.
  
  alocações, estabilidade e otimização  99
  
  Consequentemente, nos anos 40, um estudante já tinha de
  escolher onde faria sua residência dois anos antes de graduar-se
  (quando, então, faria residência). Entretanto, esta estratégia não
  era realmente favorável para nenhum dos lados, pois os hospitais
  contratavam seus futuros residentes sem ao menos saber suas notas finais (ou seja, o desempenho em aula de seus dois últimos anos
  de formação), enquanto os alunos escolhiam os hospitais e programas de residência sem terem terminado seus estudos, de modo que
  o processo de aprendizado em si ficava subordinado aos resultados
  dos programas de residência pelas propostas dos hospitais.
  Com o propósito de evitar tal situação, ajustes foram feitos pela
  Association of American Medical Colleges (AAMC), os quais determinaram que as propostas não deveriam ser feitas antes do fim do penúltimo ano de graduação, o que solucionou a situação desfavorável
  de acordos precoces.
  Não obstante, continuaram a ocorrer problemas nesse mercado, porque nem todos os candidatos rapidamente decidiam aceitar
  ou não as propostas, devido ao fato de esperarem receber propostas
  melhores ou serem chamados em alguma lista de espera em um
  hospital mais preferível. Assim, a segunda alteração empregada foi
  a diminuição do prazo que um futuro residente tinha para decidir se
  aceitava ou não uma proposta.
  Dentro dessa nova estratégia, os prazos foram cada vez mais
  reduzidos, até o momento em que, em 1950, se decidiu por um prazo
  de somente 12 horas.
  Essa solução não foi eficiente devido ao fato de que funcionava
  mais como um mecanismo de pressão por escolhas e, portanto, de
  frustação para ambos os lados, do que um mecanismo que realmente considerasse os anseios e o direito de escolha de cada agente. Dessa forma, a partir desse ano, começaram as discussões em favor da
  necessidade de implementação de um sistema centralizado para
  alocação de residentes e hospitais nos Estados Unidos. Decidiu-se
  primeiro pela adoção de um sistema centralizado de forma experimental.
  100  aline guarnieri gubitoso | vinicius cifú lopes
  
  Esse sistema constituía-se da ordenação de listas de preferência que os estudantes elaboravam quanto aos hospitais a que eles
  mandavam suas propostas, ao passo que os hospitais também ordenavam os estudantes dos quais recebiam inscrições. Tais listas de
  preferência de ambos os grupos eram, então, submetidas a um escritório central, que determinava um emparelhamento com base em
  uma simulação de alocações prioritárias entre estudantes e hospitais
  (1º com 1º, 1º com 2º etc., não produzindo resultados estáveis).
  A partir dos resultados experimentais do sistema centralizado, este começou a ocorrer de forma oficial; porém, a participação de
  estudantes e hospitais era voluntária. Entretanto, durante o experimento, o sistema já foi criticado pelos candidatos estudantes devido
  ao fato de promover alocações mais favoráveis aos interesses dos
  hospitais, em vista da ordem de alocação das prioridades, motivando os estudantes a serem “realistas” em suas preferências e identificar suas opções mais viáveis, não as mais desejadas, impondo-lhes
  um ônus contrapedagógico.
  Assim, em 1951, esse algoritmo foi substituído por um novo,
  o NIMP, muito semelhante a Gale-Shapley, embora com os hospitais no que consideramos o papel de proponentes e os estudantes
  como seletores. Seu sucesso (medido pela longevidade do processo),
  mesmo em vista disso, deveu-se à produção de alocações estáveis.
  (Roth demonstrou que esse processo é mais complicado que o de
  Gale-Shapley, ainda que acabe produzindo a mesma alocação estável; veja Roth; Sotomayor, 1990, s. 5.4.)
  Nas décadas seguintes, novos problemas apareceram. Um dos
  mais importantes, devido ao seu grande impacto no sistema, foi a
  situação conflituosa em que muitos casais de médicos não se inscreviam no sistema por desejarem estar próximos em suas alocações,
  o que tornava o processo instável em virtude do número crescente
  de estudantes (casais) e hospitais que faziam e aceitavam propostas por fora do sistema. Outro foi a dificuldade de hospitais em
  áreas rurais ou remotas obter residentes, imposta pelas preferências dos estudantes por grandes centros e inevitável, em vista da
  
  alocações, estabilidade e otimização  101
  
  propriedade que destacamos na seção anterior (as vagas não
  preenchidas são sempre as mesmas em qualquer alocação estável).
  Por isso, foi necessário incluir-se uma nova opção no sistema. Até 1982, os casais de futuros residentes puderam se inscrever
  de forma conjunta a partir de um “algoritmo de casais”. Ambos os
  membros do casal enviavam suas listas de preferências ao sistema,
  porém um deles era escolhido, por eles, como “membro líder”, de
  forma que fosse o primeiro a ser alocado pelo sistema. Seu parceiro,
  ao invés de ser emparelhado da mesma forma, tinha, então, sua
  lista de preferências editada, a fim de excluir lugares distantes da
  opção obtida pelo membro líder. Desta maneira, o segundo membro
  seria alocado à melhor possibilidade de programa de residência de
  um hospital na vizinhança da opção do parceiro “líder” no programa
  de alocação.
  Porém, uma tal alocação era provavelmente instável, porque
  o líder poderia obter uma posição boa, enquanto o parceiro acabava em uma opção ruim, ditada pela localidade (não necessariamente uma de suas melhores opções naquela localidade, já eliminadas
  também), enquanto o líder e o parceiro poderiam ser preferidos por
  outra localidade e tal alocação, para o líder, fosse perfeitamente
  aceitável, e, não, uma piora significativa.
  A partir de 1983, então, cada casal pôde indicar uma única lista de preferências de pares de hospitais. Roth e Sotomayor,
  entretanto, descobriram que um tal cenário pode não ter soluções
  estáveis; Ronn concluiu que o próprio problema é computacionalmente complexo. Para ver a instabilidade, note que, se um membro
  do casal é rejeitado no processo, ambos se movem (como casal) à
  sua próxima opção de pares de hospitais, ou seja, o outro membro
  desiste em essência da vaga que tinha e o hospital desta vaga fica
  a lamentar as rejeições que, por causa desse membro, fez a outros
  estudantes não significativamente piores.
  Nos anos 90, mudanças no financiamento do setor de saúde
  nos EUA afetaram o mercado de trabalho médico e, então, o de residência médica, fortalecendo discussões sobre o sistema de alocação.
  Duas questões foram destacadas: o privilégio dos hospitais como
  
  102  aline guarnieri gubitoso | vinicius cifú lopes
  
  grupo proponente e a possibilidade de os estudantes necessitarem
  estratégias “realistas” como grupo seletor. Para evitar um novo descrédito do programa central e a consequente desorganização crítica do mercado, propôs-se uma revisão do algoritmo. Roth e Elliott
  Peranson elaboraram o novo procedimento, que entrou em funcionamento em 1998.
  O novo algoritmo é descrito por Roth; Peranson (1999, p. 756757) e baseia-se em um algoritmo de Roth e Vande Vate para eliminar instabilidades uma a uma: muito resumidamente, trata-se de
  colocar novos candidatos em um conjunto de agentes proponentes,
  um por vez; realizar sua proposta a um hospital, que pode desencadear uma cadeia de propostas e rejeições pelos demais agentes como
  em Gale-Shapley e, também, rejeições extras de ou por casais de
  médicos ou pares de programas associados para 1º e 2º anos de residência; essas rejeições extras são armazenadas temporariamente e
  dirimidas após a cadeia principal.
  Mesmo com a mudança para estudantes como grupo proponente e o tratamento homogêneo de casais, Roth e Peranson constataram que as alocações obtidas por este método eram pouquíssimo
  diferentes daquelas pelo método anterior, então oficial, utilizando-se
  os dados de alocação de cada ano. A esse respeito, resumimos o último parágrafo da Seção A (pág. 761) e sua nota de rodapé: apesar da diferença entre as alocações ótimas para hospitais e para
  estudantes diferirem em poucos agentes, para estes, a diferença é
  substancial; por um lado, um hospital (ou universidade em geral)
  pode não ver diferença entre seus candidatos classificados até mesmo várias posições em separado, enquanto um estudante pode não
  ter uma distinção clara entre suas primeiras duas opções, mas terá,
  com certeza, entre as várias opções, por sua localização em cidades distantes etc. (Os extremos ótimos serem tão próximos indica o
  pouco número de alocações estáveis relativo ao tamanho grande do
  mercado, o que é explicado na p. 768 como resultado de cada agente
  poder entrevistar-se com e avaliar poucas opções, em vista dos custos de viagem, tempo e administração.)
  alocações, estabilidade e otimização  103
  
  As matrículas nas escolas públicas
  Dificuldades na matrícula de alunos em escolas públicas são
  uma ocorrência global. Até o começo do século XXI, os sistemas de
  alocação em várias cidades americanas sofriam problemas, enquanto tentavam alocar os alunos diretamente a suas primeiras opções
  de escola. Como se verificava em New York e Boston, a melhor estratégia do estudante era ser “realista”.
  Na cidade de New York, os alunos tinham um número limitado
  de opções de escola para indicar (cinco opções), enquanto as escolas
  decidiam quem aceitar, rejeitar ou pôr em espera também em um
  número limitado de rodadas (três rodadas), enquanto alunos e vagas
  não alocados nesse processo eram resolvidos posteriormente por um
  escritório. Desse modo, a tendência das escolas era selecionar os alunos que as indicassem em primeiro lugar, mas com o agravante de
  congestão. Mais especificamente, quantidades significativas de alunos eram matriculadas em escolas pelas quais não indicavam nenhuma preferência, enquanto as escolas não podiam considerar alunos
  suficientes durante sua seleção.
  Em Boston, um procedimento centralizado já era usado desde
  a primeira etapa, porém tentando justamente matricular os alunos
  em suas primeiras opções, depois em suas segundas opções e assim
  sucessivamente.
  Nota dos Autores: Podemos observar que a tendência em
  alocar candidatos às melhores preferências como um “princípio da prioridade” (ou “aceitação imediata”), se não embutida
  já no design do processo, será de qualquer modo muito natural para os agentes seletores (por comodidade, narcisismo
  ou receio de perder o proponente), ou mesmo para o planejador central (por intuição e por baixo custo computacional).
  Contudo, esse princípio parece conduzir mais rapidamente à
  instabilidade: cf. o histórico acima e também Roth; Sotomayor
  (1990, s. 5.5.1.1) a respeito da história da alocação de residência médica no Reino Unido.
  104  aline guarnieri gubitoso | vinicius cifú lopes
  
  Convém destacar que as preferências das escolas (ou da administração central, isto é, do sistema como um todo) pelos alunos
  podem não ser explicitamente formuladas ou considerar somente
  desempenho em notas e frequência, mas acomodar outras considerações, como proximidade da escola à residência do aluno ou irmãos
  do candidato que já estudam na escola.
  Alvin Roth e seus colegas trabalharam nos sistemas de New
  York e Boston a partir de 2003, implementando programas de matrícula baseados em Gale-Shapley com propostas realizadas pelos
  alunos, reduzindo sua necessidade de procurar por estratégias. Esses trabalhos envolvem, também, a adequação dos programas aos
  regulamentos ou normas de cada sistema.
  
  alocações, estabilidade e otimização  105
  
  6
  O problema dos
  colegas de quarto
  Nossas discussões sobre o problema do emparelhamento começaram por sua forma mais simplificada, o problema do casamento, em que se combinava cada homem a uma mulher (ou vice-versa),
  segundo as preferências de cada um. Depois, contemplamos sua
  forma generalizada no problema das admissões em universidades,
  porque, ao invés de combinar dois elementos (homens e mulheres),
  esta extensão permitia a combinação de um elemento de um grupo
  com vários de outro grupo, uma vez que cada universidade busca
  admitir uma quota de estudantes.
  Nosso próximo passo é analisar o problema dos colegas de
  quarto, mais complexo devido ao fato de que não são grupos distintos que se combinam, mas cada pessoa ordena todas as outras segundo uma ordem de preferência, de forma que qualquer uma pode
  vir a ser colega de quarto.
  Definição: Semelhantemente ao problema do casamento,
  diz-se que um emparelhamento é instável se houver duas pessoas que não estão pareadas entre si, mas que se preferem ao
  invés de seus atuais pares, de modo a formarem um par de
  bloqueio. Caso contrário, o emparelhamento é estável.
  
   107
  
   Exercício
  1) No problema de colegas de quarto, nem toda situação admite uma
  solução estável; mostre que é o caso das pessoas rotuladas como ■, 1,
  2,..., M, sendo M ímpar, com listas de preferência satisfazendo estas
  condições: ■ tem uma lista qualquer; todos os demais listam ■ em
  último lugar; cada n entre 1 e M – 1 prefere n + 1 em primeiro lugar;
  M prefere 1 em primeiro. (Note o caráter cíclico das primeiras
  preferências.)
  Resposta: Qualquer n que seja alocado a ■ prefere estar com qualquer outra pessoa, enquanto alguma delas também prefere n a seu parceiro atual, seja n – 1 (no
  caso n > 1) ou M (no caso n = 1), formando um par de bloqueio.
  
  Para descrever o procedimento de alocação nos quartos, trabalharemos com um número par de indivíduos, de modo que possam ser combinados dois a dois. Comentaremos depois a respeito
  do caso ímpar, em que um agente será deixado sozinho, e das extensões do problema. Toda a apresentação baseia-se em Gusfield;
  Irving (1989).
  
  6.1 Algoritmo para resolução
  O início do processo é semelhante ao do problema de casamento, com cada pessoa fazendo proposta à sua primeira opção de pessoa como colega de quarto. Entretanto, diferentemente da situação
  do casamento, nesta situação, todas as pessoas fazem e recebem
  propostas. Por conseguinte, torna-se necessário que algumas entradas sejam removidas, como descreveremos a seguir. Então, novas
  listas de preferência, chamadas de tabelas de preferência (atualizadas a cada nova etapa do processo), são formadas sem tais entradas.
  Dessa forma, as exclusões das entradas servem para excluir possíveis pares de bloqueio das tabelas de preferência.
  É importante ressaltar que, quando se exclui o par (X,Y),
  isto é, remove-se Y da lista de preferências de X, também é preciso
  108  aline guarnieri gubitoso | vinicius cifú lopes
  
  excluir o par (Y,X), de forma que X também seja removido da lista
  de Y. Portanto, não pode haver uma pessoa que, ao mesmo tempo
  em que esteja na lista de preferências de alguém, não o tenha em
  sua própria lista, isto é, cada membro de um possível par estável
  tem de permanecer na lista do outro membro.
  Notação e alerta: Para denotar a remoção de uma pessoa na
  lista de preferências de outra, utilizamos o símbolo ^, da seguinte forma: se D é removido da lista de preferência de A, então:
  ^
  
  A: B > C > E > F > D
  
  Aqui, isso requer que A também seja removido da lista de preferência de D:
  D: E > Â > B > C > F
  O processo chega ao fim quando se alcança uma das seguintes
  condições: (a) alguma lista de preferência se torna vazia, caso em
  que não há solução estável ou (b) cada lista é reduzida a uma única
  entrada, de modo que a associação correspondente é estável. Portanto, devido à condição (a), uma alocação de colegas de quarto a
  partir de um único grupo nem sempre admite solução estável.
  A fim de exemplificar o passo a passo desse algoritmo, resolveremos detalhadamente o exemplo enunciado com apenas alguns
  passos por Gusfield; Irving (1989, p. 171).
  Tal como nos problemas anteriores, o primeiro passo é que os
  agentes ordenem os demais participantes segundo uma ordem de preferências, porém, com a ressalva de que, nesta situação, cada agente
  tem de ordenar todos os outros. Assim, temos a seguinte tabela:
  
  alocações, estabilidade e otimização  109
  
  1:
  2:
  3:
  4:
  5:
  6:
  7:
  8:
  9:
  10:
  
  8 > 2 > 9 > 3 > 6 > 4 > 5 > 7 > 10
  4 > 3 > 8 > 9 > 5 > 1 > 10 > 6 > 7
  5 > 6 > 8 > 2 > 1> 7 > 10 > 4 > 9
  10 > 7 > 9 > 3 > 1 > 6 > 2 > 5 > 8
  7 > 4 > 10 > 8 > 2 > 6 > 3 > 1 > 9
  2 > 8 > 7 > 3 > 4 > 10 > 1 > 5 > 9
  2 > 1 > 8 > 3 > 5 > 10 > 4 > 6 > 9
  10 > 4 > 2 > 5 > 6 > 7 > 1 > 3 > 9
  6 > 7 > 2 > 5 > 10 > 3 > 4 > 8 > 1
  3>1>6>5>2>9>8>4>7
  
  Como todos os agentes começam o algoritmo livres, cada um
  deles pode e faz uma proposta à primeira pessoa de sua lista. Consequentemente, a pessoa que fez a proposta deixa de ser livre e se
  torna semicombinada àquela que recebeu sua proposta, que, por
  sua vez, ou está livre ou está semicombinada com outra pessoa, a
  primeira em sua própria lista de preferências. Portanto, a relação
  de “semicombinação” não é simétrica.
  Notação e alerta: Para denotar a semicombinação de A
  com B, utilizamos novamente a moldura ⎕ da seguinte forma
  em sua lista de preferência:
  A: B > C > E > F > D
  Isso significa que, como B é a primeira opção disponível de
  A, este propõe a ele, de forma que A está semicombinado a B.
  Porém, aqui não é necessário que B esteja semicombinado a A,
  ou seja, que A esteja emoldurado na lista de preferência de B.
  Após a formação de um par semicombinado, são removidas as
  entradas imediatamente após o proponente na lista de preferência
  do receptor, ao serem agentes menos preferíveis.
  Exemplo: Se a primeira opção de A é B, então, da lista de preferência
  de B, todas as pessoas após A devem ser removidas:
  110  aline guarnieri gubitoso | vinicius cifú lopes
  
  A:
  B:
  
  B>C>E>F>D
  ^
  E>F>A>Ĉ>D
  
  Consequentemente, B deve ser removido das listas dessas pessoas:
  C:
  D:
  
  ^
  
  E>D>F>B>A
  ^
  E>A>B>C>F
  
  De fato, ao removermos as pessoas menos preferíveis e seus
  pares correspondentes, B tem A como última opção, já que as opções posteriores foram superadas pela proposta de A. Logo, os pares
  (B,C) e (B,D) já não mais devem aparecer nas listas de B, C e D,
  devido à preferência de B por A.
  Entretanto, ao considerarmos que cada pessoa de um possível
  par estável somente pode permanecer na lista de outra pessoa se
  ela mantém essa pessoa em sua própria lista, as remoções dos pares
  têm de ocorrer imediatamente após a formação da semicombinação.
  Em vista disso, se a primeira ou uma próxima opção de uma pessoa
  for removida, quando ela for fazer a proposta, essa opção removida
  já não mais aparece em sua lista (assim como ela não aparece na
  lista dessa opção), de forma que sua proposta é diretamente feita à
  opção seguinte.
  Dessa forma, para que cada nova tabela de preferências formada seja estável, três condições devem ser respeitadas: (a) o agente, que é a primeira opção de par de uma pessoa, deve tê-la como
  última opção de par; (b) se o par (X,Y) não ocorre nas listas de X ou
  Y, então X prefere sua última opção a Y ou Y prefere sua última opção a X (de forma que este par já tenha sido removido) e (c) ninguém
  deve ter sua lista de preferência vazia.
  Apliquemos isso às listas dadas:
  1ª Rodada – propostas e remoções
  Quando 1 propõe a 8, ele fica semicombinado a 8, então removem-se os agentes que aparecem depois de 1 na lista de preferências
  alocações, estabilidade e otimização  111
  
  de 8, a saber, 3 e 9. Não devemos nos esquecer que, como 3 e 9 foram
  removidos da lista de 8, então 8 também deve ser removido das listas de 3 e 9. Logo, 1, ao ser semicombinado com 8, faz com que os
  pares (8,3), (3,8), (9,8) e (8,9) sejam removidos. Ou seja:
  1:
  3:
  8:
  9:
  
  8 > 2 > 9 > 3 > 6 > 4 > 5 > 7 > 10
  ^
  5 > 6 > 8 > 2 > 1 > 7 > 10 > 4 > 9
  10 > 4 > 2 > 5 > 6 > 7 > 1 > 3 > 9
  ^
  6 > 7 > 2 > 5 > 10 > 3 > 4 > 8 > 1
  ^
  
  ^
  
  Analogamente, 2 é semicombinado com 4 (removem-se
  5 e 8 da lista de 4 e 4 das listas de 5 e 8); 3 é semicombinado com 5
  (removem-se pares de 5 com 1 e 9); 4 é semicombinado com 10 (removem-se pares de 10 com 7); 5 é semicombinado com 7 (removem-se
  pares de 7 com 10, 4, 6 e 9); 6 é semicombinado com 2 (removem-se
  pares de 2 com 7).
  Com 7, a proposta parece um pouco diferente, pois, como se
  removeu sua primeira opção de sua lista de preferências, 2, a nova
  primeira opção de 7 é 1 (considere que as remoções ocorrem imediatamente após a formação das semicombinações), de modo que 7
  faz uma proposta a 1 e, assim, é semicombinado a ele (removem-se
  pares de 7 com 10).
  Ao continuarmos o processo de proposta, 8 faz uma proposta
  a 10, que já estava semicombinado com 4, de forma que 10 tem de
  escolher entre 4 e 8; como 8 é mais preferível que 4 em sua lista, 10
  prefere 8. Assim, 8 é semicombinado com 10 (removem-se pares de
  10 com 4 e 7, entretanto, com 7 não é necessário, pois já foi removido
  em momento anterior). Consequentemente, a semicombinação de 4
  com 10 é quebrada e 4 torna-se livre.
  Finalmente, 9 é semicombinado com 6 (não se remove pares)
  e 10 é semicombinado com 3 (removem-se pares de 3 com 4 e 10).
  Em síntese, houve as seguintes propostas:
  
  112  aline guarnieri gubitoso | vinicius cifú lopes
  
  1⇝8
  
  2⇝4
  
  3⇝5
  
  4 ⇝ 10
  5⇝7
  
  6⇝2
  
  7⇝1
  
  8 ⇝ 10
  9⇝6
  
  10 ⇝ 3
  
  Com a formação de todas as semicombinações e seus pares a
  serem removidos, a nova tabela de preferências é:
  1:
  2:
  3:
  4:
  5:
  6:
  7:
  8:
  9:
  10:
  
  8 > 2 > 9 > 3 > 6 > 4 > 5 > 7 > 10
  ^
  4 > 3 > 8 > 9 > 5 > 1 > 10 > 6 > 7
  ^
  ^
  ^
  5 > 6 > 8 > 2 > 1 > 7 > 10 > 4 > 9
  ^
  ^
  ^
  ^
  ^
  10 > 7 > 9 > 3 > 1 > 6 > 2 > 5 > 8
  ^
  ^
  ^
  7 > 4 >10 > 8 > 2 > 6 > 3 > 1 > 9
  ^
  2 > 8 > 7 > 3 > 4 > 10 > 1 > 5 > 9
  ^
  ^
  ^
  ^
  ^
  2 > 1 > 8 > 3 > 5 > 10 > 4 > 6 > 9
  ^
  ^
  ^
  10 > 4 > 2 > 5 > 6 > 7 > 1 > 3 > 9
  ^
  ^
  ^
  ^
  6 > 7 > 2 > 5 > 10 > 3 > 4 > 8 > 1
  ^
  ^
  ^
  3 >1>6>5>2>9>8>4>7
  ^
  
  ^
  
  2ª rodada – propostas e remoções
  Os agentes que ficaram livres fazem uma nova proposta à melhor opção em sua lista que ainda não foi removida, enquanto os
  demais mantêm suas propostas.
  Como somente 4 ficou livre, porque sua primeira opção recebeu uma proposta melhor, apenas ele fará uma nova proposta. Sua
  próxima opção é 9 (em vista das exclusões anteriores). Dessa forma,
  4 faz uma proposta a 9 e é semicombinado a ele. Removem-se, então, os pares (9,1) e (1,9).
  1⇝8
  2⇝4
  3⇝5
  
  4⇝9
  5⇝7
  6⇝2
  7⇝1
  
  8 ⇝ 10
  9⇝6
  
  10 ⇝ 3
  
  alocações, estabilidade e otimização  113
  
  Com a modificação da semicombinação de 4 e as remoções da
  rodada anterior já apagadas, a nova tabela de preferências é:
  1:
  2:
  3:
  4:
  5:
  6:
  7:
  8:
  9:
  10:
  
  8 >2>9>3>6>4>7
  4 > 3 > 8 > 9 > 5 > 1 > 10 > 6
  5 > 6 > 2 > 1 > 7 > 10
  9 >1 > 6 > 2
  7 > 10 > 8 > 2 > 6 > 3
  2 > 8 > 3 > 4 > 10 > 1 > 5 > 9
  1 >8>3>5
  10 > 2 > 5 > 6 > 7 > 1
  ^
  6 > 2 > 10 > 4 > 1
  3 >6>5>2>9>8
  ^
  
  (Note a exclusão de 9, 1 nas listas de 1, 9, respectivamente.)
  Esse processo continua enquanto houver alguma pessoa livre, cuja lista de preferências não esteja vazia, isto é, até que todas as pessoas façam suas propostas e fiquem semicombinadas a
  alguém, como ocorre nesta rodada em nosso exemplo.
  Se houver alguma lista de preferências vazia depois das exclusões de pares, o problema não tem solução estável (lembrando que,
  aqui, se trata de um número par de pessoas).
  Se ocorrer a existência de uma única entrada em cada lista de
  preferência, há uma única alocação estável possível entre os colegas
  de quarto, indicada pelas próprias listas. Isso porque, quando uma
  pessoa A foi removida da lista de outra B, também B foi removido
  da lista de A, então a única pessoa C na lista de A não pode ter
  removido A; pelo contrário, tem A como única entrada em sua lista,
  formando o par A – C. A estabilidade é garantida pelo mesmo raciocínio de Gale-Shapley, porque cada pessoa propôs sucessivamente
  a seu melhor candidato e só foi rejeitada quando este recebeu proposta melhor.
  Contudo, se nenhuma dessas duas situações ocorrerem, então,
  o algoritmo passa para a sua próxima fase, de que falaremos a seguir.
  
  114  aline guarnieri gubitoso | vinicius cifú lopes
  
  No seu término, novamente, as duas situações acima também são
  possíveis, com as mesmas conclusões, mas, agora, as listas de preferências são reduzidas ao excluírem-se rotações. Logo, a solução
  encontrada depende da ordem com que se eliminam as rotações.
  Definição: Rotações são ciclos que identificam as
  preferências comuns entre grupos de pessoas. Por exemplo,
  tome as listas de preferências de C e F:
  C: E > D > ...
  F: D > E > ...
  Podemos perceber que E é a primeira opção de C e a segunda
  opção de F, assim como D é a segunda opção de C e a primeira opção
  de F, formando este diagrama:
  
  Girar o diagrama 180º permuta C com F e D com E, mas preserva a orientação e o rótulo de cada flecha, daí o nome “rotação”.
  Ressaltamos que esses ciclos podem ser maiores ao abranger
  mais do que somente duas pessoas com preferências comuns, como
  veremos na segunda remoção.
  Propriedade: No exemplo da definição, como C está semicombinado a E, então C é a última entrada na lista de preferência de E, após as remoções dos passos anteriores. Como
  E consta na lista de F, também F consta na lista de E, então
  concluímos que F >E C. Caso D rejeite F, o par (F,E) passa a
  bloquear o par (C,E). Devemos, portanto, remover o par (C,E)
  e, por simetria, o par (F,D).
  
  alocações, estabilidade e otimização  115
  
  Ao observarmos a última tabela obtida, percebemos uma rotação entre as preferências de 1 e de 6, isto é, a primeira opção de
  um coincide com a segunda opção do outro e vice-versa. Assim, deve
  ser removida a primeira opção de cada pessoa, isto é, os pares (1,8)
  e (6,2), além dos seus correspondentes (8,1) e (2,6). Em consequência dessas exclusões, a primeira opção de 1 passa a ser 2 e, ao ser
  semicombinada a ela, devem ser removidos da lista de 2 os agentes
  menos preferíveis que 1, correspondendo aos pares (2,10) e (10,2)
  porque (2,6) e (6,2) já foram excluídos. Agora, porque 6 é semicombinado a 8, excluem-se também os pares (8,7) e (7,8). Efetuamos tais
  alterações na tabela:
  1:
  2:
  3:
  4:
  5:
  6:
  7:
  8:
  9:
  10:
  
  8> 2 >3>6>4>7
  ^
  ^
  4 > 3 > 8 > 9 > 5 > 1 > 10 > 6
  5 > 6 > 2 > 1 > 7 > 10
  9 >1>6>2
  7 >10 > 8 > 2 > 6 > 3
  ^
  2 > 8 > 3 > 4 > 10 > 1 > 5 > 9
  ^
  1 >8>3>5
  ^
  ^
  10 > 2 > 5 > 6 > 7 > 1
  6 > 2 > 10 > 4
  ^
  3 >6>5>2>9>8
  ^
  
  Dessa forma, uma nova tabela de preferências é formada, na
  qual a próxima rotação observada ocorre entre 3 agentes, sendo eles
  1, 9 e 10:
  
  Excluímos, então, a primeira opção de cada agente, sendo
  os pares (1,2), (9,6) e (10,3), não esquecendo seus correspondentes
  
  116  aline guarnieri gubitoso | vinicius cifú lopes
  
  (2,1), (6,9) e (3,10). Logo, 1 é agora semicombinado a 3 e precisam
  ser removidos os pares (3,7) e (7,3), porque os pares (3,10) e (10,3) já
  foram removidos, ao passo que, como 9 passa a ser semicombinado
  a 2, também são removidos os pares (2,5) e (5,2), porque os pares
  (2,1) e (1,2) já foram removidos. Já 10, por parear-se a 6, remove os
  pares (6,1), (1,6) (6,5) e (5,6), porque os pares (6,9) e (9,6) já foram
  removidos. Obtemos:
  1:
  2:
  3:
  4:
  5:
  6:
  7:
  8:
  9:
  10:
  
  2> 3 >6>4>7
  ^
  ^
  4 >3>8>9>5>1
  ^
  ^
  5 > 6 > 2 > 1 > 7 > 10
  9 >1>6>2
  ^
  ^
  7 > 10 > 8 > 2 > 6 > 3
  ^
  ^
  ^
  8 > 3 > 4 > 10 > 1 > 5 > 9
  ^
  1 >3>5
  10 > 2 > 5 > 6
  ^
  6 > 2 > 10 > 4
  ^
  3> 6 >5>9>8
  ^
  
  ^
  
  Nessa nova tabela de preferência, encontramos outra rotação,
  agora entre 1 e 2, de modo que os pares removidos são (3,1), (1,3),
  (2,4), (4,2), também (4,6) e (6,4) pela nova semicombinação 1 ⇝ 4.
  1:
  2:
  3:
  4:
  5:
  6:
  7:
  8:
  9:
  10:
  
  3> 4 >7
  ^
  4> 3 >8>9
  ^
  5 >6>2>1
  ^
  ^
  9 >1>6>2
  7 > 10 > 8 > 3
  ^
  8 > 3 > 4 > 10
  1 >5
  10 > 2 > 5 > 6
  2 > 10 > 4
  6 >5>9>8
  ^
  
  alocações, estabilidade e otimização  117
  
  A rotação subsequente envolve 3 e 10. Assim, são removidos
  (3,5), (5,3), (10,6), (6,10), mais (5,8) e (8,5) pela nova semicombinação 10 ⇝ 5.
  1:
  2:
  3:
  4:
  5:
  6:
  7:
  8:
  9:
  10:
  
  4 >7
  3 >8>9
  ^
  5> 6 >2
  9 >1
  ^
  ^
  7 > 10 > 8 > 3
  ^
  8 > 3 > 10
  1 >5
  ^
  10 > 2 > 5> 6
  2 >10 > 4
  ^
  6 > 5 > 9> 8
  
  Acima, ocorre uma rotação entre 8 e 9. Consequentemente, os
  pares (8,10), (10,8). (9,2) e (2,9) são removidos.
  1:
  2:
  3:
  4:
  5:
  
  4
  3
  6
  9
  7
  
  >7
  ^
  >8>9
  >2
  >1
  > 10
  
  6:
  7:
  8:
  9:
  10:
  
  8 >3
  1 >5
  ^
  10 > 2 > 6
  ^
  2 > 10 > 4
  ^
  5 >9>8
  
  Na nova tabela formada, ainda ocorre rotação, entre 2 e 6, de
  forma que os pares (2,3), (3,2), (6,8) e (8,6) são removidos.
  1:
  2:
  3:
  4:
  5:
  
  4 >7
  ^
  3> 8
  ^
  6 >2
  9 >1
  7 > 10
  
  6:
  7:
  8:
  9:
  10:
  
  8> 3
  1 >5
  ^
  2 >6
  10 > 4
  5 >9
  ^
  
  Por fim, percebemos uma última rotação entre 4, 7 e 10; removem-se, então, os pares (4,9), (9,4), (7,1), (1,7), (10,5) e (5,10).
  118  aline guarnieri gubitoso | vinicius cifú lopes
  
  1:
  2:
  3:
  4:
  5:
  
  4 >7
  8
  6
  ^
  9> 1
  ^
  7 > 10
  
  6:
  7:
  8:
  9:
  10:
  
  ^
  
  3
  ^
  1> 5
  2
  ^
  10 > 4
  ^
  5> 9
  
  Após as eliminações, resta apenas um agente em cada lista de
  preferência e, pelo mesmo motivo que argumentamos ao final da primeira etapa, os agentes remanescentes combinam-se aos pares de
  modo estável:
  1:
  2:
  3:
  4:
  5:
  
  4
  8
  6
  1
  7
  
  6:
  7:
  8:
  9:
  10:
  
  3
  5
  2
  10
  9
  
  Portanto, obtivemos um emparelhamento estável com os pares: 1 – 4, 2 – 8, 3 – 6, 5 – 7 e 9 – 10.
  Variantes
  Prometemos relatar como uma solução para o problema dos
  colegas de quarto deve ser procurada em três casos: um número
  ímpar de agentes; listas de preferência incompletas em vista de opções inaceitáveis; listas de preferência com indiferença. Gusfield;
  Irving (1989) explicam as adaptações necessárias em suas três Seções 4.5.1, 4.5.2, e 4.5.3, respectivamente, que resumimos aqui.
  No caso de um número ímpar de pessoas a combinar duas a
  duas, em qualquer emparelhamento alguma deverá sobrar sem colega de quarto. Convenciona-se que essa pessoa solitária ocasiona
  um bloqueio se for a preferida de uma outra com relação ao colega de quarto desta. Mostra-se que, então, em todos os emparelhamentos estáveis (se houver) para um mesmo cenário de listas de
  
  alocações, estabilidade e otimização  119
  
  preferência, a mesma pessoa permanece solitária e ela é identificada como a única cuja lista aparece vazia ao final da primeira etapa
  do algoritmo. Após sua remoção, a segunda etapa pode ser aplicada
  ao número par de agentes restantes (que determinará se uma solução estável existe ou não).
  No caso de listas incompletas, quando há soluções estáveis,
  mostra-se que cada pessoa participante ou sempre consegue algum
  colega em todos os emparelhamentos estáveis, ou sempre resta solitária, sendo que as pessoas solitárias são identificadas com suas
  listas de preferência esvaziadas após a primeira etapa do algoritmo.
  Também após a remoção destas pessoas, a segunda etapa determina a existência ou não de uma solução estável.
  Finalmente, no caso de indiferenças, podemos substituir o
  símbolo “≡” pelo símbolo “>” em cada lista e, então, proceder com
  o algoritmo. Contudo, como o problema dos colegas de quarto nem
  sempre tem solução, é concebível que uma escolha aleatória da nova
  ordem estrita entre agentes equivalentes não produza um emparelhamento estável, enquanto outra sim. Pode-se identificar todas
  essas possíveis escolhas e combiná-las, para testar cada conjunto
  de listas de preferência estrita até encontrar um que admita solução estável. Tal processo, entretanto, é muito ineficiente, porque a
  quantidade de combinações a tratar pode crescer exponencialmente
  em função do número de agentes envolvidos. Certamente pode haver uma saída mais inteligente, mas mostra-se que o próprio problema, em um sentido formal, é computacionalmente complexo.
  
  6.2 Relação com o problema do casamento
  Suponha que começamos com um problema de casamento
  entre grupos de mesmo número de homens e mulheres, com listas completas. Ao final de cada lista de preferência de um homem
  (ou mulher), acrescente os demais homens (ou mulheres, respectivamente) em uma ordem arbitrária, obtendo listas de preferência
  para um problema de colegas de quarto.
  
  120  aline guarnieri gubitoso | vinicius cifú lopes
  
  Por um lado, qualquer emparelhamento estável entre os grupos
  de homens e mulheres, como solução ao problema do casamento, também é estável como solução para esse problema de colegas de quarto:
  não há pares de bloqueio formados por um homem e uma mulher (já
  que, se existissem, bloqueariam os casamentos originais), nem pares
  formados por dois homens ou duas mulheres, porque cada membro
  foi colocado, na lista do outro, após seu parceiro.
  Por outro, não pode haver qualquer novo emparelhamento estável: se houver dois homens em um quarto e duas mulheres em
  outro, bastará formar um par qualquer com um desses homens e
  uma dessas mulheres para bloquear o emparelhamento, já que se
  preferirão entre si em relação aos colegas de quarto que vêm no
  final de suas listas.
  Assim, como sempre há uma alocação estável entre homens e
  mulheres, se realizarmos o procedimento acima, então obteremos
  um emparelhamento dentro da união dos conjuntos de homens e
  mulheres, que de fato combina homens a mulheres e é uma solução estável para o problema de casamento. Exceto por saber-se de
  antemão que o problema do casamento pode ser sempre resolvido,
  esta é uma pequena redução ao problema de colegas de quarto.
  (Gusfield; Irving, 1989, lema 4.1.1.)
  Enquanto a primeira parte do algoritmo dos colegas de quarto, referente às propostas dos indivíduos, é semelhante ao mecanismo deferred acceptance de resolução do problema do casamento, a
  segunda parte é nova, ao utilizar um outro procedimento intitulado
  minimal differences (“diferenças mínimas”).
  É esse o algoritmo responsável pela eliminação das rotações,
  que reduz as listas de preferência até que ou alguma lista se torne
  vazia, caso em que não há solução estável, ou cada lista seja reduzida a uma única entrada, de modo que a associação correspondente é
  estável. Contudo, como há várias ordens em que as rotações podem
  ser identificadas e escolhidas para serem eliminadas, o emparelhamento obtido não precisa ser único (em contraste com Gale-Shapley
  no problema do casamento). Por outro lado, as rotações ocorrem
  também no problema do casamento e são instrumentais em investigações mais avançadas.
  
  alocações, estabilidade e otimização  121
  
  7
  A matrícula em
  disciplinas na UFABC
  Siglas utilizadas:
  UFABC:
  Universidade Federal do ABC
  ConsEPE:
  Conselho de Ensino, Pesquisa e Extensão da UFABC
  CP:		
  Coeficiente de progressão no bacharelado interdisciplinar
  Coeficiente de progressão no curso de formação específica
  CPk:		
  CR:		
  Coeficiente de rendimento
  ProGrad:
  Pró-reitoria de Graduação da UFABC
  Com base em seu sucesso no cotidiano como a alocação de
  alunos em escolas, propomos aplicar o algoritmo Gale-Shapley ao
  processo de matrícula dos alunos nas disciplinas da graduação da
  Universidade Federal do ABC (UFABC). Primeiramente, devemos
  entender como o processo de alocação de cada aluno em turmas de
  várias disciplinas ocorre atualmente na instituição.
  É preciso atentar para o significado preciso dos termos disciplina e turma. A disciplina é um volume de conhecimento a ser coberto
  em um ciclo letivo e é comumente conhecida como “matéria” ou “curso”, embora um curso seja uma formação de vários ciclos e disciplinas (bacharelado, licenciatura etc.). A turma, ou “sala”, identifica o
  local, os horários, o ministrante e o grupo de alunos envolvidos nessa
  realização da disciplina.
  
   123
  
  7.1 O método contemporâneo
  Todo ano, os coordenadores dos cursos planejam as disciplinas que serão ofertadas nos três quadrimestres letivos, sendo que,
  especificamente em cada quadrimestre, eles comunicam se houve
  alguma mudança. Tais dados são lançados no sistema chamado “de
  associação”, que tem como função alimentar um outro sistema, o
  “de alocação”, o qual aloca as disciplinas ofertadas em salas de aula
  (primeiro as disciplinas que utilizam os laboratórios e, depois, as
  que ocorrem em salas). Com tal combinação, as turmas são criadas
  para, então, serem estipuladas a quantidade de vagas e horários
  que cada turma de determinada disciplina terá, segundo a escolha
  dos coordenadores de cada curso.
  Uma vez que as turmas são formadas e estabelecidas no sistema de alocação, este é vinculado a um terceiro sistema, denominado
  “de matrículas”, que, em época de matrícula (durante o quadrimestre anterior ao qual os alunos irão se matricular), libera o acesso dos
  alunos, por um tempo determinado, aos dados e turmas disponíveis
  para que esses alunos possam matricular-se nas turmas das disciplinas que desejam cursar.
  Neste sistema, as disciplinas estão organizadas em ordem alfabética segundo o bacharelado a que pertencem (interdisciplinar
  ou específico) e são listados o código, nome, turma e horário da
  disciplina, assim como o número máximo de vagas e quantos estudantes já se inscreveram nessa turma. Entretanto, um estudante
  pode escolher turmas que já têm o número máximo de inscritos,
  uma vez que o processo de escolha e eliminação é feito depois que
  todos se matricularam, de modo que a ordem de chagada não interfira na matrícula.
  Simultaneamente às matrículas que o aluno está fazendo, o
  próprio sistema verifica o número de créditos em que esse aluno
  está se matriculando, uma vez que cada aluno tem um número máximo de créditos que pode cursar de acordo com o seu CR (resolução
  ConsEPE nº 131). Além disso, o sistema verifica se, por algum
  erro, o aluno não se matriculou em horários conflitantes ou em
  
  124  aline guarnieri gubitoso | vinicius cifú lopes
  
  disciplinas iguais de turmas ou horários diferentes, de forma que,
  se algum desses conflitos ou limites forem transgredidos, o sistema
  impede a conclusão da matrícula do aluno.
  Todos os alunos podem modificar suas escolhas quantas vezes quiserem enquanto o sistema estiver aberto, porém quando o
  período de matrícula termina, o sistema não permite mais o acesso, e, consequentemente, a matrícula dos alunos. Seus pedidos de
  matrículas são, então, enviados aos coordenadores de cada curso,
  que analisam tais dados a fim de verificar a necessidade de modificações, como, por exemplo, de eliminação de turmas, aumento de
  vagas ou criação de novas turmas. Esse ajuste é informado à ProGrad, que reconfigura todos os sistemas citados anteriormente, de
  modo que as modificações sejam incluídas no sistema de matrículas.
  Nas turmas com mais matrículas do que vagas, determinam-se quais alunos têm seu pedido atendido segundo critérios específicos para cada tipo de disciplina: nas disciplinas obrigatórias dos
  bacharelados interdisciplinares (no quadrimestre ideal), aqueles
  alunos com turno de entrada correspondente e melhor CR, e, nas
  demais disciplinas, aqueles alunos com turno de entrada correspondente, reserva de vaga e melhor CPk (resolução ConsEPE nº 31).
  Assim, cada turma tem, pelo sistema, uma relação dos nomes
  dos alunos matriculados, sendo que cada um deles tem suas informações (se tem a reserva de vaga, o turno, CR, CP, dentre outros)
  analisadas pela ProGrad manualmente segundo os critérios acima.
  A partir desses dados, a ProGrad disponibiliza as matrículas
  indeferidas, isto é, disciplinas em que os alunos não conseguiram se
  matricular. Em seguida, somente os alunos com matrículas indeferidas têm acesso ao sistema de matrículas novamente, no período
  denominado “ajuste”, em que se matriculam em outras disciplinas
  ou turmas no lugar daquelas em que não conseguiram ser admitidos. Porém, as matrículas bem-sucedidas na etapa anterior continuam alocadas. Nesta etapa do processo, o critério para a aprovação
  da matrícula é a ordem de chegada.
  Depois, ocorre um segundo período de ajuste, no qual agora se
  permite o acesso de todos os alunos para que tenham a chance de, se
  
  alocações, estabilidade e otimização  125
  
  desejarem ou tiverem a necessidade, modificar alguma das turmas
  em que se matricularam. Mais uma vez, a ordem de preferência pelas vagas em cada turma é determinada pela ordem de chegada de
  cada aluno; também ocorre a inclusão de novas disciplinas criadas
  anteriormente pelos coordenadores de curso, a fim de que todos os
  alunos tenham as mesmas chances de selecioná-las. Quando esse
  sistema fecha o acesso aos alunos, encerram-se os períodos de matrícula e ajuste para o quadrimestre seguinte.
  Destacamos que a primeira matrícula dos ingressantes ocorre
  para seu segundo quadrimestre (no primeiro quadrimestre, todos os
  alunos foram inscritos pela ProGrad), ainda na vigência do primeiro
  quadrimestre, quando os alunos não possuem CP ou CR. Por isso,
  a ProGrad determina que, no sistema de matrícula, esses alunos
  tenham reserva de vagas nas disciplinas que seriam obrigatórias a
  eles em seu segundo quadrimestre. É permitido que esses alunos,
  no ajuste, também selecionem outras disciplinas.
  Antes de ser estabelecido esse método de matrícula, e como
  não havia sistema informatizado, a UFABC realizava o processo de
  matrícula manualmente, dado que eram poucos alunos e disciplinas na universidade: somente 15 turmas em 2007, comparando-se
  a aproximadamente 900 em 2014. Além disso, não era necessário
  eliminar matrículas devido à pequena quantidade de alunos.
  
  7.2 Nossa proposta
  A automação do sistema de matrícula da UFABC é um tópico de pesquisa industrial, tanto no desenvolvimento de uma solução algorítmica, como na sua implementação informatizada. Nosso
  objetivo é aproveitá-lo como exemplo das ideias que apresentamos
  neste livro e como motivação para o leitor realizar adaptações a
  suas próprias questões.
  Nesta seção, propomos um procedimento simplificado para a
  matrícula, que utiliza o algoritmo de Gale-Shapley (na versão adequada para o “problema das admissões em universidades”). Sem
  126  aline guarnieri gubitoso | vinicius cifú lopes
  
  dúvida, uma implementação experimental e desenvolvimentos posteriores poderão sanar dificuldades não consideradas aqui. Seguiremos a explanação com um exemplo diminuto.
  A proposta não contempla diversas normas da UFABC com
  respeito a reservas de vagas ou limites de carga horária, embora essas normas possam ser oportunamente observadas em um programa
  mais detalhado. A esse respeito, somente assumiremos que (a) sejam
  ofertadas vagas e turmas em número suficiente e horários compatíveis para atender à demanda regular das disciplinas e que (b) haja
  uma classificação final entre alunos, para ser utilizada como lista de
  preferência da universidade, potencialmente obtida dos coeficientes
  de rendimento e progressão e variada entre disciplinas.
  Por outro lado, fazemos uso explícito de uma distinção do
  plano pedagógico da instituição: a liberdade do aluno em cursar
  disciplinas de sua escolha e na ordem e na quantidade que quiser,
  embora haja matrizes curriculares recomendadas e requerimentos
  para a obtenção dos graus disponíveis. Enquanto é essa liberdade
  (e consequente imprevisibilidade) que torna o sistema de matrículas da UFABC um problema complexo, vemo-la também como uma
  possibilidade para sua solução.
  Nossa proposta é que o aluno especifique uma ordem de preferência entre as disciplinas que deseja cursar, podendo dar preferência a uma disciplina que necessita para colação de grau, ou a um
  conteúdo com o qual tem mais dificuldade, ou a um assunto favorito
  etc. Essa ordenação não deve ser relevante no cumprimento das matrizes ideais, conquanto haja oferta suficiente e compatível de vagas
  e horários.
  Primeira Etapa – coleta das informações dos alunos
  No período de matrícula, um formulário eletrônico deverá ser
  disponibilizado aos alunos. Após login com identificação e senha,
  será exibida uma primeira página com listas de opções, pedindo:
  “Selecione sua primeira disciplina, em ordem de prioridade”. Após a
  seleção, a página identificará as turmas oferecidas (com local, horários, ministrante etc.), pedindo: “Selecione sua 1ª opção de turma”;
  alocações, estabilidade e otimização  127
  
  “Selecione sua 2ª opção de turma”; “Selecione sua 3ª opção de turma”; ... sem limitação do número de opções.
  Concluída essa seleção, será exibida uma página semelhante,
  pedindo pela seleção da segunda disciplina e, então, as seleções das
  turmas oferecidas como 1ª opção, 2ª opção, 3ª opção etc.
  O processo será repetido para quantas disciplinas o aluno tiver interesse, bloqueando, em cada caso, a escolha de disciplinas ou
  turmas já escolhidas.
  Segunda Etapa – aplicação do algoritmo
  Para compreensão desta etapa, observamos que as disciplinas
  serão tratadas em ordem de preferência: inicialmente, a disciplina
  colocada em primeiro por cada aluno, como se ele houvesse escolhido somente essa disciplina (ainda que alunos diferentes escolham
  disciplinas diferentes), depois a disciplina colocada em segundo e
  assim por diante.
  Para n de 1 em diante:
  • listamos as opções de preferência de turma de cada aluno, referentes à sua n-ésima escolha de disciplina;
  • emparelhamos alunos e turmas segundo essas opções de preferência, segundo Gale-Shapley, com os alunos propondo às
  turmas (que têm suas listas de preferência providas pela instituição);
  • para cada aluno que tenha tido uma turma alocada, eliminamos as opções de turmas para suas disciplinas escolhidas subsequentemente – a (n + 1)-ésima, a (n + 2)-ésima etc. – cujos
  horários conflitam com o da turma alocada.
  Em vista do último passo, é importante que o aluno já escolha
  horários compatíveis entre turmas ou identifique um número suficiente de turmas para cada disciplina, para que encontre vaga em
  horário compatível.
  Note que, no primeiro passo, as vagas de uma determinada disciplina não devem ser imediatamente esgotadas, exceto se o total de
  
  128  aline guarnieri gubitoso | vinicius cifú lopes
  
  alunos (para os quais se criem vagas) já a selecione imediatamente
  como prioridade. É praticamente certo, porém, que os alunos que
  identificarem uma disciplina com mais prioridade esgotem as vagas
  das turmas mais cobiçadas dessa disciplina. Após o exemplo, relatamos outras observações.
  Exemplo: Trabalharemos com cinco alunos A, B, C, D e E; três
  disciplinas X, Y e Z; duas turmas de cada disciplina, identificadas
  com os índices D e N; cada turma com duas vagas; e dois conflitos de
  horário, XD com ZD e XN com YN.
  Por exemplo, o aluno A determina sua lista de preferência da
  seguinte forma: ele considera prioritário conseguir se matricular na
  disciplina X, da qual prefere a turma XN à turma XD. Depois, considera cursar a disciplina Z, preferindo a turma ZN à turma ZD, e, por
  fim, escolhe cursar a disciplina Y, preferindo a turma YN à turma
  YD. Sendo assim:
  A:
  
  1ª:
  2ª:
  3ª:
  
  XN > XD
  ZN > ZD
  YN > YD
  
  X:
  Z:
  Y:
  
  Enquanto isso, o aluno B, ao fazer sua própria lista, ordena
  cada disciplina de modo que escolhe como sua prioridade a disciplina X, sendo que prefere a turma XD à turma XN. Em seguida, deseja
  se matricular na disciplina Y, tendo preferência pela turma YN à
  turma YD. Sua terceira escolha de disciplina é, então, a disciplina
  Z, que prefere cursar na turma ZN e, depois, na turma ZD. Ou seja:
  B:
  
  1ª:
  2ª:
  3ª:
  
  X:
  Y:
  Z:
  
  XD > XN
  YN > YD
  ZN > ZD
  
  Dessa forma, seguem-se as listas de preferência de cada aluno
  pelas turmas ofertadas:
  alocações, estabilidade e otimização  129
  
  A:
  
  B:
  
  C:
  
  D:
  
  E:
  
  1ª:
  
  X:
  
  2ª:
  
  Z:
  
  3ª:
  
  Y:
  
  1ª:
  
  X:
  
  2ª:
  
  Y:
  
  3ª:
  
  Z:
  
  1ª:
  
  Y:
  
  2ª:
  
  X:
  
  3ª:
  
  Z:
  
  1ª:
  
  X:
  
  2ª:
  
  Z:
  
  3ª:
  
  Y:
  
  1ª:
  
  X:
  
  2ª:
  
  Y:
  
  3ª:
  
  Z:
  
  XN > XD
  ZN > ZD
  
  YN > YD
  
  XD > XN
  YN > YD
  ZN > ZD
  
  YN > YD
  
  XN > XD
  ZD > ZN
  
  XD > XN
  ZD > ZN
  
  YD > YN
  
  XD > XN
  YN > YD
  ZN > ZD
  
  Ao passo que a universidade tem sua própria classificação dos
  alunos, em conformidade com os dados de todos os alunos da instituição em determinado critério (média de notas etc.). A título de exemplo, indicamos uma classificação uniforme para todas as turmas:
  Classificação dos alunos: D > A > B > E > C
  O próximo passo é a proposta dos alunos à disciplina de sua
  primeira escolha: A, B, D, E deverão ser emparelhados com as turmas da disciplina X, enquanto C deve ser emparelhado com as turmas da disciplina Y. Formamos, então, as seguintes listas de preferência para utilizarmos o algoritmo de Gale-Shapley:
  
  130  aline guarnieri gubitoso | vinicius cifú lopes
  
  A:
  B:
  C:
  D:
  E:
  
  XN > XD
  XD > XN
  YN > YD
  
  XD > XN
  XD > XN
  
  1ª Rodada da alocação da primeira disciplina
  A ⇝ XN, B ⇝ XD, C ⇝ YN, D ⇝ XD, E ⇝ XD
  
  Com esta primeira rodada, A propõe à turma XN, que, por ter
  vagas disponíveis, aceita sua matrícula. O mesmo acontece com C,
  que propõe a YN. Entretanto, B, D e E escolhem todos propor à turma XD, de modo que, por haver mais solicitações do que vagas disponíveis, a universidade utiliza o critério de classificação dos alunos.
  Sendo assim, B e D conseguem matricular-se nesta turma, enquanto E é rejeitado na rodada:
  XD – {B, D}, XN – A, YN – C
  2ª Rodada da alocação da primeira disciplina
  E ⇝ XN
  
  Na rodada seguinte, os alunos que não foram alocados em nenhuma turma serão alocados à sua opção subsequente de turma
  preterida da primeira disciplina escolhida. Por isso, E propõe à sua
  segunda opção, a turma XN, que aceita sua matrícula por ter vagas
  disponíveis:
  XD – {B, D}, XN – {A, E}, YN – C
  Note que realizamos uma execução completa do algoritmo
  Gale-Shapley, o que finaliza a alocação nas disciplinas de prioridade
  alocações, estabilidade e otimização  131
  
  mais alta dos alunos. Durante essa execução, poderia ter havido
  “troca” de alunos em uma turma, caso uma turma já completada
  “preferisse” um aluno novo aos que já tem; isso apenas não ocorreu
  no exemplo. Porém, entre diferentes execuções, os alunos já matriculados não serão rejeitados, como veremos na última alocação.
  Agora é preciso excluir, nas listas de preferências dos alunos
  (da segunda disciplina em diante), as turmas cujos horários conflitam com a primeira turma alocada a cada aluno. Também é preciso
  diminuir o número de vagas das turmas parcialmente preenchidas
  e excluir as turmas que já estão com todas as suas vagas preenchidas (embora viole o princípio dos melhores classificados em cada
  turma). Assim, nas listas de C são excluídas as turmas XN e XD (já
  preenchidas); nas listas de D é excluída a turma ZD (em conflito com
  XD); nas listas de E é excluída a turma YN (em conflito com XN). Note
  que C, então, tem sua 2ª lista original esvaziada e substituída imediatamente pela 3ª (cf. exercício ao final do exemplo). A turma YN
  passa a ter uma única vaga, porque já tem C matriculado.
  ZN > ZD
  
  2ª:
  
  Z:
  
  3ª:
  
  Y:
  
  2ª:
  
  Y:
  
  3ª:
  
  Z:
  
  “2ª”:
  
  Z:
  
  D: 2ª:
  
  ZD > ZN
  
  Z:
  
  3ª:
  
  ZN
  
  Y:
  
  2ª:
  
  YD > YN
  
  Y:
  
  3ª:
  
  YD
  
  Z:
  
  A:
  B:
  C:
  
  E:
  
  YN > YD
  
  YN > YD
  ZN > ZD
  
  ZN > ZD
  
  Em seguida, iniciam-se as propostas dos alunos às turmas das
  segundas disciplinas escolhidas, também por Gale-Shapley, com estas listas de preferência:
  
  132  aline guarnieri gubitoso | vinicius cifú lopes
  
  A:
  B:
  
  ZN > ZD
  
  YN > YD
  
  C:
  
  ZD > ZN
  
  D:
  
  ZN
  
  E:
  
  YD
  
  Alocação da segunda disciplina
  A ⇝ ZN, B ⇝ YN, C ⇝ ZD, D ⇝ ZN, E ⇝ YD
  
  No processo de alocação da segunda disciplina, todos os alunos
  conseguem ser matriculados logo na primeira opção remanescente,
  lembrando que C, na verdade, não é matriculado na disciplina X
  que era sua segunda prioridade original. Obtemos:
  YD – E, YN – {Canterior, B}, ZD – C, ZN – {A, D}
  Com o fim da segunda etapa, é necessário que novamente sejam excluídas as opções de turmas nas disciplinas seguintes (aqui
  só havendo a terceira disciplina de cada aluno) que conflitam com
  as turmas já alocadas aos alunos ou já fechadas (sem vagas). Desse
  modo, a turma YN é excluída das listas de A e D, enquanto a turma
  ZN é excluída das listas de B e E, por não terem mais vagas disponíveis. A turma ZD passa a ter uma única vaga. O aluno C já não tem
  mais disciplinas em sua lista. Restam estas preferências:
  A:
  B:
  D:
  E:
  
  3ª:
  3ª:
  3ª:
  3ª:
  
  Y:
  Z:
  Y:
  Z:
  
  YD
  ZD
  YD
  ZD
  
  Rodadas da alocação da terceira disciplina
  A ⇝ Y D, B ⇝ Z D, D ⇝ Y D, E ⇝ Z D
  
  alocações, estabilidade e otimização  133
  
  A e D propõem a YD, mas ao haver somente uma vaga disponível
  na turma, a universidade escolhe alocar D, por ser melhor aluno segundo o critério determinado para a preferência entre os alunos. Note que
  E mantém sua vaga em YD, em detrimento de A, porque a selecionou
  anteriormente. Entre B e E a mesma situação ocorre, pois ambos
  propõem a mesma turma, ZD, que já contém C. Deste modo, por haver uma vaga disponível na turma, a universidade escolhe o melhor
  aluno B. Obtemos:
  ZD – {Canterior, B}, YD – {Eanterior, D}
  Como havia três disciplinas na lista de prioridade de cada aluno, executamos o algoritmo de Gale-Shapley três vezes e o procedimento proposto está completo. Obtivemos como resultado as seguintes alocações, que podem ser vistas em dois formatos:
  matrículas dos alunos
  
  listas de presença
  
  A – {XN, ZN};
  
  XD – {B, D};
  
  C – {YN, ZD};
  
  YD – {D, E};
  
  E – {XN, YD};
  
  ZD – {B, C};
  
  B – {XD, YN, ZD};
  
  D – {XD, YD, ZN};
  
  XN – {A, E};
  YN – {B, C};
  
  ZN – {A, D};
  
   Exercício
  1) Refaça as alocações acima sem adiantar a matrícula de C na etapa da 2ª disciplina (isto é, C não participa desta etapa e mantém
  a lista ZD > ZN para a terceria etapa) e verifique que a solução é
  alterada, tanto em sua matrícula como na dos colegas.
  Resposta: Uma vaga em ZD passa de C para E. Isso mostra que regras claras precisam ser refletidas nas especificações de um algoritmo. A alocação completa fica:
  
  134  aline guarnieri gubitoso | vinicius cifú lopes
  
  matrículas dos alunos
  A – {XN, ZN};
  B – {XD, YN, ZD};
  C – YN;
  D – {XD, YD, ZN};
  E – {XN, YD, ZD};
  
  listas de presença
  XD – {B, D};
  XN – {A, E};
  YD – {D, E};
  YN – {B, C};
  ZD – {B, E};
  ZN – {A, D};
  
  Observações: Este problema é muito semelhante ao de casais de
  estudantes na residência médica, como explicamos na Seção 5.4,
  com a consideração de que um aluno pode pleitear matrícula em
  várias disciplinas. No todo, portanto, não deve ter soluções estáveis
  e deve ser computacionalmente complexo.
  Nossa solução é a mesma adotada pelo NIMP para casais até
  1982, com a seleção de uma disciplina “líder” e outras em ordem
  de prioridade, e oferece a mesma razão para o surgimento de instabilidades: talvez uma turma considerada um pouco pior para a
  primeira disciplina tivesse horário compatível com uma turma mais
  desejada para a seguinte.
  Contudo, a solução adotada em 1983 (listas de opções conjuntas, isto é, pares de hospitais) corresponde, aqui, a pedir que os
  estudantes elaborem várias opções de grade horária (conjuntos de
  turmas). Fazê-lo a cada quadrimestre encarregaria os estudantes
  de um peso sobre-humano e poderia induzi-los a listar poucas opções, trazendo potencial congestão ao sistema.
  Uma solução preliminar, em execuções experimentais da formulação acima, seria estimular ou requerer que o aluno “em fase”
  (isto é, seguindo a matriz curricular sugerida) liste as disciplinas
  competentes em certa ordem.
  Outra, mais apropriada, pode ser o não congelamento das
  matrículas realizadas em etapas anteriores, com a aplicação do algoritmo Roth-Vande Vate para retornar a tais etapas e refazer a
  alocação dos alunos rejeitados, procurando eliminar instabilidades.
  
  alocações, estabilidade e otimização  135
  
  Antes da execução do algoritmo, vale notar, podem ser acomodadas situações de emergência, matriculando diretamente e descontando os totais de vagas nas turmas, ou remodelando as preferências da instituição.
  
  136  aline guarnieri gubitoso | vinicius cifú lopes
  
  Bibliografia
  comentada
  Na literatura acadêmica e científica, existe um padrão rigoroso de citação dos trabalhos consultados para a elaboração de um
  texto ou que o fundamentam, não bastando sua listagem em uma
  bibliografia, mas também ao longo do texto e junto às informações
  utilizadas.
  Nossa exposição evitou um excesso dessas referências formais
  para preservar o fluxo de leitura de nosso público, com o entendimento de que as técnicas utilizadas são parte da tradição matemática.
  Contudo, cumpre-nos identificar e apresentar nossas diversas fontes:
  BROWN, J.; SHERBERT, D. Introductory linear algebra with
  applications. PWS, 1984.
  Apresenta a álgebra linear, um campo da matemática universitária extremamente útil para outras teorias e para as ciências e
  engenharias. Os problemas de otimização linear e o método Simplex
  são exemplificados com boa abrangência.
  GALE, D.; SHAPLEY, L. College admissions and the stability of
  marriage. The American Mathematical Monthly, v. 69, n. 1, p. 9-15,
  1962.
  É o artigo que originou toda a teoria que apresentamos. Além
  do próprio algoritmo, ele já contém diversas informações importantes, como: os conceitos de estabilidade e otimalidade aplicados a
  emparelhamentos (p. 10); a generalização para números distintos de
  homens e mulheres (p. 13); o exemplo insolúvel de colegas de quarto
  
  alocações, estabilidade e otimização  137
  
  (p. 12); o tratamento de universidades com múltiplas vagas usando
  turmas provisórias (p. 13); e o princípio de que a otimalidade deve
  ser almejada para o grupo de estudantes, porque “as universidades
  existem para os estudantes, não o contrário” (p. 10).
  Convém citar a homenagem de Roth; Sotomayor (1990, p. 170),
  feita em vista do fato notável de que uma metodologia parecida já
  fora desenvolvida pelo NIMP vários anos antes: também Colombo
  não foi o primeiro a descobrir as Américas, mas seu mérito maior é
  de ter sido o último; assim, depois dele, a descoberta não precisou ser
  refeita mais uma vez, ao contrário, possibilitou outras realizações.
  GUBITOSO, A.; LOPES, V. Proposta para alocação dos discentes
  nas turmas de graduação da UFABC: versão 1. Technical report –
  CMCC – UFABC. Santo André: CMCC-UFABC, 2015. Disponível
  em: <http://cmcc.ufabc.edu.br/images/Pesquisa/TechnicalReports/
  TR001.pdf>. Data de depósito: 21/10/2015.
  Um “relatório técnico” é uma apresentação prévia de uma técnica ou resultado – neste caso, de nossa proposta para o problema
  das matrículas na UFABC, como discutimos no último capítulo –
  antes de sua formulação definitiva ou finalizada.
  GUSFIELD, D.; IRVING, R. The stable marriage problem:
  structure and algorithms. The MIT Press, 1989.
  É mais voltado a questões de ciência da computação, como:
  (a) a especificação de algoritmos para resolver diversos problemas e
  a determinação de sua eficiência, isto é, quantos passos os procedimentos realizam até chegar a uma solução, em função do tamanho
  do problema (como, por exemplo, número de agentes envolvidos), e
  (b) à estrutura subjacente aos problemas de emparelhamento e seu
  uso nesses algoritmos.
  Por estrutura, entendem-se conceitos como o de rotação (que
  introduzimos em nosso Capítulo 6) ou padrões reconhecidos entre
  emparelhamentos ou dentro de um emparelhamento, que permitem uma melhor descrição do problema, dos métodos e das soluções.
  
  138  aline guarnieri gubitoso | vinicius cifú lopes
  
  Por exemplo, considerando somente os problemas de casamento
  mais simples de nosso Capítulo 1, pode não ser possível comparar
  duas soluções para um mesmo conjunto de listas de preferência, se
  um homem melhora enquanto outro piora de situação, mas ambas
  compartilham um emparelhamento melhor (cada homem recebe a
  esposa que julga melhor dentre as das duas soluções) e outro pior
  (cada homem recebe a pior esposa dentre as duas), formando um
  diagrama de emparelhamentos estáveis chamado reticulado. Esse
  reticulado pode ser usado para vários problemas de determinação e
  contagem de soluções com propriedades específicas.
  KNUTH, D. Stable marriage and its relation to other combinatorial
  problems: an introduction to the mathematical analysis of
  algorithms. American Mathematical Society, 1997.
  O autor serviu-se do problema de emparelhamento e do algoritmo Gale-Shapley como excelente motivação para ministrar uma
  série de aulas sobre a ciência da computação, seus assuntos, métodos e questões em aberto. É boa leitura para o estudante que deseja
  seguir carreira na área, bastando-lhe os conhecimentos universitários iniciais.
  Logo em sua pág. 5, Knuth acaba por oferecer um pequeno
  exemplo de uma regra inestimável: é preciso cuidado com definições
  semelhantes, mas não equivalentes, utilizadas para um mesmo termo por autores variados e com objetivos específicos. De fato, Knuth
  afirma que emparelhamentos estáveis nem sempre existem quando
  as listas de preferência são incompletas, dando este conjunto (com
  outros rótulos) como exemplo:
  A: X
  B: Z > X > Y
  C: Z > X
  
  X: C > A > B
  Y: B > A > C
  Z: A > B > C
  
  Por um lado, seguindo nossas convenções para listas incompletas e o algoritmo de Gale-Shapley, obtemos o emparelhamento
  B – Z, C – X, restando A, Y solteiros, que é estável. Por outro, Knuth
  
  alocações, estabilidade e otimização  139
  
  requer uma bijeção total entre os conjuntos {A, B, C} e {X, Y, Z} e
  nota só haver um único tal emparelhamento, consistindo de A – X,
  B – Y e C – Z, que não é estável porque é bloqueado pelo par (B,Z).
  LINS, M.; CALÔBA, G. Programação linear: com aplicações em
  teoria dos jogos e avaliação de desempenho (data envelopment
  analysis). Interciência, 2006.
  É uma referência lusófona e detalhada para a programação
  linear e o método Simplex.
  ROTH, A. The evolution of the labor market for medical interns
  and residents: a case study in game theory. Journal of Political
  Economy, v. 92, n. 6, p. 991-1016, 1984.
  ______. The college admissions problem is not equivalent to the
  marriage problem. Journal of Economic Theory, v. 36, p. 277-288,
  1985.
  ROTH, A.; PERANSON, E. The redesign of the matching market
  for american physicians: some engineering aspects of economic design. The American Economic Review, v. 89, n. 4, p. 748-780, 1999.
  ROTH, A.; SOTOMAYOR, M. The college admissions problem
  revisited. Econometrica, v. 57, n. 3, p. 559-570, 1989.
  Esses quatro artigos, assim como Gale; Shapley (1962), são
  publicações acadêmicas, isto é, textos de apresentação formal de
  pesquisa científica enviados a periódicos especializados que os submeteram a uma revisão por outro especialista, isto é, os trabalhos
  foram conferidos quanto a seu rigor e veracidade.
  ______. Two-sided matching: a study in game-theoretic modeling
  and analysis. Cambridge University Press, 1990.
  Este livro organiza e aglutina os resultados anteriores dos
  autores, assim como de Gale e Shapley e outros colegas, publicados em diversos artigos científicos, a fim de prover uma exposição
  
  140  aline guarnieri gubitoso | vinicius cifú lopes
  
  unificada. Tornou-se, portanto, uma referência para conhecimento
  e estudo na área de alocações. Além dos problemas de casamento
  e de admissão em universidades, o livro incorpora estudos sobre o
  conceito de “núcleo”, mercados com precificação e leilões, alocações
  de firmas e trabalhadores e de compradores e vendedores.
  ROYAL SWEDISH ACADEMY OF SCIENCES. The prize in
  economic sciences 2012: information for the public: stable matching:
  theory, evidence, and practical design. 2012a. Disponível em: <http://
  www.nobelprize.org/nobel_prizes/economics/laureates/2012/popular-economicsciences2012.pdf>. Acesso em: 08/04/2014.
  Certamente, todo ano, quando anunciados os agraciados com
  os prêmios Nobel, há grande interesse do público mundial em saber
  de suas carreiras e contribuições. A Academia Sueca, responsável
  pela outorga dos prêmios, prepara essa divulgação para satisfazer
  nossa curiosidade.
  A apresentação explica também que o prêmio de 2012 a
  Shapley e Roth reconhece todo o trabalho de suas carreiras, não
  apenas a pesquisa a respeito de emparelhamentos. Por exemplo,
  Shapley e colegas também desenvolveram um algoritmo para permitir trocas entre agentes de unidades indivisíveis de um recurso,
  com um procedimento distinto do de Gale-Shapley, mas com a mesma noção de estabilidade. Esse procedimento depois foi visto como
  adequado para transplantes de rins, em que a “preferência” de um
  paciente por um rim é expressa por sua compatibilidade.
  ROYAL SWEDISH ACADEMY OF SCIENCES. Scientific background
  on the Sveriges Riksbank Prize in economic sciences in memory of
  Alfred Nobel 2012: stable allocations and the practice of market
  design: compiled by the economic sciences prize committee of the Royal Swedish Academy of Sciences. 2012b. Disponível em: <http://www.
  nobelprize.org/nobel_prizes/economics/laureates/2012/advanced
  -economicsciences2012.pdf>. Acesso em: 08/04/2014.
  A Academia Sueca também prepara uma apresentação científica da outorga, como um retrato das contribuições feitas e seus
  alocações, estabilidade e otimização  141
  
  desdobramentos. Assim como indicamos Knuth (1997) para o estudante que ingressa na ciência da computação, este survey é leitura importante para aquele que se inicia nas ciências econômicas
  enquanto alude a diversos temas importantes. Contém resultados
  recentes e uma bibliografia técnica representativa.
  
  142  aline guarnieri gubitoso | vinicius cifú lopes
  
  