{"id":756,"date":"2024-09-16T10:02:28","date_gmt":"2024-09-16T10:02:28","guid":{"rendered":"https:\/\/www.ccor.hu\/?p=756"},"modified":"2024-09-16T10:02:28","modified_gmt":"2024-09-16T10:02:28","slug":"corvinus-game-theory-seminar-24","status":"publish","type":"post","link":"http:\/\/www.ccor.hu\/?p=756","title":{"rendered":"Corvinus Game Theory Seminar"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Sep. 19 (14:30-15:30) room&nbsp;<\/strong><strong>C.714<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>P\u00e9ter Bir\u00f3, Gergely Cs\u00e1ji&nbsp;<\/strong>(HUN-REN KRTK-KTI)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Ex-post stability under two-sided matching: Complexity and characterization<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">A probabilistic approach to the stable matching problem has been identified as an important research area with several important open problems. When considering random matchings, ex-post stability is a fundamental stability concept. A prominent open problem is characterizing ex-post stability and establishing its computational complexity. We investigate the computational complexity of testing ex-post stability. Our central result is that when either side has ties in the preferences\/priorities, testing ex-post stability is NP-complete. The result even holds if both sides have dichotomous preferences. On the positive side, we give an algorithm using an integer programming approach, that can determine a decomposition with a maximum probability of being weakly stable. We also consider stronger versions of ex-post stability (in particular robust ex-post stability and ex-post strong stability) and prove that they can be tested in polynomial time.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The talk is based on joint work with Haris Aziz \u00e9s Ali Pourmiri (UNSW Sydney).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Sep. 19 (14:30-15:30) room&nbsp;C.714 P\u00e9ter Bir\u00f3, Gergely Cs\u00e1ji&nbsp;(HUN-REN KRTK-KTI) Ex-post stability under two-sided matching: Complexity and characterization A probabilistic approach to the stable matching problem has been identified as an important research area with several important open problems. When considering <span class=\"readmore\"><a href=\"http:\/\/www.ccor.hu\/?p=756\">Continue Reading &#8230;<\/a><\/span><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-756","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/posts\/756","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=756"}],"version-history":[{"count":1,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/posts\/756\/revisions"}],"predecessor-version":[{"id":757,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/posts\/756\/revisions\/757"}],"wp:attachment":[{"href":"http:\/\/www.ccor.hu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=756"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=756"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=756"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}