Capacitated Network Bargaining Games: Stability and Structure
研究了带容量约束的网络讨价还价博弈，证明可通过容量削减和边删除操作稳定单位权重实例，且不降低总价值；对一般加权实例，给出了多项式时间算法计算最小容量削减量，并基于此得到边删除稳定化问题的近似结果。
Capacitated network bargaining games are popular combinatorial games that involve the structure of matchings in graphs. We show that it is always possible to stabilize unit weight instances of this problem (that is, ensure that they admit a stable outcome) via capacity reduction and edge removal operations without decreasing the total value that the players can get. Furthermore, for general weighted instances, we show that computing a minimum amount of vertex capacity to reduce to make an instance stable is a polynomial time solvable problem. We then exploit this to give approximation results for the NP-hard problem of stabilizing a graph via edge removal operations. Our work extends and generalizes previous results in the literature that deal with a unit capacity version of the problem, using several new arguments. In particular, whereas previous results mainly used combinatorial techniques, we here rely on polyhedral arguments and, more specifically, on the notion of circuits of a polytope. Funding: This work was supported by Toegepaste en Technische Wetenschappen, Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant VI.Vidi.193.087].