Quadratic Payments with constrained probabilities
Trying to understand how QPs act in “real world”, where marginal probabilities could be variable due to probability’s bounded-nature
April 27th, 2021 EDIT
Recently the article has been rewritten in LaTeX to use a typesetting environment more suitable for this kind of content, and is now available on arXiv:2104.12700 (cs.GT) too.
tl;dr
- an inspiring article about quadratic payments
- a simple referendum model introducing generic marginal probability
- how quadratic payments could deal with generic probability
An inspiring article
Some months ago my geek-attention has been caught by this Vitalik Buterin’s article about quadratic payments and how they could be applied to some everyday choices, e.g. voting. In many moments of my life I have wondered how much effective democracy and universal suffrage are for ballots on topics whose evaluation could be influenced by specific knowledge and awareness (for example in Italy in 1987 we had a referendum about the use of nuclear energy for civil purposes). So, starting from the article, I have felt the need to elaborate more by myself, to better understand and -why not- try to go deeper.
Before continuing here, I strongly suggest you to take a look at Vitalik’s words if you haven’t done yet, I think they are really inspiring.
I just quickly recap the concepts about vote pricing, to have a common ground from which going on and to introduce a slightly different notation:
- i is the whole number representing the votes you express, i.e. the votes you have bought;
- c(i) is the price, the cost of the i-th vote;
- p(i) is the probability the referendum will result in your desired outcome when you express i votes (so p(0) is the probability when you don’t take part);
- Δp(i) is the marginal probability: Δp(i)=p(i)-p(i-1), the gain in probability you get when you buy one more vote, the i-th, after the already bought i-1 votes;
- V is how much you value your desired outcome (e.g. if you prefer the “yes” winning in a referendum, it represents how much important that result is).
A reasonable condition is that:
stating that the potential value gain you get for i-th vote has to be higher or equal to the price of the i-th vote: it models the buying threshold of a rational player. Putting it in layman terms:
- V is the value you assign to your desired outcome,
- so if the probability of your preferred final result is 1 then the whole referendum values exactly V as well;
- if instead the probability of your preferred final result is 0 then the referendum has no value for you (you could argue that referendum has negative value, but it can be “absorbed” with an higher V for the case resulting in your desired outcome);
- each time you buy a new vote you increase the probability of getting the preferred final result (which, remember, corresponds to the whole referendum valuing V) by a factor Δp(i), so you don’t want to pay that increase more than the fraction of V (given by Δp(i) ⋅ V ) that you have potentially gained.
Of course the correspondence between actual (not the perceived) value and probability lies in frequency interpretation of the latter and return of investment cannot be guaranteed: a referendum happens only once, you really don’t have many occurrences of it determining “success cases” over “total cases”, and outcome is always binary: “yes” wins or “no” wins, no fuzziness there! That’s why I have used the “potential” and ”potentially” words earlier. Nevertheless the goal here is to build incentives to make influence of each stakeholder proportional to their perceived value V, and previous mathematical stuff works for that.
I also want to underline a couple of Vitalik’s assumptions, I guess for the sake of simplicity given the introductory nature of his article:
- Δp(i) is always considered constant: Δp(i) ≡ Δp
You can suspect that things get more complicated outside of ideal case when he writes: “ […] though eventually the gains will decrease as the probability approaches 100% […] ”, but it seems to be the only reference about it; - influence isn’t actually defined to keep the scope of the reasoning wide, however we can observe that with constant Δp we are in a special case where the influence is simply the number of votes i that you have bought.
That said, the constraint (1) becomes:
The goal is to enforce (2) to act as incentive to get an influence proportional to V, so in our special case we’ll want the maximum number of bought votes imax to be proportional to V.
Different types of cost function c(i) are considered; first case:
so when V reaches c/Δp every vote we want to buy is worth its price: this means imax is unlimited if you can afford c price for each of them: everyone who has a lot of funds to spend has a lot of influence, regardless of how much the desired outcome is valued (V).
Second case:
After the first vote, all the others have infinite cost, meaning you can buy just one, again regardless of V.
We could say first case is too plutocratic, the second one too democratic!
That’s where quadratic payments magic comes on stage! If we use a cost function linear in i (Vitalik uses a smart heuristic reasoning to derive it):
from the constraint (2) we get:
the stairs-like profile derives from imax needing to be a whole number, but linearity in whole Δp⋅V/c is plain! And if we calculate how much we spend to buy imax votes:
which is why we call them “quadratic payments”.
More or less, very summarized and with a little of more math here and there, this is the core of what you can find about voting in Vitalik’s article… now let’s try to make a few steps ahead.
Let’s play with math!
Let’s try to derive in a formal way the linear cost function (3). From (2) we know:
let’s make two assumptions (that of course will have to be verified and will anyway limit the generality of the result):
- c(i) is an invertible function
- its inverse c⁻¹(i) is monotonically increasing (to avoid problems with inequality sign)
which, by the way, can be condensed requiring c(i) to be monotonically strictly increasing; so we can write:
we have a condition limiting i, what we wanted. Then we require the i-upper bound to be proportional to V (remember that we are seeking a c(i) which makes imax ∝ V ):
from simple algebra (multiplying and dividing by ∆p) it follows that:
so we can define:
we invert and get:
Last step, we note (4) is monotonically strictly increasing, so it’s an acceptable result because it respects the previous assumptions. And, as expected it, confirms (3) setting K= Δp/c. So we have:
It’s also useful to underline a few technicalities of the formal derivation:
- K, by which we have imposed the proportionality between influence and perceived value, also acts as a result’s degree of freedom defining both the maximum number of bought votes and the cost of the first one (the cheaper)… and it seems to be an unbounded degree of freedom (apart from, of course, being positive).
- The derivation cannot say anything about not monotonically increasing cost functions because only if it’s monotonically increasing we can, inverting, transform condition on cost c(i) into condition on vote index i; however…
- …it’s not a huge limit by itself because we have an ab-initio more serious lack of generality given by Δp(i) ≡ Δp (if not, we should invert f(i) ≜ c(i) / Δp(i) and we couldn’t obtain a strictly defining condition for c(i) )
By now, it seems obvious we have to dig into the “shape” of Δp(i) in “real life” to make any educated guess on how to proceed.
A simple referendum model
So I brushed up my old interest in voting effectiveness and I tried to come up with a simple ballot model.
Let’s imagine that we are close to a referendum (a ballot with only two possible outcomes: “yes” or “no”): supporting the “yes”, we have done a statistical research on voters and we have got a voting prediction for the “average voter”. What I mean is that, instead of dealing with many different voters, each one with a different probability to vote “yes”, in our calculations we will use the average voter and the voting prediction associated to him (ok, it’s a rough model, but we have to start from somewhere). We have:
- n: number of voters
- y: probability the average voter will vote “yes” (our voting prediction)
- p(y,n): probability the referendum outcome will be “yes”
resulting in:
Let me try to convince you this is a reasonable model.
Each addend of the summation takes into account cases in which “yes” supporters are more than “no” supporters, starting from minimal difference (1 or 2 votes, depending if n is odd or even) and ending with all voters choosing the “yes”.
In each iteration d is the number of “yes” voters, the remaining n-d the number of “no” voters, and the binomial coefficient returns the number of different “order” combinations of “yes” and “no” votes (e.g. yynyn…, yyynn…, nynyy…, …).
Plotting this function gives some by-itself interesting insights into the model:
We can see that when the number of voters n grows, the curve tends to a step function polarizing the outcome (“yes” or “no”) on the sides of a discontinuity of p(y,n) at y=0.5: when there are a lot of voters, also a very small bias in vote preference will cause the referendum result to be “yes” or “no” for certain, depending on the direction of the bias. Luckily, it’s what we expect from a referendum: even if there’s a lot of uncertainty, we want one party to win even if by few votes.
So let’s look what happens for exactly y=0.5 (and a couple of other values) when n grows:
As we have seen earlier, for y ≠ 0.5, p(y,n) quickly tends to 1 or 0; for y = 0.5 it seems converging to 0.5 but with an at-first-unexpected sawtooth-like profile (visible in the leftmost parts of the other two curves as well): what is that? Just a tip: think to roulette-gambling…
…
Ok, time’s up: it depends on n being alternatively odd and even: when even, the referendum final outcome could be “yes”, “no”… but a break-even could also be possible, and of course votes combinations leading to it will lower the “yes” probability, for every y (like zero in roulette makes betting on a color a less than 50% affair).
Good, our model seems reasonable: so, remembering our purpose of exploring a more “real” (or at least a “less unreal”) Δp(i), let’s take a step further introducing vote buying. Our function becomes:
where, as earlier, i is the number of votes bought for “yes”. The new expression reflects that:
- the total number of votes whose probabilities need to be taken into account is not n anymore, but n-i in fact (each bought vote has probability 1 so no need to appear in calculus);
- if “yes” outcome has an “i votes initial treasure”, we also need to sum the probabilities of cases which lack -compared to previous expression- up to i “yes” votes (that’s why the change in summation lower bound);
- the inequality condition on i is the mathematical way to guarantee all quantities involving it are positive or zero, but also the formalization of the obvious fact that it’s enough to buy half of the votes plus one to be sure of “yes” winning.
Fixing n=100 and plotting between 0 ≤ i ≤ 60:
Of course higher y (probability the average voter will choose “yes”), sooner p(y,100,i) reaches 1 while i grows; for y > 0.6 buying votes is almost useless (remember discontinuity around y = 0.5 for high number of voters), and by i = 51 (= n/2 +1) all curves have reached highest probability.
So if a very uncertain referendum involves 100 voters and our statistical research can only establish that their penchant for “yes” falls between 40% and 50%, then graph above tells us we have to buy at least 9 votes (and no more than 23 needed) to have an higher than 80% probability of “yes” winning (just check for which i the curves for y=0.4 and y=0.5 reach the 0.8 height).
By the way, it’s obvious that Δp(i) = p(i)-p(i-1) cannot be constant, but let’s plot it to see its shape:
Definitely not constant!
We could play a lot this way: if you want on my GitHub there’s a repository (https://github.com/baro77/quadratic_influence) where I have uploaded some unleashed Octave code I have used to generate the above graphs and a quite big archive (almost 1GB overall) of precomputed values of p(y,n,i) for the 101 x 1000 x 502 lattice domain defined by:
Feel free to play with it, if you want. But here it’s time to extrapolate a few general properties of p(i) and Δp(i) (inspired by, but independent from, our referendum model).
A generic marginal probability & generalized quadratic payments
Let’s recap what we have discovered about our probabilities:
- p(i) is monotonically strictly increasing between 0 and 1;
- Δp(i) is consequently positive but in general neither constant nor monotonically increasing (that’s all we know about our generic marginal probability).
It seems now we haven’t a lot to try a formal derivation as we did earlier when marginal probability Δp(i) ≡ Δp,because (check “technicalities” after (5) ):
- Δp(i) isn’t constant in i so we should invert f(i) ≜ c(i)/Δp(i) …
- …but, wanting to deal with a general case, then we haven’t enough constraints on Δp(i) to be able to derive (please note that here -1 is the inversion, not a power):
We have to try to proceed in a wily way. Let’s begin trying to find an expression for imax.
When marginal probability was constant, degree of influence was simply given by the number of bought votes i, so making influence proportional to perceived value V led to:
Now each bought vote brings an influence increase Δp(i), so to impose influence-value proportionality we should write:
The above expression isn’t rigorous as-is, other constraints will apply apart from K₂ positiveness, we will deal with them in a few lines.
By the way, now we use K₂ because when earlier we introduced K we omitted Δp from influence evaluation; however adding just one more line to that formal derivation we could have written instead:
From which it follows (it will be useful later) that K = K₂ / Δp.
Returning to our summation, to expand it we note that:
so:
Having a probability on the left side of the equation limits the permitted values of right side: here it is one more constraint on K₂ (differently from K which was unbounded instead):
it’s a strict inequality (equality not allowed!) because we will want to invert p(i) and, as we have discovered with our referendum model, probability function saturates when it reaches 1 (remember, to be sure of “yes” winning buying n/2 + 1 votes was enough): so invertibility of p(i) is possible only in [0,1[.
So, recapping, we got:
However we need another constraint because i and imax are whole numbers and:
- p⁻¹( p(imax) ) ≡ imax for sure…
- … but p⁻¹( K₂V + p(0) ) isn’t necessarily a whole number
Unluckily we cannot introduce a further explicit constraint on K₂ because we don’t actually know p⁻¹(), so we cannot calculate which values for K₂ would make the right side of the equality a whole number. However, instead of searching which values of K₂ should be discarded, we can choose to accept all of them and to lead the outcomes of this “permissiveness” back to the allowed values. How? With the floor function:
Needing to insert (in an order-preserving way) each real number p⁻¹( K₂V + p(0) ) into one of a set of equivalence classes labeled by whole numbers, each real value has two main whole numbers it can be mapped to: the greatest less than itself (given by the floor function) and the least greater than itself (given by the ceiling function); why have we chosen the first one? Because we are seeking the maximum whole i, so the real number we get is a sort of upper-bound, a value which cannot be exceeded by the whole number we need.
If not yet convinced, let’s check if this imax expression falls back to (7) when Δp(i) ≡ Δp :
so:
which confirms that floor function is the right choice, allowing particular imax expression to be derived from the general one.
By the way, you have perhaps noted that the way we have inverted p(i) implies both p⁻¹(i) and p(i) being ℝ→ℝ functions; no problem even if p(i) was initially defined as ℕ→ℝ function, because we can always extend it to a ℝ→ℝ one (with a polyline if nothing better is suitable, we don’t need to calculate derivatives).
Now that we know how to calculate imax for a generic marginal probability, it’s time to focus on cost function c(i).
Because of fairness considerations it would be sound for c(i), once we consider a specific value i, to be proportional to Δp(i): a vote price should be linear in probability gain it allows, given all other conditions. This means the structure of cost function should be: c(i)= Δp(i) g(i).
Cost function enforces imax limit: it must be unfavorable to buy more than imax votes, so we want g(i) to keep c(i) increasing with i, until we get:
Note we are just saying that we want to satisfy -even if in its dual reformulation- condition (1). So:
Applying g⁻¹() to both sides we obtain:
(inversion and inequality sign are ok because sought g(i) will be an increasing function with positive domain and codomain). We now have two inequalities with i on the left side, comparing them:
with floor function appearing, as usual, to handle imax whole-ness.
Remembering imax formula, we get an explicit expression for g⁻¹(V) :
Inverting it:
strictly increasing, with positive domain and codomain. Great!
We have discovered that:
Let’s double-check that (1) is satisfied (“double” because it should, having started the derivation imposing it):
So, as expected:
Good, and now last step, evaluating c(i) when Δp(i) ≡ Δp :
Success!
And the name?
In the beginning, calculating how much we spend to buy imax votes when Δp(i) ≡ Δp , we got:
Which, considering (4), for the sake of thoroughness becomes:
Now it seems interesting to check if the quadratic nature of the payment is preserved by our brand new c(i) :
as previously seen, the difference inside square brackets can be expressed as summation of marginal probabilities Δp(i), so:
We need to untie that double summation. Let’s study i-j plane to understand what we are adding up:
The double summation regards the grey cells; more, values of cells are symmetric with respect to the diagonal, so when we deal with summation of values:
Summation of diagonal is given by: ∑ ∆p(i)²
To calculate the sum of whole plane we note that, for example, for the lowest row we have:
and likewise for all other rows as well. So when we add all rows to get the whole plane:
Putting together (9) and (10) we get:
or:
where we have defined the average values in [1,imax]:
Not surprisingly, when Δp(i) ≡ Δp we obtain A ≡ Δp , B ≡ Δp² and (12) falls back exactly to (8).
In general case, using (13) inequalities in (12), we obtain:
Applying Wikipedia formal definition of Big-O notation:
That is, f(x) = O(g(x)) if there exists a positive real number M and a real number x0 such that
|f(x)| ≤ M g(x) for all x ≥ xₒ .
we get:
So we could still talk of quadratic payments in the sense that:
But remembering that 1 is just an upper-bound (a very high upper-bound probably) for both A and B, above result is perhaps too coarse: let’s check with some graphs.
These are four different probability functions p(i) and their cost functions c(i) for 1 ≤ i ≤ 1000:
Their total cost functions for a given imax is:
The dashed line is a reference M⋅ imax² : as we have been suspecting, it’s definitely not a good estimator of total cost ∑c(i) behavior for a generic probability p(i).
However it jumps to the eye that total cost functions aren’t too different from their own probability functions. This suggests that perhaps Big-O equivalence classes should be driven by p(i) and not by i : let’s take (11) and rewrite it as:
Remembering that Δp(i) ≤ 1 ⟹ Δp(i)² ≤ Δp(i) :
From algebra:
But, again, p(0)² ≤ p(0) , so:
If [1–2p(0)] ≤ 0 the above inequality will be easily satisfied, for example, by M=1/2K₂ ⩝ imax
When instead [1–2p(0)] > 0 we will have:
with, for the inverted probability argument, the constraint:
So we can say:
which is a far better estimator than earlier one. So “legacy” quadratic payments (QP) actually seem a particular case of more general family which could perhaps be named quadratic success payments (QSP) — because, remember, p(i) is the probability of desired outcome given i involvement (e.g. bought votes).
Recapping
Our long journey can be summarized by following table:
Constraint a) is a way of saying that involvement of stakeholders has its own intrinsic granularity: e.g. you can buy 1 vote, 2 votes, n votes but you cannot buy 1.5 votes. Note that it doesn’t rule out decimals altogether: there could be contexts in which involvement envisages fractions of unit, but those cases can fall back to whole numbers via rescaling. However continuity of real numbers isn’t contemplated;
constraints b) and c) formalize obvious characteristics of a probability function linking desired outcome to involvement, and guarantee its invertibility;
constraint d) is what makes influence proportional to perceived value V (and being both positives, K₂ also has to);
constraint e) tells us that exercisable influence is a finite asset: from (6) and (7) we know that influence is strictly linked to product K₂V, so having the upper-bound of K₂ inversely proportional to V means maximum influence is limited as well (to 1-p(0) not surprisingly, given our definition of influence related to marginal probability).
And there’s also a consequence on market definition because it’s a two-way constraint between K₂ and V:
- V is a per-stakeholder parameter, meaning that each player will have a different perception of desired outcome value;
- given p(i), K₂ has an important role in defining cost function c(i), which hasn’t to be per-stakeholder-defined: otherwise incentives mechanics wouldn’t succeed in inducing fair ratios between players’ influences, given their perception of value (if cost function changes, two stakeholders with the same V could have different imax and, consequently, different acquired influences). So we need a single K₂ for the entire market;
all of that seems to mean we should choose K₂ as small as we can to raise the bar of allowed V, however:
- a hugely motivated player we haven’t foreseen (aka one with a very high perceived value V, higher than our predictions) will always be able to fall out of our game rules;
- prices would increase (K₂ is at denominator of c(i) ), meaning that stakeholders with small Vs would be compressed towards small imax values: being whole numbers, the risk of too much compression is to flatten players with different perceived values to the same imax.
Elaborating a bit more: when you choose K₂ , e) gives you an upper-bound for V, meaning that a stakeholder with that maximum V will be incentivized to acquire all available influence ( 1-p(0) ): so we should choose a K₂ corresponding to the sum of all Vs of all players (if predictable) plus some “guard value” to take into account unexpected stakeholders appearance. How small K₂ (or big the “guard value”) will be is a trade-off needing to balance:
- how much protection is needed against a player with a very big V coming earlier than others and hoarding influence;
- the need to keep prices low enough to have a good spread of imax values for actual players.
So K₂ also affects which difference between two values of V is big enough to guarantee two different values of imax , i.e. it chooses the granularity of V: because no rational player will pay more than the minimum needed for a certain level of influence.
In optimal case it will be:
Of course we have always been assuming that p(i) saturates to 1 for an i big enough to have “space” permitting fair involvement of all interested players: it doesn’t seem a limiting condition because if there isn’t enough “space to act” then there isn’t a market either.
Not only referendums
During last thoughts about constraints I have mainly used general terms: e.g. market and stakeholders instead of ballot and voters: that’s because formulas scope seems wider than the initial referendum context.
That’s why -for example- previous words about maximum allowed sum of Vs seem to suggest stakeholders could be in mutual competition buying as much influence as possible, so to be worried about voters with high Vs: it’s a general possibility emerging from the framework, but it isn’t always that case, and probably it isn’t when we are modeling voters hoping for the same event (“yes” winning): granularity of V seems much more important to exploit each voter commitment fairly.
So, reconsidering what we are dealing with from a more general point of view, we have:
- a stochastic process S whose execution could lead or not to D outcome;
- an i metric of involvement in favor of D;
- a generic p(i) probability of D outcome;
- a V value assigned to D outcome by a stakeholder;
- a pricing of i with a cost function c(i) incentivizing the stakeholder to influence the outcome in favor of D (by means of i buying) in a proportional-to-V way: greater involvement would be anti-economic.
The whole picture seems to suggest many applications… but that’s enough for now! Thanks for reading!
