Learning the Expected Core of Strictly Convex Stochastic Cooperative
  Games
Nam Phuong Tran The Anh Ta Shuqing Shi Debmalya Mandal Yali Du Long Tran-Thanh
Reward allocation, also known as the credit assignment problem, has been an
important topic in economics, engineering, and machine learning. An important
concept in credit assignment is the core, which is the set of stable
allocations where no agent has the motivation to deviate from the grand
coalition. In this paper, we consider the stable allocation learning problem of
stochastic cooperative games, where the reward function is characterised as a
random variable with an unknown distribution. Given an oracle that returns a
stochastic reward for an enquired coalition each round, our goal is to learn
the expected core, that is, the set of allocations that are stable in
expectation. Within the class of strictly convex games, we present an algorithm
named \texttt{Common-Points-Picking} that returns a stable allocation given a
polynomial number of samples, with high probability. The analysis of our
algorithm involves the development of several new results in convex geometry,
including an extension of the separation hyperplane theorem for multiple convex
sets, and may be of independent interest.