I am working on part of a program to return certain values from a dictionary, the scenario is as follows:

"The voting rule works in rounds. In each round, the alternatives that appear the least frequently in the first position of agents' rankings are removed, and the process is repeated. When the final set of alternatives is removed (one or possibly more), then this last set is the set of possible winners." I am trying to return this final set.

Alternatives = values in a dictionary, these are in a list format. Agents = keys from the dictionary. The dictionary is a "preference profile" that ranks each alternative as a preference, 1 = most preferred. Example dictionary: Agent 1 prefers alternative 3 the most

preferences = {
 1: [4, 2, 1, 3],
 2: [4, 3, 1, 2],
 3: [2, 3, 1, 2],
 4: [1, 3, 4, 2],
 5: [2, 3, 4, 1],
 6: [2, 1, 3, 4]}

My attempt at coding this:

def votingRule(preferences):
    dictionary = preferences.copy()
    removed_values = set()
    while dictionary:
        values = set()
        for vals in dictionary.values():
            values.update(vals) 
        
        frequencies = {value: 0 for value in values}
        for values in dictionary.values():
            try:
                if values[0] in frequencies:
                    frequencies[values[0]]  = 1 
            except IndexError:
                pass
        print("1st Freqs",frequencies) # this stage returns a correct count of each element

        if not frequencies:
            return set()
        min_frequency = min(frequencies.values())
           
        current_removed_values = set()
        for value in frequencies:
            for ele in dictionary:
                if frequencies[value] == min_frequency:
                    for key in dictionary:
                        if value in dictionary[key]:
                            dictionary[key].remove(value)
                            current_removed_values.add(value)
                break
            else:
                dictionary = {}                            
        removed_values = current_removed_values      
    return removed_values

I can return a correct count of the frequencies of each element in each round but I cannot correctly identify to final set of removed values.

E.g. using the example above my code would return:

Step by step output = 
1st Freqs {1: 1, 2: 3, 3: 0, 4: 2}
[4, 2, 1, 3]
1st Freqs {1: 1, 2: 3, 4: 2}
[4, 2, 1]
1st Freqs {2: 3, 4: 3}
[4, 2] #this would be the correct set to return as they have the same frequency but the loop continues
1st Freqs {2: 1}
[2]

Final output = {2}
Desired final output = {4, 2}

Would anyone be able to advise how to correct this? Is there a more efficient way to appraoch this problem?

Thank you

CodePudding user response：

Meaning of preferences array

preferences = {
 1: [4, 2, 1, 3],
 2: [4, 3, 1, 2],
 3: [2, 3, 1, 2],
 4: [1, 3, 4, 2],
 5: [2, 3, 4, 1],
 6: [2, 1, 3, 4]}

preferences dictionary represents:

• 6 voters (agents)
• Agent 1 prefers 4 in 1st round, 2, in 2nd, 1 in 3rd, and 3 in 4th
• Agent 2 prefers 4 in 1st round, 3, in 2nd, 1 in 3rd, and 2 in 4th,
• etc.

Voting Rule

The voting rule works in rounds (slight modification of post)

• In each round, the alternative that appears the least frequently (least common) in the current index of agents' rankings is removed (only if there is only one)
• The index is incremented and the process is repeated using the next index.
• The process terminates when there is only one candidate or we loop through all the rounds

Code

def votingRule(preferences):
    
    len_vals = len(list(preferences.values())[0])           # number of values in each list
    candidates = set(range(1, len_vals 1))                  # condidates is 1 to number of values in lists

    for index in range(len_vals):
        # Get most common value for current index
        vals = [v[index] for v in preferences.values()]    # values for current index
        cnts = Counter(vals)                               # Count of values at current index
        _, freq = cnts.most_common()[:-2:-1][0]            # frequency of least common

        # candidates which are the least common
        least_common_candidates = set(tup[0] for tup in cnts.items() if cnts[tup[0]] == freq)

        # Remove if only one least common
        if len(least_common_candidates) == 1:
            candidates = candidates - least_common_candidates

        # Done if only one candidate left
        if len(candidates) == 1:
            break
            
    return candidates

Test

 print(votingRule(preferences))
 # Output: {2, 4}