Uczciwość (pięć lat później)

O uczciwości już kiedyś pisałem (jeden z pierwszych wpisów na blogu, o tutaj: !klik!). Tam jednak było o ogólnie pojętej uczciwości życiowej, a dziś rozpatrzymy sobie przypadek bardziej szczegółowy.

Pamiętacie ten odcinek „Przyjaciół”, w którym cała szóstka gra w rugby? Jak na samym początku wybierają drużyny i na końcu Ross dostaje Rachel, najgorszego zawodnika wszechczasów?

Nie pamiętacie?

Nic nie szkodzi. Ja dziś nie o serialach.

Jednak temat wybierania graczy do dwóch drużyn jest dość interesujący.

Żeby uprościć zagadnienie wyobraźmy sobie grupę osiemnastoosobową, w której najpierw wyznaczono dwóch kapitanów drużyn (A i B) a następnie kapitanowie owi mają sobie wybrać z pozostałych szesnastu zawodników po osiem osób do swoich drużyn.

Żeby jeszcze bardziej uprościć zagadnienie, każdy z owych szesnastu zawodników gra na odrobinę lepszym lub odrobinę gorszym poziomie od każdego z pozostałych, a obaj kapitanowie wiedzą który zawodnik gra na jakim poziomie.

I teraz pytanie: w jaki sposób przeprowadzić dobór zawodników do każdej z dziewięcioosobowych drużyn tak, żeby było jak najuczciwiej dla każdej ze stron?

Pierwszy pomysł, który na ogół przychodzi do głowy, to oczywiście: dobierajmy na przemian, raz ty, raz ja.

A kto ma zaczynać?

Obojętnie!

Czyżby?

Nie do końca. Jeżeli zacznie kapitan drużyny A, z pewnością dobierze sobie najlepszego ze wszystkich graczy. Kapitan B dobierze sobie najlepszego z pozostałych – i już jest odrobinę „w plecy” względem drużyny A. Pozostałe pary zawodników A-B również za każdym razem będą miały zawodnika A odrobinę lepszego, od zawodnika B – w efekcie drużyna A będzie zawsze trochę lepsza od drużyny B.

Może więc dobierać zawodników losowo?

Hmmm. Niby tak byłoby najuczciwiej. Ale wyobraźmy sobie sytuację, w której drużyna A wylosowała ośmiu najlepszych zawodników, a drużyna B – ośmiu najsłabszych. Znów dupa blada. Oczywiście szanse na taki układ są znikome (jeden do 65 tysięcy z hakiem), ale są. A my szukamy metody gwarantującej uczciwy rozkład zawodników za każdym razem.

Okazuje się, że najuczciwsza w takiej sytuacji jest metoda Thue-Morse’a, polegająca na tym, że najpierw kapitan A wybiera jednego zawodnika, potem kapitan B też jednego, a potem odwracamy kolejność: trzeciego zawodnika wybiera B, a czwartego – A.

A potem znów odwracamy kolejność. A więc skoro było ABBA to potem robimy BAAB.

W ten sposób dobraliśmy ośmiu pierwszych zawodników (po czterech do każdej drużyny). Pozostałych ośmiu dobieramy tak samo, z tym wyjątkiem, że znów odwracamy całą dotychczasową sekwencję:

BAABABBA

Cały proces wyglądać więc będzie tak:

ABBABAABBAABABBA

Jak widać, najlepszy gracz będzie grał w drużynie A, ale będzie tam grał również ten najsłabszy. Średni poziom obu drużyn będzie bardzo zbliżony. Przy założeniu losowego, równomiernego rozkładu poziomów gry między zawodnikami symulacje wykazują, że po milionie rund średnia różnica poziomów między drużynami jest w okolicach jednego promila (lub mniej), a więc bardzo niewielka.

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

5 komentarzy do "Uczciwość (pięć lat później)"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
Jacek
Gość

Jeśli kapitanowie wiedzą kto jak gra, to nie ma sensu układać kolejności losowania. Ustawiamy wszystkich 16 w rządku i jedziemy: pierwszy i ostatni dla kapitana A, z pozostałych pierwszy i ostatni dla kapitana B, i tak aż wszyscy zostaną „wybrani”. Nie chce mi się sprawdzać czy wynik będzie jak w Twoim algorytmie, ale na oko wygląda to całkiem uczciwie.

wpDiscuz