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].

Selected Related Publications

  • [DOI] Y. Yang, M. Geilen, T. Basten, S. Stuijk, and H. Corporaal, “Playing games with scenario- and resource-aware sdf graphs through policy iteration,” in 2012 design, automation test in europe conference exhibition (date), 2012, pp. 194-199.
    [Bibtex]
    @InProceedings{YGBea12,
    author = {Y. Yang and M. Geilen and T. Basten and S. Stuijk and H. Corporaal},
    title = {Playing games with scenario- and resource-aware SDF graphs through policy iteration},
    booktitle = {2012 Design, Automation Test in Europe Conference Exhibition (DATE)},
    year = {2012},
    pages = {194-199},
    month = {March},
    doi = {10.1109/DATE.2012.6176462},
    issn = {1530-1591},
    keywords = {control system synthesis;data flow graphs;embedded systems;game theory;iterative methods;media streaming;optimal control;resource allocation;control theory;controller modeling;controller player;controller sensitive runtime behavior;dynamic environment behavior;embedded controller;embedded systems;game theoretic model;input sensitive runtime behavior;optimal controller synthesis;policy iteration;resource aware SDF graph;runtime management;runtime scheduling;scenario aware SDF graph;synchronous dataflow model;throughput constraints;two-player mean payoff throughput game;winning strategy;Aerospace electronics;Embedded systems;Games;Schedules;Throughput;Transform coding;Vectors;Game Theory;Maxplus Algebra;Policy Iteration;Synchronous DataFlow},
    }

  • [DOI] B. van der Sanden, J. Bastos, J. Voeten, M. Geilen, M. A. Reniers, T. Basten, J. Jacobs, and R. R. H. Schiffelers, “Compositional specification of functionality and timing of manufacturing systems,” in 2016 forum on specification and design languages, FDL 2016, bremen, germany, september 14-16, 2016, 2016, p. 1–8.
    [Bibtex]
    @InProceedings{SBVea16,
    author = {Bram van der Sanden and Jo{\~{a}}o Bastos and Jeroen Voeten and Marc Geilen and Michel A. Reniers and Twan Basten and Johan Jacobs and Ramon R. H. Schiffelers},
    title = {Compositional specification of functionality and timing of manufacturing systems},
    booktitle = {2016 Forum on Specification and Design Languages, {FDL} 2016, Bremen, Germany, September 14-16, 2016},
    year = {2016},
    pages = {1--8},
    doi = {10.1109/FDL.2016.7880372},
    timestamp = {Wed, 24 May 2017 08:31:17 +0200},
    url = {https://doi.org/10.1109/FDL.2016.7880372},
    }

  • B. van der Sanden, “Performance analysis and optimization of supervisory controllers,” PhD Thesis, 2018.
    [Bibtex]
    @PhdThesis{San18,
    author = {Bram van der Sanden},
    title = {performance analysis and optimization of supervisory controllers},
    school = {Eindhoven University of Technology},
    year = {2018},
    }

References

[1] [doi] V. Dhingra and S. Gaubert, “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, New York, NY, USA, 2006.
[Bibtex]
@InProceedings{DG06,
author = {Dhingra, Vishesh and Gaubert, St\'{e}phane},
title = {How to solve large scale deterministic games with mean payoff by policy iteration},
booktitle = {Proceedings of the 1st international conference on Performance evaluation methodolgies and tools},
year = {2006},
series = {valuetools '06},
address = {New York, NY, USA},
publisher = {ACM},
acmid = {1190110},
articleno = {12},
doi = {http://doi.acm.org/10.1145/1190095.1190110},
isbn = {1-59593-504-5},
keywords = {graph algorithms, max-plus algebra, nonlinear harmonic functions, policy iteration, repeated games},
location = {Pisa, Italy},
owner = {mgeilen},
timestamp = {2011.02.10},
url = {http://doi.acm.org/10.1145/1190095.1190110},
}
[2] [doi] R. Bloem, K. Greimel, T. A. Henzinger, and B. Jobstmann, “Synthesizing robust systems,” in 2009 formal methods in computer-aided design, 2009, pp. 85-92.
[Bibtex]
@INPROCEEDINGS{BGHJ19,
author={Bloem, Roderick and Greimel, Karin and Henzinger, Thomas A. and Jobstmann, Barbara},
booktitle={2009 Formal Methods in Computer-Aided Design},
title={Synthesizing robust systems},
year={2009},
volume={},
number={},
pages={85-92},
doi={10.1109/FMCAD.2009.5351139}
}
[3] B. van der Sanden, “Performance analysis and optimization of supervisory controllers,” PhD Thesis, 2018.
[Bibtex]
@PhdThesis{San18,
author = {Bram van der Sanden},
title = {performance analysis and optimization of supervisory controllers},
school = {Eindhoven University of Technology},
year = {2018},
}