{"id":5233,"date":"2025-03-22T00:19:20","date_gmt":"2025-03-21T15:19:20","guid":{"rendered":"https:\/\/saraheee.com\/?p=5233"},"modified":"2025-03-24T00:25:57","modified_gmt":"2025-03-23T15:25:57","slug":"gt-mechanism-6-myerson-satterthwaite-theorem","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2025\/03\/gt-mechanism-6-myerson-satterthwaite-theorem\/","title":{"rendered":"[GT Mechanism] #6. Myerson-Satterthwaite Theorem"},"content":{"rendered":"

GTO2-3-06: Myerson-Satterthwaite Theorem<\/h3>\n\n\n\n

\uc774 \uc601\uc0c1\uc740 Myerson-Satterthwaite \uc815\ub9ac\uc5d0 \ub300\ud574 \uc124\uba85\ud55c\ub2e4. \uc774 \uc815\ub9ac\ub294 \ud6a8\uc728\uc801\uc778 \uac70\ub798\ub97c \ub2ec\uc131\ud558\ub294 \ub370 \uc788\uc5b4 \uc790\ubc1c\uc801 \ucc38\uc5ec\uc640 \uc778\uc13c\ud2f0\ube0c \uc815\ub82c\uc758 \uc5b4\ub824\uc6c0\uc744 \ub2e4\ub8e8\uace0 \uc788\ub2e4.<\/p>\n\n\n\n

\n\n\n\n

\uac70\ub798 \uc0c1\ud669\uacfc \ubb38\uc81c \uc81c\uae30<\/h4>\n\n\n\n

\uac04\ub2e8\ud55c \uac70\ub798 \uc0c1\ud669\uc744 \uace0\ub824\ud558\uc790.
\ud310\ub9e4\uc790\ub294 \uc5b4\ub5a4 \ubb3c\uac74\uc744 \uac00\uc9c0\uace0 \uc788\uc73c\uba70, \uadf8 \uac00\uce58\ub97c \\([0, 1]\\) \ubc94\uc704\uc758 \uac12 \\(\u03b8_S\\)\ub85c \ub098\ud0c0\ub0b8\ub2e4.
\uad6c\ub9e4\uc790\ub3c4 \uadf8 \ubb3c\uac74\uc5d0 \ub300\ud574 \\([0, 1]\\) \ubc94\uc704\uc758 \uac00\uce58 \\(\u03b8_B\\)\ub97c \uac00\uc9c4\ub2e4.<\/p>\n\n\n\n

\uc774\ub54c, \\(\u03b8_B > \u03b8_S\\)\uc778 \uacbd\uc6b0 \uac70\ub798\uac00 \ud6a8\uc728\uc801\uc774\uba70, \uadf8\ub807\uc9c0 \uc54a\uc73c\uba74 \uac70\ub798\uac00 \uc774\ub8e8\uc5b4\uc9c0\uc9c0 \uc54a\ub294 \uac83\uc774 \ubc14\ub78c\uc9c1\ud558\ub2e4. \uadf8\ub7ec\ub098 \uac01\uc790\uc758 \uac00\uce58 \ud3c9\uac00\uac00 \uc0ac\uc801\uc778 \uc815\ubcf4\uc774\ubbc0\ub85c, \ud6a8\uc728\uc801\uc778 \uac70\ub798\ub97c \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uac00 \uc5b4\ub835\ub2e4.<\/p>\n\n\n\n

\n\n\n\n

\uc608\uc2dc<\/h4>\n\n\n\n

\uad6c\uccb4\uc801\uc778 \uc608\ub85c, \uad6c\ub9e4\uc790\uc758 \uac00\uce58\ub294 0.1 \ub610\ub294 1, \ud310\ub9e4\uc790\uc758 \uac00\uce58\ub294 0 \ub610\ub294 0.9\ub85c \uac00\uc815\ud558\uc790.
\uac00\ub2a5\ud55c \uc870\ud569\uc740 (0.1, 0), (0.1, 0.9), (1, 0), (1, 0.9)\uc758 \ub124 \uac00\uc9c0\uc774\ub2e4.
\uc774 \uc911 (0.1, 0.9)\ub97c \uc81c\uc678\ud55c \uc138 \uacbd\uc6b0\uc5d0\ub294 \uad6c\ub9e4\uc790\uc758 \uac00\uce58\uac00 \ud310\ub9e4\uc790\uc758 \uac00\uce58\ubcf4\ub2e4 \ub192\uc73c\ubbc0\ub85c \uac70\ub798\uac00 \ud6a8\uc728\uc801\uc774\ub2e4.
\uadf8\ub7ec\ub098 (0.1, 0.9)\uc5d0\uc11c\ub294 \uac70\ub798\uac00 \ube44\ud6a8\uc728\uc801\uc774\ub2e4.<\/p>\n\n\n\n

\n\n\n\n

\uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc758 \uc5b4\ub824\uc6c0<\/h4>\n\n\n\n

\ud310\ub9e4\uc790\uac00 \uac00\uaca9\uc744 \uc81c\uc2dc\ud558\uace0 \uad6c\ub9e4\uc790\uac00 \uc774\ub97c \uc218\ub77d\ud558\uac70\ub098 \uac70\uc808\ud558\ub294 \ub2e8\uc21c\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uace0\ub824\ud558\uc790.
\ud310\ub9e4\uc790\ub294 \uc790\uc2e0\uc758 \uc774\uc775\uc744 \uadf9\ub300\ud654\ud558\uae30 \uc704\ud574 \ub192\uc740 \uac00\uaca9\uc744 \uc124\uc815\ud558\ub824 \ud560 \uac83\uc774\uba70, \uc774\ub294 \ub0ae\uc740 \uac00\uce58\uc758 \uad6c\ub9e4\uc790\uac00 \uac70\ub798\ub97c \ud3ec\uae30\ud558\uac8c \ub9cc\ub4e4\uc5b4 \ud6a8\uc728\uc801\uc778 \uac70\ub798\ub97c \ubc29\ud574\ud55c\ub2e4.
\ubc18\ub300\ub85c \ub0ae\uc740 \uac00\uaca9\uc744 \uc124\uc815\ud558\uba74 \ub192\uc740 \uac00\uce58\uc758 \uad6c\ub9e4\uc790\ub3c4 \ub0ae\uc740 \uac00\uce58\ub97c \uc8fc\uc7a5\ud558\uc5ec \uac00\uaca9\uc744 \ub0ae\ucd94\ub824 \ud560 \uc218 \uc788\ub2e4.
\uc774\ub7ec\ud55c \uc778\uc13c\ud2f0\ube0c \ubb38\uc81c\ub85c \uc778\ud574 \ud6a8\uc728\uc801\uc778 \uac70\ub798\ub97c \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uac00 \uc5b4\ub835\ub2e4.<\/p>\n\n\n\n

\n\n\n\n

Myerson-Satterthwaite \uc815\ub9ac<\/h4>\n\n\n\n

\uc774 \uc815\ub9ac\ub294 \ud2b9\uc815\ud55c \ubd84\ud3ec \ud558\uc5d0\uc11c \uad6c\ub9e4\uc790\uc640 \ud310\ub9e4\uc790\uc758 \uac00\uce58 \ud3c9\uac00\uac00 \uacb9\uce58\ub294 \uacbd\uc6b0, \ud6a8\uc728\uc801\uc774\uace0 \uc778\uc13c\ud2f0\ube0c \ud638\ud658\uc801\uc774\uba70 \uc608\uc0b0 \uade0\ud615\uacfc \uac1c\uc778 \ud569\ub9ac\uc131\uc744 \ubaa8\ub450 \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc740 \uc874\uc7ac\ud558\uc9c0 \uc54a\ub294\ub2e4\uace0 \ub9d0\ud55c\ub2e4.
\uc774\ub294 \uc0ac\uc801\uc778 \uc815\ubcf4\ub85c \uc778\ud574 \uac70\ub798\uc5d0\uc11c \ube44\ud6a8\uc728\uc131\uc774 \ubc1c\uc0dd\ud560 \uc218\ubc16\uc5d0 \uc5c6\uc74c\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n

\n\n\n\n

\uc694\uc57d<\/h4>\n\n\n\n

\uc0ac\uc801\uc778 \uc815\ubcf4\ub85c \uc778\ud574 \uc790\ubc1c\uc801\uc778 \uac70\ub798\uc5d0\uc11c \ube44\ud6a8\uc728\uc131\uc774 \ubc1c\uc0dd\ud558\uba70, \uc774\ub294 \uc778\uc13c\ud2f0\ube0c\uc640 \ud6a8\uc728\uc131 \uac04\uc758 \uadfc\ubcf8\uc801\uc778 \uae34\uc7a5\uc744 \ub098\ud0c0\ub0b8\ub2e4.
\uc774\ub7ec\ud55c \uacb0\uacfc\ub294 \ud611\uc0c1\uc5d0\uc11c\uc758 \uc2e4\ud328\ub098 \ud30c\uc5c5\uacfc \uac19\uc740 \ud604\uc0c1\uc744 \uc124\uba85\ud558\ub294 \ub370 \uc911\uc694\ud55c \ud1b5\ucc30\uc744 \uc81c\uacf5\ud55c\ub2e4.<\/p>\n\n\n\n

<\/p>\n\n\n\n

References<\/h4>\n\n\n\n

Game Theory Online, (6\/6) GTO2-3-06: Myerson-Satterthwaite Theorem, Dec 3, 2013 https:\/\/www.youtube.com\/watch?v=v09adx-aIs0<\/a><\/p>\n\n\n\n

<\/p>","protected":false},"excerpt":{"rendered":"

VCG is neither individually rational nor budget balanced in general, but could there exist some other incentive-compatible mechanism that is? This post from Game Theory Online (http:\/\/www.game-theory-class.org) gives an example that proves the Myerson-Satterthwaite Theorem, which states that there is no such mechanism.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[4,215,198,214,216],"class_list":["post-5233","post","type-post","status-publish","format-standard","hentry","category-game-theory-and-applications","tag-game-theory","tag-mar-21-2025","tag-mechanism","tag-vcg","tag-vickrey"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/5233"}],"collection":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/comments?post=5233"}],"version-history":[{"count":3,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/5233\/revisions"}],"predecessor-version":[{"id":5418,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/5233\/revisions\/5418"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=5233"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=5233"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=5233"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}