Musing about preference allocation

I’ve been wrestling with a question this week that I think is ready at least to have some explicit confusion written out. And I settle on some conclusions at the bottom. The basic situation is this: you have some set C of funding targets, a set S of assessors, and (for now) a single meta-assessor m. The general idea is that the members of S looks at the members of C and describe somehow how they would distribute funding among the members of C, and then m allocates funding among the members of S to determine how much of each of their budgets gets exhausted!

There are lots and lots of free parameters left in the above description, so let me fix some for concreteness. I’m going to have people describe their funding preferences using what I’ll call a tranche priority table. A tranche priority table is nothing but a list of tranches, and a tranche is a dollar amount plus a probability distribution over C.

So if assessor s provides a tranche table whose first tranche is (\$75,.5,.5) and whose second tranche is (\$50,.4,.6), then s is expressing a preference to distribute \$75 equally among the (apparently) two available charities, and then if possible to distribute the remaining \$50 among the two charities in a 2:3 ratio. Probably the idea is that the second charity c_2 has a bit more headroom to absorb bigger funding levels.

We thus assume that we have a tranche table for each s\in S, involving distributions over C, and a tranche table for m, involving distributions over S. The problem is to appropriately “convolve” these tranche tables together to get a tranche table for m's budget, now involving the final distributions over C.

So, how does this work? First, an approach that doesn’t work. Suppose there are two assessors s_1,s_2\in S and two charities c_1,c_2\in C and the assessors have the following tranche tables:

s_1 c_1 c_2 s_2 c_1 c_2
$50 1 0 $50 1 0
$50 0 1 $50 0 1

OK, so both assessors have exactly the same preferences: charity c_1 should get the first \$50, and if possible c_2 should get the next \$50. Suppose m is distributing only \$100 in total. Then what should happen? For instance, suppose m's tranche table is just one tranche, (\$100,p,1-p).

I see two ways this can play out:

  • We give \$100p to s_1 to distribute according to s_1's table, and similarly, \$100(1-p) to s_2. Assuming p>1-p, this means we’ll give out all of s_1's first tranche plus some of their second tranche, while we’ll give out part of s_2's second tranche proportional to how close p is to 1-p. But that means charity c_1 will always end up with more than \$50, and the closer m is to indifferent between s_1 and s_2, the closer c_1 will be to getting all the money!

This is an unsatisfactory outcome in several ways. Pragmatically, this algorithm would mean that consensus gets concentrated: the charities with the most consensus among the assessors that they’re a high priority would routinely get almost all the money, and weirder charities further down will always lose out. Mathematically, it seems really bad that the outcome of the aggregation can depend on how many identical agents are serving as assessors!

Therefore we need to distribute differently.

  • Now let’s interpreted the sizes of the tranches as what each agent would like to see the overall outcome come out to. With this semantics it’s clear that our example must come out with \$50 to c_1 and \$50 to c_2, and it’s similarly easy to see the result of any other smaller amount of total funding from m.

This is better-behaved in that we can fuse identical agents without affecting the outcome, and it allows for lower reaches of tranche lists to be reached. So far, so good. But what’s the algorithm here in general, assuming not all the assessors have identical preferences?

An important special case is when the assessors’ preference are piecewise concentrated: we’ll assume that each probability distribution in each assessor’s tranche table is \delta_c, fully concentrated at some charity c. We’ll allow m to have non-concentrated probability distributions in their tranches still, though.

For instance, let’s consider the following setup.

s_1 c_1 c_2 s_2 c_1 c_2 m s_1 s_2
$25 1 0 $100 1 0 $50 .6 .4
$75 0 1 $50 .8 .2

So, how do we distribute? m's first \$50 tranche must send \$30 to s_1 and \$20 to s_2; the second tranche will give \$40 to s_1 and \$10 to s_2. We can only have s_2 fund c_1, so \$30 will go that way, leading to all \$70 of s_1's budget going to c_2. Similarly, if s_2 had been all in on c_2, then s_1 would give \$25 to c_1 if posible and the rest to c_2. So this one’s no problem. How about this?

s_1 c_1 c_2 s_2 c_1 c_2 m s_1 s_2
$25 1 0 $30 1 0 $50 .6 .4
$75 0 1 $70 0 1 $50 .8 .2

Here we see things begin to get tricky. Presumably the final outcome must be somewhere in between s_1's preferred \$25-\$75 split and s_2's preferred \$30-\$70 split. One plausible resolution here is to say that m gave s_1 \$70 in the end and s_2 just \$30; thus we should take s_1's preferences over s_2's at a 7:3 ratio. In other words, c_1 ends up with .7\cdot 25+.3\cdot 30=\$26.50.

This seems pretty fair, but it’s a bit disappointing in that it collapses away the actual tranches: it’s equivalent to just having s_1,s_2,m give a single overall distribution over their children in the funding tree. But s_2 prioritized \$30 to c_1 higher than s_1 prioritized the \$75 to c_2, so plausibly we should conclude the process a bit closer to s_2 than the result in the previous paragraph!

There’s another problem with collapsing tranches, too: this algorithm has the bad property that we can’t split the distribution into stages. If we imagine m first gave out \$25, then both s_1 and s_2's truncated tranche tables would be concentrated fully on c_1, so that the result would surely be that c_1 got all \$25. If then m came back again with \$75, the remaining tranche tables would look like this:

s_1 c_1 c_2 s_2 c_1 c_2 m s_1 s_2
$0 1 0 $5 1 0 $25 .6 .4
$75 0 1 $70 0 1 $50 .8 .2

Now s_1 gets \$55 more while s_2 gets just \$20 more, so perhaps we go at an 11:4 ratio for the result of the money, meaning c_2 gets all the rest except for 4/15\cdot \$5=\$4/3 to c_1 from s_2. Thus c_1 ended up with \$26 \tfrac 13, not \$26.50 as before. Weird. And actually, wait a sec: if we decompose further, splitting the final \$75 into \$25 then \$50, we see that s_2 will get to target up to 2/5 of that \$25, which lets her give the whole desired \$5 out to c_1, and end up in the end getting exactly her desired total distribution–even though m trusts her less overall! Super weird.

…Or maybe it’s not that bad? After all, if s_1 really wanted to push for close to a \$25:\$75 split, he has a way to specify that: give the single tranche (\$100,.25,.75)! Let’s see what happens in that situation.

s_1 c_1 c_2 s_2 c_1 c_2 m s_1 s_2
$100 .25 .75 $30 1 0 $50 .6 .4
$70 0 1 $50 .8 .2

The first m-tranche goes out without either assessor running out of their tranche, so we just weight the two distributions, 3:2 in s_1's favor. Thus c_2 gets 3/5 of what s_1 would have given them, which is 3/5\cdot \$37.5=\$22.50, while c_1 gets \$27.50. Now the table looks like so:

s_1 c_1 c_2 s_2 c_1 c_2 m s_1 s_2
$100 .25 .75 $2.50 1 0 0 .6 .4
$70 0 1 $50 .8 .2

Next s_2 ought to get to allocate \$2.50 to c_1, which leaves s_1 with \$10. But will s_1 allocate those \$10 at a 1:3 ratio? Probably not! He wants c_1 to end with \$25, but c_1 already has \$30. So probably s_1 now effectively has a \delta_{c_2} distribution. Anyway, again, we end up with s_2 dominating. Still weird! (Maybe!)

What all these examples have gone to show is that if money is allocated in stages according to the explicit distributions in a tranche list, it’s possible for a single assessor s to end up completely dominating the result, even if s is not particularly popular with the meta-assessor m.

OK, well, maybe we should stop calling the algorithm bad names and just try to understand it. This allocation algorithm is always going to work very hard to guarantee that every assessor’s top preference tranches get filled out–unless m really, really doesn’t like that assessor. Dually, an assessor who has a little tranche way down at the bottom might as well not bother: if we proceed compositionally/stepwise, you’re never really going to get all the way down there. Again, it seems like the only obvious way to be sure that every preference gets a bit of attention is to do the whole allocation globally, combining all the tranches, and that’s very destructive of the prioritization information. So as much as it may feel like if s_1 has \$5 at the bottom to some c_3 then c_3 should end up with at least a bit of money, that’s just not consistent with our other intuitions about the process.


Alright, so can we specify a general algorithm consistent with the stepwise distribution process we saw a couple examples of above? We’ll loop as long as m has money left to distribute, assuming the members of S don’t run out of preferences first. Suppose m's current tranche is (A_m,p_m), where again A is the size of the tranche and p_m is some probability distribution over the assessors S. Similarly, for s\in S let s's current tranche be (A_s,p_s). Then the current distribution \hat p is the convex combination of the p_s determined by the p_m. That is, for a charity c\in C, we have \hat p(c)=\sum_{s:S}p_s(c)p_m(s).

The goal is to let m distribute money according to \hat p “until something happens.” What can happen that would make us want to change the current distribution? Most often we’ll have to stop and re-calibrate because one of the initially-nonzero quantities A_sp_s(c) “reaches zero.” This is the quantity that assessor s wants to see charity c receive during the current tranche; if m keeps giving according to \hat p past the point where c has received this quantity, then s is going to be unhappy: s would like to switch p_s to the distribution p_s'(c')=p_s(c')/(1-p_s(c)) for c'\ne c and p'_s(c)=0. Note that if another assessor s' still has positive p_{s'}(c) in the current tranche, then continuing will indeed increase c's winnings beyond what s wants; but at least s won’t be responsible for that.

OK, so, home stretch. If we try to give our \$K according to the current distribution \hat p then a charity c will receive K\hat p(c)=K\sum_sp_s(c)p_m(s). This reached the maximum allowance A_sp_s(c) when

K=\dfrac{A_sp_s(c)}{\sum_sp_s(c)p_m(s)}.

Thus to compute the optimal distribution for the round we have to compute \sum_sp_s(c)p_m(s) for each charity c\in C, and divide this by A_sp_s(c) for each s\in S. This is a bit more complex of a computation than one might like: ignoring additions and finding the minimum of a list, you have O(|C||S|) multiplications to compute p_s(c)p_m(s) and A_sp_s(c), and again O(|C||S|) divisions to compute all the candidate K's. (Although I find it almost impossible to figure out to what extent floating point division is actually worse than multiplication on modern CPUs, especially Apple Silicon.)