Emparellamentos Estables: Algoritmo de Gale-Shapley

Traballo Fin de Grao Emparellamentos Estables: Algoritmo de Gale-Shapley Uxío García Andrade Xullo, 2022 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Emparellamentos Estables: Algoritmo de Gale-Shapley Uxío García Andrade Xullo, 2022 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA iii iv Traballo proposto Área de Coñecemento: Estatística e Investigación Operativa Título: Emparellamentos Estables: Algoritmo de Gale-Shapley Breve descrición do contido O obxecto de estudo deste TFG será o problema de atopar un emparellamento estable entre dous conxuntos de elementos de igual tamaño, onde cada elemento dun conxunto ten unha orde de preferencias sobre os elementos do outro conxunto. Un emparellamento é simplemente unha bixección entre os elementos de ambos conxuntos. Un emparellamento A é estable se non existe ningunha parella (α,β), distinta ás propostas polo emparellamento, coa propiedade de que tanto αcomo βse prefiren mutuamente fronte ás súas respectivas parellas baixo o emparellamento A. O principal obxectivo deste traballo será introducir o algoritmo de Gale e Shapley, introducido formalmente en 1962, e estudar as súas propiedades matemáticas. O problema do emparellamento estable recibiu unha gran atención da comunidade científica polas súas múltiples aplicacións en distintos ámbitos: asignación de estudantes a colexios, de médicos a hospitais,... Recomendacións Non hai ningunha recomendación en particular. Outras observacións Non hai ningunha observación. Índice Resumo viii Introdución xi 1. Algoritmos de Emparellamento 1 2. Algoritmo de Gale-Shapley 5 2.1. Caso Particular: Matrimonio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1. Propiedades de Gale-Shapley para o problema do matrimonio . . . . . . . 9 2.2. Extensión: Admisión a universidades . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1. Propiedades de Gale-Shapley para o problema das admisións a universidades 14 3. Estudo Numérico Gale-Shapley 17 3.1. Xeración dos conxuntos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2. Resultados........................................ 18 3.2.1. Satisfacción emparellamentos . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.2. Eficiencia de Gale-Shapley . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4. Mecanismo Xeral de Subasta 25 4.1. Introdución ao mecanismo xeral de subasta . . . . . . . . . . . . . . . . . . . . . 32 4.2. Algoritmo........................................ 33 4.2.1. Invariantes ................................... 38 v vi ÍNDICE 5. Estudo numérico mecanismo xeral de subasta 45 5.1. Exemploinicial:..................................... 45 5.2. Xeracióndedatos.................................... 51 5.3. Resultados........................................ 51 5.3.1. Calidade dos emparellamentos . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.3.2. Eficiencia do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 A. Código do estudo numérico de Gale-Shapley 1 A.1. Xeración dos conxuntos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 A.2.Códigodosalgoritmos ................................. 2 A.3. Código para a realización do experimento . . . . . . . . . . . . . . . . . . . . . . 4 B. Código do estudo numérico do mecanismo xeral de subasta 5 B.1. Código para a xeración dos datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Bibliografía 21 2 1. Algoritmos de Emparellamento Definición 1.8 (Emparellamento).Unha asignación ou emparellamento Aé un conxunto de pares ordenados (n, m), onde n∈Nem∈M, de tal xeito que cada n∈Naparece como moito nunha parella de A, e cada m∈Maparece como moito nunha parella de A. Definición 1.9. Unha asignación Aentre un conxunto NeMdirase perfecta se |N|=|M|= |A|. Definición 1.10. Unha asignación Adirase que é inestable se existen dous elementos A, B ∈N que foron asignados a α, β ∈Mrespectivamente, a pesar de que A≻βBeβ≻Aα, é dicir, β prefire a A antes que a B, e Apefire a βantes que a α. Unha representación gráfica dunha asignación inestable amósase na figura 1.1. Figura 1.1: Exemplo de asignación inestable. Definición 1.11. Unha asignación Adirase estable se non é inestable. Definición 1.12. Estratexia. En teoría de xogos, a estratexia dun xogador é o plan das acción que pode escoller nunha situación na que a saída non depende unicamente das súas accións, senón das accións dos demais xogadores tamén. No referido a emparellamentos estables, a estratexia dun elemento v∈V(G)será a súa orde de preferencia {≻v}v, polo que, nalgún caso usaranse os dous termos indistintamente. 3 Definición 1.13. Un algoritmo de emparellamento dirase a proba de estratexias ou non manipulable se un individuo non ten ningún incentivo para non presentar a súa orde de preferencias reais. De non contar con esta propiedade, un individuo podería conseguir un resultado mais favorable modificando a súa orde de preferencia. 4 1. Algoritmos de Emparellamento Capítulo 2 Algoritmo de Gale-Shapley Ao longo deste capítulo describirase a teoría e as propiedades do algoritmo de Gale-Shapley, introducido polos autores homónimos en 1962 [1]. Comenzaremos centrándonos nun caso particular que permite simplificar e introducir o algoritmo dun xeito mais intuitivo, facilitando a posterior descrición do caso xeral. 2.1. Caso Particular: Matrimonio Antes de introducir o algoritmo que resolve o caso xeral das admisións á universidade, é conveniente estudar un caso particular. Este caso sería o de que o número de estudantes e universidades fose o mesmo, e todas as cuotas fosen unitarias. Téndese a estudar este caso dentro do seguinte contexto: supoñamos que existe unha comunidade na que temos nhomes e nmulleres, onde cada persoa conta cunha lista na que ordea a cada individuo do xénero oposto segundo as súas preferencias. O obxectivo será o de obter unha asignación de xeito que cada persoa poida casar con outra de tal forma que non exista ningunha outra asignación na que existe un casamento que melloraría a satisfacción global. Para visualizar claramente este problema, introducirase a continuación un exemplo: Exemplo 2.1. Na figura 2.1 detállase a matriz de preferencias de emparellamentos para tres homes, α,βeγ, e tres mulleres, A, B e C. Nesta matriz, o valor que aparece debaixo da columna de home, será a preferencia que o home que está nesa columna lle asigna á muller á que lle corresponde esa fila. Deste xeito, teriamos, por exemplo, para o home α, a súa orde de preferencias sería C≻αA≻αB. Coa notación introducida no capítulo exterior, as ordes de preferencias serían as seguintes: 5 6 2. Algoritmo de Gale-Shapley Figura 2.1: Matriz de preferencias. Homes: ≻α:=C, A, B ≻β:=B, C, A ≻γ:=A, B, C Mulleres: ≻A:=β, α, γ ≻B:=α, γ, β ≻C:=γ, β, α Existen 6 combinacións posibles de matrimonios posibles, dos cales 3 son estables 3 son inestables. Un exemplo de combinación estable sería o caso no que cada home casase coa súa primeira elección, é dicir, a asignación sería a seguinte: A= (α, C),(β, B),(γ, A). Deste xeito, cada muller obtería o home que está na última posición na súa orde de preferencias, pero seguiría sendo estable, posto que non existe ningunha posibilidade de que os homes estean mais satisfeitos, xa que todos teñen a súa primeira elección. As outras dúas posibilidades de asignacións estables serían asignar a cada muller a súa primeira elección, ou asignar a cada persoa a súa segunda elección (a segunda elección coincide para homes e para mulleres). Por outra parte, é posible comprobar rapidamente como o resto de asignacións son inestables. Tómese como exemplo a seguinte asignación: A= (α, C),(β, A),(γ, B). No caso de αeβ, temos que A≻αCeC≻βA, pero o emparellamento é (α, C),(β, A). Teorema 2.2 (Gale-Shapley).Sexa H=h1, ..., hnun conxunto de nhomes, e M=m1, ..., mn un conxunto de nmulleres, sempre existe unha asignación estable de casamentos. Demostración. A demostración deste teorema realizarase a partir da definición dun procedemento iterativo, cuxo pseudocódigo se pode ver na figura 2.1, coñecido tamén polo nome de algoritmo de aceptación diferida. Neste caso, supoñerase que os homes son os que propoñen matrimonio ás mulleres, pero a inversa sería equivalente e funcionaría do mesmo xeito. Iteración 0: Antes de comezar a parte iterativa do algoritmo, deberán resolverse as preferencias que non son estrictas. É dicir, se mi=hkmj,1≤i, j, k ≤n,i=j, será preciso resolver este empate 2.1. Caso Particular: Matrimonio 7 dalgún xeito. Tipicamente, estes resolveranse ordeando os empates alfabeticamente, pero os tipos de estratexias son moi variados, escolléndose ás veces a resolución de conflitos aleatoria. Iteración 1: a. Todo home hi,i∈1, ..., n, propón matrimonio á súa muller preferida, é dicir, a Ohi,1. b. Toda muller mi,i∈1, ..., n, acepta a proposta do home que mais alto estea na súa orde de preferencia, e rexeita o resto. Iteración k: a. Todo home hi,i∈1, ..., n rexeitado no paso k−1realiza unha nova proposta a Ohi,j, j∈1, ..., n, sendo j o menor índice tal que Ohi,j aínda non rexeitase a hi. b. Toda muller mimantén a súa oferta preferida ata o momento, é dicir, Omi,j, sendo j o menor índice tal que Omi,j fixo unha proposta a mi.mirexeita o resto de propostas. Finalización: Se nunha iteración non hai ningunha nova proposta, obtense a asignación emparellando a cada muller coa proposta que manteña. Seguindo este algoritmo, teremos que que todas as mulleres terán, polo menos, unha proposta, xa que, de non ser así, teremos que haberá polo menos 2 homes, hiehj,j, i ≤n, j =ique terán realizado unha proposta á mesma muller mk,k≤n. Non obstante, como non é posible que se produzan empates na orde de preferencia debido á resolución dos mesmos realizada no paso 0, terase que hi≻mkhjou hj≻mkhi, polo que mkrexeitará unha das propostas e o algoritmo procederá a realizar outra iteración. Por outra parte, vexamos agora como a asignación producida a partir deste algoritmo será estable. Sexa Aesta asignación e sexa un emparellamento (hi, mj)∈A. Supoñamos que existe outra muller mk, tal que mk≻himj. Deste xeito, o home hienvioulle unha proposta á muller mknunha iteración previa a mj. Como finalmente non foi emparellado con mk, isto quere dicir que mkrexeitou a súa proposta por outro home hltal que hl≻mkhi, polo que non se pode dar unha inestabilidade no algoritmo. 1Inicializar propostas para cada muller m a baleiro 2do 3m :=cada home h envía unha proposta ámuller m que mais alta estea na lista e aínda non lla enviase antes 4if a muller m ten mais dunha proposta then 5m :=a muller m rexeita todas as propostas menos a do home h, que éo que mais alto está na súa lista 6end if 7while apareza algunha nova proposta 8devolver a asignación de cada muller co home que enviase a proposta que segue mantendo Código 2.1: Pseudocódigo do algoritmo de aceptación diferida. 8 2. Algoritmo de Gale-Shapley Exemplo 2.3. Vexamos agora como se aplicaría Gale-Shapley ao seguinte exemplo: Sexan 4 homes H={α, β, γ, δ}e sexan 4 mulleres M={A, B, C, D}, coas seguintes ordes de preferencias: Homes: ≻α:=A, B, C, D ≻β:=A, D, C, B ≻γ:=B, A, C, D ≻δ:=D, B, C, A Mulleres: ≻A:=δ, γ, α, β ≻B:=β, δ, α, γ ≻C:=δ, α, β, γ ≻D:=γ, β, α, δ Unha execución normal do algoritmo sería o seguinte: Iteración 0: As ordes de preferencia son todas estrictas, polo que non será preciso resolver empates. Iteración 1: a. A recibe propostas de αeβ. B recibe proposta de γ. D recibe proposta de δ. b. A única muller que recibe varias propostas é A, que rexeita β, xa que α≻A β. Iteración 2: a. O único home rexeitado no paso 1 foi β, que lle enviará unha proposta a Oβ,2= D. b. D conta con dúas propostas, rexeita δ, xa que β≻Dδ. Iteración 3: a. O único home rexeitado no paso 2 foi δ, que lle enviará unha proposta a Oδ,2= B. b. B conta con dúas propostas, rexeita γ, xa que δ≻Bγ. Iteración 4: a. O único home rexeitado no paso 3 foi γ, que lle enviará unha proposta a Oγ,2= A. b. A conta con dúas propostas, rexeita α, xa que γ≻Aα. Iteración 5: a. O único home rexeitado no paso 4 foi α, que lle enviará unha proposta a Oα,2= 2.1. Caso Particular: Matrimonio 9 B. b. B conta con dúas propostas, rexeita α, xa que δ≻Bα. Iteración 6: a. O único home rexeitado no paso 5 foi α, que lle enviará unha proposta a Oα,3= C. b. Non hai ningunha muller con mais dunha proposta, non se produce ningún rexeitamento. Finalización: Na iteración 6 non se produciu ningún rexeitamento, polo que non haberá novas propostas e o algoritmo finaliza. Polo tanto, a asignación final será S= (α, C),(β, D),(γ, A),(δ, D). É facilmente comprobable que esta asignación será estable. 2.1.1. Propiedades de Gale-Shapley para o problema do matrimonio Nesta subsección presentaranse as principais propiedades matemáticas que presenta o algoritmo de Gale-Shapley. Entre elas, as mais desexables e que fixeron que o algoritmo tivese cabida en distintas aplicacións son a de optimalidade da solución obtida e a de que a estratexia sexa non manipulable. De novo, as propiedades desexadas neste apartado estarán asociadas aos homes, o grupo que realiza as propostas nesta versión, pero tamén serían válidas no caso de que fosen as mulleres as que realizan as propostas. Non obstante, as distintas propiedades non se verificarán para o grupo que recibe as propostas, podendo, por exemplo, dar lugar a situacións nas que unha muller se beneficie de non aportar a súa orde de preferencia real, como veremos posteriormente. Teorema 2.4. O algoritmo de Gale-Shapley remata en, como moito n2−2n+ 2 iteracións, despois de realizarse n2−n+ 1 propostas. Demostración. Por unha banda, temos que o algoritmo parará cando nunha iteración non se realice ningunha proposta. Deste xeito, teremos que, no peor caso, un dos homes hiterá realizado npropostas, sendo emparellado finalmente coa muller que se atopa no último lugar da súa orde de preferencias, Ohi,n. Pola contra, o resto dos n−1homes poderán realizar unha proposta, como moito, n−1veces, xa que, senon, a asignación non sería estable. Deste xeito, o número total de propostas virá dado por: (n−1)(n−1) + n=n2−2n+ 1 = n2−n+ 1. 10 2. Algoritmo de Gale-Shapley Do mesmo xeito, para o número de iteracións, haberá que ter en conta que sempre será preciso 1 iteración inicial, na que realizan niteracións. Nas iteracións sucesivas, no peor caso, realizarase só 1 proposta, que será no caso no que só 1 home sexa rexeitado. Deste xeito, teremos que o número máximo de iteracións será o mesmo que o de propostas realizadas, restándolle as propostas da iteración inicial. Deste xeito, o número total de iteracións será: (n2−n+ 1) −(n−1) = n2−2n+ 2. Teorema 2.5. Optimalidade. O algoritmo de Gale-Shapley é óptimo para os homes. Isto é, a asignación estable Aproducida polo algoritmo é tal que non existe outra asignación estable A′ na que, dado un home he dúas mulleres m, m′, tal que (h, m)∈A(h, m′)∈A′em′≻hm. É dicir, non existirá outra asignación estable na que un home estea emparellado a unha muller que prefira antes que á que foi emparellado na asignación producida polo algoritmo de Gale-Shapley. Demostración. Supoñamos que un home hé emparellado na asignación producida por GaleShapley A cunha muller m,(h, m)∈Aque non sexa a mellor parella posible. Sexa m′a mellor parella posible e sexa. En GS, os homes realizan as súas propostas en orde decrecente, polo que, nalgunha iteración, existirá un primeiro home hserá rexeitado pola primeira muller m′da súa orde de preferencia. Unha vez que hé rexeitado por m′,m′aceptará a proposta doutro home h′, polo que teremos que: h′≻m′h. (2.1) Supoñamos que exista outra asignación A′tal que (h′, m)∈A′. O home h′aínda non foi rexeitado por ningunha muller no momento no que se produce o rexeitamento de m′ah, xa que se trata do primeiro rexeitamento. Deste xeito, h′aínda non lle tería enviado a proposta a m′cando lle envía a proposta a m′, polo que: m′≻h′m. (2.2) Polo tanto, teremos a asignación A′tal que (h′, m)∈A′, pero, por 2.1 e 2.2, esta asignación non será estable, polo que temos unha contradición. Pola contra, cabe plantexarse como de óptimo é o emparellamento producido para a parte que acepta as propostas. Como veremos a continuación, o emparellamento non só non será óptimo pola súa parte, senon que será pésimo. 2.1. Caso Particular: Matrimonio 11 Proposición 2.6. O emparellamento producido por Gale-Shapley é pésimo (o peor posible dentro dos emparellamentos estables) para as mulleres. Demostración. Sexan dous homes heh′e dúas mulleres mem′. Supoñamos que mé emparellada con hnunha asignación A, pero hnon é a peor parella posible para m. Entón existe unha asignación estable A′na que hestá emparellada con h′, home que lle gusta menos que h,h≻mh′. Sexa m′a parella de hen A′. Como sabemos polo teorema anterior que este emparellamento é óptimo para os homes, temos que m′ ≻hm. Deste xeito, mehprefirense entre eles antes que as súas parellas en A′, polo que A′non pode ser un emparellamento estable. Teorema 2.7. O algoritmo de Gale-Shapley é a proba de manipulacións de estratexias por parte dos homes, de xeito que un home non pode manipular a súa orde de preferencias de xeito que isto lle beneficie. Do mesmo modo, tamén contará coa propiedade de ser a proba de manipulacións grupais de estratexias por parte dos homes, de xeito que non é posible que un conxunto de homes coordine unha manipulación das súas ordes de preferencias de xeito que estes todos se vexan modificados. Si que será posible, non obstante, que algúns deles acaben cunha parella mellor, mentres que o resto manteñan a mesma parella. Demostración. Por unha banda, a demostración da proba da non manipulabilidade de estratexias para homes é trivial a partir da optimalidade da solución. O algoritmo asegura que o resultado será o mellor posible para cada home, polo que cambiar a súa orde de preferencias só poderá levar a un peor emparellamento. Do mesmo xeito, calquera manipulación por parte dun grupo levará a un emparellamento peor para algúns dos elementos do grupo, xa que, debido á característica de optimalidade, a única opción de que o emparellamento resultante fose mellor sería que fose inestable, o que sería unha contradición. De novo, plantexámonos a dúbida de se esta propiedade de ser a proba de manipulacións tamén é compartida pola parte que acepta as propostas. Neste caso, a resposta volve a ser negativa. Proposición 2.8. O algoritmo de Gale-Shapley non é a proba de manipulacións para as mulleres. Demostración. Sexan 3 homes h1, h2eh3e 3 mulleres m1, m2em3coas seguintes preferencias: ≻h1:=m2, m1, m3 ≻h2:=m2, m3, m1 ≻h3:=m3, m2, m1 ≻m1:=h2, h1, h3 ≻m2:=h3, h2, h1 ≻m3:=h1, h2, h3. No caso de que todo o mundo aporte as súas preferencias reais, o algoritmo de Gale-Shapley rematará coa asignación A={(h1, m1),(h2, m2),(h3, m3)}. Non obstante, se a muller m2modifica as 18 3. Estudo Numérico Gale-Shapley intercambiar as posicións dos elementos presentes no índice no que se atopa a iteración e no índice xerado aleatoriamente. Deste xeito, sexa a función xeradora de números naturais aleatorios nun intervalo [0, l], l ∈N: U:N−→ N. E sexa a función que intercambia as posicións na orde de preferencia: f:N×N−→ N×N (n1, n2)7−→ (n2, n1). Polo que o algoritmo procederá do seguinte xeito: ∀j∈n, ..., 1k:=U(n), f(Ohi,j, Ohi,k). O algoritmo de Fihser-Yates proporciona unha permutación aleatoria sen sesgo sempre que o xerador de números aleatorios tampouco sexa sesgado, condición que se verifica neste caso. O código empregado para a xeración dos conxuntos de datos pode revisarse no código A.1. 3.2. Resultados 3.2.1. Satisfacción emparellamentos O primeiro aspecto a estudar será a satisfacción dos emparellamentos. Para iso, será preciso definir unha función que, dado un emparellamento A, proporcione unha medida de como de contento está cada individuo coa súa respectiva parella. A definición desta función poderá realizarse desde enfoques distintos, pero a que se usará neste estudo, creada explicitamente para este caso de uso, caracterízase pola súa facilidade de interpretación. Sexa sdita función: s:N×N×N−→ R (u, v, n)7−→ (n−Iu,v −1) (n−1) . Por outra parte, tamén precisaremos algunha liña base coa que comparar os resultados obtidos co algoritmo de Gale-Shapley. As seguintes funcións de emparellamento foron usadas para esta comparación: Emparellamento aleatorio: esta función xerará os emparellamentos de xeito aleatorio, facendo uso do algoritmo de Fisher-Yates descrito previamente para producir unha permutación que dea lugar ao emparellamento. 3.2. Resultados 19 Emparellamento heurístico: esta función basearase en asignar a cada un dos homes, por orde do seu índice, a muller dispoñible que mais alta estea na súa lista. É dicir, sexa Ha función que, para un home dado, obteña a muller coa que será emparellado: H:N×N×N× −→ N (h, A)7−→ Oh,i,m´ın i:∀(h′, m)∈A, m =Oh,i. Deste xeito, como xa se indicou previamente, realizáronse 1000 iteracións para distintos tamaños de problemas, obtendo os resultados presentes na figura 3.1. Tamén se incluiu outra gráfica con escala logarítmica na figura 3.2, para poder visualizar correctamente os valores de satisfacción para valores de npequenos. Como era de esperar, o emparellamento aleatorio é o que menos Figura 3.1: Comparación da satisfacción xeral cos emparellamentos nos distintos algoritmos a considerar. satisfacción xeral produce, posto que en ningún momento se teñen en conta as preferencias para cada individuo. Por outra parte, tamén é posible comprobar o correcto funcionamento do algoritmo Gale-Shapley, posto que supera a calquera dos outros 2 algoritmos para calquera tamaño do problema. Vexamos agora a comparación da satisfacción para cada unha das partes. En primeiro lugar, 20 3. Estudo Numérico Gale-Shapley Figura 3.2: Comparación da satisfacción xeral cos emparellamentos nos distintos algoritmos a considerar en escala logarítmica. comezaremos cos homes que, como xa vimos previamente, son os que contan coa característica de obter un emparellamento óptimo dentro das asignacións estables. Por outra banda, o algoritmo heurístico sabemos que está baseado exclusivamente na satisfacción dos homes, polo que un podería pensar que esta heurística podería chegar a superar a Gale-Shapley nesta métrica. Estes resultados poden verse na figura 3.3. A continuación, revisaremos a satisfacción das mulleres nos distintos emparellamentos. Como xa se describiu previamente, Gale-Shapley non asegura a optimalidade da asignación para o grupo que acepta as propostas. Do mesmo xeito, a heurística céntrase só nas preferencias dos homes, polo que a satisfacción das mulleres será practicamente a mesma que no caso do algoritmo aleatorio. Estes resultados amósanse na figura 3.4. Finalmente, comprobouse a optimalidade do emparellamento en Gale-Shapley. Como ben sabemos, esta optimalidade só está presente para os homes, e non as mulleres. Deste xeito, cabe esperar que a satisfacción dos homes sexa superior á das mulleres en Gale-Shapley, como se pode observar na figura 3.5. A satisfacción das mulleres é en torno a un 85% inferior á dos homes para os distintos tamaños de problema. 3.2. Resultados 21 Figura 3.3: Comparación da satisfacción dos homes cos emparellamentos nos distintos algoritmos a considerar. Figura 3.4: Comparación da satisfacción das mulleres cos emparellamentos nos distintos algoritmos a considerar. 22 3. Estudo Numérico Gale-Shapley Figura 3.5: Comparación entre a satisfacción dos homes e das mulleres en Gale-Shapley. 3.2.2. Eficiencia de Gale-Shapley Neste apartado estudarase a eficiencia do algoritmo de Gale-Shapley. En particular, estudarase o número de iteracións realizadas ata a finalización do algoritmo para os distintos n, o que permitirá determinar a súa complexidade computacional. A figura 3.6 representa con puntos o número de iteracións realizadas nas distintas repeticións do algoritmo en escala logarítmica. Por outra parte, engadiuse a cota superior teórica do número de iteracións n2−2n+ 2 que non só non se supera en ningunha ocasión, senon que non están cerca. Neste sentido, tamén se incluíu unha regresión lineal que pretende representar a tendencia do número de iteracións a medida que o tamaño do problema aumenta. O código relacionado coa implementación dos algoritmos está presente no código A.2, mentres que o script usado para executar todo o experimento pode observarse no código A.3. 3.2. Resultados 23 Figura 3.6: Número de iteracións realizadas para distintos tamaños de problema. 24 3. Estudo Numérico Gale-Shapley Capítulo 4 Mecanismo Xeral de Subasta Neste capítulo cubrirase unha das aplicacións mais recentes de Gale-Shapley: o desenvolvemento dun mecanismo xeral de subasta para anuncios en motores de búsqueda [6], desenvolvido e posto en práctica por Google. A publicidade en Internet en xeral, e os anuncios en motores de búsqueda en particular, son casos claros de mercados con dúas partes diferenciadas, xa que temos anunciantes (postores) que compiten por ocos nos que colocar so seus anuncios. Por norma xeral, estes ocos terán valores distintos asignados polos postores, xa que as primeiras posicións terán un maior valor que as que aparezan mais abaixo, debido a que canto mais arriba estea un oco maior será a probabilidade de que un usuario faga click nese anuncio. Un exemplo de subastas nun motor de búsqueda amósase na figura 4.1. Estes mercados son do mesmo tipo aos descritos previamente, como o caso dos alumnos e as universidades. Polo tanto, non é ningunha sorpresa que algúns dos mecanismos empregados estean basados ou relacionados co algoritmo de Gale-Shapley. Este é o caso do mecanismo descrito neste capítulo, que combinará devandito algoritmo e o mecanismo de asignación de Shapley e Shubik [7], que segue os principios de Gale-Shapley, pero incorpora unha variable que representa o valor que unha das partes obtén ao ser emparellada con outra, ademais de permitir pagos entre individuos. Antes de nada, procederase a describir un mecanismo típico de subasta de múltiples obxectos con puxas seladas, é dicir, onde os oferentes presentan as súas puxas sen coñecer as puxas do resto de participantes (tradicionalmente facíase por escrito). Isto permitiranos entender mellor a teoría de subastas, ademais de estudar os primeiros intentos de buscar o mellor mecanismo de subastas posibles. Definición 4.1 (Subasta).Sexan npostores e kobxectos tal que n>k. Cada postor conta cun 25 26 4. Mecanismo Xeral de Subasta Figura 4.1: Exemplo de ocos de anuncios que son subastados nunha búsqueda no motor de búsqueda Google. valor vij ≥0∀i∈ {1, ..., n}, j ∈ {1, ..., k}que lle asigna a cada un dos obxectos, aínda que é frecuente atopar subastas nas que os obxectos son iguais, polo que se usará a notación vipara abreviar. Por outra parte, o vendedor pode definir un prezo de reserva rij ≥0∀i∈ {1, ..., n}, j ∈ {1, ..., k}, que será o prezo mínimo polo que lle estará disposto a vender o obxecto jao postor i. De novo, o máis frecuente será que o prezo de reserva sexa equivalente para todos os postores, polo que se abreviará coa notación rjpara algúns dos exemplos previos, aínda que este non será o caso para o algoritmo que se describirá ao longo do capítulo. Finalmente, cada postor iindicará a súa puxa mij polo obxecto j,mij < vij, que tamén pode ser visto como o máximo prezo que está disposto a pagar polo obxecto j. Unha vez contamos con estes datos de entrada, que son os que as dúas partes poden controlar, poderanse definir outros dous parámetros. Por unha parte, defínese pij coma o prezo que o postor i paga polo obxecto j. Este dependerá principalmente das puxas realizadas mij, e, dado un obxecto j, o seu valor será 0 para calquera postor que non gañase a puxa por ese obxecto. Do mesmo xeito, temos a utilidade uij que un postor iobtén a partir do obxecto j. A utilidade pode representar diversos conceptos, sendo o beneficio obtido a partir do obxecto un dos seus significados máis comúns. Finalmente, a subasta contará cunha asignación A, que será un grupo de pares ordeados (i, j)i∈ {1, ..., n}, j ∈ {1, ..., k}que representará que o obxecto jfoi adxudicado ao postor i. 27 A partir dos mecanismos de Gale-Shapley e Shapley-Shubik desenvolvéronse varios mecanismos de subasta, entre os que destacan dous: GSP (Segundo prezo de puxa xeral) [8] e VCG (Vickrey–Clarke–Groves) [9]. Estes dous mecanismos e as súas variacións son as bases das subastas en Internet modernas, establecéndose na maioría de motores de búsquedas tras desbancar ao seu predecesor, a subasta baseada no primeiro prezo de puxa. Esta asignaba cada oco ao postor que maior puxa presentase, cobrando un prezo igual á puxa do postor gañador. O problema con este tipo de subastas de primeiro prezo de puxa é que non presentaban equilibrio en estratexias puras (en teoría de xogos, as estratexias puras son aquelas que proporcionan unha definición completa das accións que toma un xogador, como é o caso), é dicir, non existe un perfil de estratexia tal que cada unha delas é mellor que as restantes. Polo tanto, as puxas poden ser axustadas de xeito dinámico dependendo do resto de postores, de posuir esta información previo envío das puxas. Esencialmente, podemos entender esta característica como a de manipulacións de estratexias en Gale-Shapley, introducida no capítulo 2. Na práctica, isto tradúcese en que o gañador i, de saber o resto de puxas (en particular da puxa do segundo postor jque mais ofreceu), podería modificar a súa puxa para que fose da forma mi=mj+ϵ∀ϵ > 0, para poder maximizar a súa utilidade. GSP xurdiu como primeira alternativa, contando cun procedemento moi semellante ao seu predecesor, pero cada postor coa kpuxa mais alta pagará o prezo correspondente á puxa do postor k+ 1. É dicir, o postor que mais ofreceu por un oco non pagará un prezo equivalente á súa puxa, senon que dependerá do ofrecido na segunda puxa mais alta. Non obstante, este tipo de subastas tampouco é a proba de manipulación de estratexias para subastas nas que o número de obxectos é superior a 1, xa que os postores poden modificar as súas puxas para obter uns mellores resultados, como se verá no exemplo a continuación. Para poder ilustrar o exemplo, introducirase brevemente a definición do mecanismo do GSP, en particular no contexto no que se usa nas subastas de anuncios, que posteriormente se verá que garda semellanzas co mecanismo cuberto neste apartado. Sexan npostores e kocos. Neste caso todos os ocos consideraranse iguais, polo que cada postor determinará un valor e prezo máximo xeral, e só será no prezo no que se terá en conta a probabilidade de que un usuario faga click nese oco para distinguir os ocos. Cada postor iasigna un valor por click vi, así como o máximo prezo que está disposto a pagar mi, que será a súa puxa. Cada postor pagará un prezo por click pise gana a puxa, mentres que ese prezo será 0 se a perde. Finalmente, αjé o número de clicks que un oco recibe por unidade de tempo. A partir destes datos, definirase a utilidade uobtida por un postor iao que se lle asigna o oco icomo ui=αi(vi−pi). Exemplo 4.2. Sexan n= 3 postores e k= 2 ocos. O primeiro oco recibe 100 clicks por hora, mentres que o segundo recibe 50, é dicir, α1= 100, α2= 80. Os valores asignados polos postores son os seguintes: v1= 10, v2= 7, v3= 2. Por outra parte, supoñamos que os prezos máximos dispostos a pagar son os mesmos que o valor, é dicir, m1=v1= 10, m2=v2= 7, m3=v3= 2, 34 4. Mecanismo Xeral de Subasta Figura 4.2: Un emparellamento será estable sempre que un postor i∈Ie un oco j∈Jteñan respectivamente unha utilidade uie un prezo pjtal que as coordenadas (pj, ui)son tales que o punto está fóra da área de cor azul. 4.2. Algoritmo 35 A continuación presentaranse as definicións dos conceptos asociados ao procedemento iterativo que se presentará posteriormente. Definición 4.13. (Grafo de actualización). Dada unha subasta (v, m, r)o grafo de actualización para unha asignación (u, p, µ)é un multigrafo bipartito direccionado, no que µ∈I×J∪ {j0}, sendo j0o oco simulado. Este grafo conta con 5 tipos de aristas: para cada postor ie para cada oco j∈Jtemos que: Existe unha aresta cara adiante dende iata jse pj∈[rij, mij]. O seu peso asociado será ui+pj−vij. Como se verá posteriormente, este tipo de aresta irase creando a medida que os prezos se vaian actualizando segundo os emparellamentos. Existe unha aresta cara atrás dende jata ise (i, j)∈µ. O seu peso asociado será vij −ui−pj. O grafo de actualización non conta con ningunha destas arestas nun primeiro momento, senon que se irán engadindo segundo se engadan emparellamentos en cada iteración. Existe unha aresta de prezo de reserva dende iata jse ui+rij > vij emij > rij. O seu peso asociado será de ui+rij −vij. Este tipo de aresta correspóndese aos emparellamentos nos que o postor está interesado no oco e a súa utilidade é suficiente para asegurarse de que o emparellamento non será bloqueante. Existe unha aresta de prezo de máximo dende iata jse ui+mij > vij emij > rij. O seu peso asociado será de ui+mij −vij. Este tipo de aresta correspóndese aos emparellamentos nos que o postor está interesado no oco e a utilidade asociada á asignación é suficiente para exceder a diferenza entre prezo máximo e o seu valor. No caso de seguir unha estratexia de optimizar ganancias, estas arestas estarán presentes sempre que o postor teña unha utilidade positiva. Existe unha aresta terminal dende iata j0se ui>0. O seu peso asociado será de ui. Todo postor con utilidade positiva contará con este tipo de aresta. Definición 4.14. (Camiño alternado). Un camiño alternado P no grafo de actualización é unha n-tupla (i0, j1, i1, j2, ..., il, jl+1). Comeza cun postor non asignado i0cunha utilidade ui0>0, e segue cunha secuencia de arestas cara adiante e arestas cara atrás, de forma que os elementos da tupla sexan, alternativamente, postores e ocos. Finalmente, o último oco debe ser engadido a partir dunha aresta de prezo de reserva, de prezo máximo ou terminal. Todos os vértices deben de ser distintos, exceptuando o último, que pode aparecer mais dunha vez. Definición 4.15. O peso w(P)dun camiño alternado defínese como a suma dos pesos das súas arestas. 36 4. Mecanismo Xeral de Subasta Definición 4.16. Sexa i0un postor e sexa yun vértice calquera dun grafo de actualización G. Defínese a distancia d(i0, y)como o número de vértices percorridos em G dende i0ata yusando exclusivamente arestas cara adiante e cara atrás. Se non é posible alcanzar o vértice ydende i0, a distancia será ∞. Definición 4.17 (Posición xeral).Unha subasta (v, m, r)esta en posición xeral se, para cada postor i, non existen 2 camiños alternados no grafo de actualización que empecen no postor i, sigan unha serie de arestas cara adiante e cara atrás e rematen nunha aresta de prezo de reserva, prezo máximo ou terminal e teñan o mesmo peso. Nota: Usarase a notación G(t)en distintos elementos da subasta para facer referencia á iteración t. Inicialización. Sexa unha subasta (v, m, r)de npostores e kocos. O algoritmo comeza cunha asignación baleira (u0, p0, µ0), onde cada un dos elementos é inicializado do seguinte xeito: u(0) i=B∀i∈I, sendo B > max{vij |(i, j)∈I×J}. p(0) j= 0 ∀j∈J. µ(0) =∅. Iteración t: Sexa (ut, pt, µt)unha asignación e Gto grafo de actualización correspondente á iteración t do algoritmo Asignación Estable. A iteración tdo algoritmo consistirá nos seguintes pasos. 1. Buscar o camiño alternado de custe mínimo P de Gt. No caso de non existir ningún camiño alternado, o algoritmo detense e devolve a asignación (u(t), p(t), µ(t)). Sexa w(t)(P)o peso asociado aPe sexa P= (i0, j1, i1, j2, i2, ..., jl, il, jl+1)para un l≥0. 2. Calculase o vector de distancias d(t)∈Rn+ktal como se indica en 4.16. É posible usar o algoritmo de Dijkstra para calcular este vector de distancias, xa que, por definición, todas as arestas do grafo de actualización serán non negativas. Do mesmo xeito, os vértices que non están emparellados só poden ser alcanzados desde i0, o vértice desde o que se están a calcular as distancias, polo que só haberá, como moito, 2kvértices alcanzables en cada iteración. Por iso, como Dijkstra ten un custe computacional igual ao cadrado dos vértices alcanzables, sabemos que a complexidade deste paso será O(k2). 3. Calculase o novo vector de utilidades: u(t+1) i=u(t) i−m´ax(w(t)(P)−d(i0, i),0) ∀i∈I. (4.11) 4.2. Algoritmo 37 4. Calculase o novo vector de prezos: p(t+1) j=p(t) j−m´ax(w(t)(P)−d(i0, j),0) ∀j∈J. (4.12) No caso de que a última aresta de Psexa do tipo prezo de reserva, o prezo do último oco jl+1 virá dado por p(t+1) l+1 = m´ax(p(t+1), riljl+1 ). 5. Finalmente, actualízase a asignación µ(t)ao longo de P para obter a nova asignación µ(t+1). Distinguimos 3 casos dependendo da natureza do tipo de aresta final: Aresta terminal: se P acaba nunha aresta terminal, temos que jl+1 =j0, é dicir, é o oco simulado. Desta forma, emparéllase cada postor ixco oco jx+1 ∀x∈ {0,1, ..., l −1}. O postor ilqueda desemparellado. Aresta de prezo máximo: considéranse dous subcasos. Caso 1 jl+1 =jlO caso é equivalente ao da aresta terminal. Caso 2 jl+1 =jlA asignación mantense igual, µ(t)=µ(t+1). Aresta de prezo de reserva: considéranse tres subcasos. Caso 1 ∄i: (i, jl+1)∈µ(t). ∀x∈ {0, ..., l}, emparellar o postor ixco oco jx+1. Caso 2 ∃i: (i, jl+1)∈µ(t)eriljl+1 ≤p(t+1) jl+1 Neste caso, a asignación mantense igual µ(t)=µ(t+1). Caso 3 ∃il+1 : (il+1, jl+1)∈µ(t)eriljl+1 > p(t+1) jl+1 . Se Pé un camiño tal que Pnon visita jl+1 dúas veces, eliminarase o emparellamento, de xeito que (il+1, jl+1)/∈µ(t+1). A continuación, emparéllanse o resto de postores e ocos de P do mesmo xeito que o visto para o caso de arestas termianis. Se Pvisita jl+1 dúas veces, teremos que jl+1 =jdpara algún d∈ {1, ..., l −1}. Deste xeito, os elementos finais de Pforman un ciclo con polo menos 2 postores e 2 ocos. Polo tanto, simplemente se procederá a emparellar os elementos de P a partir do índice d, é dicir, procedese a emparellar ixcon jx+1 para x∈ {d, d + 1, ..., l}. Unha vez o introducido, veranse algunhas das propiedades coas que conta este algoritmo. En primeiro lugar, demostraranse unha serie de invariantes que permitirán derivar as propiedades que o algoritmo descrito presenta. 38 4. Mecanismo Xeral de Subasta 4.2.1. Invariantes (A1) A asignación (u(t), p(t), µ(t))xerada na iteración té estable para a subasta (v, m, r). (A2) ∀(i, j)∈µ(t),u(t) iep(t) jverifican as condicións de asignación factible. (A3) pj= 0 ∀j∈J:∄i∈I(i, j)∈µ. (B1) mij ≥0eu(t) i+mij =vij ⇒(i, j)/∈µ(t). (B2) mij ≥0eu(t) i+rij =vij ⇒(i, j)∈µ(t)ou p(t) j≥rij. Demostracións dos invariantes. Todos os invariantes poden ser demostrados por indución, como se verá a continuación. Comenzaranse demostrando os invariantes (B1) e (B2), xa que se usarán nas demostracións de (A1), (A2) e (A3). Demostración (B1). Caso base, t= 0. Trivial, non existe ningún emparellamento. Caso t+1. Sexa iun postor interesado no oco jtal que non están emparellados, (i, j)/∈µ(t). Temos que mij ≥0eu(t+1) i+mij =vij. No algoritmo só é posible emparellar un oco e un postor se estes están presentes nun camiño alternado de xeito consecutivo. Á súa vez, para que isto ocorra será preciso que exista unha aresta que una os dous vértices. Vexamos que, nas condicións deste caso, non existe aresta de ningún dos tipos: Aresta terminal. jnon é o oco simulado, polo que non pode existir unha aresta deste tipo. Aresta de prezo máximo. Unha das condicións necesarias para este tipo de arestas é u(t+1) i+mij > vij. Como temos que u(t+1) i+mij =vij, non se pode dar esta aresta. Aresta de prezo de reserva. mij > rij eu(t+1) i+mij =vij ⇒u(t+1) i+rij < vij, polo que non se pode dar esta aresta. Aresta cara atrás. Trivial, xa que (i, j)/∈µ. Aresta cara adiante. Veremos que, no caso de darse esta aresta, tería peso negativo. Para darse esta aresta, ten que darse que pj∈[rij, mij). En particular, pj< mij. Pola condición u(t+1) i+mij =vij, temos que u(t+1) i−vij =−mij. Polo tanto, o seu peso asociado sería ui+pj−vij =pj−mij <0, xa que 0≤pj< mij. Deste xeito, non existe ningunha aresta entre i e j e (i, j)/∈µ(t+1). Demostración (B2). 4.2. Algoritmo 39 Caso base, t= 0. Trivial, non se dan as condicións en ningún debido ao vector de utilidades u(0) i∀i∈I. Caso t+ 1. Se a parella de postor e oco xa fose emparellada nalgunha iteración anterior xa se verificaría, posto que (i, j)∈µ(t)⇒(i, j)∈µ(t+1). Se (i, j)/∈µ(t), sería preciso distinguir 2 casos: Caso u(t) i+ri,j =vi,j. Por hipótese de indución, como (i, j)/∈µ(t), entón temos que se verifica p(t) j≥ri,j. Como p(t+1) j≥p(t) j, as condicións do lema estarían satisfeitas. Caso u(t) i+ri,j =vi,j. Como u(t+1) i≤u(t) i, temos que a desigualdade sería u(t) i+ri,j ≥ vi,j. Do mesmo xeito, combinando coa actualización da utilidade, teriamos u(t) i−w(t)(P) + d(t)(i0, i) + rij =vij, polo que, combinado coa desigualdade anterior, conclúese que w(t)(P)> d(t)(i0, i), isto é, existirá algunha aresta dende iata algún oco, e esta non será a única presente no camiño, posto que non é igual ao peso. Así mesmo, nas condicións dadas, existiría unha aresta de prezo de reserva dende iata j. De ser esta a aresta final do camiño alternado, teriamos que (i, j)serían emparellados, seguindo o procedemento de actualización da asignación para camiños alternados de prezo de reserva. Demostración (A1). Caso base, t= 0. Como u(0) i=B∀i∈Iep(0) j= 0 ∀j∈J. Deste xeito, teremos que ui+pj=B+ 0 ≥vi,j, polo que se verifica (3). Caso t+ 1. Considéranse 3 casos distintos para cada emparellamento (i, j): Caso 1: p(t) j∈[ri,j, mi,j].(u(t), p(t), µ(t))é estable pola hipótese de indución, polo que u(t) i+p(t) j≥vi,j. Neste caso preséntanse 2 posibilidades: Se d(t)(io, i)≥w(t)(P), a utilidade non se actualizará debido á fórmula do paso 3 do algoritmo, polo que u(t+1) i) = u(t) iep(t+1) j≥p(t) j, polo que se verifica 4.8. Por outra parte, se d(t)(io, i)< w(t)(P), a utilidade e o prezo actualizaranse segundo as fórmulas descritas no algoritmo: u(t+1) i=u(t) i−(w(t)(P)−d(t)(io, i)). p(t+1) j=p(t) j−(w(t)(P)−d(t)(io, j)). Ademais, como existe unha aresta cara adiante dende iata j, temos que d(t)(io, j)≤d(t)(io, i)+(u(t) i+p(t) j)−vi,j. 40 4. Mecanismo Xeral de Subasta Polo tanto, susituindo en 4.8 u(t+1) i+p(t+1) j≥u(t) i−w(t)(P) + d(t)(io, i) + p(t) j+w(t)(P)−d(t)(io, i)−u(t) i−p(t) j+vij =vij ≥vij. Caso 2: p(t) j≥mij. A condición 4.9 verifícase trivialmente. Caso 3: p(t) j< rij eiestá interesado en j.u(t) ié estable pola hipótese de indución, polo que u(t) iverifica 4.10. Distínguense 2 opcións aquí: Se d(t)(io, i)≥w(t)(P), a utilidade non se actualizará debido á fórmula do paso 3 do algoritmo, polo que u(t+1) i=u(t) ieu(t+1) isatisfai 4.10. Se d(t)(io, i)≥w(t)(P), entón u(t+1) i=u(t) i−(w(t)(P)−d(t)(io, i)), mentres que, grazas á aresta de prezo de reserva de i aj, temos que w(t)(P)≤d(t)(io, i)+(u(t) i+p(t) j)−vij, polo que, sustituindo, en (5), vemos que u(t) i)tamén a satisfai. A presenza da aresta de prezo de reserva pódese obter grazas ás invariantes (B1) e (B2). Demostración (A2). Caso base, t= 0. Trivial, a inicialización faise de tal xeito que p(0) j= 0 ∀j∈J. Caso t+1. Tal e como se pode ver na actualización dos prezos (paso 4 do algoritmo), temos que p(t+1) ≥p(t). Sexa emparellamento (i, j)∈G(t), no que existe unha aresta cara atrás dende jata i. Pola hipótese de indución, (u(t), p(t), µ(t))satisfai (A2), polo que, debido á definición de aresta cara atrás, esta terá peso 0, e d(t)(io, i) = d(t)(io, j). (Demostración A3). Caso base, t= 0. Trivial, p(0) j= 0 ∀j∈J. Caso t+ 1: Como sabemos polo paso 4 do algoritmo, p(t+1) ≥p(t). Os ocos emparellados en µ(t)tamén estarán emparellados en µ(t+1). Do mesmo xeito, como o emparellamento é realizado a través dun camiño alternado, no que, salvo a última aresta, o resto son cara adiante ou cara atrás, como moito emparellarase 1 oco novo, que non estaba emparellado antes. Vexamos que o resto dos ocos non se poden alcanzar dende o postor inicial i0dun camiño 4.2. Algoritmo 41 alternado Pen G(t). Para calquera oco jnon emparellado en t+1, por hipótese de indución, p(t)= 0. Do mesmo xeito, ∀i∈I, ri,j >0debido á suposición de posición xeral, polo que non existe aresta cara adiante en jepj= 0. Lema 4.18. A asignación (u(t), p(t), µ(t))obtida polo algoritmo Asignación Estable é factible e estable. Demostración. O invariante (A1) asegura a estabilidade da asignación. As condicións 4.6 e 4.7 da factibilidade veñen dadas do invariante (A2). Como o algoritmo remata cando non existen mais camiños alternados, a utilidade será u(t) i= 0 para todo postor non emparellado, xa que, de non ser así, existiría un camiño alternado debido á aresta terminal dende iata j0. Lema 4.19. O algoritmo Asignación Estable remata en, como moito, n(2k+ 1) iteracións. Demostración. Na iteración inicial, o grafo de actualización G(0) ten, como moito, nk arestas de reserva, nk arestas de prezo máximo e narestas de prezo terminal. Veremos como, en cada iteración, o número de arestas vese reducida nunha unidade. Sexa unha iteración tdo algoritmo Asignación estable. Vexamos que, dado un camiño alternado P= (i0, j1, i1, ..., jl, il, jl+1), a aresta (i, j)=(il, il+1)non aparecerá no grafo de actualización G(t+1). Separamos agora en casos: Caso 1: Se (i, j)é unha aresta terminal, entón w(t)(P) = d(t)(i0, i) + u(t) i, polo que u(t+1) i= u(t+1) i−(w(t)(P)−d(t)(i0, i)) = 0. Caso 2: Se (i, j)é unha aresta de prezo máximo, entón w(t)(P) = d(t)(i0, i)+(u(t) i+mij −vij), polo que u(t+1) i+mij =u(t) i−(w(t)(P) = d(t)(i0, i)) + mij =vij. Caso 3: Se (i, j)é unha aresta de prezo máximo, entón w(t)(P) = d(t)(i0, i)+(u(t) i+rij −vij), polo que u(t+1) i+rij =u(t) i−(w(t)(P) = d(t)(i0, i)) + rij =vij. Como as utilidades non aumentan e os prezos non se ven reducidos en ningunha parte do algoritmo, a aresta (i, j)non volverá aparecer en ningunha iteración ˆ t>t. Deste xeito, teremos que o algoritmo rematará, como moito, en nk +nk +n=n(2k+ 1) iteracións. Lema 4.20. Sexa (v, m, r)unha subasta en posición xeral, e sexa (u′, p′, µ′)unha asignación factible e estable. Para calquera iteración t do algoritmo Asignación Estable, teremos que u′ i≤u(t) i ∀i∈Iep′ j≥p(t) j∀j∈J. 42 4. Mecanismo Xeral de Subasta Demostración. Esta demostración, de caracter técnico, non se incluirá debido á súa extensión, pero poderá consultarse en [6]. Teorema 4.21. Se unha subasta (v, m, r)está en posición xeral, terá un emparellamento estable óptimo para os postores único. Este emparellamento pode ser atopado cunha complexidade computacional de O(nk3). Demostración. Sexa unha subasta (v, m, r)en posición xeral. O algoritmo Asignación Estable producirá como resultado un emparellamento (u′, p′, µ′), que é estable e factible polo lema 4.18. Aplicando o lema 4.20 ao emparellamento anterior despois da última iteración do algoritmo implica que u′, v′, µ′é preferido a calquera asignación estable por calquera postor, polo que será óptimo para os postores. Por outra parte, temos que o número máximo de iteracións será n(2k+ 1) polo lema 4.19. Por outra parte, grazas a que os pesos do grafo de actualización son non negativos, é posible usar Dijkstra para calcular as distancias, que ten unha complexidade computacional de O(k2), sendo k o número de vértices. Deste xeito, como o Dijkstra se usa en cada unha das iteracións, e para o cálculo da complexidade computacional elimínanse as constantes, teremos que esta será O(nk3). Finalmente, revisarase a manipulabilidade de estratexias por parte dos postores. En particular, probarase un resultado en torno á manipulación de estratexias, tanto para postores individuais como grupos, de xeito similar á que xa se viu previamente para Gale-Shapley. Lema 4.22 (Lema de Hwang).Sexa (u, p, µ)unha asignación factible para unha subasta (v, m, r) en posición xeral, e sexa (u∗, p∗, µ∗)a asignación óptima para os postores para esa subasta. Definimos ˆ I={i∈I|ui> u∗ i}. Se ˆ I=∅, entón existirá un par bloqueante (i, j)∈(I\ˆ I)×J. Demostración. De novo, a demostración deste lema será fundamentalmente técnica, separando en casos e empregando técnicas semellantes ás doutras demostracións xa detalladas, polo que non se incluirá nesta memoria. Esta pode consultarse en [6]. Teorema 4.23. Non é posible que un postor ou unha agrupación de postores manipulen as súas puxas de xeito que cada postor na agrupación se beneficie de xeito estricto da manipulación. Demostración. Sexa unha agrupación de postores ˆ Ique pretenden beneficiarse de mentir coas súas preferencias. Sexa a tripla (v, m, r)a subasta que representa as preferencias reais para todos os postores, e sexa a tripla (ˆv, ˆm, r)a subasta que representa as puxas modificadas polo grupo ˆ I. 4.2. Algoritmo 43 Nótese que os prezos de reserva son os mesmos, xa que non son controlados polos postores, eˆvi=vi,ˆmi=mi∀i /∈ˆ I. Sexa (u, p, µ)a asignación óptima para os postores na subasta (ˆv, ˆm, r), que será factible, xa que as restricións de factibilidade son as mesmas para as dúas subastas no caso de que i∈I\ˆ I, mentres que, para i∈ˆ I, teremos que verificar que pj≤mij para todo (i, j)∈µ. Isto é directo, xa que, de non darse, (ˆv, ˆm, r)non sería óptimo para os postores, xa que sempre haberá outro emparellamento no que non se excedan os prezos máximos e sexa óptimo para os postores. Como (u, p, µ)é factible, é posible usar o lema 4.22. Deste xeito, temos que existe un par (i, j)∈(I\ˆ I)×Jque sexa bloqueante para a subastas (v, m, r). 50 5. Estudo numérico mecanismo xeral de subasta 3. u(6) = (6.0,7.0,1.0). 4. p(6) = (2.0,0.0). 5. Trátase do caso de prezo de reserva. Como o oco j1si que está emparellado en µ(5), temos que mirar o prezo de reserva r3,1. Como r3,1> p1, o emparellamento mantense igual. µ(6) ={(i2, j1),(i1, j2)}. G(6) =     (0.0,0,0.0,4.0,0.0) (0.0,0,0.0,5.0,0.0) (0,0,0,0,6.0) (0,0.0,0,7.0,0.0) (0.0,0,0.0,4.0,0.0) (0,0,0,0,7.0) (0.0,0,0.0,0.0,0.0) (0.0,0,0.0,0.0,0.0) (0,0,0,0,1.0)     . Iteración 6: 1. P= (i3, j0),w(P) = 1.0. 2. Distancias ao vértice i3: Postores: d(6)(i1, i1) = ∞d(6)(i1, i2) = ∞d(6)(i1, i3) = 0. Ocos: d(6)(i1, j1) = ∞d(6)(i1, j2) = ∞. 3. u(7) = (6.0,7.0,0.0). 4. p(7) = (2.0,0.0). 5. Trátase do caso de aresta terminal. O último oco presente en Pnon se emparella. ao tratarse Pdun camiño con lonxitude 2, o emparellamento mantense igual. µ(7) ={(i2, j1),(i1, j2)}. Novo grafo de actualización: G(7) =     (0.0,0,0.0,4.0,0.0) (0.0,0,0.0,5.0,0.0) (0,0,0,0,6.0) (0,0.0,0,7.0,0.0) (0.0,0,0.0,4.0,0.0) (0,0,0,0,7.0) (0.0,0,0.0,0.0,0.0) (0.0,0,0.0,0.0,0.0) (0,0,0,0,0.0)     . Iteración 7: 1. Non existe ningún camiño alterando P, polo que o algoritmo detén a súa execución. A asignación final (u, p, µ)é: Utilidades: u= (6.0,7.0,0.0). Prezos: p= (2.0,0.0). Emparellamento: µ={(i2, j1),(i1, j2)}. Unha vez comprendido o funcionamento do algoritmo, procederase a detallar o experimento que puxo a proba o algoritmo, permitindo derivar distintas conclusións sobre as súas características e a súa eficiencia. 5.2. Xeración de datos 51 5.2. Xeración de datos Ao longo desta sección, haberá detalles de implementación nos que non se profundizará debido a que xa foron cubertos no Capítulo 3. A pesar de que os conxuntos de datos contan con características distintas, a base da xeración dos datos será común. Neste caso, os tamaños de problema escollidos foron N={3,5,8,10,20,50,100}. O principal motivo de usar tamaños mais pequenos que no estudo de Gale-Shapley é a complexidade computacional do mesmo. Deste xeito, de usar tamaños da mesma orde, os tempos de execución comezarían a dispararse. Por outra parte, nun primeiro momento usarase o caso particular de que o número de postores e o número de ocos é o mesmo, n=k, principalmente por unha cuestión de simplicidade, pero posteriormente estes parámetros iranse variando. Do mesmo xeito, o número de iteracións realizadas neste caso tamén será unha orde inferior, repetindo cada execución para cada tamaño 100 veces. O script que foi empregado para este experimento está presente no código B.3. Finalmente, para producir os valores iniciais para cada postor e oco usarase unha distribución uniforme para xerar estes números. Deste xeito, o valor, prezo máximo e prezo de reserva serán xerados con devandita distribución seguindo as seguintes restricións: 0.0≤rij < mij ≤vij ≤10.0∀i, j ∈ {1, ..., n}. A intuición detrás destas restricións será forzar que cada un dos postores estea interesado en todos os ocos, por iso o prezo que puxa é superior ao de reserva, ademais de poder optar por distintas estratexias, por iso a súa puxa pode ser inferior ao valor real que o postor lle asigna ao oco. O código do script implementado en Python empregado para a xeración dos conxuntos de datos amósase no código B.1. 5.3. Resultados A implementación do algoritmo do mecanismo xeral de subastas empregado para os experimentos pode consultarse no código B.2. 5.3.1. Calidade dos emparellamentos En primeiro lugar, antes de proceder a revisar os prezos e utilidades obtidas, verificarase que o algoritmo funcionou como era esperado. Ao tratarse dunhas condicións nas que calquera dos 52 5. Estudo numérico mecanismo xeral de subasta postores conta cunha puxa superior ao prezo de reserva de calquera dos ocos, é de esperar que todos os postores sexan emparellados con un oco. Figura 5.2: Media de emparellamentos para distintos tamaños de problema. Como se pode observar na figura 5.2, na que se representa a media do número de emparellamentos producidos no experimento para cada un dos tamaños de problema. Aí podemos observar como este valor é exactamente igual ao tamaño do problema, polo que podemos verificar a suposición inicial. A partir de aí, estudaremos a distribución das utilidades e dos prezos finais. Ao tratarse de dous parámetros xerados a partir dunha distribución uniforme e cunhas cotas restrictivas, un poderá pensar que non deberían estar moi espallados. Por unha banda, na figura 5.3 pódese observar un diagrama de caixa que amosa a distribución das medias dos prezos. Debido ás restricións nos prezos de reserva, considerablemente inferiores ás puxas e valores, estes son relativamente pequenos. Do mesmo xeito, a medida que se aumenta o tamaño do problema, a diferenza entre a media de prezos é cada vez mais pequena, polo que a maioría de postores pagarán un prezo semellante polo oco. Deste xeito, o prezo de cada oco xa non virá tan influenciado pola diferenza entre os valores que os postores lle asignaron inicialmente. Por outra parte, a figura 5.4 amosa un diagrama de caixa coa distribución das medias das 5.3. Resultados 53 Figura 5.3: Distribución de prezos para distintos tamaños de problema. utilidades. De novo, pode observarse como estas utilidades son elevadas, preto do máximo imposto inicialmente, sendo mais uniformes a medida que se achega a tamaños de problema mais elevados. Isto é consecuencia directa da distribución dos prezos, xa que, ao ser mais ben baixos, a utilidade tenderá a non baixar demasiado en cada iteración. Figura 5.4: Distribución das utilidades para distintos tamaños de problema. A continuación, realizouse outro estudo fixando o número de postores a 30, e variando o 54 5. Estudo numérico mecanismo xeral de subasta parámetro k, o número de ocos. Completáronse probas ∀k∈ {1, ..., 30}, de novo realizando 100 iteracións para cada un dos valores. O script empregado neste caso está presente no código B.4. Figura 5.5: Utilidade total segundo o número de ocos dispoñibles. A pesar de que si que se pode observar na regresión lineal representada na figura 5.5 a tendencia crecente da utilidade total segundo o número de ocos dispoñibles, esta non é tan evidente para valores baixos. Para eses casos de números de ocos baixos, a dispersión dos valores da utilidade leva a contar con valores de utilidade total mais altos que os que se atopan preto do número de 10 ocos. Será a partir de aí cando o número de ocos sexa o suficientemente elevado para contrarrestar devandita dispersión. 5.3.2. Eficiencia do algoritmo De xeito similar ao estudado en Gale-Shapley, neste caso tamén nos centramos en comprobar o número de iteracións que o algoritmo precisa para a súa finalización, o que permitirá determinar a súa complexidade computacional. A figura 5.6 representa con puntos as iteracións realizadas polo algoritmo nas distintas repeticións do experimento en escala logarítmica. A liña azul representa a cota superior, a curva n(2k+ 1), que, ao tratarse do caso particular de n=k, esta curva será da forma 2n2+n. Finalmente, a liña de cor negro representa a curva obtida a partir dunha regresión lineal calculada a partir do número de iteracións. 5.3. Resultados 55 Figura 5.6: Número de iteracións segundo o tamaño do problema. Como se pode observar, en ningún momento o número de iteracións se acerca ao número máximo de iteracións, situándose a meirande parte dos puntos mais cerca da función identidade que da cota máxima. Isto é debido a que, para alcanzar esta cota, sería preciso contar cunha situación moi particular, na que cada un dos postores presente unha aresta de cada tipo a cada un dos ocos, e en cada iteración só podería eliminarse unha aresta. 56 5. Estudo numérico mecanismo xeral de subasta Apéndice A Código do estudo numérico de Gale-Shapley A.1. Xeración dos conxuntos de datos 1import random 2import sys 3 4if __name__ == ’__main__’: 5 6n= int(sys.argv[1]) 7n_list =[i for iin range(n)] 8 9f= open(’dataset.txt’,’w’) 10 11 f.write(str(n) + ’\n’) 12 13 for _in range(n): 14 random.shuffle(n_list) 15 for iin range(n-1): 16 f.write(str(n_list[i]) + ’ ’) 17 f.write(str(n_list[-1]) + ’\n’) 18 19 for _in range(n): 20 random.shuffle(n_list) 21 for iin range(n-1): 22 f.write(str(n_list[i]) + ’ ’) 23 f.write(str(n_list[-1]) + ’\n’) 24 25 f.close() Código A.1: Código usado para a xeración dos conxuntos de datos. 1 2 A. Código do estudo numérico de Gale-Shapley A.2. Código dos algoritmos 1import sys 2import random 3 4def stable_match(n, men_preferences, women_preferences): 5men_index =[0 for _in range(n)] 6free_men = set([i for iin range(n)]) 7women_proposals =[[] for _in range(n)] 8active_proposals =True 9n_iter =0 10 while len(free_men) > 0: 11 n_iter +=1 12 for min free_men: 13 curr_choice =men_preferences[m][men_index[m]] 14 men_index[m] +=1 15 women_proposals[curr_choice].append(m) 16 for win range(n): 17 p= len(women_proposals[w]) 18 if p > 1: 19 curr_w_pref =women_preferences[w] 20 first_index =curr_w_pref.index(women_proposals[w][0]) 21 for iin range(1,p): 22 curr_index =curr_w_pref.index(women_proposals[w][i]) 23 if curr_index < first_index: 24 women_proposals[w][0], women_proposals[w][i] =women_proposals[w][i], women_proposals[w][0] 25 free_men.add(women_proposals[w][i]) 26 first_index =curr_index 27 women_proposals[w] =[women_proposals[w][0]] 28 29 if p>0and women_proposals[w][0] in free_men: 30 free_men.remove(women_proposals[w][0]) 31 32 matches =[(x[0],i) for (i,x) in enumerate(women_proposals)] 33 34 return (matches, n_iter) 35 36 def get_satisfaction(n, preferences, match): 37 total =0 38 39 for iin range(n): 40 index =preferences[i].index(match[i]) 41 individual_satisfaction =(n - index - 1)/(n-1) 42 total +=individual_satisfaction 43 return total 44 45 def read_dataset(path): 46 men_pref =[] 47 wom_pref =[] 48 f= open(path, ’r’) 49 n= int(f.readline()) 50 for _in range(n): 51 line =f.readline() A.2. Código dos algoritmos 3 52 arr =[int(x) for xin line.split(" ")] 53 men_pref.append(arr) 54 for _in range(n): 55 line =f.readline() 56 arr =[int(x) for xin line.split(" ")] 57 wom_pref.append(arr) 58 59 return (n, men_pref, wom_pref) 60 61 def random_allocation(n): 62 n_range =[i for iin range(n)] 63 random.shuffle(n_range) 64 matches =[(x, i) for i,x in enumerate(n_range)] 65 return matches 66 67 def heuristic_allocation(n, m_pref): 68 matched_w = set() 69 men_match =[-1 for _in range(n)] 70 for iin range(n): 71 curr_prefs =m_pref[i] 72 for jin range(n): 73 if curr_prefs[j] not in matched_w: 74 men_match[i] =curr_prefs[j] 75 matched_w.add(curr_prefs[j]) 76 break 77 78 matches =[(i,x) for i,x in enumerate(men_match)] 79 return matches 80 81 def get_men_and_women_matches(matches): 82 women_matches =[i for (i,_) in matches] 83 men_matches =[-1 for _in range(n)] 84 85 for (i,j) in matches: 86 men_matches[i] =j 87 88 return (men_matches, women_matches) 89 90 def write_results(f, algo, n, m_matches, w_matches, m_pref, w_pref, n_iter): 91 women_sat =get_satisfaction(n, w_pref, women_matches) 92 men_sat =get_satisfaction(n, m_pref, men_matches) 93 overall_sat =women_sat + men_sat 94 f.write(algo + ’,’ +str(n) + ’,’ +str(overall_sat) + ’,’ +str(men_sat) + ’,’ +str(women_sat) + ’,’ +str(n_iter) + ’\n’) 95 96 97 98 if __name__ == ’__main__’: 99 path =sys.argv[1] 100 101 n, m_pref, w_pref =read_dataset(path) 102 103 out_path =sys.argv[2] 104 10 B. Código do estudo numérico do mecanismo xeral de subasta 205 return UpdateGraph{ 206 graph, 207 terminal_arr: terminals 208 } 209 } 210 211 fn update_graph_edges(&mut self) { 212 let n_bidders = self.values.shape()[0]; 213 let n_slots = self.values.shape()[1]; 214 let mut terminals: Vec<TerminalNode> = Vec::new(); 215 216 for iin 0..n_bidders { 217 if self.matching.utilities[i] > 0.0 { 218 terminals.push(TerminalNode{terminal_edge : Some(self.matching.utilities[i])}); 219 }else { 220 terminals.push(TerminalNode{terminal_edge: None}); 221 } 222 } 223 self.graph.terminal_arr =terminals; 224 for iin 0..n_bidders { 225 for jin 0..n_slots { 226 if self.matching.prices[j] >= self.reserve_prices[[i,j]] && self.matching.prices[j] < self.max_prices[[i, j]]{ 227 let forward_edge_value = self.matching.utilities[i] + self.matching.prices[j] - self.values[[i, j]]; 228 if forward_edge_value > 0.0 { 229 self.graph.graph[i][j].forward_edge = Some(forward_edge_value); 230 }else { 231 self.graph.graph[i][j].forward_edge = None; 232 } 233 } 234 for (bidder, slot) in &self.matching.pairs{ 235 if *bidder == i && *slot == j { 236 let backward_edge_value = self.values[[i, j]] - self.matching.utilities[i] - self.matching.prices[j]; 237 self.graph.graph[i][j].backward_edge = Some(backward_edge_value); 238 break; 239 }else { 240 self.graph.graph[i][j].backward_edge = None; 241 } 242 } 243 if self.matching.utilities[i] + self.reserve_prices[[i, j]] > self.values[[i,j]] { 244 let reserve_price_edge_value = self.matching.utilities[i] + self.reserve_prices[[i,j]] - self.values[[i, j]]; 245 self.graph.graph[i][j].reserve_price_edge = Some(reserve_price_edge_value); 246 }else { 247 self.graph.graph[i][j].reserve_price_edge = None; 248 } 249 if self.matching.utilities[i] + self.max_prices[[i, j]] > self.values[[i,j]] { 250 let max_price_edge_value = self.matching.utilities[i] + self.max_prices[[i, j]] - self.values[[i,j]]; 251 self.graph.graph[i][j].maximum_edge= Some(max_price_edge_value); 252 }else { 253 self.graph.graph[i][j].maximum_edge = None; B.1. Código para a xeración dos datos 11 254 } 255 } 256 } 257 } 258 259 pub fn update_graph(&self) -> UpdateGraph { 260 return Auction::update_graph_values(&self.matching, &self.values, &self.max_prices, &self.reserve_prices); 261 } 262 263 pub fn get_bidders_num(&self)->usize { 264 return self.values.shape()[0]; 265 } 266 267 pub fn get_slots_num(&self)->usize { 268 return self.values.shape()[1]; 269 } 270 271 pub fn is_feasible(&self, matching: Matching) -> bool { 272 for (i,j) in matching.pairs { 273 if matching.prices[j] < self.reserve_prices[[i, j]] || 274 matching.prices[j] > self.max_prices[[i, j]] || 275 matching.prices[j] + matching.utilities[i] != self.values[[i,j]] { 276 return false; 277 } 278 } 279 280 return true; 281 } 282 283 fn is_blocking(&self, matching: &Matching, i: usize, j: usize)->bool { 284 return matching.utilities[i] + matching.prices[j] >= self.values[[i,j]] || 285 matching.prices[j] >= self.max_prices[[i,j]] || 286 matching.utilities[i] + self.reserve_prices[[i,j]] >= self.values[[i,j]]; 287 } 288 289 pub fn get_blocking_pairs(&self, matching: &Matching) -> Array1<(usize,usize)> { 290 let blocking_pairs =matching 291 .pairs 292 .iter() 293 .filter(|(i,j)| self.is_blocking(matching, *i, *j)) 294 .map(|(i,j)| (*i, *j)); 295 return Array1::from_iter(blocking_pairs); 296 297 } 298 299 pub fn is_stable(&self, matching: Matching) -> bool { 300 let blocking_pairs = self.get_blocking_pairs(&matching); 301 return blocking_pairs.len() > 0; 302 } 303 304 305 fn get_unmatched_bidders(&self)->Vec<usize> { 306 let n= self.get_bidders_num(); 12 B. Código do estudo numérico do mecanismo xeral de subasta 307 let mut set: HashSet<usize>= HashSet::with_capacity(n); 308 for (i, _) in &self.matching.pairs{ 309 set.insert(*i); 310 } 311 let bidders: Vec<usize>=(0..n).collect(); 312 let available_bidders: Vec<usize>=bidders 313 .into_iter() 314 .filter(|i| !set.contains(&i)) 315 .collect(); 316 return available_bidders; 317 } 318 319 fn get_unmatched_slots(&self)->Vec<usize> { 320 let m= self.get_slots_num(); 321 let mut set: HashSet<usize>= HashSet::with_capacity(m); 322 for (_, j) in &self.matching.pairs{ 323 set.insert(*j); 324 } 325 let slots: Vec<usize>=(0..m).collect(); 326 let available_slots: Vec<usize>=slots 327 .into_iter() 328 .filter(|j| !set.contains(&j)) 329 .collect(); 330 return available_slots; 331 } 332 333 fn get_alternating_path(&self) -> AlternatingPath { 334 let unmatched_bidders = self.get_unmatched_bidders(); 335 let unmatched_slots: Vec<usize>=(0..self.get_slots_num()).collect(); 336 let feasible_bidders: Vec<usize>=unmatched_bidders 337 .iter() 338 .filter(|&i| self.matching.utilities[*i] > 0.0) 339 .map(|x| *x) 340 .collect(); 341 const B: f64 = std::f64::MAX; 342 let DUMMY_SLOT: usize = self.get_slots_num(); 343 let mut curr_min_path =AlternatingPath{ 344 path: Vec::new(), 345 cost: B, 346 final_edge: EdgeType::TERMINAL 347 }; 348 for initial_bidder in feasible_bidders{ 349 let mut curr_path =AlternatingPath{ 350 path: Vec::new(), 351 cost: B, 352 final_edge: EdgeType::TERMINAL 353 }; 354 curr_path.path.push(initial_bidder); 355 let mut size = 0; 356 let mut curr_node =initial_bidder; 357 let mut visited_slots: HashSet<usize>= HashSet::new(); 358 let mut visited_bidders: HashSet<usize>= HashSet::new(); 359 visited_bidders.insert(curr_node); 360 let mut end = false; B.1. Código para a xeración dos datos 13 361 let mut is_viable = false; 362 while visited_bidders.len() + visited_slots.len() > size && !end { 363 let mut candidate: Option<usize>= None; 364 let mut candidate_cost =B; 365 let mut edge_type =EdgeType::TERMINAL; 366 let available_slots =unmatched_slots 367 .iter() 368 .filter(|&x| !visited_slots.contains(x)); 369 let curr_terminal =&self.graph.terminal_arr[curr_node]; 370 if curr_terminal.terminal_edge.is_some() { 371 end = true; 372 let max_cost =curr_terminal.terminal_edge.unwrap(); 373 if max_cost < candidate_cost{ 374 candidate = Some(DUMMY_SLOT); 375 candidate_cost =max_cost; 376 edge_type =EdgeType::TERMINAL; 377 } 378 is_viable = true; 379 } 380 for &j in available_slots { 381 let node =&self.graph.graph[curr_node][j]; 382 if node.maximum_edge.is_some() { 383 end = true; 384 let max_cost =node.maximum_edge.unwrap(); 385 if max_cost < candidate_cost{ 386 candidate = Some(j); 387 candidate_cost =max_cost; 388 edge_type =EdgeType::MAXIMUM; 389 } 390 is_viable = true; 391 } 392 if node.reserve_price_edge.is_some() { 393 end = true; 394 let max_cost =node.reserve_price_edge.unwrap(); 395 if max_cost < candidate_cost{ 396 candidate = Some(j); 397 candidate_cost =max_cost; 398 edge_type =EdgeType::RESERVE; 399 } 400 is_viable = true; 401 } 402 if !end & node.forward_edge.is_some() { 403 let max_cost =node.forward_edge.unwrap(); 404 if max_cost < candidate_cost{ 405 candidate = Some(j); 406 candidate_cost =max_cost; 407 } 408 is_viable = false; 409 } 410 } 411 if candidate.is_some(){ 412 visited_slots.insert(candidate.unwrap()); 413 size +=1; 414 if curr_path.path.len() == 1{ 14 B. Código do estudo numérico do mecanismo xeral de subasta 415 curr_path.cost =candidate_cost; 416 }else { 417 curr_path.cost +=candidate_cost; 418 } 419 curr_path.final_edge =edge_type; 420 curr_path.path.push(candidate.unwrap()); 421 curr_node =candidate.unwrap(); 422 } 423 if !end && candidate.is_some(){ 424 let available_bidders =unmatched_bidders 425 .iter() 426 .filter(|x| !visited_bidders.contains(x)); 427 candidate = None; 428 candidate_cost =B; 429 for &i in available_bidders{ 430 let backward_node =&self.graph.graph[curr_node][i]; 431 if backward_node.backward_edge.is_some() { 432 let max_cost =backward_node.backward_edge.unwrap(); 433 if max_cost < candidate_cost{ 434 candidate = Some(i); 435 candidate_cost =max_cost; 436 } 437 is_viable = false; 438 } 439 } 440 if candidate.is_some(){ 441 if candidate.is_some(){ 442 visited_bidders.insert(candidate.unwrap()); 443 size +=1; 444 curr_path.cost +=candidate_cost; 445 curr_path.path.push(candidate.unwrap()); 446 curr_node =candidate.unwrap(); 447 } 448 } 449 } 450 } 451 452 if is_viable && curr_min_path.cost > curr_path.cost { 453 curr_min_path =curr_path; 454 } 455 } 456 return curr_min_path; 457 } 458 459 fn compute_distances(&self, start: usize) -> Distances { 460 let n_slots = self.get_slots_num(); 461 let n_bidders = self.get_bidders_num(); 462 let B=10.0; 463 let mut slots_distances: Array1<f64>=Array::from_elem(n_slots,B); 464 let mut bidders_distances: Array1<f64>=Array::from_elem(n_bidders,B); 465 let mut visited_slots : HashSet<usize>= HashSet::new(); 466 let mut visited_bidders: HashSet<usize>= HashSet::new(); 467 let mut queue: VecDeque<(usize,f64,bool)> = VecDeque::new(); 468 queue.push_front((start, 0.0, true)); B.1. Código para a xeración dos datos 15 469 while !queue.is_empty() { 470 let (node, cost, is_bidder) =queue.pop_back().unwrap(); 471 if is_bidder { 472 for jin 0..n_slots{ 473 if !visited_slots.contains(&j){ 474 match self.graph.graph[node][j].forward_edge { 475 None => (), 476 Some(x) => { 477 slots_distances[j] =x + cost; 478 queue.push_front((j, x + cost, false)); 479 visited_slots.insert(j); 480 } 481 } 482 } 483 } 484 }else { 485 for iin 0..n_bidders{ 486 if !visited_bidders.contains(&i){ 487 match self.graph.graph[i][node].backward_edge { 488 None => (), 489 Some(x) => { 490 bidders_distances[i] =x + cost; 491 queue.push_front((i, x + cost, true)); 492 visited_bidders.insert(i); 493 } 494 } 495 } 496 } 497 } 498 } 499 bidders_distances[start] =0.0; 500 return Distances{ 501 slots_distances, 502 bidders_distances 503 } 504 } 505 506 fn fill_pairs(&self, path: &AlternatingPath, length: usize) -> Array1<(usize,usize)> { 507 let mut pairs : Vec<(usize,usize)> = Vec::new(); 508 for iin (0..length).step_by(2) { 509 let pair =(*path.path.get(i).unwrap(), *path.path.get(i+1).unwrap()); 510 pairs.push(pair); 511 } 512 return Array::from_vec(pairs); 513 } 514 515 fn update_matches(&self, new_pairs: Array1<(usize,usize)>) -> Array1<(usize,usize)> { 516 let mut new_matches : Vec<(usize,usize)> = Vec::new(); 517 let mut bidders_set: HashSet<usize>= HashSet::with_capacity(new_pairs.len()); 518 let mut slots_set: HashSet<usize>= HashSet::with_capacity(new_pairs.len()); 519 520 for iin 0..new_pairs.len() { 521 new_matches.push(new_pairs[i]); 522 bidders_set.insert(new_pairs[i].0); 16 B. Código do estudo numérico do mecanismo xeral de subasta 523 slots_set.insert(new_pairs[i].1); 524 } 525 526 for iin 0..self.matching.pairs.len(){ 527 let curr_match = self.matching.pairs[i]; 528 if !bidders_set.contains(&curr_match.0) && !slots_set.contains(&curr_match.1) { 529 new_matches.push(curr_match); 530 } 531 } 532 533 return Array::from_vec(new_matches); 534 } 535 536 fn update_terminal_assignment(&self, path: &AlternatingPath) -> Option<Array1<(usize,usize)>>{ 537 let new_pairs = self.fill_pairs(path, path.path.len() - 2); 538 return Some(self.update_matches(new_pairs)); 539 } 540 541 fn update_maximum_assignment(&self, path: &AlternatingPath) -> Option<Array1<(usize,usize)>>{ 542 let n=path.path.len(); 543 if n >=4 && path.path.get(n-1).unwrap() !=path.path.get(n-3).unwrap() { 544 return None; 545 } 546 let new_pairs = self.fill_pairs(path, path.path.len() - 2); 547 return Some(self.update_matches(new_pairs)); 548 } 549 550 fn update_reserve_assignment(&self, path: &AlternatingPath, updated_prices: &Array1<f64>) -> Option<Array1<(usize,usize)>> { 551 let last_item =path.path.last().unwrap(); 552 let is_last_item_matched = self.matching.pairs.iter().filter(|(_, j)| j == last_item).last().is_some(); 553 if !is_last_item_matched { 554 let pairs = self.fill_pairs(path, path.path.len()); 555 return Some(concatenate(ndarray::Axis(0),&[self.matching.pairs.view(), pairs.view()]).unwrap()); 556 }else if self.graph.graph[*path.path.get(path.path.len()-2).unwrap()][*last_item].reserve_price_edge.unwrap_or_else(|| 0.0) < updated_prices[*last_item]{ 557 return None; 558 }else { 559 let new_pairs = self.fill_pairs(path, path.path.len() - 2); 560 return Some(self.update_matches(new_pairs)); 561 } 562 } 563 564 fn update_assignments(&self, updated_prices: &Array1<f64>, path: &AlternatingPath) -> Option<Array1<(usize,usize)>> { 565 match path.final_edge { 566 EdgeType::TERMINAL => self.update_terminal_assignment(path), 567 EdgeType::MAXIMUM => self.update_maximum_assignment(path), 568 EdgeType::RESERVE => self.update_reserve_assignment(path, updated_prices) 569 } 570 } B.1. Código para a xeración dos datos 17 571 572 pub fn stable_match(mut self)->usize { 573 let n= self.get_bidders_num(); 574 let k= self.get_slots_num(); 575 const B:f64 = std::f64::MAX; 576 let mut iter : usize = 0; 577 let mut cost: f64 = 0.0; 578 while cost !=B { 579 iter =iter + 1; 580 let path: AlternatingPath = self.get_alternating_path(); 581 if path.path.len() < 2 || iter > n*(2*k+1){ 582 break; 583 } 584 cost =path.cost; 585 let max_f64 =|f1, f2| { 586 if f1 >=f2 { 587 return f1 588 }else { 589 return f2 590 } 591 }; 592 593 let first_item =path.path.get(0).unwrap_or_else(|| &(0 as usize)); 594 let distances: Distances = self.compute_distances(*first_item); 595 let mut updated_utilities = self.matching.utilities.clone(); 596 let mut updated_prices = self.matching.prices.clone(); 597 for iin 0..n{ 598 updated_utilities[i] =updated_utilities[i] - max_f64(path.cost - distances.bidders_distances[i], 0.0); 599 } 600 for jin 0..k{ 601 updated_prices[j] =updated_prices[j] + max_f64(path.cost - distances.slots_distances[j], 0.0); 602 } 603 match path.final_edge { 604 EdgeType::RESERVE => { 605 let last_slot : usize = *path.path.get(path.path.len()-1).unwrap(); 606 let last_bidder : usize = *path.path.get(path.path.len()-2).unwrap(); 607 updated_prices[last_slot] =max_f64(updated_prices[last_slot], self.reserve_prices[[last_bidder, last_slot]]); 608 } 609 _=> () 610 } 611 612 let updated_assignments = self.update_assignments(&updated_prices, &path); 613 let new_assignments = match updated_assignments { 614 None => self.matching.pairs.clone(), 615 Some(x) => x 616 }; 617 self.matching =Matching { 618 utilities: updated_utilities, 619 prices: updated_prices, 620 pairs: new_assignments 621 }; 18 B. Código do estudo numérico do mecanismo xeral de subasta 622 self.update_graph_edges(); 623 } 624 self.write_results("rust-results2.txt".to_string(), iter); 625 return iter; 626 } 627 628 629 fn write_results(self, path: String, iterations: usize) -> () { 630 let mut file =fs::OpenOptions::new() 631 .write(true) 632 .append(true) 633 .open(path) 634 .unwrap(); 635 let n= self.get_bidders_num(); 636 let k= self.get_slots_num(); 637 let mut result : String = 638 n.to_string() + "," + 639 &k.to_string() + "," + 640 &iterations.to_string() + ","; 641 642 for (i,j) in self.matching.pairs { 643 result =result + 644 &i.to_string() + "-" + &j.to_string() + "/"; 645 } 646 result =result + ","; 647 for xin self.matching.utilities { 648 result =result + &x.to_string() + "-"; 649 } 650 result =result + ","; 651 for xin self.matching.prices { 652 result =result + &x.to_string() + "-"; 653 } 654 result =result + "\n"; 655 file.write_all(result.as_bytes()).expect("Unable to write to file"); 656 } 657 } 658 659 fn main() { 660 let vals_opt =Auction::read_file("./rust-dataset.txt".to_string()).unwrap(); 661 let auction =Auction::new(vals_opt.0, vals_opt.1, vals_opt.2); 662 println!("Auction"); 663 println!("{:?}",auction.values); 664 println!("{:?}",auction.reserve_prices); 665 println!("{:?}",auction.max_prices); 666 println!("{:?}",auction.graph); 667 let iter =auction.stable_match(); 668 println!("Number of iterations: {:?}", iter); 669 } Código B.2: Implementación do mecanismo xeral de subasta. 1n=(3 5 8 10 20 50 100) 2len=${#n[@]} 3iter=100 4 B.1. Código para a xeración dos datos 19 5for((j=0; j < $iter; j++)) 6do 7for((i=0; i < $len; i++)) 8do 9echo "Execucion: ${j} - n: ${n[$i]}" 10 python3 generate_auction.py ${n[$i]} ${n[$i]} 11 cargo run 12 done 13 done Código B.3: Script usado para o primeiro experimento do mecanismo xeral de subastas. 1n=30 2iter=100 3 4for((j=0; j < $iter; j++)) 5do 6for((i=0; i < 30; i++)) 7do 8echo "Execucion: ${j} - k: $i" 9python3 generate_auction.py $n $i 10 cargo run 11 done 12 done Código B.4: Script usado para o primeiro experimento do mecanismo xeral de subastas.