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.
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.
To prawda. Przypuszczam jednak, że podany przeze mnie algorytm Thue-Morse’a działa niezależnie od liczebności drużyn. Ten mój przykład był taki trochę wyidealizowany. Niemniej jednak Twoja metoda wydaje się być dużo prostsza i bez pułapek. Hmmm. Do przemyślenia.
Zadałem Twoje pytanie na blogu, z którego zerżnąłem byłem oryginalny temat (http://www.johndcook.com/blog/2016/06/30/fair-division-and-the-thue-morse-sequence/) i mi tam odpowiedzieli, że Twoje podejście zadziała wyłącznie w sytuacji, kiedy obydwaj kapitanowie będą mieli 100% zgodności co do poziomów wszystkich graczy oraz gdy ilość wszystkich graczy jest liczbą podzielną przez 4, podczas gdy sekwencja Thue-Morse’a daje dobre wyniki niezależnie od tych dwóch czynników.
1 warunek (100% zgodności) to chyba w ogóle jest założenie do tego algorytmu. Bo jeśli nie zgadzają się w ocenie zawodników to wtedy tworzenie algorytmu jest bez sensu.
Racja. Jeśli nie zgadzają się w ocenie zawodników, to algorytm jest (moim zdaniem) nieweryfikowalny.