Learning the Expected Core of Strictly Convex Stochastic Cooperative Games

Reward allocation, also known as the credit assignment problem, has been an important topic in economics, engineering, and machine learning. An important concept in reward allocation is the core, which is the set of stable allocations where no agent has the motivation to deviate from the grand coalition. In previous works, computing the core requires either knowledge of the reward function in deterministic games or the reward distribution in stochastic games. However, this is unrealistic, as the reward function or distribution is often only partially known and may be subject to uncertainty. In this paper, we consider the core learning problem in stochastic cooperative games, where the reward distribution is unknown. Our goal is to learn the expected core, that is, the set of allocations that are stable in expectation, given an oracle that returns a stochastic reward for an enquired coalition each round. Within the class of strictly convex games, we present an algorithm named exttt{Common-Points-Picking} that returns a point in the expected core given a polynomial number of samples, with high probability. To analyse the algorithm, we develop a new extension of the separation hyperplane theorem for multiple convex sets.

奖励分配，也被称为信用分配问题，一直是经济学、工程学和机器学习中的一个重要课题。奖励分配中的一个重要概念是核心（core），它是一组稳定的分配集合，在其中没有参与者有动机偏离大联盟。在以往的研究中，计算核心要么需要知道确定性博弈中的奖励函数，要么需要知道随机博弈中的奖励分布。然而，这是不现实的，因为奖励函数或分布往往只是部分已知的，并且可能受到不确定性的影响。在本文中，我们考虑随机合作博弈中的核心学习问题，其中奖励分布是未知的。我们的目标是学习期望核心，即期望上稳定的分配集合，给定一个每轮为所查询的联盟返回一个随机奖励的预言机（oracle）。在严格凸博弈的类别中，我们提出了一种名为\texttt{Common - Points - Picking}的算法，该算法在给定多项式数量的样本的情况下，以高概率返回期望核心中的一个点。为了分析该算法，我们为多个凸集开发了分离超平面定理的一种新的扩展。