{"entities":{"Q935157":{"pageid":937005,"ns":120,"title":"Item:Q935157","lastrevid":65493471,"modified":"2026-04-12T02:59:04Z","type":"item","id":"Q935157","labels":{"en":{"language":"en","value":"The complexity of uniform Nash equilibria and related regular subgraph problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5306537"}},"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":"Q935157$DA292A6E-E4F8-43BF-82C3-615DB0132483","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c451e366fcaf6ab59e20fb71b5a368d8d42263bb","datavalue":{"value":{"text":"The complexity of uniform Nash equilibria and related regular subgraph problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q935157$C1B1833C-5C20-4D5A-B090-A2B605DD71CF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0925cf7e7349f6bbf1ed14d54d8c1e1fa9f18c11","datavalue":{"value":"1153.91006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q935157$F04D7E3A-C32D-4EFA-9B11-3E1E70CC7262","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8fe76713946a2857353ce8f60daef41c82a44748","datavalue":{"value":{"entity-type":"item","numeric-id":255295,"id":"Q255295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$8EED0C07-E145-4092-8973-25D22E8D5D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"98267b942c325f954f275b4e9b0b6604a3265ec1","datavalue":{"value":{"entity-type":"item","numeric-id":935156,"id":"Q935156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$58DF96F3-2383-4181-A4B4-A718B6880C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"04d1d66dbdfd54898c2352793c10b49dbcd7ff94","datavalue":{"value":{"entity-type":"item","numeric-id":270021,"id":"Q270021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$7B064A81-C2FB-45F7-93D7-6E2C4C319CBE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$7FB5418B-0961-47CC-AFA6-48D3A1489BF5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8d7bf80e07847c0b262029f7e143cabd4beaa66d","datavalue":{"value":{"time":"+2008-07-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q935157$3AE21CD9-F916-40E7-9601-85F0B85B9F37","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"93f1ce825d2552c72ba50375aaaf68fd28e95203","datavalue":{"value":"The complexity of finding uniform Nash equilibria is investigated. A Nash equilibrium is uniform if, for each player, all the strategies played with non-zero probability are assigned the same probability. It is shown that, even for a restricted class of win-lose bimatrix games, deciding the existence of such uniform equilibria is an NP-complete problem. The proof is graph-theoretical. As a related result it is shown that it is NP-complete to decide if a graph has an induced regular subgraph of large size or regularity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q935157$64171FEB-3263-49E2-B299-FCBB562489B3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c82436212510eb3fd57a05c9debac7e41dff5f00","datavalue":{"value":{"entity-type":"item","numeric-id":226578,"id":"Q226578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$59751120-8AC4-4D14-B34B-F0D9AE5C093B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7dd7003e1269b5b10ff3f935da8af9e44f172f","datavalue":{"value":"91A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q935157$A253CD65-0718-4944-A422-FC4C0DB6D91D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q935157$3BF40A03-C6B5-42D2-AAB5-0F807684EAD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b62273aea3375cefac54cd8688def5a3b6704b92","datavalue":{"value":"91A46","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q935157$CF48EAC4-0911-4C12-AB70-20CA22A4B894","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c27357d6aafec39d5f8f240d9f2be669fc61d5e5","datavalue":{"value":"5306537","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q935157$91C4EBB0-FE8A-4954-964C-8211077F1121","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q935157$E77D31B0-62EA-4EB7-890D-3CC660B12FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q935157$81108B0A-ED85-4333-856A-D0E482052565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93fa2c1b47722d5c294e7b1d30744aaa9f219c65","datavalue":{"value":"uniform Nash equilibrium","type":"string"},"datatype":"string"},"type":"statement","id":"Q935157$3E66A035-F184-41D7-AD78-1F17AD7A501A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c2300cc050a2fd54ce613f2ebeb8a9316619d11","datavalue":{"value":"regular induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q935157$62F66D2D-82C5-40D1-BC31-7FC3D46C7374","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":"Q935157$C9AB74A1-C836-41AD-92B4-3842F05564E7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c60d30714d2da4ef18542eb2011e420961cb3ca1","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2008.03.036","type":"string"},"datatype":"url"},"type":"statement","id":"Q935157$10B9ABDE-1214-480F-9162-08D78475F147","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"764ab96a7e69a74143f6a70091dd1e7e969d8932","datavalue":{"value":"W2149624304","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q935157$E215C3DA-D7F0-48F1-9AAC-BA64ED785CF5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0beb599d2e17bb8c532f90f8352be15f1767ebd","datavalue":{"value":{"entity-type":"item","numeric-id":5301416,"id":"Q5301416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$EE310A2D-6F59-4374-B695-68A73CA740B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8185ccda6708ef8733e7bebf33a7ddf86b23cf82","datavalue":{"value":{"entity-type":"item","numeric-id":5492928,"id":"Q5492928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$0E0A8B98-5D99-4E0E-B048-463D3B30B713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e8ec56905d2f0133cf929d8791aad7f052fad6b","datavalue":{"value":{"entity-type":"item","numeric-id":2426653,"id":"Q2426653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$D7DD7BF0-214A-4C65-A438-79E60D9BD540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99aa876e63b75442b0310c60d82815f7aefbc80f","datavalue":{"value":{"entity-type":"item","numeric-id":5449531,"id":"Q5449531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$7548D594-5B4F-46C0-8B2B-02B38D0A61EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de89bda030186089feadfd6e7d3077b1d4ce0e58","datavalue":{"value":{"entity-type":"item","numeric-id":1041739,"id":"Q1041739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$96C48CDC-A266-46CD-9F4C-984A318CC537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c085326ad7efa761d702052ae45772ed294782d","datavalue":{"value":{"entity-type":"item","numeric-id":932810,"id":"Q932810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$8AE08162-4523-4BA6-BA05-4339F374E8A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3afdee806199444072e3f972bb2fc9312ffe1281","datavalue":{"value":{"entity-type":"item","numeric-id":2931371,"id":"Q2931371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$6C4D3D7B-A652-47F3-ABD6-30373BFB38E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6adc018b390e0f0cc028634d4d999a55c0fd8988","datavalue":{"value":{"entity-type":"item","numeric-id":3580952,"id":"Q3580952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$6F7C0F98-38E1-44B7-AB03-77BCAA71514C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5e5bd18b456670d066598f219d6e5b72a14a969","datavalue":{"value":{"entity-type":"item","numeric-id":1191824,"id":"Q1191824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$921FF23D-7A9B-443D-8EC5-416249C81271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"039676149d0c369e700dbcea704c1ce84cf49753","datavalue":{"value":{"entity-type":"item","numeric-id":2931370,"id":"Q2931370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$AADEA602-21C6-449A-8CDA-72D30E00356C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62ec8ba4d552a02542482dfa4aa78c5e126bfa67","datavalue":{"value":{"entity-type":"item","numeric-id":5715720,"id":"Q5715720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$3376AF4A-24AE-4153-B037-FBDB073F921C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da94934fd9b85d14e1e5c1050a56b7763d7ef04b","datavalue":{"value":{"entity-type":"item","numeric-id":5385981,"id":"Q5385981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$540D6B73-274E-4A82-AA60-B74B8313E763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb0e137e137d67cf21dfa60890f8ec3ac67746d","datavalue":{"value":{"entity-type":"item","numeric-id":5402566,"id":"Q5402566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$D8D8AD4B-37F6-4EEE-B70E-66C85E4390F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"147b1e094b81d14fc66f2f6c2e25e4a2209bc718","datavalue":{"value":{"entity-type":"item","numeric-id":5897862,"id":"Q5897862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$34C8592D-85C9-49BD-9E6E-98409C768166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a35ee073efb257c2ff6944a7cc91fcd0fe8bb82","datavalue":{"value":{"entity-type":"item","numeric-id":1329155,"id":"Q1329155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$CEAC458E-2239-48AB-B12A-98F5DB69FA18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad494f00e9e528af13f8e1063881b009113ba5ca","datavalue":{"value":{"entity-type":"item","numeric-id":5901104,"id":"Q5901104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$9B63E1C7-AC71-4CC1-84C4-E338C26D3E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53931acda4d1de6fffc8c785b472a64b77dbbda9","datavalue":{"value":{"entity-type":"item","numeric-id":5402565,"id":"Q5402565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q935157$91AA8A38-FBF3-4E1B-B959-F5AB8E3F7009","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c373faf214d00e0cf2ac136ccfcb4d3b9230b60a","datavalue":{"value":"10.1016/J.TCS.2008.03.036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q935157$3A79E7BD-9378-499A-B1D7-EEBA0F725D43","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f58f78c6374d648b9cdff4c11f07db6147a1eee9","datavalue":{"value":{"entity-type":"item","numeric-id":5492928,"id":"Q5492928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b8cccb8d4e74be49a2811980438a30b178b037c","datavalue":{"value":{"amount":"+0.9451002478599548","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":"Q935157$8D8EAFED-606E-4D0E-A892-A7F2BBB34535","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fc97fd920f13c9903be957fccf805ce57449f4a","datavalue":{"value":{"entity-type":"item","numeric-id":932810,"id":"Q932810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d372564f587549632e1d424a70e37d1c9387cde","datavalue":{"value":{"amount":"+0.8217737674713135","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":"Q935157$FAE297FE-ECD7-4D73-B18C-68B5E9A99F33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d61dae97ae28571eeb7e722d783452099c3e1268","datavalue":{"value":{"entity-type":"item","numeric-id":4910930,"id":"Q4910930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d94e86dcf07341cb260f0373ce533f0161f9f9e1","datavalue":{"value":{"amount":"+0.8154184818267822","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":"Q935157$1E858E4B-226F-4E2E-8BD3-741D8588D63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"957589e64d96acf6b22c8fbe5c334da93d516cf0","datavalue":{"value":{"entity-type":"item","numeric-id":5715720,"id":"Q5715720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"307f42bff0b10802344c27f31d5690ddab26ecdb","datavalue":{"value":{"amount":"+0.8112073540687561","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":"Q935157$694F061E-95DF-4F3C-AF31-6E1D77272745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f96fc6a74ad09e2444ac1087019f41fb61e444e","datavalue":{"value":{"entity-type":"item","numeric-id":2931371,"id":"Q2931371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cba514f2e6a6541f6bcb765b1ce4bd345022dc25","datavalue":{"value":{"amount":"+0.8110490441322327","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":"Q935157$53C6EF9E-47D2-4601-AABB-DD39BFD9CF7D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of uniform Nash equilibria and related regular subgraph problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_uniform_Nash_equilibria_and_related_regular_subgraph_problems"}}}}}