Game-theoretic model:

Here, we are trying to provide the model for the coercing interaction. We make few simplifications: first, the vote utility of the seller is known to the buyer. Second, buyer has some prior assumption on the distribution of keychain height, we assume it to be uniformly random (for example, because this is our standard setup algorithm).

Utilities of the vote are denoted $u_b$ and $u_s$.

Assume the following game with two parties:

1. Seller runs the setup phase protocol, outputting uniformly random number $0 \leq k < N$.

2. Buyer sets the price list: function $p: \{0..(N-1)\} \rightarrow \mathbb{R}_{\geq 0}$

3. Seller outputs the claimed height $t \leq k$.

4. If it outputs $t = k$, it gets $p(k)$, and buyer gets $u_{b} - p(k)$, if it outputs $t<k$, it gets $p(t) + u_s$, and buyer gets $-p(t)$.

First, it is easy to see whether seller defects on 3rd step or not. Clearly, if $p(k) - \underset{t<k}{\max} [p(t) < u_s]$, it is profitable to defect by outputting $t<k$ with maximal price, and otherwise, it is not profitable to defect.

Because we assume that the buyer has knowledge of $u_s$, it can predict the optimal behavior of seller on the third step, lets optimize the price list.

Let's call the value $k$ "bad" if $p(k) - \underset{t<k}{\max}[p(t) < u_s]$, and good otherwise. There is $g \leq N$ good values. The prices in good values monotonously increase, with step at least $u_s$. Bad values are never picked correctly, so their price can be safely set to $0$ wlog.

Assuming we optimize for $g$ good values, we can ensure that they grow exactly by $u_s$ increments (which minimizes expected bribe over them), and ensure that expected bribe over bad values is $0$ (by setting their price to $0$ and moving them to the left of all good values): so, the optimal price list looks like $p(N-\alpha) = \max((g-\alpha + 1)u_s, 0)$.

This gives the average bribe spending $\frac{g(g+1)}{2N} u_s$ with $\frac{g}{N}$ votes being purchased. This gives the cost of one vote $\frac{g+1}{2} u_s$.

Denote the advantage $A = u_b / u_s$ (if the buyer is going to buy votes it must have greater utility for them; practically speaking this advantage can be quite big if buyer is a resourceful party and seller is a small voter).

The buyer is willing to purchase votes at cost at most $u_b$. Solving $\frac{g+1}{2} u_s = u_b$ we get $g = 2A - 1$.

This means that at most $\frac{2A - 1}{N}$ votes will be purchased in this model.

Should we analyse it without prior distribution?

It is unclear for us what are the correct assumptions without buyer knowing the prior distribution of $k$ - probably that of a repeated game. However, in practice the process of generating the key will eventually be bound to the modified unconditional private key possession proof (see here Vitalik's description of such meatspace protocol for normal private keys), which fixes the distribution.

Can we do better with different distribution?

It is not exactly clear, but likely yes: while using non-uniform distribution on $\{0..N-1\}$ means that the buyer can get an advantage by choosing a subset of size $g$ with probability $> g/N$, this advantage likely will be offset by defections (for example, for slowly decreasing probability of obtaining $k$).

We did not work through details; nor did we consider more complex negotiation strategies.