Fashion game on graphs with more than two actions

Qi Wang and Wensong Lin ()
Additional contact information
Qi Wang: Southeast University
Wensong Lin: Southeast University

Journal of Combinatorial Optimization, 2024, vol. 48, issue 4, No 9, 18 pages

Abstract: Abstract We study the fashion game, a classical network coordination/anti-coordination game employed to model social dynamics in decision-making processes, especially in fashion choices. In this game, individuals, represented as vertices in a graph, make decisions based on their neighbors’ choices. Some individuals are positively influenced by their neighbors while others are negatively affected. Analyzing the game’s outcome aids in understanding fashion trends and flux within the population. In an instance of the fashion game, an action profile is formed when all individuals have made their choices. The utility of an individual under an action profile is defined according to the choices he and his neighbors made. A pure Nash equilibria is an action profile under which each individual has a nonnegative utility. To further study the existence of pure Nash equilibria, we investigate an associated optimization problem aimed at maximizing the minimal individual utility, referred to as the utility of a fashion game instance. The fashion game with two different but symmetric actions (choices) has been studied extensively in the literature. This paper seeks to extend the fashion game analysis to scenarios with more than two available actions, thereby enhancing comprehension of social dynamics in decision-making processes. We determine the utilities of all instances on paths, cycles and complete graphs. For instances where each individual likes to anti-coordinate, graph is planar and three actions are available, we illustrate the time complexity of determining the utility of such instances. Additionally, for instances containing both coordinating and anti-coordinating individuals, we extend the results on the time complexity of determining the utility of instances with two available actions to cases with more than two actions.

Keywords: Fashion game; Utility; t-satisfiability problem; Complete graphs; Planar graphs; NP-completeness (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01225-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:4:d:10.1007_s10878-024-01225-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01225-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().