Background:

In this assignment you will design and implement several voting rules. In a voting setting, we have a set of

$$

agents and a set of

$$

alternatives. Every agent has a preference ordering

$$

where

$$

$$

$$

means that the agent prefers alternative

$$

to alternative

$$

$.$ A preference profile is a set of

$$

preference orderings, one for every agent.

For example, if we have a voting setting with $4$ agents and $4$ alternatives, one possible preference profile could be the following:

Agent $1$:

$$

$$

$$

$$

$$

$$

$$

Agent $2$:

$$

$$

$$

$$

$$

$$

$$

Agent $3$:

$$

$$

$$

$$

$$

$$

$$

Agent $4$:

$$

$$

$$

$$

$$

$$

$$

A voting rule is a function that takes as input the preferences of a set of agents and outputs a winning alternative.

Consider the following voting rules:

Voting Rules:

Dictatorship:

An agent is selected, and the winner is the alternative that this agent ranks first. For example, if the preference ordering of the selected agent is

$$

$$

$$

$$

$$

$$

$$

$,$ then the winner is alternative

$$

$.$

Plurality:

The winner is the alternative that appears the most times in the first position of the agents' preference orderings. In the case of a tie, use a tie$-$breaking rule to select a single winner.

Veto:

Every agent assigns $0$ points to the alternative that they rank in the last place of their preference orderings, and $1$ point to every other alternative. The winner is the alternative with the most number of points. In the case of a tie, use a tie$-$breaking rule to select a single winner.

Borda:

Every agent assigns a score of

$0$

to the their least$-$preferred alternative $($the one at the bottom of the preference ranking$),$ a score of

$1$

to the second least$-$preferred alternative, $...,$ and a score of

$$

$$

$1$

to their favourite alternative. In other words, the alternative ranked at position

$$

receives a score of

$$

$$

$$

$.$ The winner is the alternative with the highest score. In the case of a tie, use a tie$-$breaking rule to select a single winner.

Harmonic:

Every agent assigns a score of

$1$

$$

to the their least$-$preferred alternative $($the one at the bottom of the preference ranking$),$ a score of

$1$

$$

$$

$1$

to the second least$-$preferred alternative, $...,$ and a score of

$1$

to their favourite alternative. In other words, the alternative ranked at position

$$

receives a score of

$1$

$$

$.$ The winner is the alternative with the highest score. In the case of a tie, use a tie$-$breaking rule to select a single winner.

Single Transferable Vote $($STV$)$:

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. If there are more than one, a tie$-$breaking rule is used to select a single winner.

Example:

Consider the preference profile of the example above. In the first round alternative $(\backslash$delta is removed$\backslash )$ and we get the following new preference profile:

Agent $1$:

$$

$$

$$

$$

$$

Agent $2$:

$$

$$

$$

$$

$$

Agent $3$:

$$

$$

$$

$$

$$

Agent $4$:

$$

$$

$$

$$

$$

In the second round, both

$$

and

$$

are removed. In the third round,

$$

is removed, and

$$

is the winner.

Tie$-$Breaking Rules:

We will consider the following three tie$-$breaking rules. Here, we assume that the alternatives are represented by integers.

max: Among the possible winning alternatives, select the one with the highest number.

min: Among the possible winning alternatives, select the one with the lowest number.

agent

$$

: Among the possible winning alternatives, select the one that agent

$$

ranks the highest in his$/$her preference ordering.

Objective:

Task $1$: Implement a function called generate$\_$preferences$($values$)$ which inputs a set of numerical values that the agents have for the different alternatives and outputs a preference profile.

In particular:

The input values to the generate$\_$preferences function is a worksheet corresponding to an xlsx file.

Note: By worksheet, it is meant what we have seen as a worksheet in class, meaning an openpyxl worksheet. Note that the input to the function should not be an xlsx file or a workbook. See Lab Session $10-$ Week $11-$ Handling Data

The rows of the file correspond to agents and the columns correspond to alternatives. The value of a cell

$$

$,$

$$

is a numerical value that signifies how happy the agent would be if that alternative were to be selected. We refer to that value as the valuation of the agent. An example of such a worksheet is the following:

$0\mathrm{.}2961780\mathrm{.}4343620\mathrm{.}0330330\mathrm{.}758968$

$0\mathrm{.}5593230\mathrm{.}4557920\mathrm{.}7704230\mathrm{.}770423$

$0\mathrm{.}590960\mathrm{.}519580\mathrm{.}7316060\mathrm{.}767473$

$0\mathrm{.}5551080\mathrm{.}3442850\mathrm{.}5434840\mathrm{.}396021$

$0\mathrm{.}8362790\mathrm{.}9509280\mathrm{.}8719960\mathrm{.}852851$

$0\mathrm{.}7934271\mathrm{.}5091480\mathrm{.}7006210\mathrm{.}659306$

Here for example, the value of agent $5$ for alternative $2$ i