Game Theoretic Models

Many analysis and synthesis problems can be reduced to game-theoretic problems and existing strategy algorithms for such games can be exploited, for example, performance optimal supervisory control, or optimal resource management.

A commonly used 2-player game is the mean pay-off game ^[1], played on a graph, where two players alternatingly select an outgoing edge from the current vertex to move to the next. The edges are decorated with a weight and one player’s objective is to minimize the average weight per step, and the other player’s objective is to maximize it.

A related game, the ration game, is a 2-player game, played on a graph where all edges have two weights and the objective is to minimize anf maximize, respectively, the ratio of the sum of one weight along the path and the sum of the other weight along the path. This is used for example to optimize the ration of progress and cost or progress and time ^[2][3].

References

1. Vishesh Dhingra and Stéphane Gaubert (2006): How to solve large scale deterministic games with mean payoff by policy iteration. In: Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, ACM, Pisa, Italy, 2006, ISBN: 1-59593-504-5.
2. Roderick Bloem and Karin Greimel and Thomas A. Henzinger and Barbara Jobstmann (2009): Synthesizing robust systems. In: 2009 Formal Methods in Computer-Aided Design, pp. 85-92, 2009.
3. Bram Sanden (2018): performance analysis and optimization of supervisory controllers. Eindhoven University of Technology, 2018.

Selected Related Publications

@phdthesis{San18,

title = {performance analysis and optimization of supervisory controllers},

author = {Bram Sanden},

year  = {2018},

date = {2018-01-01},

urldate = {2018-01-01},

school = {Eindhoven University of Technology},

keywords = {},

pubstate = {published},

tppubtype = {phdthesis}

}

@inproceedings{SBVea16,

title = {Compositional specification of functionality and timing of manufacturing systems},

author = {Bram Sanden and João Bastos and Jeroen Voeten and Marc Geilen and Michel A. Reniers and Twan Basten and Johan Jacobs and Ramon R. H. Schiffelers},

url = {https://doi.org/10.1109/FDL.2016.7880372},

doi = {10.1109/FDL.2016.7880372},

year  = {2016},

date = {2016-01-01},

urldate = {2016-01-01},

booktitle = {2016 Forum on Specification and Design Languages, FDL 2016, Bremen, Germany, September 14-16, 2016},

pages = {1–8},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{YGBSC12,

title = {Playing games with scenario- and resource-aware SDF graphs through policy iteration},

author = {Yang Yang and Marc Geilen and Twan Basten and Sander Stuijk and Henk Corporaal},

doi = {10.1109/DATE.2012.6176462},

year  = {2012},

date = {2012-01-01},

urldate = {2012-01-01},

booktitle = {2012 Design, Automation & Test in Europe Conference & Exhibition (DATE)},

pages = {194-199},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}