/woptim

Using optimization to solve allocation problems.

Primary LanguagePythonMIT LicenseMIT

woptim

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.

Input Specification

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",
        }
    ]
}

Method

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 l, u, and t be the vectors of lower bounds, upper bounds, and targets, respectively. A solution is:

x^* = \arg\min_x \sum_{i=1}^{N}(x_i - t_i)^2

\text{s.t. } l_i \leq x_i \leq u_i, \ \forall i = [1 .. N].

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 W:

x^* = \arg\min_x \sum_{i=1}^{N}w^l_i (x_i - t_i)^2

\text{s.t. } l_i \leq x_i \leq u_i, \ \forall i = [1 .. N],

where w^l_i = \min(1/t_i, W). The maximum weight should be chosen such that W = 1 / t_{min}, where t_{min} is a minimum target (for example, we can choose t_{min} = 0.5 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 \gamma 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:

E(x) = \gamma \sum_{i=1}^{N}(x_i - t_i)^2 + \sum_{i=1}^{N}(l_i - x_i)_+^2 + \sum_{i=1}^{N}(x_i - u_i)_+^2,

where (.)_+ := \max(0, .). The proportional formulation is:

E(x) = \gamma \sum_{i=1}^{N}w_i^t(x_i - t_i)^2 + \sum_{i=1}^{N}w_i^l(l_i - x_i)_+^2 + \sum_{i=1}^{N}w_i^u(x_i - u_i)_+^2,

where the weights w^l and w^u are calculated similarly to w^t. By removing the unsatisfiable constraints and optimizing the objective functions above, we solve these cases.

Usage

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.

Requirements

To run this code, you will need:

  • Python 3;
  • Numpy;
  • Cvxpy;