Document stochastic voting procedure

[riastradh-brave]

The procedure implemented by Synopsis.prototype.weights in index.js determines how Brave distributes its votes to publishers according to the caller-supplied attention weights w_i and publisher pin weights p_i.

The procedure to distribute n votes is currently simply to draw a multinomial sample of publishers weighted by the w_i, ignoring the p_i. (Presumably the caller just sets w_i = p_i where p_i is specified, but I don't know; the caller is somewhere in browser-laptop or something.)

After #24 as it stands right now, the procedure to distribute n votes will become something like this:

1. Permute the list of publishers uniformly at random.
2. For each publisher i in the permuted order of step (1), distribute round(n*p_i) votes to the ith publisher (where round is IEEE 754 round-to-nearest/ties-to-even?), or stop if we have run out.
3. If any ballots remain after step (2), which happens if the sum of the p_i is below (one floating-point epsilon beneath) 1 - 1/n, randomly draw a multinomial sample of the publishers weighted by the w_i.

The attention weights and the pin weights are independent: a pinned publisher can have votes from step (2), arising from pinning, and from step (3), arising from attention.

(An n-way multinomial sample with k prescribed weights is an array of k counts adding up to n, equivalent to counting up a sequence of n independent categorical samples with the k prescribed weights -- i.e., an n-way multinomial sample is an array of counts from rolling a k-sided die n times.)

From what I have gathered, there are a few criteria constraining the procedure:

• Votes are expensive: each one requires an independent round-trip to the server. So we want to minimize the number of votes to maintain low communication cost.
• Votes are the granularity available to us. So we want to maximize the number of votes to maintain high granularity for user allocation of contributions.
• We want the expected fraction of non-pinned votes for the ith publisher, integrated over all users over time, to be the caller's attention weight w_i.
  • This should allow even infrequently attended sites to have the opportunity to profit from attention, even if w_i is so small it might be rounded away by some procedures.
  • Limit? If there were ten billion users using Brave every second of the day for a year and used a site for a single second that day and the weights were the duration spent, that would be about 1/(1e10 * 60 * 60 * 24 * 365) ~= 2^-58. If we cut the weights off at 2^-64 as I expect we do right now with the uniform [0,1] sampler we're using, that's more than adequate for this extreme case so we don't have to worry about very small numbers in floating-point uniform [0,1] sampling (although it's not that hard to drive the limit below anything anyone including cryptographers should care about -- JavaScript code).
• We want the expected fraction of pinned votes for the ith publisher to be the caller's pin weight p_i.
• We want the pinned votes for a single user each settlement to be close to the user's pin weights times the number of ballots the user exchanged BAT for. Otherwise they may look at their receipts and be dismayed.
  For example, if there are a million users each pinning half their contribution to a single publisher of their choice, and each user gets 10 votes, and if the votes are sampled by a naive categorical as in the first procedure, the expected number of users who will see none of their votes go to their 50%-pinned publisher is about 1000. This likely means some nontrivial fraction of 1000 unhappy users posting flames about Brave on the internet.

All this should be written down in a living document that we can use to assess (a) whether Brave is intended to do something sensible and (b) whether Brave actually implements what we intend.

[mrose17]

@riastradh-brave - thanks. it would be more helpful, to make this issue a PR adding text to https://github.com/brave-intl/bat-ledger/blob/master/documentation/Ledger-Principles.md#ad-free-statistical-voting ...

[riastradh-brave]

Additional notes from Rafael Pass passed on by @bridriver (with TeX tidied up by me; \let\eps\varepsilon in preamble):

Let X be the number of ``daily-rewards'' (of \$5/30) that some site
 gets in a month.
If we go for the \$100 cut-off as discussed above (i.e., only sites
 that make more than \$100 per month need to get a reliable payment),
 think of $\mu = E[X] > 600$.

Let's assume that users are independent.
The multiplicative Chernoff bound then says that $\Pr[X < (1-\eps)
  \mu] < e^{-\eps^2 \mu/2}$.
So, if we set $\eps = 0.1$, we get that except with probability
 $e^{-(1/200) \cdot 600} = e^{-3} < 0.05$, the webpage will get 90\%
 of what it is supposed to get.
(And webpages that are supposed to get \$1000 will get at least 97\%
 of that.)

The Chernoff bound says: $\Pr[X < (1-\eps) \mu] < e^{-\eps^2 \mu/2}$,
 where $X = \sum_i X_i$ and $X_i$ are 0/1 r.v.
So you actually don't care about the \# of samples $X_i$, but rather
 the expectation of the sum: you need the expectation $\mu$ to be
 larger than $\eps^2$.
If you want to be within 10\% of the ideal payment, we need the
 expectation to be ${>}600$.
And thus if you just do 1 submission/month this would only kick in for
 websites making 3K.