{"id":4710,"date":"2025-02-15T06:03:59","date_gmt":"2025-02-14T21:03:59","guid":{"rendered":"https:\/\/saraheee.com\/?p=4710"},"modified":"2025-03-21T23:20:30","modified_gmt":"2025-03-21T14:20:30","slug":"review15-mechanism-design-via-differential-privacy","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2025\/02\/review15-mechanism-design-via-differential-privacy\/","title":{"rendered":"[review#15] Mechanism Design via Differential Privacy_McSherry and Kunal,\u00a02007"},"content":{"rendered":"<h4 class=\"wp-block-heading\">Structured summary<\/h4>\n\n\n\n<p>This paper explores the role of privacy-preserving algorithms in mechanism design, specifically using differential privacy to ensure that participants have limited effect on the outcome of the mechanism and limited incentive to lie.<br>\uc774 \ub17c\ubb38\uc740 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uc54c\uace0\ub9ac\uc998\uc758 \uc5ed\ud560\uc744 \ud0d0\uad6c\ud558\uba70, \ud2b9\ud788 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ud65c\uc6a9\ud558\uc5ec \ucc38\uac00\uc790\uac00 \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \uc81c\ud55c\ud558\uace0 \uac70\uc9d3\ub9d0\uc744 \ud560 \uc720\uc778\uc744 \uc904\uc774\ub294 \ubc29\ubc95\uc744 \uc5f0\uad6c\ud55c\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Abstract<\/h2>\n\n\n\n<p>\ucc38\uc5ec\uc790\uc5d0 \ub300\ud55c \ud2b9\uc815 \uc815\ubcf4\uc758 \uc720\ucd9c\uc744 \ubc29\uc9c0\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uc54c\uace0\ub9ac\uc998(privacy-preserving algorithms)\uc774 \uc804\ub7b5\uc801(agent-based) \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0\uc11c \uc5b4\ub5a4 \uc5ed\ud560\uc744 \ud560 \uc218 \uc788\ub294\uc9c0 \uc5f0\uad6c\ud55c\ub2e4.<br>\uc804\ub7b5\uc801 \uba54\ucee4\ub2c8\uc998\uc5d0\uc11c\ub294 \ucc38\uc5ec\uc790\ub4e4\uc774 \uc815\ubcf4\ub97c \uc815\uc9c1\ud558\uac8c \ubcf4\uace0\ud558\ub3c4\ub85d \uc720\ub3c4\ud558\ub294 \uac83\uc774 \ud544\uc218\uc801\uc774\ub2e4.<\/p>\n\n\n\n<p>\uad6c\uccb4\uc801\uc73c\ub85c, \uc6b0\ub9ac\ub294 \ucd5c\uadfc \ub3c4\uc785\ub41c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(differential privacy) \uac1c\ub150\uc774, \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638\ub77c\ub294 \uc7a5\uc810 \uc678\uc5d0\ub3c4 \ucc38\uc5ec\uc790\uac00 \uba54\ucee4\ub2c8\uc998 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \uc81c\ud55c\ud558\uace0, \uacb0\uacfc\uc801\uc73c\ub85c \uac70\uc9d3 \ubcf4\uace0(incentive to lie)\ub97c \uc904\uc774\ub294 \uc5ed\ud560\uc744 \ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<p>\ub354 \uc815\ud655\ud558\uac8c \ub9d0\ud558\uba74, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc740 \uc784\uc758\uc758 \ud50c\ub808\uc774\uc5b4 \ud6a8\uc6a9 \ud568\uc218(utility function) \ud558\uc5d0\uc11c\ub3c4 \uadfc\uc0ac\uc801 \uc6b0\uc6d4\uc804\ub7b5(approximate dominant strategy)\uc744 \ud615\uc131\ud558\uba70,<br>\uc790\ub3d9\uc801\uc73c\ub85c \uc5f0\ud569(coalition)\uc5d0 \ub300\ud55c \ub0b4\uc131\uc744 \uac00\uc9c0\uba70, \ubc18\ubcf5 \uc2dc\ud589\uc774 \uc6a9\uc774\ud558\ub2e4.<\/p>\n\n\n\n<p>\ubb34\uc81c\ud55c \uacf5\uae09 \uacbd\ub9e4(unlimited supply auction) \ubb38\uc81c\uc758 \uc5ec\ub7ec \ud2b9\uc218 \uc0ac\ub840\ub97c \uc5f0\uad6c\ud558\uba70, \ub2e4\uc74c\uacfc \uac19\uc740 \uc0c8\ub85c\uc6b4 \uacb0\uacfc\ub97c \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\ub514\uc9c0\ud138 \uc0c1\ud488 \uacbd\ub9e4<\/li>\n\n\n\n<li>\uc18d\uc131 \uae30\ubc18 \uacbd\ub9e4<\/li>\n\n\n\n<li>\uac00\uaca9 \uad6c\uc870\uc5d0 \uc784\uc758\uc758 \uc81c\uc57d\uc774 \uc874\uc7ac\ud558\ub294 \uacbd\ub9e4<\/li>\n<\/ul>\n\n\n\n<p>\ud2b9\ud788, \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uacbd\ub9e4 \uba54\ucee4\ub2c8\uc998\uc744 \uac1c\ubc1c\ud558\ub294 \uc911\uc694\ud55c \uc804\uc81c \uc870\uac74\uc73c\ub85c, \uae30\uc874\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uc5f0\uad6c\ub97c \ud655\uc7a5\ud558\uc5ec \uacbd\ub9e4 \ud658\uacbd\uc758 \ub192\uc740 \ubbfc\uac10\ub3c4(high sensitivity)\ub97c \uc218\uc6a9\ud558\ub294 \uc77c\ubc18\ud654\ub41c \ubaa8\ub378\uc744 \uc18c\uac1c\ud558\uace0 \uc5f0\uad6c\ud55c\ub2e4.<br>\uc774\ub7ec\ud55c \ud658\uacbd\uc5d0\uc11c\ub294,<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\ub2e8\uc77c \ucc38\uac00\uc790\uac00 \ucd5c\uc801 \uace0\uc815 \uac00\uaca9(optimal fixed price)\uc744 \uadf9\uc801\uc73c\ub85c \ubcc0\ud654\uc2dc\ud0ac \uac00\ub2a5\uc131\uc774 \uc874\uc7ac\ud558\uba70, <\/li>\n\n\n\n<li>\uc81c\uacf5\ub418\ub294 \uac00\uaca9\uc774 \uc57d\uac04\ub9cc \ubcc0\uacbd\ub418\uc5b4\ub3c4 \uc218\uc775\uc774 \ucd5c\uc801\uc5d0\uc11c 0\uc73c\ub85c \uae09\ub77d\ud560 \uc218 \uc788\ub2e4.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">1. Introduction<\/h2>\n\n\n\n<p>\ubbfc\uac10\ud55c \ub370\uc774\ud130\ub97c \ubd84\uc11d\ud558\uba74\uc11c \ub3d9\uc2dc\uc5d0 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc720\uc9c0\ud558\ub824\ub294 \ubb38\uc81c\ub294 \uc624\ub798\uc804\ubd80\ud130 \uc5f0\uad6c\ub418\uc5b4 \uc654\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \uc778\uad6c\uc870\uc0ac\uad6d(Census Bureau)\uc5d0\uc11c \uc9c1\uba74\ud55c \ubb38\uc81c\ub4e4\uc740, &#8220;\uc815\ubcf4 \uacf5\uac1c \uc81c\ud55c \uba54\ucee4\ub2c8\uc998(disclosure limitation mechanisms)&#8221; \uc5f0\uad6c\uc758 \ubc1c\uc804\uc744 \uc774\ub04c\uc5c8\ub2e4. \uc774\ub7ec\ud55c \uba54\ucee4\ub2c8\uc998\uc740 \ub370\uc774\ud130 \uc138\ud2b8\uc5d0\uc11c \uc720\ucd9c\ub418\ub294 \ud2b9\uc815 \uc815\ubcf4\uc758 \uc591\uc774\ub098 \uc131\uaca9\uc744 \uc81c\ud55c\ud558\ub294 \uac83\uc744 \ubaa9\ud45c\ub85c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc774\ub7ec\ud55c \uacfc\uc815\uc5d0\uc11c &#8216;\ubbfc\uac10\ud55c \uc785\ub825 \ub370\uc774\ud130\uac00 \ubb34\uc791\uc704\ud654(randomized), \uc9d1\uacc4(aggregated), \uc775\uba85\ud654(anonymized)&#8217; \ub4f1\uc758 \uae30\ubc95\uc744 \ud1b5\ud574 \ubcc0\ud615\ub418\uc5c8\uace0, \uc6d0\ub798 \ub370\uc774\ud130\uc758 \uad6c\uccb4\uc801\uc778 \uc758\ubbf8\ub97c \uc81c\uac70\ud558\uace0 \uc720\ucd9c\uc744 \ubc29\uc9c0\ud558\ub294 \ubc29\uc2dd\uc774 \uc0ac\uc6a9\ub418\uc5c8\ub2e4.<\/p>\n\n\n\n<p>\ub300\ubd80\ubd84\uc758(\ubaa8\ub4e0 \uac83\uc740 \uc544\ub2c8\uc9c0\ub9cc) \uc815\ubcf4 \uacf5\uac1c \uc81c\ud55c \uba54\ucee4\ub2c8\uc998\uc5d0\uc11c\ub294 \uc5b4\ub5a4 \uc815\ubcf4 \uacf5\uac1c\uac00 \u201c\ud5c8\uc6a9\ub418\uc9c0 \uc54a\ub294(unacceptable)\u201d \uac83\uc778\uc9c0 \uc815\ud655\ud788 \uc815\uc758\ud558\ub294 \uac83\uc774 \ud575\uc2ec \uc694\uc18c\uc774\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc77c\ubc18\uc801\uc73c\ub85c, \uac1c\ubcc4 \ucc38\uac00\uc790\uc5d0 \ub300\ud55c \ud2b9\uc815 \uc815\ubcf4 \uacf5\uac1c\ub294 \ud5c8\uc6a9\ub418\uc9c0 \uc54a\ub294\ub2e4.<\/li>\n\n\n\n<li>\ubc18\uba74, \uc9d1\ub2e8\uc5d0 \ub300\ud55c \ube44\ud2b9\uc815\uc801\uc774\uace0 \uc77c\ubc18\uc801\uc778 \uc815\ubcf4\ub294 \ud5c8\uc6a9\ub418\uac70\ub098 \uc624\ud788\ub824 \ubc14\ub78c\uc9c1\ud560 \uc218 \uc788\ub2e4.<\/li>\n\n\n\n<li>\ub530\ub77c\uc11c, \uac01 \uae30\ubc95\uc774 \uc81c\uacf5\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uc218\uc900\uc740 \ub2e4\ub97c \uc218 \uc788\uc73c\uba70, \ub300\ubd80\ubd84\uc758 \uc5f0\uad6c\ub294 \ud2b9\uc815\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubaa9\ud45c\ub97c \uc124\uc815\ud558\ub294 \ub300\uc2e0, \ud2b9\uc815 \uba54\ucee4\ub2c8\uc998\uc774 \ubc29\uc9c0\ud558\ub294 \uc815\ubcf4 \uacf5\uac1c\ub97c \ud1b5\ud574 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ud615\uc2dd\uc801\uc73c\ub85c \uc815\uc758\ud558\ub294 \uacbd\ud5a5\uc774 \uc788\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p>\ucd5c\uadfc \uc5f0\uad6c [15, 14]\ub294 \uc815\ubcf4 \uacf5\uac1c\ub97c \ud615\uc2dd\uc801\uc73c\ub85c \uc815\uc758\ud558\ub294 \uc5b4\ub824\uc6c0\uc744 \ud68c\ud53c\ud558\uae30 \uc704\ud574 \u201c\ud655\ub960 \ubcc0\ud654(relative change in probability)\u201c\uc5d0 \ub300\ud55c \uc0c1\ub300\uc801 \uc81c\ud55c\uc744 \ubd80\uacfc\ud558\ub294 \uc815\uc758\ub97c \ub3c4\uc785\ud588\ub2e4.<br>\uc774 \uc811\uadfc\ubc95\uc5d0\uc11c\ub294 \uc5b4\ub5a4 \uc0ac\uac74(event)\uc774 \ubc1c\uc0dd\ud560 \ud655\ub960 \uc790\uccb4\ub97c \uc9c1\uc811 \uc81c\ud55c\ud558\ub294 \uac83\uc774 \uc544\ub2c8\ub77c, \uac1c\ubcc4 \uc0ac\uc6a9\uc790\uc758 \ub370\uc774\ud130 \ubcc0\uacbd\uc73c\ub85c \uc778\ud574 \uc0ac\uac74\uc758 \ud655\ub960\uc774 \ubcc0\ud558\ub294 \uc815\ub3c4\ub97c \uc0c1\ub300\uc801\uc73c\ub85c \uc81c\ud55c\ud55c\ub2e4.<\/p>\n\n\n\n<p>Definition 1 (Differential Privacy)<br>\uc784\uc758\uc131\uc744 \uac16\ub294 \ud568\uc218 M \uc774 \\(\\epsilon\\)-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud558\ub824\uba74,<br>\ubaa8\ub4e0 \ub2e8\uc77c \uc0ac\uc6a9\uc790\ub9cc \ub2e4\ub974\uac8c \ud3ec\ud568\ud558\ub294 \ub370\uc774\ud130\uc14b \\(D_1\\) \ubc0f \\(D_2\\), \uadf8\ub9ac\uace0 M \uc758 \ucd9c\ub825 \ubc94\uc704 \\(Range(M)\\) \uc758 \ubaa8\ub4e0 \ubd80\ubd84\uc9d1\ud569 S \uc5d0 \ub300\ud574 \ub2e4\uc74c\uc774 \uc131\ub9bd\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\\(Pr[M(D_1) \\in S] \\leq \\exp(\\epsilon) \\times Pr[M(D_2) \\in S]\\)<\/p>\n\n\n\n<p>\uc774 \uc815\uc758\uc758 \uc790\uc5f0\uc2a4\ub7ec\uc6b4 \uacb0\uacfc\ub294 \ub2e4\uc74c\uacfc \uac19\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\ud2b9\uc815 \uc0ac\uac74(event) S (\uc608: \uc6d0\uce58 \uc54a\ub294 \uac1c\uc778\uc815\ubcf4 \uc720\ucd9c)\uc774 \uc5b4\ub5a4 \uc0ac\uc6a9\uc790\uc758 \ucc38\uc5ec \uc5ec\ubd80\uc5d0 \ub530\ub77c \ud655\ub960\uc801\uc73c\ub85c \ud06c\uac8c \ubcc0\ud558\uc9c0 \uc54a\ub294\ub2e4.<\/li>\n\n\n\n<li>\ud2b9\uc815 \uc0ac\uc6a9\uc790\uc758 \ub370\uc774\ud130 \uc5c6\uc774 \ubc1c\uc0dd \uac00\ub2a5\uc131\uc774 \ub0ae\uac70\ub098 \ubd88\uac00\ub2a5\ud55c \uc0ac\uac74\uc740, \ud574\ub2f9 \ub370\uc774\ud130\ub97c \ucd94\uac00\ud558\ub354\ub77c\ub3c4 \uc5ec\uc804\ud788 \ubc1c\uc0dd \uac00\ub2a5\uc131\uc774 \ub0ae\uac70\ub098 \ubd88\uac00\ub2a5\ud558\ub2e4.<\/li>\n\n\n\n<li>\uc989, \ub2e8\uc77c \uc0ac\uc6a9\uc790\uc758 \ucc38\uc5ec\uac00 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \uc81c\ud55c\ud558\ub294 \uac83\uc774 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc758 \ud575\uc2ec\uc774\ub2e4.<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\uba54\ucee4\ub2c8\uc998 \uc124\uacc4(Mechanism Design)\uc640 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc758 \uad00\uacc4<\/h5>\n\n\n\n<p>\uba54\ucee4\ub2c8\uc998 \uc124\uacc4(Mechanism Design)\ub294 \uc774\uae30\uc801\uc778(agent-based) \ud50c\ub808\uc774\uc5b4\ub4e4\uc774 \uc785\ub825\uc744 \uc804\ub7b5\uc801\uc73c\ub85c \uc870\uc791\ud558\ub294 \uc0c1\ud669\uc5d0\uc11c\ub3c4 \uacac\uace0\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \uc124\uacc4\ud558\uace0 \ubd84\uc11d\ud558\ub294 \ubd84\uc57c\uc774\ub2e4.<br>\uc774\ub97c \ud504\ub77c\uc774\ubc84\uc2dc \ubb38\uc81c\uc640 \uc5f0\uad00 \uc9c0\uc5b4 \uc0dd\uac01\ud558\uba74, \ucc38\uc5ec\uc790\ub4e4\uc774 \uc790\uc2e0\uc758 \uc785\ub825\uac12\uc774 \uacb0\uacfc\uc5d0 \ud070 \uc601\ud5a5\uc744 \ubbf8\uce60 \uac83\uc744 \uc6b0\ub824\ud558\uc5ec, \uc804\ub7b5\uc801\uc73c\ub85c \ud589\ub3d9\ud560 \uc218 \uc788\ub294 \uc0c1\ud669\uc744 \uace0\ub824\ud560 \uc218 \uc788\ub2e4.<br>\uc989, \ud504\ub77c\uc774\ubc84\uc2dc \ubb38\uc81c \uc790\uccb4\ub97c \uc804\ub7b5\uc801 \ud589\uc704(strategic play)\uc758 \ud55c \ud615\ud0dc\ub85c \ud574\uc11d\ud560 \uc218 \uc788\ub2e4.<br>\uc77c\ubc18\uc801\uc73c\ub85c \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc758 \uacb0\uacfc\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uc54c\uace0\ub9ac\uc998 \uac1c\ubc1c\uc5d0 \uc751\uc6a9\ub420 \uc218 \uc788\ub2e4.<br>\uadf8\ub7ec\ub098 \uc774 \uc5f0\uad6c\uc5d0\uc11c\ub294 \ubc18\ub300\ub85c, \uac15\ub825\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\uc7a5(\uc608: \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc)\uc774 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\ub97c \uac1c\uc120\ud558\uace0 \ud655\uc7a5\ud558\ub294 \ub370 \uae30\uc5ec\ud560 \uc218 \uc788\uc74c\uc744 \ud0d0\uad6c\ud55c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">1.1 Statement of Results and Comparison with Related Work<\/h3>\n\n\n\n<p>\ub17c\ubb38\uc758 \uae30\uc5ec\ub294 \uc138 \uac00\uc9c0 \ubd80\ubd84\uc73c\ub85c \ub098\ub25c\ub2e4.<br>1. \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc758 \ud574\ubc95 \uac1c\ub150(solution concept)\uc73c\ub85c \ub3c4\uc785\ud55c\ub2e4.<br>2. \uae30\uc874 \uc5f0\uad6c\ubcf4\ub2e4 \ud6e8\uc52c \ub354 \ub2e4\uc591\ud55c \uc0c1\ud669\uc5d0 \uc801\uc6a9\ud560 \uc218 \uc788\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc2dc\ud568\uc73c\ub85c\uc368, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc758 \uc801\uc6a9 \uac00\ub2a5\uc131\uc744 \ud655\uc7a5\ud55c\ub2e4.<br>3. \ubb34\uc81c\ud55c \uacf5\uae09 \uacbd\ub9e4(unlimited supply auctions)\ub77c\ub294 \ud2b9\uc815 \uc0ac\ub840\ub97c \uc5f0\uad6c\ud558\uba70, \uc774 \ud574\ubc95 \uac1c\ub150\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud6c4\ud68c(regret) \uacbd\uacc4\ub97c \ud06c\uac8c \uac1c\uc120\ud55c\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Differential Privacy as a Solution Concept<\/h4>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0\uc11c \uac00\uc7a5 \uc77c\ubc18\uc801\uc778 \ud574\ubc95 \uac1c\ub150\uc740 &#8216;\uc9c4\uc2e4\uc131(truthfulness)&#8217;\uc77c \uac83\uc774\ub2e4. \uc989, \uba54\ucee4\ub2c8\uc998\uc774 \uac01 \uc0ac\uc6a9\uc790\uac00 \uc790\uc2e0\uc758 \uac00\uce58\ub97c \uc815\ud655\ud558\uac8c \ubcf4\uace0\ud558\ub294 \uac83\uc774 \uc6b0\uc6d4 \uc804\ub7b5(dominant strategy)\uc774 \ub418\ub3c4\ub85d \uc124\uacc4\ub418\ub294 \uacbd\uc6b0\ub97c \uc758\ubbf8\ud55c\ub2e4.<\/mark><\/p>\n\n\n\n<p>\uc9c4\uc2e4\ud55c(truthful) \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud558\uba74 \ubd84\uc11d\uc774 \ub2e8\uc21c\ud574\uc9c4\ub2e4.<br>\u2022 \uc0ac\uc6a9\uc790\uac00 \uae30\ub300 \ud6a8\uc6a9(expected utility)\uc744 \ub192\uc774\uae30 \uc704\ud574 \uc804\ub7b5\uc801\uc73c\ub85c \uac70\uc9d3 \ubcf4\uace0(gaming the system)\ub97c \uc2dc\ub3c4\ud560 \uac00\ub2a5\uc131\uc744 \uace0\ub824\ud560 \ud544\uc694\uac00 \uc5c6\uae30 \ub54c\ubb38\uc774\ub2e4.<br>\u2022 \ub530\ub77c\uc11c, \uc9c4\uc2e4\uc131\uc744 \ud574\ubc95 \uac1c\ub150\uc73c\ub85c \ucc44\ud0dd\ud558\ub294 \uac83\uc740 \ub9e4\uc6b0 \uc9c1\uad00\uc801\uc774\uace0 \ud3b8\ub9ac\ud55c \uc811\uadfc\ubc95\uc774\ub2e4.<\/p>\n\n\n\n<p>\uadf8\ub7ec\ub098, \uc77c\ubc18\uc801\uc778 \uc9c4\uc2e4\uc131 \uba54\ucee4\ub2c8\uc998\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uc81c\uc57d \uc870\uac74\ud558\uc5d0\uc11c\ub9cc \uc99d\uba85 \uac00\ub2a5\ud558\ub2e4.<\/p>\n\n\n\n<p>1. \ubcf5\uc218\uc758 \ud50c\ub808\uc774\uc5b4 \uac04 \ub2f4\ud569(collusion)\uc774 \uae08\uc9c0\ub41c \ud658\uacbd<br>2. \uc785\ucc30\uc790\uc758 \ud6a8\uc6a9 \ud568\uc218(utility function)\uac00 \ud2b9\uc815\ud55c \ub2e8\uc21c\ud55c \ubc94\uc704\ub85c \uc81c\ud55c\ub41c \uacbd\uc6b0<br>3. \uba54\ucee4\ub2c8\uc998\uc774 \ub2e8 \ud55c \ubc88 \uc2e4\ud589\ub418\uba70, \uc774\ud6c4 \ucd94\uac00\uc801\uc778 \ub300\uc751(recourse)\uc774 \uc81c\ud55c\ub41c \uacbd\uc6b0<br>4. \uc77c\ubd80 \uc0ac\uc6a9\uc790\uc5d0\uac8c \ud070 \uae08\uc561\uc744 \uc9c0\uae09\ud558\uac70\ub098, \uc77c\ubd80 \uc0ac\uc6a9\uc790\uc5d0\uac8c\ub9cc \ud2b9\uc815 \uac00\uaca9\uc73c\ub85c \uc0c1\ud488\uc744 \uc81c\uacf5\ud558\ub294 \uad6c\uc870\ub97c \ud3ec\ud568\ud560 \uac00\ub2a5\uc131<\/p>\n\n\n\n<p>\uc774\ub7ec\ud55c \uac15\ud55c \uac00\uc815(strong assumptions)\uc740 \uba54\ucee4\ub2c8\uc998\uc774 \ucda9\uc2e4\ud558\uac8c \uad6c\ud604\ub420 \uc218 \uc788\ub294 \ubc94\uc704\ub97c \uc81c\ud55c\ud558\uba70, \uc9c4\uc2e4\uc131\uc774 \uc8fc\ub294 \uc774\uc810\uc744 \uc628\uc804\ud788 \uc2e4\ud604\ud558\ub294 \ub370 \uc7a5\uc560\uac00 \ub420 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h6 class=\"wp-block-heading\">\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ud65c\uc6a9\ud55c \uc9c4\uc2e4\uc131\uc758 \uc644\ud654(Relaxation of Truthfulness)<\/h6>\n\n\n\n<p>\ub17c\ubb38\uc758 2\uc7a5\uc5d0\uc11c \uc0b4\ud3b4\ubcf4\uaca0\uc9c0\ub9cc, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub294 \uc9c4\uc2e4\uc131(truthfulness)\uc744 \uc644\ud654(relax)\ud558\ub294 \uc5ed\ud560\uc744 \ud55c\ub2e4.<br>\uc989, \ucc38\uc5ec\uc790\uac00 \uac70\uc9d3 \ubcf4\uace0\ub97c \ud560 \uc720\uc778\uc774 \uc644\uc804\ud788 0\uc774 \ub418\uc9c0\ub294 \uc54a\uc9c0\ub9cc, \ub9e4\uc6b0 \uc81c\ud55c\uc801\uc73c\ub85c \uc870\uc815\ub420 \uc218 \uc788\ub2e4.<br>\ub354\uc6b1 \uc911\uc694\ud55c \uc810\uc740, \uc774\ub7ec\ud55c \u201c\uadfc\uc0ac\uc801 \uc9c4\uc2e4\uc131(approximate truthfulness)\u201c\uc774 \ub2e4\uc74c\uacfc \uac19\uc740 \ucd94\uac00\uc801 \ubcf4\uc7a5\uc744 \uc81c\uacf5\ud55c\ub2e4\ub294 \uac83\uc774\ub2e4.<br>\ub2f4\ud569(collusion)\uc774 \uc874\uc7ac\ud558\ub294 \ud658\uacbd\uc5d0\uc11c\ub3c4 \uc989\uac01\uc801\uc778 \ubcf4\uc7a5(immediate guarantees)\uc744 \uc81c\uacf5\ud55c\ub2e4.<br>\uc784\uc758\uc758 \ud6a8\uc6a9 \ud568\uc218(arbitrary utility functions)\uc5d0\uc11c\ub3c4 \uc801\uc6a9 \uac00\ub2a5\ud558\ub2e4.<br>\uba54\ucee4\ub2c8\uc998\uc774 \ubc18\ubcf5 \uc2e4\ud589(repeated runs)\ub418\ub354\ub77c\ub3c4 \uc801\uc6a9 \uac00\ub2a5\ud558\ub2e4.<\/p>\n\n\n\n<p>\ucd5c\uadfc Chaudhuri et al. [12]\uc758 \uc5f0\uad6c\uc5d0 \ub530\ub974\uba74, <br>\uc774\ub7ec\ud55c \uba54\ucee4\ub2c8\uc998\uc740 \ub192\uc740 \ud655\ub960\ub85c(truthful with high probability) \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud560 \uc218 \uc788\ub3c4\ub85d \uad6c\ud604\ub420 \uc218 \uc788\ub2e4.<br>\ub610\ud55c, \uc5c4\uaca9\ud55c \uc9c4\uc2e4\uc131\uc744 \uc694\uad6c\ud558\ub294 \uae30\uc874 \ubc29\uc2dd\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc5c6\ub294 \ubb38\uc81c\ub4e4\uc744 \ub2e4\ub8f0 \uc218 \uc788\ub294 \uac00\ub2a5\uc131\uc744 \uc5f0\ub2e4.<br>\ub300\ud45c\uc801\uc778 \uc608\uc2dc\ub85c, \ubb34\uc81c\ud55c \uacf5\uae09 \uac00\uaca9 \ucc45\uc815 \ubb38\uc81c(unlimited supply pricing problem)\uac00 \uc788\ub2e4.<br>\uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \ubb34\uc81c\ud55c\uc73c\ub85c \uc81c\uacf5\ub418\ub294 \uc0c1\ud488\uc744 \ub2e8\uc77c \uac00\uaca9(single price)\uc73c\ub85c \ubaa8\ub4e0 \uad6c\ub9e4\uc790\uc5d0\uac8c \uc81c\uacf5\ud574\uc57c \ud558\ub294 \uc0c1\ud669\uc774 \ubc1c\uc0dd\ud55c\ub2e4.<br>\uae30\uc874\uc758 \uc5c4\uaca9\ud55c \uc9c4\uc2e4\uc131 \uae30\ubc18 \uba54\ucee4\ub2c8\uc998\uc73c\ub85c\ub294 \ud574\uacb0\uc774 \uc5b4\ub824\uc6b4 \ubb38\uc81c\uc9c0\ub9cc, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ud65c\uc6a9\ud558\uba74 \ud574\uacb0\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">A General Differential Privacy Framework<\/h4>\n\n\n\n<p>\uae30\uc874\uc758 DP \uc811\uadfc\ubc95\ub4e4\uc740 \uc2e4\uc218 \uac12(real-valued)\uc744 \uac16\ub294 \ud568\uc218\uc5d0 \ucd08\uc810\uc744 \ub9de\ucd94\uc5c8\ub2e4.<br>\uc774\ub7ec\ud55c \ud568\uc218\ub4e4\uc740 \uac1c\ubcc4 \uc0ac\uc6a9\uc790\uc758 \ub370\uc774\ud130 \ubcc0\uacbd\uc5d0 \uc0c1\ub300\uc801\uc73c\ub85c \ub454\uac10(insensitive)\ud558\uace0, \ub367\uc148\uc801 \ub178\uc774\uc988(additive perturbations)\ub97c \ucd94\uac00\ud558\ub354\ub77c\ub3c4 \uc720\uc6a9\uc131\uc774 \ud06c\uac8c \uac10\uc18c\ud558\uc9c0 \uc54a\ub294 \ud2b9\uc131\uc744 \uac16\ub294\ub2e4. \ub9ce\uc740 \ud1b5\uacc4\uc801 \uc9c0\ud45c(statistical quantities)\ub4e4\uc774 \uc774\ub7ec\ud55c \uc694\uad6c\uc0ac\ud56d\uc744 \ucda9\uc871\ud558\uba70, \uc77c\ubd80 \uacc4\uc0b0\uc801 \uc9c0\ud45c(computational quantities)\ub4e4\ub3c4 \ub3d9\uc77c\ud558\uac8c \uc801\uc6a9\ub420 \uc218 \uc788\ub2e4.<br>\ub530\ub77c\uc11c \ub300\ubd80\ubd84\uc758 \uc5f0\uad6c\ub294 \ub367\uc148\uc801 \ub178\uc774\uc988 \ud06c\uae30\ub97c \uc904\uc774\ub294 \ubc29\ud5a5\uc73c\ub85c \uc9c4\ud589\ub418\uc5c8\ub2e4.<\/p>\n\n\n\n<p>\ud568\uc218\uc758 \uc18d\uc131(properties of the function)\uc744 \uc5f0\uad6c\ud558\uac70\ub098, <br>\ud568\uc218\uc758 \ubbfc\uac10\ub3c4(sensitivity)\uac00 \uade0\uc77c\ud558\uc9c0 \uc54a\ub2e4\ub294 \uc810(non-uniformity sensitivity)\uc744 \ud65c\uc6a9\ud558\ub294 \ubc29\ubc95 \ub4f1\uc774 \ucd5c\uadfc \uc5f0\uad6c\uc5d0\uc11c \uc8fc\ubaa9\ubc1b\uace0 \uc788\ub2e4 [33].<\/p>\n\n\n\n<p>\uadf8\ub7ec\ub098 \uae30\uc874 \uc811\uadfc\ubc95\ub4e4\uc774 \ub17c\uc758\ud558\uc9c0 \uc54a\uc740 \uc911\uc694\ud55c \ubb38\uc81c\ub294, <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\uc774\ub7ec\ud55c \uac00\uc815\ub4e4\uc774 \uc131\ub9bd\ud558\uc9c0 \uc54a\ub294 \uc601\uc5ed\uc5d0\uc11c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc5b4\ub5bb\uac8c \uc801\uc6a9\ud560 \uac83\uc778\uac00\uc774\ub2e4.<\/mark><br>\uc608\ub97c \ub4e4\uc5b4, \ubb34\uc81c\ud55c \uacf5\uae09 \uacbd\ub9e4(unlimited supply auctions)\ub97c \uace0\ub824\ud558\uba74,<br>\u201c\ud310\ub9e4\ud560 \ucd5c\uc801\uc758 \uace0\uc815 \uac00\uaca9(optimal fixed price to sell at)\u201c\uc744 \uacb0\uc815\ud558\ub294 \ud568\uc218\ub294 \ubbfc\uac10\ub3c4\uac00 \ub0ae\uc740(insensitive) \ud568\uc218\uac00 \uc544\ub2c8\ub2e4.\ub2e8\uc77c \uc785\ucc30\uc790(single bidder)\uc758 \ub370\uc774\ud130 \ubcc0\uacbd\ub9cc\uc73c\ub85c\ub3c4 \ucd5c\uc801 \uac00\uaca9\uc774 \ud06c\uac8c \ubcc0\ud560 \uac00\ub2a5\uc131\uc774 \uc788\ub2e4.<br>\ub610\ud55c, \ub367\uc148\uc801 \ub178\uc774\uc988\ub97c \ucd94\uac00\ud574\ub3c4 \uc548\uc815\uc801\uc774\uc9c0 \uc54a\ub2e4.<br>\uc81c\uc2dc\ub41c \uac00\uaca9(offer price)\uc774 \uc870\uae08\ub9cc \ub192\uc544\uc838\ub3c4 \ubaa8\ub4e0 \uc785\ucc30\uc790\uac00 \uad6c\ub9e4\ub97c \ud3ec\uae30\ud560 \uac00\ub2a5\uc131\uc774 \uc788\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n\n\n\n<p>\ucd5c\uadfc Nissim et al. [33]\uc758 \uc5f0\uad6c\uc5d0\uc11c\ub294 \ucd5c\uc801 \uac00\uaca9\uc774 \ubbfc\uac10\ud558\uc9c0 \uc54a\uc740 \uacbd\uc6b0\ub97c \ub2e4\ub8e8\uc5c8\uc73c\ub098,<br>\uac00\uaca9\uc774 \ubbfc\uac10\ud558\uac8c \ubcc0\ud558\ub294 \uacbd\uc6b0(sensitive instances)\ub098 \ub367\uc148\uc801 \ub178\uc774\uc988\uc758 \ubb38\uc81c\ub294 \ud574\uacb0\ud558\uc9c0 \ubabb\ud588\ub2e4.<br>\ubcf8 \uc5f0\uad6c\uc5d0\uc11c\ub294 \uc774\ub7ec\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \ubcf4\ub2e4 \uc77c\ubc18\uc801\uc778 \ud504\ub808\uc784\uc6cc\ud06c\ub97c \uc81c\uc548\ud55c\ub2e4.<\/p>\n\n\n\n<p>\ub354 \ub098\uc544\uac00, \uc774 \uc5f0\uad6c\uc5d0\uc11c \ud574\uacb0\ud558\uace0\uc790 \ud558\ub294 \ub354 \ud070 \ubb38\uc81c\ub294 \u201c<mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\ucd9c\ub825\uc774 \uc218\uce58 \uac12\uc774 \uc544\ub2cc(non-numeric output) \uacbd\uc6b0\uc5d0\ub3c4 \uc801\uc6a9 \uac00\ub2a5\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud558\ub294 \uac83<\/mark>\u201d\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc608\ub97c \ub4e4\uc5b4:<br>\uba38\uc2e0 \ub7ec\ub2dd(Machine Learning)\uc5d0\uc11c\ub294 \ubaa8\ub378(model)\uc774\ub098 \ubd84\ub958\uae30(classifier)\ub97c \uc0dd\uc131\ud55c\ub2e4.<br>\ucd5c\uc801\ud654(Optimization)\uc5d0\uc11c\ub294 \uc2dc\uc124\uc744 \ud65c\uc131\ud654\ud558\uac70\ub098(flow routing), \uacbd\ub85c\ub97c \uc124\uc815(route flow)\ud558\ub294 \ubb38\uc81c\uac00 \uc874\uc7ac\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc774\ub7ec\ud55c \ud574\uacb0\ucc45\ub4e4\uc740 \uc218\uce58 \uac12\uc744 \ud3ec\ud568\ud560 \uc218\ub3c4 \uc788\uc9c0\ub9cc, \uc0c1\ub2f9 \ubd80\ubd84\uc774 \uad6c\uc870\uc801 \uc815\ubcf4(structural information)\ub85c \uad6c\uc131\ub418\uba70, \uc774\ub294 \uc27d\uac8c \u201c\ub178\uc774\uc988 \ucd94\uac00(perturbation)\u201c\uac00 \uc5b4\ub835\ub2e4.<\/p>\n\n\n\n<p>\ub530\ub77c\uc11c, \ubcf8 \uc5f0\uad6c\uc5d0\uc11c\ub294<br>\uc784\uc758\uc758 \uce21\uc815 \uac00\ub2a5\ud55c \ubc94\uc704(arbitrary measurable range)\ub97c \ud5c8\uc6a9\ud558\ub294 \uc77c\ubc18\uc801\uc778 \ud504\ub808\uc784\uc6cc\ud06c\ub97c \uac1c\ubc1c\ud558\uace0,<br>\uc774\uc804 \uc5f0\uad6c\ub4e4\uc774 \ub2e4\ub8e8\uc9c0 \ubabb\ud55c \ubb38\uc81c\ub4e4\uc744 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\ud638\ud558\ub294 \ubc29\uc2dd(privacy-preserving manner)\uc73c\ub85c \ud574\uacb0\ud558\ub294 \uac83\uc744 \ubaa9\ud45c\ub85c \ud55c\ub2e4.<br>\uc774 \ud504\ub808\uc784\uc6cc\ud06c\ub294 \ubaa8\ub4e0 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc81c\uacf5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \ud3ec\ud568\ud560 \uc218 \uc788\ub3c4\ub85d \uc124\uacc4\ub418\uc5c8\uc73c\uba70,<br>\ud2b9\uc815\ud55c \ud658\uacbd\uc5d0\uc11c \ubc1c\uc0dd\ud560 \uc218 \uc788\ub294 \uacc4\uc0b0\uc801 \uc774\uc810(computational benefits)\uc744 \ubc18\ub4dc\uc2dc \ub178\ucd9c\ud560 \ud544\uc694 \uc5c6\uc774, \uc77c\ubc18\uc801\uc778 \ud615\ud0dc\ub85c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc801\uc6a9\ud560 \uc218 \uc788\ub3c4\ub85d \ud55c\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Applications to Digital Goods Auctions<\/h4>\n\n\n\n<p>\ub514\uc9c0\ud138 \uc0c1\ud488 \uacbd\ub9e4 \ubb38\uc81c(Digital Goods Auction Problem)\ub294 \ubb34\uc81c\ud55c\uc73c\ub85c \uacf5\uae09\ub418\ub294 \uc0c1\ud488\uc744 \ud310\ub9e4\ud558\ub294 \uacbd\ub9e4 \ud658\uacbd\uc744 \ub2e4\ub8ec\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc785\ucc30\uc790(bidders) \uc218\ub294 n\uba85\uc774\uba70, \uac01 \uc785\ucc30\uc790\ub294 \ud574\ub2f9 \uc0c1\ud488\uc5d0 \ub300\ud55c \uac1c\ubcc4\uc801\uc778(private) \ud6a8\uc6a9(utility)\uc744 \uac00\uc9c4\ub2e4.<\/li>\n\n\n\n<li>\uacbd\ub9e4\uc790(auctioneer)\ub294 \uc0c1\ud488\uc744 \ubb34\uc81c\ud55c\uc73c\ub85c \uacf5\uae09\ud560 \uc218 \uc788\uc73c\uba70, \uac01 \uc785\ucc30\uc790\ub85c\ubd80\ud130 [0,1] \ubc94\uc704\uc758 \uc785\ucc30\uac00(bid)\ub97c \uc81c\ucd9c\ubc1b\ub294\ub2e4.<\/li>\n\n\n\n<li>\uc785\ucc30 \uacb0\uacfc\ub97c \uae30\ubc18\uc73c\ub85c \uc0c1\ud488\uc744 \ub204\uad6c\uc5d0\uac8c \uc81c\uacf5\ud560\uc9c0, \uadf8\ub9ac\uace0 \uc5b4\ub5a4 \uac00\uaca9\uc73c\ub85c \ud310\ub9e4\ud560\uc9c0\ub97c \uacb0\uc815\ud55c\ub2e4.<\/li>\n\n\n\n<li>\uc81c\ucd9c\ub41c \uc785\ucc30\uc790\ub4e4\ub85c\ubd80\ud130 \uacbd\ub9e4\uc778\uc774 \uc5bb\uc744 \uc218 \uc788\ub294 \ucd5c\uc801\uc758 \uace0\uc815 \uac00\uaca9 \uc218\uc775\uc744 OPI\ub85c \uc815\uc758\ud55c\ub2e4.<br>\uc989, OPT(Optimal Fixed Price Revenue)\ub294 \uc81c\ucd9c\ub41c \uc785\ucc30\uac00\uc5d0\uc11c \uacbd\ub9e4\uc790\uac00 \ucd5c\uc801\uc758 \uace0\uc815 \uac00\uaca9\uc744 \uc124\uc815\ud588\uc744 \ub54c \uc5bb\uc744 \uc218 \uc788\ub294 \ucd5c\ub300 \uc218\uc775\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p><strong>Theorem 1<\/strong>. (\ub514\uc9c0\ud138 \uc0c1\ud488 \uacbd\ub9e4 \ubb38\uc81c\uc5d0\uc11c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc801\uc6a9\ud55c \uba54\ucee4\ub2c8\uc998)<\/p>\n\n\n\n<p>\ub514\uc9c0\ud138 \uc0c1\ud488 \uacbd\ub9e4 \ubb38\uc81c\uc5d0\uc11c \u03f5-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(\u03f5-differential privacy)\ub97c \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \uc874\uc7ac\ud558\uba70,<br>\ud574\ub2f9 \uba54\ucee4\ub2c8\uc998\uc758 \uae30\ub300 \uc218\uc775(expected revenue)\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ud558\ud55c\uc744 \uac16\ub294\ub2e4:<\/p>\n\n\n\n<p>\\(\\text{OPT} &#8211; \\frac{3 \\ln(e + \u03f5^2 \\text{OPT} n)}{\u03f5}\\)<\/p>\n\n\n\n<p><strong>\uae30\uc874 \uc5f0\uad6c\uc640\uc758 \ube44\uad50<\/strong><\/p>\n\n\n\n<p>\uc774 \uc5f0\uad6c\uc5d0\uc11c \uc81c\uc548\ud558\ub294 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \uba54\ucee4\ub2c8\uc998\uc740 \uae30\uc874\uc758 Balcan et al. [6] \uc5f0\uad6c\uc640 \ube44\uad50\ub41c\ub2e4.<br>Balcan et al. [6] \uc5f0\uad6c\uc5d0\uc11c\ub294 \uba38\uc2e0\ub7ec\ub2dd(machine learning)\uc744 \ud65c\uc6a9\ud558\uc5ec, \ubb34\uc791\uc704 \ud45c\ubcf8\uc5d0\uc11c \ud559\uc2b5\ud558\ub294 \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud588\ub2e4.<br>\uadf8 \uacb0\uacfc \uc9c4\uc2e4\ud55c \uc751\ub2f5(truthful bidding)\uc744 \uc720\ub3c4\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud588\uc73c\uba70,<br>\uae30\ub300 \uc218\uc775\uc740 \\(\\text{OPT} &#8211; O(\\sqrt{\\text{OPT}})\\) \uc218\uc900\uc744 \ub2ec\uc131\ud588\ub2e4.<\/p>\n\n\n\n<p><strong>\ud558\uc9c0\ub9cc \ubcf8 \uc5f0\uad6c\uc5d0\uc11c\ub294:<\/strong><\/p>\n\n\n\n<p>\uc5c4\uaca9\ud55c \uc9c4\uc2e4\uc131(strict truthfulness)\uc744 \ud3ec\uae30\ud558\ub294 \ub300\uc2e0,<br>\ucd5c\uc801 \uae30\ub300 \uc218\uc775(OPT)\uacfc\uc758 \ucc28\uc774\ub97c \uae30\ud558\uae09\uc218\uc801\uc73c\ub85c \uac10\uc18c\uc2dc\ud0b4\uc73c\ub85c\uc368, \ub354 \ub098\uc740 \uae30\ub300 \uc218\uc775\uc744 \ubcf4\uc7a5\ud55c\ub2e4.<br>\ub610\ud55c, Balcan et al. [6]\uc5d0\uc11c \uc81c\uacf5\ud558\uc9c0 \uc54a\ub294 \uac15\ub825\ud55c \uc18d\uc131\ub4e4(Section 2\uc5d0\uc11c \ub17c\uc758\ub428)\uc744 \ucd94\uac00\ub85c \ubcf4\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n<p>\ucd94\uac00\uc801\uc73c\ub85c,<br>\uc81c\uc548\ub41c \uba54\ucee4\ub2c8\uc998\uc740 \ubaa8\ub4e0 \uc0ac\uc6a9\uc790\uc5d0\uac8c \ub3d9\uc77c\ud55c \uac00\uaca9\uc744 \uc801\uc6a9\ud558\ubbc0\ub85c \u201c\uc9c8\ud22c \uc5c6\uc74c(envy-free)\u201d \uc18d\uc131\uc744 \ubcf4\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n<p><strong>\ub514\uc9c0\ud138 \uc0c1\ud488 \uc18d\uc131 \uacbd\ub9e4(Digital Goods Attribute Auction)\ub85c\uc758 \ud655\uc7a5<\/strong><\/p>\n\n\n\n<p>\ub514\uc9c0\ud138 \uc0c1\ud488 \uc18d\uc131 \uacbd\ub9e4(Digital Goods Attribute Auction)\ub294 \uae30\ubcf8 \ub514\uc9c0\ud138 \uc0c1\ud488 \uacbd\ub9e4 \ubb38\uc81c\ub97c \ud655\uc7a5\ud55c \uac1c\ub150\uc774\ub2e4.<br>\uac01 \ucc38\uac00\uc790\ub294 \uacf5\uac1c\ub41c(public) \ubcc0\ud558\uc9c0 \uc54a\ub294(immutable) \uc18d\uc131(attributes)\uc744 \uac00\uc9c4\ub2e4.<br>\uc774 \ubb38\uc81c\uc5d0\uc11c \uba54\ucee4\ub2c8\uc998\uc758 \ucd9c\ub825(output)\uc740 \uc2dc\uc7a5 \uc138\ubd84\ud654(market segmentation)\ub97c \uc124\uba85\ud55c\ub2e4.<br>\uc989, \uc18d\uc131 \uacf5\uac04(attribute space)\uc758 \ubd84\ud560(partitioning)\uacfc \uac01 \uc2dc\uc7a5 \uc138\ubd84\ud654\ubcc4 \uac00\uaca9\uc744 \uacb0\uc815\ud55c\ub2e4.<br>\uc77c\ubc18\uc801\uc73c\ub85c \uac00\ub2a5\ud55c \uc138\ubd84\ud654(segmentations)\ub97c \uc81c\ud55c\ud558\uc5ec, \ucd5c\uc801\ud574(optimal solution)\uac00 \ubcf4\ub2e4 \uad00\ub9ac \uac00\ub2a5\ud55c \ud615\ud0dc\ub85c \uc720\uc9c0\ub418\ub3c4\ub85d \ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc774 \ubb38\uc81c\uc5d0\uc11c\ub294:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>OPTk: k\uac1c\uc758 \uc2dc\uc7a5(segment)\uc73c\ub85c \ub098\ub208 \uacbd\uc6b0 \ucd5c\uc801 \uc218\uc775(optimal revenue)<\/li>\n\n\n\n<li>SEGk: \ud604\uc7ac \uc785\ucc30\uc790\ub4e4\uc758 \uc18d\uc131\uc744 \uae30\uc900\uc73c\ub85c k\uac1c\uc758 \uc2dc\uc7a5(segment)\uc73c\ub85c \ub098\ub20c \uc218 \uc788\ub294 \ubc29\ubc95\uc758 \uc218(number of segmentations)<\/li>\n<\/ul>\n\n\n\n<p>\uc989, \uc18d\uc131\uc744 \uae30\ubc18\uc73c\ub85c \ucd5c\uc801 \uc2dc\uc7a5 \uc138\ubd84\ud654\ub97c \ucc3e\ub294 \ubb38\uc81c\ub85c \ud655\uc7a5\ub41c \ub514\uc9c0\ud138 \uc0c1\ud488 \uacbd\ub9e4 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p><strong>Theorem 2<\/strong>. (\ub514\uc9c0\ud138 \uc0c1\ud488 \uc18d\uc131 \uacbd\ub9e4 \ubb38\uc81c\uc5d0\uc11c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc801\uc6a9\ud55c \uba54\ucee4\ub2c8\uc998)<\/p>\n\n\n\n<p>\ub514\uc9c0\ud138 \uc0c1\ud488 \uc18d\uc131 \uacbd\ub9e4(Digital Goods Attribute Auction) \ubb38\uc81c\uc5d0\uc11c \u03f5-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(\u03f5-differential privacy)\ub97c \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \uc874\uc7ac\ud558\uba70,<br>\ud574\ub2f9 \uba54\ucee4\ub2c8\uc998\uc758 \uae30\ub300 \uc218\uc775(expected revenue)\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ud558\ud55c\uc744 \uac16\ub294\ub2e4:<\/p>\n\n\n\n<p>\\(\\max_k \\left( OPT_k &#8211; \\frac{3 \\ln(e + \u03f5^{k+1} OPT_k SEG_k n^{k+1})}{\u03f5} \\right)\\)<\/p>\n\n\n\n<p><strong>\uae30\uc874 \uc5f0\uad6c([6] Theorem 5)\uc640\uc758 \ube44\uad50<\/strong><\/p>\n\n\n\n<p>\uae30\uc874 \uc5f0\uad6c\uc778 Balcan et al. [6]\uc758 Theorem 5\uc5d0\uc11c\ub294 \uad6c\uc870\uc801 \uc704\ud5d8 \ucd5c\uc18c\ud654(Structural Risk Minimization, SRM)\ub97c \uae30\ubc18\uc73c\ub85c \ud55c \uae30\ub300 \uc218\uc775 \ud558\ud55c\uc744 \uc81c\uacf5\ud588\ub2e4.<br>\uc774 \uc5f0\uad6c\uc5d0\uc11c\ub294 \ub2e4\uc74c\uc744 \ubcf4\uc7a5\ud55c\ub2e4:<\/p>\n\n\n\n<p>\\(\\max_k \\left( OPT_k &#8211; O\\left( (OPT_k^2 \\ln(k^2 SEG_k))^{1\/3} \\right) \\right)\\)<\/p>\n\n\n\n<p>\uc989, \uae30\uc874 \uc5f0\uad6c\uc5d0\uc11c\ub294 \ud655\ub960\uc801\uc73c\ub85c \ub192\uc740 \uc2e0\ub8b0\ub3c4\ub97c \uac00\uc9c0\ub294 \uae30\ub300 \uc218\uc775\uc744 \ubcf4\uc7a5\ud588\ub2e4.<\/p>\n\n\n\n<p>\ud558\uc9c0\ub9cc \ubcf8 \uc5f0\uad6c\uc758 \ucc28\ubcc4\uc810\uc740:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc5c4\uaca9\ud55c \uc9c4\uc2e4\uc131(strict truthfulness)\uc744 \ud3ec\uae30\ud558\ub294 \ub300\uc2e0,<\/li>\n\n\n\n<li>\ucd94\uac00\uc801\uc778 \uae30\ub300 \uc218\uc775 \uc99d\uac00 \ubc0f Section 2\uc5d0\uc11c \ub17c\uc758\ub41c \ucd94\uac00 \uc18d\uc131\ub4e4\uc744 \ubcf4\uc7a5\ud558\uba70,\ub2e8\uc77c \uac00\uaca9(single-price) \uc815\ucc45\uc744 \uc720\uc9c0\ud558\uc5ec \u201c\uc9c8\ud22c \uc5c6\uc74c(envy-free)\u201d \uc18d\uc131\uc744 \ubcf4\uc7a5\ud55c\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p><strong>\ucd94\uac00\uc801\uc778 \uc5f0\uad6c \uae30\uc5ec<\/strong><\/p>\n\n\n\n<p>\ubcf8 \uc5f0\uad6c\uc5d0\uc11c\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ucd94\uac00\uc801\uc778 \uc0c8\ub85c\uc6b4 \uacb0\uacfc\ub97c \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\uc81c\uc57d\ub41c \uac00\uaca9 \uc124\uc815(constrained pricing) \ubb38\uc81c\uc5d0 \ub300\ud55c \uc0c8\ub85c\uc6b4 \uacb0\uacfc \uc81c\uacf5<br><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\ud2b9\uc815\ud55c \uac00\uaca9 \uc81c\ud55c \uc870\uac74\uc774 \uc788\ub294 \uacbd\uc6b0\uc5d0\ub3c4 \uc801\uc6a9\ud560 \uc218 \uc788\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4<\/mark><\/li>\n\n\n\n<li>\uc5ec\ub7ec \uac1c\uc758 \uc9c4\uc2e4\ud55c \uc54c\uace0\ub9ac\uc998(truthful algorithms) \uc911 \ucd5c\uc801\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \uc120\ud0dd\ud558\uace0 \uc801\uc6a9\ud558\ub294 \ubb38\uc81c \ud574\uacb0<br><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\ub2e4\uc591\ud55c \uc9c4\uc2e4\ud55c \uc54c\uace0\ub9ac\uc998\uc774 \uc788\uc744 \ub54c, \ucd5c\uc801\uc758 \uc218\uc775\uc744 \ubcf4\uc7a5\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc744 \uc120\ud0dd\ud558\ub294 \ubc29\ubc95\uc744 \uc81c\uc548<\/mark><\/li>\n<\/ol>\n\n\n\n<h4 class=\"wp-block-heading\">1.1.1. Previous Work in Privacy<\/h4>\n\n\n\n<p>\uc5ec\ub7ec \uc5f0\uad6c\uc5d0\uc11c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(differential privacy)\ub97c \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \uc81c\uc548\ub418\uc5c8\uc73c\uba70, \uc8fc\ub85c \ub370\uc774\ud130 \ub9c8\uc774\ub2dd, \uba38\uc2e0 \ub7ec\ub2dd, \ud1b5\uacc4 \ubd84\uc57c\uc758 \uc791\uc5c5\uc5d0\uc11c \ud65c\uc6a9\ub418\uc5c8\ub2e4.<br>\uc774\ub7ec\ud55c \uba54\ucee4\ub2c8\uc998\uc758 \ud070 \ud2b9\uc9d5 \uc911 \ud558\ub098\ub294 \ucd9c\ub825\uac12\uc774 \uc791\uc740 \ub367\uc148\uc801 \ub178\uc774\uc988(additive noise)\uc5d0 \ub300\ud574 \uac15\uc778(robust)\ud558\uac8c \uc720\uc9c0\ub41c\ub2e4\ub294 \uc810\uc774\ub2e4.<br>\ub530\ub77c\uc11c, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud558\uae30 \uc704\ud574 \uc801\uc808\ud55c \ub178\uc774\uc988\ub97c \ucd94\uac00\ud574\ub3c4 \uc720\uc6a9\uc131\uc744 \ud06c\uac8c \uc190\uc0c1\uc2dc\ud0a4\uc9c0 \uc54a\ub294 \ubc29\uc2dd\uc774 \uc0ac\uc6a9\ub41c\ub2e4.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\ub367\uc148\uc801 \ub178\uc774\uc988 \uae30\ubc18 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \uba54\ucee4\ub2c8\uc998<br>[9, 15] \uc5f0\uad6c\uc5d0\uc11c\ub294 \ub300\uce6d\uc801\uc778(exp) \ubd84\ud3ec\ub97c \ub530\ub974\ub294 \ub178\uc774\uc988\ub97c \ud2b9\uc815 \ud568\uc218\uc5d0 \ucd94\uac00\ud558\uba74 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc600\ub2e4.<br>\uc774\ub7ec\ud55c \ud568\uc218\ub294 Lipschitz \uc5f0\uc18d \uc870\uac74(Lipschitz condition)\uc744 \ub9cc\uc871\ud574\uc57c \ud558\uba70, \uc989, \uc785\ub825 \ub370\uc774\ud130\uac00 \uc870\uae08 \ubcc0\uacbd\ub418\ub354\ub77c\ub3c4 \ucd9c\ub825\uc774 \ud070 \uc601\ud5a5\uc744 \ubc1b\uc9c0 \uc54a\ub3c4\ub85d \uc81c\uc5b4\ub41c\ub2e4.<\/li>\n\n\n\n<li>\uc9c0\uc5ed(local) \ubbfc\uac10\ub3c4\ub97c \ud65c\uc6a9\ud55c \uc5f0\uad6c<br>Nissim et al. [33] \uc5f0\uad6c\uc5d0\uc11c\ub294 \ud568\uc218\uc758 \uc804\uc5ed(global) \ubbfc\uac10\ub3c4\uac00 \ud06c\ub354\ub77c\ub3c4, \uc9c0\uc5ed(local) \ubbfc\uac10\ub3c4\uac00 \uc791\uc740 \uacbd\uc6b0\ub97c \ud65c\uc6a9\ud558\ub294 \ubc29\ubc95\uc744 \uc81c\uc548\ud558\uc600\ub2e4.<br>\uc774\ub294 \uacc4\uc0b0\ub41c \uac12\uc5d0 \ucd94\uac00\ub418\ub294 \ub178\uc774\uc988\uc758 \ud06c\uae30\ub97c \uc0c1\ub2f9\ud788 \uc904\uc77c \uc218 \uc788\ub3c4\ub85d \uac1c\uc120\ud560 \uc218 \uc788\ub2e4.<\/li>\n<\/ol>\n\n\n\n<p>\ub2e4\ub978 \uc815\ubcf4 \uc720\ucd9c \ubc29\uc9c0 \uae30\ubc95(disclosure limitation techniques)\uc73c\ub85c\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uac83\ub4e4\uc774 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc785\ub825 \ubcc0\ud615(input perturbation): \uc0ac\uc6a9\uc790\uac00 \uc81c\uacf5\ud558\ub294 \ub370\uc774\ud130\ub97c \ub09c\uc218\ud654(scrambling)\ud558\uc5ec \uc9c1\uc811 \ubcc0\ud615\ud558\ub294 \ubc29\uc2dd.<br>\ucffc\ub9ac \uc81c\ud55c(query restriction): \ud2b9\uc815 \ucffc\ub9ac(\uc9c8\ubb38)\uc758 \ucd9c\ub825\uc774 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc704\ud611\ud560 \uac00\ub2a5\uc131\uc774 \ub192\ub2e4\uba74, \ud574\ub2f9 \ucffc\ub9ac\uc5d0 \ub300\ud55c \uc751\ub2f5\uc744 \uc81c\ud55c\ud558\ub294 \ubc29\uc2dd.<\/p>\n\n\n\n<p>\uc774\ub7ec\ud55c \uc5f0\uad6c\ub4e4\uc740 \uc808\ub300\uc801\uc778 \uc815\ubcf4 \uc720\ucd9c \ubc29\uc9c0(absolute disclosure limitation)\ub97c \ubaa9\ud45c\ub85c \ud558\uc9c0\ub9cc,<br>\uc774\ub294 \uacf5\uaca9\uc790\uc758 \uc0ac\uc804 \uc9c0\uc2dd(prior knowledge)\uc5d0 \ub300\ud55c \uac00\uc815\uc744 \ud3ec\ud568\ud558\ub294 \uacbd\uc6b0\uac00 \ub9ce\ub2e4.<br>\ud2b9\ud788 [14] \uc5f0\uad6c\uc5d0\uc11c\ub294 \uacf5\uaca9\uc790\uc758 \uc0ac\uc804 \uc9c0\uc2dd\uc744 \uc81c\ud55c\ud558\uc9c0 \uc54a\uc73c\uba74, \uc808\ub300\uc801\uc778 \uc815\ubcf4 \uc720\ucd9c \ubc29\uc9c0\ub294 \ubd88\uac00\ub2a5\ud558\ub2e4\ub294 \uac83\uc744 \uc99d\uba85\ud588\ub2e4.<br>\uc774\ub294 <mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uac00 \uc808\ub300\uc801\uc778 \ubcf4\ud638\ub97c \uc81c\uacf5\ud558\ub294 \uac83\uc774 \uc544\ub2c8\ub77c, \ud655\ub960\uc801(\ud1b5\uacc4\uc801) \ubcf4\uc7a5\uc744 \ud1b5\ud574 \uc815\ubcf4 \uc720\ucd9c \uac00\ub2a5\uc131\uc744 \uc81c\ud55c\ud558\ub294 \ubc29\uc2dd\uc784\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/mark><br>\ucd94\uac00\uc801\uc73c\ub85c, \uad00\ub828 \uc5f0\uad6c\uc5d0 \ub300\ud55c \uc88b\uc740 \uc11c\ubca0\uc774 \ub17c\ubb38\uc740 [1]\uc5d0\uc11c \ud655\uc778\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">1.1.2. Previous Work in Mechanism Design<\/h4>\n\n\n\n<p>\uba54\ucee4\ub2c8\uc998 \ub514\uc790\uc778(mechanism design)\uc740 \uac8c\uc784 \uc774\ub860 \ubc0f \uacbd\uc81c\ud559\uc5d0\uc11c \uc624\ub79c \uc5f0\uad6c \uc5ed\uc0ac\ub97c \uac00\uc9c4 \ubd84\uc57c\ub85c,<br>Vickrey \uacbd\ub9e4\ub97c \uc2dc\uc791\uc73c\ub85c \uc0ac\ud68c\uc801 \uc120\ud0dd \uc774\ub860(social choice theory)\uae4c\uc9c0 \ud655\uc7a5\ub418\uc5c8\ub2e4.<br>(\uc790\uc138\ud55c \ub0b4\uc6a9\uc740 Mas-Colell, Whinston, Green\uc758 \uc800\uc11c [30] \ucc38\uace0)<\/p>\n\n\n\n<p>\ud2b9\ud788, \uc54c\uace0\ub9ac\uc998\uc801 \uba54\ucee4\ub2c8\uc998 \ub514\uc790\uc778(algorithmic mechanism design)\uc740 Nisan\uacfc Ronen [32]\uc758 \uc5f0\uad6c\ub97c \uae30\uc810\uc73c\ub85c \ubc1c\uc804\ud558\uc600\uc73c\uba70, \uc8fc\ub85c \uc9c4\uc2e4\ud55c(truthful) \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0 \ucd08\uc810\uc744 \ub9de\ucdb0\uc654\ub2e4.<br>\ub300\ud45c\uc801\uc778 \uc608\ub85c, \ub514\uc9c0\ud138 \uc0c1\ud488 \uacbd\ub9e4(auctions for digital goods), \uc2a4\ucf00\uc904\ub9c1 \ubb38\uc81c(scheduling problems), \uc870\ud569\uc801 \uacbd\ub9e4(combinatorial auctions) \ub4f1\uc774 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uadf8\ub7ec\ub098 \uac15\ud55c \uc9c4\uc2e4\uc131(truthfulness) \uac00\uc815\uc774 \ub108\ubb34 \uc81c\ud55c\uc801\uc774\uc5b4\uc11c, \uba54\ucee4\ub2c8\uc998\uc774 \uac00\uc9c8 \uc218 \uc788\ub294 \ub2e4\ub978 \uc911\uc694\ud55c \ud2b9\uc131\uc744 \ubc29\ud574\ud558\ub294 \uacbd\uc6b0\uac00 \ub9ce\ub2e4.<\/p>\n\n\n\n<p>\uc608\ub97c \ub4e4\uc5b4,<br>1) Archer &amp; Tardos [4], Elkind, Sahai &amp; Steiglitz [16] \uc5f0\uad6c\uc5d0\uc11c\ub294<br>\uadf8\ub798\ud504 \ub0b4 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uad6c\ub9e4\ud558\ub294 \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc9c0\ub098\uce58\uac8c \ub192\uc740 \ube44\uc6a9\uc744 \ucd08\ub798\ud55c\ub2e4\ub294 \uac83\uc744 \ubcf4\uc600\ub2e4.<\/p>\n\n\n\n<p>2) \uc870\ud569\uc801 \uacbd\ub9e4(combinatorial auction) \ubb38\uc81c\uc5d0\uc11c, Lavi, Mu\u2019alem, Nisan [27]\uc758 \uc5f0\uad6c\ub294<br>\uc790\uc5f0\uc2a4\ub7ec\uc6b4 \uac00\uc815\ud558\uc5d0\uc11c \uc9c4\uc2e4\ud558\uba74\uc11c\ub3c4 \uacc4\uc0b0\uc801\uc73c\ub85c \ud6a8\uc728\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc774 \ub192\uc740 \uc0ac\ud68c\uc801 \ubcf5\uc9c0(social welfare)\ub97c \ubcf4\uc7a5\ud558\uc9c0 \ubabb\ud568\uc744 \uc99d\uba85\ud588\ub2e4.<br>\ub2e8\uc77c \ud30c\ub77c\ubbf8\ud130(single-parameter) \uc5d0\uc774\uc804\ud2b8\uc5d0 \ub300\ud55c \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\uc740 \ube44\uad50\uc801 \uc798 \uc5f0\uad6c\ub418\uc5c8\uc9c0\ub9cc,<br>\ub2e4\ucc28\uc6d0(multi-dimensional) \uc5d0\uc774\uc804\ud2b8\uc5d0 \ub300\ud55c \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\uc758 \ud2b9\uc131 \ubd84\uc11d\uc740 \uc0c1\ub300\uc801\uc73c\ub85c \ucd5c\uadfc \uc5f0\uad6c\uc5d0\uc11c \ub2e4\ub8e8\uc5b4\uc84c\ub2e4 [8, 35].<\/p>\n\n\n\n<p><strong>\uac15\ud55c \uc9c4\uc2e4\uc131(truthfulness)\uc758 \uc644\ud654(Relaxation of Strong Truthfulness)<\/strong><\/p>\n\n\n\n<p>\ub530\ub77c\uc11c, \uc9c4\uc2e4\uc131 \uac00\uc815\uc744 \uc644\ud654\ud558\ub294 \uc5f0\uad6c\uac00 \uc790\uc5f0\uc2a4\ub7fd\uac8c \uace0\ub824\ub418\uc5c8\uc73c\uba70, \uc774\ubbf8 \uad11\ubc94\uc704\ud558\uac8c \uc5f0\uad6c\ub418\uc5c8\ub2e4.<\/p>\n\n\n\n<p>1. Bayes-Nash \uade0\ud615(Bayes-Nash equilibria) \uc801\uc6a9<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uacbd\ub9e4 \uc774\ub860\uc5d0\uc11c\ub294 Bayes-Nash \uade0\ud615\uc744 \uae30\ubc18\uc73c\ub85c \ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc77c\ubc18\uc801\uc774\ub2e4 (\uc608: [30]).<\/li>\n\n\n\n<li>Elkind et al. [16]: \ucd5c\ub2e8 \uacbd\ub85c \uacbd\ub9e4(shortest path auctions)\uc5d0\uc11c Bayes-Nash \uade0\ud615\uc744 \ubd84\uc11d.<\/li>\n\n\n\n<li>Czumaj &amp; Ronen [13]: Nash \uade0\ud615\uacfc Myopic \uade0\ud615\uc744 \uc801\uc6a9\ud55c \ucd5c\ub2e8 \uacbd\ub85c \uacbd\ub9e4 \uc5f0\uad6c.<\/li>\n\n\n\n<li>Immorlica et al. [24]: \\(\\epsilon\\)-Nash \uade0\ud615\uc744 \uae30\ubc18\uc73c\ub85c \ud558\ub294 \uba54\ucee4\ub2c8\uc998 \uc5f0\uad6c.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><\/li>\n<\/ol>\n\n\n\n<p>2. \ud655\ub960\uc801(truthfulness with high probability) \uc9c4\uc2e4\uc131 \ubcf4\uc7a5<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Archer et al. [3]: \uc870\ud569\uc801 \uacbd\ub9e4\uc5d0\uc11c \ub192\uc740 \ud655\ub960\ub85c \uc9c4\uc2e4\uc131\uc774 \ubcf4\uc7a5\ub418\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uc5f0\uad6c.<\/li>\n\n\n\n<li>Babaioff, Lavi &amp; Pavlov [5]: \ub2e8\uc77c \uac00\uce58(single-value) \uc870\ud569\uc801 \uacbd\ub9e4\uc5d0\uc11c \uc9c4\uc2e4\ud55c \uc751\ub2f5\uc774 \uc6b0\uc6d4\ud55c \uc804\ub7b5(undominated strategy)\uc784\uc744 \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4.<\/li>\n<\/ul>\n\n\n\n<p>&#8230;<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">1.2. Paper Outline<\/h3>\n\n\n\n<p>\uc774 \ub17c\ubb38\uc740 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(differential privacy)\uc758 \uac8c\uc784 \uc774\ub860\uc801(game-theoretic) \uc601\ud5a5\uc744 \ubd84\uc11d\ud558\uace0,<br>\uc774\ub97c \ud65c\uc6a9\ud55c \uba54\ucee4\ub2c8\uc998 \uc124\uacc4(mechanism design)\ub97c \uc81c\uc548\ud558\ub294 \ub0b4\uc6a9\uc744 \ud3ec\ud568\ud558\uace0 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc81c2\uc7a5 (Section 2): <br>\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uac00 \uac8c\uc784 \uc774\ub860\uc801\uc73c\ub85c \uc5b4\ub5a4 \uacb0\uacfc\ub97c \ucd08\ub798\ud558\ub294\uc9c0 \ub17c\uc758\ud55c\ub2e4.<br>\uc774\ub97c \ud1b5\ud574 \uc804\ub7b5\uc801 \ud589\ub3d9(strategic behavior)\uc744 \uc81c\ud55c\ud558\uace0, \uc9c4\uc2e4\ud55c \uc751\ub2f5(truthfulness)\uc744 \uc720\ub3c4\ud558\ub294 \ubc29\ubc95\uc744 \uc124\uba85\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc81c3\uc7a5 (Section 3):<br>\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc81c\uacf5\ud558\ub294 \uc0c8\ub85c\uc6b4 \uba54\ucee4\ub2c8\uc998\uc744 \uac1c\ubc1c\ud558\uba70, \uae30\uc874\uc758 \ub367\uc148\uc801 \ub178\uc774\uc988(additive noise) \uba54\ucee4\ub2c8\uc998 [9, 15]\uc744 \uc77c\ubc18\ud654\ud55c\ub2e4.<br>\ub610\ud55c, \uc774 \uba54\ucee4\ub2c8\uc998\uc774 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud568\uc744 \uc99d\uba85\ud558\uace0, \ucd9c\ub825(output)\uc774 \ubc14\ub78c\uc9c1\ud558\uc9c0 \uc54a\uc744 \ud655\ub960\uc774 \ub9e4\uc6b0 \ub0ae\uc74c\uc744 \ubcf4\uc774\ub294 \uc720\uc6a9\uc131(usefulness) \uc815\ub9ac\ub97c \uc99d\uba85\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc81c4\uc7a5 (Section 4):<br>\uac1c\ubc1c\ub41c \uc77c\ubc18 \uba54\ucee4\ub2c8\uc998\uc744 \ub2e4\uc591\ud55c \uacbd\ub9e4 \ubb38\uc81c(auction problems)\uc5d0 \uc801\uc6a9\ud55c\ub2e4.<br>\ub2e8\uc77c \ud488\ubaa9 \uac00\uaca9 \uacb0\uc815(single-commodity pricing), \uc18d\uc131 \uae30\ubc18 \uacbd\ub9e4(attribute auctions), \uad6c\uc870\uc801 \uc81c\uc57d\uc774 \uc788\ub294 \uac00\uaca9 \uacb0\uc815 \ubb38\uc81c(structurally constrained pricing problems)\uc5d0 \uc801\uc6a9\ud558\uc5ec \uc131\ub2a5\uc744 \ubd84\uc11d\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uacb0\ub860 \ubc0f \ud5a5\ud6c4 \uc5f0\uad6c \ubc29\ud5a5 (Conclusion &amp; Future Work):<br>\uc5f0\uad6c\ub97c \ub9c8\ubb34\ub9ac\ud558\uba70, \ub0a8\uc740 \uac1c\ubc29\ud615 \ubb38\uc81c(open problems)\uc640 \ucd94\uac00 \uc5f0\uad6c \ubc29\ud5a5(further research)\uc744 \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2. Differential Privacy as a Solution Concept<\/h2>\n\n\n\n<p>DP\uc758 \uba87 \uac00\uc9c0 \ud568\uc758\ub97c \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0\uc11c \ubcf4\ub2e4 \uc775\uc219\ud55c \uc6a9\uc5b4\ub85c \ubcc0\ud658\ud558\uc5ec \uc124\uba85\ud55c\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">2.1 Approximate Truthfulness<\/h5>\n\n\n\n<p>\ubcf8 \ub17c\ubb38\uc5d0\uc11c \uac15\uc870\ud560 \uac1c\ub150 \uc911 \ud558\ub098\ub294 &#8216;\\(\\varepsilon\\)-\uc9c0\ubc30(\\(\\varepsilon\\)-dominance)&#8217;\uc774\ub2e4. \uc774\ub294 Schummer [37]\uc5d0 \uc758\ud574 \uc81c\uc548 \ubc0f \uc5f0\uad6c\ub41c \uac1c\ub150\uc73c\ub85c, \uc5b4\ub5a0\ud55c \uc5d0\uc774\uc804\ud2b8\u001d\ub3c4 \uc9c4\uc2e4\ub418\uc9c0 \uc54a\uc740 \uc751\ub2f5\uc744 \ud560 \uc720\uc778\uc774 \\(\\varepsilon\\) \uc774\uc0c1 \uc99d\uac00\ud558\uc9c0 \uc54a\ub294\ub2e4\ub294 \uac83\uc744 \uc758\ubbf8\ud55c\ub2e4. \uc774\ub294 \\(\\varepsilon\\)-\ub0b4\uc2dc \uade0\ud615\ubcf4\ub2e4 \uac15\ud55c \uac1c\ub150\uc774\ub2e4.<\/p>\n\n\n\n<p>\\(\\varepsilon\\)-DP\ub97c \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc740 \uc9c4\uc2e4\ud55c \ubcf4\uace0\ub97c (\\(exp(\\epsilon)-1\\))-\uc9c0\ubc30 \uc804\ub7b5\uc73c\ub85c \ub9cc\ub4e0\ub2e4. \uc774\ub294 \uc720\ud2f8\ub9ac\ud2f0 \ud568\uc218\uac00 \uba54\ucee4\ub2c8\uc998 \ucd9c\ub825\uc758 \ubc94\uc704 \\(Range(M)\\)\uc5d0\uc11c [0, 1]\ub85c \ub9e4\ud551\ub418\ub294 \ubaa8\ub4e0 \uacbd\uc6b0\uc5d0 \ud574\ub2f9\ub41c\ub2e4. \uc774\ub294 \ubcf4\ub2e4 \uc77c\ubc18\uc801\uc778 \ubcf4\uc7a5\uc5d0\uc11c \ube44\ub86f\ub418\uba70, \uc5b4\ub5a4 \uc0ac\uc6a9\uc790\ub3c4 \uc790\uc2e0\uc758 \ud6a8\uc6a9\uc744 \\(exp(\\varepsilon)\\) \uc774\uc0c1 \uc0c1\ub300\uc801\uc73c\ub85c \ubcc0\uacbd\ud560 \uc218 \uc5c6\uc74c\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n<p>Chaudhuri et al. [12]\ub294 \\(\\varepsilon\\)<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">2.2 Collusion Resistance<\/h5>\n\n\n\n<p>\ub9ce\uc740 \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\uc740 \ud55c \uac00\uc9c0 \uacb0\ud568\uc744 \uac16\ub294\ub370, \uac1c\ubcc4 \ud50c\ub808\uc774\uc5b4\ub294 \uc790\uc2e0\uc758 \uc774\uc775\uc744 \uc704\ud574 \uac70\uc9d3\ub9d0\uc744 \ud560 \uc720\uc778\uc774 \uc5c6\ub354\ub77c\ub3c4, \uc5ec\ub7ec \ud50c\ub808\uc774\uc5b4\uac00 \uc9d1\ub2e8\uc801\uc73c\ub85c \uacf5\ubaa8(collusion)\ud558\uc5ec \uac01\uc790\uc758 \ud6a8\uc6a9\uc744 \uc0dd\uc131\ud560 \uc218 \uc788\ub2e4. \uc774\ub294 \ucd94\uac00\uc801\uc778 \ubcf4\uc0c1\uc774 \uc5c6\ub294 \uacbd\uc6b0\uc5d0\ub3c4 \ubc1c\uc0dd\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>DP\uc758 \ud55c \uac00\uc9c0 \uc720\ub9ac\ud55c \ud2b9\uc131\uc740 \ub370\uc774\ud130\uc14b\uc5d0\uc11c \ubc1c\uc0dd\ud558\ub294 \ubcc0\ud654\uc758 \ud69f\uc218\uc5d0 \ub530\ub77c \uc810\uc9c4\uc801\uc73c\ub85c \uc131\ub2a5\uc774 \uc800\ud558\ub41c\ub2e4\ub294 \uc810\uc774\ub2e4.<\/p>\n\n\n\n<p>\ud50c\ub808\uc774\uc5b4\ub4e4\uc758 \uc9d1\ub2e8\uc801 \ud6a8\uc6a9\uc774 \ud06c\uac8c \uc99d\uac00\ud558\uc9c0 \uc54a\ub294\ub2e4. \ub530\ub77c\uc11c \ud50c\ub808\uc774\uc5b4\ub4e4 \uac04\uc758 \ucd94\uac00\uc801\uc778 \ubcf4\uc0c1 \ubb38\uc81c\ub294 \uc758\ubbf8\uac00 \uc5c6\uc5b4\uc9c4\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">2.3 Composability<\/h5>\n\n\n\n<p>\ub9ce\uc740 \uba54\ucee4\ub2c8\uc998\uc740 \ubc18\ubcf5 \uc2e4\ud589 \ubb38\uc81c\uac00 \ubc1c\uc0dd\ud558\ub294\ub370, \ucc38\uac00\uc790\ub4e4\uc774 \uc790\uc2e0\uc758 \ud6a8\uc6a9\uc744 \uc65c\uace1\ud558\uc5ec \ucd08\uae30 \ub77c\uc6b4\ub4dc\uc5d0\uc11c \uc720\ub9ac\ud55c \uacb0\uacfc\ub97c \uc720\ub3c4\ud558\uace0, \uc774\ub97c \ud1b5\ud574 \uc774\ud6c4 \ub77c\uc6b4\ub4dc\uc5d0\uc11c \ub354 \ub098\uc740 \uacb0\uacfc\ub97c \uc5bb\uc73c\ub824\ub294 \uc804\ub7b5\uc801 \ud589\ub3d9\uc744 \ud560 \uc218 \uc788\uae30 \ub54c\ubb38\uc774\ub2e4.<br>\uad6c\uccb4\uc801\uc778 \uc608\ub85c, \ub9e4\uc77c \ubc18\ubcf5 \uc2e4\ud589\ub418\ub294 \ubb34\uc81c\ud55c \uacf5\uae09 \uacbd\ub9e4\ub97c \uac00\uc815\ud574 \ubcf4\uc790. \uc601\ub9ac\ud55c \ucc38\uac00\uc790\ub4e4\uc740 \ucc98\uc74c\uc5d0\ub294 \ub0ae\uc740 \uc785\ucc30\uac00(underbid)\ub97c \uc81c\uc2dc\ud558\uc5ec \ucd08\uae30 \uac00\uaca9\uc744 \ub0ae\ucd94\uace0, \uc774\ub97c \ud1b5\ud574 \uc790\uae08\ub825\uc774 \uc788\ub294 \uc785\ucc30\uc790\ub4e4\uc774 \ube60\ub974\uac8c \ud0c8\ub77d\ud558\ub3c4\ub85d \uc720\ub3c4\ud560 \uc218 \uc788\ub2e4. \uadf8 \uacb0\uacfc, \uc774\ud6c4 \ub77c\uc6b4\ub4dc\uc5d0\uc11c\ub294 \uacbd\uc7c1\uc774 \uc904\uc5b4\ub4e4\uc5b4 \ucc38\uac00\uc790\ub4e4\uc774 \ub354 \uc720\ub9ac\ud55c \uac00\uaca9\uc5d0 \uc0c1\ud488\uc744 \uc5bb\uc744 \uac00\ub2a5\uc131\uc774 \ucee4\uc9c4\ub2e4.<\/p>\n\n\n\n<p>\u2192 \ub9e4\uc77c \ubc18\ubcf5\ub418\ub294 \uacbd\ub9e4\uc5d0\uc11c \ucc38\uac00\uc790\uac00 \uc804\ub7b5\uc801\uc73c\ub85c \ud589\ub3d9\ud560 \uc218 \uc788\uc74c<\/p>\n\n\n\n<p>\uc704\uc5d0\uc11c \uc124\uba85\ud55c \uacbd\ub9e4\uc5d0\uc11c, \uac01 \uacbd\ub9e4\uc758 \uba54\ucee4\ub2c8\uc998 \uc778\uc2a4\ud134\uc2a4\uac00 \\(\\varepsilon\\)-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud55c\ub2e4\uace0 \uac00\uc815\ud558\uba74, \ub2e8\uc77c \uc0ac\uc6a9\uc790\uac00 \ud5a5\ud6c4 7\uc77c \ub3d9\uc548\uc758 \uac00\uaca9\uc744 \ucd5c\ub300 \\(exp(7\\varepsilon)\\)\uc758 \ubc94\uc704 \ub0b4\uc5d0\uc11c \uc65c\uace1\ud560 \uc218 \uc788\ub2e4. \uc774\ub294 \uac01 \uba54\ucee4\ub2c8\uc998 \uc778\uc2a4\ud134\uc2a4\uac00 \uc774\uc804 \uc2e4\ud589 \uacb0\uacfc\uc5d0 \ubc18\uc751\ud558\ub294 \uacbd\uc6b0\uc5d0\ub3c4 \uc131\ub9bd\ud558\uba70, \uc608\ub97c \ub4e4\uc5b4 \uc774\ubbf8 \uc0c1\ud488\uc744 \ud68d\ub4dd\ud55c \uc785\ucc30\uc790\ub97c \uacbd\ub9e4\uc5d0\uc11c \uc81c\uc678\ud558\ub294 \ubc29\uc2dd\uc774 \ud574\ub2f9\ub420 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\u2192 \uc989, \uc0ac\uc6a9\uc790\uac00 \ub9e4\uc77c \uc785\ucc30 \uac00\uaca9\uc744 \uc870\uc791\ud558\ub824 \ud574\ub3c4 \uadf8 \uc601\ud5a5\ub825\uc740 \uc9c0\uc218\uc801\uc73c\ub85c \uc81c\ud55c\ub428<br>\u2192 \uacf5\ubaa8 \uc800\ud56d\uc131(Collusion Resistance, Corollary 4)\uc744 \uc801\uc6a9\ud574\uc57c \ud568<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">3. A General Differential Privacy Mechanism<\/h4>\n\n\n\n<p>\ud504\ub77c\uc774\ubc84\uc2dc \uba54\ucee4\ub2c8\uc998\uc758 \ubaa9\ud45c\ub294 \uc785\ub825 \uacf5\uac04 D\uc5d0\uc11c \uc628 n\uac1c\uc758 \uc785\ub825 \uc9d1\ud569\uc744 \ubb34\uc791\uc704\ub85c \ucd9c\ub825 \uacf5\uac04 R\uc758 \uac12\uc73c\ub85c \ubcc0\ud658\ud558\ub294 \uac83\uc774\ub2e4.<br>D\uc640 R\uc758 \uc131\uc9c8\uc5d0 \ub300\ud574 \ud2b9\uc815\ud55c \uac00\uc815\uc744 \ub450\uc9c0 \uc54a\uc73c\uba70, \ucd9c\ub825 \uacf5\uac04 R \uc704\uc5d0\uc11c \uc815\uc758\ub41c \uae30\ubcf8 \uce21\ub3c4(base measure) \\(\\mu\\) \ub9cc\uc744 \uace0\ub824\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc785\ub825 \uacf5\uac04 D (\uac01 \ucc38\uac00\uc790\uc758 \ub370\uc774\ud130) \ubc0f \ucd9c\ub825 \uacf5\uac04 R (\ucd9c\ub825\ub418\ub294 \uac12)\uc5d0\uc11c \ud2b9\uc815 \uc785\ub825 d\uc640 \ud2b9\uc815 \ucd9c\ub825 r\uc758 \uc801\uc808\uc131(\uc810\uc218)\ub97c \ub098\ud0c0\ub0b4\ub294 \uc9c8\uc758 \ud568\uc218(query function): q(d, r)\uc5d0 \ub300\ud574, \uba54\ucee4\ub2c8\uc998\uc758 \ubaa9\ud45c\ub294 q(d, r)\uc758 \uc810\uc218\uac00 \ub192\uc740 \uac12\uc744 \ucd9c\ub825\ud558\uba74\uc11c\ub3c4 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud558\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p>\u2192 \ub9cc\uc57d \uac00\uc7a5 \ub192\uc740 q(d, r) \uac12\uc744 \uac00\uc9c4 r\ub9cc \ucd9c\ub825\ud558\uba74, \uc0ac\uc6a9\uc790\uc758 \ub370\uc774\ud130 d\uac00 \ud2b9\uc815 \uac12\uc774\ub77c\ub294 \uac83\uc774 \uc27d\uac8c \ub4dc\ub7ec\ub09c\ub2e4.<br>\u2192 \uadf8\ub798\uc11c \ucd5c\uc801\uc758 r\uc744 \uc120\ud0dd\ud558\ub294 \uacbd\ud5a5\uc744 \uc720\uc9c0\ud558\uba74\uc11c\ub3c4, \ub2e4\ub978 \uac12\ub4e4\ub3c4 \ucd9c\ub825\ub420 \uac00\ub2a5\uc131\uc744 \ub0a8\uaca8\ub454\ub2e4. (exponential mechanism\uc758 \uc77c\ubc18\ud654\ub41c \ud615\ud0dc)<\/p>\n\n\n\n<p>\uc785\ub825 \ub370\uc774\ud130 d\uac00 \uc870\uae08 \ubcc0\ud558\ub354\ub77c\ub3c4 \ucd9c\ub825 \ud655\ub960 \ubd84\ud3ec\uac00 \ud06c\uac8c \ub2ec\ub77c\uc9c0\uc9c0 \uc54a\ub3c4\ub85d \uc870\uc815\ub418\uc5b4 DP\uac00 \ubcf4\uc7a5<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>\ubcf4\ud1b5 \uade0\ub4f1 \ubd84\ud3ec(uniform distribution)\uc778 \uae30\ubcf8 \uce21\ub3c4 \\(\\mu\\)\uc5d0\uc11c \uc2dc\uc791\ud558\uba70, \uac01 \ucd9c\ub825\uc5d0 \ud560\ub2f9\ub41c \ud655\ub960\uc744 \\(exp(\\varepsilon q(d, r))\\) \ubc30\ub9cc\ud07c \uc99d\ud3ed\ud55c\ub2e4.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"494\" height=\"129\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/02\/image.png\" alt=\"\" class=\"wp-image-4749\" srcset=\"https:\/\/saraheee.com\/wp-content\/uploads\/2025\/02\/image.png 494w, https:\/\/saraheee.com\/wp-content\/uploads\/2025\/02\/image-300x78.png 300w\" sizes=\"(max-width: 494px) 100vw, 494px\" \/><\/figure>\n\n\n\n<p>\uc989, \ucd9c\ub825 \ud655\ub960\uc740 \uae30\ubcf8 \ubd84\ud3ec \\(\\mu(r)\\)\uc5d0 \ube44\ub840\ud558\uba74\uc11c\ub3c4, \\(q(d, r)\\) \uac12\uc774 \ud074\uc218\ub85d \ub354\uc6b1 \ub192\uc740 \ud655\ub960\ub85c \uc120\ud0dd\ub41c\ub2e4. \uc774\ub294 laplace mechanism\uc774\ub098 exponential mechanism\uc758 \uc77c\ubc18\ud654\ub41c \ud615\ud0dc\ub85c \ubcfc \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc9c1\uad00\uc801\uc73c\ub85c \ubcf4\uba74, q(d, r) \uac12\uc774 \uc18c\ud3ed \ubcc0\uacbd\ub418\ub294 \uac83(\uc608: \ub2e8\uc77c \ucc38\uac00\uc790\uc758 \ub370\uc774\ud130 \ubcc0\uacbd\uc73c\ub85c \uc778\ud574 \ubc1c\uc0dd)\uc774 \ucd9c\ub825 \ud655\ub960 \ubc00\ub3c4\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc740 \uacf1\uc148\uc801\uc73c\ub85c \uc81c\ud55c\ub418\ubbc0\ub85c DP\uac00 \ubcf4\uc7a5\ub41c\ub2e4.<br>\uc989, \ud55c \uba85\uc758 \ucc38\uac00\uc790\uac00 \ub370\uc774\ud130\ub97c \uc0b4\uc9dd \ubcc0\uacbd\ud55c\ub2e4\uace0 \ud574\ub3c4 \uc804\uccb4 \ucd9c\ub825 \ubd84\ud3ec\uac00 \uae09\uaca9\ud558\uac8c \ubcc0\ud558\uc9c0 \uc54a\uc73c\ubbc0\ub85c \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \ud6a8\uacfc\uac00 \uc788\ub2e4.<\/p>\n\n\n\n<p>Remark: <\/p>\n\n\n\n<p>\uc774 \uc801\ubd84\uac12\uc774 \uc720\ud55c\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\\(\\int_{r} \\exp(\\epsilon q(d,r)) \\mu(r) \\, dr\\)<\/p>\n\n\n\n<p>\ubcf8 \ub17c\ubb38\uc5d0\uc11c q \uac12\uc774 \ud56d\uc0c1 n \uc774\ud558\ub85c \uc81c\ud55c\ub428\uc744 \uac00\uc815\ud558\ubbc0\ub85c, \uc704 \uc801\ubd84\uac12\ub3c4 \\(exp(\\epsilon n)\\)\uc73c\ub85c \uc81c\ud55c\ub41c\ub2e4.<\/p>\n\n\n\n<p>Remark:<\/p>\n\n\n\n<p>\uae30\uc874 \uc5f0\uad6c [15, 14]\uc5d0\uc11c\ub294 \ub77c\ud50c\ub77c\uc2a4 \ub178\uc774\uc988\ub97c \ud568\uc218 \\(f: D^n \\to R\\)\uc758 \uacb0\uacfc\uac12\uc5d0 \ucd94\uac00\ud558\ub294 \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud588\ub294\ub370, \uc774\ub97c \uc77c\ubc18\uc801\uc778 DP \uba54\ucee4\ub2c8\uc998\uc73c\ub85c \ud574\uc11d\ud558\uba74 q(d, r) = -|f(d) &#8211; r|\ub85c \ubcfc \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\u2192 \uc989, \uae30\uc874 \ub77c\ud50c\ub77c\uc2a4 \uba54\ucee4\ub2c8\uc998\uc740 \ucd9c\ub825 r\uc774 f(d)\uc640 \uac00\uae4c\uc6b8\uc218\ub85d \ud655\ub960\uc774 \ub192\uc544\uc9c0\ub3c4\ub85d \uc870\uc815\ub41c \uacbd\uc6b0\ub85c \ud574\uc11d \uac00\ub2a5<br>\uc774 \ub17c\ubb38\uc758 \uc77c\ubc18\uc801\uc778 \uba54\ucee4\ub2c8\uc998\ub3c4 \ub3d9\uc77c\ud55c \ubc29\uc2dd\uc73c\ub85c \uae30\uc874\uc758 \ub77c\ud50c\ub77c\uc2a4 \uba54\ucee4\ub2c8\uc998\uc744 \ud3ec\ud568\ud560 \uc218 \uc788\uc74c<\/p>\n\n\n\n<p>\ub3c4\uc785\ubd80\uc5d0\uc11c \uc5b8\uae09\ub41c \ub2e8\uc704 \uc218\uc694(unit demand) \uacbd\ub9e4 \uc124\uc815\uacfc \uac19\uc740 \uba87\uba87 \uacbd\uc6b0\uc5d0\uc11c\ub294, \\(\\exp(\\epsilon q(d,r))\\mu(r)\\) \uac12\uc774 \ubcc0\uacbd\ub418\uba74, \uc815\uaddc\ud654 \uacc4\uc218(normalization factor)\ub3c4 \uac19\uc740 \ubc29\ud5a5(\uc99d\uac00\/\uac10\uc18c)\uc73c\ub85c \ubcc0\uacbd\ub420 \uc218\ubc16\uc5d0 \uc5c6\ub2e4.<br>\uc774\ub85c \uc778\ud574, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc758 \ubcf4\uc7a5 \uc218\uc900\uc774 \ub354\uc6b1 \uac15\ud654\ub420 \uc218 \uc788\uc73c\uba70, \\((2\\epsilon \\Delta q)\\)-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc5d0\uc11c \\((\\epsilon \\Delta q)\\)-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub85c \uc0c1\ud55c\uc774 \uac10\uc18c\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">5. Conclusions and Future Research<\/h4>\n\n\n\n<p>\uc6b0\ub9ac\ub294 \ub367\uc148\uc801 \ub178\uc774\uc988(additive noise)\uc5d0 \ub300\ud574 \uac15\uac74\ud558\uc9c0 \uc54a\uac70\ub098, \ucd9c\ub825\uc774 \uad50\ub780(perturbation)\uc744 \ud5c8\uc6a9\ud558\uc9c0 \uc54a\ub294 \ud568\uc218\uc5d0\ub3c4 \uc801\uc6a9 \uac00\ub2a5\ud55c \uc0c8\ub85c\uc6b4 \uc77c\ubc18\uc801\uc778 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc548\ud558\uc600\ub2e4. \uc774 \uba54\ucee4\ub2c8\uc998\uc740 \ucd9c\ub825\uc758 \ud488\uc9c8(quality)\uc744 \ubcf4\uc7a5\ud558\ub294 \ud2b9\uc131\uc744 \uac16\ub294\ub2e4.<br>\uc774 \uba54\ucee4\ub2c8\uc998\uc740 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud558\uba74\uc11c\ub3c4 \uae30\ubcf8 \ud655\ub960 \ubd84\ud3ec(base measure)\ub97c \uac00\ub2a5\ud55c \ud55c \ucd5c\ub300\ub85c \uc65c\uace1(skew) \ud558\uc5ec, \uac00\uc7a5 \ub192\uc740 \uac00\uce58(value)\ub97c \uac00\uc9c0\ub294 \ucd9c\ub825\uc774 \uc120\ud0dd\ub420 \uac00\ub2a5\uc131\uc744 \ub192\uc778\ub2e4.<br>\ub9c8\uc9c0\ub9c9\uc73c\ub85c, \uc6b0\ub9ac\ub294 \uc774 \uc77c\ubc18\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 \uc5ec\ub7ec \uacbd\ub9e4 \ubb38\uc81c(auction problems)\uc5d0 \uc801\uc6a9\ud558\uc600\uc73c\uba70, \ucd5c\uc801 \uc218\uc775(optimal revenue)\uc5d0 \ub300\ud574 \ub85c\uadf8(logarithmic) \ucc28\uc774 \uc774\ub0b4\uc758 \uc218\uc775\uc744 \uc81c\uacf5\ud568\uc744 \ud655\uc778\ud558\uc600\ub2e4.<br>\uc6b0\ub9ac\ub294 \uae30\uc874 \uc5f0\uad6c(\uc608: [6])\uc640 \ub2ec\ub9ac, \ubcf8 \ub17c\ubb38\uc5d0\uc11c \uc81c\uc548\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc5c4\uaca9\ud55c \uc9c4\uc2e4\uc131(strict truthfulness)\uc744 \ubcf4\uc7a5\ud558\uc9c0 \uc54a\ub294\ub2e4\ub294 \uc810\uc744 \uac15\uc870\ud55c\ub2e4.<br>\ubc18\uba74, \uc6b0\ub9ac\ub294 \uae30\uc874 \uc5f0\uad6c([6] \ub4f1)\uac00 \uc720\uc9c0\ud560 \uc218 \uc5c6\ub294 \uac15\ud55c \uad6c\uc870\uc801 \uc81c\uc57d(hard structural constraints) \uc18d\uc5d0\uc11c\ub3c4 \uc801\uc6a9 \uac00\ub2a5\ud55c \uc5ec\ub7ec \uc81c\ud55c\ub41c \uac00\uaca9 \uc124\uc815(constrained pricing settings)\uc744 \uc81c\uc2dc\ud558\uc600\ub2e4.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>\u2192 DP \uba54\ucee4\ub2c8\uc998\uc740 \uc644\uc804\ud55c \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud558\uc9c0\ub294 \uc54a\uc9c0\ub9cc, \uadfc\uc0ac\uc801 \uc9c4\uc2e4\uc131\uc744 \ub9cc\uc871\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uadfc\uc0ac\uc801 \uc9c4\uc2e4\uc131(Approximate Truthfulness) \uc774\ub780, \ucc38\uac00\uc790\uac00 \uc790\uc2e0\uc758 \uc785\ub825\uc744 \uc870\uc791\ud558\ub354\ub77c\ub3c4 \uc5bb\uc744 \uc218 \uc788\ub294 \uc774\uc775\uc774 \ub9e4\uc6b0 \uc791\uc544 \uc804\ub7b5\uc801 \uc870\uc791\uc774 \ube44\ud6a8\uc728\uc801\uc774 \ub418\ub294 \uc0c1\ud0dc\ub97c \uc758\ubbf8\ud55c\ub2e4.<br>\uc989, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \uba54\ucee4\ub2c8\uc998\uc774 \ucc38\uac00\uc790\uc758 \uc120\ud0dd\uc5d0 \ub300\ud574 \ub2e4\uc74c\uacfc \uac19\uc740 \uc131\uc9c8\uc744 \ubcf4\uc7a5\ud574\uc57c \ud55c\ub2e4.<br>\u2022 \uc0ac\uc6a9\uc790\uac00 \uc785\ub825\uc744 \uc870\uc791(\uac70\uc9d3 \ubcf4\uace0) \ud558\ub354\ub77c\ub3c4 \uae30\ub300 \ud6a8\uc6a9(utility)\uc774 \uac70\uc758 \ubcc0\ud558\uc9c0 \uc54a\uc74c.<br>\u2022 \uac70\uc9d3 \ubcf4\uace0\ub85c \uc778\ud55c \uc774\uc775\uc774&nbsp; \\epsilon&nbsp; \uc5d0 \uc758\ud574 \uc81c\uc5b4\ub418\uba70, \uc9c0\uc218\uc801\uc73c\ub85c \uac10\uc18c\ud568.<br>\u2022 \uacb0\uacfc\uc801\uc73c\ub85c, \ucc38\uac00\uc790\uac00 \uc9c4\uc2e4\ud558\uac8c \uc790\uc2e0\uc758 \uac12\uc744 \ubcf4\uace0\ud558\ub294 \uac83\uc774 \ucd5c\uc801\uc758 \uc120\ud0dd\uc5d0 \uac00\uae4c\uc6c0.<\/p>\n\n\n\n<p>DP\uc758 \uc815\uc758\uc5d0 \uc758\ud574, \ud55c \uba85\uc758 \uc0ac\uc6a9\uc790\uac00 \uc790\uc2e0\uc758 \ub370\uc774\ud130\ub97c \ubcc0\uacbd\ud558\ub354\ub77c\ub3c4 \ucd9c\ub825 \ud655\ub960 \ubd84\ud3ec\uac00 \uae09\uaca9\ud558\uac8c \ubcc0\ud558\uc9c0 \uc54a\ub3c4\ub85d \uc81c\ud55c\ub41c\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">References<\/h5>\n\n\n\n<p>McSherry, Frank, and Kunal Talwar. &#8220;Mechanism design via differential privacy.&#8221;&nbsp;<em>48th Annual IEEE Symposium on Foundations of Computer Science (FOCS&#8217;07)<\/em>. IEEE, 2007.<\/p>\n\n\n\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>This paper explores the role of privacy-preserving algorithms in mechanism design, specifically using differential privacy to ensure that participants have limited effect on the outcome of the mechanism and limited incentive to lie.<\/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,200,198],"class_list":["post-4710","post","type-post","status-publish","format-standard","hentry","category-paper-review","tag-differential-privacy","tag-feb-11-2025","tag-mechanism"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4710"}],"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=4710"}],"version-history":[{"count":85,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4710\/revisions"}],"predecessor-version":[{"id":5207,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4710\/revisions\/5207"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=4710"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=4710"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=4710"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}