Itererad ångerminimering har nyligen introducerats av J.Y. Halpern och R. Pass i klassiska strategiska spel. För många spel av intresse, denna nya lösning koncept ger lösningar som bedöms vara mer rimliga än lösningar som erbjuds av traditionella spel koncept - som Nash jämvikt -. Även dator iterated ångra på explicit matris spel är konceptuellt och beräkningsmässigt lätt, ingenting är känt om att beräkna iterated ångra på spel vars matriser definieras implicit med hjälp av spel träd, spel DAG eller, mer allmänt spel grafer. I detta papper undersöker vi itererade ångra minimering för oändlig varaktighet två spelare kvantitativa icke-noll summa spel spelas på grafer. Vi anser att uppnåbarhetsmål som inte nödvändigtvis är antagonistiska. Kanter viktas av heltal - en för varje spelare - och utbetalningar definieras av summan av vikterna längs vägarna. Beroende på klassen av grafer, ger vi antingen polynom eller pseudo-polynom tid algoritmer för att beräkna en strategi som minimerar ångra för en fast spelare. Vi ger slutligen algoritmer för att beräkna de två spelarnas strategier som minimerar den itererade ångern för träd, och för grafer med strikt positiva vikter.
I ett tidigare bidrag har vi tillämpat den itererade ångra minimering koncept icke-noll summa spel spelas på viktade grafer för den kortaste vägen problem REF.
Iterated Regret Minimization in Game Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}