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.
This is a most excellent proof (it makes everything obvious) and I am convinced by this that agents should not insist that their outcomes above all lie on a Pareto frontier, because some of the points on a Pareto frontier represent unfair splits of gains from trade a la Ultimatum. An auction system between multiple agents might resolve this, but meanwhile one must be willing to refuse certain proposed 'Pareto improvements' in order to possess any negotiating power about which Pareto improvement to make, and it may also be that by the nature of utility functions it is not possible to distinguish aliens that have cleverly rejiggered their utility functions from aliens which were born with them.
If both players lie in this way, the standard outcome is the default point
Does that mean choosing whether to lie or not is like a prisoner's dilemma?
Yes, and this parallels real negotiation. If the two sides sufficiently trust each other, you show each other your term sheets (basically utility functions), find the Pareto optimum set of solutions and then pick a point on that line.
For sufficiently reliably repeated interactions that don't vary too much in size, with agents with whom trust is in context total, from what I can tell optimum real world behavior is isomorphic to MWBS with a meta-negotiation over the ratio. As these conditions get closer to yours, your behavior should approach MWBS.
Indeed, the Myerson-Satterthwaite theorem from mechanism design implies that no mechanism for bilateral trading can be perfectly efficient.
My understanding is that there has been research into mechanisms that can reach some kind of constrained optimum, but the problem is complex enough that even these mechanisms are not considered to be feasible.
no mechanism for bilateral trading can be perfectly efficient.
Yep, but this illustrates how bad it can get!
Then either player can lie, if they know everyone's preferences
Where did that knowledge of another's preferences come from? If all the players know each others' preferences, what they claim about their own is irrelevant. If they know nothing but each others' claims about their preferences, and can claim anything they like, then they cannot communicate their preferences.
Real negotiations happen somewhere between these degenerate cases.
Here's another case (the worrying one): one player has much greater knowledge of the other's preferences than vice versa.
But your mutual knowledge does raise an interesting point...
I wonder if there's a way of Player X saying "I know that player Y's true valuation is BLAH", while convincing people that player X is actually telling the truth about what he thinks he knows. Maybe being completely transparent wouldn't be such a disadvantage as it seems...
If all they can do is make claims about themselves that no-one is in a position to check, then they cannot communicate anything. Non-verbal evidence of some sort has to be shown. When everyone can lie without loss, words are not evidence of anything. Language is an iterated PD.
Even with zero knowledge of the other guy's function, you'd always start with Lie #1: Always represent any outcome that leaves you worse off as having infinite negative utility (or at least more bad than your utopia point is good).
This cuts off any outcome that decreases your utility, and thus is very, very good for you - even if you need to self-modify and make it real. Note that this is how actual negotiations work.
Another easy hack is to limit your goals, and pretend that impossibly good outcomes are no better for you than the best possible outcome, in order to increase the value of utility to you via decreasing your Utopia point.
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:
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.