Let there be $n$ indivisible heterogenous items.
Let there be $m$ agents.
The subjective utility functions of the agents are additive and identical. i.e $\forall X,i,j\ V_i(X) = V_j(X)$.
The additional constraint is:
there are agents that some items cannot be assigned to them (i.e the qualification constraint)
This can be defined by a matrix $Q \in Z_2^{m,n}$
where $Q_{i, j} = 1$ iff agent i is qualified to be assigned item m.
The task
I would like to be able to do the following:
- define some fairness criterion that matches the problem
- find an algorithm that provides an allocation that implements it.
I believe that due to the qualification constraint some standard fairness criteria, like $EF1$, may not exist. This is why I am also asking for a fairness criterion.
We can define the problem as an optimization problem, and than solve it using a suitable solver.
define $X \in Z_2^{m, n}$ as the decision variable.
$X_{i, j} = 1$ will denote that item j was decided to be assigned to agent i and $X_{i, j} = 0$ will denote the opposite.
Therefore the optimization problem is the following: $$ \text{minimize f(X)}$$ $$ \text{subject to } \forall j \sum_i X_{i, j} = 1$$ $$ \ \quad\qquad\qquad \sum_{i, j} X \circ Q = n $$ where $f(X)$ is the fairness objective.
the first constraint ensures every item is assigned to exactly one agent.
the second constraint ensures that the qualification constraint is satisfied.
As for the fairness objective, I decided to minimize the amount of envy.
therefore $f(X)$ is defined as: $$f(X) = max(Xv) - min(Xv)$$ where $v = [v_1, v_2, ... v_n]^t$ is the vector of the values of the items.
Other fairness objectives could be used as long as they are convex.
this optimization problem is a non-linear mixed integer programming problem and can be solved by using suitable solvers. An example for a solver is the python library cvxpy.
here is the part it discusses mixed integer programming