{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T13:26:11Z","timestamp":1777728371734,"version":"3.51.4"},"reference-count":27,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Intelligenza Artificiale: The international journal of the AIxIA"],"published-print":{"date-parts":[[2024,10,9]]},"abstract":"<jats:p>We study equilibrium approximation in extensive-form adversarial team games, in which two teams of rational players compete in a zero-sum interaction. The suitable solution concept in these settings is the Team-Maxmin Equilibrium with Correlation (TMECor), which naturally arises when the team players play ex-ante correlated strategies. While computing such an equilibrium is APX -hard, recent techniques show that scalability beyond toy instances is possible. However, even compact representations of the team\u2019s strategy space, such as that exploiting Directed Acyclic Graphs (DAGs), have exponential size prohibiting solving large instances. In the present paper, we show that Monte Carlo sampling for regret minimization in adversarial team games can provide an important advancement. In particular, we design a DAG Monte Carlo Counterfactual Regret Minimization algorithm that performs outcome sampling with [Formula: see text] time complexity per iteration, where d is the depth of the DAG, and with a convergence rate bound of [Formula: see text], where b is the branching factor and k is the maximum number of private states in each public state of the team. We empirically evaluate our algorithms with a standard testbed of games, showing their performance when approximating equilibria. We investigate both cases in which only one team is composed of multiple players and cases in which both teams are composed of multiple players. Our empirical results show that our algorithms can provide a rough approximation to equilibrium strategies in all game instances considered, trading off a lower precision in the computed equilibrium for lower resource utilization.<\/jats:p>","DOI":"10.3233\/ia-240004","type":"journal-article","created":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T10:41:25Z","timestamp":1727174485000},"page":"219-237","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Monte-Carlo Regret Minimization for Adversarial Team Games"],"prefix":"10.1177","volume":"18","author":[{"given":"Luca","family":"Carminati","sequence":"first","affiliation":[{"name":"Politecnico di Milano, Piazza Leonardo da Vinci, Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Federico","family":"Cacciamani","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Piazza Leonardo da Vinci, Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"ref001","author":"Brown N.","year":"2017","journal-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1126\/science.aay2400"},{"key":"ref003","first-page":"2638","volume":"162","author":"Carminati L.","year":"2022","journal-title":"Proceedings of the 39th International Conference on Machine Learning"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11462"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1007\/s001820100066"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16678"},{"key":"ref007","author":"Farina G.","year":"2018","journal-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011917"},{"key":"ref009","author":"Farina G.","year":"2019","journal-title":"Proceedings of the 33rd International Conference on Neural Information Processing Systems"},{"key":"ref010","author":"Farina G.","year":"2020","journal-title":"Proceedings of the 37th International Conference on Machine Learning"},{"key":"ref011","first-page":"3164","author":"Farina G.","year":"2021","journal-title":"International Conference on Machine Learning"},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"key":"ref013","author":"Jakobsen S.K.","year":"2016","journal-title":"Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science"},{"key":"ref014","first-page":"97","volume":"1","author":"Kuhn. H.","year":"1951","journal-title":"Contributions to the Theory of Games"},{"key":"ref015","volume":"22","author":"Lanctot M.","year":"2009","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref016","author":"Lanctot M.","year":"2019","journal-title":"CoRR"},{"key":"ref017","author":"McAleer S.","year":"2024","journal-title":"Proceedings of the 37th International Conference on Neural Information Processing Systems"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1126\/science.aam6960"},{"key":"ref019","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33012157"},{"key":"ref020","unstructured":"SoutheyF., BowlingM., LarsonB., PiccioneC., BurchN., BillingsD., Rayner.C. Bayes\u2019 bluff: Opponent modelling in poker. 2005."},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1724-z"},{"key":"ref022","author":"Zhang B.H.","year":"2022","journal-title":"AAAI"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538330"},{"key":"ref024","author":"Zhang B.H.","year":"2023","journal-title":"Proceedings of the 40th International Conference on Machine Learning"},{"key":"ref025","author":"Zhang Y.","year":"2024","journal-title":"Proceedings of the 41st International Conference on Machine Learning"},{"key":"ref026","first-page":"928","author":"Zinkevich. M.","year":"2003","journal-title":"Proceedings of the 20th International Conference on Machine Learning"},{"key":"ref027","volume":"20","author":"Zinkevich M.","year":"2007","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["Intelligenza Artificiale: The international journal of the AIxIA"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/IA-240004","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/IA-240004","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/IA-240004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:51:54Z","timestamp":1777459914000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/IA-240004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10,9]]}},"alternative-id":["10.3233\/IA-240004"],"URL":"https:\/\/doi.org\/10.3233\/ia-240004","relation":{},"ISSN":["1724-8035","2211-0097"],"issn-type":[{"value":"1724-8035","type":"print"},{"value":"2211-0097","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,19]]}}}