SUBMODULARITY HELPS IN NASH AND NONSYMMETRIC BARGAINING GAMES

Motivated by the recent work of [V. V. Vazirani, J. ACM, 59 (2012), 7], we take a fresh look at understanding the quality and robustness of solutions to Nash and nonsymmetric bargaining games by subjecting them to several stress tests. Our tests are quite basic; e. g., we ask whether the solutions are computable in polynomial time, and whether they have certain properties such as efficiency, fairness, and desirable response when agents change their disagreement points or play with a subset of the agents. Our main conclusion is that imposing submodularity, a natural economies of scale condition, on Nash and nonsymmetric bargaining games endows them with several desirable properties.