Talk:Fairshare between two and more: Difference between revisions

← Older edit

Talk:Fairshare between two and more (view source)

Revision as of 06:44, 27 June 2020

7,577 bytes added , 3 years ago

m

→‎Fairness and randomized rewards: Thanks for the investigation

Anonymous user

rosettacode>Horst.h

Revision as of 13:44, 2 February 2020 (view source) Thundergnat (talk \| contribs) (→‎Perl 6 count of how many turns each person gets: The light went on) ← Older edit		Latest revision as of 06:44, 27 June 2020 (view source) rosettacode>Horst.h m (→‎Fairness and randomized rewards: Thanks for the investigation)
(6 intermediate revisions by 2 users not shown)
Line 4: :I have to say, I kind of missed the point of the task initially so was not really sure what it was demonstrating. The actual algorithm was simple, the reason for it escaped me. After reading your links, the lightbulb lit. I removed the "number of times each person goes" which was kind-of pointless, and added a "fairness correlation" calculation showing the relative fairness to the Perl 6 entry. --[[User:Thundergnat\|Thundergnat]] ([[User talk:Thundergnat\|talk]]) 13:43, 2 February 2020 (UTC) :: Great :-) <br>--[[User:Paddy3118\|Paddy3118]] ([[User talk:Paddy3118\|talk]]) 18:26, 2 February 2020 (UTC) ::: I tried to clearify things to me, like [[User:Paddy3118\|Paddy3118]] described in his links.Without different values, it makes no sense.<BR>Rest removed, explanation by [[User:Paddy3118\|Paddy3118]] ([[User:Horst.h\|Horst.h]]) [[User:Horst.h\|Horst.h]] ([[User talk:Horst.h\|talk]]) 11:42, 26 June 2020 (UTC) ===Fairness example and cycles=== I saw Horsts' Perl program above, and recognized that the idea of fairness is hard to bring across so I thought I might do an example by hand. The set of numbers in this case are not a linear progression, so we (maybe), see the emergence of Thue-Morse as being the most "fair" calculated as the spread in final amounts per person. '''For all cases we will have have three people A B and C to choose the best at their turn, from the same, ever decreasing pots of money.''' ====18 then 27 Fibonacci numbers==== <pre>Numbers: [2584, 1597, 987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1] Order: ABC_ABC_ABC_ABC_ABC_ABC : Simple Repetition A gets: 2584 + 610 + 144 + 34 + 8 + 2 = 3382 B gets: 1597 + 377 + 89 + 21 + 5 + 1 = 2090 C gets: 987 + 233 + 55 + 13 + 3 + 1 = 1292 Maximum difference in amounts = 2090 Order: ABC-BCA-CAB_ABC-BCA-CAB : Simple Rotation A gets: 2584 + 233 + 89 + 34 + 3 + 1 = 2944 B gets: 1597 + 610 + 55 + 21 + 8 + 1 = 2292 C gets: 987 + 377 + 144 + 13 + 5 + 2 = 1528 Maximum difference in amounts = 1416 Order: ABC-BCA-CAB-BCA-CAB-ABC : Thue-Morse Fairshare A gets: 2584 + 233 + 89 + 13 + 5 + 2 = 2926 B gets: 1597 + 610 + 55 + 34 + 3 + 1 = 2300 C gets: 987 + 377 + 144 + 21 + 8 + 1 = 1538 Maximum difference in amounts = 1388 Numbers: [196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1] Order: ABC_ABC_ABC_ABC_ABC_ABC_ABC_ABC_ABC : Simple Repetition A gets: 196418 + 46368 + 10946 + 2584 + 610 + 144 + 34 + 8 + 2 = 257114 B gets: 121393 + 28657 + 6765 + 1597 + 377 + 89 + 21 + 5 + 1 = 158905 C gets: 75025 + 17711 + 4181 + 987 + 233 + 55 + 13 + 3 + 1 = 98209 Maximum difference in amounts = 158905 Order: ABC-BCA-CAB_ABC-BCA-CAB_ABC-BCA-CAB : Simple Rotation A gets: 196418 + 17711 + 6765 + 2584 + 233 + 89 + 34 + 3 + 1 = 223838 B gets: 121393 + 46368 + 4181 + 1597 + 610 + 55 + 21 + 8 + 1 = 174234 C gets: 75025 + 28657 + 10946 + 987 + 377 + 144 + 13 + 5 + 2 = 116156 Maximum difference in amounts = 107682 Order: ABC-BCA-CAB-BCA-CAB-ABC-CAB-ABC-BCA : Thue-Morse Fairshare A gets: 196418 + 17711 + 6765 + 987 + 377 + 144 + 21 + 8 + 1 = 222432 B gets: 121393 + 46368 + 4181 + 2584 + 233 + 89 + 13 + 5 + 2 = 174868 C gets: 75025 + 28657 + 10946 + 1597 + 610 + 55 + 34 + 3 + 1 = 116928 Maximum difference in amounts = 105504 </pre> Thue-Morse is best in ''this'' case. Hmmm, I feel a blog coming on... --[[User:Paddy3118\|Paddy3118]] ([[User talk:Paddy3118\|talk]]) 03:50, 26 June 2020 (UTC) ===Fairness and randomized rewards=== I needed to further investigate Horst's work above finding repeated rotations being best, being best, and me finding that for Fibonacci (also above), Thue-Morse wins over repeated rotations. I wrote something that for the rewards just took some random integers and ordered them highest to lowest; then used different orderings of three people selecting their best reward on the from that reward order. The winning ordering would have the least difference between peoples total reward, '''and crucially multiple orderings can have the win if they all have the same minimum spread of peoples winnings.''' ;Results: <pre>## ALL SIMULATIONS BEING OF 3 PEOPLE TAKING TURNS TO TAKE EVER DECREASING AMOUNTS OF CASH FROM A REWARD_LIST. Give summary stats on 250_000 repetitions of: New reward_list = an ordered, random, selection of between 3 and 84 ints from the range 999_999 .. 0: (Note: reward_list length is always a multiple of 3) Each of the following 4 methods of ordering used to order this reward_list [ "Randomised: Gen from repeat(shuffle('ABC')) eg ABC CAB ABC ABC BCA ...", "Simple Repetition: Gen from repeat('ABC') eg ABC ABC ABC ...", "Simple Rotation: Gen from repeat(rotate('ABC')) eg ABC BCA CAB, ABC BCA CAB, ... ", "Thue-Morse Fairshare: Start _sequence_ not replicated later, but 'balanced' ABC's", ] The ordering(s) with the LEAST spread of winnings per person wins the round. SUMMARY Wins for All 250_000 repetitions order_by_thue_morse : 116_022 order_by_rotation : 116_007 order_by_randomise : 51_744 order_by_repetition : 8_905 Wins for All 88_099 repetitions where: len(reward_list) div 9 == 0 order_by_thue_morse : 37_591 order_by_rotation : 37_471 order_by_randomise : 13_037 Wins for All 115_767 repetitions where: len(reward_list) div 9 == 3 order_by_rotation : 42_194 order_by_thue_morse : 42_080 order_by_randomise : 22_588 order_by_repetition : 8_905 Wins for All 88_812 repetitions where: len(reward_list) div 9 == 6 order_by_thue_morse : 36_351 order_by_rotation : 36_342 order_by_randomise : 16_119 Wins for All 26_679 repetitions where: len(reward_list) div 27 == 0 order_by_thue_morse : 11_310 order_by_rotation : 11_209 order_by_randomise : 4_160 Wins for All 62_423 repetitions where: len(reward_list) div 27 == 3 order_by_thue_morse : 20_059 order_by_rotation : 19_973 order_by_randomise : 13_486 order_by_repetition : 8_905 Wins for All 35_168 repetitions where: len(reward_list) div 27 == 6 order_by_thue_morse : 14_211 order_by_rotation : 14_137 order_by_randomise : 6_820 Wins for All 34_589 repetitions where: len(reward_list) div 27 == 9 order_by_rotation : 15_083 order_by_thue_morse : 14_936 order_by_randomise : 4_570 Wins for All 26_598 repetitions where: len(reward_list) div 27 == 12 order_by_rotation : 11_068 order_by_thue_morse : 10_888 order_by_randomise : 4_642 Wins for All 26_654 repetitions where: len(reward_list) div 27 == 15 order_by_thue_morse : 11_045 order_by_rotation : 10_976 order_by_randomise : 4_633 Wins for All 26_831 repetitions where: len(reward_list) div 27 == 18 order_by_thue_morse : 11_345 order_by_rotation : 11_179 order_by_randomise : 4_307 Wins for All 26_746 repetitions where: len(reward_list) div 27 == 21 order_by_rotation : 11_153 order_by_thue_morse : 11_133 order_by_randomise : 4_460 Wins for All 26_990 repetitions where: len(reward_list) div 27 == 24 order_by_rotation : 11_229 order_by_thue_morse : 11_095 order_by_randomise : 4_666 </pre> Thue-Morse wins for this case of random rewards, but not by much! --[[User:Paddy3118\|Paddy3118]] ([[User talk:Paddy3118\|talk]]) 12:04, 26 June 2020 (UTC) :A simple rotation of n slots/people is balanced (= A..Z were all once in every position 1..n ) after n rotations like Thue-Morse, but Thue-Morse changes than the order of the permutations of ABC so A isn't always the first fetcher after nn.That's more fair.Still more work to calculate and for big n the balance nn is hard to reach.After that point Thue-Morse makes the difference over simple rotation. --[[User:Horst.h\|Horst.h]] [[User:Horst.h\|Horst.h]] ([[User talk:Horst.h\|talk]]) 06:39, 27 June 2020 (UTC)