Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On the Separability of Functions and Games

Arditti, Laura ; Como, Giacomo LU and Fagnani, Fabio (2024) In IEEE Transactions on Control of Network Systems 11(2). p.831-841
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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Hammersley-Clifford theorem, hypergraphical games, network games, potential games, separable functions
in
IEEE Transactions on Control of Network Systems
volume
11
issue
2
pages
11 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85171590322
ISSN
2325-5870
DOI
10.1109/TCNS.2023.3314552
language
English
LU publication?
yes
id
138b27d3-1571-4251-8571-f02f343e0a80
date added to LUP
2025-01-10 13:36:25
date last changed
2025-04-04 15:13:06
@article{138b27d3-1571-4251-8571-f02f343e0a80,
  abstract     = {{<p>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.</p>}},
  author       = {{Arditti, Laura and Como, Giacomo and Fagnani, Fabio}},
  issn         = {{2325-5870}},
  keywords     = {{Hammersley-Clifford theorem; hypergraphical games; network games; potential games; separable functions}},
  language     = {{eng}},
  number       = {{2}},
  pages        = {{831--841}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Control of Network Systems}},
  title        = {{On the Separability of Functions and Games}},
  url          = {{http://dx.doi.org/10.1109/TCNS.2023.3314552}},
  doi          = {{10.1109/TCNS.2023.3314552}},
  volume       = {{11}},
  year         = {{2024}},
}