I have a seemingly simple task that I want to solve using an online algorithm but unfortunately I wasn't able to find relevant resources even though it seems so basic.
The inputs are $D=(d_1,\dots,d_m)$ a distribution, $P=(p_1,\dots,p_m)$ positive prices and $K=(k_1,\dots,k_m)$ an allocation of integers to be augmented. At every turn we get $q$ points to spend, choose an augmentation $J=(j_1,\dots,j_m)$ of integers such that $\langle J,P\rangle\approx q$ and augment $K=K+J$. I don't want to worry too much about utilizing exactly $q$ points and turn this into some Knapsack problem, new points will keep coming so small leftovers aren't so bad. The goal is to make $\frac{K\odot P}{\langle K,P\rangle}$ resemble $D$, ($\odot$ denotes element-wise multiplication).
I'll give examples and try to make things clearer.

Approach 1: The most basic approach is the non-adaptive one, simply keep drawing $i\sim \frac{d_i}{p_i}$ and augmenting $k_i$ by $1$, until we run out of points. Remember the last draw (where we didn't have enough points left) to start with in the next turn, so that we don't bias against larger prices. (Can assume $q$ is larger than all prices)
The problem with this approach is inaccuracy: We want to use adaptiveness in order to get better convergence. For example if $m=2$ with $d_1=d_2=0.5$ and $p_1=p_2=1$ then instead of drawing $i$ at random, it would be smarter to choose $\arg\min_ik_i$ and balance between them.

Approach 2: The adaptive approach that seemed natural to me but failed, is to use the residual distribution. For every $i$ we compute how much weight is missing, $d_i-\frac{k_i p_i}{\langle K,P\rangle}$ (setting negative results to zero) and divide by the jump size $p_i$. Namely, we keep augmenting using draws $i\sim \max\left(\frac{d_i-\frac{k_i p_i}{\langle K,P\rangle}}{p_i},0\right)$, updating the weighting after every draw.
Unfortunately, this approach is problematic. For example, assume that $m=10$, $\forall i:\:d_i=0.1$ and $p_i=1$ except for $p_{10}=10$. Say that we want to distribute $q=20$ points, so logic indicates we want to distribute in expectation around $2$ points in each cell. However, what is probably going to happen is that we distribute $1$ point to every $i$ other than $10$, and then immediately turn to increase the only under-represented choice left, $k_{10}$ by $1$, causing it to be largely over-presented.
We can try to fix that using a loss function assigning values to allocations and using the post-step value when assigning weights, but I don't see a natural way to do that. We don't only care about distance between $\frac{K\odot P}{\langle K,P\rangle}$ and $D$, but also about how hard it would be to bridge the gap. If $\frac{K\odot P}{\langle K,P\rangle}\equiv D$ it would be natural to have the same behavior as the non-adaptive case, and they are expected to get closer over time but we don't expect to converge into the non-adaptive behavior.

I also want to comment that if all $p_i$'s are equal, then this question is similar to dividing seats after an election: The distribution $D$ is determined by the distribution of votes, $q$ is the number of seats to be distributed, and we start with $K=0$.

Also, another property that I care about but not sure how to formulate: Let's say that all $p_i$'s and all $d_i$'s are equal, and let's say that for some reason we were given $k_1=10,\,k_2=0,\,k_3=1$, and we want to distribute $1$ point. One legitimate approach would be to immediately go for $k_2$ because it is minimal, but I think that a more fair and continuous approach would be to also give $k_3$ a chance, though slightly smaller. For example, pick $k_2$ w.p. $4/7$ and $k_1$ w.p. $3/7$.

Any advice would be appreciated, thanks!

  • $\begingroup$ It looks like the Webster/Sainte-Laguë method performs pretty well, but in some sense fairness and continuity are compromised. I'd like to use randomness in order to fix that. $\endgroup$
    – Nathan
    Jan 3 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.