Solving Multi-Agent Games on Networks

Solving Multi-Agent Games on Networks | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Solving Multi-Agent Games on Networks Yair Vaknin, Amnon Meisels This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3992095/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 26 Feb, 2025 Read the published version in Autonomous Agents and Multi-Agent Systems → Version 1 posted 9 You are reading this latest preprint version Abstract Multi-agent games on networks (GoNs) have nodes that represent agents and edges that represent interactions among agents. Binary GoNs are composed of 2-Players games on each of their edges. Non binary GoNs have games that are played by all agents in each neighborhood.Solutions to games on networks are stable states (i.e., pure Nash equilibria), and in general one is interested in efficient solutions (i.e., of high social welfare).Incentives, in the form of side payments among agents, are known to promote increased-efficiency stable states. This study addresses the multi-agent aspect of games on networks - a system of multiple agents that compose a game and seek a solution. The agents playing the game are assumed to be strategic and the present study proposes an iterative distributed algorithm that lets the agents interact (i.e., negotiate) in neighborhoods in a process that guarantees the convergence of any multi-agent game on network to a stable state.The proposed algorithm treats the game as a repeated social choice action that takes place in one neighborhood at a time. A truthful enforcing mechanism is integrated into the process, collecting agents' valuations and computing incentives on the fly while eliminating strategic behavior. This method - the TECon algorithm - is proven to converge to solutions that are at least as efficient as the initial state, for any game on network.A specific version of the algorithm is given for the class of public goods games, where the main properties of the algorithm are guaranteed even when the strategic agents playing the game consider their possible future valuations when interacting.This opens an interesting new research direction on application-specific derivatives of TECon that, similarly to the case of public goods games, may lead to solutions of greater efficiency. An extensive experimental evaluation on randomly generated games on networks demonstrates that the TECon algorithm outperforms former solving methods on several classes of games on networks. Games on networks Multi-agent search Side payments Efficient solutions Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 26 Feb, 2025 Read the published version in Autonomous Agents and Multi-Agent Systems → Version 1 posted Editorial decision: Revision requested 21 May, 2024 Reviews received at journal 14 May, 2024 Reviews received at journal 09 May, 2024 Reviewers agreed at journal 12 Mar, 2024 Reviewers agreed at journal 04 Mar, 2024 Reviewers invited by journal 03 Mar, 2024 Editor assigned by journal 29 Feb, 2024 Submission checks completed at journal 29 Feb, 2024 First submitted to journal 26 Feb, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-3992095","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":276077922,"identity":"e3d1e845-826b-493a-bc48-7a6b1660bb4c","order_by":0,"name":"Yair Vaknin","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA7ElEQVRIiWNgGAWjYFACxgYgYQNmMsPEDjwgrCUNrAGhJYGwVYdRtTDg02Jw/HDbZ56a83n8/OcPMBf8OszA336AEa8tBmcSm2fzHLtdLDkjmYF5Zt9hBokzCfgdZnAgsZlxBtvtxA03gA7j7QG68AYBvxicfwjU8u9c4obzhyFa5AlquZHYzPCx7UDihgNAh/H8OAwUIaBF8sZDoJa+ZJBfDA7PbEjnMTyT2IBXC9/59McMCd/sgCF28OHjgj/WcnLHDx/+8AGPFoUDEBps7AHGNgYeaOTiBvINSFoYGP7gVTwKRsEoGAUjFAAA9VJVxJaWIsAAAAAASUVORK5CYII=","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":true,"submittingAuthor":false,"prefix":"","firstName":"Yair","middleName":"","lastName":"Vaknin","suffix":""},{"id":276077923,"identity":"df44fedd-6975-4382-9ab2-1f4f40ca8338","order_by":1,"name":"Amnon Meisels","email":"","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Amnon","middleName":"","lastName":"Meisels","suffix":""}],"badges":[],"createdAt":"2024-02-26 22:35:16","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3992095/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3992095/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s10458-025-09696-7","type":"published","date":"2025-02-26T15:57:57+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":77622749,"identity":"70d96d57-2602-4228-8098-3e105a8cec99","added_by":"auto","created_at":"2025-03-03 16:10:12","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":669818,"visible":true,"origin":"","legend":"","description":"","filename":"GoNsJAAMAS.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3992095/v1_covered_7946f87d-4729-450e-bd87-81b3b9dfa3ec.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Solving Multi-Agent Games on Networks","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"autonomous-agents-and-multi-agent-systems","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"agnt","sideBox":"Learn more about [Autonomous Agents and Multi-Agent Systems](http://link.springer.com/journal/10458)","snPcode":"10458","submissionUrl":"https://submission.nature.com/new-submission/10458/3","title":"Autonomous Agents and Multi-Agent Systems","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Games on networks, Multi-agent search, Side payments, Efficient solutions","lastPublishedDoi":"10.21203/rs.3.rs-3992095/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3992095/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Multi-agent games on networks (GoNs) have nodes that represent agents and edges that represent interactions among agents. Binary GoNs are composed of 2-Players games on each of their edges. Non binary GoNs have games that are played by all agents in each neighborhood.Solutions to games on networks are stable states (i.e., pure Nash equilibria), and in general one is interested in efficient solutions (i.e., of high social welfare).Incentives, in the form of side payments among agents, are known to promote increased-efficiency stable states.\nThis study addresses the multi-agent aspect of games on networks - a system of multiple agents that compose a game and seek a solution. The agents playing the game are assumed to be strategic and the present study proposes an iterative distributed algorithm that lets the agents interact (i.e., negotiate) in neighborhoods in a process that guarantees the convergence of any multi-agent game on network to a stable state.The proposed algorithm treats the game as a repeated social choice action that takes place in one neighborhood at a time. A truthful enforcing mechanism is integrated into the process, collecting agents' valuations and computing incentives on the fly while eliminating strategic behavior. This method - the TECon algorithm - is proven to converge to solutions that are at least as efficient as the initial state, for any game on network.A specific version of the algorithm is given for the class of public goods games, where the main properties of the algorithm are guaranteed even when the strategic agents playing the game consider their possible future valuations when interacting.This opens an interesting new research direction on application-specific derivatives of TECon that, similarly to the case of public goods games, may lead to solutions of greater efficiency. An extensive experimental evaluation on randomly generated games on networks demonstrates that the TECon algorithm outperforms former solving methods on several classes of games on networks.","manuscriptTitle":"Solving Multi-Agent Games on Networks","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-03-04 05:41:28","doi":"10.21203/rs.3.rs-3992095/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-05-21T15:55:25+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-05-14T15:29:49+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-05-09T04:58:47+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"73571b24-c144-4f0c-ad95-fa122d582f2a","date":"2024-03-12T19:51:49+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"0453c1c7-a82d-47bb-b8d5-097bef35310a","date":"2024-03-04T05:22:08+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-03-03T17:59:26+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-03-01T03:28:46+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-02-29T07:40:52+00:00","index":"","fulltext":""},{"type":"submitted","content":"Autonomous Agents and Multi-Agent Systems","date":"2024-02-26T22:32:40+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"autonomous-agents-and-multi-agent-systems","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"agnt","sideBox":"Learn more about [Autonomous Agents and Multi-Agent Systems](http://link.springer.com/journal/10458)","snPcode":"10458","submissionUrl":"https://submission.nature.com/new-submission/10458/3","title":"Autonomous Agents and Multi-Agent Systems","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"4faf4e91-352b-4685-8391-82ecaca918b9","owner":[],"postedDate":"March 4th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-03-03T16:05:43+00:00","versionOfRecord":{"articleIdentity":"rs-3992095","link":"https://doi.org/10.1007/s10458-025-09696-7","journal":{"identity":"autonomous-agents-and-multi-agent-systems","isVorOnly":false,"title":"Autonomous Agents and Multi-Agent Systems"},"publishedOn":"2025-02-26 15:57:57","publishedOnDateReadable":"February 26th, 2025"},"versionCreatedAt":"2024-03-04 05:41:28","video":"","vorDoi":"10.1007/s10458-025-09696-7","vorDoiUrl":"https://doi.org/10.1007/s10458-025-09696-7","workflowStages":[]},"version":"v1","identity":"rs-3992095","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3992095","identity":"rs-3992095","version":["v1"]},"buildId":"7rjqhiLT3MXkJMwkYKINL","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}