In a previous post, I showed that the Nash Bargaining Solution (NBS), the Kalai-Smorodinsky Bargaining Solution (KSBS) and own my Mutual Worth Bargaining Solution (MWBS) were all maximally vulnerable to lying. Here I can present a more general result: all bargaining solutions are maximally vulnerable to lying.

Assume that players X and Y have settled on some bargaining solution (which only cares about the defection point and the utilities of X and Y). Assume further that player Y knows player X's utility function. Let player X look at the possible outcomes, and let her label any outcome O "admissible" if there is some possible bargaining partner Y_O with utility function u_O such that O would be the outcome of the bargain between X and Y_O.

For instance, in the case of NBS and KSBS, the admissible outcomes would be the outcomes Pareto-better than the disagreement point. The MWBS has a slightly larger set of admissible outcomes, as it allows players to lose utility (up to the maximum they could possibly gain).

Then the general result is:

If player Y is able to lie about his utility function while knowing player X's true utility (and player X is honest), he can freely select his preferred outcome among the outcomes that are admissible.

The proof of this is also derisively brief: player Y need simply claim to have utility u_O, in order to force outcome O.

Thus, if you've agreed on a bargaining solution, all that you've done is determined the set of outcomes among which your lying opponent will freely choose.

There may be a subtlety: your system could make use of an objective (or partially objective) disagreement point, which your opponent is powerless to change. This doesn't change the result much:

If player Y is able to lie about his utility function while knowing player X's true utility (and player X is honest), he can freely select his preferred outcome among the outcomes that are admissible given the disagreement point.

Exploitation and gains from trade

Note that the above result did not make any assumptions about the outcome being Pareto - giving up Pareto doesn't make you non-exploitable (or "strategyproof" as it is often called).

But note also that the result does not mean that the system is exploitable! In the random dictator setup, you randomly assign power to one player, who then makes all the decisions. In terms of expected utility, this is a pU_X+(1-p)U_Y, where U_X is the best outcome ("Utopia") for X and U_Y the best outcome for Y, and p the probability that X is the random dictator. The theorem still holds for this setup: player X knows that player Y will be able to select freely among the admissible outcomes, which is the set S={pUX+(1-p)O | O an outcome}. However, player X knows that player Y will select pU_X+(1-p)U_Y as this maximises his expected utility. So a bargaining solution which has a particular selection of admissible outcomes can be strategyproof.

However, it seems that the only strategyproof bargaining solutions are variants of random dictators! These solutions do not allow much gain from trade. Conversely, the more you open your bargaining solution up to gains from trade, the more exploitable you become from lying. This can be seen in the examples above: my MWBS tried to allow greater gains (in expectation) by not restricting to strict Pareto improvements from the disagreement point. As a result, it makes itself more vulnerable to liars.

What to do

What can be done about this? There seem to be several possibilities:

1. Restrict to bargaining solutions difficult to exploit. This is the counsel of despair: give up most of the gains from trade, to protect yourself from lying. But there may be a system where the tradeoff between exploitability and potential gains is in some sense optimal.
2. Figure out your opponent's true utility function. The other obvious solution: prevent lying by figuring out what your opponent really values, by inspecting their code, their history, their reactions, etc... This could be combined with refusing to trade with those who don't make their true utility easy to discover (or only using non-exploitable trades with those).
3. Hide your own true utility. The above approach only works because the liar knows their opponent, and their opponent doesn't know them. If both utilities are hidden, it's not clear how exploitable the system really is.
4. Play only multi-player. If there are many different trades with many different people, it becomes harder to construct a false utility that exploits them all. This is in a sense a variant of "hiding your own true utility": in that situation, the player has to lie given their probability distribution of your possible possible utilities; in this this situation, they have to lie, given the known distribution of multiple true utilities.

So there does not seem to be a principled way of getting rid of liars. But the multi-player (or hidden utility function) may point to a single "best" bargaining solution: the one that minimises the returns to lying and maximises the gains to trade, given ignorance of the other's utility function.

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.