T aballo Fin de G ao
Empa ellamen os Es ables: Algo i mo
de Gale-Shapley
Uxío Ga cía And ade
Xullo, 2022
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
GRAO DE MATEMÁTICAS
T aballo Fin de G ao
Empa ellamen os Es ables: Algo i mo
de Gale-Shapley
Uxío Ga cía And ade
Xullo, 2022
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
iii
i
T aballo p opos o
Á ea de Coñecemen o: Es a ís ica e In es igación Ope a i a
Tí ulo: Empa ellamen os Es ables: Algo i mo de Gale-Shapley
B e e desc ición do con ido
O obxec o de es udo des e TFG se á o p oblema de a opa un empa e-
llamen o es able en e dous conxun os de elemen os de igual amaño,
onde cada elemen o dun conxun o en unha o de de p e e encias sob e
os elemen os do ou o conxun o. Un empa ellamen o é simplemen e
unha bixección en e os elemen os de ambos conxun os. Un empa e-
llamen o A é es able se non exis e ningunha pa ella (α,β), dis in a ás
p opos as polo empa ellamen o, coa p opiedade de que an o αcomo
βse p e i en mu uamen e on e ás súas espec i as pa ellas baixo o
empa ellamen o A. O p incipal obxec i o des e aballo se á in odu-
ci o algo i mo de Gale e Shapley, in oducido o malmen e en 1962,
e es uda as súas p opiedades ma emá icas. O p oblema do empa e-
llamen o es able ecibiu unha g an a ención da comunidade cien í ica
polas súas múl iples aplicacións en dis in os ámbi os: asignación de
es udan es a colexios, de médicos a hospi ais,...
Recomendacións
Non hai ningunha ecomendación en pa icula .
Ou as obse acións
Non hai ningunha obse ación.
Índice
Resumo iii
In odución xi
1. Algo i mos de Empa ellamen o 1
2. Algo i mo de Gale-Shapley 5
2.1. Caso Pa icula : Ma imonio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1. P opiedades de Gale-Shapley pa a o p oblema do ma imonio . . . . . . . 9
2.2. Ex ensión: Admisión a uni e sidades . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1. P opiedades de Gale-Shapley pa a o p oblema das admisións a uni e sidades 14
3. Es udo Numé ico Gale-Shapley 17
3.1. Xe ación dos conxun os de da os . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2. Resul ados........................................ 18
3.2.1. Sa is acción empa ellamen os . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2. E iciencia de Gale-Shapley . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4. Mecanismo Xe al de Subas a 25
4.1. In odución ao mecanismo xe al de subas a . . . . . . . . . . . . . . . . . . . . . 32
4.2. Algo i mo........................................ 33
4.2.1. In a ian es ................................... 38
i ÍNDICE
5. Es udo numé ico mecanismo xe al de subas a 45
5.1. Exemploinicial:..................................... 45
5.2. Xe acióndeda os.................................... 51
5.3. Resul ados........................................ 51
5.3.1. Calidade dos empa ellamen os . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.2. E iciencia do algo i mo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
A. Código do es udo numé ico de Gale-Shapley 1
A.1. Xe ación dos conxun os de da os . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
A.2.Códigodosalgo i mos ................................. 2
A.3. Código pa a a ealización do expe imen o . . . . . . . . . . . . . . . . . . . . . . 4
B. Código do es udo numé ico do mecanismo xe al de subas a 5
B.1. Código pa a a xe ación dos da os . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Bibliog a ía 21
2 1. Algo i mos de Empa ellamen o
De inición 1.8 (Empa ellamen o).Unha asignación ou empa ellamen o Aé un conxun o
de pa es o denados (n, m), onde n∈Nem∈M, de al xei o que cada n∈Napa ece como
moi o nunha pa ella de A, e cada m∈Mapa ece como moi o nunha pa ella de A.
De inición 1.9. Unha asignación Aen e un conxun o NeMdi ase pe ec a se |N|=|M|=
|A|.
De inición 1.10. Unha asignación Adi ase que é ines able se exis en dous elemen os A, B ∈N
que o on asignados a α, β ∈M espec i amen e, a pesa de que A≻βBeβ≻Aα, é dici , β
p e i e a A an es que a B, e Ape i e a βan es que a α.
Unha ep esen ación g á ica dunha asignación ines able amósase na igu a 1.1.
Figu a 1.1: Exemplo de asignación ines able.
De inición 1.11. Unha asignación Adi ase es able se non é ines able.
De inición 1.12. Es a exia. En eo ía de xogos, a es a exia dun xogado é o plan das acción
que pode escolle nunha si uación na que a saída non depende unicamen e das súas accións, senón
das accións dos demais xogado es amén. No e e ido a empa ellamen os es ables, a es a exia
dun elemen o ∈V(G)se á a súa o de de p e e encia {≻ } , polo que, nalgún caso usa anse os
dous e mos indis in amen e.
3
De inición 1.13. Un algo i mo de empa ellamen o di ase a p oba de es a exias ou non
manipulable se un indi iduo non en ningún incen i o pa a non p esen a a súa o de de p e-
e encias eais. De non con a con es a p opiedade, un indi iduo pode ía consegui un esul ado
mais a o able modi icando a súa o de de p e e encia.
4 1. Algo i mos de Empa ellamen o
Capí ulo 2
Algo i mo de Gale-Shapley
Ao longo des e capí ulo desc ibi ase a eo ía e as p opiedades do algo i mo de Gale-Shapley,
in oducido polos au o es homónimos en 1962 [1]. Comenza emos cen ándonos nun caso pa -
icula que pe mi e simpli ica e in oduci o algo i mo dun xei o mais in ui i o, acili ando a
pos e io desc ición do caso xe al.
2.1. Caso Pa icula : Ma imonio
An es de in oduci o algo i mo que esol e o caso xe al das admisións á uni e sidade, é
con enien e es uda un caso pa icula . Es e caso se ía o de que o núme o de es udan es e
uni e sidades ose o mesmo, e odas as cuo as osen uni a ias.
Téndese a es uda es e caso den o do seguin e con ex o: supoñamos que exis e unha comu-
nidade na que emos nhomes e nmulle es, onde cada pe soa con a cunha lis a na que o dea a
cada indi iduo do xéne o opos o segundo as súas p e e encias. O obxec i o se á o de ob e unha
asignación de xei o que cada pe soa poida casa con ou a de al o ma que non exis a ningunha
ou a asignación na que exis e un casamen o que mello a ía a sa is acción global.
Pa a isualiza cla amen e es e p oblema, in oduci ase a con inuación un exemplo:
Exemplo 2.1. Na igu a 2.1 de állase a ma iz de p e e encias de empa ellamen os pa a es
homes, α,βeγ, e es mulle es, A, B e C. Nes a ma iz, o alo que apa ece debaixo da
columna de home, se á a p e e encia que o home que es á nesa columna lle asigna á mulle á
que lle co esponde esa ila. Des e xei o, e iamos, po exemplo, pa a o home α, a súa o de de
p e e encias se ía C≻αA≻αB.
Coa no ación in oducida no capí ulo ex e io , as o des de p e e encias se ían as seguin es:
5
6 2. Algo i mo de Gale-Shapley
Figu a 2.1: Ma iz de p e e encias.
Homes:
≻α:=C, A, B
≻β:=B, C, A
≻γ:=A, B, C
Mulle es:
≻A:=β, α, γ
≻B:=α, γ, β
≻C:=γ, β, α
Exis en 6 combinacións posibles de ma imonios posibles, dos cales 3 son es ables 3 son ines ables.
Un exemplo de combinación es able se ía o caso no que cada home casase coa súa p imei a
elección, é dici , a asignación se ía a seguin e: A= (α, C),(β, B),(γ, A). Des e xei o, cada mulle
ob e ía o home que es á na úl ima posición na súa o de de p e e encias, pe o segui ía sendo
es able, pos o que non exis e ningunha posibilidade de que os homes es ean mais sa is ei os, xa
que odos eñen a súa p imei a elección. As ou as dúas posibilidades de asignacións es ables
se ían asigna a cada mulle a súa p imei a elección, ou asigna a cada pe soa a súa segunda
elección (a segunda elección coincide pa a homes e pa a mulle es).
Po ou a pa e, é posible comp oba apidamen e como o es o de asignacións son ines ables.
Tómese como exemplo a seguin e asignación: A= (α, C),(β, A),(γ, B). No caso de αeβ, emos
que A≻αCeC≻βA, pe o o empa ellamen o é (α, C),(β, A).
Teo ema 2.2 (Gale-Shapley).Sexa H=h1, ..., hnun conxun o de nhomes, e M=m1, ..., mn
un conxun o de nmulle es, semp e exis e unha asignación es able de casamen os.
Demos ación. A demos ación des e eo ema ealiza ase a pa i da de inición dun p ocedemen o
i e a i o, cuxo pseudocódigo se pode e na igu a 2.1, coñecido amén polo nome de algo i mo
de acep ación di e ida. Nes e caso, supoñe ase que os homes son os que p opoñen ma imonio ás
mulle es, pe o a in e sa se ía equi alen e e unciona ía do mesmo xei o.
I e ación 0:
An es de comeza a pa e i e a i a do algo i mo, debe án esol e se as p e e encias que non
son es ic as. É dici , se mi=hkmj,1≤i, j, k ≤n,i=j, se á p eciso esol e es e empa e
2.1. Caso Pa icula : Ma imonio 7
dalgún xei o. Tipicamen e, es es esol e anse o deando os empa es al abe icamen e, pe o os ipos
de es a exias son moi a iados, escolléndose ás eces a esolución de con li os alea o ia.
I e ación 1:
a. Todo home hi,i∈1, ..., n, p opón ma imonio á súa mulle p e e ida, é dici , a Ohi,1.
b. Toda mulle mi,i∈1, ..., n, acep a a p opos a do home que mais al o es ea na súa
o de de p e e encia, e exei a o es o.
I e ación k:
a. Todo home hi,i∈1, ..., n exei ado no paso k−1 ealiza unha no a p opos a a Ohi,j,
j∈1, ..., n, sendo j o meno índice al que Ohi,j aínda non exei ase a hi.
b. Toda mulle miman én a súa o e a p e e ida a a o momen o, é dici , Omi,j, sendo j
o meno índice al que Omi,j ixo unha p opos a a mi.mi exei a o es o de p opos as.
Finalización: Se nunha i e ación non hai ningunha no a p opos a, ob ense a asignación
empa ellando a cada mulle coa p opos a que man eña.
Seguindo es e algo i mo, e emos que que odas as mulle es e án, polo menos, unha p opos a,
xa que, de non se así, e emos que habe á polo menos 2 homes, hiehj,j, i ≤n, j =ique e án
ealizado unha p opos a á mesma mulle mk,k≤n. Non obs an e, como non é posible que se
p oduzan empa es na o de de p e e encia debido á esolución dos mesmos ealizada no paso 0,
e ase que hi≻mkhjou hj≻mkhi, polo que mk exei a á unha das p opos as e o algo i mo
p ocede á a ealiza ou a i e ación.
Po ou a pa e, examos ago a como a asignación p oducida a pa i des e algo i mo se á
es able. Sexa Aes a asignación e sexa un empa ellamen o (hi, mj)∈A. Supoñamos que exis e
ou a mulle mk, al que mk≻himj. Des e xei o, o home hien ioulle unha p opos a á mulle
mknunha i e ación p e ia a mj. Como inalmen e non oi empa ellado con mk, is o que e dici
que mk exei ou a súa p opos a po ou o home hl al que hl≻mkhi, polo que non se pode da
unha ines abilidade no algo i mo.
1Inicializa p opos as pa a cada mulle m a balei o
2do
3m :=cada home h en ía unha p opos a ámulle m que mais al a es ea na lis a e aínda non lla en iase
an es
4i a mulle m en mais dunha p opos a hen
5m :=a mulle m exei a odas as p opos as menos a do home h, que éo que mais al o es á na súa
lis a
6end i
7while apa eza algunha no a p opos a
8de ol e a asignación de cada mulle co home que en iase a p opos a que segue man endo
Código 2.1: Pseudocódigo do algo i mo de acep ación di e ida.
8 2. Algo i mo de Gale-Shapley
Exemplo 2.3. Vexamos ago a como se aplica ía Gale-Shapley ao seguin e exemplo: Sexan 4
homes H={α, β, γ, δ}e sexan 4 mulle es M={A, B, C, D}, coas seguin es o des de p e e encias:
Homes:
≻α:=A, B, C, D
≻β:=A, D, C, B
≻γ:=B, A, C, D
≻δ:=D, B, C, A
Mulle es:
≻A:=δ, γ, α, β
≻B:=β, δ, α, γ
≻C:=δ, α, β, γ
≻D:=γ, β, α, δ
Unha execución no mal do algo i mo se ía o seguin e:
I e ación 0:
As o des de p e e encia son odas es ic as, polo que non se á p eciso esol e
empa es.
I e ación 1:
a. A ecibe p opos as de αeβ. B ecibe p opos a de γ. D ecibe p opos a de δ.
b. A única mulle que ecibe a ias p opos as é A, que exei a β, xa que α≻A
β.
I e ación 2:
a. O único home exei ado no paso 1 oi β, que lle en ia á unha p opos a a Oβ,2=
D.
b. D con a con dúas p opos as, exei a δ, xa que β≻Dδ.
I e ación 3:
a. O único home exei ado no paso 2 oi δ, que lle en ia á unha p opos a a Oδ,2=
B.
b. B con a con dúas p opos as, exei a γ, xa que δ≻Bγ.
I e ación 4:
a. O único home exei ado no paso 3 oi γ, que lle en ia á unha p opos a a Oγ,2=
A.
b. A con a con dúas p opos as, exei a α, xa que γ≻Aα.
I e ación 5:
a. O único home exei ado no paso 4 oi α, que lle en ia á unha p opos a a Oα,2=
2.1. Caso Pa icula : Ma imonio 9
B.
b. B con a con dúas p opos as, exei a α, xa que δ≻Bα.
I e ación 6:
a. O único home exei ado no paso 5 oi α, que lle en ia á unha p opos a a Oα,3=
C.
b. Non hai ningunha mulle con mais dunha p opos a, non se p oduce ningún exei amen o.
Finalización:
Na i e ación 6 non se p oduciu ningún exei amen o, polo que non habe á no as p opos as
e o algo i mo inaliza.
Polo an o, a asignación inal se á S= (α, C),(β, D),(γ, A),(δ, D). É acilmen e
comp obable que es a asignación se á es able.
2.1.1. P opiedades de Gale-Shapley pa a o p oblema do ma imonio
Nes a subsección p esen a anse as p incipais p opiedades ma emá icas que p esen a o algo-
i mo de Gale-Shapley. En e elas, as mais desexables e que ixe on que o algo i mo i ese cabida
en dis in as aplicacións son a de op imalidade da solución ob ida e a de que a es a exia sexa
non manipulable.
De no o, as p opiedades desexadas nes e apa ado es a án asociadas aos homes, o g upo que
ealiza as p opos as nes a e sión, pe o amén se ían álidas no caso de que osen as mulle es as
que ealizan as p opos as. Non obs an e, as dis in as p opiedades non se e i ica án pa a o g upo
que ecibe as p opos as, podendo, po exemplo, da luga a si uacións nas que unha mulle se
bene icie de non apo a a súa o de de p e e encia eal, como e emos pos e io men e.
Teo ema 2.4. O algo i mo de Gale-Shapley ema a en, como moi o n2−2n+ 2 i e acións,
despois de ealiza se n2−n+ 1 p opos as.
Demos ación. Po unha banda, emos que o algo i mo pa a á cando nunha i e ación non se
ealice ningunha p opos a. Des e xei o, e emos que, no peo caso, un dos homes hi e á ealizado
np opos as, sendo empa ellado inalmen e coa mulle que se a opa no úl imo luga da súa o de
de p e e encias, Ohi,n. Pola con a, o es o dos n−1homes pode án ealiza unha p opos a,
como moi o, n−1 eces, xa que, senon, a asignación non se ía es able. Des e xei o, o núme o
o al de p opos as i á dado po :
(n−1)(n−1) + n=n2−2n+ 1 = n2−n+ 1.
10 2. Algo i mo de Gale-Shapley
Do mesmo xei o, pa a o núme o de i e acións, habe á que e en con a que semp e se á
p eciso 1 i e ación inicial, na que ealizan ni e acións. Nas i e acións sucesi as, no peo ca-
so, ealiza ase só 1 p opos a, que se á no caso no que só 1 home sexa exei ado. Des e xei-
o, e emos que o núme o máximo de i e acións se á o mesmo que o de p opos as ealizadas,
es ándolle as p opos as da i e ación inicial. Des e xei o, o núme o o al de i e acións se á:
(n2−n+ 1) −(n−1) = n2−2n+ 2.
Teo ema 2.5. Op imalidade. O algo i mo de Gale-Shapley é óp imo pa a os homes. Is o é, a
asignación es able Ap oducida polo algo i mo é al que non exis e ou a asignación es able A′
na que, dado un home he dúas mulle es m, m′, al que (h, m)∈A(h, m′)∈A′em′≻hm. É
dici , non exis i á ou a asignación es able na que un home es ea empa ellado a unha mulle que
p e i a an es que á que oi empa ellado na asignación p oducida polo algo i mo de Gale-Shapley.
Demos ación. Supoñamos que un home hé empa ellado na asignación p oducida po Gale-
Shapley A cunha mulle m,(h, m)∈Aque non sexa a mello pa ella posible.
Sexa m′a mello pa ella posible e sexa.
En GS, os homes ealizan as súas p opos as en o de dec ecen e, polo que, nalgunha i e ación,
exis i á un p imei o home hse á exei ado pola p imei a mulle m′da súa o de de p e e encia.
Unha ez que hé exei ado po m′,m′acep a á a p opos a dou o home h′, polo que e emos
que:
h′≻m′h. (2.1)
Supoñamos que exis a ou a asignación A′ al que (h′, m)∈A′. O home h′aínda non oi
exei ado po ningunha mulle no momen o no que se p oduce o exei amen o de m′ah, xa que
se a a do p imei o exei amen o.
Des e xei o, h′aínda non lle e ía en iado a p opos a a m′cando lle en ía a p opos a a m′,
polo que:
m′≻h′m. (2.2)
Polo an o, e emos a asignación A′ al que (h′, m)∈A′, pe o, po 2.1 e 2.2, es a asignación non
se á es able, polo que emos unha con adición.
Pola con a, cabe plan exa se como de óp imo é o empa ellamen o p oducido pa a a pa e que
acep a as p opos as. Como e emos a con inuación, o empa ellamen o non só non se á óp imo
pola súa pa e, senon que se á pésimo.
2.1. Caso Pa icula : Ma imonio 11
P oposición 2.6. O empa ellamen o p oducido po Gale-Shapley é pésimo (o peo posible den o
dos empa ellamen os es ables) pa a as mulle es.
Demos ación. Sexan dous homes heh′e dúas mulle es mem′. Supoñamos que mé empa ellada
con hnunha asignación A, pe o hnon é a peo pa ella posible pa a m. En ón exis e unha
asignación es able A′na que hes á empa ellada con h′, home que lle gus a menos que h,h≻mh′.
Sexa m′a pa ella de hen A′. Como sabemos polo eo ema an e io que es e empa ellamen o é
óp imo pa a os homes, emos que m′ ≻hm. Des e xei o, mehp e i ense en e eles an es que as
súas pa ellas en A′, polo que A′non pode se un empa ellamen o es able.
Teo ema 2.7. O algo i mo de Gale-Shapley é a p oba de manipulacións de es a exias
po pa e dos homes, de xei o que un home non pode manipula a súa o de de p e e encias de
xei o que is o lle bene icie. Do mesmo modo, amén con a á coa p opiedade de se a p oba de
manipulacións g upais de es a exias po pa e dos homes, de xei o que non é posible que
un conxun o de homes coo dine unha manipulación das súas o des de p e e encias de xei o que
es es odos se exan modi icados. Si que se á posible, non obs an e, que algúns deles acaben cunha
pa ella mello , men es que o es o man eñan a mesma pa ella.
Demos ación. Po unha banda, a demos ación da p oba da non manipulabilidade de es a exias
pa a homes é i ial a pa i da op imalidade da solución. O algo i mo asegu a que o esul ado
se á o mello posible pa a cada home, polo que cambia a súa o de de p e e encias só pode á le a
a un peo empa ellamen o. Do mesmo xei o, calque a manipulación po pa e dun g upo le a á
a un empa ellamen o peo pa a algúns dos elemen os do g upo, xa que, debido á ca ac e ís ica
de op imalidade, a única opción de que o empa ellamen o esul an e ose mello se ía que ose
ines able, o que se ía unha con adición.
De no o, plan exámonos a dúbida de se es a p opiedade de se a p oba de manipulacións
amén é compa ida pola pa e que acep a as p opos as. Nes e caso, a espos a ol e a se
nega i a.
P oposición 2.8. O algo i mo de Gale-Shapley non é a p oba de manipulacións pa a as mulle es.
Demos ación. Sexan 3 homes h1, h2eh3e 3 mulle es m1, m2em3coas seguin es p e e encias:
≻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 odo o mundo apo e as súas p e e encias eais, o algo i mo de Gale-Shapley ema-
a á coa asignación A={(h1, m1),(h2, m2),(h3, m3)}. Non obs an e, se a mulle m2modi ica as
18 3. Es udo Numé ico Gale-Shapley
in e cambia as posicións dos elemen os p esen es no índice no que se a opa a i e ación e no
índice xe ado alea o iamen e.
Des e xei o, sexa a unción xe ado a de núme os na u ais alea o ios nun in e alo [0, l], l ∈N:
U:N−→ N.
E sexa a unción que in e cambia as posicións na o de de p e e encia:
:N×N−→ N×N
(n1, n2)7−→ (n2, n1).
Polo que o algo i mo p ocede á do seguin e xei o:
∀j∈n, ..., 1k:=U(n), (Ohi,j, Ohi,k).
O algo i mo de Fihse -Ya es p opo ciona unha pe mu ación alea o ia sen sesgo semp e que o
xe ado de núme os alea o ios ampouco sexa sesgado, condición que se e i ica nes e caso.
O código emp egado pa a a xe ación dos conxun os de da os pode e isa se no código A.1.
3.2. Resul ados
3.2.1. Sa is acción empa ellamen os
O p imei o aspec o a es uda se á a sa is acción dos empa ellamen os. Pa a iso, se á p eciso
de ini unha unción que, dado un empa ellamen o A, p opo cione unha medida de como de con-
en o es á cada indi iduo coa súa espec i a pa ella. A de inición des a unción pode á ealiza se
desde en oques dis in os, pe o a que se usa á nes e es udo, c eada explici amen e pa a es e caso
de uso, ca ac e ízase pola súa acilidade de in e p e ación. Sexa sdi a unción:
s:N×N×N−→ R
(u, , n)7−→ (n−Iu, −1)
(n−1) .
Po ou a pa e, amén p ecisa emos algunha liña base coa que compa a os esul ados ob idos
co algo i mo de Gale-Shapley. As seguin es uncións de empa ellamen o o on usadas pa a es a
compa ación:
Empa ellamen o alea o io: es a unción xe a á os empa ellamen os de xei o alea o io, acen-
do uso do algo i mo de Fishe -Ya es desc i o p e iamen e pa a p oduci unha pe mu ación
que dea luga ao empa ellamen o.
3.2. Resul ados 19
Empa ellamen o heu ís ico: es a unción basea ase en asigna a cada un dos homes, po
o de do seu índice, a mulle dispoñible que mais al a es ea na súa lis a. É dici , sexa Ha
unción que, pa a un home dado, ob eña a mulle coa que se á empa ellado:
H:N×N×N× −→ N
(h, A)7−→ Oh,i,m´ın i:∀(h′, m)∈A, m =Oh,i.
Des e xei o, como xa se indicou p e iamen e, ealizá onse 1000 i e acións pa a dis in os amaños
de p oblemas, ob endo os esul ados p esen es na igu a 3.1. Tamén se incluiu ou a g á ica con
escala loga í mica na igu a 3.2, pa a pode isualiza co ec amen e os alo es de sa is acción
pa a alo es de npequenos. Como e a de espe a , o empa ellamen o alea o io é o que menos
Figu a 3.1: Compa ación da sa is acción xe al cos empa ellamen os nos dis in os algo i mos a
conside a .
sa is acción xe al p oduce, pos o que en ningún momen o se eñen en con a as p e e encias
pa a cada indi iduo. Po ou a pa e, amén é posible comp oba o co ec o uncionamen o
do algo i mo Gale-Shapley, pos o que supe a a calque a dos ou os 2 algo i mos pa a calque a
amaño do p oblema.
Vexamos ago a a compa ación da sa is acción pa a cada unha das pa es. En p imei o luga ,
20 3. Es udo Numé ico Gale-Shapley
Figu a 3.2: Compa ación da sa is acción xe al cos empa ellamen os nos dis in os algo i mos a
conside a en escala loga í mica.
comeza emos cos homes que, como xa imos p e iamen e, son os que con an coa ca ac e ís ica de
ob e un empa ellamen o óp imo den o das asignacións es ables. Po ou a banda, o algo i mo
heu ís ico sabemos que es á baseado exclusi amen e na sa is acción dos homes, polo que un
pode ía pensa que es a heu ís ica pode ía chega a supe a a Gale-Shapley nes a mé ica. Es es
esul ados poden e se na igu a 3.3.
A con inuación, e isa emos a sa is acción das mulle es nos dis in os empa ellamen os. Como
xa se desc ibiu p e iamen e, Gale-Shapley non asegu a a op imalidade da asignación pa a o
g upo que acep a as p opos as. Do mesmo xei o, a heu ís ica cén ase só nas p e e encias dos
homes, polo que a sa is acción das mulle es se á p ac icamen e a mesma que no caso do algo i mo
alea o io. Es es esul ados amósanse na igu a 3.4.
Finalmen e, comp obouse a op imalidade do empa ellamen o en Gale-Shapley. Como ben
sabemos, es a op imalidade só es á p esen e pa a os homes, e non as mulle es. Des e xei o, cabe
espe a que a sa is acción dos homes sexa supe io á das mulle es en Gale-Shapley, como se pode
obse a na igu a 3.5. A sa is acción das mulle es é en o no a un 85% in e io á dos homes pa a
os dis in os amaños de p oblema.
3.2. Resul ados 21
Figu a 3.3: Compa ación da sa is acción dos homes cos empa ellamen os nos dis in os algo i mos
a conside a .
Figu a 3.4: Compa ación da sa is acción das mulle es cos empa ellamen os nos dis in os algo i -
mos a conside a .
22 3. Es udo Numé ico Gale-Shapley
Figu a 3.5: Compa ación en e a sa is acción dos homes e das mulle es en Gale-Shapley.
3.2.2. E iciencia de Gale-Shapley
Nes e apa ado es uda ase a e iciencia do algo i mo de Gale-Shapley. En pa icula , es uda-
ase o núme o de i e acións ealizadas a a a inalización do algo i mo pa a os dis in os n, o que
pe mi i á de e mina a súa complexidade compu acional.
A igu a 3.6 ep esen a con pun os o núme o de i e acións ealizadas nas dis in as epe icións
do algo i mo en escala loga í mica. Po ou a pa e, engadiuse a co a supe io eó ica do núme o
de i e acións n2−2n+ 2 que non só non se supe a en ningunha ocasión, senon que non es án
ce ca. Nes e sen ido, amén se incluíu unha eg esión lineal que p e ende ep esen a a endencia
do núme o de i e acións a medida que o amaño do p oblema aumen a.
O código elacionado coa implemen ación dos algo i mos es á p esen e no código A.2, men es
que o sc ip usado pa a execu a odo o expe imen o pode obse a se no código A.3.
3.2. Resul ados 23
Figu a 3.6: Núme o de i e acións ealizadas pa a dis in os amaños de p oblema.
24 3. Es udo Numé ico Gale-Shapley
Capí ulo 4
Mecanismo Xe al de Subas a
Nes e capí ulo cub i ase unha das aplicacións mais ecen es de Gale-Shapley: o desen ol e-
men o dun mecanismo xe al de subas a pa a anuncios en mo o es de búsqueda [6], desen ol ido
e pos o en p ác ica po Google.
A publicidade en In e ne en xe al, e os anuncios en mo o es de búsqueda en pa icula , son
casos cla os de me cados con dúas pa es di e enciadas, xa que emos anuncian es (pos o es) que
compi en po ocos nos que coloca so seus anuncios. Po no ma xe al, es es ocos e án alo es
dis in os asignados polos pos o es, xa que as p imei as posicións e án un maio alo que as que
apa ezan mais abaixo, debido a que can o mais a iba es ea un oco maio se á a p obabilidade de
que un usua io aga click nese anuncio. Un exemplo de subas as nun mo o de búsqueda amósase
na igu a 4.1.
Es es me cados son do mesmo ipo aos desc i os p e iamen e, como o caso dos alumnos e
as uni e sidades. Polo an o, non é ningunha so p esa que algúns dos mecanismos emp egados
es ean basados ou elacionados co algo i mo de Gale-Shapley. Es e é o caso do mecanismo desc i o
nes e capí ulo, que combina á de andi o algo i mo e o mecanismo de asignación de Shapley e
Shubik [7], que segue os p incipios de Gale-Shapley, pe o inco po a unha a iable que ep esen a
o alo que unha das pa es ob én ao se empa ellada con ou a, ademais de pe mi i pagos en e
indi iduos.
An es de nada, p ocede ase a desc ibi un mecanismo ípico de subas a de múl iples obxec os
con puxas seladas, é dici , onde os o e en es p esen an as súas puxas sen coñece as puxas do
es o de pa icipan es ( adicionalmen e acíase po esc i o). Is o pe mi i anos en ende mello
a eo ía de subas as, ademais de es uda os p imei os in en os de busca o mello mecanismo de
subas as posibles.
De inición 4.1 (Subas a).Sexan npos o es e kobxec os al que n>k. Cada pos o con a cun
25
26 4. Mecanismo Xe al de Subas a
Figu a 4.1: Exemplo de ocos de anuncios que son subas ados nunha búsqueda no mo o de
búsqueda Google.
alo ij ≥0∀i∈ {1, ..., n}, j ∈ {1, ..., k}que lle asigna a cada un dos obxec os, aínda que é
ecuen e a opa subas as nas que os obxec os son iguais, polo que se usa á a no ación ipa a
ab e ia . Po ou a pa e, o endedo pode de ini un p ezo de ese a ij ≥0∀i∈ {1, ..., n}, j ∈
{1, ..., k}, que se á o p ezo mínimo polo que lle es a á dispos o a ende o obxec o jao pos o i.
De no o, o máis ecuen e se á que o p ezo de ese a sexa equi alen e pa a odos os pos o es,
polo que se ab e ia á coa no ación jpa a algúns dos exemplos p e ios, aínda que es e non se á
o caso pa a o algo i mo que se desc ibi á ao longo do capí ulo. Finalmen e, cada pos o iindica á
a súa puxa mij polo obxec o j,mij < ij, que amén pode se is o como o máximo p ezo que
es á dispos o a paga polo obxec o j.
Unha ez con amos con es es da os de en ada, que son os que as dúas pa es poden con ola ,
pode anse de ini ou os dous pa áme os. Po unha pa e, de ínese pij coma o p ezo que o pos o i
paga polo obxec o j. Es e depende á p incipalmen e das puxas ealizadas mij, e, dado un obxec o
j, o seu alo se á 0 pa a calque a pos o que non gañase a puxa po ese obxec o. Do mesmo xei o,
emos a u ilidade uij que un pos o iob én a pa i do obxec o j. A u ilidade pode ep esen a
di e sos concep os, sendo o bene icio ob ido a pa i do obxec o un dos seus signi icados máis
comúns. Finalmen e, a subas a con a á cunha asignación A, que se á un g upo de pa es o deados
(i, j)i∈ {1, ..., n}, j ∈ {1, ..., k}que ep esen a á que o obxec o j oi adxudicado ao pos o i.
27
A pa i dos mecanismos de Gale-Shapley e Shapley-Shubik desen ol é onse a ios mecanis-
mos de subas a, en e os que des acan dous: GSP (Segundo p ezo de puxa xe al) [8] e VCG
(Vick ey–Cla ke–G o es) [9]. Es es dous mecanismos e as súas a iacións son as bases das sub-
as as en In e ne mode nas, es ablecéndose na maio ía de mo o es de búsquedas as desbanca
ao seu p edeceso , a subas a baseada no p imei o p ezo de puxa. Es a asignaba cada oco ao
pos o que maio puxa p esen ase, cob ando un p ezo igual á puxa do pos o gañado . O p o-
blema con es e ipo de subas as de p imei o p ezo de puxa é que non p esen aban equilib io en
es a exias pu as (en eo ía de xogos, as es a exias pu as son aquelas que p opo cionan unha
de inición comple a das accións que oma un xogado , como é o caso), é dici , non exis e un pe il
de es a exia al que cada unha delas é mello que as es an es. Polo an o, as puxas poden se
axus adas de xei o dinámico dependendo do es o de pos o es, de posui es a in o mación p e io
en ío das puxas. Esencialmen e, podemos en ende es a ca ac e ís ica como a de manipulacións
de es a exias en Gale-Shapley, in oducida no capí ulo 2. Na p ác ica, is o adúcese en que
o gañado i, de sabe o es o de puxas (en pa icula da puxa do segundo pos o jque mais
o eceu), pode ía modi ica a súa puxa pa a que ose da o ma mi=mj+ϵ∀ϵ > 0, pa a pode
maximiza a súa u ilidade.
GSP xu diu como p imei a al e na i a, con ando cun p ocedemen o moi semellan e ao seu
p edeceso , pe o cada pos o coa kpuxa mais al a paga á o p ezo co esponden e á puxa do
pos o k+ 1. É dici , o pos o que mais o eceu po un oco non paga á un p ezo equi alen e á
súa puxa, senon que depende á do o ecido na segunda puxa mais al a. Non obs an e, es e ipo
de subas as ampouco é a p oba de manipulación de es a exias pa a subas as nas que o núme o
de obxec os é supe io a 1, xa que os pos o es poden modi ica as súas puxas pa a ob e uns
mello es esul ados, como se e á no exemplo a con inuación.
Pa a pode ilus a o exemplo, in oduci ase b e emen e a de inición do mecanismo do GSP,
en pa icula no con ex o no que se usa nas subas as de anuncios, que pos e io men e se e á que
ga da semellanzas co mecanismo cube o nes e apa ado. Sexan npos o es e kocos. Nes e caso
odos os ocos conside a anse iguais, polo que cada pos o de e mina á un alo e p ezo máximo
xe al, e só se á no p ezo no que se e á en con a a p obabilidade de que un usua io aga click
nese oco pa a dis ingui os ocos. Cada pos o iasigna un alo po click i, así como o máximo
p ezo que es á dispos o a paga mi, que se á a súa puxa. Cada pos o paga á un p ezo po click
pise gana a puxa, men es que ese p ezo se á 0 se a pe de. Finalmen e, αjé o núme o de clicks
que un oco ecibe po unidade de empo. A pa i des es da os, de ini ase a u ilidade uob ida
po un pos o iao que se lle asigna o oco icomo ui=αi( i−pi).
Exemplo 4.2. Sexan n= 3 pos o es e k= 2 ocos. O p imei o oco ecibe 100 clicks po ho a,
men es que o segundo ecibe 50, é dici , α1= 100, α2= 80. Os alo es asignados polos pos o es
son os seguin es: 1= 10, 2= 7, 3= 2. Po ou a pa e, supoñamos que os p ezos máximos
dispos os a paga son os mesmos que o alo , é dici , m1= 1= 10, m2= 2= 7, m3= 3= 2,
34 4. Mecanismo Xe al de Subas a
Figu a 4.2: Un empa ellamen o se á es able semp e que un pos o i∈Ie un oco j∈J eñan
espec i amen e unha u ilidade uie un p ezo pj al que as coo denadas (pj, ui)son ales que o
pun o es á ó a da á ea de co azul.
4.2. Algo i mo 35
A con inuación p esen a anse as de inicións dos concep os asociados ao p ocedemen o i e a i o
que se p esen a á pos e io men e.
De inición 4.13. (G a o de ac ualización). Dada unha subas a ( , m, )o g a o de ac ualización
pa a unha asignación (u, p, µ)é un mul ig a o bipa i o di eccionado, no que µ∈I×J∪ {j0},
sendo j0o oco simulado. Es e g a o con a con 5 ipos de a is as: pa a cada pos o ie pa a cada
oco j∈J emos que:
Exis e unha a es a ca a adian e dende ia a jse pj∈[ ij, mij].
O seu peso asociado se á ui+pj− ij. Como se e á pos e io men e, es e ipo de a es a
i ase c eando a medida que os p ezos se aian ac ualizando segundo os empa ellamen os.
Exis e unha a es a ca a a ás dende ja a ise (i, j)∈µ. O seu peso asociado se á ij −ui−pj.
O g a o de ac ualización non con a con ningunha des as a es as nun p imei o momen o,
senon que se i án engadindo segundo se engadan empa ellamen os en cada i e ación.
Exis e unha a es a de p ezo de ese a dende ia a jse ui+ ij > ij emij > ij.
O seu peso asociado se á de ui+ ij − ij. Es e ipo de a es a co espóndese aos empa ella-
men os nos que o pos o es á in e esado no oco e a súa u ilidade é su icien e pa a asegu a se
de que o empa ellamen o non se á bloquean e.
Exis e unha a es a de p ezo de máximo dende ia a jse ui+mij > ij emij > ij.
O seu peso asociado se á de ui+mij − ij. Es e ipo de a es a co espóndese aos empa-
ellamen os nos que o pos o es á in e esado no oco e a u ilidade asociada á asignación é
su icien e pa a excede a di e enza en e p ezo máximo e o seu alo . No caso de segui
unha es a exia de op imiza ganancias, es as a es as es a án p esen es semp e que o pos o
eña unha u ilidade posi i a.
Exis e unha a es a e minal dende ia a j0se ui>0.
O seu peso asociado se á de ui. Todo pos o con u ilidade posi i a con a á con es e ipo
de a es a.
De inición 4.14. (Camiño al e nado). Un camiño al e nado P no g a o de ac ualización é unha
n- upla (i0, j1, i1, j2, ..., il, jl+1). Comeza cun pos o non asignado i0cunha u ilidade ui0>0, e
segue cunha secuencia de a es as ca a adian e e a es as ca a a ás, de o ma que os elemen os
da upla sexan, al e na i amen e, pos o es e ocos. Finalmen e, o úl imo oco debe se engadido a
pa i dunha a es a de p ezo de ese a, de p ezo máximo ou e minal. Todos os é ices deben
de se dis in os, excep uando o úl imo, que pode apa ece mais dunha ez.
De inición 4.15. O peso w(P)dun camiño al e nado de ínese como a suma dos pesos das súas
a es as.
36 4. Mecanismo Xe al de Subas a
De inición 4.16. Sexa i0un pos o e sexa yun é ice calque a dun g a o de ac ualización G.
De ínese a dis ancia d(i0, y)como o núme o de é ices pe co idos em G dende i0a a yusando
exclusi amen e a es as ca a adian e e ca a a ás. Se non é posible alcanza o é ice ydende i0,
a dis ancia se á ∞.
De inición 4.17 (Posición xe al).Unha subas a ( , m, )es a en posición xe al se, pa a cada
pos o i, non exis en 2 camiños al e nados no g a o de ac ualización que empecen no pos o i,
sigan unha se ie de a es as ca a adian e e ca a a ás e ema en nunha a es a de p ezo de ese a,
p ezo máximo ou e minal e eñan o mesmo peso.
No a: Usa ase a no ación G( )en dis in os elemen os da subas a pa a ace e e encia á
i e ación .
Inicialización. Sexa unha subas a ( , m, )de npos o es e kocos. O algo i mo comeza cunha
asignación balei a (u0, p0, µ0), onde cada un dos elemen os é inicializado do seguin e xei o:
u(0)
i=B∀i∈I, sendo B > max{ ij |(i, j)∈I×J}.
p(0)
j= 0 ∀j∈J.
µ(0) =∅.
I e ación :
Sexa (u , p , µ )unha asignación e G o g a o de ac ualización co esponden e á i e ación
do algo i mo Asignación Es able. A i e ación do algo i mo consis i á nos seguin es pasos.
1. Busca o camiño al e nado de cus e mínimo P de G . No caso de non exis i ningún camiño
al e nado, o algo i mo de ense e de ol e a asignación (u( ), p( ), µ( )). Sexa w( )(P)o peso asociado
aPe sexa
P= (i0, j1, i1, j2, i2, ..., jl, il, jl+1)pa a un l≥0.
2. Calculase o ec o de dis ancias d( )∈Rn+k al como se indica en 4.16. É posible usa
o algo i mo de Dijks a pa a calcula es e ec o de dis ancias, xa que, po de inición, odas
as a es as do g a o de ac ualización se án non nega i as. Do mesmo xei o, os é ices que non
es án empa ellados só poden se alcanzados desde i0, o é ice desde o que se es án a calcula as
dis ancias, polo que só habe á, como moi o, 2k é ices alcanzables en cada i e ación. Po iso,
como Dijks a en un cus e compu acional igual ao cad ado dos é ices alcanzables, sabemos
que a complexidade des e paso se á O(k2).
3. Calculase o no o ec o de u ilidades:
u( +1)
i=u( )
i−m´ax(w( )(P)−d(i0, i),0) ∀i∈I. (4.11)
4.2. Algo i mo 37
4. Calculase o no o ec o de p ezos:
p( +1)
j=p( )
j−m´ax(w( )(P)−d(i0, j),0) ∀j∈J. (4.12)
No caso de que a úl ima a es a de Psexa do ipo p ezo de ese a, o p ezo do úl imo oco
jl+1 i á dado po p( +1)
l+1 = m´ax(p( +1), iljl+1 ).
5. Finalmen e, ac ualízase a asignación µ( )ao longo de P pa a ob e a no a asignación µ( +1).
Dis inguimos 3 casos dependendo da na u eza do ipo de a es a inal:
A es a e minal: se P acaba nunha a es a e minal, emos que jl+1 =j0, é dici , é o oco
simulado. Des a o ma, empa éllase cada pos o ixco oco jx+1 ∀x∈ {0,1, ..., l −1}. O
pos o ilqueda desempa ellado.
A es a de p ezo máximo: considé anse dous subcasos.
Caso 1 jl+1 =jlO caso é equi alen e ao da a es a e minal.
Caso 2 jl+1 =jlA asignación man ense igual, µ( )=µ( +1).
A es a de p ezo de ese a: considé anse es subcasos.
Caso 1 ∄i: (i, jl+1)∈µ( ).
∀x∈ {0, ..., l}, empa ella o pos o ixco oco jx+1.
Caso 2 ∃i: (i, jl+1)∈µ( )e iljl+1 ≤p( +1)
jl+1
Nes e caso, a asignación man ense igual µ( )=µ( +1).
Caso 3 ∃il+1 : (il+1, jl+1)∈µ( )e iljl+1 > p( +1)
jl+1 .
Se Pé un camiño al que Pnon isi a jl+1 dúas eces, elimina ase o empa ellamen o, de
xei o que (il+1, jl+1)/∈µ( +1). A con inuación, empa éllanse o es o de pos o es e ocos de
P do mesmo xei o que o is o pa a o caso de a es as e mianis.
Se P isi a jl+1 dúas eces, e emos que jl+1 =jdpa a algún d∈ {1, ..., l −1}. Des e
xei o, os elemen os inais de P o man un ciclo con polo menos 2 pos o es e 2 ocos. Polo
an o, simplemen e se p ocede á a empa ella os elemen os de P a pa i do índice d, é
dici , p ocedese a empa ella ixcon jx+1 pa a x∈ {d, d + 1, ..., l}.
Unha ez o in oducido, e anse algunhas das p opiedades coas que con a es e algo i mo. En
p imei o luga , demos a anse unha se ie de in a ian es que pe mi i án de i a as p opiedades
que o algo i mo desc i o p esen a.
38 4. Mecanismo Xe al de Subas a
4.2.1. In a ian es
(A1) A asignación (u( ), p( ), µ( ))xe ada na i e ación é es able pa a a subas a ( , m, ).
(A2) ∀(i, j)∈µ( ),u( )
iep( )
j e i ican as condicións de asignación ac ible.
(A3) pj= 0 ∀j∈J:∄i∈I(i, j)∈µ.
(B1) mij ≥0eu( )
i+mij = ij ⇒(i, j)/∈µ( ).
(B2) mij ≥0eu( )
i+ ij = ij ⇒(i, j)∈µ( )ou p( )
j≥ ij.
Demos acións dos in a ian es. Todos os in a ian es poden se demos ados po indución,
como se e á a con inuación. Comenza anse demos ando os in a ian es (B1) e (B2), xa que se
usa án nas demos acións de (A1), (A2) e (A3).
Demos ación (B1).
Caso base, = 0. T i ial, non exis e ningún empa ellamen o.
Caso +1. Sexa iun pos o in e esado no oco j al que non es án empa ellados, (i, j)/∈µ( ).
Temos que mij ≥0eu( +1)
i+mij = ij. No algo i mo só é posible empa ella un oco e un
pos o se es es es án p esen es nun camiño al e nado de xei o consecu i o. Á súa ez, pa a
que is o oco a se á p eciso que exis a unha a es a que una os dous é ices. Vexamos que,
nas condicións des e caso, non exis e a es a de ningún dos ipos:
A es a e minal. jnon é o oco simulado, polo que non pode exis i unha a es a des e
ipo.
A es a de p ezo máximo. Unha das condicións necesa ias pa a es e ipo de a es as é
u( +1)
i+mij > ij. Como emos que u( +1)
i+mij = ij, non se pode da es a a es a.
A es a de p ezo de ese a. mij > ij eu( +1)
i+mij = ij ⇒u( +1)
i+ ij < ij, polo
que non se pode da es a a es a.
A es a ca a a ás. T i ial, xa que (i, j)/∈µ.
A es a ca a adian e. Ve emos que, no caso de da se es a a es a, e ía peso nega i o.
Pa a da se es a a es a, en que da se que pj∈[ ij, mij). En pa icula , pj< mij. Pola
condición u( +1)
i+mij = ij, emos que u( +1)
i− ij =−mij. Polo an o, o seu peso
asociado se ía ui+pj− ij =pj−mij <0, xa que 0≤pj< mij.
Des e xei o, non exis e ningunha a es a en e i e j e (i, j)/∈µ( +1).
Demos ación (B2).
4.2. Algo i mo 39
Caso base, = 0. T i ial, non se dan as condicións en ningún debido ao ec o de u ilidades
u(0)
i∀i∈I.
Caso + 1. Se a pa ella de pos o e oco xa ose empa ellada nalgunha i e ación an e io
xa se e i ica ía, pos o que (i, j)∈µ( )⇒(i, j)∈µ( +1). Se (i, j)/∈µ( ), se ía p eciso
dis ingui 2 casos:
Caso u( )
i+ i,j = i,j. Po hipó ese de indución, como (i, j)/∈µ( ), en ón emos que se
e i ica p( )
j≥ i,j. Como p( +1)
j≥p( )
j, as condicións do lema es a ían sa is ei as.
Caso u( )
i+ i,j = i,j. Como u( +1)
i≤u( )
i, emos que a desigualdade se ía u( )
i+ i,j ≥
i,j. Do mesmo xei o, combinando coa ac ualización da u ilidade, e iamos
u( )
i−w( )(P) + d( )(i0, i) + ij = ij,
polo que, combinado coa desigualdade an e io , conclúese que w( )(P)> d( )(i0, i), is o é,
exis i á algunha a es a dende ia a algún oco, e es a non se á a única p esen e no camiño,
pos o que non é igual ao peso. Así mesmo, nas condicións dadas, exis i ía unha a es a de
p ezo de ese a dende ia a j. De se es a a a es a inal do camiño al e nado, e iamos que
(i, j)se ían empa ellados, seguindo o p ocedemen o de ac ualización da asignación pa a
camiños al e nados de p ezo de ese a.
Demos ación (A1).
Caso base, = 0. Como u(0)
i=B∀i∈Iep(0)
j= 0 ∀j∈J. Des e xei o, e emos que
ui+pj=B+ 0 ≥ i,j, polo que se e i ica (3).
Caso + 1. Considé anse 3 casos dis in os pa a cada empa ellamen o (i, j):
Caso 1: p( )
j∈[ i,j, mi,j].(u( ), p( ), µ( ))é es able pola hipó ese de indución, polo que
u( )
i+p( )
j≥ i,j. Nes e caso p esén anse 2 posibilidades:
Se d( )(io, i)≥w( )(P), a u ilidade non se ac ualiza á debido á ó mula do paso 3 do
algo i mo, polo que u( +1)
i) = u( )
iep( +1)
j≥p( )
j, polo que se e i ica 4.8.
Po ou a pa e, se d( )(io, i)< w( )(P), a u ilidade e o p ezo ac ualiza anse segundo as
ó mulas desc i as no algo i mo:
u( +1)
i=u( )
i−(w( )(P)−d( )(io, i)).
p( +1)
j=p( )
j−(w( )(P)−d( )(io, j)).
Ademais, como exis e unha a es a ca a adian e dende ia a j, emos que
d( )(io, j)≤d( )(io, i)+(u( )
i+p( )
j)− i,j.
40 4. Mecanismo Xe al de Subas a
Polo an o, susi uindo en 4.8
u( +1)
i+p( +1)
j≥u( )
i−w( )(P) + d( )(io, i) + p( )
j+w( )(P)−d( )(io, i)−u( )
i−p( )
j+ ij
= ij ≥ ij.
Caso 2: p( )
j≥mij. A condición 4.9 e i ícase i ialmen e.
Caso 3: p( )
j< ij eies á in e esado en j.u( )
ié es able pola hipó ese de indución, polo que
u( )
i e i ica 4.10. Dis ínguense 2 opcións aquí:
Se d( )(io, i)≥w( )(P), a u ilidade non se ac ualiza á debido á ó mula do paso 3 do
algo i mo, polo que u( +1)
i=u( )
ieu( +1)
isa is ai 4.10. Se d( )(io, i)≥w( )(P), en ón
u( +1)
i=u( )
i−(w( )(P)−d( )(io, i)), men es que, g azas á a es a de p ezo de ese a de i
aj, emos que
w( )(P)≤d( )(io, i)+(u( )
i+p( )
j)− ij,
polo que, sus i uindo, en (5), emos que u( )
i) amén a sa is ai. A p esenza da a es a de
p ezo de ese a pódese ob e g azas ás in a ian es (B1) e (B2).
Demos ación (A2).
Caso base, = 0. T i ial, a inicialización aise de al xei o que p(0)
j= 0 ∀j∈J.
Caso +1. Tal e como se pode e na ac ualización dos p ezos (paso 4 do algo i mo), emos
que p( +1) ≥p( ). Sexa empa ellamen o (i, j)∈G( ), no que exis e unha a es a ca a a ás
dende ja a i. Pola hipó ese de indución, (u( ), p( ), µ( ))sa is ai (A2), polo que, debido á
de inición de a es a ca a a ás, es a e á peso 0, e d( )(io, i) = d( )(io, j).
(Demos ación A3).
Caso base, = 0. T i ial, p(0)
j= 0 ∀j∈J.
Caso + 1:
Como sabemos polo paso 4 do algo i mo, p( +1) ≥p( ). Os ocos empa ellados en µ( ) amén
es a án empa ellados en µ( +1). Do mesmo xei o, como o empa ellamen o é ealizado a
a és dun camiño al e nado, no que, sal o a úl ima a es a, o es o son ca a adian e ou
ca a a ás, como moi o empa ella ase 1 oco no o, que non es aba empa ellado an es.
Vexamos que o es o dos ocos non se poden alcanza dende o pos o inicial i0dun camiño
4.2. Algo i mo 41
al e nado Pen G( ). Pa a calque a oco jnon empa ellado en +1, po hipó ese de indución,
p( )= 0. Do mesmo xei o, ∀i∈I, i,j >0debido á suposición de posición xe al, polo que
non exis e a es a ca a adian e en jepj= 0.
Lema 4.18. A asignación (u( ), p( ), µ( ))ob ida polo algo i mo Asignación Es able é ac ible e
es able.
Demos ación. O in a ian e (A1) asegu a a es abilidade da asignación.
As condicións 4.6 e 4.7 da ac ibilidade eñen dadas do in a ian e (A2). Como o algo i mo
ema a cando non exis en mais camiños al e nados, a u ilidade se á u( )
i= 0 pa a odo pos o
non empa ellado, xa que, de non se así, exis i ía un camiño al e nado debido á a es a e minal
dende ia a j0.
Lema 4.19. O algo i mo Asignación Es able ema a en, como moi o, n(2k+ 1) i e acións.
Demos ación. Na i e ación inicial, o g a o de ac ualización G(0) en, como moi o, nk a es as
de ese a, nk a es as de p ezo máximo e na es as de p ezo e minal. Ve emos como, en cada
i e ación, o núme o de a es as ese educida nunha unidade.
Sexa unha i e ación do algo i mo Asignación es able. Vexamos que, dado un camiño al e na-
do P= (i0, j1, i1, ..., jl, il, jl+1), a a es a (i, j)=(il, il+1)non apa ece á no g a o de ac ualización
G( +1). Sepa amos ago a en casos:
Caso 1: Se (i, j)é unha a es a e minal, en ón w( )(P) = d( )(i0, i) + u( )
i, polo que u( +1)
i=
u( +1)
i−(w( )(P)−d( )(i0, i)) = 0.
Caso 2: Se (i, j)é unha a es a de p ezo máximo, en ón w( )(P) = d( )(i0, i)+(u( )
i+mij − ij),
polo que u( +1)
i+mij =u( )
i−(w( )(P) = d( )(i0, i)) + mij = ij.
Caso 3: Se (i, j)é unha a es a de p ezo máximo, en ón w( )(P) = d( )(i0, i)+(u( )
i+ ij − ij),
polo que u( +1)
i+ ij =u( )
i−(w( )(P) = d( )(i0, i)) + ij = ij.
Como as u ilidades non aumen an e os p ezos non se en educidos en ningunha pa e do
algo i mo, a a es a (i, j)non ol e á apa ece en ningunha i e ación ˆ
> .
Des e xei o, e emos que o algo i mo ema a á, como moi o, en nk +nk +n=n(2k+ 1)
i e acións.
Lema 4.20. Sexa ( , m, )unha subas a en posición xe al, e sexa (u′, p′, µ′)unha asignación
ac ible e es able. Pa a calque a i e ación do algo i mo Asignación Es able, e emos que u′
i≤u( )
i
∀i∈Iep′
j≥p( )
j∀j∈J.
42 4. Mecanismo Xe al de Subas a
Demos ación. Es a demos ación, de ca ac e écnico, non se inclui á debido á súa ex ensión,
pe o pode á consul a se en [6].
Teo ema 4.21. Se unha subas a ( , m, )es á en posición xe al, e á un empa ellamen o es a-
ble óp imo pa a os pos o es único. Es e empa ellamen o pode se a opado cunha complexidade
compu acional de O(nk3).
Demos ación. Sexa unha subas a ( , m, )en posición xe al. O algo i mo Asignación Es able
p oduci á como esul ado un empa ellamen o (u′, p′, µ′), que é es able e ac ible polo lema 4.18.
Aplicando o lema 4.20 ao empa ellamen o an e io despois da úl ima i e ación do algo i mo
implica que u′, ′, µ′é p e e ido a calque a asignación es able po calque a pos o , polo que se á
óp imo pa a os pos o es.
Po ou a pa e, emos que o núme o máximo de i e acións se á n(2k+ 1) polo lema 4.19.
Po ou a pa e, g azas a que os pesos do g a o de ac ualización son non nega i os, é posible
usa Dijks a pa a calcula as dis ancias, que en unha complexidade compu acional de O(k2),
sendo k o núme o de é ices. Des e xei o, como o Dijks a se usa en cada unha das i e acións, e
pa a o cálculo da complexidade compu acional elimínanse as cons an es, e emos que es a se á
O(nk3).
Finalmen e, e isa ase a manipulabilidade de es a exias po pa e dos pos o es. En pa -
icula , p oba ase un esul ado en o no á manipulación de es a exias, an o pa a pos o es
indi iduais como g upos, de xei o simila á que xa se iu p e iamen e pa a Gale-Shapley.
Lema 4.22 (Lema de Hwang).Sexa (u, p, µ)unha asignación ac ible pa a unha subas a ( , m, )
en posición xe al, e sexa (u∗, p∗, µ∗)a asignación óp ima pa a os pos o es pa a esa subas a.
De inimos
ˆ
I={i∈I|ui> u∗
i}.
Se ˆ
I=∅, en ón exis i á un pa bloquean e (i, j)∈(I ˆ
I)×J.
Demos ación. De no o, a demos ación des e lema se á undamen almen e écnica, sepa ando
en casos e emp egando écnicas semellan es ás dou as demos acións xa de alladas, polo que
non se inclui á nes a memo ia. Es a pode consul a se en [6].
Teo ema 4.23. Non é posible que un pos o ou unha ag upación de pos o es manipulen as súas
puxas de xei o que cada pos o na ag upación se bene icie de xei o es ic o da manipulación.
Demos ación. Sexa unha ag upación de pos o es ˆ
Ique p e enden bene icia se de men i coas
súas p e e encias. Sexa a ipla ( , m, )a subas a que ep esen a as p e e encias eais pa a odos
os pos o es, e sexa a ipla (ˆ , ˆm, )a subas a que ep esen a as puxas modi icadas polo g upo ˆ
I.
4.2. Algo i mo 43
Nó ese que os p ezos de ese a son os mesmos, xa que non son con olados polos pos o es,
eˆ i= i,ˆmi=mi∀i /∈ˆ
I.
Sexa (u, p, µ)a asignación óp ima pa a os pos o es na subas a (ˆ , ˆm, ), que se á ac ible, xa
que as es icións de ac ibilidade son as mesmas pa a as dúas subas as no caso de que i∈I ˆ
I,
men es que, pa a i∈ˆ
I, e emos que e i ica que pj≤mij pa a odo (i, j)∈µ. Is o é di ec o,
xa que, de non da se, (ˆ , ˆm, )non se ía óp imo pa a os pos o es, xa que semp e habe á ou o
empa ellamen o no que non se excedan os p ezos máximos e sexa óp imo pa a os pos o es.
Como (u, p, µ)é ac ible, é posible usa o lema 4.22. Des e xei o, emos que exis e un pa
(i, j)∈(I ˆ
I)×Jque sexa bloquean e pa a a subas as ( , m, ).
50 5. Es udo numé ico mecanismo xe al de subas a
3. u(6) = (6.0,7.0,1.0).
4. p(6) = (2.0,0.0).
5. T á ase do caso de p ezo de ese a. Como o oco j1si que es á empa ellado en µ(5), emos que
mi a o p ezo de ese a 3,1. Como 3,1> p1, o empa ellamen o man ense 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)
.
I e ación 6:
1. P= (i3, j0),w(P) = 1.0.
2. Dis ancias ao é ice i3:
Pos o es: 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. T á ase do caso de a es a e minal. O úl imo oco p esen e en Pnon se empa ella. ao a a se
Pdun camiño con lonxi ude 2, o empa ellamen o man ense igual.
µ(7) ={(i2, j1),(i1, j2)}.
No o g a o de ac ualizació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)
.
I e ación 7:
1. Non exis e ningún camiño al e ando P, polo que o algo i mo de én a súa execución.
A asignación inal (u, p, µ)é:
U ilidades: u= (6.0,7.0,0.0).
P ezos: p= (2.0,0.0).
Empa ellamen o: µ={(i2, j1),(i1, j2)}.
Unha ez comp endido o uncionamen o do algo i mo, p ocede ase a de alla o expe imen o
que puxo a p oba o algo i mo, pe mi indo de i a dis in as conclusións sob e as súas ca ac e ís-
icas e a súa e iciencia.
5.2. Xe ación de da os 51
5.2. Xe ación de da os
Ao longo des a sección, habe á de alles de implemen ación nos que non se p o undiza á
debido a que xa o on cube os no Capí ulo 3. A pesa de que os conxun os de da os con an con
ca ac e ís icas dis in as, a base da xe ación dos da os se á común.
Nes e caso, os amaños de p oblema escollidos o on N={3,5,8,10,20,50,100}. O p inci-
pal mo i o de usa amaños mais pequenos que no es udo de Gale-Shapley é a complexidade
compu acional do mesmo. Des e xei o, de usa amaños da mesma o de, os empos de execución
comeza ían a dispa a se. Po ou a pa e, nun p imei o momen o usa ase o caso pa icula de que
o núme o de pos o es e o núme o de ocos é o mesmo, n=k, p incipalmen e po unha cues ión
de simplicidade, pe o pos e io men e es es pa áme os i anse a iando. Do mesmo xei o, o nú-
me o de i e acións ealizadas nes e caso amén se á unha o de in e io , epe indo cada execución
pa a cada amaño 100 eces. O sc ip que oi emp egado pa a es e expe imen o es á p esen e no
código B.3.
Finalmen e, pa a p oduci os alo es iniciais pa a cada pos o e oco usa ase unha dis ibución
uni o me pa a xe a es es núme os. Des e xei o, o alo , p ezo máximo e p ezo de ese a se án
xe ados con de andi a dis ibución seguindo as seguin es es icións:
0.0≤ ij < mij ≤ ij ≤10.0∀i, j ∈ {1, ..., n}.
A in uición de ás des as es icións se á o za que cada un dos pos o es es ea in e esado en
odos os ocos, po iso o p ezo que puxa é supe io ao de ese a, ademais de pode op a po
dis in as es a exias, po iso a súa puxa pode se in e io ao alo eal que o pos o lle asigna ao
oco.
O código do sc ip implemen ado en Py hon emp egado pa a a xe ación dos conxun os de
da os amósase no código B.1.
5.3. Resul ados
A implemen ación do algo i mo do mecanismo xe al de subas as emp egado pa a os expe i-
men os pode consul a se no código B.2.
5.3.1. Calidade dos empa ellamen os
En p imei o luga , an es de p ocede a e isa os p ezos e u ilidades ob idas, e i ica ase que
o algo i mo uncionou como e a espe ado. Ao a a se dunhas condicións nas que calque a dos
52 5. Es udo numé ico mecanismo xe al de subas a
pos o es con a cunha puxa supe io ao p ezo de ese a de calque a dos ocos, é de espe a que
odos os pos o es sexan empa ellados con un oco.
Figu a 5.2: Media de empa ellamen os pa a dis in os amaños de p oblema.
Como se pode obse a na igu a 5.2, na que se ep esen a a media do núme o de empa ella-
men os p oducidos no expe imen o pa a cada un dos amaños de p oblema. Aí podemos obse a
como es e alo é exac amen e igual ao amaño do p oblema, polo que podemos e i ica a su-
posición inicial.
A pa i de aí, es uda emos a dis ibución das u ilidades e dos p ezos inais. Ao a a se de
dous pa áme os xe ados a pa i dunha dis ibución uni o me e cunhas co as es ic i as, un
pode á pensa que non debe ían es a moi espallados.
Po unha banda, na igu a 5.3 pódese obse a un diag ama de caixa que amosa a dis ibución
das medias dos p ezos. Debido ás es icións nos p ezos de ese a, conside ablemen e in e io es
ás puxas e alo es, es es son ela i amen e pequenos. Do mesmo xei o, a medida que se aumen a
o amaño do p oblema, a di e enza en e a media de p ezos é cada ez mais pequena, polo que a
maio ía de pos o es paga án un p ezo semellan e polo oco. Des e xei o, o p ezo de cada oco xa non
i á an in luenciado pola di e enza en e os alo es que os pos o es lle asigna on inicialmen e.
Po ou a pa e, a igu a 5.4 amosa un diag ama de caixa coa dis ibución das medias das
5.3. Resul ados 53
Figu a 5.3: Dis ibución de p ezos pa a dis in os amaños de p oblema.
u ilidades. De no o, pode obse a se como es as u ilidades son ele adas, p e o do máximo impos o
inicialmen e, sendo mais uni o mes a medida que se achega a amaños de p oblema mais ele ados.
Is o é consecuencia di ec a da dis ibución dos p ezos, xa que, ao se mais ben baixos, a u ilidade
ende á a non baixa demasiado en cada i e ación.
Figu a 5.4: Dis ibución das u ilidades pa a dis in os amaños de p oblema.
A con inuación, ealizouse ou o es udo ixando o núme o de pos o es a 30, e a iando o
54 5. Es udo numé ico mecanismo xe al de subas a
pa áme o k, o núme o de ocos. Comple á onse p obas ∀k∈ {1, ..., 30}, de no o ealizando 100
i e acións pa a cada un dos alo es. O sc ip emp egado nes e caso es á p esen e no código B.4.
Figu a 5.5: U ilidade o al segundo o núme o de ocos dispoñibles.
A pesa de que si que se pode obse a na eg esión lineal ep esen ada na igu a 5.5 a
endencia c ecen e da u ilidade o al segundo o núme o de ocos dispoñibles, es a non é an
e iden e pa a alo es baixos. Pa a eses casos de núme os de ocos baixos, a dispe sión dos alo es
da u ilidade le a a con a con alo es de u ilidade o al mais al os que os que se a opan p e o do
núme o de 10 ocos. Se á a pa i de aí cando o núme o de ocos sexa o su icien emen e ele ado
pa a con a es a de andi a dispe sión.
5.3.2. E iciencia do algo i mo
De xei o simila ao es udado en Gale-Shapley, nes e caso amén nos cen amos en comp oba
o núme o de i e acións que o algo i mo p ecisa pa a a súa inalización, o que pe mi i á de e mina
a súa complexidade compu acional.
A igu a 5.6 ep esen a con pun os as i e acións ealizadas polo algo i mo nas dis in as e-
pe icións do expe imen o en escala loga í mica. A liña azul ep esen a a co a supe io , a cu a
n(2k+ 1), que, ao a a se do caso pa icula de n=k, es a cu a se á da o ma 2n2+n. Final-
men e, a liña de co neg o ep esen a a cu a ob ida a pa i dunha eg esión lineal calculada a
pa i do núme o de i e acións.
5.3. Resul ados 55
Figu a 5.6: Núme o de i e acións segundo o amaño do p oblema.
Como se pode obse a , en ningún momen o o núme o de i e acións se ace ca ao núme o
máximo de i e acións, si uándose a mei ande pa e dos pun os mais ce ca da unción iden idade
que da co a máxima. Is o é debido a que, pa a alcanza es a co a, se ía p eciso con a cunha
si uación moi pa icula , na que cada un dos pos o es p esen e unha a es a de cada ipo a cada
un dos ocos, e en cada i e ación só pode ía elimina se unha a es a.
56 5. Es udo numé ico mecanismo xe al de subas a
Apéndice A
Código do es udo numé ico de
Gale-Shapley
A.1. Xe ación dos conxun os de da os
1impo andom
2impo sys
3
4i __name__ == ’__main__’:
5
6n= in (sys.a g [1])
7n_lis =[i o iin ange(n)]
8
9 = open(’da ase . x ’,’w’)
10
11 .w i e(s (n) + ’ n’)
12
13 o _in ange(n):
14 andom.shu le(n_lis )
15 o iin ange(n-1):
16 .w i e(s (n_lis [i]) + ’ ’)
17 .w i e(s (n_lis [-1]) + ’ n’)
18
19 o _in ange(n):
20 andom.shu le(n_lis )
21 o iin ange(n-1):
22 .w i e(s (n_lis [i]) + ’ ’)
23 .w i e(s (n_lis [-1]) + ’ n’)
24
25 .close()
Código A.1: Código usado pa a a xe ación dos conxun os de da os.
1
2 A. Código do es udo numé ico de Gale-Shapley
A.2. Código dos algo i mos
1impo sys
2impo andom
3
4de s able_ma ch(n, men_p e e ences, women_p e e ences):
5men_index =[0 o _in ange(n)]
6 ee_men = se ([i o iin ange(n)])
7women_p oposals =[[] o _in ange(n)]
8ac i e_p oposals =T ue
9n_i e =0
10 while len( ee_men) > 0:
11 n_i e +=1
12 o min ee_men:
13 cu _choice =men_p e e ences[m][men_index[m]]
14 men_index[m] +=1
15 women_p oposals[cu _choice].append(m)
16 o win ange(n):
17 p= len(women_p oposals[w])
18 i p > 1:
19 cu _w_p e =women_p e e ences[w]
20 i s _index =cu _w_p e .index(women_p oposals[w][0])
21 o iin ange(1,p):
22 cu _index =cu _w_p e .index(women_p oposals[w][i])
23 i cu _index < i s _index:
24 women_p oposals[w][0], women_p oposals[w][i] =women_p oposals[w][i],
women_p oposals[w][0]
25 ee_men.add(women_p oposals[w][i])
26 i s _index =cu _index
27 women_p oposals[w] =[women_p oposals[w][0]]
28
29 i p>0and women_p oposals[w][0] in ee_men:
30 ee_men. emo e(women_p oposals[w][0])
31
32 ma ches =[(x[0],i) o (i,x) in enume a e(women_p oposals)]
33
34 e u n (ma ches, n_i e )
35
36 de ge _sa is ac ion(n, p e e ences, ma ch):
37 o al =0
38
39 o iin ange(n):
40 index =p e e ences[i].index(ma ch[i])
41 indi idual_sa is ac ion =(n - index - 1)/(n-1)
42 o al +=indi idual_sa is ac ion
43 e u n o al
44
45 de ead_da ase (pa h):
46 men_p e =[]
47 wom_p e =[]
48 = open(pa h, ’ ’)
49 n= in ( . eadline())
50 o _in ange(n):
51 line = . eadline()
A.2. Código dos algo i mos 3
52 a =[in (x) o xin line.spli (" ")]
53 men_p e .append(a )
54 o _in ange(n):
55 line = . eadline()
56 a =[in (x) o xin line.spli (" ")]
57 wom_p e .append(a )
58
59 e u n (n, men_p e , wom_p e )
60
61 de andom_alloca ion(n):
62 n_ ange =[i o iin ange(n)]
63 andom.shu le(n_ ange)
64 ma ches =[(x, i) o i,x in enume a e(n_ ange)]
65 e u n ma ches
66
67 de heu is ic_alloca ion(n, m_p e ):
68 ma ched_w = se ()
69 men_ma ch =[-1 o _in ange(n)]
70 o iin ange(n):
71 cu _p e s =m_p e [i]
72 o jin ange(n):
73 i cu _p e s[j] no in ma ched_w:
74 men_ma ch[i] =cu _p e s[j]
75 ma ched_w.add(cu _p e s[j])
76 b eak
77
78 ma ches =[(i,x) o i,x in enume a e(men_ma ch)]
79 e u n ma ches
80
81 de ge _men_and_women_ma ches(ma ches):
82 women_ma ches =[i o (i,_) in ma ches]
83 men_ma ches =[-1 o _in ange(n)]
84
85 o (i,j) in ma ches:
86 men_ma ches[i] =j
87
88 e u n (men_ma ches, women_ma ches)
89
90 de w i e_ esul s( , algo, n, m_ma ches, w_ma ches, m_p e , w_p e , n_i e ):
91 women_sa =ge _sa is ac ion(n, w_p e , women_ma ches)
92 men_sa =ge _sa is ac ion(n, m_p e , men_ma ches)
93 o e all_sa =women_sa + men_sa
94 .w i e(algo + ’,’ +s (n) + ’,’ +s (o e all_sa ) + ’,’ +s (men_sa ) + ’,’ +s (women_sa ) +
’,’ +s (n_i e ) + ’ n’)
95
96
97
98 i __name__ == ’__main__’:
99 pa h =sys.a g [1]
100
101 n, m_p e , w_p e = ead_da ase (pa h)
102
103 ou _pa h =sys.a g [2]
104
10 B. Código do es udo numé ico do mecanismo xe al de subas a
205 e u n Upda eG aph{
206 g aph,
207 e minal_a : e minals
208 }
209 }
210
211 n upda e_g aph_edges(&mu sel ) {
212 le n_bidde s = sel . alues.shape()[0];
213 le n_slo s = sel . alues.shape()[1];
214 le mu e minals: Vec<Te minalNode> = Vec::new();
215
216 o iin 0..n_bidde s {
217 i sel .ma ching.u ili ies[i] > 0.0 {
218 e minals.push(Te minalNode{ e minal_edge : Some(sel .ma ching.u ili ies[i])});
219 }else {
220 e minals.push(Te minalNode{ e minal_edge: None});
221 }
222 }
223 sel .g aph. e minal_a = e minals;
224 o iin 0..n_bidde s {
225 o jin 0..n_slo s {
226 i sel .ma ching.p ices[j] >= sel . ese e_p ices[[i,j]] && sel .ma ching.p ices[j] <
sel .max_p ices[[i, j]]{
227 le o wa d_edge_ alue = sel .ma ching.u ili ies[i] + sel .ma ching.p ices[j] -
sel . alues[[i, j]];
228 i o wa d_edge_ alue > 0.0 {
229 sel .g aph.g aph[i][j]. o wa d_edge = Some( o wa d_edge_ alue);
230 }else {
231 sel .g aph.g aph[i][j]. o wa d_edge = None;
232 }
233 }
234 o (bidde , slo ) in &sel .ma ching.pai s{
235 i *bidde == i && *slo == j {
236 le backwa d_edge_ alue = sel . alues[[i, j]] - sel .ma ching.u ili ies[i] -
sel .ma ching.p ices[j];
237 sel .g aph.g aph[i][j].backwa d_edge = Some(backwa d_edge_ alue);
238 b eak;
239 }else {
240 sel .g aph.g aph[i][j].backwa d_edge = None;
241 }
242 }
243 i sel .ma ching.u ili ies[i] + sel . ese e_p ices[[i, j]] > sel . alues[[i,j]] {
244 le ese e_p ice_edge_ alue = sel .ma ching.u ili ies[i] +
sel . ese e_p ices[[i,j]] - sel . alues[[i, j]];
245 sel .g aph.g aph[i][j]. ese e_p ice_edge = Some( ese e_p ice_edge_ alue);
246 }else {
247 sel .g aph.g aph[i][j]. ese e_p ice_edge = None;
248 }
249 i sel .ma ching.u ili ies[i] + sel .max_p ices[[i, j]] > sel . alues[[i,j]] {
250 le max_p ice_edge_ alue = sel .ma ching.u ili ies[i] + sel .max_p ices[[i, j]] -
sel . alues[[i,j]];
251 sel .g aph.g aph[i][j].maximum_edge= Some(max_p ice_edge_ alue);
252 }else {
253 sel .g aph.g aph[i][j].maximum_edge = None;
B.1. Código pa a a xe ación dos da os 11
254 }
255 }
256 }
257 }
258
259 pub n upda e_g aph(&sel ) -> Upda eG aph {
260 e u n Auc ion::upda e_g aph_ alues(&sel .ma ching, &sel . alues, &sel .max_p ices,
&sel . ese e_p ices);
261 }
262
263 pub n ge _bidde s_num(&sel )->usize {
264 e u n sel . alues.shape()[0];
265 }
266
267 pub n ge _slo s_num(&sel )->usize {
268 e u n sel . alues.shape()[1];
269 }
270
271 pub n is_ easible(&sel , ma ching: Ma ching) -> bool {
272 o (i,j) in ma ching.pai s {
273 i ma ching.p ices[j] < sel . ese e_p ices[[i, j]] ||
274 ma ching.p ices[j] > sel .max_p ices[[i, j]] ||
275 ma ching.p ices[j] + ma ching.u ili ies[i] != sel . alues[[i,j]] {
276 e u n alse;
277 }
278 }
279
280 e u n ue;
281 }
282
283 n is_blocking(&sel , ma ching: &Ma ching, i: usize, j: usize)->bool {
284 e u n ma ching.u ili ies[i] + ma ching.p ices[j] >= sel . alues[[i,j]] ||
285 ma ching.p ices[j] >= sel .max_p ices[[i,j]] ||
286 ma ching.u ili ies[i] + sel . ese e_p ices[[i,j]] >= sel . alues[[i,j]];
287 }
288
289 pub n ge _blocking_pai s(&sel , ma ching: &Ma ching) -> A ay1<(usize,usize)> {
290 le blocking_pai s =ma ching
291 .pai s
292 .i e ()
293 . il e (|(i,j)| sel .is_blocking(ma ching, *i, *j))
294 .map(|(i,j)| (*i, *j));
295 e u n A ay1:: om_i e (blocking_pai s);
296
297 }
298
299 pub n is_s able(&sel , ma ching: Ma ching) -> bool {
300 le blocking_pai s = sel .ge _blocking_pai s(&ma ching);
301 e u n blocking_pai s.len() > 0;
302 }
303
304
305 n ge _unma ched_bidde s(&sel )->Vec<usize> {
306 le n= sel .ge _bidde s_num();
12 B. Código do es udo numé ico do mecanismo xe al de subas a
307 le mu se : HashSe <usize>= HashSe ::wi h_capaci y(n);
308 o (i, _) in &sel .ma ching.pai s{
309 se .inse (*i);
310 }
311 le bidde s: Vec<usize>=(0..n).collec ();
312 le a ailable_bidde s: Vec<usize>=bidde s
313 .in o_i e ()
314 . il e (|i| !se .con ains(&i))
315 .collec ();
316 e u n a ailable_bidde s;
317 }
318
319 n ge _unma ched_slo s(&sel )->Vec<usize> {
320 le m= sel .ge _slo s_num();
321 le mu se : HashSe <usize>= HashSe ::wi h_capaci y(m);
322 o (_, j) in &sel .ma ching.pai s{
323 se .inse (*j);
324 }
325 le slo s: Vec<usize>=(0..m).collec ();
326 le a ailable_slo s: Vec<usize>=slo s
327 .in o_i e ()
328 . il e (|j| !se .con ains(&j))
329 .collec ();
330 e u n a ailable_slo s;
331 }
332
333 n ge _al e na ing_pa h(&sel ) -> Al e na ingPa h {
334 le unma ched_bidde s = sel .ge _unma ched_bidde s();
335 le unma ched_slo s: Vec<usize>=(0..sel .ge _slo s_num()).collec ();
336 le easible_bidde s: Vec<usize>=unma ched_bidde s
337 .i e ()
338 . il e (|&i| sel .ma ching.u ili ies[*i] > 0.0)
339 .map(|x| *x)
340 .collec ();
341 cons B: 64 = s d:: 64::MAX;
342 le DUMMY_SLOT: usize = sel .ge _slo s_num();
343 le mu cu _min_pa h =Al e na ingPa h{
344 pa h: Vec::new(),
345 cos : B,
346 inal_edge: EdgeType::TERMINAL
347 };
348 o ini ial_bidde in easible_bidde s{
349 le mu cu _pa h =Al e na ingPa h{
350 pa h: Vec::new(),
351 cos : B,
352 inal_edge: EdgeType::TERMINAL
353 };
354 cu _pa h.pa h.push(ini ial_bidde );
355 le mu size = 0;
356 le mu cu _node =ini ial_bidde ;
357 le mu isi ed_slo s: HashSe <usize>= HashSe ::new();
358 le mu isi ed_bidde s: HashSe <usize>= HashSe ::new();
359 isi ed_bidde s.inse (cu _node);
360 le mu end = alse;
B.1. Código pa a a xe ación dos da os 13
361 le mu is_ iable = alse;
362 while isi ed_bidde s.len() + isi ed_slo s.len() > size && !end {
363 le mu candida e: Op ion<usize>= None;
364 le mu candida e_cos =B;
365 le mu edge_ ype =EdgeType::TERMINAL;
366 le a ailable_slo s =unma ched_slo s
367 .i e ()
368 . il e (|&x| ! isi ed_slo s.con ains(x));
369 le cu _ e minal =&sel .g aph. e minal_a [cu _node];
370 i cu _ e minal. e minal_edge.is_some() {
371 end = ue;
372 le max_cos =cu _ e minal. e minal_edge.unw ap();
373 i max_cos < candida e_cos {
374 candida e = Some(DUMMY_SLOT);
375 candida e_cos =max_cos ;
376 edge_ ype =EdgeType::TERMINAL;
377 }
378 is_ iable = ue;
379 }
380 o &j in a ailable_slo s {
381 le node =&sel .g aph.g aph[cu _node][j];
382 i node.maximum_edge.is_some() {
383 end = ue;
384 le max_cos =node.maximum_edge.unw ap();
385 i max_cos < candida e_cos {
386 candida e = Some(j);
387 candida e_cos =max_cos ;
388 edge_ ype =EdgeType::MAXIMUM;
389 }
390 is_ iable = ue;
391 }
392 i node. ese e_p ice_edge.is_some() {
393 end = ue;
394 le max_cos =node. ese e_p ice_edge.unw ap();
395 i max_cos < candida e_cos {
396 candida e = Some(j);
397 candida e_cos =max_cos ;
398 edge_ ype =EdgeType::RESERVE;
399 }
400 is_ iable = ue;
401 }
402 i !end & node. o wa d_edge.is_some() {
403 le max_cos =node. o wa d_edge.unw ap();
404 i max_cos < candida e_cos {
405 candida e = Some(j);
406 candida e_cos =max_cos ;
407 }
408 is_ iable = alse;
409 }
410 }
411 i candida e.is_some(){
412 isi ed_slo s.inse (candida e.unw ap());
413 size +=1;
414 i cu _pa h.pa h.len() == 1{
14 B. Código do es udo numé ico do mecanismo xe al de subas a
415 cu _pa h.cos =candida e_cos ;
416 }else {
417 cu _pa h.cos +=candida e_cos ;
418 }
419 cu _pa h. inal_edge =edge_ ype;
420 cu _pa h.pa h.push(candida e.unw ap());
421 cu _node =candida e.unw ap();
422 }
423 i !end && candida e.is_some(){
424 le a ailable_bidde s =unma ched_bidde s
425 .i e ()
426 . il e (|x| ! isi ed_bidde s.con ains(x));
427 candida e = None;
428 candida e_cos =B;
429 o &i in a ailable_bidde s{
430 le backwa d_node =&sel .g aph.g aph[cu _node][i];
431 i backwa d_node.backwa d_edge.is_some() {
432 le max_cos =backwa d_node.backwa d_edge.unw ap();
433 i max_cos < candida e_cos {
434 candida e = Some(i);
435 candida e_cos =max_cos ;
436 }
437 is_ iable = alse;
438 }
439 }
440 i candida e.is_some(){
441 i candida e.is_some(){
442 isi ed_bidde s.inse (candida e.unw ap());
443 size +=1;
444 cu _pa h.cos +=candida e_cos ;
445 cu _pa h.pa h.push(candida e.unw ap());
446 cu _node =candida e.unw ap();
447 }
448 }
449 }
450 }
451
452 i is_ iable && cu _min_pa h.cos > cu _pa h.cos {
453 cu _min_pa h =cu _pa h;
454 }
455 }
456 e u n cu _min_pa h;
457 }
458
459 n compu e_dis ances(&sel , s a : usize) -> Dis ances {
460 le n_slo s = sel .ge _slo s_num();
461 le n_bidde s = sel .ge _bidde s_num();
462 le B=10.0;
463 le mu slo s_dis ances: A ay1< 64>=A ay:: om_elem(n_slo s,B);
464 le mu bidde s_dis ances: A ay1< 64>=A ay:: om_elem(n_bidde s,B);
465 le mu isi ed_slo s : HashSe <usize>= HashSe ::new();
466 le mu isi ed_bidde s: HashSe <usize>= HashSe ::new();
467 le mu queue: VecDeque<(usize, 64,bool)> = VecDeque::new();
468 queue.push_ on ((s a , 0.0, ue));
B.1. Código pa a a xe ación dos da os 15
469 while !queue.is_emp y() {
470 le (node, cos , is_bidde ) =queue.pop_back().unw ap();
471 i is_bidde {
472 o jin 0..n_slo s{
473 i ! isi ed_slo s.con ains(&j){
474 ma ch sel .g aph.g aph[node][j]. o wa d_edge {
475 None => (),
476 Some(x) => {
477 slo s_dis ances[j] =x + cos ;
478 queue.push_ on ((j, x + cos , alse));
479 isi ed_slo s.inse (j);
480 }
481 }
482 }
483 }
484 }else {
485 o iin 0..n_bidde s{
486 i ! isi ed_bidde s.con ains(&i){
487 ma ch sel .g aph.g aph[i][node].backwa d_edge {
488 None => (),
489 Some(x) => {
490 bidde s_dis ances[i] =x + cos ;
491 queue.push_ on ((i, x + cos , ue));
492 isi ed_bidde s.inse (i);
493 }
494 }
495 }
496 }
497 }
498 }
499 bidde s_dis ances[s a ] =0.0;
500 e u n Dis ances{
501 slo s_dis ances,
502 bidde s_dis ances
503 }
504 }
505
506 n ill_pai s(&sel , pa h: &Al e na ingPa h, leng h: usize) -> A ay1<(usize,usize)> {
507 le mu pai s : Vec<(usize,usize)> = Vec::new();
508 o iin (0..leng h).s ep_by(2) {
509 le pai =(*pa h.pa h.ge (i).unw ap(), *pa h.pa h.ge (i+1).unw ap());
510 pai s.push(pai );
511 }
512 e u n A ay:: om_ ec(pai s);
513 }
514
515 n upda e_ma ches(&sel , new_pai s: A ay1<(usize,usize)>) -> A ay1<(usize,usize)> {
516 le mu new_ma ches : Vec<(usize,usize)> = Vec::new();
517 le mu bidde s_se : HashSe <usize>= HashSe ::wi h_capaci y(new_pai s.len());
518 le mu slo s_se : HashSe <usize>= HashSe ::wi h_capaci y(new_pai s.len());
519
520 o iin 0..new_pai s.len() {
521 new_ma ches.push(new_pai s[i]);
522 bidde s_se .inse (new_pai s[i].0);
16 B. Código do es udo numé ico do mecanismo xe al de subas a
523 slo s_se .inse (new_pai s[i].1);
524 }
525
526 o iin 0..sel .ma ching.pai s.len(){
527 le cu _ma ch = sel .ma ching.pai s[i];
528 i !bidde s_se .con ains(&cu _ma ch.0) && !slo s_se .con ains(&cu _ma ch.1) {
529 new_ma ches.push(cu _ma ch);
530 }
531 }
532
533 e u n A ay:: om_ ec(new_ma ches);
534 }
535
536 n upda e_ e minal_assignmen (&sel , pa h: &Al e na ingPa h) -> Op ion<A ay1<(usize,usize)>>{
537 le new_pai s = sel . ill_pai s(pa h, pa h.pa h.len() - 2);
538 e u n Some(sel .upda e_ma ches(new_pai s));
539 }
540
541 n upda e_maximum_assignmen (&sel , pa h: &Al e na ingPa h) -> Op ion<A ay1<(usize,usize)>>{
542 le n=pa h.pa h.len();
543 i n >=4 && pa h.pa h.ge (n-1).unw ap() !=pa h.pa h.ge (n-3).unw ap() {
544 e u n None;
545 }
546 le new_pai s = sel . ill_pai s(pa h, pa h.pa h.len() - 2);
547 e u n Some(sel .upda e_ma ches(new_pai s));
548 }
549
550 n upda e_ ese e_assignmen (&sel , pa h: &Al e na ingPa h, upda ed_p ices: &A ay1< 64>) ->
Op ion<A ay1<(usize,usize)>> {
551 le las _i em =pa h.pa h.las ().unw ap();
552 le is_las _i em_ma ched = sel .ma ching.pai s.i e (). il e (|(_, j)| j ==
las _i em).las ().is_some();
553 i !is_las _i em_ma ched {
554 le pai s = sel . ill_pai s(pa h, pa h.pa h.len());
555 e u n Some(conca ena e(nda ay::Axis(0),&[sel .ma ching.pai s. iew(),
pai s. iew()]).unw ap());
556 }else i
sel .g aph.g aph[*pa h.pa h.ge (pa h.pa h.len()-2).unw ap()][*las _i em]. ese e_p ice_edge.unw ap_o _else(||
0.0) < upda ed_p ices[*las _i em]{
557 e u n None;
558 }else {
559 le new_pai s = sel . ill_pai s(pa h, pa h.pa h.len() - 2);
560 e u n Some(sel .upda e_ma ches(new_pai s));
561 }
562 }
563
564 n upda e_assignmen s(&sel , upda ed_p ices: &A ay1< 64>, pa h: &Al e na ingPa h) ->
Op ion<A ay1<(usize,usize)>> {
565 ma ch pa h. inal_edge {
566 EdgeType::TERMINAL => sel .upda e_ e minal_assignmen (pa h),
567 EdgeType::MAXIMUM => sel .upda e_maximum_assignmen (pa h),
568 EdgeType::RESERVE => sel .upda e_ ese e_assignmen (pa h, upda ed_p ices)
569 }
570 }
B.1. Código pa a a xe ación dos da os 17
571
572 pub n s able_ma ch(mu sel )->usize {
573 le n= sel .ge _bidde s_num();
574 le k= sel .ge _slo s_num();
575 cons B: 64 = s d:: 64::MAX;
576 le mu i e : usize = 0;
577 le mu cos : 64 = 0.0;
578 while cos !=B {
579 i e =i e + 1;
580 le pa h: Al e na ingPa h = sel .ge _al e na ing_pa h();
581 i pa h.pa h.len() < 2 || i e > n*(2*k+1){
582 b eak;
583 }
584 cos =pa h.cos ;
585 le max_ 64 =| 1, 2| {
586 i 1 >= 2 {
587 e u n 1
588 }else {
589 e u n 2
590 }
591 };
592
593 le i s _i em =pa h.pa h.ge (0).unw ap_o _else(|| &(0 as usize));
594 le dis ances: Dis ances = sel .compu e_dis ances(* i s _i em);
595 le mu upda ed_u ili ies = sel .ma ching.u ili ies.clone();
596 le mu upda ed_p ices = sel .ma ching.p ices.clone();
597 o iin 0..n{
598 upda ed_u ili ies[i] =upda ed_u ili ies[i] - max_ 64(pa h.cos -
dis ances.bidde s_dis ances[i], 0.0);
599 }
600 o jin 0..k{
601 upda ed_p ices[j] =upda ed_p ices[j] + max_ 64(pa h.cos -
dis ances.slo s_dis ances[j], 0.0);
602 }
603 ma ch pa h. inal_edge {
604 EdgeType::RESERVE => {
605 le las _slo : usize = *pa h.pa h.ge (pa h.pa h.len()-1).unw ap();
606 le las _bidde : usize = *pa h.pa h.ge (pa h.pa h.len()-2).unw ap();
607 upda ed_p ices[las _slo ] =max_ 64(upda ed_p ices[las _slo ],
sel . ese e_p ices[[las _bidde , las _slo ]]);
608 }
609 _=> ()
610 }
611
612 le upda ed_assignmen s = sel .upda e_assignmen s(&upda ed_p ices, &pa h);
613 le new_assignmen s = ma ch upda ed_assignmen s {
614 None => sel .ma ching.pai s.clone(),
615 Some(x) => x
616 };
617 sel .ma ching =Ma ching {
618 u ili ies: upda ed_u ili ies,
619 p ices: upda ed_p ices,
620 pai s: new_assignmen s
621 };
18 B. Código do es udo numé ico do mecanismo xe al de subas a
622 sel .upda e_g aph_edges();
623 }
624 sel .w i e_ esul s(" us - esul s2. x ". o_s ing(), i e );
625 e u n i e ;
626 }
627
628
629 n w i e_ esul s(sel , pa h: S ing, i e a ions: usize) -> () {
630 le mu ile = s::OpenOp ions::new()
631 .w i e( ue)
632 .append( ue)
633 .open(pa h)
634 .unw ap();
635 le n= sel .ge _bidde s_num();
636 le k= sel .ge _slo s_num();
637 le mu esul : S ing =
638 n. o_s ing() + "," +
639 &k. o_s ing() + "," +
640 &i e a ions. o_s ing() + ",";
641
642 o (i,j) in sel .ma ching.pai s {
643 esul = esul +
644 &i. o_s ing() + "-" + &j. o_s ing() + "/";
645 }
646 esul = esul + ",";
647 o xin sel .ma ching.u ili ies {
648 esul = esul + &x. o_s ing() + "-";
649 }
650 esul = esul + ",";
651 o xin sel .ma ching.p ices {
652 esul = esul + &x. o_s ing() + "-";
653 }
654 esul = esul + " n";
655 ile.w i e_all( esul .as_by es()).expec ("Unable o w i e o ile");
656 }
657 }
658
659 n main() {
660 le als_op =Auc ion:: ead_ ile("./ us -da ase . x ". o_s ing()).unw ap();
661 le auc ion =Auc ion::new( als_op .0, als_op .1, als_op .2);
662 p in ln!("Auc ion");
663 p in ln!("{:?}",auc ion. alues);
664 p in ln!("{:?}",auc ion. ese e_p ices);
665 p in ln!("{:?}",auc ion.max_p ices);
666 p in ln!("{:?}",auc ion.g aph);
667 le i e =auc ion.s able_ma ch();
668 p in ln!("Numbe o i e a ions: {:?}", i e );
669 }
Código B.2: Implemen ación do mecanismo xe al de subas a.
1n=(3 5 8 10 20 50 100)
2len=${#n[@]}
3i e =100
4
B.1. Código pa a a xe ación dos da os 19
5 o ((j=0; j < $i e ; j++))
6do
7 o ((i=0; i < $len; i++))
8do
9echo "Execucion: ${j} - n: ${n[$i]}"
10 py hon3 gene a e_auc ion.py ${n[$i]} ${n[$i]}
11 ca go un
12 done
13 done
Código B.3: Sc ip usado pa a o p imei o expe imen o do mecanismo xe al de subas as.
1n=30
2i e =100
3
4 o ((j=0; j < $i e ; j++))
5do
6 o ((i=0; i < 30; i++))
7do
8echo "Execucion: ${j} - k: $i"
9py hon3 gene a e_auc ion.py $n $i
10 ca go un
11 done
12 done
Código B.4: Sc ip usado pa a o p imei o expe imen o do mecanismo xe al de subas as.
