Non-cooperative Bargaining with Arbitrary One-Sided Uncertainty

摘要

Non-cooperative bargaining is modeled as an extensive-form game with uncertain information and infinite actions. Its resolution is a long-standing open problem and no algorithm addressing uncertainty over multiple parameters is known. We provide an algorithm to solve bargaining with any kind of one-sided uncertainty. Our algorithm reduces a bargaining problem to a finite game, solves this last game, and then maps its strategies with the original continuous game. Computational complexity is polynomial with two types, while with more types the problem is hard and only small settings can be solved in exact way.