Abstract
Machine learning and game theory are known to exhibit a very strong link as they mutually provide each other with solutions and models allowing to study and analyze the optimal behaviour of a set of agents. In this paper, we take a closer look at a special class of games, known as fair cost sharing games, from a machine learning perspective. We show that this particular kind of games, where agents can choose between selfish behaviour and cooperation with shared costs, has a natural link to several machine learning scenarios including collaborative learning with homogeneous and heterogeneous sources of data. We further demonstrate how the game-theoretical results bounding the ratio between the best Nash equilibrium (or its approximate counterpart) and the optimal solution of a given game can be used to provide the upper bound of the gain achievable by the collaborative learning expressed as the expected risk and the sample complexity for homogeneous and heterogeneous cases, respectively. We believe that the established link can spur many possible future implications for other learning scenarios as well, with privacy-aware learning being among the most noticeable examples.
Introduction
In many real-world scenarios, multiple entities—such as hospitals or research labs—must decide whether to train machine learning models in isolation or pool their resources. While collaborative learning is intuitively beneficial, quantifying its exact advantage and ensuring participation from "selfish" agents (who only cooperate if it reduces their own costs) remains a challenge. This paper establishes a formal bridge between game theory and machine learning by framing collaborative learning as a "fair cost sharing game."
By applying the concept of the Price of Stability (PoS), the authors provide new theoretical guarantees on the reduction of error or sample complexity achievable through data pooling. This framework simplifies the understanding of collaborative learning by importing well-established tools from algorithmic game theory.
Methodology: Mapping ML to Game Theory
The core of the approach involves representing machine learning scenarios as a graph-based game. Agents are represented as source nodes seeking to reach a destination (a trained model). They can choose between a direct, individual path or a shared path through a "pooling" node.
In this model:
- Cost Functions: For homogeneous data, cost is defined as empirical risk. For heterogeneous data, it is defined as sample complexity.
- Weighting: A weighted version of the game accounts for disparities in data contributions; agents with more data contribute more but may benefit less.
- The Carpooling Analogy: Collaborative learning is likened to colleagues choosing between driving individual cars (high cost) or sharing a bus (shared cost).
Theoretical Results and Insights
The paper demonstrates that the "overhead" in collaborative PAC (Probably Approximately Correct) learning is mathematically equivalent to the Price of Stability in fair cost sharing games. This allows for the derivation of several key bounds:
- Homogeneous Sources: For agents sharing the same distribution, the collaborative gain is tied to the disparity in sample sizes ($m_i$). The ratio between individual and collaborative risks is bounded by $O(\frac{\log(\sum m_{max}/m_i)}{\alpha})$.
- Heterogeneous Sources: In transfer learning contexts, the ratio of individual to collaborative sample complexity is $\leq \frac{\Theta(\log K)}{K}$.
The benefit of collaboration is most pronounced when there is a large difference in the amount of data held by different agents. Furthermore, under certain conditions like Empirical Risk Minimization, the cost structure encourages agents to be truthful about their data labels, as dishonesty would increase their own eventual error.
Limitations and Future Work
While providing a unified framework, the current model assumes zero-cost pooling, ignoring communication and infrastructure overhead. Future research could incorporate Privacy-Aware Learning by adding a "privacy cost" to the graph edges. Additionally, extending this framework to multi-source domain adaptation and addressing the existence of pure Nash equilibria in weighted games remain open challenges.
Summary updated