Action Investment Games
Author
Laursen, Simon
Term
4. term
Education
Publication year
2012
Pages
31
Abstract
Denne afhandling introducerer formalismen Action Investment Games (AIG), en udvidelse af to-spiller energispil med budgetter og priser på handlinger, til at analysere afvejningen mellem en begrænset energiresurse og to budgetter. I AIG kan hver spiller, før selve spillet, investere inden for et fastsat budget for at deaktivere eller aktivere handlinger, hvilket modellerer designvalg som komponentkvalitet kontra batteristørrelse; en netværks-relæstation bruges som motiverende eksempel. Det centrale beslutningsproblem er, om Spiller 1 kan foretage en investering inden for sit budget, så uanset hvilken investering Spiller 2 foretager inden for sit budget, har Spiller 1 en strategi, der holder energien inden for et givet interval og dermed vinder det resulterende energispil. Afhandlingen giver formelle definitioner, opsummerer relevant baggrund om kvantificerede booleske formler og det polynomielle hierarki, og etablerer kompleksitetsgrænser via reduktioner konstrueret med dedikerede gadgets. Hovedresultatet er, at de relevante problemer i værste fald bliver to niveauer sværere i det polynomielle hierarki sammenlignet med de tilsvarende energispilsproblemer, og afhandlingen afgrænser disse grænser for relevante varianter inden for formalismen.
This thesis introduces the formalism of Action Investment Games (AIG), an extension of two-player energy games with budgets and prices on actions, to analyze the trade-off between a constrained energy resource and two budgets. In AIG, before play, each player may invest within a fixed budget to disable or enable actions, modeling design choices such as component quality versus battery size; a network relay station serves as a motivating example. The central decision problem asks whether Player 1 can make an investment within budget such that, for any investment by Player 2 within budget, Player 1 has a strategy that keeps the energy within a given interval and thus wins the resulting energy game. The thesis provides formal definitions, reviews background on quantified Boolean formulas and the polynomial hierarchy, and derives complexity bounds via reductions built from dedicated gadgets. The main finding is that, in the worst case, the relevant problems become two levels harder in the polynomial hierarchy than the corresponding energy-game problems, and the thesis delineates these bounds for pertinent variants within the formalism.
[This summary has been generated with the help of AI directly from the project (PDF)]
Documents