{"entities":{"Q372955":{"pageid":374722,"ns":120,"title":"Item:Q372955","lastrevid":51847343,"modified":"2026-01-20T08:24:41Z","type":"item","id":"Q372955","labels":{"en":{"language":"en","value":"On the complexity of Pareto-optimal Nash and strong equilibria"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6217429"}},"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":"Q372955$6987B825-1A2F-4C3F-A376-0B51FBA3B2E1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"73f2abef024ac3049e59e8c50a9b92d094623f72","datavalue":{"value":{"text":"On the complexity of Pareto-optimal Nash and strong equilibria","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q372955$8B7B1451-727C-4070-82B2-638BBC6D0237","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e139a09fab98d73b013775ac38f424b343e35ab","datavalue":{"value":"1282.91025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q372955$24959D30-CE4A-40B4-8411-FA277C9D56D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"89dd81a1300d67daad8256b210b757bca65d1a83","datavalue":{"value":{"entity-type":"item","numeric-id":287989,"id":"Q287989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$BC6C0959-433E-4B89-9BDE-2D99DCA29F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"937c27b26047023981de2a93f9da3edc1517f5ae","datavalue":{"value":{"entity-type":"item","numeric-id":372954,"id":"Q372954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$11850F49-9B57-43AE-AFF4-7BC4998D1F22","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$2902E127-20BA-409C-B8A6-8675C9E410A7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"06bdca2898df413a78f8d2cdbb7311760f3e2760","datavalue":{"value":{"time":"+2013-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q372955$6C8159DC-F56F-436D-BCA6-8B4D9FF03007","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd1de69dcd683c71e7c08dfe4a08977f0e178d49","datavalue":{"value":"The authors consider computational complexity of strong and Pareto-optimal Nash equilibria in some classes of noncooperative games. First they show that a recognition task is polynomial for anonymous games, but the existence is NP-hard. The algorithm is based on a perfect matching scheme. It is shown that the recognition and computation task are polynomial for the special class of player-specific singleton congestion games, but existence and recognition are NP-hard in general congestion games.","type":"string"},"datatype":"string"},"type":"statement","id":"Q372955$C3CBD353-AA04-4269-A01A-03E50DFAE22B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b981544e2f372881d1f9988ce185eacb08cab83f","datavalue":{"value":{"entity-type":"item","numeric-id":400024,"id":"Q400024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$A5E9F260-737A-4531-8EAF-5F05CD3C6539","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7dd7003e1269b5b10ff3f935da8af9e44f172f","datavalue":{"value":"91A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q372955$1CFC6017-DCD9-4150-BD93-C648716AAC1D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"597aaab51ebffadf67b377296bac2034fe7f661b","datavalue":{"value":"6217429","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q372955$23F582DE-AF40-4CB8-9906-6188BFCD0813","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c4097a447714ddda65a2c1097151b892465640c","datavalue":{"value":"noncooperative games","type":"string"},"datatype":"string"},"type":"statement","id":"Q372955$AA6C0B30-4F4D-4714-AD37-FD558FAA543E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53dde8b387b5cd23f4abb2e117e873f60004406d","datavalue":{"value":"Nash equilibrium","type":"string"},"datatype":"string"},"type":"statement","id":"Q372955$05DCAFD8-7A7B-41B9-A6A0-E98B95796214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f4c5726e423dcbdd0a2ab5f9677f285a14fdc98","datavalue":{"value":"strong equilibrium","type":"string"},"datatype":"string"},"type":"statement","id":"Q372955$D8BCC135-F311-4455-9A0E-4C698A250B6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ecbf857a620dd6b37baa28f795dfddaa90e8b7d","datavalue":{"value":"Pareto optimality","type":"string"},"datatype":"string"},"type":"statement","id":"Q372955$E2DD122D-1F63-42ED-8046-C52C74B4933A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q372955$47D1F55D-9B0D-4C6E-8195-CBD8DD8FFA8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"918ab5403dbcba5f7d14066d3d4f6ff46892a293","datavalue":{"value":"congestion games","type":"string"},"datatype":"string"},"type":"statement","id":"Q372955$C5D51A3A-E73B-42D7-B1A9-5113B0597448","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":"Q372955$447B712C-D626-4542-933D-26C1E37FEC11","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba8a2dfd83b0f66ae4fb115de739fd23e9253a4d","datavalue":{"value":"https://doi.org/10.1007/s00224-012-9433-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q372955$33856E6F-DAC8-4128-A0D0-7A545638343D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"17203238cfb1da3124269937d19c4418ba6649b4","datavalue":{"value":"W2034471979","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q372955$3892EFB1-E3B4-4A7D-ACEC-E712BB226248","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4278bbf7df30d69247c30a18b3a1df089733eab9","datavalue":{"value":{"entity-type":"item","numeric-id":3452191,"id":"Q3452191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$26F8702B-3E92-4A95-BF60-EEB800E8723E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aa01a0440fe8709d9f219ff7f8175fd47dfd3e6","datavalue":{"value":{"entity-type":"item","numeric-id":1007765,"id":"Q1007765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$9D5902E5-D8C7-4D82-8EBB-EDAB782CC601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84b608baed09213cad2be194cc4c3228326ab1bd","datavalue":{"value":{"entity-type":"item","numeric-id":3254691,"id":"Q3254691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$D66CA00E-478A-4E68-9F13-6A9A5DB9680A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"431ea0a73bb35c60da8ba1661da4fa5e6ed8dc49","datavalue":{"value":{"entity-type":"item","numeric-id":1304003,"id":"Q1304003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$25A39783-938B-426B-AA24-912D0D5CEB70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f8ccae462ab59af90a7f2e6bcbfb9caacb371cb","datavalue":{"value":{"entity-type":"item","numeric-id":1587389,"id":"Q1587389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$28BCF753-5C4D-4A58-AA86-49A17412F3BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9847d286a03eff2fd4e5920b178013563ed289a8","datavalue":{"value":{"entity-type":"item","numeric-id":1004282,"id":"Q1004282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$65A0D004-B9E6-45A9-9E79-84F60E6DE842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca22d0018f3ed84480a79599a3a3dc00e7202337","datavalue":{"value":{"entity-type":"item","numeric-id":3638041,"id":"Q3638041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$D2FE02D4-7A3D-40D3-8A75-E96E3440BA56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18ca557ffa948eff186873f7b40dc667c9db0b93","datavalue":{"value":{"entity-type":"item","numeric-id":3168999,"id":"Q3168999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$5A35D3C0-05FF-4B2B-9811-700E382FAC65","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":"Q372955$39A9728C-26C3-4B86-9A35-8145E296FD85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41028dcf75ec00365cda807a56f011e263e0ca38","datavalue":{"value":{"entity-type":"item","numeric-id":5428841,"id":"Q5428841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$4484BADA-667F-4FAD-A860-0BB339939BE2","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":"Q372955$C72A0C43-EFCD-4580-A819-D0859D12D531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4b852d963168139ef185a209a725614ce44125c","datavalue":{"value":{"entity-type":"item","numeric-id":3586381,"id":"Q3586381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$C728A42C-E638-4D2A-ABBB-763D12EB872E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90ff8a0deb80b62b252ea02bd6ad4274de5f38b9","datavalue":{"value":{"entity-type":"item","numeric-id":3162529,"id":"Q3162529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$A1B3FBFA-A0D7-409B-A199-44767EB2853E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dfd98e0491ea2f4b7c6f35c23df1d88f3885fc4","datavalue":{"value":{"entity-type":"item","numeric-id":1378018,"id":"Q1378018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$42E1BF3D-F455-4970-B2C6-3BC6CC8312FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"628cad6ff082229f83e8c0b2127fd77397dd3af2","datavalue":{"value":{"entity-type":"item","numeric-id":1363532,"id":"Q1363532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$5AF771D0-7B61-413E-8FBD-A7E6F8845E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9061c5f8e928b165b3a3647aa8899a7c971be11b","datavalue":{"value":{"entity-type":"item","numeric-id":4902563,"id":"Q4902563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$69C5692E-3381-4500-80E6-192306F13705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23f53f4ede8d28e2585c34919c7af03716c36170","datavalue":{"value":{"entity-type":"item","numeric-id":1915710,"id":"Q1915710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$6D76FE1F-3CF2-4230-9094-195A18003281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee2f9a101ae5b6d241bbadf1b9c2d9104f25e6a5","datavalue":{"value":{"entity-type":"item","numeric-id":2560099,"id":"Q2560099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q372955$8C8638C9-4B7A-48E2-9E70-18928ED05CFD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4f21f44eb89adcf3b73a14fe3c351ba288e5427b","datavalue":{"value":"10.1007/S00224-012-9433-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q372955$5F54BABD-8A1D-43CC-8733-D12CBFBC7909","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"330ca1be22d4152036ed751c0dfa8638f6c82fa2","datavalue":{"value":{"entity-type":"item","numeric-id":3162529,"id":"Q3162529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af38022c918148a25a1f7ab2e415dc3d875c4147","datavalue":{"value":{"amount":"+1.0000001192092896","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":"Q372955$298271A9-BDB3-4892-9106-E69B9A8263F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b1f6c009fd26ff6ee24f578103f50837981c6e8","datavalue":{"value":{"entity-type":"item","numeric-id":3638041,"id":"Q3638041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3028138315299f74b2989e3e756df83fd895ab2e","datavalue":{"value":{"amount":"+0.8299184441566467","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":"Q372955$BBD84899-B2AD-493C-89F5-D1FFBDEB96DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24dff096985d9fea1c7a7d6a15103e5523ed6844","datavalue":{"value":{"entity-type":"item","numeric-id":4962757,"id":"Q4962757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"178867efb461a18c3d086c81355bdc1b732c3924","datavalue":{"value":{"amount":"+0.819433331489563","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":"Q372955$68EE30B6-BDC6-4690-9A3C-BD42EAC73C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"363bcac8bbba61932b3e105da539f6168e643345","datavalue":{"value":{"entity-type":"item","numeric-id":3162508,"id":"Q3162508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97128d5c4128f15a5c88838b83f20c83cc635f8d","datavalue":{"value":{"amount":"+0.8192323446273804","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":"Q372955$722ECFFC-D27F-49FD-B0A9-F2BF6A13CDC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4673eee6670d1ea161352aa0186878a0173bc6cd","datavalue":{"value":{"entity-type":"item","numeric-id":378094,"id":"Q378094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02e5c56a0073610b98ee7e02a9d79f0744d7dc2a","datavalue":{"value":{"amount":"+0.8192087411880493","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":"Q372955$E5188A8B-0A0F-499F-8797-85244DDCDB9E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:372955","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:372955"}}}}}