Using optimization to solve allocation problems.
This program solves the problem of allocating T units of something to N different people, each one with a preferred target and acceptable intervals.
This program accepts as input a JSON file containing the total number of units, the price paid for all the units, and each person's preferences. The file should an object with the following properties:
- total: the total amount of units of goods that will be divided;
- price: (Optional) price paid for the total amount of goods. If provided, the program outputs how much each person should pay;
- requirements: the preferences of each person;
The requirements property should be a list of objects with the following properties:
- name: the name of the person;
- interval: the interval of acceptable values for this person. It should be a list with two numbers [lower, upper];
- target: the ideal value for this person. It can be either a number or the strings lower, center, upper, which denote the lower bound, the center, and the upper bound of the interval.
For example:
{
"total": 70,
"price": 10,
"requirements": [
{
"name": "alice",
"interval": [30, 40],
"target": "upper",
},
{
"name": "bob",
"interval": [30, 40],
"target": "lower",
}
]
}
This program works with convex optimization to minimize a custom convex function that models each person's discontent.
First, suppose that the constraints are satisfiable: the total amount is between the sum of lower bounds and the sum of upper bounds. Let , , and be the vectors of lower bounds, upper bounds, and targets, respectively. A solution is:
However, these errors are not all equal. Suppose two people have targets 10 and 100 and that a solution misses these targets by one unit. In proportion, one person achieved 0.9 of their goal and the other 0.99, but they both had equivalent discontent according to the formulation above. We weight the objective function above proportionally to the target magnitude, but lower than a maximum weight :
where . The maximum weight should be chosen such that , where is a minimum target (for example, we can choose for pizza slices). This assures that the solutions are more proportinally fair. This feature can be disabled with the -absolute
flag, which sets all weights to 1.
Now we consider cases where the conditions are not satisfiable. In that case, we add additional error terms that are positive only when a value is outside of the acceptable interval. The parameter, which defaults to 0.2, controls the trade-off between the error in relation to the target and the errors due to a value being outside the acceptable interval. The objective function can be written as:
where . The proportional formulation is:
where the weights and are calculated similarly to . By removing the unsatisfiable constraints and optimizing the objective functions above, we solve these cases.
The problem information should be entirely contained in the input JSON file. The program accepts the following arguments:
--input
,-i
: path to input JSON file. Required;--gamma
: penalties inside the interval are multiplied by gamma. Defaults to 0.2;--t-min
: minimum expected target, used to compute the maximum weight. Defaults to 0.5;-absolute
: if set, the objective will use absolute differences, instead of proportionally weighted differences.
To run this code, you will need:
- Python 3;
- Numpy;
- Cvxpy;