{"id":4759,"date":"2025-02-15T08:58:09","date_gmt":"2025-02-14T23:58:09","guid":{"rendered":"https:\/\/saraheee.com\/?p=4759"},"modified":"2025-03-21T23:20:56","modified_gmt":"2025-03-21T14:20:56","slug":"review16-selling-privacy-at-auction","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2025\/02\/review16-selling-privacy-at-auction\/","title":{"rendered":"[review#16] Selling Privacy at Auction_Ghosh and Aaron, 2011 (2024)"},"content":{"rendered":"<h2 class=\"wp-block-heading\">Abstract<\/h2>\n\n\n\n<p>\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(differential privacy) \uc758 \uad00\uc810\uc5d0\uc11c \uac1c\uc778 \ub370\uc774\ud130 \uc2dc\uc7a5(private data markets) \uc5d0 \ub300\ud55c \uc5f0\uad6c\ub97c \uc2dc\uc791\ud55c\ub2e4. \uc6b0\ub9ac\ub294 \uc778\uad6c \ud1b5\uacc4\ub97c \ucd94\uc815\ud558\uae30 \uc704\ud574 \ubbfc\uac10\ud55c \uc815\ubcf4\ub97c \uad6c\ub9e4\ud558\ub824\ub294 \ub370\uc774\ud130 \ubd84\uc11d\uac00\ub97c \ubaa8\ub378\ub9c1\ud55c\ub2e4.<br>\uc774\ubbf8 \uac1c\uc778 \ub370\uc774\ud130\uc758 \ub9e4\ub9e4\uac00 \ub300\uaddc\ubaa8\ub85c \uc774\ub8e8\uc5b4\uc9c0\uace0 \uc788\uc9c0\ub9cc, \uac1c\uc778\uc815\ubcf4\ub97c \uc0c1\ud488(commodity)\uc73c\ub85c \ubcf4\ub294 \uc774\ub860\uc801\uc778 \uc5f0\uad6c\ub294 \ubd80\uc871\ud558\ub2e4. \ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 \uc774\ub7ec\ud55c \uc774\ub860\uc744 \uad6c\ucd95\ud558\ub294 \uac83\uc744 \ubaa9\ud45c\ub85c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uad6c\uccb4\uc801\uc73c\ub85c, \uc6b0\ub9ac\ub294 \ub370\uc774\ud130 \ubd84\uc11d\uac00(data analyst) \uac00 \ud2b9\uc815 \ud1b5\uacc4\ub97c \ucd94\uc815\ud558\uae30 \uc704\ud574 \uc77c\ubc18 \ub300\uc911\uc73c\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub294 \uc0c1\ud669\uc744 \uace0\ub824\ud55c\ub2e4.<br>\ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \uc815\ud655\ud55c \ud1b5\uacc4\ub97c \uac00\ub2a5\ud55c \ud55c \uc800\ub834\ud558\uac8c \uc5bb\uae30\ub97c \uc6d0\ud558\uba70, \ubc18\uba74 \uac1c\uc778 \ub370\uc774\ud130\uc758 \uc18c\uc720\uc790\ub4e4\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4(privacy loss)\ub85c \uc778\ud574 \ube44\uc6a9(cost)\uc744 \uacbd\ud5d8\ud558\uac8c \ub418\ubbc0\ub85c, \uc774\uc5d0 \ub300\ud55c \ubcf4\uc0c1\uc744 \ubc1b\uc544\uc57c \ud55c\ub2e4.<br>\uac01 \uac1c\uc778(\uc5d0\uc774\uc804\ud2b8)\uc740 \uc790\uc2e0\uc758 \uc774\uc775(profit)\uc744 \uadf9\ub300\ud654\ud558\ub824\ub294 \uc774\uae30\uc801\uc778 \uc874\uc7ac\uc774\ubbc0\ub85c, \ubcf8 \ub17c\ubb38\uc758 \ubaa9\ud45c\ub294 <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud558\ub294(truthful) \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud558\ub294 \uac83\uc774\ub2e4.<\/mark><\/p>\n\n\n\n<p>&#8211; \uc870\ub2ec \uacbd\ub9e4: \uad6c\ub9e4\uc790\uac00 \uc5ec\ub7ec \ud310\ub9e4\uc790\ub85c\ubd80\ud130 \ud2b9\uc815 \uc0c1\ud488\uc744 \uad6c\ub9e4\ud558\ub824\ub294 \uacbd\ub9e4 \ubc29\uc2dd<br>&#8211; \ub2e4\uc911 \ub2e8\uc704 \uc870\ub2ec \uacbd\ub9e4: \uad6c\ub9e4\uc790\uac00 \ub3d9\uc77c\ud55c \uc0c1\ud488\uc744 \uc5ec\ub7ec \uac1c \uad6c\ub9e4\ud574\uc57c \ud558\ub294 \uacbd\uc6b0\ub97c \ub2e4\ub8e8\ub294 \uacbd\ub9e4 \ubc29\uc2dd<\/p>\n\n\n\n<p>\ubcf8 \ub17c\ubb38\uc758 \uc8fc\uc694 \uacb0\uacfc\ub294 \uc774\ub7ec\ud55c \ubb38\uc81c\ub97c \ub2e4\uc911 \ub2e8\uc704 \uc870\ub2ec \uacbd\ub9e4(multi-unit procurement auctions)\uc758 \ubcc0\ud615\uc73c\ub85c \uc790\uc5f0\uc2a4\ub7fd\uac8c \ud574\uc11d\ud558\uace0 \ucd5c\uc801\ud654\ud560 \uc218 \uc788\ub2e4\ub294 \uc810\uc774\ub2e4.<br>\uc774 \uacb0\uacfc\ub97c \ubc14\ud0d5\uc73c\ub85c, \uc6b0\ub9ac\ub294 \ub450 \uac00\uc9c0 \uc790\uc5f0\uc2a4\ub7ec\uc6b4 \uc0c1\ud669\uc5d0\uc11c \ucd5c\uc801(\uc0c1\uc218 \uacc4\uc218 \ub0b4\uc5d0\uc11c)\uc778 \uacbd\ub9e4 \ubc29\uc2dd\uc744 \ub3c4\ucd9c\ud55c\ub2e4.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \uace0\uc815\ub41c \uc815\ud655\ub3c4 \ubaa9\ud45c(fixed accuracy goal) \ub97c \uac00\uc9c0\uace0 \uc788\uc744 \ub54c, \uc804\ud1b5\uc801\uc778 \ube45\ub9ac(Vickrey) \uacbd\ub9e4\ub97c \uc801\uc6a9\ud558\uba74 \ubd84\uc11d\uac00\uc758 \uc815\ud655\ub3c4 \ubaa9\ud45c\ub97c \ub2ec\uc131\ud558\uba74\uc11c \ucd1d \uc9c0\ubd88 \ube44\uc6a9\uc744 \ucd5c\uc18c\ud654\ud560 \uc218 \uc788\uc74c\uc744 \uc99d\uba85\ud55c\ub2e4.<\/mark><\/li>\n\n\n\n<li><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \uace0\uc815\ub41c \uc608\uc0b0(fixed budget) \uc744 \uac00\uc9c0\uace0 \uc788\uc744 \ub54c, \uc6b0\ub9ac\ub294 \ucd5c\uc885\uc801\uc73c\ub85c \ucd94\uc815\ub41c \uac12\uc758 \uc815\ud655\ub3c4\ub97c \ucd5c\ub300\ud654\ud558\uba74\uc11c\ub3c4, \ucd1d \uc9c0\ubd88 \uae08\uc561\uc774 \uc608\uc0b0\uc744 \ucd08\uacfc\ud558\uc9c0 \uc54a\ub3c4\ub85d \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc548\ud55c\ub2e4.<\/mark><\/li>\n<\/ol>\n\n\n\n<p>\uc774 \ub450 \uac00\uc9c0 \uacbd\uc6b0 \ubaa8\ub450\uc5d0\uc11c, \uc6b0\ub9ac\ub294 \ube44\uad50 \uae30\uc900\uc73c\ub85c \uc9c8\ud22c \uc5c6\uc74c\/\uc2dc\uae30\uc2ec \uc5c6\ub294(envy-free) \uba54\ucee4\ub2c8\uc998\uc744 \uc0ac\uc6a9\ud558\uba70, \uc774\ub294 \uace0\uc815 \uac00\uaca9(fixed-price) \uba54\ucee4\ub2c8\uc998\uc758 \uc790\uc5f0\uc2a4\ub7ec\uc6b4 \ubc94\uc8fc\uc640 \uc77c\uce58\ud55c\ub2e4. <br>\uc774 \ub450 \uac00\uc9c0 \uacb0\uacfc\uc5d0\uc11c, \uc6b0\ub9ac\ub294 \uac1c\uc778\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58(valuation for privacy)\uc640 \uc2e4\uc81c \ub370\uc774\ud130 \uc0ac\uc774\uc758 \uc0c1\uad00\uad00\uacc4\ub85c \uc778\ud574 \ubc1c\uc0dd\ud560 \uc218 \uc788\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9(privacy cost)\uc744 \uace0\ub824\ud558\uc9c0 \uc54a\uc558\ub2e4.<br>\uc6b0\ub9ac\ub294 \ub610\ud55c \uac1c\uc778\uc774 \ubcf4\uace0\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\ub85c \uc778\ud574 \ubc1c\uc0dd\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4(privacy loss)\uc5d0 \ub300\ud574 \uac1c\ubcc4\uc801\uc73c\ub85c \ud569\ub9ac\uc801\uc778(individually rational) \uba54\ucee4\ub2c8\uc998\uc774 \ubcf4\uc0c1\uc744 \uc81c\uacf5\ud560 \uc218 \uc5c6\uc74c\uc744 \uc77c\ubc18\uc801\uc73c\ub85c \uc99d\uba85\ud55c\ub2e4.<br>\uadf8\ub7fc\uc5d0\ub3c4 \ubd88\uad6c\ud558\uace0, \uc774\ub294 \uc911\uc694\ud55c \ubb38\uc81c\uc774\uba70, \uc774\ub97c \uc815\ud655\ud558\uac8c \ubaa8\ub378\ub9c1\ud558\ub294 \uac83\uc740 \ud5a5\ud6c4 \uc5f0\uad6c\uc5d0\uc11c \ub2e4\ub8e8\uc5b4\uc57c \ud560 \uc911\uc694\ud55c \ubc29\ud5a5 \uc911 \ud558\ub098\uc774\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">1. Introduction<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\uac00\uc7a5 \uc911\uc694\ud55c \ubb38\uc81c\ub294 &#8216;\uac1c\uc778\uc815\ubcf4&#8217;\ub77c\ub294 \uac1c\ub150\uc744 \uc815\uc758\ud558\uace0, \uc774\ub97c \uc815\ub7c9\uc801\uc73c\ub85c \uce21\uc815\ud558\ub294 \uac83\uc774\ub2e4.<\/strong><br>\uc774\ub7ec\ud55c \uce21\uba74\uc5d0\uc11c \uac1c\uc778\uc815\ubcf4\ub97c \uc0c1\ud488\ud654\ud558\ub294 \uac1c\ub150\uc740 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc758 \uc774\ub860\uc801 \uae30\ucd08\uc758 \ubc1c\uc804\uacfc \uc790\uc5f0\uc2a4\ub7fd\uac8c \uc5f0\uacb0\ub41c\ub2e4.<br>\ud2b9\ud788, \ucd5c\uadfc \uc5f0\uad6c\uc5d0\uc11c \ub3c4\uc785\ub41c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \uc5f0\uad6c [DMNS06] (\uc815\uc758 2.1) \ub294 \uac1c\uc778\uc815\ubcf4\ub97c \ubcf4\ud638\ud558\ub294 \uac15\ub825\ud55c \uac1c\ub150\uc744 \uc81c\uacf5\ud560 \ubfd0\ub9cc \uc544\ub2c8\ub77c, \uc774\ub97c \uc815\ub7c9\uc801\uc73c\ub85c \uce21\uc815\ud560 \uc218 \uc788\ub294 \uccb4\uacc4\ub97c \uc81c\uc2dc\ud55c\ub2e4.<br>\ub354 \uc911\uc694\ud55c \uc810\uc740, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uac00 \ubcf4\uc7a5\ud558\ub294 \uc131\uc9c8\uc774 \ud6a8\uc6a9 \uc774\ub860(utility-theoretic) \uad00\uc810\uc5d0\uc11c \uc790\uc5f0\uc2a4\ub7fd\uac8c \ud574\uc11d\ub420 \uc218 \uc788\uc73c\uba70, \uc774\ub97c \uc0ac\uace0\ud314 \uc218 \uc788\ub294 \uc591\uc801 \uac1c\ub150\uc73c\ub85c \uc815\uc758\ud560 \uc218 \uc788\ub2e4.<\/li>\n\n\n\n<li><strong>\uac1c\uc778 \ub370\uc774\ud130\ub294 \ubcf8\uc9c8\uc801\uc73c\ub85c \uc0c1\ud638 \ubcf4\uc644\uc131\uc778 \uc131\uc9c8(intrinsic complementarities)\uc744 \uac16\ub294 \uc0c1\ud488\uc774\ub2e4.<\/strong><br>\ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \ud2b9\uc815 \uac1c\uc778\uc758 \uac1c\ubcc4\uc801\uc778 \ub370\uc774\ud130 \uc790\uccb4\uc5d0\ub294 \uad00\uc2ec\uc774 \uc5c6\uc73c\uba70, \uc77c\ubc18\uc801\uc73c\ub85c \ub300\uaddc\ubaa8 \ubaa8\uc9d1\ub2e8\uc5d0\uc11c \ub300\ud45c\uc801\uc778 \uc0d8\ud50c\uc744 \uc5bb\ub294 \uac83\uc5d0 \uad00\uc2ec\uc774 \uc788\ub2e4. \ud558\uc9c0\ub9cc \ubd84\uc11d\uac00\ub294 \uac1c\ubcc4\uc801\uc778 \uac1c\uc778\ub4e4\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud574\uc57c \ud55c\ub2e4.<br>\ub9cc\uc57d \uac01 \uac1c\uc778\ub4e4\uc774 \uc790\uc2e0\uc758 \uac1c\uc778\uc815\ubcf4\uc5d0 \ub300\ud55c \uac00\uce58(value for privacy)\uc640 \uc2e4\uc81c \ub370\uc774\ud130 \uc0ac\uc774\uc5d0 \uc54c \uc218 \uc5c6\ub294 \uc0c1\uad00\uad00\uacc4\ub97c \uac00\uc9c0\uace0 \uc788\ub2e4\uba74, \u201c\uac00\uc7a5 \uc800\ub834\ud55c \ud310\ub9e4\uc790\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub294&#8221; \uc77c\ubc18\uc801\uc778 \uc804\ub7b5\uc740 \uc2e4\ud328\ud560 \uac00\ub2a5\uc131\uc774 \ud06c\ub2e4.<br>\uadf8\ub807\ub2e4\uba74, \ubd84\uc11d\uac00\uac00 \uc804\uccb4 \uc778\uad6c\ub97c \ub300\ud45c\ud558\ub294 \uac12\uc744 \uacc4\uc0b0\ud558\ub824 \ud560 \ub54c, \uc5b4\ub5a4 \ubc29\uc2dd\uc73c\ub85c \uacbd\ub9e4\ub97c \uc124\uacc4\ud574\uc57c \ud560\uae4c?<\/li>\n\n\n\n<li><strong>\uac1c\uc778\uc774 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc5d0 \ub300\ud574 \uc9c0\ubd88\ud574\uc57c \ud558\ub294 \ube44\uc6a9 \uc790\uccb4\uac00 \ube44\uacf5\uac1c \uc815\ubcf4\uc77c \uc218 \uc788\ub2e4.<\/strong><br>\uc608\ub97c \ub4e4\uc5b4, \uc568\ub9ac\uc2a4\uac00 \uc885\uc591\ud559 \uc804\ubb38\uc758\ub97c \ubc29\ubb38\ud55c \ud6c4, \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc758 \uac00\uce58\ub97c \uae09\uaca9\ud788 \ub192\uac8c \ud3c9\uac00\ud558\uae30 \uc2dc\uc791\ud588\ub2e4\uace0 \uac00\uc815\ud574 \ubcf4\uc790. \uc774 \uacbd\uc6b0, \uc568\ub9ac\uc2a4\uac00 \uac11\uc790\uae30 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc911\uc694\ud558\uac8c \uc0dd\uac01\ud558\uae30 \uc2dc\uc791\ud588\ub2e4\ub294 \uc0ac\uc2e4 \uc790\uccb4\uac00 \uc774\ubbf8 \uc815\ubcf4 \uc720\ucd9c\uc774 \ub420 \uc218 \uc788\ub2e4.(<br>\uc774\ub7ec\ud55c \ubcc0\ud654 \uc790\uccb4\uac00 \uadf8\ub140\uc758 \uac74\uac15 \uc0c1\ud0dc\uc5d0 \ub300\ud55c \uc815\ubcf4\ub97c \uc554\uc2dc\ud560 \uc218 \uc788\ub2e4.) \uadf8\ub807\ub2e4\uba74, \uacbd\ub9e4\ub97c \uc124\uacc4\ud560 \ub54c \uac1c\ubcc4 \uc751\ucc30\uc790\ub4e4\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc190\uc2e4\uc744 \ubcf4\uc0c1\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\uc131\ud560 \uc218 \uc788\uc744\uae4c? \uc989, \ub2e8\uc21c\ud788 \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud558\ub294 \ub300\uac00\ub97c \uc9c0\ubd88\ud558\ub294 \uac83\uc774 \uc544\ub2c8\ub77c, \uc751\ucc30(bid) \uc790\uccb4\uac00 \uacbd\ub9e4\uc758 \uc791\ub3d9 \ubc29\uc2dd\uc5d0 \uc601\ud5a5\uc744 \ubbf8\uce58\uba74\uc11c \ubc1c\uc0dd\ud558\ub294 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc190\uc2e4\uae4c\uc9c0\ub3c4 \uace0\ub824\ud560 \uc218 \uc788\uc744\uae4c?<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">1.1. Differential Privacy as a Commodity<\/h3>\n\n\n\n<p>\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638(differential privacy)\ub294 \ub370\uc774\ud130\ubca0\uc774\uc2a4 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uc704\ud55c \uae30\uc220\uc801 \uc815\uc758\ub85c, Dwork \ub4f1 [DMNS06]\uc5d0 \uc758\ud574 \uacf5\uc2dd\uc801\uc73c\ub85c \uc81c\uc548\ub418\uc5c8\ub2e4(\uc790\uc138\ud55c \ub0b4\uc6a9\uc740 2\uc7a5\uc5d0\uc11c \uc815\uc758\ud568). \ube44\uacf5\uc2dd\uc801\uc73c\ub85c, \ud55c \uac1c\uc778\uc758 \ub370\uc774\ud130\uac00 \ubcc0\uacbd\ub418\ub354\ub77c\ub3c4 \uc54c\uace0\ub9ac\uc998\uc758 \ucd9c\ub825 \ud655\ub960\uc774 exp(\u03b5) \u2248 (1 + \u03b5) \ubc30 \uc774\uc0c1 \ubcc0\ud558\uc9c0 \uc54a\uc73c\uba74, \ud574\ub2f9 \uc54c\uace0\ub9ac\uc998\uc740 \u03b5-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud55c\ub2e4\uace0 \ud55c\ub2e4.<\/p>\n\n\n\n<p>\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub294 \ub610\ud55c \uc790\uc5f0\uc2a4\ub7ec\uc6b4 \ud6a8\uc6a9 \uc774\ub860\uc801(utility-theoretic) \ud574\uc11d\uc744 \uc81c\uacf5\ud558\ubbc0\ub85c, \uac1c\uc778\uc815\ubcf4\ub97c \uad6c\ub9e4\ud558\uac70\ub098 \ud310\ub9e4\ud560 \ub54c \uc774\ub97c \uc815\ub7c9\uc801\uc73c\ub85c \uce21\uc815\ud558\ub294 \uc720\uc6a9\ud55c \ucc99\ub3c4\ub85c \ud65c\uc6a9\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\u03b5-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\ub294 \uc54c\uace0\ub9ac\uc998 A\uc758 \uc911\uc694\ud55c \uc18d\uc131 \uc911 \ud558\ub098\ub294, \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc640 \ub3c5\ub9bd\uc801\uc778 \uc784\uc758\uc758 \ud568\uc218 f\uc640 \uc870\ud569\ub418\ub354\ub77c\ub3c4 f(A) \uc5ed\uc2dc \u03b5-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uc720\uc9c0\ud55c\ub2e4\ub294 \uc810\uc774\ub2e4. \uc774 \uc18d\uc131\uc744 \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998\uc758 \uc2e4\uc81c \ucd9c\ub825\uacfc\ub294 \uc0c1\ub2f9\ud788 \ub3d9\ub5a8\uc5b4\uc9c4 \uc0ac\uac74\uc5d0 \ub300\ud574\uc11c\ub3c4 \ub17c\ub9ac\uc801\uc73c\ub85c \ucd94\ub860\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc608\ub97c \ub4e4\uc5b4, \u03b5-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubcf4\uc7a5\uc740 \u201c\uc800\ub141 \uc2dd\uc0ac \uc911\uc5d0 \uad11\uace0 \uc804\ud654\ub97c \ubc1b\uc744 \ud655\ub960\u201d \ub610\ub294 \u201c\uac74\uac15 \ubcf4\ud5d8 \uac00\uc785\uc774 \uac70\ubd80\ub420 \ud655\ub960\u201d\uc774 exp(\u03b5) \ubc30 \uc774\uc0c1 \uc99d\uac00\ud558\uc9c0 \uc54a\ub294\ub2e4\ub294 \uac83\uc744 \uc758\ubbf8\ud55c\ub2e4. \uc774\ub7ec\ud55c \uc18d\uc131 \ub355\ubd84\uc5d0 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub294 \ubaa8\ub4e0 \uac1c\ubcc4 \uc0ac\uc6a9\uc790\uc5d0 \ub300\ud574, \uc784\uc758\uc758 (\uc54c\ub824\uc9c0\uc9c0 \uc54a\uc740) \ud6a8\uc6a9 \ud568\uc218\uac00 \uc874\uc7ac\ud558\ub354\ub77c\ub3c4 \uc801\uc6a9\ub420 \uc218 \uc788\ub294 \uac15\ub825\ud55c \ubcf4\uc7a5\uc774 \ub41c\ub2e4.<br>\uad6c\uccb4\uc801\uc73c\ub85c, \uc5b4\ub5a4 \uac1c\uc778\uc774 \ubbf8\ub798 \uc0ac\uac74\ub4e4\uc5d0 \ub300\ud574 \ud2b9\uc815 \ud6a8\uc6a9 \ud568\uc218 u\ub97c \uac00\uc9c0\uace0 \uc788\ub2e4\uace0 \ud560 \ub54c, \u03b5-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\ub294 \uc5f0\uc0b0\uc740 \ud574\ub2f9 \uac1c\uc778\uc758 \ubbf8\ub798 \uae30\ub300 \ud6a8\uc6a9\uc744 exp(-\u03b5) \u2248 (1 &#8211; \u03b5) \ubc30 \uc774\uc0c1 \uac10\uc18c\uc2dc\ud0a4\uc9c0 \uc54a\ub294\ub2e4. \ub610\ub294, \uc774\ub97c \ub3d9\ub4f1\ud558\uac8c \ud45c\ud604\ud558\uba74, \uae30\ub300 \ud6a8\uc6a9 E[u(x)]\uc758 \u03b5\ubc30(\u03b5E[u(x)]) \uc774\ud558\uc758 \uac00\uc0b0\uc801 \uac10\uc18c\ub97c \ucd08\ub798\ud55c\ub2e4.<br>\ub530\ub77c\uc11c, \uac1c\uc778\uc774 \uc790\uc2e0\uc758 \ub370\uc774\ud130\ub97c \u03b5-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubc29\uc2dd\uc73c\ub85c \uc0ac\uc6a9\ud558\ub3c4\ub85d \ud5c8\uc6a9\ud560 \ub54c \ubc1c\uc0dd\ud558\ub294 \ube44\uc6a9\uc744 \uc815\ub7c9\uc801\uc73c\ub85c \ud3c9\uac00\ud558\ub294 \uc790\uc5f0\uc2a4\ub7ec\uc6b4 \ubc29\ubc95\uc774 \uc874\uc7ac\ud55c\ub2e4. \uc989, \uadf8 \uac1c\uc778\uc5d0\uac8c \uc788\uc5b4 \ud574\ub2f9 \ub370\uc774\ud130 \uc0ac\uc6a9\uc758 \uac00\uce58\ub294 \uadf8\uc758 \uae30\ub300 \ud6a8\uc6a9\uc758 \u03b5-\ube44\uc728(\u03b5-fraction)\uc5d0 \ud574\ub2f9\ud574\uc57c \ud55c\ub2e4. \uc774\uc5d0 \ub300\ud55c \ubcf4\ub2e4 \uc790\uc138\ud55c \uc124\uba85\uc740 2.3\uc7a5\uc5d0\uc11c \ub2e4\ub8ec\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">1.2. Results<\/h3>\n\n\n\n<p><br>\ubcf8 \ub17c\ubb38\uc758 \uc8fc\uc694 \uae30\uc5ec\ub294 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \uc77c\uc815 \uc218\uc900\uc758 \uc815\ud655\ub3c4\ub97c \uc81c\uacf5\ud558\ub824\uba74, \ud2b9\uc815 \uc218\uc758 \uac1c\uc778\uc73c\ub85c\ubd80\ud130 \ucd5c\uc18c\ud55c\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638(privacy)\ub97c \uad6c\ub9e4\ud574\uc57c \ud55c\ub2e4\ub294 \uc810\uc744 \ubc1d\ud78c \uac83\uc774\ub2e4. \uc774\ub294 \uc815\ud655\ud55c \uc751\ub2f5\uc744 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubc29\uc2dd\uc73c\ub85c \uc81c\uacf5\ud558\ub294 \ubb38\uc81c\ub97c \uc870\ub2ec \ubb38\uc81c(procurement problem)\uc758 \ud615\ud0dc\ub85c \ub2e8\uc21c\ud654\ud560 \uc218 \uc788\uc74c\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uad6c\uccb4\uc801\uc73c\ub85c, \uc6b0\ub9ac\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ubaa8\ub378\uc744 \uc5f0\uad6c\ud55c\ub2e4. \uba3c\uc800, <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>n\uba85\uc758 \uac1c\uc778(n individuals)\uc774 \uc874\uc7ac\ud558\uba70, \uac01 \uac1c\uc778 i\ub294 \uac1c\uc778\uc801\uc778 \ube44\ud2b8 \uac12 b\u1d62\ub97c \uac00\uc9c0\uace0 \uc788\ub2e4.<\/li>\n\n\n\n<li>\uc774 \uc815\ubcf4\ub294 \ubcd1\uc6d0\uacfc \uac19\uc740 \uac1c\uc778\uc815\ubcf4\ub97c \uad00\ub9ac\ud558\ub294 \ub370\uc774\ud130\ubca0\uc774\uc2a4 \uad00\ub9ac\uc790(database administrator)\uc5d0 \uc758\ud574 \uc774\ubbf8 \uc54c\ub824\uc838 \uc788\ub2e4.<\/li>\n\n\n\n<li>\uac01 \uac1c\uc778\uc740 \ub610\ud55c \ube44\uc6a9 \ud568\uc218(cost function) c\u1d62(\u03b5)\ub97c \uac00\uc9c0\uace0 \uc788\uc73c\uba70, \uc774\ub294 b\u1d62\uac00 \u03b5-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubc29\uc2dd\uc73c\ub85c \uc0ac\uc6a9\ub420 \uacbd\uc6b0 \ud574\ub2f9 \uac1c\uc778\uc774 \ubd80\ub2f4\ud574\uc57c \ud558\ub294 \ube44\uc6a9\uc744 \ub098\ud0c0\ub0b8\ub2e4.<\/li>\n\n\n\n<li>\ubaa8\ub4e0 \uc720\ud6a8\ud55c \uba54\ucee4\ub2c8\uc998\uc740 \uac01 \uac1c\uc778\uc5d0\uac8c \uadf8\ub4e4\uc758 \uac1c\uc778\uc815\ubcf4 \uc0ac\uc6a9\uc5d0 \ub300\ud55c \ubcf4\uc0c1\uc744 \uc81c\uacf5\ud574\uc57c \ud55c\ub2e4.<\/li>\n\n\n\n<li>\ub610\ud55c, \uac1c\uc778\ub4e4\uc740 \uc790\uc2e0\uc758 \ube44\uc6a9 \ud568\uc218\ub97c \uc870\uc791\ud558\uc5ec \uc9c0\uae09\ubc1b\ub294 \uae08\uc561\uc744 \ucd5c\ub300\ud654\ud558\ub824\ub294 \uc804\ub7b5\uc801 \ud589\ub3d9\uc744 \ud560 \uc218 \uc788\uc73c\ubbc0\ub85c, \uac1c\uc778\ub4e4\uc774 \uc790\uc2e0\uc758 \uc2e4\uc81c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9\uc744 \uc815\uc9c1\ud558\uac8c \ubcf4\uace0\ud558\ub3c4\ub85d \uc720\ub3c4\ud558\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uac00 \ud544\uc694\ud558\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p>\ud55c\ud3b8, \ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \ub450 \uac00\uc9c0 \ubaa9\ud45c \uc911 \ud558\ub098\ub97c \uac00\uc9c0\uace0 \uc788\ub2e4. \uccab \ubc88\uc9f8\ub294 \uace0\uc815\ub41c \uc815\ud655\ub3c4 \ubaa9\ud45c\ub97c \uc124\uc815\ud558\uace0, \ud574\ub2f9 \uc815\ud655\ub3c4\ub97c \uc5bb\ub294 \ub370 \ud544\uc694\ud55c \ube44\uc6a9\uc744 \ucd5c\uc18c\ud654\ud558\ub294 \uac83\uc774\uba70, \ub450 \ubc88\uc9f8\ub294 \uc81c\ud55c\ub41c \uc608\uc0b0 \ub0b4\uc5d0\uc11c \uac00\ub2a5\ud55c \ud55c \ub192\uc740 \uc815\ud655\ub3c4\ub97c \ub2ec\uc131\ud558\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc774\ub7ec\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574, \uc6b0\ub9ac\ub294 \uba3c\uc800 \uac1c\uc778\ub4e4\uc774 \uc790\uc2e0\uc758 \ube44\ud2b8 \uac12 b\u1d62\uc758 \uc0ac\uc6a9\uc73c\ub85c \uc778\ud55c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc190\uc2e4\uc5d0 \ub300\ud55c \ubcf4\uc0c1\uc744 \ubc1b\uc9c0\ub9cc, b\u1d62\uc640 \ube44\uc6a9 \ud568\uc218 c\u1d62 \uc0ac\uc774\uc758 \uc554\ubb35\uc801\uc778 \uc0c1\uad00\uad00\uacc4\ub85c \uc778\ud55c \ucd94\uac00\uc801\uc778 \uac1c\uc778\uc815\ubcf4 \uc720\ucd9c\uc5d0 \ub300\ud55c \ubcf4\uc0c1\uc740 \ubc1b\uc9c0 \uc54a\ub294 \uac04\ub2e8\ud55c \ubaa8\ub378\uc744 \uace0\ub824\ud55c\ub2e4. \uc989, \ud2b9\uc815 \uac1c\uc778\uc758 \ub370\uc774\ud130 b\u1d62\uac00 \uc804\ud600 \uc0ac\uc6a9\ub418\uc9c0 \uc54a\ub294\ub2e4\uba74, \ud574\ub2f9 \uac1c\uc778\uc740 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc190\uc2e4\uc744 \uc785\uc9c0 \uc54a\uc73c\ubbc0\ub85c, \uba54\ucee4\ub2c8\uc998\uc774 \ubcf4\uc0c1\uc744 \uc81c\uacf5\ud560 \ud544\uc694\uac00 \uc5c6\ub2e4.<br>\ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \uc815\ud655\ud55c \ud1b5\uacc4 \uac12 s = \u2211 b\u1d62\ub97c \ud655\ubcf4\ud558\ub294 \uacbd\ub9e4\ub97c \uc124\uacc4\ud558\ub824 \ud560 \ub54c, \uc9c1\uad00\uc801\uc73c\ub85c \uc5ec\ub7ec \uac00\uc9c0 \ubcf5\uc7a1\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uace0\ub824\ub420 \uc218 \uc788\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \ubb34\uc791\uc704\ub85c \uac1c\uc778\uc744 \uc0d8\ud50c\ub9c1\ud55c \ud6c4, \uc0d8\ud50c \uc804\uccb4\ub97c \ub300\uc0c1\uc73c\ub85c \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub294 \ubc29\uc2dd\uc774 \uac00\ub2a5\ud558\ub2e4. \uadf8\ub7ec\ub098 \uc774\ub7ec\ud55c \ubc29\uc2dd\uc5d0\ub294 \ub9ce\uc740 \ubcc0\ud615\uc774 \uc874\uc7ac\ud558\uba70, \ucc98\uc74c\uc5d0\ub294 \uc774\ub7ec\ud55c \uc811\uadfc\ubc95\uc744 \ud0d0\uc0c9\ud558\ub294 \ubc29\ud5a5\uc73c\ub85c \uc5f0\uad6c\ub97c \uc9c4\ud589\ud588\ub2e4.<br>\uadf8\ub7ec\ub098 \uc6b0\ub9ac\uc758 \uc8fc\uc694 \uacb0\uacfc\ub294 \uc774\ub7ec\ud55c \ubcf5\uc7a1\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uace0\ub824\ud560 \ud544\uc694\uac00 \uc5c6\ub2e4\ub294 \uac83\uc774\ub2e4. \uc6b0\ub9ac\ub294 \uba54\ucee4\ub2c8\uc998\uc758 \ub0b4\ubd80 \uad6c\uc870\ub97c \ucd94\uc0c1\ud654\ud560 \uc218 \uc788\uc73c\uba70, \ubcf8\uc9c8\uc801\uc73c\ub85c \ub2e4\uc911 \ub2e8\uc704 \uc870\ub2ec \uacbd\ub9e4\ub85c \ubb38\uc81c\ub97c \ub2e8\uc21c\ud654\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<p>\uc774\ub85c \uc778\ud574 \uba87 \uac00\uc9c0 \uc911\uc694\ud55c \uacb0\uacfc\uac00 \ub3c4\ucd9c\ub41c\ub2e4. \uccab\uc9f8, \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \ud2b9\uc815 \uc815\ud655\ub3c4 \ubaa9\ud45c\ub97c \ub2ec\uc131\ud558\ub294 \ub370 \ud544\uc694\ud55c \ube44\uc6a9\uc744 \ucd5c\uc18c\ud654\ud558\ub824\ub294 \uacbd\uc6b0, \uc6b0\ub9ac\ub294 \ud45c\uc900 VCG(Vickrey-Clarke-Groves) \uba54\ucee4\ub2c8\uc998\uc774 \u201c\uc2dc\uae30\uc2ec \uc5c6\ub294(Envy-Free)\u201d \uba54\ucee4\ub2c8\uc998 \uc911 \ucd5c\uc801\uc784\uc744 \ubcf4\uc778\ub2e4. \ub458\uc9f8, \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \uace0\uc815\ub41c \uc608\uc0b0 \ub0b4\uc5d0\uc11c \uc815\ud655\ub3c4\ub97c \uadf9\ub300\ud654\ud558\ub824\ub294 \uacbd\uc6b0, \uc6b0\ub9ac\ub294 \ub354 \ube44\uc815\ud615\uc801\uc778 \uc870\ub2ec \uacbd\ub9e4 \ud658\uacbd\uc744 \ub2e4\ub8ec\ub2e4. \uc774 \uacbd\uc6b0, \uad6c\ub9e4\uc790\ub294 \uac00\ub2a5\ud55c \ud55c \ub9ce\uc740 \ud310\ub9e4\uc790\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub824 \ud558\uba70, \ud310\ub9e4\uc790\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9\uc740 \ub2e4\ub978 \ud310\ub9e4\uc790\ub4e4\uc774 \ub370\uc774\ud130 \ud310\ub9e4\uc5d0 \ucc38\uc5ec\ud558\ub294\uc9c0 \uc5ec\ubd80\uc5d0 \ub530\ub77c \ub2ec\ub77c\uc9c4\ub2e4. \uc774\ub7ec\ud55c \ud658\uacbd\uc5d0\uc11c, \uc6b0\ub9ac\ub294 \uac01 \uc0ac\ub840(instance)\uc5d0 \ub300\ud574 \ucd5c\uc801\uc758(fixed-price, envy-free) \uc9c4\uc2e4\uc131(truthful) \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc548\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc6b0\ub9ac\uac00 \uc81c\uc548\ud558\ub294 \uace0\uc815 \uac00\uaca9(fixed-price) \uba54\ucee4\ub2c8\uc998\uc740 \uae30\uc874\uc758 \uc120\ud589 \uc5f0\uad6c\uc5d0\uc11c \uc0ac\uc804 \uc815\ubcf4 \uc5c6\uc774(prior-free) \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud560 \ub54c \ud45c\uc900\uc801\uc73c\ub85c \uc0ac\uc6a9\ub418\ub294 \ubc29\uc2dd\uc774\ub2e4. \uadf8\ub7ec\ub098 \uc6b0\ub9ac\uc758 \uc5f0\uad6c\uc5d0\uc11c\ub294 \uae30\uc874\uc758 \uacbd\ub9e4 \ud658\uacbd\uacfc \ucc28\uc774\uac00 \uc788\ub2e4. \ud2b9\ud788, \ubca0\uc774\uc9c0\uc548 \ucd5c\uc801(Bayesian-optimal) \uba54\ucee4\ub2c8\uc998\uc774 \uc774\ubbf8 \uc874\uc7ac\ud558\ub294 \ud658\uacbd\uc5d0\uc11c\ub294 \uace0\uc815 \uac00\uaca9 \uba54\ucee4\ub2c8\uc998\uc774 \uc801\uc808\ud55c \uae30\uc900\uc774 \ub420 \uc218 \uc788\ub2e4. \ud558\uc9c0\ub9cc, \ud604\uc7ac \uc5f0\uad6c\ub418\ub294 \uc870\ub2ec \uacbd\ub9e4 \ud658\uacbd\uc5d0\uc11c\ub294 \ubca0\uc774\uc9c0\uc548 \ucd5c\uc801 \uba54\ucee4\ub2c8\uc998\uc774 \uc54c\ub824\uc838 \uc788\uc9c0 \uc54a\uc73c\ubbc0\ub85c, \uc6b0\ub9ac\uc758 \ubca4\uce58\ub9c8\ud06c \uc120\ud0dd(\uace0\uc815 \uac00\uaca9 \uba54\ucee4\ub2c8\uc998\uc758 \uc815\ub2f9\uc131 \ub610\ub294 \uac1c\uc120 \uac00\ub2a5\uc131)\uc774 \ucd94\uac00 \uc5f0\uad6c\ub97c \ud1b5\ud574 \uac80\uc99d\ub420 \ud544\uc694\uac00 \uc788\ub2e4.<\/p>\n\n\n\n<p>\ub9c8\uc9c0\ub9c9\uc73c\ub85c, \uc6b0\ub9ac\ub294 \uc77c\ubc18\uc801\uc778 \ubd88\uac00\ub2a5\uc131(impossibility) \uacb0\uacfc\ub97c \uc81c\uc2dc\ud55c\ub2e4. \uc5b4\ub5a4 \uc9c1\uc811 \ubcf4\uace0 \uba54\ucee4\ub2c8\uc998(direct revelation mechanism)\ub3c4, \uac1c\uc778\uc758 \ube44\uacf5\uac1c \ub370\uc774\ud130 b\u1d62\uc640 \ube44\uc6a9 \ud568\uc218 c\u1d62 \uc0ac\uc774\uc758 \uc54c\ub824\uc9c0\uc9c0 \uc54a\uc740 \uc0c1\uad00\uad00\uacc4\ub85c \uc778\ud574 \ubc1c\uc0dd\ud558\ub294 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc190\uc2e4\uc744 \ubcf4\uc0c1\ud560 \uc218 \uc5c6\ub2e4. \uc989, \ub9cc\uc57d \uac1c\uc778\uc758 \ube44\uc6a9 \ud568\uc218 c\u1d62\uac00 \uc0ac\uc804\uc5d0 \uc815\ud574\uc9c4 \ud2b9\uc815 \ubc94\uc704 \ub0b4\uc5d0 \uc874\uc7ac\ud55c\ub2e4\ub294 \uac00\uc815\uc774 \uc5c6\ub2e4\uba74, \uac1c\uc778\ub4e4\uc5d0\uac8c \ube44(\u975e)\uc0ac\uc18c\ud55c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubcf4\uc7a5\uc744 \uc81c\uacf5\ud558\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud558\ub2e4. \uc774\ub7ec\ud55c \uacb0\uacfc\ub294 \uac1c\uc778 \ub370\uc774\ud130\uc640 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9 \uac04\uc758 \uc54c\ub824\uc9c0\uc9c0 \uc54a\uc740 \uc0c1\uad00\uad00\uacc4\ub97c \uc5f0\uad6c\ud560 \uc218 \uc788\ub294 \uc62c\ubc14\ub978 \ubaa8\ub378\uc744 \ucc3e\ub294 \uac83\uc774 \uc911\uc694\ud55c \uc5f0\uad6c \ubc29\ud5a5\uc774\ub77c\ub294 \uc810\uc744 \uc2dc\uc0ac\ud55c\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2. Preliminaries<\/h2>\n\n\n\n<p>\uc6b0\ub9ac\ub294 n\uba85\uc758 \uac1c\uc778 {1, \u2026, n}\uc758 \ub370\uc774\ud130\ub97c \ud3ec\ud568\ud558\ub294 \ub370\uc774\ud130\ubca0\uc774\uc2a4\ub97c \uace0\ub824\ud558\uba70, \uc774 \uc9d1\ud569\uc744 [n]\uc73c\ub85c \ud45c\uae30\ud55c\ub2e4. \uac01 \uac1c\uc778 i\ub294 \uac1c\uc778\uc801\uc778 \ube44\ud2b8 \uac12 \\(b_i \\in \\{0,1\\}\\)\uc640 \uac1c\uc778\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9\uc744 \ub098\ud0c0\ub0b4\ub294 \uac12 \\(v_i\\)\ub97c \uac00\uc9c4\ub2e4. \uc774\ub54c, \\(v_i\\)\ub294 \uac1c\uc778\uc774 \uc790\uc2e0\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc190\uc2e4\uc5d0 \ub300\ud574 \ubd80\uc5ec\ud558\ub294 \ube44\uc6a9\uc744 \ub098\ud0c0\ub0b4\ub294 \ube44\uc6a9 \ud568\uc218(cost function)\ub97c \ub9e4\uac1c\ubcc0\uc218\ud654\ud558\ub294 \uac12\uc774\ub2e4.<\/p>\n\n\n\n<p>\uac1c\uc778\uc801\uc778 \ube44\ud2b8 \\(b_i\\)\ub294 \uc784\uc758\uc758 \uc608\/\uc544\ub2c8\uc624(yes\/no) \uc9c8\ubb38\uc5d0 \ub300\ud55c \uc751\ub2f5\uc744 \ub098\ud0c0\ub0b8\ub2e4\uace0 \uac00\uc815\ud560 \uc218 \uc788\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \ud2b9\uc815 \uac1c\uc778\uc774 \ubbfc\uac10\ud55c \uc758\ub8cc \uc0c1\ud0dc\ub97c \uac00\uc9c0\uace0 \uc788\ub294\uc9c0 \uc5ec\ubd80\ub97c \ub098\ud0c0\ub0bc \uc218\ub3c4 \uc788\ub2e4.<br>\uc774 \ube44\ud2b8 \uac12 \\(b_i\\)\ub294 \uac80\uc99d \uac00\ub2a5\ud558\uba70, \uac1c\uc778\uc740 \uc790\uc2e0\uc758 \ube44\ud2b8 \uac12\uc744 \uac70\uc9d3\uc73c\ub85c \ubcf4\uace0\ud560 \uc218 \uc5c6\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \ubcd1\uc6d0\uacfc \uac19\uc740 \uc2e0\ub8b0\ud560 \uc218 \uc788\ub294 \ub370\uc774\ud130\ubca0\uc774\uc2a4 \uad00\ub9ac\uc790\uac00 \uc774\ubbf8 \uc774 \uc815\ubcf4\ub97c \uc54c\uace0 \uc788\uac70\ub098, \ud608\uc561 \ub610\ub294 \ud0c0\uc561 \uc0d8\ud50c\uc744 \ud1b5\ud574 \uacbd\ub9e4 \uc8fc\ucd5c\uc790\uac00 \uc9c1\uc811 \ud655\uc778\ud560 \uc218 \uc788\ub294 \uacbd\uc6b0\uac00 \uc774\uc5d0 \ud574\ub2f9\ud55c\ub2e4.<br>\ubc18\uba74, \uac1c\uc778\uc740 \uc790\uc2e0\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9 \\(v_i\\)\ub97c \uac70\uc9d3\uc73c\ub85c \ubcf4\uace0\ud560 \uac00\ub2a5\uc131\uc774 \uc788\uc73c\uba70, \ub530\ub77c\uc11c <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uac1c\uc778\uc774 \uc790\uc2e0\uc758 \uc2e4\uc81c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9\uc744 \uc815\uc9c1\ud558\uac8c \ubcf4\uace0\ud558\ub3c4\ub85d \uc720\ub3c4\ud558\ub294 \uc778\uc13c\ud2f0\ube0c \uad6c\uc870\uac00 \ud544\uc694\ud558\ub2e4.<\/mark><br>\uc774 \ubaa8\ub378\uc744 \ubcf4\ub2e4 \uad6c\uccb4\uc801\uc73c\ub85c \uacf5\uc2dd\ud654\ud558\ub294 \ub0b4\uc6a9\uc744 \ub2e4\uc74c \uc808\uc5d0\uc11c \ub2e4\ub8ec\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2.2. Mechanism Design<\/h3>\n\n\n\n<p>\uba54\ucee4\ub2c8\uc998 \ub0b4\uc5d0\uc11c \ucc38\uac00\uc790\uc758 \ud6a8\uc6a9 \ud568\uc218(utility function)\ub97c \uad6c\uccb4\uc801\uc73c\ub85c \uc815\uc758\ud558\uace0, \uc774 \ud568\uc218\uac00 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubcf4\uc7a5\uacfc \uc5b4\ub5bb\uac8c \uad00\ub828\ub418\ub294\uc9c0\ub97c \uc124\uba85\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uac01 \uac1c\uc778 i\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \uc54c\uc9c0 \ubabb\ud558\ub294 \ub2e8\uc77c \ub9e4\uac1c\ubcc0\uc218(single-parameter) \ube44\uc6a9 \ud568\uc218 <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\\(c(v_i, \\cdot)\\)<\/mark>\ub97c \uac00\uc9c0\uace0 \uc788\uc73c\uba70, \uc774\ub294 \\(v_i\\)\ub77c\ub294 \ub9e4\uac1c\ubcc0\uc218\ub85c \ud45c\ud604\ub41c\ub2e4. \uc5ec\uae30\uc11c <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\\(c(v_i, \\epsilon)\\)<\/mark>\ub294 \uac1c\uc778 i\uac00 \uc790\uc2e0\uc758 \ub370\uc774\ud130\ub97c \\(\\epsilon\\)-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubc29\uc2dd\uc73c\ub85c \uc0ac\uc6a9\ud560 \ub54c \ubd80\ub2f4\ud574\uc57c \ud558\ub294 \ube44\uc6a9\uc744 \ub098\ud0c0\ub0b8\ub2e4.<\/p>\n\n\n\n<p>\ube44\uc6a9 \ud568\uc218\ub294 \uc815\uaddc\ud654(normalized)\ub418\uc5b4 \uc788\uc73c\uba70, \ubaa8\ub4e0 \\(v_i\\)\uc5d0 \ub300\ud574 \\(c(v_i, 0) = 0\\)\uc744 \ub9cc\uc871\ud55c\ub2e4. \ub610\ud55c, \uc774 \ud568\uc218\ub294 \uc5f0\uc18d \ud568\uc218(continuous function)\ub77c\uace0 \uac00\uc815\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc6b0\ub9ac\ub294 \ub450 \uac00\uc9c0 \ubaa8\ub378\uc744 \uc5f0\uad6c\ud55c\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uccab \ubc88\uc9f8 \ubaa8\ub378\uc5d0\uc11c\ub294 \uac1c\uc778\uc758 \ub370\uc774\ud130\uac00 \ub2e8\uc21c\ud788 \uac1c\uc778\uc801\uc778 \ube44\ud2b8 \\(b_i\\) \ud558\ub098\ub85c\ub9cc \ud45c\ud604\ub418\ub294 \uacbd\uc6b0\ub97c \ub2e4\ub8ec\ub2e4.<\/li>\n\n\n\n<li>\ub450 \ubc88\uc9f8 \ubaa8\ub378\uc5d0\uc11c\ub294 \uac1c\uc778\uc758 \ub370\uc774\ud130\uac00 \\((v_i, b_i)\\) \uc30d\uc73c\ub85c \uad6c\uc131\ub418\uc5b4 \uc788\uc73c\uba70, \uac1c\uc778\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9\ub3c4 \ud3ec\ud568\ub418\ub294 \uacbd\uc6b0\ub97c \ub2e4\ub8ec\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p>\uac01 \uac1c\uc778\uc758 \ube44\uc6a9 \ud568\uc218\ub294 \uacf5\uac1c\uc801\uc73c\ub85c \uc54c\ub824\uc9c4 \ub3d9\uc77c\ud55c \ud568\uc218 \uacc4\uc5f4(family)\uc5d0 \uc18d\ud558\uc9c0\ub9cc, \ub9e4\uac1c\ubcc0\uc218 \\(v_i\\) \uac12 \uc790\uccb4\ub294 \uac1c\uc778\ub9cc \uc54c\uace0 \uc788\uc73c\uba70, \uc774\ub97c \uba54\ucee4\ub2c8\uc998\uc5d0 \ubcf4\uace0\ud574\uc57c \ud55c\ub2e4. \ub530\ub77c\uc11c \uba54\ucee4\ub2c8\uc998\uc740 \uac1c\uc778\uc774 \uc790\uc2e0\uc758 \\(v_i\\) \uac12\uc744 \uc815\uc9c1\ud558\uac8c \ubcf4\uace0\ud558\ub3c4\ub85d \uc720\ub3c4\ud558\ub294 \uc124\uacc4\uac00 \ud544\uc694\ud558\ub2e4.<\/p>\n\n\n\n<p>\uc6b0\ub9ac\uc758 \uc5f0\uad6c \uacb0\uacfc\uac00 \uc720\ud6a8\ud558\uae30 \uc704\ud574, \ube44\uc6a9 \ud568\uc218 \uacc4\uc5f4\uc740 \\(\\epsilon\\)\uc5d0 \ub300\ud574 \uc804\uccb4 \uc21c\uc11c(total ordering) \uad00\uacc4\ub97c \ub9cc\uc871\ud574\uc57c \ud55c\ub2e4. \uc989, \uc784\uc758\uc758 \uac1c\uc778 \\(i \\neq j\\) \ubc0f \ubaa8\ub4e0 \\(\\epsilon\\)\uc5d0 \ub300\ud574,<\/p>\n\n\n\n<p>\\(c(v_i, \\epsilon) \\leq c(v_j, \\epsilon) \\quad \\text{if and only if} \\quad v_i \\leq v_j\\)<\/p>\n\n\n\n<p>\u2192 \\(v_i\\)\uac00 \uc791\uc744\uc218\ub85d, \uac1c\uc778\uc740 \uc790\uc2e0\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uc0c1\ub300\uc801\uc73c\ub85c \ub35c \uc911\uc694\ud558\uac8c \uc5ec\uae34\ub2e4.<br>\ub530\ub77c\uc11c \ub3d9\uc77c\ud55c \\(\\epsilon\\)\uc5d0\uc11c \ubcf4\ud638 \ube44\uc6a9 \\(c(v_i, \\epsilon)\\)\ub3c4 \ub0ae\uc544\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc774 \uc131\uc9c8\uc744 \ub9cc\uc871\ud558\ub294 \uc790\uc5f0\uc2a4\ub7ec\uc6b4 \ube44\uc6a9 \ud568\uc218\uc758 \uc608\uc2dc\ub294 \ub2e4\uc74c\uacfc \uac19\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc120\ud615 \ube44\uc6a9 \ud568\uc218(linear cost function): \\(c(v_i, \\epsilon) = v_i \\epsilon\\)<\/li>\n\n\n\n<li>\uc9c0\uc218\ud615 \ube44\uc6a9 \ud568\uc218(exponential cost function): \\(c(v_i, \\epsilon) = \\exp(\\epsilon v_i)\\)<\/li>\n\n\n\n<li>\uc774\ucc28 \ube44\uc6a9 \ud568\uc218(quadratic cost function): \\(c(v_i, \\epsilon) = v_i \\epsilon^2\\)<\/li>\n<\/ul>\n\n\n\n<p>\uc704\uc640 \uac19\uc740 \uc5ec\ub7ec \ud615\ud0dc\uc758 \ube44\uc6a9 \ud568\uc218\uac00 \uc0ac\uc6a9\ub420 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uba54\ucee4\ub2c8\uc998 M\uc740 \uc785\ub825\uac12\uc73c\ub85c<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\ube44\uc6a9 \ub9e4\uac1c\ubcc0\uc218 \ubca1\ud130 \\(v = (v_1, \\dots, v_n)\\) \uc640<\/li>\n\n\n\n<li>\uac1c\uc778\uc801\uc778 \ube44\ud2b8 \uac12 \ubca1\ud130 \\(b = (b_1, \\dots, b_n)\\)<\/li>\n<\/ul>\n\n\n\n<p>\ub97c \ubc1b\uc544\uc11c, \ub2e4\uc74c\uc744 \ucd9c\ub825\ud55c\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc5b4\ub5a4 \ud1b5\uacc4\ub7c9 \\(\\hat{s}\\)\uc5d0 \ub300\ud55c \ucd94\uc815\uac12(estimate of some statistic \\(\\hat{s}\\))<\/li>\n\n\n\n<li>\ub370\uc774\ud130 \ubd84\uc11d\uac00\ub85c\ubd80\ud130 \uc218\uc9d1\ud55c \ucd1d \uc9c0\ubd88 \uae08\uc561(payment), \uc774 \uae08\uc561\uc740 \ucc38\uac00\uc790\ub4e4\uc5d0\uac8c \ubd84\ubc30\ub428<\/li>\n<\/ul>\n\n\n\n<p>\uc6b0\ub9ac\ub294 \ub2e4\uc74c\uc758 \ub450 \uac00\uc9c0 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubaa8\ub378\uc744 \uace0\ub824\ud55c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2.3. Valuing Differential Privacy<\/h3>\n\n\n\n<p>\uc774 \uc808\uc5d0\uc11c\ub294 \uac1c\uc778\uc774 \uc790\uc2e0\uc758 \ub370\uc774\ud130\uac00 \\(\\epsilon\\)-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubc29\uc2dd\uc73c\ub85c \uc0ac\uc6a9\ub420 \ub54c \ubc1c\uc0dd\ud558\ub294 \ube44\uc6a9\uc744 \uc815\ub7c9\ud654\ud560 \uc218 \uc788\uc5b4\uc57c \ud558\ub294 \uc774\uc720\ub97c \uc124\uba85\ud55c\ub2e4.<\/p>\n\n\n\n<p>Fact 2. \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uac00 \ud568\uc218 \ud569\uc131(composition)\uacfc\ub3c4 \ud638\ud658\ub41c\ub2e4\ub294 \uc758\ubbf8\uc774\ub2e4. \uc989, \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uac70\uce5c \ub370\uc774\ud130\ub77c\uba74, \uadf8 \uacb0\uacfc\ub97c \uc774\uc6a9\ud574 \ucd94\uac00\uc801\uc778 \ucc98\ub9ac\ub97c \ud558\ub354\ub77c\ub3c4 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubcf4\uc7a5\uc774 \uc720\uc9c0\ub41c\ub2e4\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc0ac\ub78c\ub4e4\uc740 \ubcf4\ud1b5 \uc790\uc2e0\uc758 \uae30\ub300 \ud6a8\uc6a9(\ubbf8\ub798\uc5d0 \uc5bb\uc744 \uc218 \uc788\ub294 \uc774\uc775)\uc774 \uc904\uc5b4\ub4dc\ub294 \uac83\uc744 \uc6d0\ud558\uc9c0 \uc54a\ub294\ub2e4. \ub9cc\uc57d \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud588\uc744 \ub54c\uc758 \uae30\ub300 \ud6a8\uc6a9\uc774 \uc904\uc5b4\ub4e0\ub2e4\uba74, \ub2f9\uc5f0\ud788 \uadf8\uc5d0 \ub300\ud55c \ubcf4\uc0c1\uc744 \ubc1b\uc544\uc57c \ud55c\ub2e4. \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uac00 \uc81c\uacf5\ub41c\ub2e4\uba74, \uae30\ub300 \ud6a8\uc6a9\uc758 \ubcc0\ud654\ub294 \ucd5c\ub300 (exp(\u03b5) &#8211; 1) \ubc30\ub9cc\ud07c \ubcc0\ud560 \uc218 \uc788\ub2e4. \uc989, \ub370\uc774\ud130 \uc81c\uacf5\uc790\uac00 \uc783\uc744 \uc218 \uc788\ub294 \ud6a8\uc6a9 \uc190\uc2e4\uc744 \ubcf4\uc0c1\ud558\ub824\uba74, \ube44\uc6a9 \ud568\uc218\ub97c \ub2e4\uc74c\uacfc \uac19\uc774 \uc815\uc758\ud558\ub294 \uac83\uc774 \ud569\ub9ac\uc801\uc774\ub2e4.<\/p>\n\n\n\n<p>\\(c(v_i, \\epsilon_i) = (e^{\\epsilon_i} &#8211; 1) v_i\\)<\/p>\n\n\n\n<p>\uc5ec\uae30\uc11c, \\(v_i\\)\ub294 \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud558\uc9c0 \uc54a\uc558\uc744 \ub54c \uac1c\uc778\uc774 \uae30\ub300\ud558\ub294 \ubbf8\ub798 \ud6a8\uc6a9, \\(\\epsilon_i\\)\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \uc81c\uacf5\ud558\ub294 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc218\uc900\uc774\ub2e4.<\/p>\n\n\n\n<p>\ud604\uc2e4\uc5d0\uc11c\ub294 \\(\\epsilon\\)\uc774 \uc544\uc8fc \uc791\uc740 \uacbd\uc6b0\uac00 \ub9ce\ub2e4. \uc9c0\uc218 \ud568\uc218(exp(\u03b5))\ub294 \uc791\uc740 \uac12\uc5d0\uc11c\ub294 \uac70\uc758 \uc120\ud615\uc801(\u03b5)\uc73c\ub85c \ub3d9\uc791\ud558\uae30 \ub54c\ubb38\uc5d0, \ube44\uc6a9 \ud568\uc218\ub97c \ub354 \ub2e8\uc21c\ud558\uac8c \ub2e4\uc74c\uacfc \uac19\uc774 \uadfc\uc0ac\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\\(c(v_i, \\epsilon_i) \\approx \\epsilon_i v_i\\)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3. Characterizing Accurate Mechanisms<\/h2>\n\n\n\n<p>\uc774 \uc808\uc5d0\uc11c\ub294 \uc815\ud655\ub3c4\ub97c \ubcf4\uc7a5\ud558\uae30 \uc704\ud574 \uac01 \uac1c\uc778\uc73c\ub85c\ubd80\ud130 \uba54\ucee4\ub2c8\uc998\uc774 \uad6c\ub9e4\ud574\uc57c \ud558\ub294 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc758 \uc591\uc5d0 \ub300\ud55c \ud544\uc694\ud558\uace0 \ucda9\ubd84\ud55c \uc870\uac74\uc744 \uc81c\uc2dc\ud55c\ub2e4. \ud2b9\uc815 \uc815\ud655\ub3c4 \uc218\uc900\uc744 \uc5bb\uae30 \uc704\ud574, \uc6b0\ub9ac\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \ucd5c\uc18c\ud55c \u01eb \ub2e8\uc704\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c, \uc801\uc5b4\ub3c4 |H|\uba85\uc758 \uac1c\uc778\uc73c\ub85c\ubd80\ud130 \uad6c\ub9e4\ud574\uc57c \ud55c\ub2e4\uace0 \ubcf4\uc5ec\uc900\ub2e4. \uc5ec\uae30\uc11c \u01eb\uacfc |H|\uc758 \uac12\uc740 \uc6d0\ud558\ub294 \uc815\ud655\ub3c4\uc5d0 \ub530\ub77c \ub2ec\ub77c\uc9c4\ub2e4. \uc6b0\ub9ac\ub294 \uc774\ub7ec\ud55c \uc870\uac74\ub4e4\uc774 \uba54\ucee4\ub2c8\uc998\uc758 \uc9c4\uc2e4\uc131 \uc694\uad6c\uc0ac\ud56d(truthfulness requirements)\uacfc\ub294 \ubb34\uad00\ud558\uac8c, \uc815\ud655\ub3c4\ub97c \ub2ec\uc131\ud558\uae30 \uc704\ud55c \ud544\uc694\uc131\uc5d0\uc11c\ub9cc \ubc1c\uc0dd\ud55c\ub2e4\uace0 \uac15\uc870\ud55c\ub2e4. \uc774\ub7ec\ud55c \uc870\uac74\ub4e4\uc740 \ubbfc\uac10\ud55c \uac12 \ubaa8\ub378(sensitive value model)\uacfc \ube44\ubbfc\uac10\ud55c \uac12 \ubaa8\ub378(insensitive value model) \ubaa8\ub450\uc5d0 \uc801\uc6a9\ub41c\ub2e4. \uc774\ub294 \uac1c\uc778 \uc815\ubcf4 \uacbd\ub9e4 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\ub97c \ud06c\uac8c \ub2e8\uc21c\ud654\uc2dc\ud0a8\ub2e4. \uc65c\ub0d0\ud558\uba74, \uc774\ub97c \ud1b5\ud574 \uc6b0\ub9ac\ub294 \ub2e4\uc911 \ub2e8\uc704 \uc870\ub2ec \uacbd\ub9e4(multi-unit procurement auction)\uc5d0\ub9cc \uc9d1\uc911\ud558\uba74 \ub418\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n\n\n\n<p>Theorem 3.1. (\uc815\ud655\ub3c4\uc5d0 \ub300\ud55c \uc870\uac74)<\/p>\n\n\n\n<p>\\(0 &lt; \\alpha &lt; 1\\)\uc77c \ub54c, \u03b1\u00b7n\/4-\uc815\ud655\uc131(\u03b1\u00b7n\/4-accuracy)\uc744 \ub9cc\uc871\ud558\ub294 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uba54\ucee4\ub2c8\uc998\uc740 \ub2e4\uc74c \uc870\uac74\uc744 \ub9cc\uc871\ud574\uc57c \ud55c\ub2e4:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\ubaa8\ub4e0 \\(i \\in H\\)\uc5d0 \ub300\ud574 \\(\\epsilon_i \\geq \\frac{1}{\\alpha n}\\).<\/li>\n\n\n\n<li>\\(|H| \\geq (1 &#8211; \\alpha)n\\).<\/li>\n<\/ol>\n\n\n\n<p>Proof. M\uc744 \u03b1\u00b7n\/4-\uc815\ud655\uc131\uc744 \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc774\ub77c\uace0 \ud558\uc790. \ub610\ud55c, \\(H \\subseteq [n]\\)\uc744 \\(\\epsilon_i \\geq \\frac{1}{\\alpha n}\\)\uc744 \ub9cc\uc871\ud558\ub294 \uac1c\uc778\ub4e4\uc758 \uc9d1\ud569\uc73c\ub85c \uc815\uc758\ud558\uc790.<\/p>\n\n\n\n<p>\ubaa8\uc21c\uc744 \uc704\ud55c \uac00\uc815: \\(|H| &lt; (1 &#8211; \\alpha)n\\)\uc774\ub77c\uace0 \uac00\uc815\ud558\uc790. \uadf8\ub7ec\uba74, \\(H = [n] \\setminus H\\)\ub85c \uc815\uc758\ud560 \uc218 \uc788\ub2e4. \uc774 \uacbd\uc6b0, \\(|\\bar{H}| &gt; \\alpha n\\)\uc774\ubbc0\ub85c, \uc9d1\ud569 \\(S = \\{x \\in \\mathbb{R} : |x &#8211; s| &lt; \\frac{\\alpha n}{4} \\}\\), \uc5ec\uae30\uc11c \\(s = \\sum_{i=1}^{n} b_i\\)\ub77c\uace0 \uc815\uc758\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc815\ud655\ub3c4\uc5d0 \ub530\ub77c \uba54\ucee4\ub2c8\uc998 M(v, D)\uc758 \ucd9c\ub825\uc778 \ucd94\uc815\uce58 \\(\\hat{s}\\)\ub294 \ub2e4\uc74c\uc744 \ub9cc\uc871\ud574\uc57c \ud55c\ub2e4:<\/p>\n\n\n\n<p>\\(Pr[\\hat{s} \\in S] \\geq \\frac{2}{3}\\).<\/p>\n\n\n\n<p>\uc774\uc81c, \\(H_1 = \\{i \\in H : b_i = 1\\}\\)\uacfc \\(H_0 = \\{i \\in H : b_i = 0\\}\\)\uc73c\ub85c H\ub97c \ub450 \uc9d1\ud569\uc73c\ub85c \ubd84\ud560\ud560 \uc218 \uc788\ub2e4. \uc774\ub54c, \\(H_0\\)\uc640 \\(H_1\\)\uc740 H\uc758 \ubd84\ud560\uc744 \uc774\ub8e8\uba70, \ub2e4\uc74c\uc774 \uc131\ub9bd\ud55c\ub2e4:<\/p>\n\n\n\n<p>\\(\\max(|H_0|, |H_1|) &gt; \\frac{\\alpha n}{2}\\).<\/p>\n\n\n\n<p>\uc190\uc2e4 \uc5c6\uc774 \uc77c\ubc18\uc131\uc744 \uc783\uc9c0 \uc54a\uae30 \uc704\ud574 \\(|H_0| &gt; \\frac{\\alpha n}{2}\\)\ub77c\uace0 \uac00\uc815\ud558\uc790. \uc774\uc81c, \\(T \\subseteq H_0\ub85c\uc11c |T| = \\frac{\\alpha n}{2}\\)\uc774\uace0, \ub370\uc774\ud130\uc14b \\(D{\\prime}\\)\ub294 T\uc5d0 \ud3ec\ud568\ub41c \uac01 \\(b_i\\) \uac12\uc744 1\ub85c \ubcc0\uacbd\ud55c \ub370\uc774\ud130\uc14b\uc774\ub77c\uace0 \ud558\uc790. \uc774\ub54c, \\(D{\\prime}\\)\uc640 D\ub294 \ud574\ubc0d \uac70\ub9ac\uac00 \\(|T| = \\frac{\\alpha n}{2}\\)\uc774\uace0, T\uc758 \uc778\ub371\uc2a4\uc5d0\uc11c\ub9cc \uc11c\ub85c \ub2e4\ub974\ub2e4.<\/p>\n\n\n\n<p>\uc774\ub54c, \uba54\ucee4\ub2c8\uc998\uc758 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ud2b9\uc131\uc744 \uc0ac\uc6a9\ud558\uc5ec, \uc0ac\uc2e4 1\uc744 \uc801\uc6a9\ud558\uba74 \ub2e4\uc74c\uc774 \uc131\ub9bd\ud55c\ub2e4:<\/p>\n\n\n\n<p>\\(Pr[\\hat{s}{\\prime} \\in S] \\geq e^{-\\frac{2}{\\alpha n}} \\cdot Pr[\\hat{s} \\in S]\\)<\/p>\n\n\n\n<p>\uc774\ud6c4, \\(\\hat{s}\uc640 \\hat{s}{\\prime}\\)\uc758 \ucc28\uc774\ub97c \uace0\ub824\ud558\uc5ec \\(\\hat{s}{\\prime} \\in S\\)\uc77c \ub54c \uc0bc\uac01 \ubd80\ub4f1\uc2dd(triangle inequality)\uc744 \uc774\uc6a9\ud558\uc5ec \ubaa8\uc21c\uc744 \uc720\ub3c4\ud560 \uc218 \uc788\ub2e4. \uc774 \uacfc\uc815\uc5d0\uc11c \\(\\hat{s}{\\prime}\\)\uc640 \uc2e4\uc81c \uac12 \\(s{\\prime}\\)\uc758 \ucc28\uc774\uac00 \\(\\frac{\\alpha n}{4}\\)\ub97c \ucd08\uacfc\ud558\ub294 \ud655\ub960\uc774 1\/3\ubcf4\ub2e4 \ud074 \uc218 \uc5c6\ub2e4\ub294 \ubaa8\uc21c\uc744 \ub3c4\ucd9c\ud558\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p>\ub530\ub77c\uc11c, \uba54\ucee4\ub2c8\uc998\uc774 \u03b1\u00b7n\/4-\uc815\ud655\uc131\uc744 \ub9cc\uc871\ud558\ub824\uba74 \uc801\uc5b4\ub3c4 \\((1-\\alpha)n\\)\uba85\uc758 \uac1c\uc778\uc73c\ub85c\ubd80\ud130 \\(\\epsilon_i \\geq \\frac{1}{\\alpha n}\\)\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uad6c\ub9e4\ud574\uc57c \ud55c\ub2e4\ub294 \uacb0\ub860\uc744 \ub3c4\ucd9c\ud560 \uc218 \uc788\ub2e4.<br>(\uac01 \uac1c\uc778\uc5d0\uac8c \ucd5c\uc18c\ud55c \u03b5 \u2265 1 \/ (\u03b1n) \uc815\ub3c4\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc218\uc900\uc744 \ubcf4\uc7a5\ud574\uc57c \ud55c\ub2e4.)<\/p>\n\n\n\n<p>\u2192 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ubcf4\uc7a5\ud558\uba74\uc11c\ub3c4 \uc6d0\ud558\ub294 \uc218\uc900\uc758 \uc815\ud655\ub3c4\ub97c \ub2ec\uc131\ud558\uae30 \uc704\ud574 \uba54\ucee4\ub2c8\uc998\uc774 \ucd5c\uc18c\ud55c \uc5b4\ub290 \uc815\ub3c4\uc758 \uac1c\uc778\uc815\ubcf4\ub97c \uad6c\ub9e4\ud574\uc57c \ud558\ub294\uc9c0\ub97c \uc124\uba85\ud558\ub294 \uac83\uc774\ub2e4.<br>\uc989, \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \uc815\ud655\ud55c \ud1b5\uacc4\uac12\uc744 \uc5bb\uace0 \uc2f6\ub2e4\uba74, \uc77c\uc815 \uc218\uc900 \uc774\uc0c1\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638(\u03b5)\ub97c \ud2b9\uc815 \uc218\uc758 \uac1c\uc778\ub4e4\uc5d0\uac8c \uc81c\uacf5\ud574\uc57c \ud55c\ub2e4\ub294 \uc758\ubbf8\uc774\ub2e4.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">4. Deriving Truthful Mechanisms<\/h2>\n\n\n\n<p>\uac1c\uc778 \ub370\uc774\ud130 \uac70\ub798\ub97c \uacbd\ub9e4 \ubb38\uc81c\ub85c \ubcc0\ud658\ud558\uc5ec \ud574\uacb0\ud558\ub294 \uc811\uadfc\ubc95\uc744 \uc0ac\uc6a9\ud55c\ub2e4.<br>\uc989, \ub370\uc774\ud130 \uad6c\ub9e4\ub97c \ub2e4\uc911 \ub2e8\uc704 \uc870\ub2ec \uacbd\ub9e4(Multi-Unit Procurement Auction) \ubb38\uc81c\ub85c \ubcf4\uace0, \uc774\ub97c \ud1b5\ud574 \ucd5c\uc801\uc758 \uac00\uaca9 \ucc45\uc815 \ubc0f \ub370\uc774\ud130 \uac70\ub798 \ubc29\uc2dd\uc744 \ub3c4\ucd9c\ud55c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.1 Maximizing Accuracy Subject to a Budget Constraint<\/h3>\n\n\n\n<p>1) \uccab\ubc88\uc9f8 \uba54\ucee4\ub2c8\uc998: \uc815\ud655\ub3c4 \ubaa9\ud45c(fixed accuracy goal) \ub97c \uac00\uc9c4 \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \ucd1d \uc9c0\ubd88 \ube44\uc6a9\uc744 \ucd5c\uc18c\ud654\ud558\uba74\uc11c \ubaa9\ud45c \uc815\ud655\ub3c4\ub97c \ub2ec\uc131\ud558\ub824\ub294 \uacbd\uc6b0, \uc6b0\ub9ac\ub294 \ud45c\uc900 VCG (Vickrey-Clarke-Groves) \uba54\ucee4\ub2c8\uc998\uc774 envy-free(\uc9c8\ud22c \uc5c6\uc74c) \uba54\ucee4\ub2c8\uc998 \uc911 \ucd5c\uc801\uc784\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<p>* envy-free: \uc790\uc2e0 i\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \uace0\ub824\ud560 \ub54c, \ub2e4\ub978 \uac1c\uc778 j\uc758 \uacb0\uacfc\ub97c \ub354 \uc120\ud638\ud558\uc9c0 \uc54a\uc544\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \uace0\uc815\ub41c \uc815\ud655\ub3c4 \ubaa9\ud45c\ub97c \uac00\uc9c0\uace0 \uc788\uc5b4, \ud1b5\uacc4\ub97c \ucd94\uc815\ud560 \ub54c \uc77c\uc815 \uc218\uc900 \uc774\uc0c1\uc758 \uc815\ud655\ub3c4\ub97c \uc720\uc9c0\ud574\uc57c \ud55c\ub2e4.<br>\uc774 \ub54c \ud074\ub798\uc2dd Vickrey Auction (2\ub4f1 \uac00\uaca9 \uacbd\ub9e4, \ube45\ub9ac \uacbd\ub9e4)\ub97c \uc801\uc6a9\ud558\uc5ec<br>\u2022 \ucc38\uac00\uc790(\ub370\uc774\ud130 \uc81c\uacf5\uc790)\ub4e4\uc774 \uc790\uc2e0\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \uc81c\uc548.<br>\u2022 \ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \uac00\uc7a5 \ub0ae\uc740 \uac00\uaca9\uc744 \uc81c\uc2dc\ud55c \ub370\uc774\ud130 \uc81c\uacf5\uc790\ub85c\ubd80\ud130 \uad6c\ub9e4.<br>\u2022 \ub099\ucc30\uc790\ub294 \ub450 \ubc88\uc9f8\ub85c \ub0ae\uc740 \uac00\uaca9\uc744 \uc81c\uc2dc\ud55c \ucc38\uac00\uc790\uc758 \uac00\uaca9\uc73c\ub85c \ubcf4\uc0c1\uc744 \ubc1b\uc74c.<br>\u2022 \uc774\ub97c \ud1b5\ud574 \uc9c4\uc2e4\ud55c \uc751\ub2f5(truthful bidding)\uc744 \uc720\ub3c4\ud560 \uc218 \uc788\uc74c.<\/p>\n\n\n\n<p>&#8211; \ub099\ucc30\uc790\ub294 \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub294 \uac1c\uc778(\ub370\uc774\ud130 \uc81c\uacf5\uc790)\uc744 \uc758\ubbf8\ud55c\ub2e4.<br>&#8211; \ub099\ucc30\uc790\ub294 \uac00\uc7a5 \ub0ae\uc740 \uac00\uaca9\uc744 \uc81c\uc2dc\ud55c \ucc38\uac00\uc790\uc774\ub2e4.<br>&#8211; \ud558\uc9c0\ub9cc \ub099\ucc30\uc790\ub294 \uc790\uc2e0\uc774 \uc81c\uc2dc\ud55c \uac00\uaca9\uc774 \uc544\ub2c8\ub77c, \ub450 \ubc88\uc9f8\ub85c \ub0ae\uc740 \uac00\uaca9\uc744 \uc81c\uc2dc\ud55c \ucc38\uac00\uc790\uc758 \uac00\uaca9\uc744 \ubc1b\ub294\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Vickrey \uacbd\ub9e4\uac00 \uc9c4\uc2e4\ud55c \uc751\ub2f5\uc744 \uc720\ub3c4\ud558\ub294 \uc774\uc720<\/h5>\n\n\n\n<p>\u2022 \ub108\ubb34 \ub192\uc740 \uac00\uaca9\uc744 \ubd80\ub974\uba74 \ub099\ucc30\ub418\uc9c0 \uc54a\uc744 \uc704\ud5d8\uc774 \uc788\uc74c.<br>\u2022 \ub108\ubb34 \ub0ae\uc740 \uac00\uaca9\uc744 \ubd80\ub974\uba74 \uc2e4\uc81c \ube44\uc6a9\ubcf4\ub2e4 \uc801\uc740 \ubcf4\uc0c1\uc744 \ubc1b\uc744 \uc704\ud5d8\uc774 \uc788\uc74c.<br>\u2022 \ud558\uc9c0\ub9cc \uc790\uc2e0\uc758 \uc2e4\uc81c \ube44\uc6a9\uc744 \uc815\uc9c1\ud558\uac8c \ubcf4\uace0\ud558\uba74,<br>\u2022 \ub099\ucc30\ub420 \uac00\ub2a5\uc131\uc774 \ub192\uc544\uc9c0\uba74\uc11c\ub3c4,<br>\u2022 \ub450 \ubc88\uc9f8\ub85c \ub0ae\uc740 \uac00\uaca9\uc744 \ubc1b\uc744 \uc218 \uc788\uae30 \ub54c\ubb38\uc5d0 \ud56d\uc0c1 \ubcf4\uc0c1\uc744 \ubc1b\uc744 \uc218 \uc788\ub294 \uc548\uc804\ud55c \uc804\ub7b5\uc774 \ub428.<\/p>\n\n\n\n<p>Observation 4.3. \ubaa8\ub4e0 i, j\uc5d0 \ub300\ud574 \\(\\epsilon_i > 0, \\epsilon_j > 0\\) \uc774\ub77c\uba74 \ubc18\ub4dc\uc2dc \\(p_i = p_j\\)\uac00 \uc131\ub9bd\ud574\uc57c \ud55c\ub2e4.<br>\uc774\ub7ec\ud55c \uba54\ucee4\ub2c8\uc998\uc744 &#8216;\uace0\uc815 \uad6c\ub9e4(fixed purchase) \uba54\ucee4\ub2c8\uc998&#8217;\uc774\ub77c\uace0 \ubd80\ub978\ub2e4.<br>\uc989 envy free fixed purchase mechanisms\uc740 \ubaa8\ub4e0 \uac1c\uc778\uc815\ubcf4\ub97c \uad6c\ub9e4\ud558\ub294 \uac1c\uc778\ub4e4\uc5d0\uac8c \ub3d9\uc77c\ud55c \uac00\uaca9\uc744 \uc9c0\ubd88\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>Proposition 4.4. FairQuery\uc758 \ucd5c\uc801\uc131 \uc99d\uba85<\/p>\n\n\n\n<p>FairQuery\ub294 \ubaa8\ub4e0 \uc9c4\uc2e4\uc131(truthful), \uac1c\ubcc4 \ud569\ub9ac\uc131(individually rational), \uc2dc\uae30\uc2ec \uc5c6\ub294(envy-free) \uace0\uc815 \uad6c\ub9e4 \uba54\ucee4\ub2c8\uc998 \uc911\uc5d0\uc11c, \uc8fc\uc5b4\uc9c4 \uc608\uc0b0 B \ub0b4\uc5d0\uc11c \ucd5c\uc801\uc758 \uc815\ud655\ub3c4\ub97c \ub2ec\uc131\ud55c\ub2e4.<\/p>\n\n\n\n<p>Proof. <\/p>\n\n\n\n<p>1. FairQuery\uac00 \uc2dc\uae30\uc2ec \uc5c6\ub294 \uace0\uc815 \uad6c\ub9e4 \uba54\ucee4\ub2c8\uc998\uc778\uc9c0<br>\ubaa8\ub4e0 \uc120\ud0dd\ub41c \uac1c\uc778\uc5d0\uac8c \ub3d9\uc77c\ud55c \\(\\epsilon_i = \\frac{1}{n-k}\\) \uc218\uc900\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uad6c\ub9e4\ud55c\ub2e4.<\/p>\n\n\n\n<p>2. FairQuery\uac00 \uc608\uc0b0 \ub0b4\uc5d0\uc11c \ucd5c\uc801\uc758 \uc815\ud655\ub3c4\ub97c \ubcf4\uc7a5\ud558\ub294\uc9c0<br>k\uba85\uc758 \uac1c\uc778\uc774 \uc120\ud0dd\ub418\uc5c8\uc744 \ub54c, \ub2e4\uc74c \uc0ac\ub78c\uc774 \ucd94\uac00\ub85c \uc120\ud0dd\ub420 \uacbd\uc6b0\uc758 \uc870\uac74\uc744 \uace0\ub824\ud55c\ub2e4.<br>\uc120\ud0dd\ub418\uc9c0 \uc54a\uc740 \ub2e4\uc74c \uac1c\uc778 k+1\uc758 \ube44\uc6a9 \uc870\uac74\uc740<\/p>\n\n\n\n<p>\\(\\frac{v_{k+1}}{(n-k-1)} > \\frac{B}{k+1}\\)<\/p>\n\n\n\n<p>\ub9cc\uc57d k&#8217; > k\uc778 \ub2e4\ub978 \uba54\ucee4\ub2c8\uc998\uc774 \ub354 \ub9ce\uc740 \uac1c\uc778\uc744 \uc120\ud0dd\ud558\ub824\uba74 \\(p_{k+1} > B\/(k+1)\\)\uac00 \ub418\uc5b4\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc0c8\ub85c\uc6b4 \uac1c\uc778 k+1\uc774 \ud3ec\ud568\ub41c\ub2e4\uba74, \ubaa8\ub4e0 \uc120\ud0dd\ub41c \uac1c\uc778\uc5d0\uac8c \uc9c0\uae09\ub418\ub294 \uc9c0\ubd88\uae08 \\(p_i\\)\ub294 \ub2e4\uc74c \uc870\uac74\uc744 \ub9cc\uc871\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\\(p_{k+1} > \\frac{B}{k+1}\\)<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.2 Minimizing Payment Subject to an Accuracy Constraint<\/h3>\n\n\n\n<p>2) \ub450\ubc88\uc9f8 \uba54\ucee4\ub2c8\uc998: \uc608\uc0b0 \uc81c\ud55c(fixed budget) \ub0b4\uc5d0\uc11c \uc815\ud655\ub3c4\ub97c \ucd5c\ub300\ud654\ud558\ub824\ub294 \uacbd\uc6b0, \uc774\ub294 \ubcf4\ub2e4 \ud2b9\uc774\ud55c \ud615\ud0dc\uc758 \uc870\ub2ec \uacbd\ub9e4(procuring auction) \ubb38\uc81c\ub85c \ubcc0\ud658\ub41c\ub2e4.<\/p>\n\n\n\n<p>\ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \uc81c\ud55c\ub41c \uc608\uc0b0 \uc548\uc5d0\uc11c \ucd5c\ub300\ud55c \ub9ce\uc740 \uac1c\uc778\uc758 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\uc5ec, \uac00\ub2a5\ud55c \ud55c \ub192\uc740 \uc815\ud655\ub3c4\ub97c \ud655\ubcf4\ud558\ub824\uace0 \ud55c\ub2e4.<br>\uc989, \uc608\uc0b0\uc744 \ucd08\uacfc\ud558\uc9c0 \uc54a\ub294 \ubc94\uc704 \ub0b4\uc5d0\uc11c, \uac00\uc7a5 \ub9ce\uc740 \ub370\uc774\ud130\ub97c \uc5bb\ub294 \uac83\uc774 \ubaa9\ud45c\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \uad6c\ub9e4\uc790\uac00 \uac00\ub2a5\ud55c \ud55c \ub9ce\uc740 \ud310\ub9e4\uc790\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub824 \ud558\uba70, \uac01 \ud310\ub9e4\uc790\uc758 \ube44\uc6a9\uc774 \ub2e4\ub978 \ud310\ub9e4\uc790\uc758 \ud310\ub9e4 \uc5ec\ubd80\uc5d0 \ub530\ub77c \ub2ec\ub77c\uc9c8 \uc218 \uc788\ub294 \uad6c\uc870\ub97c \uac16\ub294\ub2e4.<br>\uc608\uc0b0 \uc81c\ud55c \uae30\ubc18, \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \uace0\uc815\ub41c \uc608\uc0b0\uc744 \uac00\uc9c0\uace0 \uc788\uc5b4 \uc608\uc0b0 \ub0b4\uc5d0\uc11c \ucd5c\ub300\ud55c \ub192\uc740 \uc815\ud655\ub3c4\ub97c \ubcf4\uc5ec\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc5f0\uad6c\uc5d0\uc11c\ub294 \uace0\uc815 \uac00\uaca9(fixed-price) \uba54\ucee4\ub2c8\uc998\uc744 \uc801\uc6a9\ud558\uc5ec \ucd5c\uc801\uc758 \ub370\uc774\ud130\ub97c \ud655\ubcf4\ud558\ub294 \ubc29\ubc95\uc744 \uc81c\uc548\ud55c\ub2e4.<br>\uc774 \uba54\ucee4\ub2c8\uc998\uc740 \uac01 \ucc38\uac00\uc790\uc5d0\uac8c \uc77c\uc815\ud55c \uac00\uaca9\uc744 \uc81c\uc2dc\ud558\uace0, \ud574\ub2f9 \uac00\uaca9\uc5d0 \ub3d9\uc758\ud558\ub294 \ucc38\uac00\uc790\ub4e4\uc758 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub294 \ubc29\uc2dd\uc774\ub2e4.<\/p>\n\n\n\n<p>1. \ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \ud2b9\uc815\ud55c \uac00\uaca9 p\ub97c \uacb0\uc815\ud568.<br>\u2022 \uc774 \uac00\uaca9\uc740 \ucc38\uac00\uc790\ub4e4\uc5d0\uac8c \ub3d9\uc77c\ud558\uac8c \uc801\uc6a9\ub418\ub294 \uace0\uc815\ub41c \uac00\uaca9\uc784.<br>\u2022 \uac00\uaca9\uc744 \ub108\ubb34 \ub0ae\uac8c \uc124\uc815\ud558\uba74 \ub9ce\uc740 \ucc38\uac00\uc790\ub4e4\uc774 \ucc38\uc5ec\ud558\uc9c0 \uc54a\uac8c \ub428.<br>\u2022 \uac00\uaca9\uc744 \ub108\ubb34 \ub192\uac8c \uc124\uc815\ud558\uba74 \uc801\uc740 \uc218\uc758 \ucc38\uac00\uc790\uc5d0\uac8c\ub9cc \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud560 \uc218 \uc788\uc5b4 \uc804\uccb4 \uc815\ud655\ub3c4\uac00 \ub5a8\uc5b4\uc9c8 \uc218 \uc788\uc74c.<\/p>\n\n\n\n<p>2. \ucc38\uac00\uc790\ub4e4\uc740 \uc81c\uc548\ub41c \uac00\uaca9 p\uc5d0 \ub3d9\uc758\ud560\uc9c0 \uacb0\uc815\ud568.<br>\u2022 \uc790\uc2e0\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9 \\(c_i(\\epsilon)\\)&nbsp;\ubcf4\ub2e4 \ub192\uc740 \uacbd\uc6b0: \ucc38\uac00\uc790\ub294 \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud568.<br>\u2022 \uc790\uc2e0\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9&nbsp;\\(c_i(\\epsilon)\\)&nbsp;\ubcf4\ub2e4 \ub0ae\uc740 \uacbd\uc6b0: \ucc38\uac00\uc790\ub294 \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud558\uc9c0 \uc54a\uc74c.<\/p>\n\n\n\n<p>3. \ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \uc608\uc0b0&nbsp; B&nbsp; \ub0b4\uc5d0\uc11c \ucd5c\ub300\ud55c \ub9ce\uc740 \ucc38\uac00\uc790\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud568.<\/p>\n\n\n\n<p>\u2022 \ub9cc\uc57d \uc81c\uc548\ub41c \uac00\uaca9\uc73c\ub85c \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud558\ub824\ub294 \ucc38\uac00\uc790\uac00 \ub108\ubb34 \ub9ce\uc73c\uba74, \uc77c\ubd80\ub9cc \uc120\ud0dd\ud574\uc57c \ud568.<br>\u2022 \ub9cc\uc57d \uc81c\uacf5\uc790\uac00 \ubd80\uc871\ud558\uba74, \uac00\uaca9\uc744 \uc870\uc815\ud558\uc5ec \ub354 \ub9ce\uc740 \ucc38\uac00\uc790\ub97c \ud655\ubcf4\ud574\uc57c \ud568.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\uc65c \uace0\uc815 \uac00\uaca9\uc744 \uc0ac\uc6a9\ud558\ub294\uac00?<\/h5>\n\n\n\n<p>\u2022 \ucc38\uac00\uc790\ub294 \uc790\uc2e0\uc758 \ube44\uc6a9\uc744 \uc228\uae30\uac70\ub098 \uc870\uc791\ud560 \uc720\uc778\uc774 \uc904\uc5b4\ub4e6<br>\u2022 \ubaa8\ub4e0 \ucc38\uac00\uc790\uac00 \uac19\uc740 \uac00\uaca9\uc744 \ubc1b\uae30 \ub54c\ubb38\uc5d0, \uac70\uc9d3\uc73c\ub85c \ub192\uc740 \uac00\uaca9\uc744 \uc81c\uc2dc\ud574\ub3c4 \ub354 \ub9ce\uc740 \ub3c8\uc744 \ubc1b\uc744 \uc218 \uc5c6\uc74c<br>\u2022 \ubcf5\uc7a1\ud55c \uac00\uaca9 \uc870\uc815 \uc5c6\uc774, \ud55c \ubc88\uc758 \uac00\uaca9 \uacb0\uc815\uc73c\ub85c \ucc38\uac00\uc790\ub4e4\uc758 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud560 \uc218 \uc788\uc74c<\/p>\n\n\n\n<p>\uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \uad6c\ub9e4\uc790\ub294 \uac00\ub2a5\ud55c \ud55c \ub9ce\uc740 \ud310\ub9e4\uc790\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub824 \ud558\uba70, \uac01 \ud310\ub9e4\uc790\uc758 \ube44\uc6a9\uc774 \ub2e4\ub978 \ud310\ub9e4\uc790\uac00 \ub370\uc774\ud130\ub97c \ud310\ub9e4\ud558\ub294\uc9c0 \uc5ec\ubd80\uc5d0 \ub530\ub77c \uacb0\uc815\ub418\ub294 \uad6c\uc870\ub97c \uac00\uc9c4\ub2e4.<br>\u2022 \uc774\ub7ec\ud55c \uc124\uc815\uc5d0\uc11c \uc6b0\ub9ac\ub294 \uace0\uc815 \uac00\uaca9(fixed-price) \uba54\ucee4\ub2c8\uc998 \uc911\uc5d0\uc11c \uac1c\ubcc4 \uc0ac\ub840\ubcc4(instance-by-instance)\ub85c \ucd5c\uc801\uc758 \uc9c4\uc2e4\uc131(truthful) \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc548\ud55c\ub2e4.<br>\u2022 \uc6b0\ub9ac\ub294 \uace0\uc815 \uac00\uaca9 \uba54\ucee4\ub2c8\uc998\uc744 \ube44\uad50 \uae30\uc900(benchmark)\uc73c\ub85c \uc0ac\uc6a9\ud558\uba70,<br>\uc774\ub294 \uae30\uc874\uc758 \ud504\ub77c\uc774\uc5b4-\ud504\ub9ac \uba54\ucee4\ub2c8\uc998 \uc124\uacc4(prior-free mechanism design)\uc5d0\uc11c \ud45c\uc900\uc801\uc778 \uc811\uadfc \ubc29\uc2dd\uc774\ub2e4.<\/p>\n\n\n\n<p>&#8211; \ub2e4\ub9cc, \uc774 \uc5f0\uad6c\uc758 \uc124\uc815\uc5d0\uc11c\ub294 \ubca0\uc774\uc9c0\uc548 \ucd5c\uc801(Bayesian-optimal) \uba54\ucee4\ub2c8\uc998\uc774 \uc54c\ub824\uc838 \uc788\uc9c0 \uc54a\uc73c\ubbc0\ub85c, \uace0\uc815 \uac00\uaca9 \uc811\uadfc\ubc95\uc744 \uc815\ub2f9\ud654\ud558\uac70\ub098 \uac1c\uc120\ud558\ub294 \uac83\uc774 \ud5a5\ud6c4 \uc5f0\uad6c \uacfc\uc81c.<\/p>\n\n\n\n<p>&#8211;<\/p>\n\n\n\n<p>\uace0\uc815\ub41c \uc815\ud655\ub3c4 \uc81c\uc57d k \ud558\uc5d0\uc11c \ucd5c\uc18c \ube44\uc6a9\uc73c\ub85c \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uace0\ub824\ud55c\ub2e4.<br>\uc815\ud655\ub3c4 k-\uc815\ud655\uc131\uc744 \ubcf4\uc7a5\ud558\uba74\uc11c, \uc9c0\ubd88\ud574\uc57c \ud558\ub294 \ube44\uc6a9\uc744 \ucd5c\uc18c\ud654\ud558\ub824\uba74 \uc5b4\ub5bb\uac8c \ud574\uc57c \ud558\ub294\uac00?<br>\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574, \ub2e4\uc911 \ub2e8\uc704 \uc870\ub2ec \uacbd\ub9e4(multi-unit procurement auction) \ubaa8\ub378\uc744 \uc0ac\uc6a9\ud558\uba70, VCG \uba54\ucee4\ub2c8\uc998\uc774 \ucd5c\uc801\uc784\uc744 \ubcf4\uc77c \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc815\ub9ac 3.3\uc5d0 \uc758\ud574, \uc815\ud655\ub3c4 \ubaa9\ud45c \\(\\alpha n\\)\uc744 \ub2ec\uc131\ud558\ub824\uba74 \\((1\/2 + \\ln 3) \\cdot \\alpha n\\) \ub9cc\ud07c\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uad6c\ub9e4\ud574\uc57c \ud55c\ub2e4. \uadf8\ub9ac\uace0 \uc774 \ubcf4\ud638\ub97c \ucd1d \\((1 &#8211; \\frac{\\alpha}{(1\/2 + \\ln 3)}) n\\)\uba85\uc758 \uac1c\uc778\uc73c\ub85c\ubd80\ud130 \uad6c\ub9e4\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uac01 \uac1c\uc778\uc740 \\((1\/2 + \\ln 3) \\cdot \\alpha n\\) \ub2e8\uc704\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ud310\ub9e4\ud55c\ub2e4\uace0 \uac00\uc815\ud560 \ub54c, \uac01 \uac1c\uc778\uc758 \ube44\uc6a9 \\(v_i\\)\uc740 \ud574\ub2f9 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub7c9\uc744 \ud310\ub9e4\ud558\ub294 \ucd1d \ube44\uc6a9\uc73c\ub85c \uc124\uc815\ub41c\ub2e4.<\/p>\n\n\n\n<p>\\(v_i = c_i((1\/2 + \\ln 3)an)\\)<\/p>\n\n\n\n<p>\ub530\ub77c\uc11c, \uc774 \ubb38\uc81c\ub294 \\((1 &#8211; \\frac{\\alpha}{(1\/2 + \\ln 3)}) n\\) \uac1c\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ub2e8\uc704\ub97c \uad6c\ub9e4\ud558\ub294 \uacbd\ub9e4 \ubb38\uc81c\ub85c \ubcc0\ud658\ub41c\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">MinCostAuction<\/h4>\n\n\n\n<p>\uc785\ub825: \ube44\uc6a9 \ubca1\ud130 \\(v_i\\), \ub370\uc774\ud130\ubca0\uc774\uc2a4 D, \uc815\ud655\ub3c4 \ubaa9\ud45c \\(\\alpha\\)<br>\ucd9c\ub825: \uc815\ud655\ub3c4 k\ub97c \ub9cc\uc871\ud558\ub294 \ub370\uc774\ud130 \\(\\hat{s}\\) \ubc0f \ube44\uc6a9 \\(p_i\\)<\/p>\n\n\n\n<p>\uc815\ud655\ub3c4 \ubaa9\ud45c \uae30\ubc18\uc73c\ub85c k \uacb0\uc815<br>\uac1c\uc778 k\uba85\uc744 \uc120\ud0dd\ud574\uc57c \ud558\ubbc0\ub85c k\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc124\uc815\ub41c\ub2e4.<\/p>\n\n\n\n<p>\\(k = [(1-\\alpha^{\\prime})n]\\)<\/p>\n\n\n\n<p>\uac1c\uc778\uc774 \uc81c\uacf5\ud558\ub294 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9 \\(v_i = c_i \\epsilon_i = c_i(1\/(n-k))\\)<\/p>\n\n\n\n<p>\ub370\uc774\ud130 \ucd94\uc815\uac12 \\(\\hat{s}\\)\ub294 \\(\\hat{s} = \\sum_{i=1}^{k} b_i + \\frac{n-k}{2} + \\text{Lap}(\\alpha{\\prime} n)\\)\uc73c\ub85c \uc124\uc815\ub41c\ub2e4.<\/p>\n\n\n\n<p>\uc120\ud0dd\ub418\uc9c0 \uc54a\uc740 \uac1c\uc778(i > k)\uc5d0\uac8c\ub294 \uc9c0\ubd88\uae08 \\(p_i = 0\\), \uc120\ud0dd\ub41c \uac1c\uc778(i \\(\\leq\\) k)\uc5d0\uac8c\ub294 \uc9c0\ubd88\uae08 \\(p_i = v_{k+1}\\).<br>\ub2e4\uc74c \ub099\ucc30\uc790\uc758 \ube44\uc6a9 \\(v_{k+1}\\)\uc744 \uc9c0\ubd88\ud558\ub3c4\ub85d \uc124\uacc4\ub41c\ub2e4. (\ud55c \ub2e8\uacc4 \ub0ae\uc740 \uac00\uaca9\uc744 \uae30\uc900\uc73c\ub85c \uc9c0\ubd88\ud558\ub294 \uc6d0\uce59)<br>\u2192 \ucd94\uac00\ub85c \ub099\ucc30\ub420 \uc218 \uc788\ub294 k+1 \ubc88\uc9f8 \uac1c\uc778\uc758 \uac00\uaca9\uc744 \uae30\uc900\uc73c\ub85c \uc9c0\ubd88\uae08\uc744 \uacb0\uc815\ud55c\ub2e4.<\/p>\n\n\n\n<p>1. \uac1c\ubcc4 \ud569\ub9ac\uc131<br>\ubaa8\ub4e0 \uc120\ud0dd\ub41c \uac1c\uc778 i\uc5d0\uac8c \uc9c0\uae09\ub418\ub294 \ube44\uc6a9 \\(p_i\\)\ub294 \ud56d\uc0c1 \uc790\uc2e0\uc758 \uc2e4\uc81c \ube44\uc6a9 \\(v_i\\)\ubcf4\ub2e4 \ud06c\uac70\ub098 \uac19\ub2e4.<br>\uc65c\ub0d0\ud558\uba74, \\(p_i = v_{k+1}\\)\uc774\uace0, \uc815\ub82c\ub41c \uc21c\uc11c\uc5d0\uc11c \\(v_i \\leq v_{k+1}\\)\uc774\ubbc0\ub85c \ud56d\uc0c1 \\(p_i \\geq v_i\\)\uac00 \ub41c\ub2e4.<br>\ub530\ub77c\uc11c \ubaa8\ub4e0 \uac1c\uc778\uc774 \uc190\ud574\ub97c \ubcf4\uc9c0 \uc54a\uace0 \ucc38\uc5ec\ud560 \ub3d9\uae30\uac00 \uc788\uae30 \ub54c\ubb38\uc5d0 \uac1c\ubcc4 \ud569\ub9ac\uc131\uc744 \ub9cc\uc871\ud55c\ub2e4.<\/p>\n\n\n\n<p>2. \uc9c4\uc2e4\uc131<br>VCG \ubc29\uc2dd\uc740 \uac1c\uc778\uc774 \uc790\uc2e0\uc774 \ube44\uc6a9\uc744 \uc870\uc791\ud558\uc5ec \ub354 \ub9ce\uc740 \uc774\ub4dd\uc744 \uc5bb\uc744 \uc218 \uc5c6\ub294 \uad6c\uc870\ub97c \uac00\uc9c4\ub2e4.<br>\uc65c\ub0d0\ud558\uba74, \uc9c0\ubd88\uae08 \\(p_i\\)\uc740 \\(v_{k+1}\\)\ub85c \uace0\uc815\ub418\uc5b4 \uc788\ub2e4.<\/p>\n\n\n\n<p>Proposition 4.5. MinCostAuction\uc774 \uc9c4\uc2e4\uc131, \uac1c\ubcc4 \ud569\ub9ac\uc131 \ubc0f \uc815\ud655\ub3c4\ub97c \ub9cc\uc871\ud55c\ub2e4.<\/p>\n\n\n\n<p>1. MinCostAuction\uc774 \\(\\alpha n\\)-\uc815\ud655\ub3c4\ub97c \ub9cc\uc871\ud55c\ub2e4.<br>\uc815\ub9ac 3.3\uc5d0 \ub530\ub974\uba74, \uace0\uc815\ub41c \uc815\ud655\ub3c4 \ubaa9\ud45c \\(\\alpha n\\)\uc744 \ub2ec\uc131\ud558\uae30 \uc704\ud574 \\((1\/2 + \\ln 3) \\alpha n\\) \ub2e8\uc704\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uad6c\ub9e4\ud574\uc57c \ud55c\ub2e4.<br>MinCostAuction\uc740 \uc815\ud655\ud788 \ud544\uc694\ud55c \ub9cc\ud07c\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uad6c\ub9e4\ud558\ub3c4\ub85d \uc124\uacc4\ub418\uc5c8\uae30 \ub54c\ubb38\uc5d0 \\(\\alpha n\\)-\uc815\ud655\ub3c4\ub97c \ub9cc\uc871\ud55c\ub2e4.<\/p>\n\n\n\n<p>2. \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc218\uc900 (\\(\\epsilon_i\\)) \uc124\uc815<br>\uc815\ub9ac 3.3\uc5d0 \ub530\ub77c, \uc120\ud0dd\ub41c \uac1c\uc778 \\(i \\leq k\\)\uc5d0 \ub300\ud574 \\(\\epsilon_i = \\frac{1}{\\alpha^{\\prime} n}\\), \uc120\ud0dd\ub418\uc9c0 \uc54a\uc740 \uac1c\uc778 \\(i > k\\)\uc5d0 \ub300\ud574 \\(\\epsilon_i = 0\\)\uc774 \uc131\ub9bd\ud55c\ub2e4. \uc989, \uc815\ud655\ud788 \ud544\uc694\ud55c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc218\uc900\ub9cc \uad6c\ub9e4\ud568\uc73c\ub85c\uc368 \ucd5c\uc801\uc758 \uc9c0\ubd88 \uad6c\uc870\ub97c \uc720\uc9c0\ud55c\ub2e4.<\/p>\n\n\n\n<p>3. \uc9c4\uc2e4\uc131\uacfc \uac1c\ubcc4 \ud569\ub9ac\uc131 \uc99d\uba85<br>MinCostAuction\uc5d0\uc11c \uac01 \uac1c\uc778 i\uc758 \ube44\uc6a9\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \uc815\uc758\ub41c\ub2e4.<\/p>\n\n\n\n<p>\\(v_i = c_i(1\/(\\alpha^{\\prime} n))\\)<\/p>\n\n\n\n<p>MinCostAuction\uc740 \uc804\ud615\uc801\uc778 VCG(Vickrey-Clarke-Groves) \uba54\ucee4\ub2c8\uc998\uc758 \ud55c \ubcc0\ud615(instantiation of the classical VCG mechanism)\uc774\ubbc0\ub85c,<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uac01 \uac1c\uc778\uc774 \uc790\uc2e0\uc758 \ube44\uc6a9\uc744 \uac70\uc9d3\uc73c\ub85c \ubcf4\uace0\ud560 \uc720\uc778\uc774 \uc5c6\uc74c (\uc9c4\uc2e4\uc131 \ubcf4\uc7a5)<\/li>\n\n\n\n<li>\uac01 \uac1c\uc778\uc774 \uc790\uc2e0\uc758 \uc2e4\uc81c \ube44\uc6a9\ubcf4\ub2e4 \ub0ae\uc740 \ubcf4\uc0c1\uc744 \ubc1b\uc9c0 \uc54a\uc74c (\uac1c\ubcc4 \ud569\ub9ac\uc131 \ubcf4\uc7a5)<\/li>\n<\/ul>\n\n\n\n<p>MinCostAuction\uc774 \ubaa9\ud45c\ub85c \ud558\ub294 \ud6a8\uc6a9(utiltiy)\uc744 \ub2e4\uc74c\uacfc \uac19\uc740 \ucd1d \ube44\uc6a9\uc73c\ub85c \ub2ec\uc131\ud55c\ub2e4.<\/p>\n\n\n\n<p>\\(\\sum_{i=1}^{n} p_i = k \\cdot v_{k+1}\\)<\/p>\n\n\n\n<p>\uc989, \ucd1d \ube44\uc6a9\uc740 \uc120\ud0dd\ub41c k\uba85\uc758 \uac1c\uc778\uc5d0\uac8c \uc9c0\uae09\ub41c \ucd1d \uae08\uc561\uc774\uace0, \uc774\ub54c \uac01 \uac1c\uc778\uc740 \\(v_{k+1}\\) \ub9cc\ud07c\uc758 \ube44\uc6a9\uc744 \uc9c0\uae09\ubc1b\ub294\ub2e4.<\/p>\n\n\n\n<p>MinCostAuction\uc5d0\uc11c \uac01 \uc120\ud0dd\ub41c \uac1c\uc778\uc740 \\(p_i = v_{k+1}\\) \ub9cc\ud07c\uc744 \ubc1b\uc73c\ubbc0\ub85c \ucd1d \ube44\uc6a9\uc740 \\(k \\cdot v_{k+1}\\)\uc774\ub2e4.<br>\ub2e4\ub978 \uc2dc\uae30\uc2ec \uc5c6\ub294 \uacbd\ub9e4\uac00 \ub354 \uc801\uc740 \ube44\uc6a9\uc744 \uc9c0\ubd88\ud560 \uc218 \uc5c6\ub294 \uc774\uc720\ub294, \ub9cc\uc57d \uc5b4\ub5a4 \ub2e4\ub978 \uc2dc\uae30\uc2ec \uc5c6\ub294 \ub2e4\uc911 \ub2e8\uc704 \uc870\ub2ec \uacbd\ub9e4\uac00 k\uac1c\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ub2e8\uc704\ub97c \uad6c\ub9e4\ud558\uba74\uc11c \ub354 \uc801\uc740 \ube44\uc6a9\uc744 \uc9c0\ubd88\ud558\ub824 \ud55c\ub2e4\uba74, \ucd5c\uc18c\ud55c \ub2e4\uc74c \uc870\uac74\uc744 \ub9cc\uc871\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\\(p_1 = p_2 = \\dots = p_k \\leq v_{k+1}\\)<\/p>\n\n\n\n<p>\uadf8\ub7ec\ub098, \uc2dc\uae30\uc2ec \uc5c6\ub294(envy-free) \uc870\uac74\uc5d0 \uc758\ud574, \ubaa8\ub4e0 \uc120\ud0dd\ub41c \uac1c\uc778\ub4e4\uc740 \ub3d9\uc77c\ud55c \uc9c0\ubd88\uae08\uc744 \ubc1b\uc544\uc57c \ud558\ubbc0\ub85c, \uac01 \uac1c\uc778\uc5d0\uac8c \\(v_{k+1}\\) \ubbf8\ub9cc\uc744 \uc9c0\uae09\ud560 \uacbd\uc6b0, \ucd5c\uc18c \ube44\uc6a9\uc744 \uc694\uad6c\ud558\ub294 \uac1c\uc778\uc774 \uac70\ubd80\ud560 \uc218 \uc788\uae30\uc5d0 \uc774\ubcf4\ub2e4 \ub354 \ub0ae\uc740 \ube44\uc6a9\uc744 \uc9c0\ubd88\ud558\ub294 \uacbd\ub9e4\ub294 \ubd88\uac00\ub2a5\ud558\ub2e4.<\/p>\n\n\n\n<p>\uc989, MinCostAuction\uc740 \uac19\uc740 \uc815\ud655\ub3c4\ub97c \ubcf4\uc7a5\ud558\ub294 \uc2dc\uae30\uc2ec \uc5c6\ub294 \uba54\ucee4\ub2c8\uc998 \uc911\uc5d0\uc11c \ucd5c\uc18c \ube44\uc6a9\uc744 \ub2ec\uc131\ud558\ub294 \ucd5c\uc801\uc758 \uacbd\ub9e4\uc774\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">5. Preserving the Privacy of the Bid<\/h2>\n\n\n\n<p>\uc774\uc804 \uc139\uc158(Section 4)\uc5d0\uc11c\ub294 \uc9c4\uc2e4\uc131(truthfulness)\uacfc \uac1c\ubcc4 \ud569\ub9ac\uc131(individual rationality)\uc744 \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uace0\ub824\ud588\ub2e4.<br>\uc774\ub7ec\ud55c \uba54\ucee4\ub2c8\uc998\uc740 \uac01 \uac1c\uc778\uc774 \uc81c\uacf5\ud558\ub294 \ub370\uc774\ud130(\uc989, \uac1c\uc778\uc758 \ube44\ud2b8 \\(b_i\\))\ub97c \uc0ac\uc6a9\ud558\ub294 \uac83\uc5d0 \ub300\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \ubcf4\uc0c1\ud558\ub294 \uad6c\uc870\uc600\ub2e4.<br>\uadf8\ub7ec\ub098 \uc774\uc804\uae4c\uc9c0\ub294 \uac01 \uac1c\uc778\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9(valuation for privacy, \\(v_i\\))\uc744 \ubcc4\ub3c4\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \ub300\uc0c1\uc73c\ub85c \uace0\ub824\ud558\uc9c0 \uc54a\uc558\ub2e4.<br>\uc989, \uba54\ucee4\ub2c8\uc998\uc774 \uac1c\uc778\uc758 \\(b_i\\) \ub97c \uc0ac\uc6a9\ud558\ub294 \uac83\uc5d0 \ub300\ud574\uc11c\ub294 \ubcf4\uc0c1\ud558\uc9c0\ub9cc, \uac1c\uc778\uc758 \\(v_i\\) \ub97c \uc0ac\uc6a9\ud568\uc73c\ub85c \uc778\ud574 \ubc1c\uc0dd\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc740 \uace0\ub824\ub418\uc9c0 \uc54a\uc558\ub2e4.<\/p>\n\n\n\n<p>Q. <strong>\uc0c8\ub85c\uc6b4 \ubb38\uc81c: \\(v_i\\) \ub3c4 \ud504\ub77c\uc774\ube57 \ub370\uc774\ud130\ub85c \uac04\uc8fc\ud560 \uc218 \uc788\ub294\uac00?<\/strong><\/p>\n\n\n\n<p>\uc6b0\ub9ac\ub294 \uac01 \uac1c\uc778\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9( \\(v_i\\) ) \uc5ed\uc2dc \ud504\ub77c\uc774\ube57 \ub370\uc774\ud130\ub85c \uac04\uc8fc\ud558\uace0, \uc774\ub97c \ubcf4\ud638\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud560 \uc218 \uc788\uc744\uae4c?<br>\ud604\uc2e4\uc801\uc73c\ub85c, \uac1c\uc778\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9 \\(v_i\\) \ub294 \uac1c\uc778\uc758 \uc2e4\uc81c \ub370\uc774\ud130 \\(b_i\\) \uc640 \uc0c1\uad00\uad00\uacc4\ub97c \uac00\uc9c8 \uac00\ub2a5\uc131\uc774 \ub192\ub2e4.<\/p>\n\n\n\n<p>\uc608\ub97c \ub4e4\uc5b4, \uc5b4\ub5a4 \uc0ac\ub78c\uc774 \ub192\uc740 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9\uc744 \uc694\uad6c\ud55c\ub2e4\uba74, \uc774\ub294 \uadf8\uac00 \ub9e4\uc6b0 \ubbfc\uac10\ud55c \uc815\ubcf4\ub97c \uac00\uc9c0\uace0 \uc788\uc74c\uc744 \uc758\ubbf8\ud560 \uac00\ub2a5\uc131\uc774 \uc788\ub2e4. \ub530\ub77c\uc11c, \uba54\ucee4\ub2c8\uc998\uc774 \\(v_i\\) \ub97c \uc0ac\uc6a9\ud558\uba74, \uac04\uc811\uc801\uc73c\ub85c \uac1c\uc778\uc758 \ube44\ud2b8 \\(b_i\\) \uc5d0 \ub300\ud55c \uc815\ubcf4\ub3c4 \ub178\ucd9c\ub420 \uc704\ud5d8\uc774 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc9c8\ubb38: <strong>\uac1c\uc778\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9 \\(v_i\\) \ub3c4 \ubcf4\ud638\ud558\uba74\uc11c\ub3c4, \uc774\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc801\uc808\ud55c \ubcf4\uc0c1\uc744 \uc81c\uacf5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud560 \uc218 \uc788\ub294\uac00?<\/strong><\/p>\n\n\n\n<p>&#8211; \ubd88\uac00\ub2a5\ud558\ub2e4.<\/p>\n\n\n\n<p>\uba54\ucee4\ub2c8\uc998\uc758 \ub450 \uac00\uc9c0 \ucd9c\ub825<br>: \ucd94\uc815\uac12 \\(\\hat{s}\\) (estimate), \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \uc9c0\uae09\ud574\uc57c \ud558\ub294 \ucd1d \uc9c0\ubd88\uae08 P (payment)<\/p>\n\n\n\n<p>\ub9cc\uc57d \uc785\ucc30 \uae08\uc561(bid) \\(v_i\\)\ub3c4 \ube44\uacf5\uac1c \ub370\uc774\ud130\ub85c \uac04\uc8fc\ub41c\ub2e4\uba74, \uba54\ucee4\ub2c8\uc998\uc740 \uac01 \uac1c\uc778 i\uc5d0 \ub300\ud574 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>Theorem 5.1. \uc785\ucc30\uc790\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9\uc744 \ubcf4\ud638\ud558\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud568<\/p>\n\n\n\n<p>\ub9cc\uc57d \uc785\ucc30\uc790\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9( \\(v_i\\) )\uc774 \uc784\uc758\ub85c \ud074 \uc218 \uc788\ub2e4\uba74,<br>\uc5b4\ub5a4 \uac1c\ubcc4 \ud569\ub9ac\uc801\uc778(individually rational) \uba54\ucee4\ub2c8\uc998\ub3c4 \uc785\ucc30\uc790\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ube44\uc6a9\uc744 \ubcf4\ud638\ud558\uba74\uc11c\ub3c4, k &lt; n\/2<strong> \uc778 <\/strong>k-\uc815\ud655\ub3c4\ub97c \ubcf4\uc7a5\ud560 \uc218 \uc5c6\ub2e4.<br><strong>\uc989, <\/strong>n\/2 \ubbf8\ub9cc\uc758 \uc815\ud655\ub3c4\ub97c \ub2ec\uc131\ud558\ub294 \ube44(\u975e)\uc0ac\uc18c\ud55c(nontrivial) \uba54\ucee4\ub2c8\uc998\uc740 \uc874\uc7ac\ud560 \uc218 \uc5c6\ub2e4.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\uc65c \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \\(v_i\\)\ub97c \ubcf4\ud638\ud558\uba74\uc11c \ubcf4\uc0c1\ud558\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud55c\uac00?<\/h5>\n\n\n\n<p>\uc774 \uc139\uc158\uc5d0\uc11c\ub294 \ub9cc\uc57d \uac1c\uc778\uc774 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \\(v_i\\)\uc5d0 \ub300\ud574 \uc784\uc758\ub85c \ub192\uc740 \uac12\uc744 \uc124\uc815\ud560 \uc218 \uc788\ub2e4\uba74, \uc774\ub7ec\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud558\ub294 \uac83\uc740 \ubcf8\uc9c8\uc801\uc73c\ub85c \ubd88\uac00\ub2a5\ud558\ub2e4\ub294 \uc810\uc744 \ubcf4\uc778\ub2e4.<br>\ub354 \ub098\uc544\uac00, \uac1c\uc778\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \\(v_i\\)\uc5d0 \uc0ac\uc804\uc801\uc73c\ub85c \uc0c1\ud55c\uc120\uc744 \uc124\uc815\ud558\ub824\uace0 \ud558\uba74, \uacbd\ub9e4\ub97c \ud1b5\ud574 \ud574\uacb0\ud558\uace0\uc790 \ud588\ub358 \ud45c\ubcf8 \ucd94\ucd9c \ud3b8\ud5a5(sampling bias) \ubb38\uc81c\uac00 \ub2e4\uc2dc \ubc1c\uc0dd\ud558\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p>1) \ub192\uc740 \uac00\uaca9\uc744 \ubd80\ub97c \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>&#8211; \uacbd\ub9e4\uc5d0\uc11c\ub294 \ucc38\uac00\uc790\ub4e4\uc774 \uc790\uc2e0\uc774 \uc0dd\uac01\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58 \\(v_i\\)\ub97c \uc9c1\uc811 \uc785\ub825\ud55c\ub2e4.<br>&#8211; \ud558\uc9c0\ub9cc \ub9cc\uc57d \\(v_i\\)\uac00 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638\ub97c \ubc1b\uc544\uc57c \ud55c\ub2e4\uba74, \uc774\ub97c \uc81c\ud55c\ud560 \ubc29\ubc95\uc774 \uc5c6\ub2e4.<br>&#8211; \uc989, \uc5b4\ub5a4 \uc0ac\ub78c\uc774 &#8216;\ub098\ub294 \ub0b4 \ub370\uc774\ud130\ub97c \uacf5\uac1c\ud558\ub294 \ub300\uac00\ub85c 1\uc5b5 \uc6d0\uc744 \ubc1b\uc544\uc57c \ud574&#8217;\ub77c\uace0 \ud558\uba74, \uc774\ub97c \ub9c9\uc744 \ubc29\ubc95\uc774 \uc5c6\ub2e4.<br>\u2192 \ubaa8\ub4e0 \uc0ac\ub78c\uc774 \uc790\uc2e0\uc774 \uc6d0\ud558\ub294 \ub9cc\ud07c \ub192\uc740 \\(v_i\\)\ub97c \uc124\uc815\ud560 \uc218 \uc788\ub2e4\uba74, \uacbd\ub9e4\ub294 \uc131\ub9bd\ud558\uc9c0 \uc54a\ub294\ub2e4.<\/p>\n\n\n\n<p>2) \uc0c1\ud55c\uc120\uc744 \uc124\uc815\ud558\uba74 \uc0d8\ud50c\ub9c1 \ud3b8\ud5a5(bias)\uc774 \uc0dd\uae40<\/p>\n\n\n\n<p>&#8211; \\(v_i\\) \uac12\uc5d0 \uc81c\ud55c\uc744 \ub450\uba74 \ub418\uc9c0 \uc54a\uc744\uae4c? \uc608\ub97c \ub4e4\uc5b4, &#8216;\ucd5c\ub300 100\ub2ec\ub7ec\uae4c\uc9c0\ub9cc \ubcf4\uc0c1\ud574\uc900\ub2e4&#8217;\ub77c\uace0 \ud558\uba74 \uc5b4\ub5a8\uae4c?<br>&#8211; \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc911\uc694\ud558\uac8c \uc5ec\uae30\ub294 \uc0ac\ub78c\ub4e4(\ub192\uc740 \\(v_i\\)\ub97c \uac00\uc9c4 \uc0ac\ub78c\ub4e4)\uc740 \uacbd\ub9e4\uc5d0 \ucc38\uc5ec\ud558\uc9c0 \uc54a\uc744 \uac00\ub2a5\uc131\uc774 \ub192\ub2e4.<br>&#8211; \uacb0\uad6d, \uacbd\ub9e4\uc5d0\uc11c \ud655\ubcf4\ud55c \ub370\uc774\ud130\uac00 \uc804\uccb4 \ubaa8\uc9d1\ub2e8\uc744 \uc81c\ub300\ub85c \ub300\ud45c\ud558\uc9c0 \ubabb\ud560 \uac00\ub2a5\uc131\uc774 \ucee4\uc9c4\ub2e4.<br>&#8211; \uc774\uac83\uc740 \uacbd\ub9e4\ub97c \ud1b5\ud574 \ud574\uacb0\ud558\ub824 \ud588\ub358 \ub300\ud45c\uc131 \ubb38\uc81c(sampling bias)\ub97c \ub2e4\uc2dc \ubd88\ub7ec\uc624\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p>3) \uc218\ud559\uc801 \uc870\uac74: DP \ubcf4\ud638\uc758 \ud55c\uacc4<\/p>\n\n\n\n<p>&#8211; \ub17c\ubb38\uc5d0\uc11c\ub294 \\(v_i\\)\ub97c DP\ub85c \ubcf4\ud638\ud574\uc57c \ud55c\ub2e4\uba74, \ud2b9\uc815\ud55c \ud655\ub960 \uc870\uac74\uc744 \ub9cc\uc871\ud574\uc57c \ud55c\ub2e4\uace0 \uc124\uba85\ud55c\ub2e4.<br>&#8211; \ub9cc\uc57d \\(v_i\\)\uac00 \ubcf4\ud638\ub41c\ub2e4\uba74, \uacbd\ub9e4 \uacb0\uacfc(\ucd94\uc815\uac12\uacfc \ubcf4\uc0c1)\uac00 \\(v_i\\)\uc758 \ubcc0\ud654\uc5d0 \ub530\ub77c \uae09\uaca9\ud558\uac8c \ubcc0\ud558\uba74 \uc548 \ub41c\ub2e4.<br>&#8211; \ud558\uc9c0\ub9cc, \ubcf4\uc0c1\uc744 \uc9c0\uae09\ud558\ub824\uba74 \uacb0\uad6d \\(v_i\\)\ub97c \uace0\ub824\ud574\uc57c \ud558\ubbc0\ub85c, \uc774 \uc870\uac74\uc744 \ub9cc\uc871\ud558\uba74\uc11c \uacf5\uc815\ud55c \ubcf4\uc0c1\uc744 \uc8fc\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud558\ub2e4.<br>&#8211; \\(v_i\\)\ub97c \ubcf4\ud638\ud558\uba74\uc11c\ub3c4 \uacf5\uc815\ud55c \ubcf4\uc0c1\uc744 \uc81c\uacf5\ud558\ub294 \uac83\uc740 \uc774\ub860\uc801\uc73c\ub85c \ubd88\uac00\ub2a5\ud558\ub2e4.<\/p>\n\n\n\n<h6 class=\"wp-block-heading\">\uacb0\ub860 &#8211; Theorem 5.1<\/h6>\n\n\n\n<p>1) \\(v_i\\)\ub97c \ubb34\uc81c\ud55c\uc73c\ub85c \ud5c8\uc6a9\ud560 \uacbd\uc6b0, \ucc38\uac00\uc790\uac00 1\uc5b5\uc6d0 \uac19\uc740 \ube44\ud604\uc2e4\uc801\uc778 \uac00\uaca9\uc744 \uc694\uad6c\ud560 \uc218 \uc788\uc5b4 \uacbd\ub9e4\uac00 \uc131\ub9bd\ud558\uc9c0 \uc54a\uc74c<br>2) \\(v_i\\)\uc5d0 \uc0c1\ud55c\uc120\uc744 \uc124\uc815\ud560 \uacbd\uc6b0, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\ud638\ud558\uac8c \uc5ec\uae30\ub294 \ucc38\uac00\uc790\uac00 \ube60\uc9c0\uba74\uc11c \uc0d8\ud50c\ub9c1 \ud3b8\ud5a5\uc774 \uc0dd\uae40<br>3) \\(v_i\\)\ub97c DP\ub85c \ubcf4\ud638\ud560 \uacbd\uc6b0, \ubcf4\uc0c1\uc744 \uacc4\uc0b0\ud560 \ub54c \\(v_i\\)\ub97c \uace0\ub824\ud574\uc57c \ud558\ubbc0\ub85c, \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638\uc640 \ubcf4\uc0c1\uc744 \ub3d9\uc2dc\uc5d0 \ud560 \uc218 \uc5c6\uc74c<\/p>\n\n\n\n<p>\u2192 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \\(v_i\\)\ub97c \ubcf4\ud638\ud558\uba74\uc11c\ub3c4 \ubcf4\uc0c1\uc744 \uc81c\uacf5\ud558\ub294 \uac83\uc740 \ubd88\uac00\ub2a5\ud558\ub2e4. \/ k-\uc815\ud655\ub3c4\ub97c \uc720\uc9c0\ud558\ub294 \uac1c\ubcc4 \ud569\ub9ac\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc740 \uc874\uc7ac\ud560 \uc218 \uc5c6\ub2e4.<\/p>\n\n\n\n<p>Remark 5.2<\/p>\n\n\n\n<p>\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc740 \uc785\ucc30\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \\(v_i\\)\uac00 \ud2b9\uc815\ud55c \ubc94\uc704 (e.g. [0, 1]) \ub0b4\uc5d0 \uc788\ub3c4\ub85d \uc81c\ud55c\ud558\ub294 \uac83\uc774\uc9c0\ub9cc, \uc774 \ubc29\ubc95\uc740 \ub9cc\uc871\uc2a4\ub7fd\uc9c0 \uc54a\ub2e4.<br>\uc6b0\ub9ac\uac00 \uacbd\ub9e4\ub97c \ud1b5\ud574 \ud574\uacb0\ud558\ub824\uace0 \ud588\ub358 \ud45c\ubcf8 \ucd94\ucd9c \ud3b8\ud5a5(sampling bias) \ubb38\uc81c\uac00 \ub2e4\uc2dc \ubc1c\uc0dd\ud558\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">6. Future Directions<\/h3>\n\n\n\n<p>\uac1c\uc778 \ub370\uc774\ud130 \uacbd\ub9e4(auction for private data) \uac1c\ub150\uc744 \ud615\uc2dd\ud654\ud558\uace0, \uc774\ub7ec\ud55c \uacbd\ub9e4\uc758 \uc124\uacc4 \uacf5\uac04\uc774 \ub2e4\uc911 \ub2e8\uc704 \uc870\ub2ec \uacbd\ub9e4\ub85c \ub2e8\uc21c\ud654\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\ud5a5\ud6c4 \uc5f0\uad6c \uc9c8\ubb38<\/h5>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\uacbd\ub9e4\uc758 \uc801\uc808\ud55c \ubca4\uce58\ub9c8\ud06c\ub780 \ubb34\uc5c7\uc778\uac00?<br>\ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 fixed-price \ub610\ub294 envy-free \uba54\ucee4\ub2c8\uc998\uc744 \ubca4\uce58\ub9c8\ud06c\ub85c \uc0ac\uc6a9\ud588\ub2e4.<br>\uc774\ub7ec\ud55c \uc811\uadfc \ubc29\uc2dd\uc740 \uc0ac\uc804 \ubd84\ud3ec\uac00 \uc5c6\ub294(prior-free) \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0\uc11c \ud45c\uc900\uc801\uc73c\ub85c \uc0ac\uc6a9\ub418\ub294 \ubc29\ubc95\uc774\uc9c0\ub9cc, \uc774\ub294 \ubca0\uc774\uc9c0\uc548 \ucd5c\uc801 \uba54\ucee4\ub2c8\uc998(Bayesian optimal mechanism)\uc774 \uc798 \uc54c\ub824\uc838 \uc788\ub294 \ud658\uacbd\uc5d0\uc11c \ub354 \uc801\ud569\ud55c \ubc29\uc2dd\uc774\ub2e4.<br>\uadf8\ub7ec\ub098, \ubcf8 \ub17c\ubb38\uc5d0\uc11c \ub2e4\ub8ec \uc608\uc0b0 \uc81c\ud55c\uc774 \uc788\ub294 \uacbd\ub9e4(budget-constrained auctitons)\uc5d0\uc11c\ub294 \ubca0\uc774\uc9c0\uc548 \ucd5c\uc801 \uba54\ucee4\ub2c8\uc998\uc774 \uc54c\ub824\uc838 \uc788\uc9c0 \uc54a\ub2e4. \ub530\ub77c\uc11c, \ubca0\uc774\uc9c0\uc548 \ucd5c\uc801 \uba54\ucee4\ub2c8\uc998\uc744 \uc5f0\uad6c\ud568\uc73c\ub85c\uc368, \ubcf4\ub2e4 \uc801\uc808\ud55c \ubca4\uce58\ub9c8\ud06c\ub97c \uc815\uc758\ud558\ub294 \uac83\uc774 \uc911\uc694\ud558\ub2e4.<\/li>\n\n\n\n<li>\ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00(privacy valuation)\uc758 \ubcf4\ud638 \ubc0f \ubcf4\uc0c1 \ubb38\uc81c<br>\uac1c\uc778\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \\(v_i\\)\uac00 \uac1c\uc778\uc758 \ub370\uc774\ud130 \\(b_i\\)\uc640 \uc0c1\uad00\uad00\uacc4\ub97c \uac00\uc9c8 \uc218 \uc788\uc74c\uc744 \ubcf4\uc600\ub2e4.<br>\uadf8\ub7ec\ub098, \uc774\ub7ec\ud55c \uc0c1\uad00\uad00\uacc4\ub294 \uc2e4\uc81c\ub85c \uc874\uc7ac\ud558\uba70, \uc774\ub97c \uc644\uc804\ud788 \ubc30\uc81c\ud558\ub294 \uac83\uc740 \ub9cc\uc871\uc2a4\ub7fd\uc9c0 \uc54a\ub2e4.<br>\ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\ub97c \uc81c\ud55c\ub41c \ubc94\uc704 \ub0b4\uc5d0\uc11c \uc124\uc815\ud558\ub294 \ubc29\ubc95\ub3c4 \uc81c\uc548\ub420 \uc218 \uc788\uc9c0\ub9cc, \uc774\ub294 \ub2e4\uc2dc \uc0d8\ud50c\ub9c1 \ud3b8\ud5a5 \ubb38\uc81c\ub97c \ucd08\ub798\ud560 \uc218 \uc788\ub2e4.<br>\uadf8\ub807\ub2e4\uba74, \ud2b9\uc815\ud55c \uc870\uac74 \ud558\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uc758 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\ud638\ud558\uba74\uc11c \ubcf4\uc0c1\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc774 \uc788\uc744\uae4c? \uc774\ub97c \uc704\ud574\uc11c\ub294 \uc0c8\ub85c\uc6b4 \ubaa8\ub378\uc774 \ud544\uc694\ud560 \uac83\uc774\ub2e4.<\/li>\n\n\n\n<li>\ub370\uc774\ud130\uac00 \uc911\uc559 \uad00\ub9ac\uc790\uc5d0\uac8c \uc800\uc7a5\ub418\uc9c0 \uc54a\uc740 \uacbd\uc6b0<br>\uc0ac\uc6a9\uc790\uc758 \ud504\ub77c\uc774\ube57 \ube44\ud2b8 \\(b_i\\)\uac00 \ubcd1\uc6d0\uacfc \uac19\uc740 \uc911\uc559 \ub370\uc774\ud130\ubca0\uc774\uc2a4 \uad00\ub9ac\uc790\uc5d0\uac8c \uc774\ubbf8 \uc54c\ub824\uc838 \uc788\ub2e4\uace0 \uac00\uc815\ud588\ub2e4.<br>\uadf8\ub7ec\ub098 \ubaa8\ub4e0 \uc0c1\ud669\uc5d0\uc11c \uc774\ub7ec\ud55c \uac00\uc815\uc774 \uc131\ub9bd\ud558\ub294 \uac83\uc740 \uc544\ub2c8\ub2e4.<br>\ub9cc\uc57d \uac1c\uc778\uc774 \uc9c1\uc811 \uc790\uc2e0\uc758 \ub370\uc774\ud130\ub97c \ubcf4\uc720\ud558\uace0 \uc788\uc73c\uba70, \uc774\ub97c \uac70\uc9d3\uc73c\ub85c \ubcf4\uace0\ud560 \uc218\ub3c4 \uc788\ub2e4\uba74 \uc5b4\ub5bb\uac8c \ud560 \uac83\uc778\uac00?<br>\uac1c\uc778\uc774 \uc790\uc2e0\uc758 \ub370\uc774\ud130\ub97c \uc18d\uc77c \uac00\ub2a5\uc131\uc744 \uace0\ub824\ud55c \uc0c8\ub85c\uc6b4 \uba54\ucee4\ub2c8\uc998\uc774 \ud544\uc694\ud560 \uac83\uc774\ub2e4.<\/li>\n\n\n\n<li>\ub2e4\uc911 \ub370\uc774\ud130 \ubd84\uc11d\uac00(multi-sided market) \ud658\uacbd<br>\ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 \ub2e8\uc77c \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \ud558\ub098\uc758 \uc5f0\uad6c \uc9d1\ub2e8\uc73c\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub294 \ub2e8\uc21c\ud55c \uc2dc\uc7a5\uc744 \uac00\uc815\ud588\ub2e4.<br>\uadf8\ub7ec\ub098 \ud604\uc2e4\uc5d0\uc11c\ub294 \uc5ec\ub7ec \uba85\uc758 \ub370\uc774\ud130 \ubd84\uc11d\uac00\ub4e4\uc774 \ub2e4\uc591\ud55c \uc5f0\uad6c \uc9d1\ub2e8\uc758 \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub824 \uacbd\uc7c1\ud560 \uac00\ub2a5\uc131\uc774 \uc788\ub2e4.<br>\uc774\ub7ec\ud55c \ud658\uacbd\uc5d0\uc11c, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\ud638\ud558\uba74\uc11c \uc2dc\uc7a5 \uade0\ud615 \uac00\uaca9\uc744 \uacc4\uc0b0\ud560 \uc218 \uc788\uc744\uae4c?<br>\ub2e4\uc911 \uc2dc\uc7a5 \ubaa8\ub378\uc744 \uc5f0\uad6c\ud558\uc5ec, \ub370\uc774\ud130 \ubd84\uc11d\uac00\uc640 \ub370\uc774\ud130 \uc81c\uacf5\uc790 \uac04\uc758 \uc0c1\ud638\uc791\uc6a9\uc744 \ubcf4\ub2e4 \ud604\uc2e4\uc801\uc73c\ub85c \ubd84\uc11d\ud560 \ud544\uc694\uac00 \uc788\ub2e4.<\/li>\n\n\n\n<li>\ubc18\ubcf5\uc801\uc778 \ub370\uc774\ud130 \ud310\ub9e4 \ud658\uacbd\uc5d0\uc11c\uc758 \ubb38\uc81c<br>\ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 \ub2e8\ubc1c\uc131 \uacbd\ub9e4(one-shot auction)\ub9cc \uace0\ub824\ud588\ub2e4.<br>\uadf8\ub7ec\ub098 \ud604\uc2e4\uc5d0\uc11c\ub294 \ub370\uc774\ud130\ubca0\uc774\uc2a4 \uad00\ub9ac\uc790\uac00 \uc2dc\uac04\uc774 \uc9c0\ub0a8\uc5d0 \ub530\ub77c \uc5ec\ub7ec \ubc88 \ub370\uc774\ud130 \uc811\uadfc \uc694\uccad\uc744 \ubc1b\uc744 \uac00\ub2a5\uc131\uc774 \ub192\ub2e4.<br>\uadf8\ub807\ub2e4\uba74 \ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \uac01 \uc694\uccad\uc5d0 \ub300\ud55c \uc751\ub2f5\uc744 \uc5b4\ub5bb\uac8c \uacb0\uc815\ud574\uc57c \ud558\uba70, \ucd94\uac00\uc801\uc778 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4(marginal privacy loss)\uc744 \uc5b4\ub5bb\uac8c \ud3c9\uac00\ud574\uc57c \ud560\uae4c?<br>\ubc18\ubcf5\uc801\uc778 \uacbd\ub9e4\uc640 \uc628\ub77c\uc778 \ud559\uc2b5\uc744 \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uac00 \ud544\uc694\ud560 \uac83\uc774\ub2e4.<\/li>\n<\/ol>\n\n\n\n<p><\/p>\n\n\n\n<p>+) \ud55c\uacc4<\/p>\n\n\n\n<p>1) \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uacfc \ub370\uc774\ud130 \uc81c\uacf5 \uc5ec\ubd80 \uc0ac\uc774\uc758 \uc0c1\uad00\uad00\uacc4<\/p>\n\n\n\n<p>\u2022 \uc77c\ubd80 \ucc38\uac00\uc790\ub294 \uc790\uc2e0\uc758 \ub370\uc774\ud130\uac00 \ubbfc\uac10\ud560\uc218\ub85d \ub354 \ub192\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \uc694\uad6c\ud560 \uc218 \uc788\uc74c.<br>\u2022 \ud558\uc9c0\ub9cc \uace0\uc815 \uac00\uaca9 \uba54\ucee4\ub2c8\uc998\uc740 \uc774\ub7ec\ud55c \ucc28\uc774\ub97c \ubc18\uc601\ud558\uc9c0 \ubabb\ud560 \uc218 \uc788\uc74c.<\/p>\n\n\n\n<p>2) \ub3d9\uc801\uc778 \ud658\uacbd\uc5d0\uc11c\uc758 \ucd5c\uc801 \uac00\uaca9 \uc124\uc815 \ubb38\uc81c<\/p>\n\n\n\n<p>\u2022 \uc2dc\uc7a5\uc758 \ucc38\uac00\uc790 \uc218\uac00 \ubcc0\ud560 \uacbd\uc6b0, \uace0\uc815 \uac00\uaca9\uc744 \uc5b4\ub5bb\uac8c \uc870\uc815\ud560 \uac83\uc778\uac00?<br>\u2022 \ucd5c\uc801\uc758 \uac00\uaca9\uc744 \uc2e4\uc2dc\uac04\uc73c\ub85c \ub3d9\uc801\uc73c\ub85c \uc870\uc815\ud560 \ud544\uc694\uac00 \uc788\uc744 \uc218\ub3c4 \uc788\uc74c.<\/p>\n\n\n\n<p>3) \ubc18\ubcf5\uc801 \uac70\ub798(repeated auction) \ud658\uacbd\uc5d0\uc11c\uc758 \ubb38\uc81c<\/p>\n\n\n\n<p>\u2022 \ub3d9\uc77c\ud55c \ucc38\uac00\uc790\uac00 \uc5ec\ub7ec \ubc88 \ucc38\uc5ec\ud558\ub294 \uacbd\uc6b0, \uac00\uaca9 \uc870\uc815 \uc804\ub7b5\uc774 \ud544\uc694\ud568.<br>\u2022 \ucc38\uac00\uc790\ub4e4\uc774 \uc804\ub7b5\uc801\uc73c\ub85c \uc751\ub2f5\ud560 \uac00\ub2a5\uc131\uc774 \ucee4\uc9c8 \uc218 \uc788\uc74c.<\/p>\n\n\n\n<p>\u2192 \ucc38\uac00\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \uacb0\uc815\ud560 \ub54c, \ub370\uc774\ud130 \ubbfc\uac10\ub3c4(sensitivity score)\ub97c \ubc18\uc601\ud55c \ub3d9\uc801 \uac00\uaca9 \ucc45\uc815 \ubaa8\ub378\uc744 \ub3c4\uc785.<br>\u2022 \uc608\ub97c \ub4e4\uc5b4, \uc758\ub8cc \ub370\uc774\ud130\uc640 \uac19\uc774 \uace0\uc720\ud558\uac8c \ubbfc\uac10\ud55c \uc815\ubcf4\uc77c\uc218\ub85d \ub354 \ub192\uc740 \ubcf4\uc0c1\uc744 \uc9c0\uae09\ud558\ub3c4\ub85d \uba54\ucee4\ub2c8\uc998\uc744 \uc870\uc815.<br>\u2022 \ub370\uc774\ud130\uc758 \ubbfc\uac10\ub3c4\uac00 \ub192\uc744\uc218\ub85d \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \ub354 \ub192\uac8c \ubc18\uc601\ud558\uc5ec \uacf5\uc815\uc131\uc744 \ubcf4\uc7a5.<\/p>\n\n\n\n<p>\u2022 \ud604\uc2e4 \uc138\uacc4\uc758 \ub370\uc774\ud130\ub294 \uc2dc\uac04\uc774 \uc9c0\ub0a8\uc5d0 \ub530\ub77c \ubcc0\ud654\ud55c\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \uc0ac\uc6a9\uc790\uc758 \ud589\ub3d9 \ud328\ud134, \uc2dc\uc7a5 \uc0c1\ud669, \uc9c8\ubcd1 \ubc1c\uc0dd\ub960 \ub4f1\uc740 \ub3d9\uc801\uc73c\ub85c \ubcc0\ud654\ud558\uae30 \ub54c\ubb38\uc5d0, \uae30\uc874 \ub370\uc774\ud130\ub97c \ubc18\ubcf5\uc801\uc73c\ub85c \uc5c5\ub370\uc774\ud2b8\ud574\uc57c \ud55c\ub2e4. \ub530\ub77c\uc11c \ub370\uc774\ud130 \ubd84\uc11d\uac00\ub294 \uc9c0\uc18d\uc801\uc73c\ub85c \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\uc5ec, \ucd5c\uc2e0 \uc815\ubcf4\ub97c \ubc18\uc601\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">References<\/h5>\n\n\n\n<p>Ghosh, Arpita, and Aaron Roth. &#8220;Selling privacy at auction.&#8221;&nbsp;<em>Proceedings of the 12th ACM conference on Electronic commerce<\/em>. 2011.<\/p>\n\n\n\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>We initiate the study of markets for private data, through the lens of differential privacy. Although the purchase and sale of private data has already begun on a large scale, a theory of privacy as a commodity is missing.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[108],"tags":[],"class_list":["post-4759","post","type-post","status-publish","format-standard","hentry","category-paper-review"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4759"}],"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=4759"}],"version-history":[{"count":68,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4759\/revisions"}],"predecessor-version":[{"id":5208,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4759\/revisions\/5208"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=4759"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=4759"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=4759"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}