{"entities":{"Q933752":{"pageid":935600,"ns":120,"title":"Item:Q933752","lastrevid":65455404,"modified":"2026-04-12T02:43:20Z","type":"item","id":"Q933752","labels":{"en":{"language":"en","value":"Stochastic limit-average games are in EXPTIME"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5303990"}},"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":"Q933752$F75073AD-2773-42B4-A863-4CC893F155CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"07aa0e8ca5369bd10ca93e21e628de8a29066bb4","datavalue":{"value":{"text":"Stochastic limit-average games are in EXPTIME","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q933752$F70F8C07-71E2-4B0E-AA74-D2440561A703","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"587f2387a3d6b5f143b52e1418e252c951098ad4","datavalue":{"value":"1154.91004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933752$7BD042E0-9825-45CF-BB1E-A043BD4B6E40","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2cff81c72b46c2d37ebe9a5f2cbcfbb6825cbcc7","datavalue":{"value":{"entity-type":"item","numeric-id":253965,"id":"Q253965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$A6A25A6D-6C96-4905-93B1-D9B3EA890C19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd27e91c4471a6c2f2d14ef8212c1a71ddfcbbaf","datavalue":{"value":{"entity-type":"item","numeric-id":453531,"id":"Q453531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$86D197F5-96F7-43DE-9DAF-652BE9CFE8CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e91931f3fd780c36ea4328f78b3c3352f7c16650","datavalue":{"value":{"entity-type":"item","numeric-id":355505,"id":"Q355505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$F0A82864-0488-4CA0-9A3A-F0D551EB6329","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ef8712371e142c87c3e57daa1955918131611e11","datavalue":{"value":{"entity-type":"item","numeric-id":267073,"id":"Q267073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$D9ECB7E3-6FC2-462B-8367-5E2D114964C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cbc3e0fb8151dd740a5ce25448df0d3f7f728768","datavalue":{"value":{"time":"+2008-07-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q933752$3239A886-E4AC-43F1-BEA1-B92F46D6C2BC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d4edc791052d58dc97d11ab5922c0523eb20b672","datavalue":{"value":"https://arxiv.org/abs/0805.2622","type":"string"},"datatype":"url"},"type":"statement","id":"Q933752$A07447EB-343B-41A6-A42A-A4C79743F953","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2b8a03fb03c91e9f86536792f1ed82929cd71129","datavalue":{"value":"A repeated zero-sum stochastic game \\(G=(S,A,\\Gamma_1,\\Gamma_2, \\delta,r)\\) played by two players is considered. Here \\(S\\) and \\(A\\) are finite space of states and set of actions respectively, \\(\\Gamma_i(s) \\subseteq A\\), \\(i=1,2\\), \\(s \\in S\\), describe possible sets of actions of players at each state. If in the state \\(s\\) players choose actions \\(a\\) and \\(b\\) respectively then \\(\\delta(s,a,b)(t)\\) is a probability to reach the state \\(t\\) and \\(r(s,a,b)\\) is a real-valued reward of the first player. Strategies \\(\\sigma\\) and \\(\\pi\\) of players can depend on all known history of the game. The limit-average for the player 1 reward of a pair of strategies \\(\\sigma\\) and \\(\\pi\\) and a starting state \\(s\\) is defined as  \\[  v_1(s,\\sigma,\\pi)=E_s^{\\sigma, \\pi}\\left[ \\liminf_{n \\to \\infty} n^{-1} \\sum_{i=1}^n r(X_i,\\Theta_{i,1}, \\Theta_{i.2}) \\right],  \\]  where \\(X_i\\), \\(\\Theta_{i,1}\\), \\(\\Theta_{i.2}\\) stand for the state and chosen actions at instant of time \\(i\\).  In the article the computational complexity of approximating the value of the game is characterized. It is shown that for any given real \\(\\varepsilon >0\\) the value of a game \\(G\\) at a state \\(s\\) can be computed to within \\(\\varepsilon\\)-precision in time bounded by an exponential in a polynomial in the size of the game \\(G\\) times a polynomial function of \\(\\log 1/\\varepsilon\\). The main technique is the characterization of values as semi-algebraic quantities.","type":"string"},"datatype":"string"},"type":"statement","id":"Q933752$8F92F0EF-7F7F-486D-9F5B-9E15C2166A4E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"280f101b1c750c0ba69a260fa420e20feae2066a","datavalue":{"value":{"entity-type":"item","numeric-id":629779,"id":"Q629779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$65FDD9E5-CFC8-4DAF-BE29-53EE438D4A0F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8f34675a74b150d19473221b06b085ebc8156162","datavalue":{"value":"91A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933752$4E29B795-0A5A-499E-B69D-A35327E802DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d3874ff76a67dd04e6898b028cca42f0d5b6b017","datavalue":{"value":"5303990","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933752$10D83FAC-7CD4-48DB-A62A-8054059465B7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5946a51a5884d5e86db7472d96ff43e6ea9b65f","datavalue":{"value":"stochastic games","type":"string"},"datatype":"string"},"type":"statement","id":"Q933752$D279F471-FE1B-4A70-9624-D5246CC68BF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e44292649c2851290b5b6de7afb400c3383e38a","datavalue":{"value":"limit-average payoff","type":"string"},"datatype":"string"},"type":"statement","id":"Q933752$C3DC957C-7809-429D-BC6D-69D14AB51B2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q933752$83C92FBD-D1A6-4AF4-8C8A-0625484D0704","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":"Q933752$9C56C5EB-DF21-4D1E-92D6-245024D3A7B8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"05581f29a817399b3772b8ad7c409656e72a8404","datavalue":{"value":"W2018658986","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933752$B805DC65-313E-4D29-838C-005ADEB00F6E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e252b0603cec3a7f962e5b5f55184d47bfe852e","datavalue":{"value":{"entity-type":"item","numeric-id":3158549,"id":"Q3158549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$D75F47C9-7CA7-4F59-808B-B512E722911C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95127141592e878799f1620a9e20ee4ed2d5aea0","datavalue":{"value":{"entity-type":"item","numeric-id":5906950,"id":"Q5906950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$5A855EAF-22A8-41FF-A437-F5B6FAED8E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a08fb04a108ab8179c102cae98c498881a4c20a4","datavalue":{"value":{"entity-type":"item","numeric-id":3883572,"id":"Q3883572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$5F6F0B82-2823-4978-8A46-5A92E63B4B8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0f6ec25f30ab9877522a2e3dca26ed94fdebc69","datavalue":{"value":{"entity-type":"item","numeric-id":4141056,"id":"Q4141056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$BF294C25-A542-4C0B-9D0C-E91BF22B2878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dfc1b12c134d5031fdcccc00aae6344af4fb733","datavalue":{"value":{"entity-type":"item","numeric-id":5549547,"id":"Q5549547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$B59EAC65-1F84-457E-936D-E988B6040EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5142ee1d620d0b4118f77836a47316b18c6d1122","datavalue":{"value":{"entity-type":"item","numeric-id":4382287,"id":"Q4382287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$892581B3-F802-4722-8653-44B345634E65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"256c08df1a13e6cd99e1c82b5ab080bf3df32e25","datavalue":{"value":{"entity-type":"item","numeric-id":5510376,"id":"Q5510376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$C0F84D8D-0D72-4EF6-98E7-7C78AC4F5D3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b67ee9815f7ab3c8b2b4907677d99ca915d101b0","datavalue":{"value":{"entity-type":"item","numeric-id":1164622,"id":"Q1164622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$392F36AC-1612-4262-AA58-4E726ECC5CEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bd3fd08ef1df4f4fa915c4516b9a6eee17fd89b","datavalue":{"value":{"entity-type":"item","numeric-id":5588290,"id":"Q5588290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$33496051-E89F-412E-940E-7BA84AE0063F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51fe5409f112fc45f1b4f05d8f20234d11c4c937","datavalue":{"value":{"entity-type":"item","numeric-id":5905121,"id":"Q5905121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$F1C65C67-F538-42E7-B581-D4B74F0FB449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5075438a643ae2f69c5413e36cd9d2c522d024f0","datavalue":{"value":{"entity-type":"item","numeric-id":4437142,"id":"Q4437142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$4B06DB98-03F9-4574-BF47-75B9726A2416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$B083FDC5-1624-4903-878B-DDC6FEFED401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9af13e45efc0d0c02d968579d57310ccedfb5884","datavalue":{"value":{"entity-type":"item","numeric-id":1135219,"id":"Q1135219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$1F7A9485-1A33-4F72-B087-34A5F8E0CC7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72118b2bfd3309b966d02b0d911523710a400f09","datavalue":{"value":{"entity-type":"item","numeric-id":3984137,"id":"Q3984137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$1FF97B11-FF8F-4502-BC52-595532CADCA0","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":"Q933752$43957064-6F92-4854-AE61-662F9D3DF63E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3d63052cabe12ef2d176f0fddc6bc808c0b887c","datavalue":{"value":{"entity-type":"item","numeric-id":1426850,"id":"Q1426850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$97E82E38-875D-4773-8A44-3D287706BF35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8be9375a315209f41df1b38374a5e7e956d28bf","datavalue":{"value":{"entity-type":"item","numeric-id":5807665,"id":"Q5807665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$3C536F4A-8E5B-45D4-B910-C34B21670F4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"257b1d08d00265b4b9d7f1f76c094108a4e385a4","datavalue":{"value":{"entity-type":"item","numeric-id":1351468,"id":"Q1351468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933752$0863415F-6585-49D2-9424-A6F2778F209F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35480605798ab7f3dce93e756bcb290e56ac1a9c","datavalue":{"value":"10.1007/S00182-007-0110-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933752$BB283B43-42FB-493E-B9C9-9ED90D1A2E1F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6649e3c41b27475be84281ec958f96ff46d78da1","datavalue":{"value":{"entity-type":"item","numeric-id":3638081,"id":"Q3638081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d47c51e7409ef28238d9c258670bce583aea9198","datavalue":{"value":{"amount":"+0.8107796311378479","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":"Q933752$33445ED5-A06C-4E55-8492-42D4C64501AF","rank":"normal"},{"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":"17e000cf2c10379d439919b9e0c375ad00624d6a","datavalue":{"value":{"amount":"+0.8023796081542969","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":"Q933752$BAEC89F0-5DE7-4E2A-BF90-5AC587020C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1bf5468ee781cd2234d2b945bcd361fb8992497","datavalue":{"value":{"entity-type":"item","numeric-id":1755732,"id":"Q1755732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8947890851a7b999acb2928863237aee418de4b","datavalue":{"value":{"amount":"+0.7987154126167297","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":"Q933752$0F613AD8-C95B-4446-A87A-264D28117FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"622f44ed3f02e2a0c9dd818a882396a4da4281b3","datavalue":{"value":{"entity-type":"item","numeric-id":652540,"id":"Q652540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2c9f266693fbd32ec88edf7572c518e92211aba","datavalue":{"value":{"amount":"+0.7925258874893188","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":"Q933752$90B06C79-8E73-4CE2-A9D5-E390F23C4849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2063fc7a9e4761ddf2efdb8d26a092474d085bd","datavalue":{"value":{"entity-type":"item","numeric-id":5419090,"id":"Q5419090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b47a0a51cb5bd328b56a5cde3ac9cab0750d6e2","datavalue":{"value":{"amount":"+0.7916856408119202","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":"Q933752$5182A47A-7BAB-45DA-AB18-D425484AABC0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Stochastic limit-average games are in EXPTIME","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Stochastic_limit-average_games_are_in_EXPTIME"}}}}}