Sequential Allocation
QQ1703105484
Background:
In this assignment you will design an algorithm for allocating items to a set of agents with preferences over those items. In particularly, we have a set of m items to be assigned to a set of n agents, such that each item will be given to exactly one agent (but agents can receive multiple items). Every agent has a preference ordering ≻ where α≻β means that the agent prefers item α to item β.
For example, if we have a voting setting with 3 agents and 4 items, the possible preferences could be the following:
Agent 1: α≻γ≻β≻δ
Agent 2: α≻β≻δ≻γ
Agent 3: γ≻β≻α≻δ
To allocate the items to the agents, we will use the Sequential Allocation Rule.
Sequential Allocation:
First, fix an ordering of the agents, according to which they will pick. Then, agents will take turns according to this ordering and will pick their favourite available items (which have not already been picked by other agents earlier), according to their preferences.
In the example above, if the ordering is Agent1, Agent2, Agent3, then the final allocation will be:
Agent1 -> α,δ
Agent 2 -> β
Agent 3 -> γ
If the ordering is Agent2, Agent 1, Agent3, then the final allocation will be:
Agent1 -> γ
Agent 2 -> α,δ
Agent 3 -> β
Objective:
Task 1: Define a class called "Agent" that will correspond to the agents of the assignment. The class should have the following attributes:
name: This will be a string that will be the first name of the agent.
surname: This will be a string that will be the surname of the agent.
preferences: This will be a list of numbers, e.g., [1, 5, 4, 3, 8] that denote the preferences of the agent for the items. In particular, the list [1, 5, 4, 3, 8] will mean that the preference of the corresponding agent is 1≻5≻4≻3≻8. Note that the numbers 1, 5, 4, 3, 8 represent the items of the assignment.
The class should have the following methods:
__init__(self, name, surname): The method should set the name and surname attributes as inputted upon creation of an object of the class. It should also set the preferences attribute to an empty list.
__str__(self): The method should return a string consisting of the first name of the agent followed by the surname. For example, if we create an object of the class as follows:
agent1 = Agent("Aris", "Filos-Ratsikas")
then the command print(agent1) should display "Aris Filos-Ratsikas".
setPreferences(self, newPreferences): The method should input a list of numbers (corresponding to the preferences) and should set the preferences attribute to now be that list.
returnPreferences(self): The method should return a list with the preferences of the agent, as stored in the attribute preferences.
Task 2: Implement the Sequential Allocation Rule, which will be given by the following function.
sequentialAllocation(agentList, order) -> dict
The function should input a list of agents, meaning a list containing data types of the type "Agent", i.e. objects of the class defined above. It should also input a string which will denote the order according to which the agents will pick their items. The only two values that this argument will take will be either "name" or "surname"; you don't have to check for other values or other types of inputs, and the tests will not give any other different inputs for this argument. These two values correspond to the order in which the algorithm will be run. If we use the input "name", then the agents will pick in alphabetical order of first name (those starting with "A" picking first and those starting with "Z" picking last). If the we the input "surname", then the agents will pick in alphabetical order of surname. Your implementation of the function should make sure that this ordering is enforced.
The function should return a dictionary, in which the keys will be the agents (again, objects of the data type "Agent") in the order in which they appear in the input list agentList, and the values will be lists of numbers, corresponding to the items that the sequential allocation rule will assign to these agents.
For example, if we create three objects of the class Agent as follows:
agent1 = Agent("Bill", "Bruford")
agent2 = Agent("Greg", "Lake")
agent3 = Agent("Robert", "Fripp")
then a potential input agentList to the function could be the list [agent1, agent2, agent3]. Of course, to run the algorithm and allocate the items, we will need to use the preferences of the agents. These can be set via the setPreferences method as described above. If we set the as in the example above and we run the algorithm with the option "name" for the ordering argument (which will result in the order agent1, agent2, agent3), then the output dictionary should be:
{"Bill Bruford": [α,δ]
"Greg Lake": [β],
"Robert Fripp: [γ]}
Clarifications and hints:
Your submission should not contain any code for creating objects or any type of tests, as this may cause the autotests to fail. All the examples of creating objects and inputs above are to help clarify things. Ultimately, what is needed from your code is the class Agent (with its corresponding attributes and methods) as well as the function sequentialAllocation with its input arguments. You may create extra functions if that helps you which will be called within the sequentialAllocation function.
As explained above, the sequentialAllocation function will need to fix an ordering of the agents based on the value "name" or "surname", according to which they will pick the items. To do this, you may want to use the insertionSort algorithm that was implemented and presented as part of the Pylgorithms section of the module. Note however that the algorithm is coded to sort a list of numbers. What you want to do here is to sort a list of data types of the type "Agent", according to an attribute of the object "Agent", namely the "name" or the "surname" attribute. For this, you will need to modify parts of the algorithm to access these attributes from the list of agents that is given as input. You may also choose to implement this functionality in a different manner of course.
Your mark will be determined based on the following:
Disclaimer: It is possible (but quite difficult) to try to "cheat" the tests by "hardcoding" the answers to the test. Your code will be checked manually afterwards, and if such hardcoding is detected, you will be penalised. This refers only to extreme cases and it is not going to happen "by accident".
You should submit a single file named sequential.py.