menu_book Explore the article's raw data

On the Separability of Functions and Games

Abstract

We study the notion of (additive) separability of a function of several variables with respect to a hypergraph (H-graph). We prove the existence of a unique minimal H-graph with respect to which a function is separable and show that the corresponding minimal decomposition of the function can be obtained through a recursive algorithm. We then focus on (strategic form) games and propose a concept of separability for a game with respect to a forward directed hypergraph (FDH-graph). This notion refines and generalizes that of the graphical game and is invariant with respect to strategic equivalence. We show that every game is separable with respect to a minimal FDH-graph. Moreover, for exact potential games, such minimal FDH-graph reduces to the minimal H-graph of the potential function. Our results imply and refine known results on graphical potential games and yield a new proof of the celebrated Hammersely-Clifford theorem on Markov random fields.

article Article
date_range 2024
language English
link Link of the paper
format_quote
Sorry! There is no raw data available for this article.
Loading references...
Loading citations...
Featured Keywords

Hammersley-Clifford theorem
hypergraphical games
network games
potential games
separable functions
Citations by Year

Share Your Research Data, Enhance Academic Impact