In the context of my PhD on the simulation of the labor market with a multi-agent model, I encoutered a problem that doesn't seem to be really treated in the litterature, according to my searches on different networks on the subject. This problem is the "Max-Min Fair Allocation of Divisible Heterogenous Goods".

The problem is the following : There are N fully divisible resources, and M agents that can use some of these resources. Each resource has a different utility for each agent (either 0, or a positive value). The goal here is to divide these resources between agents to maximize the least satisfied agent (the one with the least total value across his allocated resources shares).

This problem can be solved using Linear Programming, but I'm looking for an algorithm that can approximately solve this problem. The optimal solution doesn't need to be found, but the results of my current algorithm can be less satisfying that I would like, with a ratio fo around 4 between the least satisfied agent and most satisfied one.

My current algorithm is a Glouthon algorithm with a post optimization phase which transfers shares from "over-satisfied" agents, and the current least satisfied one. The initial allocation of shares is done by giving a share of each resource to each agent according to the value that they give to this resource compared to other resources.

The utility $U_i$ of an agent is the sum of the value $v_{i,j}$ given to each of his allocated resource share : $U_i = \sum_{j \in M} v_{i,j} \times s_{i,j}$ with $s_{i,j}$ the amount of resource $j$ allocated to $i$.

This problem can be described as the Santa-Claus allocation problem as described in Max-Min item allocation on Wikipedia, but this problem has indivsible goods. There are also other papers which describe close problem like How to Divide Hard Candies Farily (2 agents, indivisible goods), or Max-Min Fair Allocation of Indivisible Goods byt Daniel Goglovin (indivisible goods), and Maximin Fairness with Mixed Divisible and Indivisible Goods (contains both divisible goods and indivisible goods).

Is there an algorithm, or a way to compute such an allocation of resources without using linear programing ? This problem is repeated a lot during the model so calling a LP solver multiple times in order to get a good solution is not really feasible. An approximation algorithm is completely acceptible, as my current algorithm doesn't have a specified approximation factor. If this is of any importance, the model is in JAVA.

Thank you for your time.

  • $\begingroup$ The difficulty I see is that many (maybe all?) LP problems could be framed as instances of your problem, so finding an approximation algorithm or a good, fast heuristic for it (BTW, these are two different things) is likely as hard as finding an approximation algorithm or good, fast heuristic for the general LP problem. I suggest just using the LP solver, and "staying inside" it wherever possible, by invoking it using a library interface. Also, if using a simplex solver and the current solution is feasible for the next problem, you may be able to modify and continue instead of starting over. $\endgroup$ Jun 24, 2021 at 4:08
  • $\begingroup$ As the repeated problems are new instances, thus with different resources, agents, values, it is not possible to really start from the first solution in general. Even when the problem is repeated, the resources chan change with each iteration. Thus using a LP solver is not really what I want here, but it may be the only algorithm that can guarantee an optimal solution, or approximate one in a specific time-frame. $\endgroup$
    – Nicinic
    Jun 24, 2021 at 7:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.