کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5128242 | 1489490 | 2017 | 22 صفحه PDF | دانلود رایگان |
A correspondence P associates to every subset AâN a partition P(A) of A and to every game (N,v), the P-restricted game (N,v¯) defined by v¯(A)=âFâP(A)v(F) for all AâN. We give necessary and sufficient conditions on P to have inheritance of convexity from (N,v) to (N,v¯). The main condition is a cyclic intersecting sequence free condition. As a consequence, we only need to verify inheritance of convexity for unanimity games and for the small class of extremal convex games (N,vS) (for any 0̸â SâN) defined for any AâN by vS(A)=|Aâ©S|â1 if Aâ©Sâ 0̸, and vS(A)=0 otherwise. In particular, when (N,v¯) corresponds to Myerson's network-restricted game, inheritance of convexity can be verified by this way. For the Pmin correspondence (Pmin(A) is built by deleting edges of minimum weight in the subgraph GA of a weighted communication graph G), we show that inheritance of convexity for unanimity games already implies inheritance of convexity.
Journal: Discrete Optimization - Volume 25, August 2017, Pages 6-27