5
$\begingroup$

Short question: Propose a formula to apply on x0, x1, x2, ..., xn that returns a number which can sort these 7 datasets in this order:

enter image description here

Medium question:

Given 3 datasets, I want to have a formula that returns a number to represents the "(un)fairness" of a dataset, so I can sort/compare the datasets on that.

Let's define fairness as the best situation for the worst, then the best situation for the second worst, and so on. For example, suppose we want to make assigning 15 shifts to 5 employees as fair as possible.

enter image description here

In the above example, the middle dataset is the fairest, because the employee worst off (most shifts, so purple), is the best off (least shifts, only 5 in the middle dataset). However, if we calculate the variance (2.8) on these datasets, the second and third dataset have the same number.

enter image description here

Is there a formula for number (let's call it Fairness Variance for now) that would allow us to sort these datasets on fairness?

Long question: See this blog article which demonstrates that all common formula's (including standard deviation etc) don't work properly. Does such a formula even exist? Can anyone prove it does or doesn't?

$\endgroup$
6
  • $\begingroup$ it sounds like you are looking for $$\max_{i} \left|a_i - \mu \right|,$$ where $\{a_i\}_i$ is your sample and $\mu$ is the expected mean (3 in your example) $\endgroup$
    – gt6989b
    Feb 1, 2017 at 16:05
  • $\begingroup$ That works to distinguish the middle and the bottom dataset (and the top and the middle one), but not the top and the bottom dataset. Those 2 datasets both have a max of 6, so minus the mean that makes 3 each. $\endgroup$
    – Geoffrey De Smet
    Feb 1, 2017 at 19:27
  • $\begingroup$ I suspect what you want is impossible, but how do you define "work properly"? $\endgroup$
    – Michael Lugo
    Feb 14, 2017 at 14:43
  • $\begingroup$ @MichaelLugo I'd define it as: sort a number of datasets by their biggest number first, then by their second biggest number and so on. If it sorts the 7 schedules in the top of this question correctly, it probably works properly. See my blog post for examples of formula's that don't work properly. $\endgroup$
    – Geoffrey De Smet
    Feb 14, 2017 at 14:46
  • 1
    $\begingroup$ There is such a formula, then: write your vector $x_1, x_2, \ldots, x_n$ as a number in base $b = x_1 + x_2 + \cdots + x_n$. So you can use $x_1 b^{n-1} + x_2 b^{n-2} + x_3 b^{n-3} + \cdots + x_n b^0$. But these scores are probably larger numbers than you want... $\endgroup$
    – Michael Lugo
    Feb 14, 2017 at 14:58

2 Answers 2

Reset to default
2
+50
$\begingroup$

An ideal measuring function $\,g(x)\,$ should indicate that an equally schedule “all employees had the same number of tasks $\,(\alpha)\,$” is more fair than the perfect fair schedule with one employee has $\,(\alpha+1)\,$ task. $$ n\cdot g(\bar{x}) \,\color{red}{\lt}\, n\cdot g(\alpha) \,\color{red}{\lt}\, (n-1)\cdot g(\bar{x})+g(\alpha+1) $$ Where:
$\,\qquad\qquad\,\bar{x}\,\colon\,$ ideal number of tasks. $\,\left(\,\bar{x}=3\,\right)\,$.
$\,\qquad\qquad\,n\,\colon\,$ number of employees. $\,\left(\,n=5\,\right)\,$.

And by considering the inequality: $\,n\,(n+1)^{\alpha}\,\lt\, (n+1)^{\alpha+1}\,$,
It is possible to create a good formula as follow: $$ \begin{align} {\small\text{Measuring}\,\text{function}}\quad g(x_i) &=n^{\left| x_i-\bar{x} \right|} \\[3mm] {\small\text{Deviation}\,\,\,\text{function}}\quad d(\,n\,) &= \frac{\sum_{i=1}^{n}g(x_i)}{n} =\frac{\sum_{i=1}^{n}\,n^{\left| x_i-\bar{x} \right|}}{n} \\[3mm] {\small\text{Unfairness}\,\text{function}}\quad f(\,n\,) &= \log_{n}\frac{\sum_{i=1}^{n}g(x_i)}{n} = \color{red}{\frac{\log\left(\sum_{i=1}^{n}\,n^{\left| x_i-\bar{x} \right|}\right)}{\log{n}}-1} \\[3mm] \end{align} $$ Where the logarithmic scale shall keep the numbers reasonably readable.

enter image description here

$\endgroup$
2
  • $\begingroup$ Wonderful, now the only challenge is improving numeric stability when calculating these with normal 64-bit integers or floating points. I am especialy worried about the n^x overflowing. $\endgroup$
    – Geoffrey De Smet
    Feb 15, 2017 at 14:35
  • 1
    $\begingroup$ @GeoffreyDeSmet: Thanks, glad you like it. Yes, the floating points it is a point of worried for large $n$ and large $\Delta_i=|x_i-\bar{x}|$. Considering the practical numbers, you may wish to select a proper Data_Type. For example: $ \text{Max}({\small\text{Unsigned_Long_Long}}) = 18,446,744,073,709,551,615 \approx 2\times10^{20} $, Thus above formula should work well for $\left(\,n=10^5,\,\text{Max}(\Delta_i)=4\,\right)$, or $\left(\,n=1000,\,\text{Max}(\Delta_i)=7\,\right)$, … etc. $\endgroup$
    – Hazem Orabi
    Feb 15, 2017 at 15:00
2
$\begingroup$

So you have three samples: $\vec{a} = (1, 1, 2, 5, 6)$, $\vec{b} = (1, 2, 2, 5, 5)$, $\vec{c} = (1, 2, 3, 3, 6)$. All have mean 3.

As gt6989b suggested, defining the unfairness $f(\vec{v}) = \max_i |v_i - \mu|$, where $\mu$ is the sample mean is a possibility. But in this case $f(\vec{a}) = f(\vec{c}) = 3$, and at lest to my eye $\vec{c}$ looks fairer than $\vec{a}$.

One possibility that comes to mind is $f(\vec{v}) = 1 v_1 + 2 v_2 + \cdots + n v_n$, where I'm assuming that the $v_i$ are sorted, i. e. $v_1 \le v_2 \le \cdots \le v_n$. In this case you have

$$f(\vec{a}) = 1 \cdot 1 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 5 + 5 \cdot 6 = 59$$ $$f(\vec{b}) = 1 \cdot 1 + 2 \cdot 2 + 3 \cdot 2 + 4 \cdot 5 + 5 \cdot 5 = 56$$ $$f(\vec{c}) = 1 \cdot 1 + 2 \cdot 2 + 3 \cdot 3 + 4 \cdot 3 + 5 \cdot 6 = 56$$

The nice thing about this definition of unfairness is that it decreases when you move a shift from a person with more shifts to a person with less. In particular it will be minimized when all employees have an equal number of shifts. In addition it takes all the people into account, not just those at the extremes of the distribution. It's not so obvious that this is a problem when you only have five people, but I believe (from previously looking at OptaPlanner as a possible scheduling engine!) that you have bigger problems in mind.

$\endgroup$
2
  • 1
    $\begingroup$ Yes, I 'd like this to scale to n = 100 000 and more :) Sorting the datasets by this number should give a sorting from fairest to unfairest: b, c, a. In the formula proposed in this answer, it gives b and c the same number, but they aren't equally fair. (Note that variance has the exact same problem.) $\endgroup$
    – Geoffrey De Smet
    Feb 1, 2017 at 19:32
  • $\begingroup$ I tried a few more combinations with this formula, and it seems to have more problems than a plain variance. $\endgroup$
    – Geoffrey De Smet
    Feb 3, 2017 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .