This repository contains the source code of the experiments we have discussed in the MoL thesis "Complexity of Locally Fair Allocations on Graphs".
The file requirements.txt contains all the necessary libraries and tools (with the relative version) to run the code. Directory images contains all images that were generated from the experiments.
Inside the code directory you can find all the code written to perform the experiments. In it is also included the IPython notebook experiments.ipynb, which can be used to run experiments similar to those presented in the thesis.
- Clone the repository
git clone https://github.com/giovannivarr/Complexity-of-Fair-Allocations-on-Graphs
- Install all dependencies listed in
requirements.txt
pip install -r requirements.txt
As already mentioned the experiments.ipynb notebook contains ready-to-run examples of the experiments we have performed.
In the following sections we will briefly show what can be done with the implemented functions, presenting some use-cases for each file in the code directory.
In this file we have implemented some functions to generate graphs which were not included in the NetworkX library (at least up to the version we have used, i.e. version 2.5). For example, to generate a line of 5 vertices, it suffices to run the following code:
G = generate_line(5)
This file contains the two functions we have implemented to generate the utility of an agent for each item. Utilities can be generated by drawing samples either from a uniform or a normal distribution.
For the sake of our example, assume that we want to generate the utility function of an agent for 5 items, drawing the values from a uniform distribution which minimum value is -2 and maximum value 1. Observe that by how the library scipy defines the uniform distribution, we have to provide in this case as inputs -2 for the loc parameter and 3 for the scale one (since the maximum value is given by the sum loc + scale):
u = generate_uniform_utilities_agent_based(-2, 3, 5)
Observe that the utility functions' type is numpy.ndarray.
This file contains the functions which can be used to generate an item allocation. There are four different criteria to define the item allocation (as presented in the thesis), though all are called by a fifth function, generate_allocation. In order to compute an allocation we just need a utility profile and a criterion. The possible options for the criterion are the following:
max_utilitarianmin_envinessmin_unproportionalityrandom
Hence, given a utility profile u, to compute an item allocation that minimizes enviness it suffices to run the following code:
allocation = generate_allocation(u, 'min_enviness')
The last file contains various ways to compute position assignments. At this point, we will assume that we have the following variables are set:
agents, i.e. the number of agents;utilities, i.e. the utility profile (note that these are the utilities for the single items);item_allocation, i.e. the item allocation;G, i.e. the graph (which type isnetworkx.Graphand which nodes' type isint).
First of all, it is possible to generate all possible position assignments of the agents on the given graph. To do so, we just do the following:
assignments = generate_all_assignments(agents, G.nodes())
We can also compute the utilities of each assigned bundle for each agent:
allocated_utils = compute_utilities(agents, utilities, item_allocation)
Now, notice that for each criterion we have defined two functions, one which simply answers whether there is a position assignment that satisfies the criterion (with the fixed item allocation) and one which also finds all of them (if there are any). For the sake of our example, let us consider local envy-freeness. Thanks to what we have done so far, we are now ready to know whether there is a position assignment which satisfies LEF or find it:
exists_lef = exists_envy_free_assignment(agents, assignments, allocated_utils, G)
lef_assignments = find_envy_free_assignment(agents, assignments, allocated_utils, G)
Observe that for local envy-freeness it is also possible to check whether there is an LEF position assignments using a function which defines an ILP. In this case, as one can imagine, the list of all possible position assignments assignments is not needed.
As a final example, we will also show how to use the proofs of Theorems 2 and 8 to find whether there is a position assignment that either satisfies LEF or LEF1 in case the social graph is a tree. Notice that the following three steps, i.e. those before we will effectively show how to call the functions which follow the algorithms of the two proofs, are all performed in these two final functions, thus they can be omitted.
First, we can compute the agent-types. These can either be the EF ones or EF1 ones (see Definitions 21 and 22 respectively) based on the criterion we are considering. For our example, we will again consider local envy-freeness, thus the EF agent-types. To compute the agent-types, it suffices to do the following:
ef_agent_types = find_envy_agent_types(agents, allocated_utils)
Also, we can compute the vertex-types of the tree (see Definition 20). Notice that the tree must be a directed one (i.e. it must be a networkx.DiGraph), as otherwise the function will not work properly as explained in the comment below the definition of such function. In our case, the tree must be directed starting from the root and going down towards the leaves. Given a tree T, to find the list it suffices to call the following function:
vertex_types = find_vertex_types(T)
Given the vertex-types we can compute, for each pair of vertex-types t, t', how many vertices of type t' are child vertices of a vertex of type t. From now on, we denote with r the root of the tree. Note that the following function computes this value for any possible pair, and not a single one.
vertex_types_edges = find_vertex_types_edges(T, r, vertex_types)
As anticipated before, it is possible to check whether there is a position assignment that respects LEF or LEF1 using the two FPT algorithms we provided in the thesis.
model_exists_lef = parameterized_tree_lef_position_assignment(T, r, agents, allocated_utils)
model_exists_lef1 = parameterized_tree_lef1_position_assignment(T, r, agents, allocated_utils, utilities, item_allocation)
Notice that the two functions return a MIP model, meaning that they are not booleans telling whether there is or not an assignment (unlike the previous functions we have shown). To know whether the model m has a solution (and thus whether there is a position assignment), it suffices to do the following:
from mip import OptimizationStatus
m.optimize() == OptimizationStatus.OPTIMAL