pythonalgorithmsortingdistributionvoting-system

Python3 - Whats the best way to allocate rations among hungry wolves?


I have a problem that wants me to write a program for distributing x amount of fish to x amount of wolves. Heres the exact question.

50 hungry wolves went fishing and caught 50 fish. Now they need to allocate these 50 identical fish among them. Their democratic system works as follows: All wolves are ranked by their seniority. First, the most senior wolf (called "pack leader") proposes an allocation plan that states exactly how many fish each wolf would get. The 50 wolves would vote on the plan (no filibuster) and it would pass if more than or equal to half wolves voted for it. If it passes, wolves take their fish and eat it. If it fails, the one who proposed the plan (the pack leader in this case) would be killed, and then the second most senior wolf would take the place of "pack leader" and propose his plan. We repeat the same process above in the order of seniority until someone's plan is passed. Assume every wolf makes his decision based on the following priorities: 

  1. He doesn't want to die. 
  2. Given he's not going to die, he would prefer to get as many fish as possible. 
  3. Given he's going to get the same number of fish, he would prefer as many other wolves to die as possible.

Ive written most of the logic, but I am unsure how to optimize the distribution so it follows the priorities correctly. If anyone could point me in the right direction I'd be more than happy to figure out the rest, perhaps there is a module I could use based on a binomial distribution (scipy, pandas)

Here is my code so far.

import math
import numpy as np

def findDistribution(num_w, num_f):
    ranked_wolves = list(range(num_w+1))[1:] # 1-50
    distribution = [0]*num_w


    for index, pack_leader in enumerate(ranked_wolves):
        num_w = len(ranked_wolves[index:])
        wolfpack = distribution[index:]
        remaining_fish = num_f

        # If Wolf is last one then takes all fish
        if len(wolfpack) == 1:
            distribution[index] = remaining_fish
            break

        for wolf, value in enumerate(distribution[index:]):
            portion = remaining_fish/len(wolfpack)

            if wolf == 0:
                amount = math.ceil(portion)
                distribution[index] = amount # Pack LEader Gets the Most
                wolfpack.pop()
                remaining_fish-= amount
                continue
            else:
                amount = math.ceil(portion)
                distribution[index+wolf] = amount
                wolfpack.pop()
                remaining_fish -= amount

        # Voting
        # Count all wolves with same number of fish
        mode = stats.mode(distribution[index:])
        total_votes = len(distribution[index:])
        vote_no = mode.count[0]
        vote_yes = total_votes - vote_no

        # If more wolves without food than wolves with food
        if num_f/len(distribution[index:]) < .5:
            distribution[index] = -1

        # Going to get same number of fish so vote no
        elif vote_yes >= vote_no :
            break
        else:
            distribution[index] = -1


    # Return a tuple, with first value being the wolf number whose proposal
    # is accepted and the second value being a list of the distribution for
    # every wolf (-1 for dead wolves).
    return pack_leader, distribution

Solution

  • I think you are missing the point of an exercise. The logic is much more involved.

    Consider a case of 2 wolves (#0 and #1, which is a leader). The leader proposes 0, 2 (taking everything), and votes for it - thus assuring passing 50%.

    Now see what happens with 3 of them (#0, #1, and #3, which is a leader). The plan 0, 0, 3 would fail: #1 is happy to become a leader, #0 is bloodthirsty. So #2 has to come up with the different plan, and it clear that the best is 1, 0, 2. Here #0 would vote for it, because if it votes against the leader will be killed, they are in a 2 wolves case, and it will get nothing.

    Try to go over a 4 and 5 wolves scenario with paper and pencil, and see how the logic works there (the plans should be 0, 1, 0, 3 and 1, 0, 1, 0, 3 respectively). Then you may start to program that logic.