{"id":4918,"date":"2025-03-10T00:00:58","date_gmt":"2025-03-09T15:00:58","guid":{"rendered":"https:\/\/saraheee.com\/?p=4918"},"modified":"2025-03-21T23:22:17","modified_gmt":"2025-03-21T14:22:17","slug":"review19-truthful-mechanisms-for-agents-that-value-privacy","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2025\/03\/review19-truthful-mechanisms-for-agents-that-value-privacy\/","title":{"rendered":"[review#19] Truthful mechanisms for agents that value privacy_Chen et al, 2016"},"content":{"rendered":"<h3 class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>\ucd5c\uadfc \uc5f0\uad6c\uc5d0\uc11c\ub294 \uc9c4\uc2e4\uc131\uacfc \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ub3d9\uc2dc\uc5d0 \ubcf4\uc7a5\ud558\ub294 \uacbd\uc81c\uc801 \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud588\ub2e4. \uc774\ub7ec\ud55c \uba54\ucee4\ub2c8\uc998\uc5d0\uc11c\ub294 \ud504\ub77c\uc774\ubc84\uc2dc\uac00 \uc9c4\uc2e4\uc131\uacfc \ubcc4\uac1c\ub85c \ucde8\uae09\ub418\uba70, \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud568\uc218\uc5d0 \ud3ec\ud568\ub418\uc9c0 \uc54a\ub294\ub2e4(\uadf8\ub9ac\uace0 \uc774\ub97c \ud3ec\ud568\ud560 \uacbd\uc6b0 \uc77c\ubd80 \uacbd\uc6b0\uc5d0\uc11c \ube44\uc9c4\uc2e4\uc131\uc774 \ubc1c\uc0dd\ud558\ub294 \uac83\uc73c\ub85c \ub098\ud0c0\ub0ac\ub2e4). \ubcf8 \uc5f0\uad6c\uc5d0\uc11c\ub294 \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud568\uc218\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubaa8\ub378\ub9c1\ud558\ub294 \uc0c8\ub85c\uc6b4 \uc77c\ubc18\uc801\uc778 \ubc29\ubc95\uc744 \uc81c\uc548\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uad6c\uccb4\uc801\uc73c\ub85c, \uc5b4\ub5a4 \uacb0\uacfc o \uac00 \ud50c\ub808\uc774\uc5b4 i \uc758 \ubaa8\ub4e0 \ubcf4\uace0 \uac12\uc5d0\uc11c \uac70\uc758 \ub3d9\uc77c\ud55c \ud655\ub960\ub85c \ub3c4\ucd9c\ub41c\ub2e4\uba74, \ud574\ub2f9 \uacb0\uacfc o \ub294 \ud50c\ub808\uc774\uc5b4 i \uc5d0\uac8c \uc791\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \uac00\uc9c4\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4. \uc6b0\ub9ac\ub294 \uc774\ub7ec\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubaa8\ub378\ub9c1\uc5d0 \ub300\ud574 \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud558\ub294 \uc138 \uac00\uc9c0 \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n<p>1. \ub450 \ud6c4\ubcf4 \uac04\uc758 \uc120\uac70(Election between two candidates)<br>2. \uc774\uc0b0\uc801\uc778 \uc2dc\uc124 \uc704\uce58 \uc120\uc815 \ubb38\uc81c(Discrete version of the facility location problem)<br>3. \uc774\uc0b0\uc801 \ud6a8\uc6a9\uc744 \uac00\uc9c4 \uc77c\ubc18\uc801\uc778 \uc0ac\ud68c\uc801 \uc120\ud0dd \ubb38\uc81c(General social choice problem with discrete utilities, VCG\uc640 \uc720\uc0ac\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uc0ac\uc6a9)<\/p>\n\n\n\n<p>\ub610\ud55c, \ud50c\ub808\uc774\uc5b4 \uc218 n \uc774 \uc99d\uac00\ud568\uc5d0 \ub530\ub77c, \uc6b0\ub9ac\uc758 \uba54\ucee4\ub2c8\uc998\uc774 \ub2ec\uc131\ud558\ub294 \uc0ac\ud68c\uc801 \ud6c4\uc0dd(social welfare)\uc774 \ucd5c\uc801\uac12\uc5d0 \uc810\uc9c4\uc801\uc73c\ub85c \uc218\ub834\ud55c\ub2e4(n \uc758 \ube44\uc728\ub85c \ucd5c\uc801\uc5d0 \uc811\uadfc\ud568).<\/p>\n\n\n\n<h6 class=\"wp-block-heading\">Additional Key Words and Phrases: Differential privacy, mechanism design, truthfulness, social choice, VCG<\/h6>\n\n\n\n<h3 class=\"wp-block-heading\">1. Introduction<\/h3>\n\n\n\n<p>\uc774 \ub17c\ubb38\uc5d0\uc11c\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4(mechanism design)\uc640 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(differential privacy) \uac04\uc758 \uc0c1\ud638\uc791\uc6a9\uc744 \ubd84\uc11d\ud55c\ub2e4. \ud2b9\ud788, \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud568\uc218(utility function)\uc5d0 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uba85\uc2dc\uc801\uc73c\ub85c \ud3ec\ud568\ud558\uace0, \uc774\ub97c \uace0\ub824\ud55c \uc9c4\uc2e4\ud55c(truthful) \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud558\ub294 \uac83\uc774 \ubaa9\ud45c\ub2e4.<br>\uc6b0\ub9ac\uc758 \uc5f0\uad6c\ub294 \ub450 \uac00\uc9c0 \ubd84\uc57c\uc758 \ub3d9\uae30\uc5d0\uc11c \ucd9c\ubc1c\ud55c\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">1. \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0\uc11c\uc758 \ubb38\uc81c\uc810:<\/h5>\n\n\n\n<p>\uae30\uc874 \uc5f0\uad6c\uc5d0\uc11c\ub294 \ud50c\ub808\uc774\uc5b4\uac00 \ub2e8\uc21c\ud788 \uacb0\uacfc(\uc608: \uacbd\ub9e4\uc5d0\uc11c \ub204\uac00 \ub099\ucc30\ub418\ub294\uc9c0, \ubcd1\uc6d0\uc774 \uc5b4\ub514\uc5d0 \uc704\uce58\ud558\ub294\uc9c0)\uc5d0 \ub300\ud574\uc11c\ub9cc \uc120\ud638\ub97c \uac00\uc9c4\ub2e4\uace0 \uac00\uc815\ud588\ub2e4. \uadf8\ub7ec\ub098 \uc2e4\uc81c\ub85c\ub294 \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \uac1c\uc778 \uc815\ubcf4\uac00 \ud0c0\uc778\uc5d0\uac8c \ub178\ucd9c\ub418\ub294 \uac83 \uc790\uccb4\ub97c \uc6b0\ub824\ud558\uc5ec \uae30\uc874\uc758 \uacbd\uc81c\uc801 \ubd84\uc11d\uacfc \ub2e4\ub974\uac8c \ud589\ub3d9\ud560 \uac00\ub2a5\uc131\uc774 \uc788\ub2e4.<br>\uc608\ub97c \ub4e4\uc5b4, \uc5b4\ub5a4 \uc0ac\ub78c\uc774 \uacbd\ub9e4\uc5d0\uc11c \ud2b9\uc815 \uc0c1\ud488\uc5d0 \ub300\ud55c \ub192\uc740 \uac00\uce58\ub97c \ubcf4\uace0\ud558\uba74, \uadf8 \uc0ac\ub78c\uc758 \uc120\ud638\ub3c4\uac00 \ub178\ucd9c\ub420 \uc218 \uc788\uc73c\uba70, \ubcd1\uc6d0 \uc704\uce58\uc5d0 \ubbfc\uac10\ud55c \uc0ac\ub78c\uc740 \uc790\uc2e0\uc758 \uc758\ub8cc \uc0c1\ud0dc\ub97c \uac04\uc811\uc801\uc73c\ub85c \ub4dc\ub7ec\ub0bc \uc704\ud5d8\uc774 \uc788\ub2e4.<br>\uae30\uc874\uc758 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4 \uc5f0\uad6c\ub4e4\uc740 \uc774\ub7ec\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubb38\uc81c\ub97c \uc81c\ub300\ub85c \ubaa8\ub378\ub9c1\ud558\uc9c0 \uc54a\uc558\uae30 \ub54c\ubb38\uc5d0, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ud65c\uc6a9\ud55c \uc0c8\ub85c\uc6b4 \uc811\uadfc \ubc29\uc2dd\uc774 \ud544\uc694\ud558\ub2e4.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">2. \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc758 \ud544\uc694\uc131:<\/h5>\n\n\n\n<p>\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(Dwork et al. 2006)\ub294 \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc758 \ud1b5\uacc4 \ubd84\uc11d \uc2dc \uac1c\ubcc4 \ucc38\uc5ec\uc790\uc758 \ub370\uc774\ud130\uac00 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \uc81c\ud55c\ud558\ub294 \uac1c\ub150\uc774\ub2e4. \uc989, \ub2e8\uc77c \uac1c\uc778\uc758 \ub370\uc774\ud130\uac00 \ubcc0\uacbd\ub418\uc5b4\ub3c4 \uc54c\uace0\ub9ac\uc998\uc758 \ucd9c\ub825 \ubd84\ud3ec\uac00 \ud06c\uac8c \ubcc0\ud558\uc9c0 \uc54a\ub294\ub2e4\uba74, \ud574\ub2f9 \uc54c\uace0\ub9ac\uc998\uc740 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ub9cc\uc871\ud55c\ub2e4\uace0 \ubcfc \uc218 \uc788\ub2e4.<br>\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub294 \uc808\ub300\uc801\uc778 \uac1c\ub150\uc774 \uc544\ub2c8\ub77c \uac1c\uc778\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uc218\uc900\uacfc \uc804\uccb4 \ud1b5\uacc4\uc801 \uc815\ud655\uc131 \uac04\uc758 \ud2b8\ub808\uc774\ub4dc\uc624\ud504\ub97c \uc870\uc815\ud558\ub294 \ubc29\uc2dd\uc774\ub2e4. \ud558\uc9c0\ub9cc \uae30\uc874 \uc5f0\uad6c\ub294 \uac1c\uc778\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638\uac00 \uadf8 \uac1c\uc778\uc758 \ubaa9\ud45c(\uc608: \ud6a8\uc6a9 \uadf9\ub300\ud654)\uc640 \uc5b4\ub5bb\uac8c \uc870\ud654\ub420 \uc218 \uc788\ub294\uc9c0\uc5d0 \ub300\ud55c \ub17c\uc758\uac00 \ubd80\uc871\ud588\ub2e4.<\/p>\n\n\n\n<p>\uc774\ub7ec\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574, \uc6b0\ub9ac\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc640 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uacb0\ud569\ud558\uc5ec \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638\uc640 \uac1c\uc778\uc758 \uacbd\uc81c\uc801 \ubaa9\ud45c \uac04\uc758 \uade0\ud615\uc744 \uace0\ub824\ud558\ub294 \uc0c8\ub85c\uc6b4 \ubaa8\ub378\uc744 \uc81c\uc548\ud55c\ub2e4. \uc774\ub97c \ud1b5\ud574 \ud504\ub77c\uc774\ubc84\uc2dc\uc758 \uc758\ubbf8\uc640 \uac00\uce58\ub97c \ubcf4\ub2e4 \uae4a\uc774 \uc774\ud574\ud560 \uc218 \uc788\uc744 \uac83\uc73c\ub85c \uae30\ub300\ud55c\ub2e4.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">1.1. Previous Work<\/h4>\n\n\n\n<p><\/p>\n\n\n\n<h4 class=\"wp-block-heading\">1.2. Our Contributions<\/h4>\n\n\n\n<p>\uc774 \ub17c\ubb38\uc5d0\uc11c \uc6b0\ub9ac\ub294 \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud568\uc218\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubaa8\ub378\ub9c1\ud558\ub294 \uc0c8\ub85c\uc6b4, \ubcf4\ub2e4 \uc77c\ubc18\uc801\uc778 \ubc29\ubc95\uc744 \uc81c\uc548\ud55c\ub2e4. Xiao\uc758 \uc0c1\ud638 \uc815\ubcf4(mutual information) \uce21\uc815 \ubc29\uc2dd\uacfc \ub2ec\ub9ac, \uc6b0\ub9ac\uc758 \ubaa8\ub378\uc740 \ud50c\ub808\uc774\uc5b4 \uc720\ud615(type)\uc5d0 \ub300\ud55c \uc0ac\uc804 \ud655\ub960(prior)\uc744 \uac00\uc815\ud560 \ud544\uc694\uac00 \uc5c6\uc73c\uba70, \uc810\ubcc4(pointwise) \ubaa8\ub378\uc774\ub2e4. \uc989, \uc6b0\ub9ac\ub294 \ub2e8\uc21c\ud788 \uc5b4\ub5a4 \uacb0\uacfc o \uac00 \ud50c\ub808\uc774\uc5b4 i \uc758 \ubaa8\ub4e0 \ubcf4\uace0\uc5d0\uc11c \uac70\uc758 \ub3d9\uc77c\ud55c \ud655\ub960\ub85c \ub3c4\ucd9c\ub41c\ub2e4\uba74, \ud574\ub2f9 \uacb0\uacfc o \ub294 \ud50c\ub808\uc774\uc5b4 i \uc5d0\uac8c \uc791\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \uac00\uc9c4\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4.<\/p>\n\n\n\n<p>\uc774 \uac00\uc815\uc744 \uc124\uc815\ud55c \ub3d9\uae30 \uc911 \ud558\ub098\ub294, \uc774\ub7ec\ud55c \uacb0\uacfc o \uac00 Bayesian \uc801\ub300\uc790\uac00(\uc989, \ubca0\uc774\uc9c0\uc548 \ubaa8\ub378\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud50c\ub808\uc774\uc5b4\uc758 \uc815\ubcf4\ub97c \ucd94\ub860\ud558\ub824\ub294 \uc874\uc7ac) \ud50c\ub808\uc774\uc5b4 i \uc5d0 \ub300\ud55c \uc2e0\ub150\uc744 \uac70\uc758 \ubcc0\ud654\uc2dc\ud0a4\uc9c0 \uc54a\uc744 \uac83\uc774\uae30 \ub54c\ubb38\uc774\ub2e4(\ub2e4\ub978 \ud50c\ub808\uc774\uc5b4\ub4e4\uc758 \ubcf4\uace0\ub97c \uace0\ub824\ud588\uc744 \ub54c). \uc774 \uac00\uc815\uc740 Dwork\uc640 McSherry\uc758 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc5d0 \ub300\ud55c Bayesian \ud574\uc11d\uc5d0\uc11c \uc601\uac10\uc744 \uc5bb\uc5c8\uc73c\uba70, Kasiviswanathan\uacfc Smith [2008]\uc5d0\uc11c \uc124\uba85\ub418\uc5c8\ub2e4.<\/p>\n\n\n\n<p>Xiao\uc758 \uc0c1\ud638 \uc815\ubcf4 \uce21\uc815 \ubc29\uc2dd\uc740 \uc5c4\ubc00\ud788 \ub9d0\ud574 \uc6b0\ub9ac\uc758 \ubaa8\ub378\uc758 \ud2b9\uc218\ud55c \uacbd\uc6b0\ub294 \uc544\ub2c8\uc9c0\ub9cc, \ubd80\ub85d\uc5d0\uc11c \uc6b0\ub9ac\ub294 \uc6b0\ub9ac\uc758 \ubaa8\ub378\uc5d0 \ub300\ud55c \uc9c4\uc2e4\uc131\uc774 Xiao\uc758 \ubaa8\ub378\uc5d0 \ub300\ud55c \uc9c4\uc2e4\uc131\uc744 \ud568\uc758\ud568\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n<p>\uc774 \ubaa8\ub378\uc744 \ubc14\ud0d5\uc73c\ub85c, \uc6b0\ub9ac\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc774 \uc9c4\uc2e4\ud55c \uc751\ub2f5\uc73c\ub85c \uc778\ud55c \uacb0\uacfc \ud6a8\uc6a9(outcome-utility) \uc774\ub4dd\ubcf4\ub2e4 \uc791\uc740 \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778\ub2e4. \uad6c\uccb4\uc801\uc73c\ub85c, \uc6b0\ub9ac\ub294 \uc6b0\ub9ac\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ubaa8\ub378\uc5d0 \ub300\ud574 \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud558\ub294 \uc138 \uac00\uc9c0 \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n<p>1. \ub450 \ud6c4\ubcf4 \uac04\uc758 \uc120\uac70(election between two candidates)<br>2. \uc774\uc0b0\uc801\uc778 \uc2dc\uc124 \uc704\uce58 \uc120\uc815 \ubb38\uc81c(discrete version of the facility location problem)<br>3. \uc774\uc0b0\uc801 \ud6a8\uc6a9\uc744 \uac00\uc9c4 \uc77c\ubc18\uc801\uc778 \uc0ac\ud68c\uc801 \uc120\ud0dd \ubb38\uc81c(general social choice problems with discrete utilities, VCG\uc640 \uc720\uc0ac\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uc0ac\uc6a9)<\/p>\n\n\n\n<p>\ub610\ud55c, \ud50c\ub808\uc774\uc5b4 \uc218 n \uc774 \uc99d\uac00\ud568\uc5d0 \ub530\ub77c, \uc6b0\ub9ac\uc758 \uba54\ucee4\ub2c8\uc998\uc774 \ub2ec\uc131\ud558\ub294 \uc0ac\ud68c\uc801 \ud6c4\uc0dd(social welfare)\uc774 \ucd5c\uc801\uac12\uc5d0 \uc810\uc9c4\uc801\uc73c\ub85c \uc218\ub834\ud55c\ub2e4(n \uc758 \ube44\uc728\ub85c \ucd5c\uc801\uc5d0 \uc811\uadfc).<\/p>\n\n\n\n<p>\uc6b0\ub9ac\uc758 \uc544\uc774\ub514\uc5b4\ub97c \uc124\uba85\ud558\uae30 \uc704\ud574, \ub450 \ud6c4\ubcf4 \uac04\uc758 \uc120\uac70\ub97c \uace0\ub824\ud558\uc790. \uac01 \ud50c\ub808\uc774\uc5b4\ub294 \ud55c \ud6c4\ubcf4\uc5d0 \ub300\ud574 \ub69c\ub837\ud55c \uc120\ud638\ub97c \uac00\uc9c0\uace0 \uc788\uc9c0\ub9cc, \ud504\ub77c\uc774\ubc84\uc2dc \ubb38\uc81c\ub85c \uc778\ud574 \uc120\ud638\ub97c \uacf5\uac1c\ud558\ub294 \uac83\uc744 \uc8fc\uc800\ud560 \uc218\ub3c4 \uc788\ub2e4. \uc774\ub7ec\ud55c \uc120\uac70\ub97c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc720\uc9c0\ud558\uba74\uc11c \uc218\ud589\ud558\ub824\uba74, \uc6b0\ub9ac\ub294 \ub178\uc774\uc988\ub97c \ucd94\uac00\ud55c \ub2e4\uc218\uacb0 \ubc29\uc2dd(noisy majority vote)\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\ub2e4. \uc989,<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uac01 \ud22c\ud45c\uc790\uc758 \uc120\ud0dd\uc744 \uae30\ubc18\uc73c\ub85c \ub2e4\uc218\uacb0 \uaddc\uce59\uc744 \uc801\uc6a9\ud558\ub418,<\/li>\n\n\n\n<li>\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \ud30c\ub77c\ubbf8\ud130 \\(\\epsilon\\) \uc5d0 \ub530\ub77c \ud06c\uae30\uac00 \\(O(1\/\\epsilon)\\) \uc778 \ub79c\ub364 \ub178\uc774\uc988\ub97c \ucd94\uac00\ud55c\ub2e4.<\/li>\n\n\n\n<li>\uc5ec\uae30\uc11c \\(\\epsilon\\) \uc740 \uac01 \ud50c\ub808\uc774\uc5b4\uc758 \ud22c\ud45c\uac00 \ucd5c\uc885 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \uc81c\ud55c\ud558\ub294 \uc5ed\ud560\uc744 \ud55c\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p>\uc774\uc81c \\(\\epsilon\\) \uc744 \uc904\uc774\uba74, \ud50c\ub808\uc774\uc5b4\uac00 \uacbd\ud5d8\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\ub3c4 \uc904\uc5b4\ub4e0\ub2e4. \ud558\uc9c0\ub9cc \ub2e8\uc21c\ud788 \\(\\epsilon\\) \uc5d0 \uc758\ud574 \uc804\uccb4 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \uc81c\ud55c\ud558\ub294 \uac83\ub9cc\uc73c\ub85c\ub294 \uc120\uac70 \uba54\ucee4\ub2c8\uc998\uc758 \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud560 \uc218 \uc5c6\ub2e4.<\/p>\n\n\n\n<p>\uc608\ub97c \ub4e4\uc5b4, \ud55c \ud6c4\ubcf4\uac00 \uc804\uccb4 \uc720\uad8c\uc790\uc758 2\/3\uc758 \uc9c0\uc9c0\ub97c \ubc1b\ub294 \ud3b8\ud5a5\ub41c(skewed) \uc120\uac70\ub97c \uace0\ub824\ud574\ubcf4\uc790.<br>\uc774 \uacbd\uc6b0, \ub2e8\uc77c \ud50c\ub808\uc774\uc5b4\uc758 \ud22c\ud45c\uac00 \uacb0\uacfc\ub97c \ubc14\uafc0 \ud655\ub960\uc740 \\(e^{-\\epsilon n}\\) \uc5d0 \ube44\ub840\ud558\uc5ec \uae30\ud558\uae09\uc218\uc801\uc73c\ub85c \uc791\uc544\uc9c4\ub2e4(\uc5ec\uae30\uc11c n \uc740 \uc720\uad8c\uc790 \uc218).<br>\ub9cc\uc57d \ud50c\ub808\uc774\uc5b4\uc758 \uc804\uccb4 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc774 \\(O(\\epsilon)\\) \uae4c\uc9c0 \uc99d\uac00\ud560 \uc218 \uc788\ub2e4\uba74, \\(\\epsilon\\) \uc744 \ub9e4\uc6b0 \uc791\uac8c \uc124\uc815\ud574\uc57c \ud558\uba70, \uc774\ub294 \\(O(1\/n)\\) \uc218\uc900\uae4c\uc9c0 \uc791\uc544\uc9c8 \uc218 \uc788\ub2e4.<br>\uadf8\ub7ec\ub098 \\(\\epsilon\\) \uc774 \ub108\ubb34 \uc791\uc544\uc9c0\uba74, \uacfc\ub3c4\ud55c \ub178\uc774\uc988\uac00 \ucd94\uac00\ub418\uc5b4 \uc0ac\ud68c\uc801 \ud6c4\uc0dd\uc774 \uc2ec\uac01\ud558\uac8c \ud76c\uc0dd\ub41c\ub2e4.<\/p>\n\n\n\n<p>\uc6b0\ub9ac\ub294 \ud3b8\ud5a5\ub41c \uc120\uac70\uc5d0\uc11c \uc9c4\uc2e4\ud55c \uc751\ub2f5\uc758 \uc804\uccb4 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9 \uc5ed\uc2dc \uae30\ud558\uae09\uc218\uc801\uc73c\ub85c \uc791\uc544\uc838\uc57c \ud55c\ub2e4\uace0 \uc8fc\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n<p>\ub300\ubd80\ubd84\uc758 \ub79c\ub364 \ub178\uc774\uc988 \uc124\uc815\uc5d0\uc11c\ub294 \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \ubcf4\uace0\ub97c \ubcc0\uacbd\ud574\ub3c4 \uacb0\uacfc\uc5d0 \uc601\ud5a5\uc744 \ubbf8\uce60 \uc218 \uc5c6\ub2e4.<br>\ub530\ub77c\uc11c \ud50c\ub808\uc774\uc5b4\uac00 \uc9c4\uc2e4\ud558\uac8c \ubcf4\uace0\ud558\ub4e0 \uac70\uc9d3\uc73c\ub85c \ubcf4\uace0\ud558\ub4e0, \uacbd\ud5d8\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc740 \ub3d9\uc77c\ud574\uc57c \ud55c\ub2e4.<br>\uacb0\uacfc\uc5d0 \uc601\ud5a5\uc744 \ubbf8\uce60 \uc218 \uc788\ub294 \uadf9\ud788 \uc77c\ubd80\uc758 \uacbd\uc6b0\uc5d0\uc11c\ub294, \uc9c4\uc2e4\ud558\uac8c \ubcf4\uace0\ud560 \ub54c \ud50c\ub808\uc774\uc5b4\uac00 \uc5bb\uac8c \ub418\ub294 \uacb0\uacfc \ud6a8\uc6a9(outcome utility) \uc99d\uac00\uac00 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\ubcf4\ub2e4 \ud6e8\uc52c \ud06c\ub2e4.<br>\uc989, \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \ubcf4\uace0\ub97c \ubcc0\uacbd\ud560 \ub54c \ubc1c\uc0dd\ud558\ub294 \uae30\ub300 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9 \ubcc0\ud654\ub294 \\(\\epsilon\\) \uc5d0 \ube44\ub840\ud558\uba70, \uc774\ub294 \uacb0\uacfc\uac00 \ubcc0\uacbd\ub420 \ud655\ub960\uc758 \ucd5c\ub300 \\(O(\\epsilon)\\) \ubc30\ub97c \ub118\uc9c0 \uc54a\ub294\ub2e4.<br>\uadf8\ub7ec\ub098 \ud3b8\ud5a5\ub41c \uc120\uac70\uc640 \uac19\uc740 \uc0c1\ud669\uc5d0\uc11c\ub294 \uc774 \ud655\ub960\uc774 \ub9e4\uc6b0 \uc791\uc544\uc9c0\uae30 \ub54c\ubb38\uc5d0, \uc804\ubc18\uc801\uc778 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9 \uc99d\uac00\ub3c4 \uc791\uac8c \uc720\uc9c0\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc774 \ubd84\uc11d\uc740 \uc6b0\ub9ac\uac00 \u201c\uac1c\ubcc4 \uacb0\uacfc(per-outcome) \ud504\ub77c\uc774\ubc84\uc2dc \ubaa8\ub378\u201d\uc744 \ucc44\ud0dd\ud55c \uac83\uc758 \ud575\uc2ec\uc801\uc778 \uc7a5\uc810\uc774\uba70, Dwork et al. [2010]\uc758 \uc5f0\uad6c\ub97c \uc77c\ubc18\ud654\ud55c \uacb0\uacfc\ub85c \ubcfc \uc218 \uc788\ub2e4.<br>Dwork et al. [2010]\uc740 \ubaa8\ub4e0 \\(\\epsilon\\)-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \uba54\ucee4\ub2c8\uc998\uc740 \uc2e4\uc81c \uae30\ub300 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \\(O(\\epsilon^2)\\) \uc5d0 \ubd88\uacfc\ud568\uc744 \uc99d\uba85\ud55c \ubc14 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc6b0\ub9ac\uc758 \uc774\uc0b0\uc801 \uc2dc\uc124 \uc704\uce58 \uc120\uc815(discrete facility location) \uba54\ucee4\ub2c8\uc998\uc740 Xiao [2013]\uc758 \uba54\ucee4\ub2c8\uc998\uc5d0\uc11c \uc601\uac10\uc744 \ubc1b\uc558\ub2e4. Xiao\ub294 \ud574\ub2f9 \uba54\ucee4\ub2c8\uc998\uc774 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ub9cc\uc871\ud558\uace0 \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud568\uc744 \uc99d\uba85\ud588\uc9c0\ub9cc, \uc774\ub294 \ud50c\ub808\uc774\uc5b4\uc758 \ud6a8\uc6a9 \ud568\uc218\uc5d0 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc744 \ud3ec\ud568\ud558\uc9c0 \uc54a\uc740 \uacbd\uc6b0\uc5d0 \ud55c\uc815\ub418\uc5c8\ub2e4. \uc6b0\ub9ac\uc758 \uc811\uadfc \ubc29\uc2dd\uc740 \uc55e\uc11c \uc124\uba85\ud55c \ubd84\uc11d\uc744 \uc801\uc6a9\ud560 \uc218 \uc788\ub3c4\ub85d \uba87 \uac00\uc9c0 \ubcc0\ud615\uc744 \ucd94\uac00\ud55c \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p>\uc120\uac70(election) \ubc0f \uc2dc\uc124 \uc704\uce58 \uc120\uc815(facility location) \uba54\ucee4\ub2c8\uc998\uc758 \uacbd\uc6b0, \uc774\uc804\uc5d0 \uc124\uba85\ud55c \ubd84\uc11d \ubc29\uc2dd\uc744 \uc801\uc6a9\ud558\uba74 \ubaa8\ub4e0 \ub79c\ub364 \ucf54\uc778\uc758 \uc120\ud0dd(random coins)\uc758 \uacbd\uc6b0\uc5d0\ub3c4 \uc9c4\uc2e4\uc131\uc774 \uc131\ub9bd\ud558\ub294(universal truthfulness) \uba54\ucee4\ub2c8\uc998\uc774 \ub41c\ub2e4.<br>\ubc18\uba74, \uc77c\ubc18\uc801\uc778 \uc0ac\ud68c\uc801 \uc120\ud0dd \ubb38\uc81c(general social choice problem)\ub97c \ud574\uacb0\ud558\ub294 VCG \uc720\uc0ac(VCG-like) \uba54\ucee4\ub2c8\uc998\uc758 \uacbd\uc6b0, \uc9c0\uae09(payments)\uc774 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc190\uc0c1\uc2dc\ud0a4\uc9c0 \uc54a\ub3c4\ub85d \ucd94\uac00\uc801\uc778 \uc870\uce58\ub97c \ucde8\ud574\uc57c \ud55c\ub2e4.<br>\uc774\ub85c \uc778\ud574 \ud574\ub2f9 \uba54\ucee4\ub2c8\uc998\uc740 \uae30\ub300\uac12\uc5d0\uc11c\ub9cc \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5(expectation truthfulness)\ud558\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p>\uae30\uc874 \uc5f0\uad6c\ub4e4\uacfc \ub2ec\ub9ac, \uc6b0\ub9ac\ub294 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uadf8 \uc790\uccb4\ub85c \ubaa9\ud45c(end)\ub85c \uc0bc\uc9c0 \uc54a\uace0, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc911\uc2dc\ud558\ub294 \ud50c\ub808\uc774\uc5b4\ub85c\ubd80\ud130 \uc9c4\uc2e4\ud55c \uc751\ub2f5\uc744 \uc720\ub3c4\ud558\ub294 \uc218\ub2e8(means)\uc73c\ub85c \ud65c\uc6a9\ud55c\ub2e4.<br>\uc989, \uc6b0\ub9ac\ub294 \ubc18\ub4dc\uc2dc \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \ud30c\ub77c\ubbf8\ud130 \\(\\epsilon\\) \uc744 \ub9e4\uc6b0 \uc791\uac8c(\ub192\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638, \ud558\uc9c0\ub9cc \uc0ac\ud68c\uc801 \ud6c4\uc0dd \uc190\uc2e4 \uc99d\uac00) \uc124\uc815\ud560 \ud544\uc694\uac00 \uc5c6\ub2e4.<\/p>\n\n\n\n<p>\ub300\uc2e0, \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc774 \ud50c\ub808\uc774\uc5b4\uc758 \uacb0\uacfc\uc5d0 \ub300\ud55c \uc120\ud638(outcome preference)\ub97c \ucd08\uacfc\ud558\uc9c0 \uc54a\ub3c4\ub85d \ucda9\ubd84\ud788 \uc791\uac8c \uc124\uc815\ud558\ub294 \uac83\ub9cc\uc73c\ub85c\ub3c4 \ucda9\ubd84\ud558\ub2e4.<br>\ud2b9\ud788, \uc6b0\ub9ac\uc758 \ubd84\uc11d\uc5d0 \ub530\ub974\uba74 \\(\\epsilon\\) \uc744 \uac10\uc18c\uc2dc\ud0a4\uba74 \ud50c\ub808\uc774\uc5b4\uac00 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\ub825\uc740 \uc904\uc5b4\ub4e4\uc9c0\ub9cc, \uae30\ub300 \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc740 \ud6e8\uc52c \ube60\ub974\uac8c \uac10\uc18c\ud55c\ub2e4.<\/p>\n\n\n\n<p>\ub530\ub77c\uc11c, \ud50c\ub808\uc774\uc5b4\uac00 \uacb0\uacfc\uc5d0 \ub300\ud55c \uc120\ud638\uac00 \ud504\ub77c\uc774\ubc84\uc2dc\ubcf4\ub2e4 \ud6e8\uc52c \ud06c\ub2e4\uba74, \\(\\epsilon\\) \uc758 \ucd5c\uc801\uac12\uc740 \ube44\uad50\uc801 \ud074 \uc218\ub3c4 \uc788\uc73c\uba70, \uc774\ub54c \ud504\ub77c\uc774\ubc84\uc2dc \ube44\uc6a9\uc740 \ubb34\uc2dc\ud560 \uc218 \uc788\uc744 \uc815\ub3c4\ub85c \uc791\uc544\uc9c0\uace0, \ud50c\ub808\uc774\uc5b4\ub294 \uc9c4\uc2e4\ud558\uac8c \uc751\ub2f5\ud560 \uc720\uc778\uc744 \uac00\uc9c0\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p>\ub610\ud55c, \uc6b0\ub9ac\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\ub97c \uace0\ub824\ud55c \uc778\uc13c\ud2f0\ube0c \ubd84\uc11d\uc744 \ud1b5\ud574, \ud50c\ub808\uc774\uc5b4\ub4e4\uc774 \uc2e4\uc81c\ub85c \uc9c4\uc2e4\ud55c \uc751\ub2f5\uc744 \ud558\ub3c4\ub85d \uc720\ub3c4\ud560 \uc218 \uc788\uc73c\uba70, \uadf8 \uacb0\uacfc \uc0ac\ud68c\uc801 \ud6c4\uc0dd\uc774 \ucd5c\uc801\uc5d0 \uac00\uae5d\uac8c \uc218\ub834\ud560 \uac83\uc784\uc744 \ubcf4\ub2e4 \ud655\uc2e0\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p>\uc801\uc808\ud55c \\(\\epsilon\\) \uac12\uc758 \uc124\uc815\uc740 \ud50c\ub808\uc774\uc5b4\ub4e4\uc774 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc5bc\ub9c8\ub098 \uc911\uc694\ud558\uac8c \uc5ec\uae30\ub294\uc9c0\uc640 \uacb0\uacfc\ub97c \uc5bc\ub9c8\ub098 \uc911\uc694\ud558\uac8c \uc5ec\uae30\ub294\uc9c0\uc758 \uc0c1\ub300\uc801 \uac00\uce58(relative valuation)\uc5d0 \ub530\ub77c \ub2ec\ub77c\uc9c0\uba70, \uc774\ub294 \uba54\ucee4\ub2c8\uc998 \uc801\uc6a9 \uc774\uc804\uc5d0 \uc678\ubd80\uc801\uc73c\ub85c(exogenously) \uacb0\uc815\ub418\uc5b4\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<p>\ud50c\ub808\uc774\uc5b4\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58(value for privacy)\ub97c \uc9c1\uc811 \ucd94\ub860\ud558\ub294 \ubb38\uc81c\ub294 \uc6b0\ub9ac\uac00 \ub2e4\ub8e8\ub294 \ubb38\uc81c\uc640\ub294 \ub3c5\ub9bd\uc801\uc778 \ubb38\uc81c(orthogonal problem)\uc774\uba70, \uc774\ub294 Ghosh and Roth [2011]\uc758 \uc5f0\uad6c\uc5d0\uc11c \uc2dc\uc791\ub41c \ubcc4\ub3c4\uc758 \uc5f0\uad6c \ud750\ub984\uc774\ub2e4(\uc774\uc640 \uad00\ub828\ud55c \ub17c\uc758\ub294 \ub2e4\uc74c \uc139\uc158\uc5d0\uc11c \ub2e4\ub8ec\ub2e4).<\/p>\n\n\n\n<p>\uc6b0\ub9ac\uc758 \uc811\uadfc \ubc29\uc2dd\uc740 \uc6b0\uc6d4\uc804\ub7b5 \uc9c0\ubc30(dominant-strategy) \uc194\ub8e8\uc158 \uac1c\ub150\uc744 \uae30\ubc18\uc73c\ub85c \ud558\uae30 \ub54c\ubb38\uc5d0, \uc77c\ubd80 \ud50c\ub808\uc774\uc5b4\uc5d0 \ub300\ud574 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uc5d0 \ub300\ud55c \uac00\uc815\uc774 \uc798\ubabb\ub418\ub354\ub77c\ub3c4, \ub098\uba38\uc9c0 \ud50c\ub808\uc774\uc5b4\ub4e4\uc740 \uc5ec\uc804\ud788 \uc9c4\uc2e4\ud558\uac8c \uc751\ub2f5\ud560 \uc720\uc778\uc744 \uac00\uc9c0\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<h4 class=\"wp-block-heading\">References<\/h4>\n\n\n\n<p>Chen, Yiling, et al. &#8220;Truthful mechanisms for agents that value privacy.&#8221;\u00a0<em>ACM Transactions on Economics and Computation (TEAC)<\/em>\u00a04.3 (2016): 1-30.<\/p>\n\n\n\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>In this work, we propose a new, general way of modeling privacy in players\u2019 utility functions. Specifically, we only assume that if an outcome o has the property that any report of player i would have led to o with approximately the same probability, then o has a small privacy cost to player i.<\/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,206,198,205],"class_list":["post-4918","post","type-post","status-publish","format-standard","hentry","category-paper-review","tag-differential-privacy","tag-mar-9-2025","tag-mechanism","tag-truthful"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4918"}],"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=4918"}],"version-history":[{"count":4,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4918\/revisions"}],"predecessor-version":[{"id":5211,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4918\/revisions\/5211"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=4918"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=4918"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=4918"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}