{"id":4827,"date":"2025-03-08T23:52:00","date_gmt":"2025-03-08T14:52:00","guid":{"rendered":"https:\/\/saraheee.com\/?p=4827"},"modified":"2025-03-21T23:21:49","modified_gmt":"2025-03-21T14:21:49","slug":"review17-is-privacy-compatible-with-truthfulness","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2025\/03\/review17-is-privacy-compatible-with-truthfulness\/","title":{"rendered":"[review#18] Is Privacy Compatible with Truthfulness?_Xiao, 2013"},"content":{"rendered":"<h3 class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>\ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\ud638\ud558\ub294 \ub370\uc774\ud130 \ub9c8\uc774\ub2dd \uc601\uc5ed\uc5d0\uc11c DP \uba54\ucee4\ub2c8\uc998\uc740, \uac1c\uc778\uc758 \uc815\ubcf4\uac00 \uc720\ucd9c\ub420 \uc704\ud5d8\uc774 \uc801\uae30 \ub54c\ubb38\uc5d0 \uc0ac\ub78c\ub4e4\uc774 \ub370\uc774\ud130\ub97c \uacf5\uc720\ud558\ub3c4\ub85d \uc7a5\ub824\ud558\ub294 \uc5ed\ud560\uc744 \ud55c\ub2e4\uace0 \uc9c1\uad00\uc801\uc73c\ub85c \ud574\uc11d\ub420 \uc218 \uc788\ub2e4.<br>\uadf8\ub7ec\ub098 \uc800\uc790\ub294 \uc774 \ud574\uc11d\uc774 \ubd88\uc644\uc804\ud558\ub2e4\uace0 \uc8fc\uc7a5\ud55c\ub2e4. \uadf8 \uc774\uc720\ub294 \uc0ac\ub78c\ub4e4\uc774 \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc5d0 \ucc38\uc5ec\ud558\ub824\uba74 \uc678\ubd80 \uc778\uc13c\ud2f0\ube0c(external incentives)\uac00 \ud544\uc694\ud558\uba70, \ub530\ub77c\uc11c \ub370\uc774\ud130 \uacf5\uac1c \uba54\ucee4\ub2c8\uc998\uc740 \ub2e8\uc21c\ud788 DP\ub97c \ub9cc\uc871\ud558\ub294 \uac83\ubfd0\ub9cc \uc544\ub2c8\ub77c, \uc778\uc13c\ud2f0\ube0c\uc640\ub3c4 \ud638\ud658\ub418\uc5b4\uc57c \ud55c\ub2e4.<br>\uadf8\ub807\uc9c0 \uc54a\uc73c\uba74, \uc218\uc9d1\ub41c \ub370\uc774\ud130\uac00 \ud5c8\uc704\uc77c \uac00\ub2a5\uc131\uc774 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc800\uc790\ub294 \uac8c\uc784 \uc774\ub860\uc5d0\uc11c\uc758 \uc9c4\uc2e4\uc131(truthfulness) \uac1c\ub150\uc744 \uc801\uc6a9\ud558\uc5ec \uc774 \ubb38\uc81c\ub97c \ubd84\uc11d\ud55c\ub2e4. \ud2b9\uc815 \ud658\uacbd\uc5d0\uc11c\ub294, \uae30\uc874 DP \uba54\ucee4\ub2c8\uc998\uc774 \ucc38\uac00\uc790\ub4e4\uc774 \uc815\ubcf4\ub97c \uc9c4\uc2e4\ud558\uac8c \ubcf4\uace0\ud558\ub3c4\ub85d \uc7a5\ub824\ud558\uc9c0 \ubabb\ud55c\ub2e4\ub294 \uacb0\uacfc\ub97c \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">On the positive side<\/h5>\n\n\n\n<p>\uae0d\uc815\uc801\uc778 \uce21\uba74\uc5d0\uc11c, \uc800\uc790\ub294 &#8216;\uc9c4\uc2e4\uc131\uc744 \uc720\uc9c0\ud558\ub294 DP \ubcf4\ud638 \ubcc0\ud658 \ubc29\ubc95&#8217;\uc744 \uc81c\uc2dc\ud55c\ub2e4.<br>\uc774 \ubcc0\ud658\uc740 \uc720\ud615 \uacf5\uac04\uc774 \uc791\uace0, \uc0ac\ud68c\uc801 \ubcf5\uc9c0(social welfare)\uc640 \uac19\uc740 \ubbfc\uac10\ud558\uc9c0 \uc54a\uc740 \uc9c0\ud45c\ub97c \ucd5c\uc801\ud654\ud558\ub294 \uac8c\uc784\uc5d0 \uc801\uc6a9 \uac00\ub2a5\ud558\ub2e4.<br>\ub610\ud55c, \uc774 \ubcc0\ud658 \uacfc\uc815\uc740 \ucd5c\uc801\uc131(optimality)\uc5d0\uc11c \uc791\uc740 \ucd94\uac00\uc801 \uc190\uc2e4(small additive loss)\ub9cc \ubc1c\uc0dd\ud558\uba70, \uacc4\uc0b0\uc801\uc73c\ub85c \ud6a8\uc728\uc801\uc774\ub2e4.<br>\ud2b9\ud788, VCG(Vickrey-Clarke-Groves) \uba54\ucee4\ub2c8\uc998\uacfc \uacb0\ud569\ud558\uba74, \uc791\uc740 \uc720\ud615 \uacf5\uac04\uc744 \uac00\uc9c4 \ubaa8\ub4e0 \uc0ac\ud68c\uc801 \ubcf5\uc9c0 \uac8c\uc784\uc5d0 \ub300\ud574, \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\uba74\uc11c\ub3c4 \uc9c4\uc2e4\uc131\uc744 \uc720\uc9c0\ud558\ub294 \uadfc\uc0ac\uc801\uc73c\ub85c \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc774 \uc874\uc7ac\ud568\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<p>\uc800\uc790\ub294 \ub610\ud55c \uba54\ucee4\ub2c8\uc998\uc5d0 \uc758\ud574 \uc720\ucd9c\ub418\ub294 \uc815\ubcf4\uc5d0 \ub300\ud574 \uba85\ud655\ud55c \uc218\uce58\uc801 \ube44\uc6a9(numerical cost)\uc774 \ud560\ub2f9\ub418\ub294 \ubaa8\ub378\uc744 \uc5f0\uad6c\ud55c\ub2e4.<br>\uc774 \uacbd\uc6b0, DP \uac1c\ub150\uc870\ucc28\ub3c4 \uc0ac\ub78c\ub4e4\uc774 \uc9c4\uc2e4\ud558\uac8c \ucc38\uc5ec\ud558\ub3c4\ub85d \uc720\ub3c4\ud558\uae30\uc5d0 \ucda9\ubd84\ud788 \uac15\ub825\ud558\uc9c0 \uc54a\uc744 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778\ub2e4.<br>\ud2b9\ud788, \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc758 \ub178\uc774\uc988\uac00 \ucd94\uac00\ub41c \ud788\uc2a4\ud1a0\uadf8\ub7a8(perturbed histogram)\uc744 \uacf5\uac1c\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \uc9c0\ub098\uce58\uac8c \ub9ce\uc740 \uc815\ubcf4\ub97c \ub178\ucd9c\ud560 \uc218 \uc788\uc74c\uc744 \uc785\uc99d\ud55c\ub2e4.<br>\ub610\ud55c, Blum et al. (STOC \u201908)\uc758 \uba54\ucee4\ub2c8\uc998\uacfc \uac19\uc774, \uc6d0\ubcf8 \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc640 \uc720\uc0ac\ud55c \uac1c\uc694(synopsis)\ub97c \ucd9c\ub825\ud558\ub294 \uba54\ucee4\ub2c8\uc998\ub3c4 \uc9c0\ub098\uce58\uac8c \ub9ce\uc740 \uc815\ubcf4\ub97c \ub178\ucd9c\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Keywords: differential privacy, mechanism design<\/h5>\n\n\n\n<h3 class=\"wp-block-heading\">1. Introduction<\/h3>\n\n\n\n<p>\uc138\uc0c1\uc774 \uc810\uc810 \ub354 \ub514\uc9c0\ud138\ud654\ub418\uace0 \uc5f0\uacb0\ub428\uc5d0 \ub530\ub77c \uac1c\uc778 \uc815\ubcf4 \ubcf4\ud638\uc5d0 \ub300\ud55c \uc6b0\ub824\uac00 \uc810\uc810 \ub354 \ucee4\uc9c0\uace0 \uc788\ub2e4. \ub2e4\uc591\ud55c \uc870\uc9c1\ub4e4\uc774 \uac1c\uc778\uc758 \ub370\uc774\ud130\ub97c \uc218\uc9d1, \uc811\uadfc, \uc800\uc7a5\ud558\uba74\uc11c, <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\ub370\uc774\ud130\ub97c \ucd5c\ub300\ud55c \ud65c\uc6a9\ud558\ub824\ub294 \uc695\uad6c\uc640,<\/li>\n\n\n\n<li>\uc758\ub8cc \uae30\ub85d, \uc778\uad6c \ud1b5\uacc4 \uc815\ubcf4 \ub4f1 \ub2e4\uc591\ud55c \uac1c\uc778\uc815\ubcf4\ub97c \ubcf4\ud638\ud558\ub824\ub294 \uc695\uad6c<\/li>\n<\/ul>\n\n\n\n<p>\uc774 \ub450 \uac00\uc9c0\uac00 \uac15\ud55c \uae34\uc7a5 \uc0c1\ud0dc\uc5d0 \ub193\uc774\uac8c \ub418\uc5c8\ub2e4.<\/p>\n\n\n\n<p>\uc774\ub7ec\ud55c \uae34\uc7a5\uc744 \uc774\ud574\ud558\uace0 \ud574\uacb0\ud558\ub824\ub294 \uac83\uc740 \ud1b5\uacc4(statistics) \ubc0f \ub370\uc774\ud130 \ubd84\uc11d(data analysis) \uc5f0\uad6c \ubd84\uc57c\uc5d0\uc11c \uc624\ub7ab\ub3d9\uc548 \ub2e4\ub8e8\uc5b4 \uc628 \ubaa9\ud45c\uc600\ub2e4 [5, 16].<br>\ubcf4\ub2e4 \ucd5c\uadfc\uc5d0\ub294 \uc774\ub860\uc801 \ucef4\ud4e8\ud130 \uacfc\ud559 \ubd84\uc57c\uc5d0\uc11c \uc774 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uae30 \uc704\ud55c \uc815\uc758\uc640 \uc5c4\uaca9\ud55c \uc811\uadfc\ubc95(rigorous treatment)\uc744 \uc81c\uc2dc\ud588\uc73c\uba70, \uc774 \uc5f0\uad6c\ub294 \uacb0\uad6d DP \uac1c\ub150\uc758 \uc815\uc758 \ubc0f \uc5f0\uad6c\ub85c \uc774\uc5b4\uc84c\ub2e4 [11, 8].<\/p>\n\n\n\n<p>DP\ub294 \ub2e4\uc74c\uc744 \ubcf4\uc7a5\ud55c\ub2e4: <br>\uc5b4\ub5a4 \ub370\uc774\ud130\ubca0\uc774\uc2a4\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \ud2b9\uc815 \ucc38\uc5ec\uc790 i\uc758 \uc874\uc7ac \uc5ec\ubd80\uac00 \ub370\uc774\ud130 \uacf5\uac1c \uba54\ucee4\ub2c8\uc998\uc758 \ucd9c\ub825 s\uc5d0 \ubbf8\uce58\ub294 \ud655\ub960\uc801 \uc601\ud5a5\uc774 \ucd5c\ub300 \\(e^{\\epsilon}\\)\ubc30\ub97c \ucd08\uacfc\ud558\uc9c0 \uc54a\ub3c4\ub85d \ud55c\ub2e4. (\uc989, \ud2b9\uc815 \uac1c\uc778\uc758 \ub370\uc774\ud130\uac00 \ud3ec\ud568\ub418\uc5c8\ub294\uc9c0 \uc5ec\ubd80\uac00 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc774 \uc81c\ud55c\ub41c\ub2e4.)<\/p>\n\n\n\n<p>\uadf8\ub7ec\ub098, <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ubcf4\uc7a5\ud558\uba74\uc11c\ub3c4 \ub370\uc774\ud130 \uc720\uc6a9\uc131\uc744 \uc720\uc9c0\ud560 \uc218 \uc788\ub294\uac00? \ub77c\ub294 \uc9c8\ubb38\uc774 \ub0a8\ub294\ub2e4.<\/mark><br>\uadf9\ub2e8\uc801\uc778 \uacbd\uc6b0, \ub370\uc774\ud130\ub97c \uc804\ud600 \ubcf4\uc9c0 \uc54a\uace0 \uc77c\uc815\ud55c \uac12\uc744 \ucd9c\ub825\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \ub9cc\ub4e4\uba74 \uc644\ubcbd\ud55c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub294 \uac00\ub2a5\ud558\uc9c0\ub9cc,<br>\uc774\ub294 \uc2e4\uc6a9\uc131\uc774 \uc804\ud600 \uc5c6\ub294(trivially private but not very useful) \uba54\ucee4\ub2c8\uc998\uc774 \ub41c\ub2e4.<br>\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uac00 \uc81c\uacf5\ud558\ub294 \uc5c4\uaca9\ud55c \uc815\uc758\ub97c \uc0ac\uc6a9\ud558\uba74, \ud2b9\uc815\ud55c \uc791\uc5c5\ub4e4\uc774 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638(privacy)\uc640 \uc720\uc6a9\uc131(utility)\uc744 \uacf5\uc2dd\uc801\uc73c\ub85c \ubcf4\uc7a5(formal guarantees)\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uc218\ud589 \uac00\ub2a5\ud568\uc744 \uc99d\uba85\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc5b4\ub5a4 \ubb38\uc81c\uc5d0\uc11c \uc720\uc758\ubbf8\ud55c \uc720\uc6a9\uc131(meaningful utility)\uacfc \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638(differential privacy)\ub97c \ub3d9\uc2dc\uc5d0 \ub2ec\uc131\ud560 \uc218 \uc788\ub294 \uacbd\uc6b0, \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc758 \ubcf4\uc7a5\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \ud574\uc11d\ub41c\ub2e4.<\/p>\n\n\n\n<p>: \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uba54\ucee4\ub2c8\uc998\uc758 \ucd9c\ub825 \ubd84\ud3ec(output distribution)\ub294 \ud2b9\uc815 \ucc38\uc5ec\uc790 i\uc758 \uc874\uc7ac \uc5ec\ubd80\uc5d0 \uac70\uc758 \uc601\ud5a5\uc744 \ubc1b\uc9c0 \uc54a\ub294\ub2e4.<br>\ub530\ub77c\uc11c, \uc774 \uba54\ucee4\ub2c8\uc998\uc740 \ucc38\uc5ec\uc790\u00a0i\uc5d0 \ub300\ud55c \uac1c\uc778\uc815\ubcf4\ub97c \uac70\uc758 \uc720\ucd9c\ud558\uc9c0 \uc54a\uc73c\uba70,<br>\uadf8 \uacb0\uacfc, \ucc38\uc5ec\uc790 i\ub294 \uc790\uc2e0\uc758 \ub370\uc774\ud130\ub97c \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc5d0 \uc548\uc804\ud558\uac8c \uc81c\uacf5\ud560 \uc218 \uc788\ub2e4\uace0 \ub290\ub084 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Differential privacy and incentives.<\/h4>\n\n\n\n<p>\ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 \uc704\uc5d0\uc11c \ub17c\uc758\ud55c \ud574\uc11d\uc744 \uc2ec\uce35\uc801\uc73c\ub85c \ud0d0\uad6c\ud55c\ub2e4.<br><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uac1c\uc778\uc758 \ub370\uc774\ud130\ubca0\uc774\uc2a4 \ucc38\uc5ec \ub3d9\uae30: \uc65c \uc0ac\ub78c\ub4e4\uc774 \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud558\ub294\uac00?<\/mark><\/p>\n\n\n\n<p>\ub9cc\uc57d \uac1c\uc778\uc774 \uc790\uc2e0\uc758 \uc815\ubcf4 \ubcf4\ud638\uc5d0 \ub300\ud55c \uc6b0\ub824\ub97c \uac00\uc9c0\uace0 \uc788\ub2e4\uba74, \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud558\ub294 \ub300\uc2e0 \uc774\ub97c \uc0c1\uc1c4\ud560 \uc218 \uc788\ub294 \uc778\uc13c\ud2f0\ube0c\ub97c \ubc1b\uc544\uc57c\ub9cc \ud55c\ub2e4.<br>\uc544\ubb34\ub7f0 \uc778\uc13c\ud2f0\ube0c\ub3c4 \uc81c\uacf5\ud558\uc9c0 \uc54a\ub294 \uc870\uc9c1\uc5d0 \uac1c\uc778\uc774 \uae30\uaebc\uc774 \uc790\uc2e0\uc758 \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud558\ub294 \uac83\uc740 \uc0c1\uc0c1\ud558\uae30 \uc5b4\ub835\ub2e4.<\/p>\n\n\n\n<p>\uac1c\uc778\ub4e4\uc740 \u00a0\uc790\uc2e0\uacfc \ubb34\uad00\ud55c \uc0c1\ud488\uc744 \ud310\ub9e4\ud558\ub294 \ub9c8\ucf00\ud305 \ud68c\uc0ac\uc5d0 \uc790\ubc1c\uc801\uc73c\ub85c \uc815\ubcf4\ub97c \uc81c\uacf5\ud558\uc9c0 \uc54a\ub294\ub2e4.<br>\ub2e8, \uae08\uc804\uc801 \ubcf4\uc0c1 \ub610\ub294 \uacbd\ud488 \ub2f9\ucca8 \uae30\ud68c \ub4f1\uc758 \uc778\uc13c\ud2f0\ube0c\uac00 \uc8fc\uc5b4\uc9c0\uba74 \ucc38\uc5ec\ud560 \uc218 \uc788\ub2e4.<br>\ubc18\uba74, Facebook\uc5d0\uc11c \uce5c\uad6c\ub4e4\uacfc \uc5f0\uacb0\ub418\uac70\ub098, Google\uc758 \uc774\uba54\uc77c \uc11c\ube44\uc2a4\ub97c \uc774\uc6a9\ud558\ub294 \uac83\uacfc \uac19\uc740 \uc774\ub4dd\uc774 \uc788\ub2e4\uba74, \uac1c\uc778\ub4e4\uc740 \uae30\uaebc\uc774 \uac1c\uc778\uc815\ubcf4\ub97c \uacf5\uac1c\ud55c\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\uac8c\uc784 \uc774\ub860\uc801 \uad00\uc810\uc5d0\uc11c\uc758 \uc811\uadfc<\/h5>\n\n\n\n<p>\uac8c\uc784 \uc774\ub860(game theory) \uad00\uc810\uc5d0\uc11c \uc811\uadfc\ud558\uba74, \ud2b9\uc815 \ub370\uc774\ud130\ubca0\uc774\uc2a4\uac00 \ubbfc\uac10\ud55c \uc815\ubcf4(sensitive information)\ub97c \uc218\uc9d1\ud560 \uacbd\uc6b0, \ud574\ub2f9 \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc5d0\ub294 \uac1c\uc778\uc774 \ucc38\uc5ec\ud558\ub3c4\ub85d \uc720\ub3c4\ud558\ub294 \uac8c\uc784(game)\uc774 \uc874\uc7ac\ud574\uc57c \ud55c\ub2e4. \uc989, \ub370\uc774\ud130\ubca0\uc774\uc2a4 \ucc38\uc5ec\ub97c \uc704\ud55c \uc778\uc13c\ud2f0\ube0c \uad6c\uc870\uac00 \ud544\uc694\ud558\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\uc77c\ubc18\uc801\uc778 \uc778\uc13c\ud2f0\ube0c \uc124\uc815<\/h5>\n\n\n\n<p>\ubcf8 \uc5f0\uad6c\uc5d0\uc11c\ub294 \uac00\uc7a5 \uc77c\ubc18\uc801\uc778 \uc778\uc13c\ud2f0\ube0c \uc124\uc815\uc744 \ub2e4\uc74c \ub450 \uac00\uc9c0 \uad00\uc810\uc5d0\uc11c \uc5f0\uad6c\ud55c\ub2e4.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\uac1c\uc778\uc758 \uc778\uc13c\ud2f0\ube0c\ub294 \uc11c\ub85c \ucda9\ub3cc\ud560 \uc218 \uc788\uc73c\uba70, \ub370\uc774\ud130\ubca0\uc774\uc2a4 \uad00\ub9ac\uc790\uc758 \uc778\uc13c\ud2f0\ube0c\uc640\ub3c4 \uc77c\uce58\ud558\uc9c0 \uc54a\uc744 \uc218 \uc788\ub2e4.<\/li>\n\n\n\n<li>\uac1c\uc778\uc740 \uc790\uc2e0\uc758 \uc774\uc775\uc744 \uc704\ud574 \ub370\uc774\ud130\ub97c \uac70\uc9d3\uc73c\ub85c \ubcf4\uace0\ud560 \uc218 \uc788\ub2e4.<\/li>\n<\/ol>\n\n\n\n<p>\uc774\uc640 \ub2e4\ub978 \uac00\uc815\uc744 \uc0ac\uc6a9\ud558\ub294 \uc5f0\uad6c\ub4e4\uc5d0 \ub300\ud55c \ub17c\uc758\ub294 2.4.1\uc808\uc5d0\uc11c \ub2e4\ub8ec\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2. Our results<\/h3>\n\n\n\n<p>\uc774 \ub17c\ubb38\uc758 \uc8fc\uc694 \uae30\uc5ec(contribution)\ub294 \uac1c\ub150\uc801(conceptual)\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc800\uc790\ub294 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638(differential privacy)\uc640 \uac8c\uc784 \uc774\ub860\uc801 \uc778\uc13c\ud2f0\ube0c(game-theoretic incentives)\ub97c \uacb0\ud569\ud55c \uc790\uc5f0\uc2a4\ub7fd\uace0 \uc77c\uad00\ub41c \ubaa8\ub378\uc744 \uc81c\uc548\ud55c\ub2e4.<br>\uc989, \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc640 \uc778\uc13c\ud2f0\ube0c \ud638\ud658\uc131(incentive compatibility)\uc744 \ub3d9\uc2dc\uc5d0 \uace0\ub824\ud558\ub294 \ubaa8\ub378\uc744 \uc5f0\uad6c\ud574\uc57c \ud55c\ub2e4\uace0 \uc8fc\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\uae0d\uc815\uc801\uc778 \uacb0\uacfc<\/h5>\n\n\n\n<p>\uc800\uc790\ub294 \uc81c\uc548\ud55c \ubaa8\ub378\uc5d0\uc11c \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uc778\uc13c\ud2f0\ube0c\uc640 \uc591\ub9bd \uac00\ub2a5\ud558\uac8c(incentive-compatible way) \ub2ec\uc131\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc774\ub294 \uc77c\ubc18\uc801\uc778 \uae0d\uc815\uc801\uc778 \uacb0\uacfc(general positive results)\ub97c \uc99d\uba85\ud55c\ub2e4.<br>\uc989, \uc801\uc808\ud55c \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\ub97c \ud1b5\ud574 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uc720\uc9c0\ud558\uba74\uc11c\ub3c4 \uc0ac\ub78c\ub4e4\uc774 \uc9c4\uc2e4\ud558\uac8c \ub370\uc774\ud130\ub97c \uc81c\uacf5\ud558\ub3c4\ub85d \uc720\ub3c4\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\ubd80\uc815\uc801\uc778 \uacb0\uacfc<\/h5>\n\n\n\n<p>\ubc18\uba74, \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc5d0 \uba85\ud655\ud55c \ube44\uc6a9(explicit costs)\uc744 \ubd80\uc5ec\ud560 \uacbd\uc6b0, \ucd94\uac00\uc801\uc778 \uc8fc\uc758\uac00 \ud544\uc694\ud568\uc744 \ubcf4\uc774\ub294 \ubd80\uc815\uc801\uc778 \uacb0\uacfc(negative results)\ub3c4 \uc81c\uc2dc\ud55c\ub2e4.<br>\uc989, \uc798\ubabb\ub41c \ube44\uc6a9 \uc124\uacc4\ub294 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc640 \uc778\uc13c\ud2f0\ube0c \ud638\ud658\uc131\uc744 \uc800\ud574\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">2.1. Our model<\/h4>\n\n\n\n<h5 class=\"wp-block-heading\">The differential privacy setting.<\/h5>\n\n\n\n<p>\ub370\uc774\ud130\ubca0\uc774\uc2a4 \uad00\ub9ac\uc790(database curator)\ub294 \uac1c\uc778\ub4e4\ub85c\ubd80\ud130 \uc815\ubcf4\ub97c \uc81c\uacf5\ubc1b\uc544 \ub370\uc774\ud130\ubca0\uc774\uc2a4\ub97c \uad6c\ucd95\ud55c\ub2e4.<br>\ub370\uc774\ud130\ubca0\uc774\uc2a4\uc758 \uac01 \ud589(row)\uc740 \ud55c \uac1c\uc778\uc758 \uc815\ubcf4\ub97c \ud3ec\ud568\ud55c\ub2e4.<br>\uad00\ub9ac\uc790\ub294 \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc5d0 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uba54\ucee4\ub2c8\uc998(release mechanism)\uc744 \uc801\uc6a9\ud558\uc5ec \uacb0\uacfc\ub97c \uc0dd\uc131\ud55c \ud6c4 \uc774\ub97c \uacf5\uac1c(publish)\ud55c\ub2e4.<\/p>\n\n\n\n<p>\ub370\uc774\ud130 \uacf5\uac1c \uba54\ucee4\ub2c8\uc998\uc5d0\ub294 \ucd9c\ub825\uc758 \ud488\uc9c8\uc744 \ud3c9\uac00\ud558\ub294 \ud488\uc9c8 \uc9c0\ud45c(quality metric)\uac00 \uc874\uc7ac\ud55c\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4.<br>\ub370\uc774\ud130\ubca0\uc774\uc2a4 \uad00\ub9ac\uc790\ub294 \ud488\uc9c8\uc774 \ub192\uc740(high quality) \ucd9c\ub825\uc744 \uc0dd\uc131\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uc6d0\ud55c\ub2e4.<br>\ubc18\uba74, \uac1c\uc778\ub4e4\uc740 \ub370\uc774\ud130\uac00 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \ucc98\ub9ac\ub418\uae30\ub97c \uc6d0\ud55c\ub2e4.<br>\uc774 \ub450 \uac00\uc9c0 \ubaa9\ud45c\ub294 \uc11c\ub85c \ucda9\ub3cc(tension)\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">The mechanism design setting.<\/h5>\n\n\n\n<p>\ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4(mechanism design)\uc758 \uac8c\uc784 \uc774\ub860\uc801 \uc124\uc815(game-theoretic setting)\uc744 \ube44\uacf5\uc2dd\uc801\uc73c\ub85c \uc18c\uac1c\ud55c \ud6c4, \uc774\ub97c \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638(differential privacy) \ubb38\uc81c\uc640 \uc5f0\uacb0\ud55c\ub2e4. (in Section 3)<br>\ubcf4\ub2e4 \uad6c\uccb4\uc801\uc778 \uc774\ud574\ub97c \ub3d5\uae30 \uc704\ud574, \ub17c\ubb38\uc5d0\uc11c\ub294 \uac01 \uac1c\ub150\uc744 \ub2e8\uc77c \ud488\ubaa9(single-item) \uacbd\ub9e4\uc758 \ub9e5\ub77d\uc5d0\uc11c \uc124\uba85\ud55c\ub2e4.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\uba54\ucee4\ub2c8\uc998 \uc124\uacc4(mechanism design)\uc5d0\uc11c\ub294\u00a0 n \uba85\uc758 \ud50c\ub808\uc774\uc5b4(players)\uac00 \uc874\uc7ac\ud558\uba70, \uac01 \ud50c\ub808\uc774\uc5b4\ub294 \uac1c\uc778\uc801\uc778 \uc815\ubcf4(private information)\uc778 \u201c\uc720\ud615(type)\u201c\uc744 \uac00\uc9c4\ub2e4.<br>(\uc608: \uacbd\ub9e4\uc758 \uacbd\uc6b0, \ud50c\ub808\uc774\uc5b4\uc758 \u201c\uc720\ud615\u201d\uc740 \ud574\ub2f9 \ud488\ubaa9\uc5d0 \ub300\ud55c \uc790\uc2e0\uc758 \uac00\uce58 \ud3c9\uac00(value of the item)\uc774\ub2e4.<\/li>\n\n\n\n<li>\uac00\ub2a5\ud55c \uacb0\uacfc \uacf5\uac04(outcome space)\uc774 \uc874\uc7ac\ud55c\ub2e4.<br>(\uc608: \uacbd\ub9e4\uc758 \uacbd\uc6b0, \uacb0\uacfc\ub294 \ub099\ucc30\uc790(winner)\uc758 \uacb0\uc815\uacfc \ucd5c\uc885 \uac00\uaca9(price)\uc774\ub2e4.)<\/li>\n\n\n\n<li>\uac01 \ud50c\ub808\uc774\uc5b4\ub294 \uac1c\uc778\uc801\uc778 \ud6a8\uc6a9 \ud568\uc218(utility function)\ub97c \uac00\uc9c0\uba70, \ud2b9\uc815 \uacb0\uacfc\uc5d0\uc11c \uc790\uc2e0\uc774 \uc5bb\ub294 \ud6a8\uc6a9\uc744 \uacb0\uc815\ud55c\ub2e4.<br>(\uc608: \uacbd\ub9e4\uc758 \uacbd\uc6b0, \ub099\ucc30\ub41c \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9: \ud488\ubaa9 \uac00\uce58 &#8211; \uc9c0\ubd88 \uac00\uaca9. \ub099\ucc30\ub418\uc9c0 \uc54a\uc740 \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9: 0)<\/li>\n\n\n\n<li>\uac01 \ud50c\ub808\uc774\uc5b4\uc758 \ubaa9\ud45c\ub294 \uc790\uc2e0\uc758 \uac1c\ubcc4 \ud6a8\uc6a9(individual utility)\uc744 \ucd5c\uc801\ud654\ud558\ub294 \uac83\uc774\ub2e4.<\/li>\n\n\n\n<li>\uae00\ub85c\ubc8c \ud6a8\uc6a9(global utility) \ud568\uc218\ub3c4 \uc874\uc7ac\ud558\uba70, \uc774\ub294 \uc804\uccb4 \uacb0\uacfc\uc758 \ud488\uc9c8\uc744 \ud3c9\uac00\ud55c\ub2e4.<br>(\uc608: \uc0ac\ud68c\uc801 \ubcf5\uc9c0(social welfare) = \ubaa8\ub4e0 \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud569)<\/li>\n<\/ol>\n\n\n\n<p>\uba54\ucee4\ub2c8\uc998(mechanism)\uc774\ub780,<br>\ud50c\ub808\uc774\uc5b4\ub4e4\uc758 \uc720\ud615(type) \uc124\uc815\uc744 \ud2b9\uc815 \uacb0\uacfc(outcome)\ub85c \ub9e4\ud551\ud558\ub294 (\ub79c\ub364\ud654 \uac00\ub2a5) \ud568\uc218\uc774\ub2e4.<br><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0\uc11c \uc5f0\uad6c\ud558\ub294 \ud575\uc2ec \ubb38\uc81c\ub294 \ub2e4\uc74c \ub450 \uac00\uc9c0 \uc18d\uc131\uc744 \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ucd95\ud558\ub294 \uac83\uc774\ub2e4.<\/mark><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\ud6a8\uc728\uc131 (Efficiency)<br>\ubaa8\ub4e0 \ud50c\ub808\uc774\uc5b4 \uc720\ud615\uc5d0 \ub300\ud574, \uba54\ucee4\ub2c8\uc998\uc774 \uc0dd\uc131\ud558\ub294 \uae30\ub300 \uae00\ub85c\ubc8c \ud6a8\uc6a9(expected global utility)\uc774 \ucd5c\uc801 \uae00\ub85c\ubc8c \ud6a8\uc6a9(optimal global utility)\uc5d0 \uac00\uae5d\ub3c4\ub85d \ud574\uc57c \ud55c\ub2e4.<\/li>\n\n\n\n<li>\uc9c4\uc2e4\uc131 (Truthfulness)<br>\uc5b4\ub5a0\ud55c \ud50c\ub808\uc774\uc5b4 \uc720\ud615 \uc124\uc815\uc5d0\uc11c\ub3c4, \ud2b9\uc815 \ud50c\ub808\uc774\uc5b4 i\uac00 \uac70\uc9d3 \uc720\ud615(false type)\uc744 \ubcf4\uace0\ud588\uc744 \ub54c \uadf8\uac00 \uc9c4\uc2e4\ud558\uac8c \uc720\ud615\uc744 \ubcf4\uace0\ud55c \uacbd\uc6b0\ubcf4\ub2e4 \ub354 \ud070 \uae30\ub300 \ud6a8\uc6a9\uc744 \uc5bb\uc744 \uc218 \uc5c6\ub2e4.<br>\uc989, \uac01 \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \uc720\ud615\uc744 \uc815\uc9c1\ud558\uac8c \ubcf4\uace0\ud558\ub294 \uac83\uc774 \ucd5c\uc120\uc758 \uc804\ub7b5\uc774 \ub418\ub3c4\ub85d(truthful, incentive-compatible) \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud574\uc57c \ud55c\ub2e4.<\/li>\n<\/ol>\n\n\n\n<p>\uac1c\uc778 \ud6a8\uc6a9(individual utility)\uacfc \uae00\ub85c\ubc8c \ud6a8\uc6a9(global utility)\uc774 \ubc18\ub4dc\uc2dc \uc77c\uce58\ud558\uc9c0 \uc54a\uae30 \ub54c\ubb38\uc5d0, \uc704\uc758 \ub450 \uac00\uc9c0 \uae30\uc900(\ud6a8\uc728\uc131 &amp; \uc9c4\uc2e4\uc131)\uc744 \ub3d9\uc2dc\uc5d0 \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ud604\ud558\ub294 \uac83\uc740 \ub9e4\uc6b0 \uc5b4\ub835\ub2e4.<br>\uc608\ub97c \ub4e4\uc5b4, \ub2e8\uc77c \ud488\ubaa9 \uacbd\ub9e4(single-item auction) \ubb38\uc81c\ub97c \uc5f0\uad6c\ud55c \uacb0\uacfc, \u201c\ube45\ub9ac(Vickrey) 2\ucc28 \uac00\uaca9 \uacbd\ub9e4(Vickrey 2nd-price auction)\u201d \uba54\ucee4\ub2c8\uc998\uc774 \ub3c4\ucd9c\ub418\uc5c8\ub2e4.<br>(\uc774\ub294 \uc9c4\uc2e4\uc131\uc744 \ub9cc\uc871\ud558\ub294 \ub300\ud45c\uc801\uc778 \uacbd\ub9e4 \uba54\ucee4\ub2c8\uc998 \uc911 \ud558\ub098\uc774\ub2e4.)<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">The combined model.<\/h5>\n\n\n\n<p>\uc774\uc81c \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ud658\uacbd\uc744 \uac8c\uc784 \uc774\ub860\uc801 \uc6a9\uc5b4\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc790\uc5f0\uc2a4\ub7fd\uac8c \ub2e4\uc2dc \uc11c\uc220\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uac1c\uc778\uc740 \ud50c\ub808\uc774\uc5b4\uc774\uba70, \uac01 \uac1c\uc778\uc758 \uac1c\uc778 \uc815\ubcf4\ub294 \uadf8\uc758 \uc720\ud615\uc774\ub2e4.<br>\ub370\uc774\ud130\ubca0\uc774\uc2a4\ub294 \ubaa8\ub4e0 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uc744 \uc5f0\uacb0\ud55c \uac83\uc774\ub2e4.<br>\ub370\uc774\ud130\ubca0\uc774\uc2a4 \uacf5\uac1c \uba54\ucee4\ub2c8\uc998\uc740 \uac8c\uc784 \uc774\ub860\uc801 \uc758\ubbf8\uc5d0\uc11c\uc758 \uba54\ucee4\ub2c8\uc998\uacfc \ub3d9\uc77c\ud558\ub2e4.<br>\ud488\uc9c8 \uc9c0\ud45c\ub294 \uac8c\uc784\uc758 \uae00\ub85c\ubc8c \ud6a8\uc6a9\uc774\uba70, \ub530\ub77c\uc11c \u201c\uc815\ud655\ud55c\u201d \uacf5\uac1c \uba54\ucee4\ub2c8\uc998\uc740 \u201c\ud6a8\uc728\uc801\uc778\u201d \uac8c\uc784 \uc774\ub860\uc801 \uba54\ucee4\ub2c8\uc998\uc5d0 \ud574\ub2f9\ud55c\ub2e4.<br>\uc704 \ub0b4\uc6a9 \uc678\uc5d0\ub3c4, \uac1c\uc778 \ud6a8\uc6a9 \ud568\uc218\ub294 \uc774\uc81c \ud50c\ub808\uc774\uc5b4\ub4e4\uc758 \ud589\ub3d9\uc5d0\ub3c4 \uc601\ud5a5\uc744 \ubbf8\uce60 \uc218 \uc788\ub2e4.<br>\uc9c4\uc2e4\uc131\uc740 \ub2e8\uc21c\ud788 \uac8c\uc784 \uc774\ub860\uc758 \ud45c\uc900 \uac1c\ub150\uc774\uae30 \ub54c\ubb38\ub9cc\uc774 \uc544\ub2c8\ub77c, \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc790\uccb4\uac00 \uc9c4\uc2e4\uc131\uc774 \uc5c6\uc73c\uba74 \uc758\ubbf8\uac00 \uc5c6\uae30 \ub54c\ubb38\uc5d0 \ud544\uc218\uc801\uc774\ub2e4.<br>\uc218\uc9d1\ub41c \ub370\uc774\ud130\uac00 \uc798\ubabb \ubcf4\uace0\ub418\uc5c8\ub2e4\uba74, \ub370\uc774\ud130\ubca0\uc774\uc2a4 \uad00\ub9ac\uc790\uc5d0\uac8c \uac70\uc758 \uc4f8\ubaa8\uac00 \uc5c6\ub2e4.<br>\uac8c\ub2e4\uac00, \uc798\ubabb\ub41c \ub370\uc774\ud130\ub97c \ubcf4\ud638\ud558\ub294 \uac83\uc740 \ubd88\ud544\uc694\ud574 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<p>\ub610\ud55c <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc5d0\uc11c \uc8fc\uc694\ud55c \uc6b0\ub824\ub294 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc218\uc900\uc774 \ub108\ubb34 \ub0ae\uc73c\uba74 \uac1c\uc778\ub4e4\uc774 \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc5d0 \ucc38\uc5ec\ud558\uc9c0 \uc54a\uc744 \uc218\ub3c4 \uc788\ub2e4\ub294 \uc810\uc774\ub2e4.<\/mark><br>\uac8c\uc784 \uc774\ub860\uc801 \ud658\uacbd\uc5d0\uc11c\ub294 \uc9c4\uc2e4\uc131\uacfc \ucc38\uc5ec\uac00 \ubc00\uc811\ud558\uac8c \uad00\ub828\ub418\uc5b4 \uc788\ub2e4. \uac8c\uc784\uc744 \ud655\uc7a5\ud558\uc5ec \u201c\u22a5\u201d \uc720\ud615\uc744 \ucd94\uac00\ud558\uba74, \uc774\ub294 \ube44\ucc38\uc5ec\ub97c \uc758\ubbf8\ud558\uba70, \ud50c\ub808\uc774\uc5b4\uac00 \u201c\u22a5\u201d \uc720\ud615\uc73c\ub85c \uc774\ud0c8\ud558\ub294 \uac83\uc740 \ube44\ucc38\uc5ec\ub97c \ub098\ud0c0\ub0bc \uc218 \uc788\ub2e4.<br>\ubc18\ub300\ub85c, \uc790\uc2e0\uc758 \uc2e4\uc81c \uc720\ud615\uacfc \ubb34\uad00\ud55c \uc720\ud615\uc744 \ubcf4\uace0\ud558\ub294 \ud50c\ub808\uc774\uc5b4\ub294 \uc5b4\ub5a4 \uc758\ubbf8\uc5d0\uc11c\ub294 \ucc38\uc5ec\ud558\uc9c0 \uc54a\ub294 \uac83\uc744 \uc120\ud0dd\ud55c \uac83\uc774\ub2e4.<br>\uc774 \ub17c\ubb38\uc758 \ub098\uba38\uc9c0 \ubd80\ubd84\uc5d0\uc11c\ub294 \uc9c4\uc2e4\uc131\uc5d0 \ucd08\uc810\uc744 \ub9de\ucd94\ub418, \ube44\ucc38\uc5ec\uac00 \uc9c4\uc2e4\uc131\uc5d0\uc11c \ubc97\uc5b4\ub098\ub294 \ud2b9\uc815\ud55c \ud615\ud0dc\ub77c\ub294 \uc810\uc744 \uc774\ud574\ud558\uace0 \ub17c\uc758\ub97c \uc9c4\ud589\ud55c\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Roadmap.<\/h5>\n\n\n\n<p>\uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub9cc\uc744 \ub3c5\ub9bd\uc801\uc73c\ub85c \uc5f0\uad6c\ud560 \ub54c \ub9cc\uc871\uc2a4\ub7ec\uc6cc \ubcf4\uc774\ub294 \uba54\ucee4\ub2c8\uc998\ub3c4, \uc9c4\uc2e4\uc131\uc744 \uba85\uc2dc\uc801\uc73c\ub85c \uace0\ub824\ud558\uba74 \ubc18\ub4dc\uc2dc \ub9cc\uc871\uc2a4\ub7ec\uc6b4 \uac83\uc740 \uc544\ub2c8\ub2e4.<br>\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc640 \uc9c4\uc2e4\uc131\uc758 \uad00\uacc4\ub97c \ub450 \uac00\uc9c0 \ud504\ub808\uc784\uc6cc\ud06c\uc5d0\uc11c \uc0b4\ud3b4\ubcf8\ub2e4.<\/p>\n\n\n\n<p>\uccab \ubc88\uc9f8 \ud504\ub808\uc784\uc6cc\ud06c\uc5d0\uc11c\ub294, <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uc9c4\uc2e4\uc131\uc744 \ub9cc\uc871\ud558\uace0 \ud6a8\uc728\uc801\uc774\uba70 \ucd9c\ub825\uc774 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub530\ub974\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\uc131\ud55c\ub2e4.<\/mark><br>\uc774 \ubaa8\ub378\uc5d0\uc11c\ub294 <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uba85\ud655\ud55c \uc218\uce58\uac12\uc73c\ub85c \ud45c\ud604\ud558\uc9c0 \uc54a\uace0, \ub2e8\uc21c\ud788 \uba54\ucee4\ub2c8\uc998\uc758 \ucd94\uac00\uc801\uc778 \uc18d\uc131\uc73c\ub85c \uace0\ub824\ud55c\ub2e4.<br>\uc774\ub7ec\ud55c \uba54\ucee4\ub2c8\uc998\uc744 PTE\ub77c\uace0 \ubd80\ub974\uba70,<\/mark> \uc720\ud615 \uacf5\uac04\uc774 \uc791\uace0 \uae00\ub85c\ubc8c \ud6a8\uc6a9\uc774 \ud2b9\uc815 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uc5d0 \ubbfc\uac10\ud558\uc9c0 \uc54a\uc73c\uba70 \uac01 \uc720\ud615\uc744 \uac00\uc9c4 \ud50c\ub808\uc774\uc5b4 \uc218\uc5d0\ub9cc \uc758\uc874\ud558\ub294 \uac8c\uc784\uc5d0 \ub300\ud574, \uc9c4\uc2e4\ud558\uace0 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 PTE \uba54\ucee4\ub2c8\uc998\uc73c\ub85c \ubcc0\ud658\ud558\ub294 \ubc29\ubc95\uc744 \uc81c\uc2dc\ud558\uc5ec \ucd5c\ucd08\uc758 PTE \uba54\ucee4\ub2c8\uc998\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<p>\ub450 \ubc88\uc9f8 \ud504\ub808\uc784\uc6cc\ud06c\uc5d0\uc11c\ub294 <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc758 \uac00\uce58\ub97c \uba85\uc2dc\uc801\uc73c\ub85c \uc218\ub7c9\ud654\ud55c\ub2e4.<\/mark><br>\uba54\ucee4\ub2c8\uc998\uc5d0 \uc758\ud574 \uc720\ucd9c\ub418\ub294 \uc815\ubcf4\ub7c9\uc5d0 \ub300\ud574 0\uc774 \uc544\ub2cc \ube44\uc6a9\uc744 \ubd80\uc5ec\ud558\uace0, \uc815\ubcf4 \uacf5\uac1c \ube44\uc6a9\uc774 \ud50c\ub808\uc774\uc5b4\uac00 \uac8c\uc784\uc5d0\uc11c \uc5bb\ub294 \ud6a8\uc6a9\uc744 \ucd08\uacfc\ud558\ub294 \uacbd\uc6b0\ub97c \ubd84\uc11d\ud55c\ub2e4.<br>\uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc5d0 \ube44\uc6a9\uc774 \ubd80\uc5ec\ub420 \uacbd\uc6b0, \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc870\ucc28\ub3c4 \uac1c\uc778\uc774 \uc790\uc2e0\uc758 \uc815\ubcf4\ub97c \uc9c4\uc2e4\ud558\uac8c \uacf5\uac1c\ud558\ub3c4\ub85d \ub3d9\uae30\ubd80\uc5ec\ud558\uc9c0 \ubabb\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778\ub2e4.<br>\uccab \ubc88\uc9f8 \ud504\ub808\uc784\uc6cc\ud06c\ub294 \uac1c\uc778\uc815\ubcf4 \uc190\uc2e4\uc744 \uc815\ub7c9\ud654\ud558\uc9c0 \uc54a\uae30 \ub54c\ubb38\uc5d0 \ub2e4\uc18c \ub2e8\uc21c\ud574 \ubcf4\uc77c \uc218 \uc788\uc9c0\ub9cc, \uadf8\uacf3\uc5d0\uc11c \uac1c\ubc1c\ub41c \uae30\ubc95\ub4e4\uc774 \ub450 \ubc88\uc9f8 \ud504\ub808\uc784\uc6cc\ud06c\uc5d0\ub3c4 \uc801\uc6a9\ub420 \uc218 \uc788\uc74c\uc774 \uc774\ud6c4 \uc5f0\uad6c\uc5d0\uc11c \ubc1d\ud600\uc84c\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">2.2. Private, truthful, and efficient (PTE) mechanisms<\/h4>\n\n\n\n<h5 class=\"wp-block-heading\">The Exponential Mechanism is not necessarily truthful.<\/h5>\n\n\n\n<p>\uc800\uc790\uc758 \uccab \ubc88\uc9f8 \uacb0\uacfc\ub294 <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uc9c0\uc218 \uba54\ucee4\ub2c8\uc998(Exponential Mechanism)\uc774 \uc9c4\uc2e4\uc131\uc744 \ub9cc\uc871\ud558\ub294\uc9c0 \uc5ec\ubd80\uc5d0 \ub300\ud55c \uc9c8\ubb38\uc744 \ub2e4\uc2dc \ud0d0\uc0c9\ud55c\ub2e4.<\/mark> Nissim et al. [31]\uc740 \uc774\ubbf8 \uc9c0\uc218 \uba54\ucee4\ub2c8\uc998\uc774 \uc9c4\uc2e4\uc131\uc744 \ub9cc\uc871\ud558\uc9c0 \uc54a\uc74c\uc744 \ubcf4\uc774\ub294 \ubc18\ub840(counter-example)\ub97c \uc81c\uc2dc\ud55c \ubc14 \uc788\ub2e4. \uadf8\ub7ec\ub098, \uadf8\ub4e4\uc774 \uc81c\uc2dc\ud55c \ubc18\ub840\ub294 \ub2e4\uc18c \uc778\uc704\uc801\uc774\ub2e4.<br>\uadf8 \uc774\uc720\ub294 \ud574\ub2f9 \uac8c\uc784\uc5d0\uc11c\ub294 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uace0\ub824\ud558\uc9c0 \uc54a\ub354\ub77c\ub3c4 \ud6a8\uc728\uc801\uc774\uace0 \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc874\uc7ac\ud558\uc9c0 \uc54a\uae30 \ub54c\ubb38\uc774\ub2e4.<br>\uc800\uc790\ub294 \ub2e4\uc74c \uc815\ub9ac(Theorem 2.1)\uac00 \uc9c0\uc218 \uba54\ucee4\ub2c8\uc998\uc758 \ub2e8\uc810\uc744 \ub354 \uba85\ud655\ud558\uac8c \ubcf4\uc5ec\uc900\ub2e4\uace0 \uc0dd\uac01\ud55c\ub2e4.<br>\uadf8 \uc774\uc720\ub294 \uc6b0\ub9ac\uac00 \uace0\ub824\ud558\ub294 LINE-1-FAC \uac8c\uc784\uc5d0\uc11c\ub294 \uc9c4\uc2e4\ud558\uace0 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc774 \uc874\uc7ac\ud558\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n\n\n\n<p>\ub354 \ub098\uc544\uac00, \uc800\uc790\ub294 LINE-1-FAC\uc5d0 \ub300\ud574 PTE \uba54\ucee4\ub2c8\uc998\uc870\ucc28 \uc874\uc7ac\ud568\uc744 \ubcf4\uc778\ub2e4.<br>\uc800\uc790\ub294 \uc798 \uc5f0\uad6c\ub41c \uc120\ud615 \uacf5\uac04\uc5d0\uc11c \ud558\ub098\uc758 \uc2dc\uc124\uc744 \ubc30\uce58\ud558\ub294 \uac8c\uc784(1-facility location on a line game, LINE-1-FAC)\uc744 \uace0\ub824\ud55c\ub2e4.<br>\uc774 \uac8c\uc784\uc740 k-\uc2dc\uc124 \ubb38\uc81c(k-facility problem) [31, 26, 1]\uc758 \ud2b9\uc218\ud55c \uacbd\uc6b0\uc774\uba70, \ub2e8\uc77c \ubd09\uc6b0\ub9ac \uc120\ud638(single-peaked preference) \uac8c\uc784 [28, 33]\uc758 \uc0ac\ub840\uc774\uae30\ub3c4 \ud558\ub2e4.<br>LINE-1-FAC \uac8c\uc784\uc5d0\uc11c, \uac01 \ud50c\ub808\uc774\uc5b4\ub294 \uad6c\uac04 [0,1] \ub0b4\uc5d0\uc11c \ud55c \uc810\uc744 \uac16\ub294\ub2e4.<br>\uba54\ucee4\ub2c8\uc998\uc740 \uad6c\uac04 [0,1] \ub0b4\uc5d0\uc11c \ud558\ub098\uc758 \uc704\uce58 s\ub97c \ucd9c\ub825\ud574\uc57c \ud55c\ub2e4.<br>\uac01 \uac1c\uc778\uc758 \ubaa9\ud45c\ub294 \ucd9c\ub825\ub41c s\uae4c\uc9c0\uc758 \uac70\ub9ac\ub97c \ucd5c\uc18c\ud654\ud558\ub294 \uac83\uc774\uba70, \uba54\ucee4\ub2c8\uc998\uc758 \ubaa9\ud45c\ub294 \ubaa8\ub4e0 \uac1c\uc778\uc758 \uac70\ub9ac \ud569\uc744 \ucd5c\uc18c\ud654\ud558\ub294 \uac83\uc774\ub2e4.<br>\uc774 \uac8c\uc784\uc5d0\uc11c\ub294 \uae08\uc804\uc801 \ubcf4\uc0c1\uc774 \uc5c6\ub294(non-monetary) \uc9c4\uc2e4\ud558\uace0 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc774 \uc874\uc7ac\ud558\ub294\ub370, \uc774 \uac8c\uc784\uc5d0\uc11c\ub294 \uae08\uc804\uc801 \ubcf4\uc0c1\uc774 \uc5c6\ub294(non-monetary) \uc9c4\uc2e4\ud558\uace0 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc774 \uc874\uc7ac\ud558\ub294\ub370, \uc800\uc790\ub294 \ub2e4\uc74c\uc744 \uc99d\uba85\ud55c\ub2e4.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"109\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-1024x109.png\" alt=\"\" class=\"wp-image-4866\" srcset=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-1024x109.png 1024w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-300x32.png 300w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-768x82.png 768w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image.png 1222w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\uc815\ub9ac 2.1. LINE-1-FAC \uac8c\uc784\uc5d0\uc11c, \uc5b4\ub5a0\ud55c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc218\uc900\u00a0\\(\\epsilon > 0\\) \uc5d0 \ub300\ud574\uc11c\ub3c4 \uc9c0\uc218 \uba54\ucee4\ub2c8\uc998(Exponential Mechanism)\uc740 \uc9c4\uc2e4\uc131\uc744 \ub9cc\uc871\ud558\uc9c0 \uc54a\ub294\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Transforming a truthful and efficient mechanism into a private, truthful, and efficient mechanism.<\/h5>\n\n\n\n<p>\uc800\uc790\uc758 \uc8fc\uc694 \uae0d\uc815\uc801\uc778 \uae30\uc220\uc801 \uacb0\uacfc\ub294 \uc9c4\uc2e4\ud558\uace0 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 PTE \uba54\ucee4\ub2c8\uc998\uc73c\ub85c \ubcc0\ud658\ud558\ub294 \ubc29\ubc95\uc774\ub2e4.<br>\ubcf4\ub2e4 \uc815\ud655\ud788 \ub9d0\ud558\uba74, \uc800\uc790\ub294 \\((\\epsilon, \\eta)\\)-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uac1c\ub150\uc744 \uc0ac\uc6a9\ud55c\ub2e4 [10].<br>\uc774 \uac1c\ub150\uc740 \uae30\uc874 \\(\\epsilon\\)-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc5d0\uc11c \uc694\uad6c\ud558\ub294\u00a0\\(e^{\\epsilon}\\) \ubc30 \ud655\ub960 \ucc28\uc774 \uc870\uac74 \uc678\uc5d0\ub3c4, \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc758 \ucd9c\ub825 \ubd84\ud3ec \ucc28\uc774\uc5d0 \ub300\ud574 \uc791\uc740 \ucd94\uac00\uc801\uc778 \uc624\ucc28 \\(\\eta\\) \ub97c \ud5c8\uc6a9\ud558\ub294 \ubc29\uc2dd\uc774\ub2e4.<br>\uc800\uc790\uc758 \ubcc0\ud658 \uae30\ubc95\uc740 \uc5b4\ub5a4 \uc9c4\uc2e4\ud558\uace0 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 \\((\\epsilon, \\eta)\\)-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\uba74\uc11c\ub3c4 \uc9c4\uc2e4\ud558\uace0 \\(\\delta\\)-\ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc73c\ub85c \ubcc0\ud658\ud55c\ub2e4.<br>\uc5ec\uae30\uc11c \\(\\delta\ub294 \\epsilon, \\eta\\)\uc5d0 \ub530\ub77c \uacb0\uc815\ub418\ub294 \ucd94\uac00\uc801\uc778 \uadfc\uc0ac \uc624\ucc28(additive approximation error) \uc774\ub2e4.<br>\uc815\ud655\ud55c \uc815\uc758\ub294 3\uc7a5\uc5d0\uc11c \ub17c\uc758\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc774 \ubcc0\ud658 \uae30\ubc95\uc744 \ud1b5\ud574, \ube44\uc790\uba85\ud55c(non-trivial) \uac8c\uc784\uc5d0\uc11c \ucd5c\ucd08\uc758 PTE \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc2dc\ud55c\ub2e4.<br>\ub610\ud55c, \ubcc0\ud658 \uae30\ubc95\uc740 \uacc4\uc0b0 \ud6a8\uc728\uc131(computational efficiency)\uacfc \ube44\uae08\uc804\uc131(moneylessness) \ub4f1\uc758 \uc18d\uc131\uc744 \ubcf4\uc874\ud558\uba70, \uc720\ud615 \uacf5\uac04\uc774 \uc791\uc740 \ubaa8\ub4e0 \uac8c\uc784\uc5d0 \uc801\uc6a9 \uac00\ub2a5\ud558\ub2e4.<br>\ub530\ub77c\uc11c, \uc774 \ubcc0\ud658 \uae30\ubc95\uc744 VCG \uba54\ucee4\ub2c8\uc998\uc5d0 \uc801\uc6a9\ud558\uba74, \uc720\ud615 \uacf5\uac04\uc774 \uc791\uc740 \ubaa8\ub4e0 \uc0ac\ud68c\uc801 \ubcf5\uc9c0 \uac8c\uc784(social welfare games)\uc5d0 \ub300\ud55c PTE \uba54\ucee4\ub2c8\uc998\uc744 \uc5bb\uc744 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc774 \ub17c\ubb38 \uc804\ubc18\uc5d0\uc11c, \uc800\uc790\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uac00\uc815\uc744 \uc0ac\uc6a9\ud55c\ub2e4.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\uac01 \uc0ac\uc6a9\uc790\uc758 \ud6a8\uc6a9 \ud568\uc218(utility function)\ub294 [-1,1] \ubc94\uc704 \ub0b4\uc5d0 \uc874\uc7ac\ud55c\ub2e4.<\/li>\n\n\n\n<li>\uae00\ub85c\ubc8c \ud6a8\uc6a9 \ud568\uc218(global utility function)\ub294 [-n, n] \ubc94\uc704 \ub0b4\uc5d0 \uc874\uc7ac\ud55c\ub2e4.<\/li>\n<\/ol>\n\n\n\n<p>\ud2b9\ud788, \\(\\delta = o(n)\\)\uc744 \ub9cc\uc871\ud558\ub294 \\(\\delta\\)-\ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 \uc5bb\ub294 \uac83\uc774 \uc911\uc694\ud558\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">The transformation.<\/h5>\n\n\n\n<p>\ubcc0\ud658 \ubc29\ubc95\uc758 \uc544\uc774\ub514\uc5b4\ub294 \ud788\uc2a4\ud1a0\uadf8\ub7a8 \ub370\uc774\ud130\ub97c \ube44\uacf5\uac1c\ub85c \uacf5\uac1c\ud558\ub294 \uae30\ubc95 [11]\uc5d0\uc11c \ucc29\uc548\ub418\uc5c8\ub2e4.<br>\uac8c\uc784\uc758 \uc720\ud615 \uacf5\uac04(type space)\uc774 \ud06c\uae30 q\uc778 \uc720\ud55c \uc9d1\ud569\uc774\ub77c\uace0 \uac00\uc815\ud558\uc790.<br>\ud50c\ub808\uc774\uc5b4 \uc785\ub825\uc744 \\(t = (t_1, \u2026, t_n)\\)\uc774\ub77c \ud558\uace0, \uc5ec\uae30\uc11c \\(t_i\\)\ub294 i\ubc88\uc9f8 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uc774\ub77c\uace0 \ud558\uc790.<br>\uc774\uc81c \ud788\uc2a4\ud1a0\uadf8\ub7a8 h\ub97c \uc815\uc758\ud558\ub294\ub370, \uc774\ub294\u00a0q\uac1c\uc758 \ud56d\ubaa9\uc744 \uac00\uc9c0\uba70, \\(h_j = |\\{i | t_i = j\\}|\\)\ub294 \uac01 \uc720\ud615\uc5d0 \ub300\ud574 \ud574\ub2f9 \uc720\ud615\uc744 \uac00\uc9c4 \ud50c\ub808\uc774\uc5b4\uc758 \uc218\ub97c \ub098\ud0c0\ub0b8\ub2e4.<br>\uac01 \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud568\uc218 v(t,s)\ub97c \uac00\uc815\ud558\uc790. \uc5ec\uae30\uc11c\u00a0t\ub294 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615,\u00a0s\ub294 \uac8c\uc784\uc758 \uacb0\uacfc\uc774\ub2e4.<br>\ub610\ud55c, \ud6a8\uc6a9 \ud568\uc218\u00a0v\ub294 [-1,1] \ubc94\uc704 \ub0b4\uc5d0 \uc788\ub2e4\uace0 \uac00\uc815\ud558\uc790.<\/p>\n\n\n\n<p>\uae00\ub85c\ubc8c \ud6a8\uc6a9 \ud568\uc218 w(t,s)\uac00 \uc775\uba85\uc801(anonymous) \uc774\uba70, \uc989 \ud788\uc2a4\ud1a0\uadf8\ub7a8 h\uc5d0\ub9cc \uc758\uc874\ud558\uace0 \uac1c\ubcc4 \ud50c\ub808\uc774\uc5b4\uc758 \uc815\uccb4\uc131\uc5d0\ub294 \uc758\uc874\ud558\uc9c0 \uc54a\ub294\ub2e4\uace0 \uac00\uc815\ud558\uc790.<br>\ub610\ud55c, w\ub294 \ubbfc\uac10\ud558\uc9c0(insensitive) \uc54a\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4.<br>\uc989, \ub450 \ud788\uc2a4\ud1a0\uadf8\ub7a8\u00a0\\(h, h{\\prime}\\)\uc774\u00a0\\(\\ell_1\\) \uac70\ub9ac\uc5d0\uc11c \uac00\uae5d\ub2e4\uba74, \ubaa8\ub4e0 \uacb0\uacfc\u00a0s\uc5d0 \ub300\ud574\u00a0\\(|w(h,s) &#8211; w(h{\\prime},s)|\\)\uac00 \uc791\ub2e4.<br>\uc608\ub97c \ub4e4\uc5b4, \uc0ac\ud68c\uc801 \ubcf5\uc9c0 \ud568\uc218(social welfare function)\ub294 \ubaa8\ub4e0 \uac1c\ubcc4 \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud569\uc73c\ub85c \uc815\uc758\ub418\uba70, \uc774\ub7ec\ud55c \uae00\ub85c\ubc8c \ud6a8\uc6a9 \ud568\uc218\uc758 \ud55c \uac00\uc9c0 \uc608\uc2dc\uac00 \ub41c\ub2e4.<br>\uc77c\ubc18\uc131\uc744 \uc783\uc9c0 \uc54a\uace0, \uc774\ub7ec\ud55c \uae00\ub85c\ubc8c \ud6a8\uc6a9 \ud568\uc218\ub97c \uac00\uc9c0\ub294 \uac8c\uc784\uc5d0 \ub300\ud55c \ubaa8\ub4e0 \uba54\ucee4\ub2c8\uc998\uc740 \uac1c\ubcc4 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uc774 \uc544\ub2cc \ud50c\ub808\uc774\uc5b4 \uc720\ud615\uc758 \ud788\uc2a4\ud1a0\uadf8\ub7a8\uc5d0\ub9cc \uc758\uc874\ud558\uba74 \ucda9\ubd84\ud558\ub2e4.<br>\uc774 \uc0ac\uc2e4\uc740 \ubd80\ub85d A\uc5d0\uc11c \uc99d\uba85\ub41c\ub2e4.<\/p>\n\n\n\n<p>\uc0c1\uc704 \uac1c\ub150\uc5d0\uc11c, \uc800\uc790\uc758 \ubcc0\ud658 \ubc29\ubc95\uc740 \uc9c4\uc2e4\ud558\uace0 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 PTE \uba54\ucee4\ub2c8\uc998\uc73c\ub85c \ubcc0\ud658\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uc791\ub3d9\ud55c\ub2e4.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\uc785\ub825 \ub370\uc774\ud130\uc758 \ud788\uc2a4\ud1a0\uadf8\ub7a8\uc744 \uad6c\uc131\ud55c\ub2e4.<\/li>\n\n\n\n<li>\uac01 \ud788\uc2a4\ud1a0\uadf8\ub7a8 \ud56d\ubaa9\uc5d0 \ub300\ud574 \ub3c5\ub9bd\uc801\uc73c\ub85c, \uc591\ucabd \uae30\ud558 \ubd84\ud3ec(two-sided geometric distribution)\ub97c \ub530\ub974\ub294 \ub178\uc774\uc988\ub97c \ucd94\uac00\ud55c\ub2e4.<\/li>\n\n\n\n<li>\ubcc0\ud615\ub41c(perturbed) \ud788\uc2a4\ud1a0\uadf8\ub7a8\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc6d0\ub798\uc758 \uc9c4\uc2e4\ud558\uace0 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 \uc2e4\ud589\ud55c\ub2e4.<\/li>\n<\/ol>\n\n\n\n<p>\uadf8\ub7ec\ub098, \ub178\uc774\uc988 \ucd94\uac00 \uacfc\uc815\uc5d0\uc11c \ud788\uc2a4\ud1a0\uadf8\ub7a8\uc758 \uac12\uc774 \uc74c\uc218\uac00 \ub418\uc9c0 \uc54a\ub3c4\ub85d \uc8fc\uc758\ud574\uc57c \ud55c\ub2e4.<br>\ub2e8\uc21c\ud788 \uc74c\uc218\ub97c 0\uc73c\ub85c \uc808\ub2e8(truncate)\ud558\ub294 \ubc29\uc2dd\uc740 \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \ubcf4\uc7a5\ud558\uc9c0 \ubabb\ud55c\ub2e4.<br>\uc774\uc5d0 \ub300\ud55c \ud574\uacb0 \ubc29\ubc95\uc740 4\uc7a5\uc5d0\uc11c \ub17c\uc758\ub41c\ub2e4. \uc800\uc790\uc758 \uc808\ucc28\ub97c \ud1b5\ud574 \ub2e4\uc74c \uc815\ub9ac\ub97c \uc5bb\ub294\ub2e4.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"243\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-1-1024x243.png\" alt=\"\" class=\"wp-image-4888\" srcset=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-1-1024x243.png 1024w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-1-300x71.png 300w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-1-768x182.png 768w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-1.png 1070w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"194\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-2-1024x194.png\" alt=\"\" class=\"wp-image-4889\" srcset=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-2-1024x194.png 1024w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-2-300x57.png 300w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-2-768x146.png 768w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-2.png 1064w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\uc815\ub9ac 2.2 (\ube44\uacf5\uc2dd).\u00a0\\(\\epsilon, \\eta > 0\\)\ub77c \ud558\uc790.<br>\uac8c\uc784\u00a0 G \ub294 \uc720\ud615 \uacf5\uac04\uc758 \ud06c\uae30\uac00\u00a0q\uc774\uba70, \uae00\ub85c\ubc8c \ud6a8\uc6a9 \ud568\uc218\uac00 \ud788\uc2a4\ud1a0\uadf8\ub7a8\uc5d0\ub9cc \uc758\uc874\ud558\uace0 \uac1c\ubcc4 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uc5d0 \ub300\ud574 \ubbfc\uac10\ud558\uc9c0 \uc54a\ub2e4\uace0 \uac00\uc815\ud558\uc790.<br>\u00a0M \uc774 \uc9c4\uc2e4\ud558\uace0\u00a0\\(\\delta\\)-\uadfc\uc0ac\uc801\uc73c\ub85c \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc774\ub77c \ud558\uc790.<br>\uadf8\ub7ec\uba74, \uac8c\uc784\u00a0 G \uc5d0 \ub300\ud574\u00a0\\(\\epsilon, \\eta\\)-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\uba70,\u00a0\\(\\delta^{\\prime}\\)-\uadfc\uc0ac\uc801\uc73c\ub85c \ud6a8\uc728\uc801\uc778 \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\u00a0\\(M{\\prime}\\)\uc774 \uc874\uc7ac\ud55c\ub2e4. \uc5ec\uae30\uc11c\u00a0\\(\\delta^{\\prime} \\approx \\delta\\)\uc774\ub2e4.<br>\ub610\ud55c,\u00a0M\uc774 \uacc4\uc0b0\uc801\uc73c\ub85c \ud6a8\uc728\uc801(computationally efficient)\uc774\ub77c\uba74,\u00a0\\(M^{\\prime}\\)\ub3c4 \uadf8\ub807\ub2e4.<br>\u00a0M \uc774 \ube44\uae08\uc804\uc801(moneyless)\uc774\ub77c\uba74,\u00a0\\(M^{\\prime}\\)\ub3c4 \ube44\uae08\uc804\uc801\uc774\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">PTE mechanism for all social welfare games with small type space.<\/h5>\n\n\n\n<p>VCG \uba54\ucee4\ub2c8\uc998\uc740 \ubaa8\ub4e0 \uc0ac\ud68c\uc801 \ubcf5\uc9c0 \uac8c\uc784\uc5d0\uc11c \uc9c4\uc2e4\uc131\uc744 \ub9cc\uc871\ud558\uba70 \uc644\uc804\ud788 \ud6a8\uc728\uc801\uc778(perfectly efficient) \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uacf5\ud55c\ub2e4.<br>\uc989, \uac1c\ubcc4 \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud569\uc744 \ucd5c\uc801\ud654\ud558\ub294 \uac8c\uc784\uc5d0\uc11c \uc0ac\uc6a9\ub420 \uc218 \uc788\ub2e4. \ub530\ub77c\uc11c, \uc800\uc790\uc758 \uc8fc\uc694 \uc815\ub9ac\ub294 \ub2e4\uc74c\uc744 \ud568\uc758\ud55c\ub2e4.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"239\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-3-1024x239.png\" alt=\"\" class=\"wp-image-4897\" srcset=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-3-1024x239.png 1024w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-3-300x70.png 300w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-3-768x180.png 768w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/03\/image-3.png 1514w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\ucd94\ub860 2.4. \\(\\epsilon, \\eta > 0\\)\ub97c \uace0\uc815\ud558\uc790. \u00a0n \uba85\uc758 \ud50c\ub808\uc774\uc5b4\ub97c \uac00\uc9c0\uba70, \uc720\ud615 \uacf5\uac04\uc758 \ud06c\uae30\uac00\u00a0 q \uc774\uace0, \ubaa9\ud45c\uac00 \uc0ac\ud68c\uc801 \ubcf5\uc9c0\ub97c \ucd5c\uc801\ud654\ud558\ub294 \uac8c\uc784\u00a0 G \uc5d0 \ub300\ud574, \ub2e4\uc74c \uc870\uac74\uc744 \ub9cc\uc871\ud558\ub294 \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc874\uc7ac\ud55c\ub2e4.<br>\\((\\epsilon, \\eta)\\)-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud55c\ub2e4.<br>\\(O(q \\log(q\/\\eta) \/ \\epsilon)\\)-\uadfc\uc0ac\uc801\uc73c\ub85c \ud6a8\uc728\uc801\uc774\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">2.3. The value of privacy<\/h4>\n\n\n\n<p>\uc774\uc804 \uc5f0\uad6c\ub294 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc640 \uc720\uc6a9\uc131(utility)\uc744 \ub3c5\ub9bd\uc801\uc778 \uc694\uc18c\ub85c \ucde8\uae09\ud574\uc654\ub2e4.<br>\uc608\ub97c \ub4e4\uc5b4, \uc55e\uc5d0\uc11c \uc800\uc790\ub294 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\uba74\uc11c\ub3c4 \uc9c4\uc2e4\uc131\uc744 \uc720\uc9c0\ud558\ub294 \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc774 \uac00\ub2a5\ud568\uc744 \ubcf4\uc600\ub2e4.<br>\uadf8\ub7ec\ub098 \ucc38\uc5ec\uc790\uac00 \uc2e4\uc81c\ub85c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uac00\uce58 \uc788\uac8c \uc5ec\uae34\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4\uba74, \uc774\ub7ec\ud55c \uace0\ub824\uac00 \uac1c\uc778\uc758 \ud6a8\uc6a9 \ud568\uc218(utility function)\uc5d0 \uba85\uc2dc\uc801\uc73c\ub85c \ubc18\uc601\ub418\uc5b4\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc774\ub7ec\ud55c \uc811\uadfc \ubc29\uc2dd\uc740 \ub450 \uac00\uc9c0 \uc7a5\uc810\uc744 \uc81c\uacf5\ud55c\ub2e4.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uc5d0 \ub300\ud55c \ucc38\uc5ec\uc790\uc758 \uac00\uce58 \ud3c9\uac00\ub97c \uc815\ub7c9\ud654\ud560 \uc218 \uc788\ub2e4.<\/li>\n\n\n\n<li>\uc720\uc6a9\uc131\uacfc \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uac04\uc758 \uc0c1\ucda9 \uad00\uacc4(trade-off)\ub97c \ubaa8\ub378\ub9c1\ud560 \uc218 \uc788\ub2e4.<\/li>\n<\/ol>\n\n\n\n<p>\uc989, \ucc38\uc5ec\uc790\ub294 \uc790\uc2e0\uc758 \uc720\ud615\uc744 \uac70\uc9d3\uc73c\ub85c \ubcf4\uace0\ud568\uc73c\ub85c\uc368 \uc77c\ubd80 \uc720\uc6a9\uc131\uc744 \ud3ec\uae30\ud558\uace0 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uac15\ud654\ud560 \uc218\ub3c4 \uc788\ub2e4.<br>\ubc18\ub300\ub85c, \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \uc77c\ubd80 \ud76c\uc0dd\ud558\uba74 \uac8c\uc784\uc758 \uacb0\uacfc\uc5d0\uc11c \ub354 \ud070 \uc720\uc6a9\uc131\uc744 \uc5bb\uc744 \uc218 \uc788\uae30 \ub54c\ubb38\uc5d0 \uadf8\ub807\uac8c \uc120\ud0dd\ud560 \uc218\ub3c4 \uc788\ub2e4.<br>\uc800\uc790\ub294 PTE \uba54\ucee4\ub2c8\uc998\uc870\ucc28\ub3c4 \uc9c4\uc2e4\uc131\uc744 \uc720\uc9c0\ud558\uae30 \uc704\ud574 \ub108\ubb34 \ub9ce\uc740 \uc815\ubcf4\ub97c \uc720\ucd9c\ud560 \uac00\ub2a5\uc131\uc774 \uc788\uc74c\uc744 \ubcf4\uc77c \uac83\uc774\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">2.3.1. Quantifying privacy<\/h5>\n\n\n\n<p>\uccab \ubc88\uc9f8 \uacfc\uc81c\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \uc5bc\ub9c8\ub098 \ub9ce\uc740 \uc815\ubcf4\ub97c \uc720\ucd9c\ud558\ub294\uc9c0 \uce21\uc815\ud558\ub294 \ubc29\ubc95\uc744 \uc815\uc758\ud558\ub294 \uac83\uc774\ub2e4.<br>\uc790\uc5f0\uc2a4\ub7ec\uc6b4 \uc870\uac74 \uc911 \ud558\ub098\ub294, \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \uc2e4\uc81c \uc720\ud615\uacfc \ub3c5\ub9bd\uc801\uc778 \uc720\ud615\uc744 \ubcf4\uace0\ud560 \uacbd\uc6b0, \uc815\ubcf4 \ube44\uc6a9(information cost)\uc774 0\uc774 \ub418\uc5b4\uc57c \ud55c\ub2e4\ub294 \uac83\uc774\ub2e4.<br>\uc774\uc720\ub294, \ucd9c\ub825\ub41c \uba54\ucee4\ub2c8\uc998 \uacb0\uacfc\uac00 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uc5d0 \ub300\ud55c \uc815\ubcf4\ub97c \ud3ec\ud568\ud558\uc9c0 \uc54a\uc73c\uba74, \uadf8\uc758 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uac00 \uce68\ud574\ub418\uc9c0 \uc54a\uae30 \ub54c\ubb38\uc774\ub2e4.<br>\uc774 \uae30\uc900\uc744 \ub9cc\uc871\ud558\ub824\uba74, \uc815\ubcf4 \ube44\uc6a9\uc740 \ub2e8\uc21c\ud788 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uacfc \uac8c\uc784\uc758 \uacb0\uacfc\ub9cc\uc744 \uae30\ubc18\uc73c\ub85c \uc815\uc758\ub420 \uc218 \uc5c6\ub2e4.<br>\uc65c\ub0d0\ud558\uba74, \u201c\uc815\uc9c1\ud55c \uc720\ud615\uacfc \ub3c5\ub9bd\uc801\u201d\uc774\ub77c\ub294 \uac1c\ub150\uc740 \ud2b9\uc815 \uc720\ud615\uc5d0\uc11c\uc758 \ud589\ub3d9\uc774 \uc544\ub2c8\ub77c, \ubaa8\ub4e0 \uac00\ub2a5\ud55c \uc720\ud615\uc5d0 \ub300\ud55c \ud50c\ub808\uc774\uc5b4\uc758 \ud589\ub3d9\uc744 \uae30\ubc18\uc73c\ub85c \uc815\uc758\ub418\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc0ac\uace0 \uc2e4\ud5d8(thought experiment)\uc73c\ub85c, \uc5b4\ub5a4 \uc720\ud615\u00a0 t \uac00 \uace0\uc815\ub418\uc5b4 \uc788\ub2e4\uace0 \uac00\uc815\ud558\uace0, \ub2e4\uc74c \ub450 \uac00\uc9c0 \uc804\ub7b5\uc744 \uace0\ub824\ud558\uc790.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\uc9c4\uc2e4\ud55c \uc804\ub7b5(truthful strategy): \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \uc2e4\uc81c \uc720\ud615\uc744 \ubcf4\uace0\ud558\ub294 \uacbd\uc6b0.<\/li>\n\n\n\n<li>\uc0c1\uc218\u00a0 t\u00a0 \uc804\ub7b5(constant\u00a0 t\u00a0 strategy): \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \uc2e4\uc81c \uc720\ud615\uacfc \uad00\uacc4\uc5c6\uc774 \ud56d\uc0c1\u00a0 t \ub97c \ubcf4\uace0\ud558\ub294 \uacbd\uc6b0.<\/li>\n<\/ol>\n\n\n\n<p>\ub9cc\uc57d \ud50c\ub808\uc774\uc5b4\uc758 \uc2e4\uc81c \uc720\ud615\uc774\u00a0 t \uc778 \uacbd\uc6b0, \ub450 \uc804\ub7b5\uc740 \ub3d9\uc77c\ud55c \ucd9c\ub825\uc744 \uc0dd\uc131\ud558\uc9c0\ub9cc, \uc9c1\uad00\uc801\uc73c\ub85c \uc9c4\uc2e4\ud55c \uc804\ub7b5\uc740 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uc5d0 \ub300\ud55c \uc815\ubcf4\ub97c \ub178\ucd9c\ud560 \uac00\ub2a5\uc131\uc774 \uc788\ub294 \ubc18\uba74, \uc0c1\uc218\u00a0 t\u00a0 \uc804\ub7b5\uc740 \uadf8\ub807\uc9c0 \uc54a\ub2e4.<\/p>\n\n\n\n<p>\ub530\ub77c\uc11c, \uc815\ubcf4 \ube44\uc6a9\uc744 \uc804\ud1b5\uc801\uc778 \ud6a8\uc6a9 \ud568\uc218\uc758 \ubcc0\ud615 \ud615\ud0dc\ub85c \ud45c\ud604\ud560 \uc218 \uc5c6\ub2e4.<br>\uc989, \uc815\ubcf4 \ube44\uc6a9\uc740 \ub2e8\uc21c\ud788 \ud50c\ub808\uc774\uc5b4\uc758 \uc720\ud615\uacfc \uac8c\uc784\uc758 \uacb0\uacfc\ub9cc\uc73c\ub85c \uacb0\uc815\ub418\ub294 \uac83\uc774 \uc544\ub2c8\ub77c, \ubaa8\ub4e0 \uac00\ub2a5\ud55c \uc720\ud615\uc5d0 \ub300\ud55c \ud50c\ub808\uc774\uc5b4\uc758 \uc804\ub7b5\uc744 \uae30\ubc18\uc73c\ub85c \ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc800\uc790\ub294\u00a0\\(ICM(\\sigma, t, i)\\)\ub97c \uc815\uc758\ud558\ub294\ub370, \uc774\ub294 \uba54\ucee4\ub2c8\uc998\u00a0 M \uc774 \uc8fc\uc5b4\uc9c4 \uc0c1\ud0dc\uc5d0\uc11c, \ud50c\ub808\uc774\uc5b4\u00a0 i \uac00 \uc804\ub7b5\u00a0\\(\\sigma\\)\ub97c \uc0ac\uc6a9\ud588\uc744 \ub54c \ubc1c\uc0dd\ud558\ub294 \uc815\ubcf4 \ube44\uc6a9\uc744 \uc758\ubbf8\ud55c\ub2e4.<br>\uc804\ub7b5\u00a0\\(\\sigma\\)\ub294 \uc720\ud615\uc5d0\uc11c \uc720\ud615 \ubd84\ud3ec\ub85c\uc758 \ud568\uc218\ub85c \uc815\uc758\ub418\uba70, \uc989, \ud50c\ub808\uc774\uc5b4\u00a0 i \uc758 \uc2e4\uc81c \uc720\ud615\uc774\u00a0 t \uc77c \ub54c, \uadf8\uac00 \uc804\ub7b5\u00a0\\(\\sigma\\)\ub97c \uc0ac\uc6a9\ud558\uba74, \uc77c\uc815\ud55c \ud655\ub960\uc5d0 \ub530\ub77c\u00a0\\(t{\\prime} \\sim \\sigma(t)\\)\ub97c \uc0d8\ud50c\ub9c1\ud558\uace0, \uc774\ub97c \uba54\ucee4\ub2c8\uc998\uc5d0 \ubcf4\uace0\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc77c\ubc18\uc801\uc73c\ub85c \uc815\ubcf4 \ube44\uc6a9\uc740 \ud2b9\uc815\ud55c \uc751\uc6a9(application)\uc5d0 \ub530\ub77c \ub2ec\ub77c\uc9c8 \uc218 \uc788\ub2e4.<br>\ub530\ub77c\uc11c \uc800\uc790\ub294 \ud2b9\uc815\ud55c \uc815\ubcf4 \ube44\uc6a9 \ud568\uc218\ub97c \uace0\uc815\ud558\uc9c0 \uc54a\uace0, \ub2e4\uc74c\uacfc \uac19\uc740 \uac00\uc815\uc744 \ub9cc\uc871\ud558\ub294 \uc5b4\ub5a0\ud55c \uc815\ubcf4 \ube44\uc6a9 \ud568\uc218\uc5d0 \ub300\ud574\uc11c\ub3c4 \uacb0\uacfc\uac00 \uc131\ub9bd\ud568\uc744 \ubcf4\uc77c \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p>\ud50c\ub808\uc774\uc5b4\ub294 \uc790\uc2e0\uc758 \ub370\uc774\ud130\ub97c \uc228\uae38 \uc218 \uc788\uc5b4\uc57c \ud55c\ub2e4: <br>\uc5b4\ub5a4 \uc804\ub7b5 \\(\\sigma\\)\uac00 \uc785\ub825\uacfc \ub3c5\ub9bd\uc801\uc778 \uacbd\uc6b0(\uc989, \ubaa8\ub4e0\u00a0\\(t, t{\\prime}\\)\uc5d0 \ub300\ud574\u00a0\\(\\sigma(t) = \\sigma(t{\\prime}\\)) \ub97c \ub9cc\uc871\ud558\ub294 \uacbd\uc6b0),<br>\ubaa8\ub4e0\u00a0 i, t \uc5d0 \ub300\ud574 \uc815\ubcf4 \ube44\uc6a9\u00a0\\(ICM(\\sigma,t,i)\\)\ub294 0\uc774 \ub418\uc5b4\uc57c \ud55c\ub2e4.<br>\uc989, \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \uc2e4\uc81c \uc720\ud615\uacfc \ubb34\uad00\ud558\uac8c \ub3d9\uc77c\ud55c \uc720\ud615\uc744 \ubcf4\uace0\ud558\ub294 \uc804\ub7b5\uc744 \uc0ac\uc6a9\ud560 \uacbd\uc6b0, \uadf8\uc758 \uc720\ud615\uc774 \uc815\ubcf4 \ube44\uc6a9\uc5d0 \uc601\ud5a5\uc744 \ubbf8\uccd0\uc11c\ub294 \uc548 \ub41c\ub2e4.<\/p>\n\n\n\n<p>\uc815\ubcf4 \ube44\uc6a9\uc740 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ubc18\uc601\ud574\uc57c \ud55c\ub2e4:<br>\ub300\ub7b5\uc801\uc73c\ub85c, \ub9cc\uc57d \uba54\ucee4\ub2c8\uc998\u00a0 M \uc774\u00a0\\(\\epsilon\\)-\ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ub9cc\uc871\ud558\ub294 \ucd5c\uc18c\ud55c\uc758 \uac12\u00a0\\(\\epsilon\\)\uc774 \uc874\uc7ac\ud55c\ub2e4\uace0 \ud558\uba74,<br>\uc815\ubcf4 \ube44\uc6a9\uc740\u00a0\\(\\epsilon\\)\ubcf4\ub2e4 \ud06c\uac8c \uac10\uc18c\ud560 \uc218 \uc5c6\uc5b4\uc57c \ud55c\ub2e4.<br>\uc989, \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc218\uc900 \\(\\epsilon\\)\uc774 \ub192\uc744\uc218\ub85d, \uc815\ubcf4 \ube44\uc6a9\ub3c4 \uc77c\uc815 \uc218\uc900 \uc774\uc0c1\uc774\uc5b4\uc57c \ud55c\ub2e4\ub294 \uac83\uc744 \uc758\ubbf8\ud55c\ub2e4. \uc774 \uc870\uac74\uc740 \ucc28\ub4f1 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\uac00 \uc815\ubcf4 \uc720\ucd9c\uc744 \uc5bc\ub9c8\ub098 \uc81c\ud55c\ud558\ub294\uc9c0\ub97c \ubc18\uc601\ud558\ub294 \uc5ed\ud560\uc744 \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>Xiao, David. &#8220;Is privacy compatible with truthfulness?.&#8221; Proceedings of the 4th conference on Innovations in Theoretical Computer Science. 2013.<\/p>\n\n\n\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>In the area of privacy-preserving data mining, a di\ufb00erentially private mechanism intuitively encourages people to share their data because they are at little risk of revealing their own information.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[108],"tags":[155,4,203,201],"class_list":["post-4827","post","type-post","status-publish","format-standard","hentry","category-paper-review","tag-differential-privacy","tag-game-theory","tag-mar-3-2025","tag-truthfulness"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4827"}],"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=4827"}],"version-history":[{"count":86,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4827\/revisions"}],"predecessor-version":[{"id":5210,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4827\/revisions\/5210"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=4827"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=4827"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=4827"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}