Title: Monotonicity in bargaining networks
Speaker: Yuval Rabani, Hebrew Univ.
Abstract:
We study bargaining networks, discussed in a recent paper of Kleinberg and
Tardos (STOC 2008), from the perspective of cooperative game theory. In
particular we examine two solution concepts, the nucleolus and the core
center. Both solution concepts define unique solutions, so they provide
testable predictions. In general coalitional games, both solutions are weakly
monotone, but they are not strongly monotone. We define a new monotonicity
property that is a natural axiom of any bargaining game solution, and we prove
that both the nucleolus and the core center satisfy this monotonicity property.
Our proofs are based on a primal-dual argument (for the nucleolus) and on the
FKG inequality (for the core center). We further observe some qualitative differences
between the two solution concepts. In particular, there are cases where a strict
version of our monotonicity property is a natural axiom, but only the core center
satisfies it. On the other hand, the nucleolus is easy to compute, whereas computing
the core center is #P-hard (yet it can be approximated in polynomial time).
This is joint work with Yossi Azar, Nikhil Devanur, and Kamal Jain.