DocumentCode
3312879
Title
On the complexity of three-player snort played on complete graphs
Author
Cincotti, Alessandro
Author_Institution
Sch. of Inf. Sci., Japan Adv. Inst. of Sci. & Technol., Nomi, Japan
fYear
2009
fDate
8-11 Aug. 2009
Firstpage
68
Lastpage
70
Abstract
Snort is a map-coloring game invented by Simon Norton where to establish who has a winning strategy on a general graph is a PSPACE-complete problem. Three-player snort is a three-player version of snort where cooperation between players is a key-factor to determine the winning coalition. In this paper, we show that three-player snort played on complete graphs, that is extremely easy to solve in normal play convention, becomes an NP-complete problem in misegravere play convention.
Keywords
game theory; graph colouring; PSPACE-complete problem; complete graph; map-coloring game; three-player snort; Game theory; Information science; Law; Legal factors; Mathematics; Paints;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Science and Information Technology, 2009. ICCSIT 2009. 2nd IEEE International Conference on
Conference_Location
Beijing
Print_ISBN
978-1-4244-4519-6
Electronic_ISBN
978-1-4244-4520-2
Type
conf
DOI
10.1109/ICCSIT.2009.5234614
Filename
5234614
Link To Document