Research map / Learning theory and algorithms / Submodular and game algorithms
Learning the Expected Core of Strictly Convex Stochastic Cooperative Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Common-Points-Picking, which learns a point in the expected core of strictly convex stochastic cooperative games from bandit feedback with polynomial samples, via a new multi-convex-set hyperplane separation theorem.
Problem
Learning the expected core of stochastic cooperative games when the reward distribution is unknown and only the reward of the queried coalition is observed each round (bandit feedback).
Approach
Estimate n vertices (marginal vectors of permutations) of the expected core with Hoeffding confidence sets, and stop once separating hyperplanes show the confidence sets admit a common point; the average of chosen vertices lies in the core. Uses a new hyperplane separation theorem for multiple convex sets.
Key results
- Theorem gives sample complexity T = O(n^15 log(n/(delta*varsigma)) / varsigma^4) for permutation set based on simple adjacent permutations, returning a point in the expected core w.p. at least 1-delta.
- With cyclic permutations under an width assumption, sample complexity improves to O(n^5 c_W^4 log(...)/varsigma^4).
- Simulations show sample growth nearly matching the theoretical bound for strictly convex games, and sub-exponential growth in n even when strict convexity is violated (varsigma=0).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Common-Points-Picking under the strictly convex game assumption | Expected-core learning with bandit feedback · Strictly convex games | sample complexity: T = O\RoundBr{\frac{n^{15} \log(n\delta^{-1}\varsigma^{-1})}{\varsigma^4}} | Helped |
| Use cyclic permutations instead of the adjacent-permutation vertex set, under the stated width assumption (ablation) | Common-Points-Picking · Strictly convex games with \Width(W) \geq \frac{n\varsigma}{c_W} | sample complexity: O\RoundBr{\frac{n^{15} \log(n\delta^{-1}\varsigma^{-1})}{\varsigma^4}} -> O\RoundBr{\frac{n^{5}c_W^4 \log(n c_W \delta^{ | Helped |
| Use cyclic permutations as the input when strict convexity is violated (ablation) | Common-Points-Picking · Convex games with strict convexity constant 0 | sample complexity growth with n | Helped |
| Attempt to learn the expected core when it is not full-dimensional | Any learning algorithm · Games with expected-core dimension k < n-1 | probability of returning a point in the expected core: 1-\delta | Hurt |
| Choose the adjacent-permutation simplex instead of the cyclic-permutation simplex (ablation) | Common-Points-Picking · Permutahedron | simplex width: \Width(M) \leq \frac{3}{n} -> \Width(\overline W) \geq \frac{n}{2} | Hurt |
| Use cyclic permutations for the vertex set (ablation) | Common-Points-Picking · Simulated strictly convex games | constant c_W: interval (0, 30) | Helped |
Surprising findings
- Even with convex (non-strictly) games, the algorithm empirically needs only sub-exponential samples in n, though no theory is given.
- Expected core learning with bandit feedback is impossible with finite samples in general cooperative games when the core is not full-dimensional.
Limitations
- Requires strict convexity (full-dimensional expected core) assumption; no matching lower bound is established.
- Cyclic-permutation sample complexity relies on an unproven width assumption with constant c_W.
- Assumes the grand coalition's expected reward mu(N) is known.
Experimental setup
Metrics: number of samples required vs. number of players n
Baselines: Shapley approximation general robust-optimization expected core learner
Builds on: Hoeffding's inequality separating hyperplane theorem generalised permutahedra expected core learning (robust optimization approach)
Closest papers by meaning
- If You Like Shapley Then You’ll Love the Core (AAAI 2021 · similarity 0.88)
- Computing Least Cores of Supermodular Cooperative Games (AAAI 2017 · similarity 0.87)
- Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games (NeurIPS 2021 · similarity 0.87)
- Robust PAC Learning of Concurrent Stochastic Games (NeurIPS 2026 · similarity 0.86)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.86)
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.