Even with default points, systems remain exploitable

Stuart_Armstrong19 Jul 2013 16:24 UTC
14 points
9 comments3 min readLW linkArchive

Still exploitable, even with defaults

A while ago, I posted a brief picture-proof of the fact that whatever bargaining system you use to reach deals, they are all exploitable, in some situations, by liars (as long as the outcome is Pareto and a few other assumptions).

That included any system with an internally assigned default point. The picture proofs work no matter how you calculate the bargaining outcome: if you use the utility value data to assign a default point, before picking the Nash bargaining equilibrium, then the whole process is susceptible to exploitation by lying.

Is the same thing true for externally assigned default points (i.e. default points that come from outside the data, and are not a mere function of everyone’s preferences and the available outcomes)? A moment’s thought shows that this is the case. The picture proofs never used translations, or scaling, or anything that would shift an external default point. So having an externally assigned default point does not solve the problem of lying.

But “any Pareto bargaining system is exploitable by lying” is an existence proof: in at least one circumstance, one player may be able to derive a non-zero benefit by lying about their utility function. This doesn’t give an impression of the scale of the problem.

The scale of the problem

The problem is very severe, for the Nash Bargaining Solution (NBS), the Kalai-Smorodinsky Bargaining Solution (KSBS) and my Mutual Worth Bargaining Solution (MWBS). Essentially, it’s as bad as it can get.

For KSBS and NBS, let’s call an outcome admissible if it’s Pareto-better than the default. For the MWBS, call an outcome admissible if the combined utility values it more than the default point (as we’ve seen, this needn’t be an improvement for both players). In all three approaches, the bargaining solution must be admissible.

Then the dismal result is:

  • Let O be any admissible pure outcome. Then either player can lie, if they know everyone’s preferences, to force the bargaining solution to pick O.

The proof is nearly derisively brief: the player simply needs to reduce their declared utility on every other admissible pure outcome, until these are no longer admissible. Then O would be the only outcome available to the bargaining solution.

There are some extra subtleties (this section may be skipped by those not interested; the essence of the argument is above). For both KSBS and MWBS, you have to preserve the values of the utopia points. Player X can do this by, for instance, promoting some option that player Y absolutely hates, up to the value of the original utopia point. This would preserve all the normalisations, and the new utopia point would not be admissible (as Y hates it so much), so O would indeed be the only outcome available. For the KSBS, only equitable outcomes are chosen, so the player has to change their valuation of O to make it seem equitable. Finally, the NBS sometimes chooses mixed outcome rather than pure outcomes, so the player may need to reduce their declared utility for every other pure outcome by quite a bit, to ensure O is picked rather than some mixed outcome involving O.

When fairness fails

This is bad news for all three systems. But, in a way, it’s worst of all for KSBS. That’s because KSBS gave up the ideal of maximising something, in order to be “fair”. It’s expected that there’s a cost when you fail to maximise (you can’t get as much benefits as you possibly could), but there should be benefits as well, such as not placing yourself in as much risk of losing or being exploited. But KSBS failed you as badly as the others: the liar gets to choose their outcome.

This suggests that “have a default point and negotiate to ensure you get a fair or reasonable portion of the gains from trade”, is not an effective way of combating lying. Against liars who know your preferences, this is equivalent with “gain epsilon more than the default point, while thinking you got a good deal.”

Further research: equilibrium lying

If both players lie in this way, the standard outcome is the default point (unless one outcome Pareto-dominates all others). This is obviously much worse than the alternatives, so we have to try and avoid this. Three possible research avenues spring to mind: the first is see how stable these bargaining solutions are to small lies. If you can give a pretty good estimate of your opponent’s preference, is that enough to ensure they can only exploit you (in most cases) by only a little bit? Do small lies produce small changes in (expected) outcomes?

Effective lying relies on knowing your opponent’s preferences, though. If you don’t know your opponent’s preferences, is it still rational to lie? Are any of the bargaining solutions exploitable against a wide range of unknown opponents?

A third approach would be to go through several cycles of lying and counter-lying, and see if this eventually settles down to any sort of equilibrium.

But as I said in the previous post, I won’t be working on these any time soon! Baby comes first.

Stuart_Armstrong19 Jul 2013 16:24 UTC
14 points
9 comments3 min readLW linkArchive