01 April 2010

Disparate impact

Towards a fair mechanism for dealing with disparate impact

Introduction

On the futarchy discussion list we talk about futarchy, which is a proposal to use decision markets1 to decide policy, based on a metric called GDP+.

But what if the impact of a proposal isn't spread evenly? Surely2 we don't want to enact proposals that, while they benefit the populace3 collectively, have extremely bad consequences to a few.

We could have meta-rules that forbid certain types of proposals. That can curb the worst abuses, but it doesn't solve the problem.

So we want a mechanism that can:

  • measure disparate impact honestly.
  • tell us what side-payments will flatten the impact

I don't have a solution that I trust, but I do have some interesting approaches towards such a mechanism.

Some general issues

We want a citizen's best strategy to be honest revelation

This almost goes without saying in mechanism design. We want to can show that each citizen's best strategy is to honestly report their best estimate of the proposal's effect on them personally.

There's a free-rider problem

There's a free-rider problem. No citizen individually controls the outcome, so it always behooves him to exaggerate the damage a proposal does to him.

Hard to distinguish 3 different situations of few holdouts

It is hard to distinguish these 3 situations that we would want to treat quite differently:

Sincere objection
A minority of citizens rationally expects to be strongly negatively affected and bids accordingly.
Selection for naysayers
Due to selection effects, those citizens who bid as if they are most strongly negatively affected are those who have most overestimated the bad effects. They may have overestimated by a large amount.
Miscalculating speculators
A few citizens over-report their damages in the hope of a large profit. This is the game chicken. In the N-person game, this situation is dominated by those who play chicken most aggressively.

The first situation is what we want to take into account. For the other two, there are two outcomes, both bad:

  • The naysayers or speculators get paid off undeservedly.
  • Good proposals sink because of their influence.

General approach: Veto-like mechanism

In the following I'll describe a few potential mechanisms. In each case, the mechanism is intended to augment an overall approval mechanism, such as a decision market.

So the side-payment mechanism will have a veto-like effect:

  • If it fails to tell us what the side-payments should be, the proposal is not enacted.
  • But if it succeeds, the proposal still needs to pass in the over approval mechanism (perhaps simultaneously).

This gives us some leverage by which to keep speculators and naysayers honest. If they ask for too much, they run the risk of defeating their own windfall.

First idea: Network auctions

My first idea on the topic was to use a network auction. (As in Vickreyauctions in network routing) It's a good way to figure out appropriate side payments according to relative valuations.

If this problem had the structure of a network auction, it could be solved by a VCG auction. Run the auction, allowing both positive and negative valuations, and if there is a residual positive value,

The problem is, everybody needs to be in the resulting path. So the network is just a line that includes everybody. It lacks competition between different paths.

Second idea: Make competing paths in a network

So maybe we need to create competing paths. My next idea was to map the citizens to nodes in a random network, or randomly in a patterned network. Then find a path thru the network using network auction (as above)

But:

  • We are neccessarily using the networks that skip over those most adversely affected.
  • It capriciously skips people. The result is more a function of who is skipped than of anything else.
  • It's hard to analyze:
    • It's not clear where the path may stop and start
  • Negative costs (benefits) don't work well:
    • May result in a long path that unfairly weights the positively affected
    • May result in loops, which makes this mechanism impossible.
  • It's underspecified.

Third idea: Use percolation networks instead

So my next idea is to drop the network auction mechanism and use percolation networks instead. Large percolation networks have a nice feature that either they almost certainly allow flow or they almost certainly don't. (This feature proved to be exactly what we don't want, but I'm leaving this in because it illuminates some important thinking about the problem)

We'll specify the network structure as triangular4 and map citizens to nodes almost randomly. That is:

  • Each row contains a node for each citizen, in random order.
  • There are as many columns as there are citizens.

Instead of network auction to determine payments, we:

  • Let each citizen C specify a monetary amount payment(C), generally negative, that is the most they would pay to see the proposal pass (This part is the same as network auctions)
  • Let each node have a probability of admitting flow that is a function of the respective citizen's payment(C).
    • What specific function? As a first draft, say that the log-odds of the probability is equal to payment(C). That is, the probability is the logistic function of payment(C)
  • If a path thru the percolation network is found, the proposal passes and the given side-payments are made.

As stated, this gives entirely the wrong answer. It will say yes essentially whenever more than half5 of citizens feel a positive value. We wanted to correct the dynamic in the opposite way.

Sharp-eyed readers will notice that there is a free parameter in there: The baseline zero payment. The same percolation network would give different results if every payment(C) was transformed to payment(C) - X.

But it won't do to just set X such that it makes the total of side-payments zero. Consider the situation of an insincere opposer (IO): The lower a payment(IO) he bid, the better the proposal's chances, because the total payment asked is lower so everyone else's payment(C) - X is higher, giving their nodes a higher probability of allowing flow. So he gets more and does not risk his windfall by lowering the probability of enactment. So payment(IO) should be negative infinity. That's not good.

Fourth idea: Repeatedly subdivide the populace

So instead, let's use the available information to repeatedly split the populace binarily. These subpopulations will settle by side-payments.

So we'll have a series of stages. At each stage:

  • A subpopulation Pop is considered. Initially it's the entire populace.
  • We use the same set of payment(C) at every stage. Ie, citizens can't change them to react to stages.
  • If more than half of payment(C) - average(payment(Pop)) are positive, the proposal passes for Pop and no sidepayments need be made within Pop.
  • Otherwise, divide Pop into 2 subpopulations, those whose payment(C) is above the median (PopA), and those below (PopB). Recurse on those subpopulations.
  • If both PopA and PopB pass the proposal,
    • the proposal passes for Pop.
    • if the proposal ultimately passes, PopA is to collectively make a sidepayment to PopB, equal to the difference between their median payments times the population size (which is equal, by the way we constructed this)

ISTM this would tend to subdivide until it reached a node of the binary tree at which a significant percentage of Pop demanded unreasonable payments, and would pass at that point in the tree without further subdivision.

But this has the unfortunate property that one overly negative citizen can cause the proposal to immediately pass for the entire population by overstating his payment(C). A miscalculating naysayer or an insincere agent might do that. Yet it gives some leverage against speculators. If they are too aggressive, they'll lose their hoped-for windfall.

Repeatedly subdivide the populace, redux

How can we fix this but keep the leverage? In step 3, instead of choosing X to make the total sidepayments zero, let's choose it to make the quartile payments total zero. Also, step 2 risks entirely ignoring the tails of the distribution. So instead, say:

  • If Pop contains only one individual, the proposal passes for him, since he can make no side-payments.
  • Otherwise divide Pop into 2 subpopulations, those whose payment(C) is above the median (PopA), and those below (PopB). Recurse on those subpopulations.
  • If both PopA and PopB pass the proposal,
    • the proposal passes for Pop
    • superior nodes compute the average as if Pop were replaced by N copies of median(Pop)
    • If the proposal ultimately passes, PopA is to collectively make a sidepayment to PopB, equal to the difference between their median payments times the population size (the sizes of PopA and PopB are equal or differ by just 1, by the way we constructed this)
  • Otherwise, with a probability
    P(median(payment(C)) - average(payment(Pop)))
    

    the proposal still passes and no sidepayments will need be made between PopA and PopB.

    • As noted above, the average is a pseudo-average that replaces some subpopulations by their median.

This avoids some of the worst pitfalls. It can't easily be held hostage, because any extreme negative payment(C) will effectively eliminate its own influence. But ISTM it still tends insincerely negative. Everyone wants to be in the negative part of the tree, just not too isolated. It doesn't really leverage the probability of vetoing to encourage reporting positive payments.

Closing remarks

The final proposal solves some problems, but I don't think that it really does the job.

As far as I can see, this topic hasn't been explored before or even proposed as a topic in mechanism design. It could use further research.

Appendix A: What bad things could disparate impact cause?

If proposals with disparate impact can be adopted, these are some bad things that could happen:

Spiral towards oligarchy

In this problem, the proposal changes or indirectly affects the future franchise, and does so disparately across citizens.

Examples of changing the franchise:

  • Shrink the franchise to exclude certain people
  • Enlarge the franchise to include more people
  • Change how the GDP+ measurement weights welfare across citizens.

So there are people who expect increased control over the GDP+ metric and people who expect decreased. That implies that the change pretty much cancels out in the GDP+ metric. So such proposals might get enacted.

Once the franchise begins changing, it will probably quickly spiral inwards towards oligarchy.

Footnotes:

1 Briefly, decision markets are somewhat like the stock market, but shares do not correspond to any corporation, they correspond to issues and will be redeemed at some future time according to a well-defined measurement carried out at that time.

2 "Surely" is a warning sign of a flaw in one's argument, just like "obviously" and of course "of course". So I will flesh out the argument in Appendix A

3 When writing about futarchy, I use many terms that imply that it is to be applied to national governance, such as "populace", "citizens", "enact", "franchise", et al. That doesn't imply that it's the only possible application of futarchy. It's just convenient.

4 ie, a 36 regular lattice.

5 Because that's the site percolation threshhold of a triangular lattice.

No comments:

Post a Comment