{"entities":{"Q1187025":{"pageid":1197774,"ns":120,"title":"Item:Q1187025","lastrevid":46253728,"modified":"2025-12-24T10:06:44Z","type":"item","id":"Q1187025","labels":{"en":{"language":"en","value":"The complexity of stochastic games"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 37521"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$44C804BB-39C0-4AF4-9D5C-51ADB432B7E2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a771cfea32391683775eb9d07e36c5ccfbfe048d","datavalue":{"value":{"text":"The complexity of stochastic games","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1187025$E5708E83-0F2F-4F00-B479-1ACFC6AE4310","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"04ba01fdf5b8affb3cb79b6da4973b3e898b90c5","datavalue":{"value":"0756.90103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$B4016513-BA03-4D23-8C92-5ECAB9589C07","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a6347be2492c4db3a94ee180a5baa159fe86cd0d","datavalue":{"value":"10.1016/0890-5401(92)90048-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$1FBB7E25-0735-48F1-8665-743816A95555","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"afaa11cad02f935fe120c5b18653ba09260c4c57","datavalue":{"value":{"entity-type":"item","numeric-id":268445,"id":"Q268445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$95A5BA1D-E8B2-4573-9887-80A4DC4ACED4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$5ADB9794-8140-40B3-9646-9A7C658C3A31","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1187025$3BFFCEF1-4453-40D0-B15E-3287B1FB3110","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"243961d64db415f41f71125a1c35c9144888009d","datavalue":{"value":"We consider the complexity of a natural combinatorial problem, that of deciding the outcome of a special kind of stochastic game. We show that the problem of deciding which player has the greatest chance of winning the game is in the class \\(NP\\cap co-NP\\).   A simple stochastic game is a directed graph composed of max, min and average vertices. There is a special start vertex and two special sink vertices, called the 0-sink and the 1-sink. The graph models a game between two players, 0 and 1. Initially, a token is placed on the start vertex, and at each step, the token is moved from a vertex to one of its neighbors, according to the following rules. At a max (min) vertex, player 1 (0) chooses the neighbor to which the token is moved. At an average vertex, the token is moved to each neighbor of the average vertex with equal probability. The game ends when the token reaches a sink vertex; player 1 wins if it reaches the 1-sink vertex and player 0 wins otherwise.   Informally, a strategy for player 0 (1) is a rule that defines what move the player takes whenever the token is at a min (max) vertex. We consider the question: does player 1 win the game with probability \\(>1/2\\), if both players use their best strategies? Although many algorithms have been proposed for this problem, since the introduction of the model by Shapley in 1953, none are known to run in polynomial time. We show that this decision problem is in \\(NP\\cap co-NP\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187025$39AC2A71-2C96-472C-9F30-5BB19DF10658","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8f34675a74b150d19473221b06b085ebc8156162","datavalue":{"value":"91A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$791A1734-A06A-447C-9A05-BC3AB0BEAB42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$6AECBCDD-FDB1-4412-B587-81922DAF3B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"377d3ab03372cff12915e0de0374438ff70c3716","datavalue":{"value":"90C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$BFA3FAEE-4AAC-48FB-9575-10D80F9AC5FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$CD1B4193-60A9-4AD0-B4C7-CC5E9576184B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$DEF4409E-1F3E-450E-922E-60CBF8F1F4E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3efb64d5f7edbfbaf6f55d0f9bd63d8101d543a8","datavalue":{"value":"37521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$2C4F0EC9-9C17-4730-A97A-30DE538E1E78","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1f486a1cf8995707d9b5667417598aba1de3c742","datavalue":{"value":"Q29040293","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$946C4EC6-3195-42B3-B6FC-7C41A44E10A6","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$1D4A65B0-0028-4014-AAC8-06F3F61C21D4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$E9E93D0B-D8DB-494B-B6C5-834329963520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df043efb353d68dc496a2821da7cdba7270fc2d8","datavalue":{"value":{"entity-type":"item","numeric-id":1138490,"id":"Q1138490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$9D1C9E0D-5309-4249-8741-9EE8F159E2BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$B939DE3F-9E1C-4536-8D50-DAA8F5B917E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0459d1a93a135deb9a3f3404173b887fd894a7be","datavalue":{"value":{"entity-type":"item","numeric-id":3266141,"id":"Q3266141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$3A36A3BD-3616-4B7D-81AA-378447475F76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b117510b4422c184b3dc46595f4fe45ff7a79ad","datavalue":{"value":{"entity-type":"item","numeric-id":3262596,"id":"Q3262596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$D09FF10E-12DB-4C0F-903F-4A6B4C4A0DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$E6EC11E6-2119-4862-9E6A-43687C8C5335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba0e56df9db89377069ef2057d2ac5bcfceb74c1","datavalue":{"value":{"entity-type":"item","numeric-id":1069296,"id":"Q1069296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$40F91219-FA44-48BF-A756-9DECF480C1C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"891ff5adf1d23cc88c810c5dd0aa5fe20cf5ff86","datavalue":{"value":{"entity-type":"item","numeric-id":4723685,"id":"Q4723685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$96CE0017-9CBA-4591-83DE-285AC2D2DE22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17e0e65bc0258e3fb24301d38f9385a7e4dd4333","datavalue":{"value":{"entity-type":"item","numeric-id":5820908,"id":"Q5820908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187025$5EBB3E15-5008-42D1-A6D8-7B440F2A23ED","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"de9699b8afb2559a72f9a6bcf5d1356d204b521d","datavalue":{"value":"journals/iandc/Condon92","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187025$D3A388E4-F941-4651-A5BD-DC0F8F027A8B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42b85ef6737dc22749be705815e17f10786c97b6","datavalue":{"value":{"entity-type":"item","numeric-id":3652196,"id":"Q3652196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4b95940e051f8d8eabfe6d7c199cef1fe8a1294","datavalue":{"value":{"amount":"+0.8743738532066345","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1187025$9E035CF5-1E94-4258-83C4-C21C7127603B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f02aa17f51eda1b6728f0fa2afb951cf13826f7","datavalue":{"value":{"entity-type":"item","numeric-id":4287357,"id":"Q4287357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7a0e1196024ab7923a8714c3da2a846265cff32","datavalue":{"value":{"amount":"+0.8498342037200928","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1187025$D3286019-099E-442B-86DA-C5F88D5EFA3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ae38485f7e78d964fb4f75ad33804854c18b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":3563006,"id":"Q3563006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90bda4bd6216652d9e28bf070e3ec4516f2c619f","datavalue":{"value":{"amount":"+0.8459457159042358","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1187025$9C34FFD9-9D12-4B20-8BAA-11B77AB1F15D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb817d7a55a07c74f35ded89e3e32763ddb444c2","datavalue":{"value":{"entity-type":"item","numeric-id":635740,"id":"Q635740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"570d76516c724e46fb5797bc872cbd2fea099924","datavalue":{"value":{"amount":"+0.8435809016227722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1187025$F68276D7-D0A2-4B28-86C2-750740B300C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d1a14ee8cd47de403bfab3ba32c1a806998ad69","datavalue":{"value":{"entity-type":"item","numeric-id":1351468,"id":"Q1351468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30a771d727474dbe66b4f957fc72b9b478667bed","datavalue":{"value":{"amount":"+0.8432168364524841","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1187025$623895CA-2DD6-44D3-A33C-5F5706805DDE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1187025","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1187025"}}}}}