αααα»αααααΆα 2012 αααααΆααααΌααααααααααααααα·α
αα
ααααΌαααΆαααααααααΌα Lloyd Shapley αα·α Alvin Rothα "αααααΆααααααΉααααΈααααΆααααα
αααααα·αααΆα αα·αααΆαα’αα»ααααααααΆααααα
αααΈααααΆαα" Aleksey Savvateev αααα»αααααΆα 2012 ααΆαααααΆααΆααααααααααΆαααΆαααα αα·αα
αααΆααααΆααα’αααΈααααΉαααΆααααα»ααααααααα·ααααααα·ααα·ααΌα αααα»αααααΎαααααα αΆααααααΆαααα
α·ααααα»αααΆααααααα’αααααΌαααα
ααααΈαααααααα½αα
αααααααααΉαααΆαααΆαααααααααααΉααααΈα α’αααΈααΆααα·ααααα
αα
ααααααααΆααααΌαααΆααααααΆααααα
ααΆααααΌαααΆα ααααΆαααααααΆααααααΌαααΆααααααα±αααααααΆααα’αααΈααααααααα αααααΆααα―αααΆαααααΆα 1962 ααααααΆααααααΈααΈ "ααααΉααααΈαααααααααΆαα’αΆααΆα ααα·ααΆα α": "ααΆαα αΌαααααα αα αΆαα·ααααΆααα αα·ααααααααΆαααα’αΆααΆα ααα·ααΆα α" α
α’αααΈα’αΆααΆα ααα·ααΆα ααααααααααα·αααααααΆα
ααααΌααααα (ααΆαααααΌαααα) - ααΆααα·α αα αααααααααΆαααααΎαααααα
ααΆαααΌαα·ααΆα ααααααΆαααΆααααΆαααα½αα ααΆααα»αααααααααα "m" αα·α "w" αααααααααΈα ααΎαααααΌααααααΆαααΆαα½ααα½ααα (αα·αα αΆαααΆα ααααααΌα ααααΆαα αααα ααααΆαα ααΈαααα αα ααααΆααααΆααααΉαααααΌααα»αα ααααααααΆααα―αα )
ααΎααΆαααααααα’αααΈαααααααααααΌαααααΎαααα»αααααΌ? ααΆααΆαα·αααΆααααα½ααααααα»αααΆααααααΆαααααααααααα αααααα ααα αΆαααΆααααΆαααα½ααααα»αααααΌαααΆαα’αα»ααααααααααα αααααααΎααααααααΈα α§αααΆααΆβααΆαβα’αααααΆαα·αα»αααβαααβα ααβαααβααΆαβααΆβααααΈ ααΎααααΈβαα»αβα²ααβααΆαβαααβααβααααβααΆααβαααααβααΈβααααΆααα (ααΆαβαααβααβααΊβααΆβααααΆαααΆαβαα½αβαααβααααΆααΈβα ααβααΆαβααΆααΈβααΈβααΈβααΆβαααααααβααααβααΆααβα αααΎαβααΆαβαααααααβααααβααΆααα )
ααααΉααααΈαααααααΊαααα·ααα
αααα»αααααΆαααΈααααααααα·α
αα
ααααΎαα ααΆααα·αααΆα’ααα»ααααααααΆααα ααααααα·α
αα
ααΆαααααααΈα’ααα»ααααααα αα
αααα»αααααααα·α
αα
ααα»αααααααΌαααΆααααα½αααααααΆαααΈα ααΎααααΈαααααΎαααααΆααα
ααααα α’αααΈααααααα»αααΉαααααΆααα’ααα ααΊαα·αααΆααΏααααα½αα ααΆαααααααααΈααααα αα»αααααΆαα
αααααΌαα
α’αααβααααααα·α
αα
βααΎαβααΆαβαααααΆαβααΆαβαα·ααΈβαααα
m1, m2, ... mk - αα»ααα
w1, w2, ... wL - ααααααΈα
αα»ααααααΆααααααΌαααΆααααααα’ααααααααΆαααΈαααααααααΆαα "αααααΆ" αααααααααΈα ααΆααααΆα "ααααα·αααΌααα" ααααα αααααΆαααααααααααααααΈαα·αα’αΆα ααααΌαααΆααααααααααΆααα·ααΆααΆαααΆααααααα αααααΈααΆαα·αααΆαα’αααααααααααααα
α’αααΈααααααααΆαααΎαα‘αΎααα
αααα»ααα·ααα
ααΆααααΈαααΌα
ααααΆαααααΆαααααααααααΈα
αα·ααααααααααΌαααΊααααΆαα ααΆααααααα / αααααααααααα½ααααααΊααΆααΎααα·αααααΆααααααΌαα αααΌαα α·αααααααααΎαααα
ααααΉααααΈααα ααααα·ααα·αααΈααΆαα ααα αΆα αα·αααααα·αααΌααα ααΆαααααααΆααα·ααΈαα½αααΎααααΈαααααΎαααΆαααααΎααααααα½αααααα½ααααΆααα»αα αα·αααααααΈαα½αα ααα½αααΎααααΈα±ααααΆααΉαααΆαα ααααααΆααααααααααααααααα (αα·ααααααααΆααααααΆααΆαααααααα)α
ααΎα’αΆα ααΆαααΆαααααΆαααα ααα’αααΈαααα?
ααΆαααααΈααααααααα½αααΌ (m,w) ααααα·αααΆαααααααΆαα ααα»αααααααααΆαα w ααααΈαα αα α»ααααααα’αΆαααααααΆα m α αΎααααααΆαα m ααααααααα αα α»ααααααααΊα’αΆαααααααΆα w α αααααΊααΆααααΆαααΆααα·ααααα·ααααααα
ααΆααααΆααααααΎααααααΆααααΆααααΆααααΆααααααΆαααΆαα½αααααΆααααΆααααα "ααΆαααΆαααΌααα" αααα»αααααΆαααΆαααα α’αΆααΆα ααα·ααΆα αααααΉααα½αααααααααα
ααααα·αααΎααααααΈαααααΆαα αΎα ααα»ααααααΆαα αΌαα α·ααααα»αααα·αααΆαααααααΆα αααααΆαααΎαααΈααΌαααα
ααααα·αααΎααα»αααααΈαααΆαααα·αααΆαααααααΆα α αΎαα’αααααΆααααΈαααΊ "ααΎαααΈααΌααα" αααααΆααααααΆαα αα·ααα ααα
ααΆααααΌαααΆαα’αα’αΆαααΆαααααΆαααα·ααααααααααΌαααΆαα½αααΌα ααΆααααααααα’αΆααΆα ααα·ααΆα αααΆα, αααααΉαααΆαααααΆαααα αααααααααααααα ααΈααΈα αααα½ααααααααΆααααααΆααααΆααααααααααααΉαααααααααΊααΆααααααΆααα α αΌαααααααααααΆαα½α M*N α
ααααΌαααααααΌαααΆααααααΈα αα·ααααααΈααα ααΆ "αα α»ααααααΆα" αα·αα’αα»αααααααα»ααα·αααααΆα αααΎαα
ααΈαα·αα·ααΈ Gale-Shapley
ααααα·αααΎαα»αα αα·αααααααΈααΆααα’ααααααΎααΆα "ααααααααααΆ" ααααααααα’αΆααΆα ααα·ααΆα αααΉαααΆααα·αααααααΆαα
ααααααααααΆα
ααΎαα
αααΆααααααΈαααΈααααααΆααααααΌαααΆαα ααΎααααα
ααααΆαααααΆααααααααΆααΈαααααα (αααααααΉααα·ααααααααΆα
) α
αα ααααΉαααααΌααα»αααααααααΌααα ααααααααΈααα’αααα»αααααααΆααα αΎαααααααα’α½α αα»αααΆααααααΆαααΆαα½αααΆααα
αα βαααβααααΆα βααααβαααα αααβαααβαα βααβααααααΈ ααΎβααααααΈβα’αΆα βααβααΎαβα’αααΈ? ααΆααΆαα αααΌαααα»ααααα ααααααααα’α½α ααααααΆα αα·αααΆααααΆαα α¬ααααΆααα»ααα α’αααβαααβαα·αβααΆαβααααβαααβααααβαααβα αΎαβαααα αΆαα αα ααααααααΆααααΆαα αα ααΆαααα½α αα·αα·αααααΎααα»αααααααααΎαααΆαα½ααα "ααΎαααΈααααα·αααΌααα"α ααΎααααΈααΆααααΆαα αα ααΆαααα½αα ααααα·αααΎα’ααααα·αααΆαααααΆαααΆαααααα»α α αΎαα’αααΈααααααααΆαααΊααΆαααΆαααΌααα αααα’ααααααααααααΆαα½αααααααΌαααΆααααααΌαα ααααααΈβαααβααΎαβα’αααβαααβααβα αααΎαβααΆαβαα ααααΆααβααΆααβα²ααβαααα αΆα α αΎαβααααΎβα’αααβαααβαα βαααα
αα»αααααααΈ α’ ααααΆαααΆαααΊααΌα αααα ααααααΈααααααΆααα»ααααααααααΆαα
αα ααααααΈααΈα αα»ααααΆααα’αα "α₯ααα·ααααα" (ααΆαααααΎ) ααααΌααα ααααααααΈα’αΆαα·ααΆαααΈααΈαα ααΎααααΆαααα»ααααααααααα αα»αααααααααΌααααααΆαααΆαα ααΈαα αα»ααβαααβα’αααα»αβααΆβαα½αβααααααΈβαα½α βα αΎα αα·αβααΆααβααααΎβα’αΈβααα
αα αααααααΆα ααααααΈααΎαααααΆαααΆαα ααααα·αααΎααααΆααααΆαααααα’αααα»ααα½α α αΎαααααΌαααΆαα αΌααα½ααααα’αΆαα·ααΆααααααααΆα αααα’αΆαα·ααΆαααΆαααααΌαααΆααααααΌααα ααααΆαα ααααα·αβααΎβα’αααβαααβααβααΆαβααΆαβα’αααΈβαααβααΆαβαα½α βα αΎα α’αααβααΆααβααααΆβααααΌαβααΆαβααβαααααΌαβαα βααααΆαα ααααααΈααααΎαααΎαααΆαα»α’αα·ααααΆααΆαααααα
ααΎαααααΎαααααααα
ααΆαααααα αα»ααααααΆαααααΆαααααααΆαααααααΈααΆααααΌαααααααααΈααααααΆαα α αΎαααααΌαααΆααα»αα ααααααααΆααα―α α¬ααααΆααααΆαααααΆαα½αααααααΈαα½αα ααα½αα αααααΆααααααΎαααΉααααααΆαααΆααα’ααααααΆα
ααΎααΆα’αΆα αα αα½α αααααα»αααΆαααααΎαααΆαααααΎαααΆαααΆααααΌα ααα»αααααααααΆααααααααΈααΎααααΈααααα αααα»αα? ααΈαα·αα·ααΈααΊαααΈααααααΈααα»αααααααααααααΆαα’αΆα αα»αααααΆα ααα»ααααβαααα½αβαα½αβααΆ ααΎβα’αααβααΆβααα’βααΆαβααΈβααα?
ααααΉααααΈααα α αΌαααΎααα·α αΆαααΆαα·αααααΉααααααααααααΆααααΈααααααΈααΆααααΈααααααα»ααααααα ααα»ααααααΆαααα»αααααααααααα’αΆααΆα ααα·ααΆα ααααααΆααααααααΆαααΆααα’ααα ααααααΆααααααΆαααααΎα‘αΎαααΎα (αα»ααααα α αΎαααααααΈααα½ααα/ααα·ααα) αααααααα αααα»αααααααααα’αΆααΆα ααα·ααΆα αααααααααΎαααΆααααααΆαααα»ααααΆααααΆαα αα·αα’αΆαααααααΆαααααααΈααααααα
α’αΆααΆα ααα·ααΆα ααααααΌα ααααΆ
αα·α αΆαααΆααααΆαααΆαααΆαα½α "α’αΆααΆα ααα·ααΆα ααααααΌα ααααΆ" α α αΌαααΎααα·α αΆαααΆα’αααΈααααααααα·ααα·ααααΆαααααααα±ααααΆαααΆαααααααααΎαααααΌαααΆααααα»αααΆαααααΎα±αααα½αααααααα αααΆααα ααΆβα§ααΆα αααβαααβαα·αβααααΉαααααΌαβααΆαβααααααα·ααααΆα
αα·α αΆαααΆβα’αααΈβαααβαα½αβ a, b, c, d.
α’αΆαα·ααΆααααααΆαα a: bcd
α’αΆαα·ααΆααααααΆαα b: cad
α’αΆαα·ααΆααααααΆαα c: abd
αααααΆαα d ααΆαα·αααΆααααα αΆααΆααΎααΆααααΆααα
αααΆααααααΆααααΈααααα
ααααααααα
ααα ααααΈαααααααΆαααα αα·αααΆαααααααααα’αΆααΆα ααα·ααΆα ααααααααααα·αααααααΆααα αααα»ααααααααααααααα
ααΎααΆαααααααααααα»ααααΆααααααΆααααα»ααααα½αααΆαα? ααΈ. ab cd, ac bd, ad bc α ααΌααααΆααΈααα·ααΆααΉααα½ααααα αΎαααααΎαααΆαααΉααα ααΆααααα
αααααααα "ααΈααα" α
αααβααΆβαααα½αβααααΆααβαααα»αβαααβααΎαβα
αα βααΎβαα»ααα·ααααΆβααα·ααα·ααααΆβααΆααααΌαα αααααααΌαααΆαααααΎααααα αααα·ααααααααα»ααα
ααΈαααα»αααΌααααΌααΊ Vladimir Ivanovich Danilov α ααΆααααΆαα
αΆαααα»α "α’αΆααΆα ααα·ααΆα α" ααΆααΆααΆαααΉααααΌααΆααΆ α αΎααα½ααΆααΈααΆαααΌα
ααΆααααααα "α’αααα
αΆαα" "α’ααααα·ααΆααααααα" αα·α "α’αααααΆααααΆα
ααααα" α αααα»αααααΆαααΆααααααΆαα’αααααααΆα 4 ααΆαα α¬α
αααΎαααΆαααααα½ααΆααΈααΈαα½αα ααΆαα·αα’αΆα
αα
αα½α
αααααα»αααΆααααααααΆαααααααααΆααααΆα αΆαα αααα½ααααααααααααα·αααααααΆαααΊααΆααΆαααΎαα
αα αα½αα
ααα·α ααα Shapley
αα αααα»αααΌαα·αααα αα½αααααΆααααααα α α·αααααααΎααααΌαααααΆααα αααΌα ααααΌαααΆαααααΆααα αΌαα αααΆααααα ?
Shapley ααΆαααααΎαααααααααΆαα αααααααα αΆααααα ααααΆα 1953 α α αΌααααααααΆααααΆαααΆαααααααααααΆαα½ααααα»αααα»ααα N={1,2β¦n} α ααΆαα αααΆα/α’αααααααααααα αΆαααΆα αααααΌαα αααααααα α§αααΆβααΆβααα»αααβαα½αβααααΆβααααΎβα’αααΈβαααβααΆαβααααααααβαααβα αΎαβα ααβα ααααβαααΆαβαααα ?
Shapley ααΆαααααααααααααΆ αα ααααααα αα ααΎααα½αααααΌαααΆαααΉαααΆααααα ααα½ααααα½αα ααα½αααααα»αααααΆαααααα’αΆα ααα½αααΆαα ααΎαααα»αααααααα·αααα 2N ααΆααα’ααα’αΆα ααααααΆααααΆαααα»ααααΆα? α αΎααααααα’ααααΎααααααΆαααα Shapley ααΆααααααααΌααααααααα
α§ααΆα αααα α’ααααααααααα α’ααααααα αααΈααΆ αα·αα’αααααΆααααα ααααα
ααααΌααααααααΈαααα»αααΈαααα»αααΌααααΌα αα½αααααΆααααΈααααΆα 1000 rubles αααα»ααα½αααααα ααΎααααΎααΌα
ααααα
ααΎααααΈαααα
ααααΆ? αααα ααααΆααααΎααααΆα
V(1,2,3)=1000
α
αΌαααΎαααααΎαα»ααααα
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
ααΆααααα ααααααα»αααα·ααααα·αα’αΆα αααααααΆααα αα»αααααΆααααΎαααΉαααΈααα ααααααααααα»ααααα αΆααααα»αα αα»ααααααΆααααααα±αα ααααα·αααΎααΆαααα αα α αΎαααααΎαααααααΆαααααααα½αα―αα α αΎααα ααααααααΎααααααααα (αααααααααααα ααααα·ααααα·ααΆααααα»ααααααααααααα) α
Superadditivity ααΊαα αααααααα½αααααΆαα½αααααααΆαα αααΎαααΆααααα‘ααααΈααααΆ αα ααααααααΆααΆαααα ααααα αααΎαααΆααααα»αααΆααα½ααα½α ααα»ααααααΆαα·αα αααΆααααΈαααααααα ααααΆααααααααααα α αααΆααα ααααααΆα αααΎαααααΌαααΆαααΌα α’αααΈααΏααααα
ααΆαααααααα½αα α’ααααααα½αααΈααΆαααααα»ααααααααΆαααααΆααΆαααααΎαααααΆαααααα ααα½α 1 ααΆααα»ααααΆαα ααΎβα’αααβααΆααβααΈβαααβαααα αααβααΆαβαα½αβααΆαα ααΌααααΆααΈααα·ααΆααΆαα½αα’αΆα αααααΆαα (ααα ααααΈααααΈ) αα·αααα½αααΆαααααΆααααΆααααΆααααααΆαααααα½αααα α αΎαααααΆαααααΆααααΆααα’αΆα ααααΎα’αααΈααααααΆααα―αααΆαααα αααααΊααΆα αααααα ααΆαααααΆαααα½αα±ααααααΆα αααααααΆααααααααααΆαα ααΆαααααααΆαααα»αααααΈαααΆαααααα’αΆα αα»αααααΆααααΈααΈ... ααααΉααααΈααααααα ααααα·ααααα·ααΆαα αΆααααααΎααααα§ααΆα αααααααα·αααΆααααααααααΆαα
ααΎαβα ααβααΆαβαααααααααΆαβαααβαααβαααβααααΆαβαααα»αβα αααα»αβα ααβααΆααΆααβαααααααααΆαβαα½αα αααα»αααααΆααααα ααααΆααα’ααααααα·αα’αΆα αααααααΆααααΆαααΊ ααΊαααα ααΆααΎαα‘αΎαααΆααααΌαααΊαααα ααα»ααααβαααβαα·αβαααβααβααααΌαβαααβα αα?
Shapley ααααΎα±αααααα αααα·ααΈαααα αααααΆααααΆαα½α n! αααα ααΎααααααα ααα’ααααααααΆααα’αααα αααα»αααααΆαααααα α αΌααα·ααΆαααΆα’αααααΆαααααααααΌαα ααΆααα αΌαααα αΎααα 100 ααααααΆααα αααααΆαααα "ααΈααΈα" α αΌααα α αΌααα·ααΆαααΆα’αααααααααααα (αα½αααΆαα½αα’αααααΆαααααααα’αΆα ααααΆα 450 α’αααααΆαααααααΆααα 100 αα½α α αΎα) α’ααααααααααααα 350 α α’ααααααα αααΈααΆα αΌα (αα½αααααΆ 1000 -450) αα 550 α α’αααα α»αααααααααααααααα (ααΆαααααΎα)
ααααα·αααΎααΎααααααα
αααααααΆααααΆααααααΆαα·αααΆααα’ααα
GSB - (αααα C) - (αααα D) - (αααα B)
SGB ββ- (αααα C) - (αααα D) - (αααα B)
SBG - (αααα C) - (αααα D) - (αααα B)
BSG - (αααα C) - (αααα D) - (αααα B)
BGS - (ααα½αααΆα C) - (ααα½αααΆα D) - (ααα½αααΆα B)
GBS - (αααα C) - (αααα D) - (αααα B)
α αΎααααααΆαααα½αααααΈαα½ααααΎααααααααα·ααααα ααααα 6 - ααΆαααααααΎααΆααααααΆαα·αααΆααα’αα - αααααΊααΆααα·α ααα Shapley.
Shapley ααΆααααα αΆαααααΉααααΈαα (αααα αΆαααααα αα)α ααΆαααααΆααααα αααα (supermodular) ααααααα»ααααα’ααααααααΆααααΎααααΈα αΌααα½αααΆαα½ααααα»αααααΆαααααΌαααΆαααααααααΆααααα ααΊαααβαααααβαα·αβααα α αΎαβααΆβα ααα»α βααααβαααβαα½αβαααα αΌαβααααΆ (αααα»αβααααΈβααααβααΎα 6 αα·αααα»)α ααα·α ααα Shapley αααα·ααα α ααααααΆαααααααΌαα ααΆαααααα’αΆα αααααααΆαααααααααΆα ααααΆαααααΆααααΆααααΉααααααΆααααΉαααΆα‘αΎαα
αα ααααΆα 1973 ααΆααααΌαααΆααααα αΆαααΆαααα αΆααΆαα½αααααααΊ supermodular α
ααα»αααααΆααα’ααα αααααααααααΌααα ααΆααααααααααΌαα αα αΌααααααΈααΈα - n-1 ααΆααα αα
α’αΆααΆαααΆαααααΆαααΆαααααΌααααα αααα»αα αα»αααααααααααΆααααΌαααΆααααααααα»ααααααΆα αααα αΆααΌα ααααΆααΎαα‘αΎαα
αααα»αβαα·αβααΆ α’αααβαααβααΆαβαααααβαααααΆααβααΌαααβααΆαβαα»ααααααααα·βαααβαααα»αβα α·ααα α αΎαβαα·αβαααβααααΉαβααβαα·α αα ααΆαβααΉαβααα
ααΌαα’ααα»α!
α αααΎαααα
- ααΆααα "ααα·ααα·ααααΆ - ααΆαααα"α
youtube.com/punkmathematics - ααα»αααα·α "Savvateev αααααααΆαααααααα": edusex.ru, brainsex.ru, studfuck.ru
- ααΆααΆααααα "ααα·ααα·ααααΆααΊααΆαααα"α
vk.com/alexei_savvateev - ααΆααΆααααα "αααααααααα·ααα·ααααΆ"α
vk.com/bsu_mmf_jokes - ααα ααααα ααΆαααααααααΆααα’αααα ααΈααα +100 ααααα αα·αα αααΎααααα savvateev.xyz
ααααα: www.habr.com