Logo
Munich Personal RePEc Archive

A Sufficient Condition for Weakly Acyclic games with Applications

zhao, guo and Chai, Yingming (2024): A Sufficient Condition for Weakly Acyclic games with Applications.

[thumbnail of MPRA_paper_120789.pdf]
Preview
PDF
MPRA_paper_120789.pdf

Download (342kB) | Preview

Abstract

The class of weakly acyclic games captures many practical application domains, and is particularly relevant for multi-agent distributed control problems. However, reliably checking weak acyclicity is extremely computationally intractable (PSPACE-complete) in the worst case. The present paper identifies sufficient conditions for weak acyclicity by means of the transitive closure of individual conditional preference, which can be constructed in terms of better-reply improvement paths. This pure-ordinal approach leads to a novel connection between weak acyclic games and better-reply secure games. Specifically, a better-reply secure game is weakly acyclic if the better reply dynamics does not possess a dense orbit (in addition to the quasi-concavity of individual preferences as well as the usual convexity and compactness assumptions on strategy sets). These results give a partial answer to an open problem of finding applicable and tractable conditions for weak acyclicity, posed by Fabrikant, Jaggard, and Schapira in 2013.

Atom RSS 1.0 RSS 2.0

Contact us: mpra@ub.uni-muenchen.de

This repository has been built using EPrints software.

MPRA is a RePEc service hosted by Logo of the University Library LMU Munich.