Models for Solving Multi-Agent Decision Problems
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2023-12-12
Department
Major/Subject
Systems and Operations Research
Mcode
SCI3055
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
53 + 10
Series
Abstract
Several ways of solving multi-agent decision problems, e.g., complete information game theory and adversarial risk analysis, have been proposed in the literature. Most approaches, however, cannot accommodate constraints spanning the entire problem or situations in which earlier decisions cannot be recalled when making later ones. Decision Programming is a methodology that helps address these limitations; however, it has thus far only been used to solve single-agent decision problems. This thesis aims to expand Decision Programming to accommodate multi-agent decision problems. Our approach first transforms the multi-agent problem into several single-agent problems, one for each actor, that are represented with an influence diagram. We solve these problems with the level-$k$ approach, updating the initial distribution for the decisions of each actor iteratively. For each problem at each level, we use Decision Programming to solve the single-agent problems. This process is repeated until we arrive at a convergent solution. We apply our methodology to two examples, one in critical infrastructure protection and the other in border security. In the first example, our methodology produced results very similar to a traditional adversarial risk analysis method that used node removals. Furthermore, we solved an extension of the first example and one example concerning border security, which both included overarching constraints, non-perfect strategists, and multiple decision alternatives. Overall, our solutions created beneficial results for protecting critical infrastructure and constructing border security portfolios.Kirjallisuudessa on esitetty useita tapoja ratkaista usean päätöksentekijän päätösongelmia, kuten complete information -peliteoria ja vastakkainasettelullinen riskianalyysi. Näillä metodeilla ei voi kuitenkaan ratkaista ongelmia, joissa on koko ongelman kattavia rajoitusehtoja tai tilanteita, joissa aikaisempia päätöksiä ei tiedetä tehtäessä myöhempiä päätöksiä. Decision Programming -metodologia kehitettiin ratkaisemaan päätösongelmia, joissa esiintyy näitä haasteita. Tätä metodologiaa on kuitenkin käytetty vain yhden päätöksentekijän päätösongelmien ratkaisuun. Tässä diplomityössä Decision Programming -metodologiaa kehitetään siten, että sillä voidaan ratkaista usean päätöksentekijän päätösongelmia. Työssä esitetty menetelmä luo ensin usean päätöksentekijän päätösongelmasta yhden päätösongelman jokaiselle päätöksentekijälle. Nämä ongelmat ratkaistaan level-$k$ -viitekehyksellä päivittäen jokaisen päätöksentekijän päätöksille luotua alkujakaumaa iteratiivisesti. Jokaisen tason jokainen päätösongelma ratkaistaan Decision Programming -metodologialla. Menetelmää toistetaan kunnes tasojen tulokset konvergoituvat. Kehitettyä menetelmää sovelletaan kahteen esimerkkiin, joista ensimmäinen liittyy kriittisen infrastruktuurin suojaamiseen ja toinen rajaturvallisuuteen. Menetelmä antaa näistä ensimmäiseen samankaltaisia tuloksia kuin perinteisempi vastakkainasettelullinen riskianalyysi. Lisäksi työ esittelee ratkaisut jatkokehitetylle versiolle infrastruktuuri-esimerkistä ja rajaturvallisuutta kuvaavasta esimerkistä. Näistä molemmat sisälsivät ongelman kattavia rajoitusehtoja, rajoittunutta rationaalisuutta sekä useita päätösvaihtoehtoja. Saadut tulokset ovat hyödyllisiä infrastruktuurien suojelemiseen sekä rajaturvallisuusportfolioiden kehittämiseen.Description
Supervisor
Salo, AhtiThesis advisor
Roponen, JuhoKeywords
influence diagram, adversarial risk analysis, decision programming, optimization