<img src="http://cse.lab.imtlucca.it/~bemporad/gnep-learn/images/gnep-learn-logo.png" alt="gnep-learn" width=40%/>
A Python package for solving Generalized Nash Equilibrium Problems by active learning of best-response models.
# Contents
* [Package description](#description)
* [Installation](#install)
* [Basic usage](#basic-usage)
* [Contributors](#contributors)
* [Acknowledgments](#acknowledgments)
* [Citing jax-sysid](#bibliography)
* [License](#license)
<a name="description"></a>
## Package description
**gnep-learn** is a Python package for solving Generalized Nash Equilibrium Problems with $n$ agents by actively learning linear surrogate models of the agents' best responses. The algorithm is based on a centralized entity that probes the agents’ reactions and recursively updates the local linear parametric estimates of the action-reaction mappings, possibly converging to a stationary action profile.
The package implements the approach described in the following paper:
<a name="cite-FB24"></a>
> [1] F. Fabiani, A. Bemporad, "[An active learning method for solving competitive multi-agent decision-making and control problems](
http://arxiv.org/abs/2212.12561)," submitted for publication. Available on arXiv at <a href="http://arxiv.org/abs/2212.12561">
http://arxiv.org/abs/2212.12561</a>, 2024. [[bib entry](#ref1)]
<a name="install"></a>
## Installation
~~~python
pip install gnep-learn
~~~
<a name="basic-usage"></a>
## Basic usage
Consider a set of agents $j=1,\ldots,n$, each one minimizing a private objective function $J_j(x_j,x_{-j})$, possibly under global constraints $Ax\leq b$, $g(x)\leq 0$, where $x\in R^{n_d}$ is the overall decision vector, $x_j$ is the subvector of $x$ containing the variables decided by agent $j$, $x_{-j}$ are the variables optimized by the remaining agents.
Denoting by $f_j(x_{-j})$ the best response of agent $j$ given the remaining decisions $x_{-j}$, the goal is to find
a stationary profile $x^*$ such that $x^*_j=f_j(x^*_{-j})$.
The central entity proposes iteratively a tentative decision vector $x(k)$ to the agents and collects the corresponding best responses $x_j(k)=f_j(x_{-j}(k))$. Such information is used by the central entity to update affine surrogate models $\hat f_j$ of the best responses by linear Kalman filtering (i.e., by recursive least-squares). During the first `N_init` iterations, the vectors $x(k)$ are generated randomly; afterward, based on the learned best response models, the centralized entity solves a constrained least-squares problem to attempt to find a stationary profile $x(k)$.
Let us set up a simple problem with two agents, each one optimizing a single variable within the range $[-10,10]$. We want to run 10 random sampling steps followed by another 10 active learning steps, for a total of $N=20$ iterations:
~~~python
from gnep_learn import GNEP
n = 2 # number of agents
dim = [1, 1] # each agent optimizes one variable
N_init = 10 # number of initial random sampling iterations
N = 20 # total number of iterations
def J1(x1,x2):
return x1**2 -x1*x2 - x1 # function minimized by agent #1
def J2(x2,x1):
return x2**2 +x1*x2 -x2 # function minimized by agent #2
J = [lambda x1, x2: J1(x1,x2)[0],
lambda x2, x1: J2(x2,x1)[0]] # collection of agents' objectives
lbx = -10. * np.ones(2) # lower bound on x used during optimization
ubx = 10. * np.ones(2) # upper bound on x used during optimization
gnep = GNEP(J, dim, lbx=lbx, ubx=ubx) # Create GNEP object
xeq, XX, XXeq, _ = gnep.learn(N=N, N_init=N_init) # Learn equilibrium
~~~
The returned vector `xeq` is a stationary profile. The learning function `learn` also returns the sequence `XX` of tentative equilibria suggested by the central entity and `XXeq` the corresponding best responses.
~~~python
xeq, XX, XXeq, TH = gnep.learn(N=N, N_init=N_init, save_model_params = True)
~~~
also returns the sequence `TH` of parameters of the affine best response models learned, where `TH[k][j][i]` contains the parameter vector $\theta_{ji}(k)$ of the model at step $k$ of the $i$th component of the best response $x_j$ given $x_{-j}$, namely the estimate $[\hat x_j]_i = [x_{-j}'\ 1]\theta_{ji}(k)$ of $[x_j]_i$.
More generally, each agent can minimize an objective function $\tilde J_j(w_j,x_{-j})$, possibly under private constraints
on the local decision vector $w_j$, and returns the shared decision vector $x_j=f_j(x_{-j})=h_j(w_j)$,
where $h_j$ is some private mapping that we assume here to be linear, i.e., $x_j=W_jw_j$.
See the example files in the `examples` folder for how to set up and solve different generalized Nash equilibrium problems.
<a name="contributors"></a>
## Contributors
This package was coded by Alberto Bemporad.
This software is distributed without any warranty. Please cite the paper below if you use this software.
<a name="acknowledgments"></a>
## Acknowledgments
<a name="bibliography"></a>
## Citing `gnep-learn`
<a name="ref1"></a>
```
@article{FB24,
author = {F. Fabiani and A. Bemporad},
title={An active learning method for solving competitive multi-agent decision-making and control problems},
note = {submitted for publication. Also available on arXiv
at \url{http://arxiv.org/abs/2212.12561}},
year=2024
}
```
<a name="license"></a>
## License
Apache 2.0
(C) 2024 A. Bemporad
Raw data
{
"_id": null,
"home_page": null,
"name": "gnep-learn",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": null,
"keywords": "active learning, generalized nash equilibrium problems, game theory, kalman filtering",
"author": null,
"author_email": "Alberto Bemporad <alberto.bemporad@imtlucca.it>",
"download_url": "https://files.pythonhosted.org/packages/1e/d3/26be46ba1e5d85657f9d02a0c219956d2af794769420620681c89854d291/gnep_learn-0.1.0.tar.gz",
"platform": null,
"description": "<img src=\"http://cse.lab.imtlucca.it/~bemporad/gnep-learn/images/gnep-learn-logo.png\" alt=\"gnep-learn\" width=40%/>\n\nA Python package for solving Generalized Nash Equilibrium Problems by active learning of best-response models.\n \n# Contents\n\n* [Package description](#description)\n\n* [Installation](#install)\n\n* [Basic usage](#basic-usage)\n\n* [Contributors](#contributors)\n\n* [Acknowledgments](#acknowledgments)\n\n* [Citing jax-sysid](#bibliography)\n\n* [License](#license)\n\n\n<a name=\"description\"></a>\n## Package description \n\n**gnep-learn** is a Python package for solving Generalized Nash Equilibrium Problems with $n$ agents by actively learning linear surrogate models of the agents' best responses. The algorithm is based on a centralized entity that probes the agents\u2019 reactions and recursively updates the local linear parametric estimates of the action-reaction mappings, possibly converging to a stationary action profile. \n\nThe package implements the approach described in the following paper:\n\n<a name=\"cite-FB24\"></a>\n> [1] F. Fabiani, A. Bemporad, \"[An active learning method for solving competitive multi-agent decision-making and control problems](\nhttp://arxiv.org/abs/2212.12561),\" submitted for publication. Available on arXiv at <a href=\"http://arxiv.org/abs/2212.12561\">\nhttp://arxiv.org/abs/2212.12561</a>, 2024. [[bib entry](#ref1)]\n\n\n<a name=\"install\"></a>\n## Installation\n\n~~~python\npip install gnep-learn\n~~~\n\n<a name=\"basic-usage\"></a>\n## Basic usage\nConsider a set of agents $j=1,\\ldots,n$, each one minimizing a private objective function $J_j(x_j,x_{-j})$, possibly under global constraints $Ax\\leq b$, $g(x)\\leq 0$, where $x\\in R^{n_d}$ is the overall decision vector, $x_j$ is the subvector of $x$ containing the variables decided by agent $j$, $x_{-j}$ are the variables optimized by the remaining agents.\nDenoting by $f_j(x_{-j})$ the best response of agent $j$ given the remaining decisions $x_{-j}$, the goal is to find\na stationary profile $x^*$ such that $x^*_j=f_j(x^*_{-j})$.\n\nThe central entity proposes iteratively a tentative decision vector $x(k)$ to the agents and collects the corresponding best responses $x_j(k)=f_j(x_{-j}(k))$. Such information is used by the central entity to update affine surrogate models $\\hat f_j$ of the best responses by linear Kalman filtering (i.e., by recursive least-squares). During the first `N_init` iterations, the vectors $x(k)$ are generated randomly; afterward, based on the learned best response models, the centralized entity solves a constrained least-squares problem to attempt to find a stationary profile $x(k)$.\n\nLet us set up a simple problem with two agents, each one optimizing a single variable within the range $[-10,10]$. We want to run 10 random sampling steps followed by another 10 active learning steps, for a total of $N=20$ iterations:\n\n~~~python\nfrom gnep_learn import GNEP\n\nn = 2 # number of agents\ndim = [1, 1] # each agent optimizes one variable\nN_init = 10 # number of initial random sampling iterations\nN = 20 # total number of iterations\n\ndef J1(x1,x2):\n return x1**2 -x1*x2 - x1 # function minimized by agent #1\ndef J2(x2,x1):\n return x2**2 +x1*x2 -x2 # function minimized by agent #2\n\nJ = [lambda x1, x2: J1(x1,x2)[0],\n lambda x2, x1: J2(x2,x1)[0]] # collection of agents' objectives\n\nlbx = -10. * np.ones(2) # lower bound on x used during optimization\nubx = 10. * np.ones(2) # upper bound on x used during optimization\n\ngnep = GNEP(J, dim, lbx=lbx, ubx=ubx) # Create GNEP object\n\nxeq, XX, XXeq, _ = gnep.learn(N=N, N_init=N_init) # Learn equilibrium\n~~~\n\nThe returned vector `xeq` is a stationary profile. The learning function `learn` also returns the sequence `XX` of tentative equilibria suggested by the central entity and `XXeq` the corresponding best responses. \n\n~~~python\nxeq, XX, XXeq, TH = gnep.learn(N=N, N_init=N_init, save_model_params = True)\n~~~\nalso returns the sequence `TH` of parameters of the affine best response models learned, where `TH[k][j][i]` contains the parameter vector $\\theta_{ji}(k)$ of the model at step $k$ of the $i$th component of the best response $x_j$ given $x_{-j}$, namely the estimate $[\\hat x_j]_i = [x_{-j}'\\ 1]\\theta_{ji}(k)$ of $[x_j]_i$.\n\nMore generally, each agent can minimize an objective function $\\tilde J_j(w_j,x_{-j})$, possibly under private constraints\non the local decision vector $w_j$, and returns the shared decision vector $x_j=f_j(x_{-j})=h_j(w_j)$,\nwhere $h_j$ is some private mapping that we assume here to be linear, i.e., $x_j=W_jw_j$.\n\nSee the example files in the `examples` folder for how to set up and solve different generalized Nash equilibrium problems.\n \n<a name=\"contributors\"></a>\n## Contributors\n\nThis package was coded by Alberto Bemporad.\n\n\nThis software is distributed without any warranty. Please cite the paper below if you use this software.\n\n<a name=\"acknowledgments\"></a>\n## Acknowledgments\n\n\n<a name=\"bibliography\"></a>\n## Citing `gnep-learn`\n\n<a name=\"ref1\"></a>\n\n```\n@article{FB24,\n author = {F. Fabiani and A. Bemporad},\n title={An active learning method for solving competitive multi-agent decision-making and control problems},\n note = {submitted for publication. Also available on arXiv\n at \\url{http://arxiv.org/abs/2212.12561}},\n year=2024\n}\n```\n\n<a name=\"license\"></a>\n## License\n\nApache 2.0\n\n(C) 2024 A. Bemporad\n",
"bugtrack_url": null,
"license": null,
"summary": "gnep-learn - A Python package for learning-based solutions of generalized Nash equilibrium problems.",
"version": "0.1.0",
"project_urls": {
"Homepage": "http://cse.lab.imtlucca.it/~bemporad/gnep-learn"
},
"split_keywords": [
"active learning",
" generalized nash equilibrium problems",
" game theory",
" kalman filtering"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "9cc5419ddca37372f2d2cfafebef8644022f07eb184366d7c98f8b6c8831d54e",
"md5": "fb0ac460770b6fb9a405f163b9124c8f",
"sha256": "9480ad26e3364258bbb93f81487dbb87544d6d97e9d01db404b060b768d4bc7f"
},
"downloads": -1,
"filename": "gnep_learn-0.1.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "fb0ac460770b6fb9a405f163b9124c8f",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 14337,
"upload_time": "2024-07-04T21:38:52",
"upload_time_iso_8601": "2024-07-04T21:38:52.905628Z",
"url": "https://files.pythonhosted.org/packages/9c/c5/419ddca37372f2d2cfafebef8644022f07eb184366d7c98f8b6c8831d54e/gnep_learn-0.1.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "1ed326be46ba1e5d85657f9d02a0c219956d2af794769420620681c89854d291",
"md5": "e635dbce376d46ad0eb76dff4984ce5f",
"sha256": "87539240e689e51241214553803c7c301117fe860478e0345e2109d67d5c7d19"
},
"downloads": -1,
"filename": "gnep_learn-0.1.0.tar.gz",
"has_sig": false,
"md5_digest": "e635dbce376d46ad0eb76dff4984ce5f",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 15092,
"upload_time": "2024-07-04T21:38:54",
"upload_time_iso_8601": "2024-07-04T21:38:54.345929Z",
"url": "https://files.pythonhosted.org/packages/1e/d3/26be46ba1e5d85657f9d02a0c219956d2af794769420620681c89854d291/gnep_learn-0.1.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-07-04 21:38:54",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "gnep-learn"
}
JSON