Core nonemptiness holds for two thirds convex cooperative games
Core nonemptiness for $2/3$-convex games
Computer Science and Game Theory
Summary
Some cooperative situations in math called games can be hard to share fairly. The authors study a special class called two thirds convex games, which relaxes previous fairness rules. They prove these games always have a stable way to distribute value so no group wants to break away. They also provide a fast method to find such fair divisions and link this to a real-world voting method called consensus-minus-two.
What this means in practice
- •For political negotiation teams: Use the proven core nonemptiness of 2/3-convex games to model and find stable agreement divisions inspired by consensus-minus-two voting rules.
- •For game theory software developers: Implement the linear-time algorithm to quickly find core allocations in 2/3-convex games, enabling efficient fair division computations.
Authors
Keisuke Bando, Toshiyuki Hirai, Kenzo Imamura, Ryuhei Mizutani
Abstract
We study the core of $2/3$-convex games, a class of transferable-utility (TU) games that generalizes convex games, which requires at least two of any three distinct coalitions satisfy the supermodular inequality. We show that every $2/3$-convex game admits a marginal worth vector in the core, and hence has a nonempty core. Our proof is constructive and yields a linear-time algorithm for finding such a core allocation. We also show that $2/3$-convexity does not imply permutational convexity in general, while the implication holds under an additional superadditivity condition on pairs of singletons. As an application, we introduce a TU model motivated by the OSCE's consensus-minus-two procedure and show that the resulting game is $2/3$-convex but need not be convex.