{"id":5216,"date":"2025-03-21T23:46:26","date_gmt":"2025-03-21T14:46:26","guid":{"rendered":"https:\/\/saraheee.com\/?p=5216"},"modified":"2025-03-23T19:54:31","modified_gmt":"2025-03-23T10:54:31","slug":"gt-mechanism-3-vcg-example","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2025\/03\/gt-mechanism-3-vcg-example\/","title":{"rendered":"[GT Mechanism] #3. VCG Example"},"content":{"rendered":"<h3 class=\"wp-block-heading\">GTO2-3-03: VCG Example<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">VCG \uba54\ucee4\ub2c8\uc998 \uc791\ub3d9 \uc608\uc2dc<br>&#8211; Selfish routing example<\/h4>\n\n\n\n<p>\uc774\uc81c VCG, \uc989 Vickrey-Clarke-Groves \uba54\ucee4\ub2c8\uc998\uc774 \uc2e4\uc81c\ub85c \uc5b4\ub5bb\uac8c \uc791\ub3d9\ud558\ub294\uc9c0\ub97c \ud558\ub098\uc758 \uc608\uc81c\ub97c \ud1b5\ud574 \uc0b4\ud3b4\ubcf4\uc790.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><img decoding=\"async\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-10-1024x592.png\" alt=\"\"><\/td><td><img decoding=\"async\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-11-1024x607.png\" alt=\"\"><\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\">What outcome will be selected by \\(\\chi\\)? path ABEF.<\/figcaption><\/figure>\n\n\n\n<p>\uc774 \uc608\uc2dc\ub294 \ub77c\uc6b0\ud305, \uc989 \uacbd\ub85c \uc120\ud0dd \ubb38\uc81c\uc774\ub2e4.<br>\ud654\uba74\uc5d0\ub294 \ubc29\ud5a5\uc131\uc774 \uc788\ub294 \ub124\ud2b8\uc6cc\ud06c\uac00 \uc788\uc73c\uba70, \uac01 \ub9c1\ud06c\uc5d0\ub294 \uc774\ub3d9 \ube44\uc6a9(\ud639\uc740 \uae38\uc774)\uc774 \uc8fc\uc5b4\uc838 \uc788\ub2e4.<br>\uc6b0\ub9ac\uc758 \ubaa9\ud45c\ub294 \uc815\uc810 A\uc5d0\uc11c \uc815\uc810 F\uae4c\uc9c0 \uac00\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p>\uac89\uc73c\ub85c \ubcf4\uae30\uc5d0 \uba85\ubc31\ud558\uac8c, \ucd5c\ub2e8 \uacbd\ub85c\ub294 \ubc14\ub85c ABEF \uc774 \uacbd\ub85c\uc774\ub2e4.<br>\ub530\ub77c\uc11c A\uc5d0\uc11c F\uae4c\uc9c0 \uac00\uc7a5 \ube60\ub974\uac8c \uac00\uace0\uc790 \ud558\ub294 \uc5ec\ud589\uc790\uac00 \uc120\ud0dd\ud560 \uacbd\ub85c\ub3c4 \uc774 \uacbd\ub85c\uac00 \ub41c\ub2e4.<\/p>\n\n\n\n<p>How much will AC have to pay?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The shortest path taking AC&#8217;s declaration into account has length 5, and imposes cost -5 on agents other than AC. The shortest path without AC&#8217;s declaration also has length 5. Thus, <br>\\(p_{AC} = (-5) &#8211; (-5) = 0\\).<\/li>\n\n\n\n<li>This is what we expect, since AC is not pivotal.<\/li>\n\n\n\n<li>Likewise, BD, CE, CF and DF will all pay zero.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">\ub9c1\ud06c \uc18c\uc720\uc790\uc758 \uc9c0\ubd88 \u2013 \uc608: AF \ub9c1\ud06c<\/h4>\n\n\n\n<p>VCG \uba54\ucee4\ub2c8\uc998\uc5d0 \ub530\ub974\uba74, AF \ub9c1\ud06c\uc758 \uc18c\uc720\uc790\ub294 \uc5bc\ub9c8\ub97c \uc9c0\ubd88\ud574\uc57c \ud560\uae4c?<br>\uc9c1\uad00\uc801\uc73c\ub85c \ubcf4\uba74, \uc774 \ub9c1\ud06c\ub294 \ucd5c\ub2e8 \uacbd\ub85c\uc5d0 \ud3ec\ud568\ub418\uc5b4 \uc788\uc9c0 \uc54a\uae30 \ub54c\ubb38\uc5d0, \uc9c0\ubd88\ub3c4, \ubcf4\uc0c1\ub3c4 \ubc1b\uc744 \uc774\uc720\uac00 \uc5c6\uc5b4\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>VCG \uba54\ucee4\ub2c8\uc998\uc758 \uacc4\uc0b0\uc5d0 \ub530\ub77c \ud655\uc778\ud574\ubcf4\uc790.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\ucd5c\ub2e8 \uacbd\ub85c\ub294 \ub9c1\ud06c AC\uc758 \ube44\uc6a9 \uc120\uc5b8\uc5d0 \ub530\ub77c \ucd1d \ube44\uc6a9\uc774 5\uc774\ub2e4.<\/li>\n\n\n\n<li>\ub9cc\uc57d AC\uac00 \uc874\uc7ac\ud558\uc9c0 \uc54a\uc558\ub354\ub77c\ub3c4, \uc5ec\uc804\ud788 \ucd5c\ub2e8 \uacbd\ub85c\ub294 \ub3d9\uc77c\ud558\uba70 \ube44\uc6a9\ub3c4 5\uc774\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p>\uc989, AC\uc758 \ucc38\uc5ec \uc5ec\ubd80\uac00 \uacb0\uacfc\uc5d0 \uc544\ubb34\ub7f0 \uc601\ud5a5\uc744 \uc8fc\uc9c0 \uc54a\uc558\uc73c\ubbc0\ub85c, AC\uc758 \uc9c0\ubd88\uc561\uc740 0\uc774\ub2e4.<br>\uc774 \ub17c\ub9ac\ub294 \ucd5c\ub2e8 \uacbd\ub85c\uc5d0 \ud3ec\ud568\ub418\uc9c0 \uc54a\uc740 \ub2e4\ub978 \ubaa8\ub4e0 \ub9c1\ud06c\ub4e4\uc5d0\ub3c4 \ub611\uac19\uc774 \uc801\uc6a9\ub41c\ub2e4.<\/p>\n\n\n\n<p>\ud654\uba74\uc5d0\uc11c \ud30c\ub780\uc0c9\uc73c\ub85c \ud45c\uc2dc\ub41c \ubaa8\ub4e0 \ub9c1\ud06c\ub4e4\uc740 \uc9c0\ubd88\ub3c4 \ubcf4\uc0c1\ub3c4 \ubc1c\uc0dd\ud558\uc9c0 \uc54a\ub294\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">\ucd5c\ub2e8 \uacbd\ub85c\uc5d0 \ud3ec\ud568\ub41c \ub9c1\ud06c\uc758 \uc9c0\ubd88 \uacc4\uc0b0<\/h4>\n\n\n\n<p>\uc774\uc81c \ucd5c\ub2e8 \uacbd\ub85c\uc5d0 \uc2e4\uc81c\ub85c \ucc38\uc5ec\ud55c \ub9c1\ud06c\uc5d0 \ub300\ud574 \uc0b4\ud3b4\ubcf4\uc790.<br>\uba3c\uc800 \ub9c1\ud06c AB\ub97c \uc608\ub85c \ub4e4\uc5b4 \ubcf4\uc790.<\/p>\n\n\n\n<p>\ud604\uc7ac \ucd5c\ub2e8 \uacbd\ub85c\uc758 \ucd1d \ube44\uc6a9\uc740 1 + 1 = 2\uc774\ub2e4 (BE + EF).<br>\ub9cc\uc57d AB\uac00 \uc5c6\uc5c8\ub2e4\uba74, \ucd5c\ub2e8 \uacbd\ub85c\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \ubcc0\uacbd\ub41c\ub2e4:<\/p>\n\n\n\n<p>A \u2192 C \u2192 D \u2192 F<\/p>\n\n\n\n<p>\ube44\uc6a9\uc740 2 + 3 + 1 = 6\uc774\ub2e4.<\/p>\n\n\n\n<p>How much will AB pay?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The shortest path taking AB&#8217;s declaration into account has length 5, and imposes cost 2 on other agents.<\/li>\n\n\n\n<li>The shortest path without AB is ACEF, which has cost 6.<\/li>\n\n\n\n<li>Thus \\(p_{AB} = (-6) &#8211; (-2) = -4\\).<\/li>\n<\/ul>\n\n\n\n<p>\ub530\ub77c\uc11c AB \ub9c1\ud06c\uc758 \uc18c\uc720\uc790\ub294 \uc0ac\ud68c \uc804\uccb4\uc5d0 4\ub9cc\ud07c\uc758 \ube44\uc6a9 \uc808\uac10\uc744 \uc81c\uacf5\ud55c \uc148\uc774\ub2e4.<br>\uc989, \uadf8\ub294 4\uc758 \ubcf4\uc0c1\uc744 \ubc1b\uac8c \ub41c\ub2e4.<br>\uadf8\uc758 \uc2e4\uc81c \ube44\uc6a9\uc774 3\uc774\ub77c\uba74, 1\uc758 \uc21c\uc774\uc775(profit)\uc744 \uc5bb\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p>\u2192\u00a0\uc5ec\uae30\uc5d0\uc11c \u201cAB \uc2a4\uc2a4\ub85c\uc758 \ube44\uc6a9\u201d\uc740 \uacc4\uc0b0\uc5d0\uc11c \uc81c\uc678\ub41c\ub2e4.<br>\uc65c\ub0d0\ud558\uba74 VCG\uc5d0\uc11c\ub294 \uac01 \uc5d0\uc774\uc804\ud2b8\uac00 <strong>\uc790\uc2e0\uc774 \uc0ac\ud68c\uc5d0 \uc5bc\ub9c8\ub098 \ud53c\ud574\ub97c \uc8fc\ub294\uc9c0\ub97c \uae30\uc900\uc73c\ub85c \ube44\uc6a9\uc744 \uc9c0\ubd88\ud558\uac8c \ub9cc\ub4e4\uae30 \ub54c\ubb38<\/strong>\uc774\ub2e4. \ub530\ub77c\uc11c \uc790\uc2e0\uc758 \ube44\uc6a9\uc740 \uc9c0\ubd88\ud560 \ud544\uc694\uac00 \uc5c6\uace0, \uc790\uc2e0\uc758 \uc874\uc7ac \uc720\ubb34\uc5d0 \ub530\ub77c <em>\ub2e4\ub978 \uc0ac\ub78c\ub4e4\uc758 \uc720\ud2f8\ub9ac\ud2f0(\ud639\uc740 \ube44\uc6a9)<\/em>\uc774 \uc5bc\ub9c8\ub098 \ub2ec\ub77c\uc9c0\ub294\uc9c0\ub97c \ubcf4\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">\ub9c1\ud06c BE\uc758 \uacbd\uc6b0<\/h4>\n\n\n\n<p>How much will BE pay? \\(p_{BE} = (-6) &#8211; (-4) = -2\\).<\/p>\n\n\n\n<p>BE\uac00 \uc5c6\uc5c8\ub2e4\uba74 \ucd5c\ub2e8 \uacbd\ub85c\ub294 \uc5ec\uc804\ud788 6\uc774\uc5c8\uc744 \uac83\uc774\ub2e4. (ACEF)<br>BE\uac00 \ud3ec\ud568\ub41c \ud604\uc7ac\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub294 3(AB) + 1(EF) = 4\uc774\ub2e4. \ub530\ub77c\uc11c BE\uac00 \uc0ac\ud68c\uc5d0 \uae30\uc5ec\ud55c \uac00\uce58\ub294 6 &#8211; 4 = 2\uc774\ub2e4.<br>\uc989, BE \ub9c1\ud06c\uc758 \uc18c\uc720\uc790\ub294 2\uc758 \ubcf4\uc0c1\uc744 \ubc1b\uace0, \ube44\uc6a9\uc774 1\uc774\uc5c8\ub2e4\uba74 1\uc758 \uc21c\uc774\uc775\uc744 \uc5bb\ub294\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">\ub9c1\ud06c EF\uc758 \uacbd\uc6b0<\/h4>\n\n\n\n<p>How much will EF pay? \\(p_{EF} = (-7) &#8211; (-4) = -3\\)<\/p>\n\n\n\n<p>EF\ub294 \uc870\uae08 \ub2e4\ub978 \uacb0\uacfc\uac00 \ub098\uc628\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>EF\uac00 \uc5c6\uc5c8\ub2e4\uba74 \uac00\ub2a5\ud55c \ucd5c\ub2e8 \uacbd\ub85c\ub294 7\uc774\uc5c8\uc744 \uac83\uc774\ub2e4. (ABDF)<\/li>\n\n\n\n<li>EF\uac00 \uc788\uc744 \uacbd\uc6b0, \ucd5c\ub2e8 \uacbd\ub85c\ub294 3(AB) + 1(BE) = 4\uc774\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p>\ucc28\uc774\ub294 7 &#8211; 4 = 3\uc774\uba70, \ub530\ub77c\uc11c EF\ub294 3\uc758 \ubcf4\uc0c1\uc744 \ubc1b\ub294\ub2e4. \uadf8\uc758 \ube44\uc6a9\uc774 1\uc774\ub77c\uba74, \uc21c\uc774\uc775\uc740 2\uc774\ub2e4.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">\uc694\uc57d \ubc0f \ud574\uc11d<\/h4>\n\n\n\n<p>VCG \uba54\ucee4\ub2c8\uc998 \ud558\uc5d0\uc11c, \uac01 \ub9c1\ud06c\uc758 \ubcf4\uc0c1 \ub610\ub294 \uc9c0\ubd88 \uae08\uc561\uc774 \uc11c\ub85c \ub2e4\ub978 \uc774\uc720\ub294<br>\uadf8 \ub9c1\ud06c\uac00 \uc5c6\uc5c8\uc744 \uacbd\uc6b0 \uc0ac\ud68c \uc804\uccb4\uac00 \uc5bc\ub9c8\ub098 \uc190\ud574\ub97c \ubcf4\ub294\uac00, \uc989 \uc0ac\ud68c\uc801 \uc601\ud5a5\ub825 \ub54c\ubb38\uc774\ub2e4.<br>\uc774\ub294 \uc77c\uc885\uc758 \uc2dc\uc7a5 \uc9c0\ubc30\ub825(Market Power) \uac1c\ub150\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc5b4\ub5a4 \ub9c1\ud06c\ub294 \ub300\uccb4 \uac00\ub2a5\ud558\ubbc0\ub85c \uc601\ud5a5\ub825\uc774 \ub0ae\uace0,<br>\uc5b4\ub5a4 \ub9c1\ud06c\ub294 \ub300\uccb4 \ubd88\uac00\ub2a5\ud558\ubbc0\ub85c \uc0ac\ud68c\uc5d0 \ud070 \uac00\uce58\ub97c \uc81c\uacf5\ud558\uba70 \ub354 \ub9ce\uc740 \ubcf4\uc0c1\uc744 \ubc1b\ub294\ub2e4.<\/p>\n\n\n\n<p>\ub530\ub77c\uc11c \ubcf4\uc0c1\uc774 \ub2ec\ub77c\uc9c0\ub294 \uac83\uc740 \uacf5\uc815\uc131 \ubb38\uc81c\uac00 \uc544\ub2c8\ub77c \uc0ac\ud68c\uc801 \uae30\uc5ec\ub3c4\uc5d0 \uae30\ubc18\ud55c \ucc28\ub4f1 \ubcf4\uc0c1 \uad6c\uc870\uc774\ub2e4.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\uc774\uac83\uc774 \ubc14\ub85c VCG \uba54\ucee4\ub2c8\uc998\uc774 \uc2e4\uc81c\ub85c \uc791\ub3d9\ud558\ub294 \ubc29\uc2dd\uc774\ub2e4.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<h4 class=\"wp-block-heading\">References<\/h4>\n\n\n\n<p>Game Theory Online, (3\/6) GTO2-3-03: VCG Example, Dec 3, 2013, <a href=\"https:\/\/www.youtube.com\/watch?v=luh_xkxKdrY\" rel=\"noopener\">https:\/\/www.youtube.com\/watch?v=luh_xkxKdrY<\/a><\/p>\n\n\n\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>This post from Game Theory Online (http:\/\/www.game-theory-class.org) gives an example of VCG in action.  It features Yoav Shoham (Stanford).<\/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,216],"class_list":["post-5216","post","type-post","status-publish","format-standard","hentry","category-game-theory-and-applications","tag-game-theory","tag-mar-21-2025","tag-mechanism","tag-vickrey"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/5216"}],"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=5216"}],"version-history":[{"count":19,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/5216\/revisions"}],"predecessor-version":[{"id":5339,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/5216\/revisions\/5339"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=5216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=5216"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=5216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}