\uae30\uacc4\uc801 \uc124\uacc4(Mechanism Design)\ub294 \uc790\uae30 \uc774\uc775\uc744 \ucd94\uad6c\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc774 \uc2e4\ud589\ud558\ub294 \ubd84\uc0b0 \uc54c\uace0\ub9ac\uc998\uc744 \ub2e4\ub8e8\ub294 \ud559\ubb38\uc774\ub2e4. \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc790\uc758 \ubaa9\ud45c\ub294 \ud589\uc704\uc790\uc758 \uac1c\uc778\uc801\uc778 \uc720\ud615\uacfc \uad00\ub828\ub41c \uc5b4\ub5a4 \ud568\uc218\ub97c \ucd5c\uc801\ud654\ud558\ub294 \uac83\uc774\ub2e4. \uc774\ub97c \uc704\ud574\uc11c\ub294 \ud589\uc704\uc790\ub4e4\uc758 \uc778\uc13c\ud2f0\ube0c\ub97c \uace0\ub824\ud55c \uacc4\uc0b0\uc744 \uc124\uacc4\ud574\uc57c \ud558\uba70, \uc774\ub294 \ubc18\ub4dc\uc2dc \uba54\ucee4\ub2c8\uc998\uc758 \ubaa9\ud45c\uc640 \uc77c\uce58\ud558\ub294 \uac83\uc740 \uc544\ub2c8\ub2e4. \uc804\ud1b5\uc801\uc73c\ub85c \uba54\ucee4\ub2c8\uc998\uc740 \ud589\uc704\uc790\ub4e4\uc774 \uba54\ucee4\ub2c8\uc998 \uacb0\uacfc\ub85c\ubd80\ud130 \uc5bb\ub294 \ud6a8\uc6a9\ub9cc\uc744 \uace0\ub824\ud558\uc5ec \uc124\uacc4\ub418\uc5c8\uc73c\uba70, \uc774 \uacfc\uc815\uc5d0\uc11c \ud589\uc704\uc790\uc758 \uac1c\uc778\uc801\uc778 \uc815\ubcf4\ub97c \uc644\uc804\ud788 \ub610\ub294 \ubd80\ubd84\uc801\uc73c\ub85c \uacf5\uac1c\ud558\ub294 \uac83\uc774 \uc77c\ubc18\uc801\uc774\uc5c8\ub2e4. \uadf8\ub7ec\ub098 \ud589\uc704\uc790\uac00 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc911\uc694\ud558\uac8c \uc0dd\uac01\ud558\ub294 \uacbd\uc6b0, \uc989 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \uc790\uc2e0\uc758 \ud6a8\uc6a9\uc5d0 \ubd80\uc815\uc801\uc778 \uc601\ud5a5\uc744 \ubbf8\uce58\ub294 \uacbd\uc6b0, \uc774\ub7ec\ud55c \uc804\ud1b5\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc740 \uc801\uc808\ud558\uc9c0 \uc54a\uc744 \uc218 \uc788\ub2e4. \uc774\ub7f0 \uacbd\uc6b0, \uba54\ucee4\ub2c8\uc998 \uc124\uacc4 \uacfc\uc815\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc \uc778\uc2dd\uc744 \uace0\ub824\ud558\uc9c0 \uc54a\uc73c\uba74, \ud574\ub2f9 \uba54\ucee4\ub2c8\uc998\uc740 \uc778\uc13c\ud2f0\ube0c \ud638\ud658\uc801\uc774\uc9c0 \uc54a\uc744 \uc218 \uc788\uc73c\uba70, \ub530\ub77c\uc11c \ube44\ud6a8\uc728\uc801\uc77c \uc218 \uc788\ub2e4. \ud765\ubbf8\ub86d\uac8c\ub3c4, \ub2e4\uc18c \uc9c1\uad00\uc5d0 \ubc18\ud558\ub294 \uc5f0\uad6c \uacb0\uacfc\ub85c Xiao(2011)\ub294 \uac15\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \uac1c\ub150\uc744 \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc5d0\uc11c\ub3c4 \uc774\ub7ec\ud55c \ubb38\uc81c\uac00 \ubc1c\uc0dd\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc600\ub2e4.<\/p>\n\n\n\n
\uc6b0\ub9ac\ub294 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790\ub97c \uc704\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ucd95\ud558\uae30 \uc704\ud574, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998 \uc124\uacc4 \ubaa8\ub378\uc744 \uc81c\uc548\ud558\uace0 \uadf8 \ud0c0\ub2f9\uc131\uc744 \uc124\uba85\ud55c\ub2e4. \uc774\ud6c4, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc2e4\ud604 \uac00\ub2a5\ud568\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n
1. \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \ud589\uc704\uc790 \ubaa8\ub378\ub9c1 (Modeling privacy-aware agents)<\/p>\n\n\n\n
\uc6b0\ub9ac\ub294 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790\ub97c \uc704\ud55c \uc0c8\ub85c\uc6b4 \ubaa8\ub378\uc744 \uc81c\uc548\ud55c\ub2e4. \uc774 \ubaa8\ub378\uc5d0\uc11c\ub294 \ud589\uc704\uc790\uac00 \uc790\uc2e0\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \ud6a8\uc6a9\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \uc644\uc804\ud788 \ud30c\uc545\ud560 \ud544\uc694 \uc5c6\uc774, \ubcf4\uc218\uc801\uc778 \uc0c1\ud55c\uc120\ub9cc \uac00\uc9c0\uba74 \ucda9\ubd84\ud558\ub2e4. \uc774\ub7ec\ud55c \uc811\uadfc\ubc95\uc740 \uae30\uc874 \ubaa8\ub378\ub4e4\uacfc \ucc28\ubcc4\ub418\uba70, \uae30\uc874 \uc5f0\uad6c\uc5d0\uc11c\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \uc644\uc804\ud788 \uaddc\uba85\ud574\uc57c\ub9cc \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud560 \uc218 \uc788\uc5c8\ub2e4.<\/p>\n\n\n\n
2. \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 (Privacy of the Privacy Loss Valuations)<\/p>\n\n\n\n
\ud589\uc704\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\ub294 \uadf8 \uc790\uccb4\ub85c\ub3c4 \ubbfc\uac10\ud55c \uc815\ubcf4\uc77c \uc218 \uc788\ub2e4. \uc6b0\ub9ac\uac00 \uc81c\uc548\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc740 \uc774\ub7ec\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uac00 \uc720\ucd9c\ub428\uc73c\ub85c \uc778\ud574 \ubc1c\uc0dd\ud558\ub294 \ud6a8\uc6a9 \uc190\uc2e4\uae4c\uc9c0 \uace0\ub824\ud55c\ub2e4.<\/p>\n\n\n\n
3. \ub192\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\ub97c \uac00\uc9c4 \ud589\uc704\uc790\uc5d0 \ub300\ud55c \ubcf4\uc7a5 (Guarantees for Agents with High Privacy Valuations)<\/p>\n\n\n\n
\ud589\uc704\uc790\uac00 \uc784\uc758\uc801\uc73c\ub85c \ub192\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\ub97c \uac00\uc9c8 \uc218 \uc788\ub2e4\uba74, \uc778\uc13c\ud2f0\ube0c \ud638\ud658\uc131(incentive compatible)\uc744 \ubcf4\uc7a5\ud558\ub294 \uac83\uc740 \ubd88\uac00\ub2a5\ud558\ub2e4. \ub530\ub77c\uc11c, \uc6b0\ub9ac\ub294 \uba54\ucee4\ub2c8\uc998\uc774 \ud2b9\uc815 \uc784\uacc4\uac12\uc744 \uc124\uc815\ud558\uc5ec, \uc774 \uac12\uc744 \ub118\uc9c0 \uc54a\ub294 \ud589\uc704\uc790\uc5d0 \ub300\ud574\uc11c\ub9cc \uc778\uc13c\ud2f0\ube0c \ud638\ud658\uc131\uc744 \ubcf4\uc7a5\ud558\uace0, \ub098\uba38\uc9c0 \ud589\uc704\uc790\ub4e4\uc5d0 \ub300\ud574\uc11c\ub294 \u03b5-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud558\ub294 \ubc29\uc2dd\uc744 \ucc44\ud0dd\ud55c\ub2e4.<\/mark><\/p>\n\n\n\n 4. \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998 \uad6c\ucd95 (Constructing privacy-aware mechanisms)<\/p>\n\n\n\n \uc6b0\ub9ac\ub294 \uba3c\uc800 \uac04\ub2e8\ud55c \ud22c\ud45c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ucd95\ud55c \ud6c4, \uc774\ub97c \ud655\uc7a5\ud558\uc5ec \ubcf4\ub2e4 \uc77c\ubc18\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud55c\ub2e4. \uc774 \uacfc\uc815\uc5d0\uc11c, Nissim, Smorodinsky, Tennenholtz(2012)\uc758 \uadfc\uc0ac\uc801 \ub367\uc148 \uba54\ucee4\ub2c8\uc998 \uacb0\uacfc\ub97c \uae30\ubc18\uc73c\ub85c \ud558\uc5ec, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc744 \ud3ec\ud568\ud55c \ubaa8\ub378\uc744 \uc124\uacc4\ud55c\ub2e4. \ub610\ud55c, \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58 \ubd84\ud3ec\uc5d0 \ub300\ud55c \uac00\ubcbc\uc6b4 \uac00\uc815(\uc989, \ub300\ubd80\ubd84\uc758 \uc778\uad6c\uac00 \uc720\ud55c\ud55c \ubc94\uc704 \ub0b4\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\ub97c \uac00\uc9c4\ub2e4\ub294 \uac00\uc815) \ud558\uc5d0\uc11c, \uc6b0\ub9ac\uac00 \uc81c\uc548\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc740 \uac70\uc758 \ubaa8\ub4e0 \ud589\uc704\uc790\uc5d0\uac8c \uc778\uc13c\ud2f0\ube0c \ud638\ud658\uc131\uc744 \uc81c\uacf5\ud558\uba70 \ucd5c\uc801\uc758 \uacb0\uacfc\uc5d0 \uac00\uae4c\uc6b4 \uc131\ub2a5\uc744 \ubcf4\uc7a5\ud55c\ub2e4. \ub9c8\uc9c0\ub9c9\uc73c\ub85c, \uc6b0\ub9ac\ub294 \uc774 \uc77c\ubc18\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 \ub514\uc9c0\ud138 \uc0c1\ud488\uc758 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \ud310\ub9e4 \ubb38\uc81c\uc5d0 \uc801\uc6a9\ud558\ub294 \ubc29\ubc95\uc744 \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n \uae30\uacc4\uc801 \uc124\uacc4(Mechanism Design)\ub294 \uc790\uae30 \uc774\uc775\uc744 \ucd94\uad6c\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc774 \uc2e4\ud589\ud558\ub294 \ubd84\uc0b0 \uc54c\uace0\ub9ac\uc998\uc744 \ub2e4\ub8e8\uba70, \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc790\ub294 \ud589\uc704\uc790\uc758 \uac1c\uc778\uc801\uc778 \uc785\ub825(\uc720\ud615)\uc744 \uae30\ubc18\uc73c\ub85c \ud2b9\uc815 \ud568\uc218\ub97c \uacc4\uc0b0\ud558\ub824 \ud55c\ub2e4. \uc804\ud1b5\uc801\uc73c\ub85c \ud589\uc704\uc790\ub4e4\uc740 \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc\ub85c \uc5bb\ub294 \ud6a8\uc6a9\ub9cc\uc744 \uace0\ub824\ud558\uace0 \ud504\ub77c\uc774\ubc84\uc2dc\ub294 \uc2e0\uacbd \uc4f0\uc9c0 \uc54a\ub294\ub2e4\uace0 \uac00\uc815\ub418\uc5c8\uc73c\ub098, \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \ud6a8\uc6a9\uc5d0 \ubd80\uc815\uc801\uc778 \uc601\ud5a5\uc744 \ubbf8\uce58\ub294 \uacbd\uc6b0 \uc774\ub7ec\ud55c \uc811\uadfc \ubc29\uc2dd\uc740 \uc801\uc808\ud558\uc9c0 \uc54a\uc744 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n \uae30\uc874 \uc5f0\uad6c\ub4e4\uc740 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ud65c\uc6a9\ud574 \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ucd95\ud588\uc73c\ub098, \ud589\uc704\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58 \uc790\uccb4\ub97c \ubcf4\ud638\ud558\uc9c0 \uc54a\ub294 \ud55c\uacc4\ub97c \uac00\uc84c\ub2e4. Xiao(2011)\ub294 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc640 \uc9c4\uc2e4\uc131\uc774 \uacb0\ud569\ub418\uc5c8\uc74c\uc5d0\ub3c4, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc5d0\uac8c\ub294 \uc9c4\uc2e4\uc131\uc774 \ud56d\uc0c1 \ubcf4\uc7a5\ub418\uc9c0 \uc54a\uc744 \uc218 \uc788\uc74c\uc744 \ubcf4\uc600\uace0, Ghosh\uc640 Roth(2011)\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \ubcf4\uc0c1\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uc81c\uc548\ud588\uc9c0\ub9cc, \ud589\uc704\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58 \uc790\uccb4\ub97c \ubcf4\ud638\ud558\uc9c0 \ubabb\ud558\ub294 \ubb38\uc81c\uac00 \uc788\uc5c8\ub2e4.<\/mark><\/p>\n\n\n\n Ghosh and Roth (2011)\uc758 \uc5f0\uad6c \uacb0\uacfc\uc5d0 \ub530\ub974\uba74, \ucc38\uc5ec\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \uc815\ubcf4\uac00 \uacf5\uac1c\ub428\uc73c\ub85c \uc778\ud574 \ubc1c\uc0dd\ud558\ub294 \uc815\ubcf4 \uc190\uc2e4(disutility)\uc744 \ubcf4\uc0c1\ud558\ub294 \uac83\uc744 \ubd88\uac00\ub2a5\ud558\ub2e4. \uc989, \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \\(v_i\\) \uc790\uccb4\uac00 \ub178\ucd9c\ub420 \uac00\ub2a5\uc131\uc774 \uc788\ub294 \uacbd\uc6b0, \uc774\ub97c \ubcf4\uc0c1\ud558\ub294 \uac1c\ubcc4 \ud569\ub9ac\uc801(individually rational) \uba54\ucee4\ub2c8\uc998\uc740 \uc874\uc7ac\ud560 \uc218 \uc5c6\ub2e4. \ubcf8 \uc5f0\uad6c\ub294 \uae30\uc874 \uba54\ucee4\ub2c8\uc998\uc774 \ub2e4\ub8e8\uc9c0 \uc54a\uc558\ub358 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58 \uc790\uccb4\uae4c\uc9c0 \ubcf4\ud638\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ucd95\ud558\ub294 \uac83\uc744 \ubaa9\ud45c\ub85c \ud55c\ub2e4. \uadf8\ub7ec\ub098 \uac1c\ubcc4\uc801\uc73c\ub85c \ud569\ub9ac\uc801\uc778 \uc218\uc900\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uc758 \uc720\ucd9c\ub85c \uc778\ud55c \uc815\ubcf4 \uc190\uc2e4\uc744 \uc644\uc804\ud788 \ubcf4\uc0c1\ud558\ub294 \uac83\uc740 \ubd88\uac00\ub2a5\ud558\uae30 \ub54c\ubb38\uc5d0, \uc6b0\ub9ac\ub294 \ub300\uaddc\ubaa8 \ud589\uc704\uc790 \uc9d1\ub2e8(large populations of agents)\uc744 \ub300\uc0c1\uc73c\ub85c \ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc744 \uace0\ub824\ud55c\ub2e4. \uc989, \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \ubcf4\uc0c1\ud558\ub294 \ub300\uc0c1\uc744 \ud55c\uc815\ud558\uc5ec \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uac00 \uc77c\uc815 \uc784\uacc4\uac12 \uc774\ud558\ub85c \uc81c\ud55c\ub41c \ud589\uc704\uc790\ub4e4\uc5d0\uac8c\ub9cc \ubcf4\uc0c1\uc744 \uc81c\uacf5<\/mark>\ud558\uace0, \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uac00 \ub108\ubb34 \ub192\uc544 \uba54\ucee4\ub2c8\uc998\uc774 \ubcf4\uc0c1\ud560 \uc218 \uc5c6\ub294 \uc784\uacc4\uac12\uc744 \ucd08\uacfc\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc5d0 \ub300\ud574\uc11c\ub294 \u03b5-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc801\uc6a9\ud558\uc5ec \ubcf4\ud638\ud558\ub294 \ubc29\uc2dd\uc744 \uc81c\uc548\ud55c\ub2e4. \ubcf8 \uc5f0\uad6c\uc758 \uc8fc\uc694 \uae30\uc5ec \uc911 \ud558\ub098\ub294 \uae30\uc874 \ubaa8\ub378\uc758 \ud55c\uacc4\ub97c \ubcf4\uc644\ud55c \uc0c8\ub85c\uc6b4 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998 \uc124\uacc4 \ubaa8\ub378\uc744 \uc81c\uc548\ud558\ub294 \uac83\uc774\ub2e4. \uc6b0\ub9ac\uc758 \ubaa8\ub378\uc5d0\uc11c \ud589\uc704\uc790\ub294 \uae30\uc874\uc758 \uac8c\uc784 \uc774\ub860\uc801 \uc720\ud615(game type)\uacfc \ud504\ub77c\uc774\ubc84\uc2dc \uc720\ud615(privacy type)\uc744 \ud568\uaed8 \uac00\uc9c0\uba70, \ud504\ub77c\uc774\ubc84\uc2dc \uc720\ud615\uc5d0 \ub300\ud574\uc11c\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \ud6a8\uc6a9\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \ubcf4\uc218\uc801\uc778 \uc0c1\ud55c\uc120\uc73c\ub85c\ub9cc \ud3c9\uac00\ud560 \uc218 \uc788\ub2e4. \ud589\uc704\uc790\ub294 \uc790\uc2e0\uc758 \uac8c\uc784 \uc720\ud615\uacfc \ud504\ub77c\uc774\ubc84\uc2dc \uc720\ud615\uc774 \uc720\ucd9c\ub418\ub294 \uac83 \ubaa8\ub450\uc5d0 \ub300\ud574 \ud6a8\uc6a9 \uac10\uc18c\ub97c \uacbd\ud5d8\ud560 \uc218 \uc788\uc73c\uba70, \uc774\ub294 \uae30\uc874 \uc5f0\uad6c(Ghosh and Roth, 2011)\uc5d0\uc11c \uc815\ubcf4 \ud6a8\uc6a9(information utilty)\uc744 \uc644\uc804\ud788 \uaddc\uba85\ud574\uc57c\ub9cc \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud560 \uc218 \uc788\uc5c8\ub358 \uc811\uadfc \ubc29\uc2dd\uacfc \ucc28\ubcc4\ub41c\ub2e4.<\/p>\n\n\n\n \uae30\uc874 \uba54\ucee4\ub2c8\uc998\ub4e4\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \ud0c0\uc785\uc5d0 \ub300\ud55c \uc815\ubcf4 \ube44\uc6a9(information cost)\uc744 \uace0\ub824\ud558\uc9c0 \uc54a\uc558\ub2e4. \ud589\uc704\uc790\uac00 \uc784\uc758\uc801\uc73c\ub85c \ub192\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\ub97c \uac00\uc9c8 \uc218 \uc788\ub2e4\uba74, \uacc4\uc0b0 \uacb0\uacfc\uc5d0 \ub530\ub77c \uc720\ucd9c\ub418\ub294 \uc815\ubcf4 \ud6a8\uc6a9\uc744 \uc0ac\uc804\uc5d0 \uc81c\ud55c\ud558\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud558\ub2e4. \uc774\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574, \uc6b0\ub9ac\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uc758 \uc784\uacc4\uac12 \\(v_{\\max}\\)\uacfc \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \ub9e4\uac1c\ubcc0\uc218 \u03b5\uc744 \uc124\uc815\ud558\uc5ec, \\(v_{\\max}\\) \uc774\ud558\uc758 \ud589\uc704\uc790\ub4e4\uc5d0\uac8c\ub294 \uc778\uc13c\ud2f0\ube0c \ud638\ud658\uc131\uc744 \ubcf4\uc7a5\ud558\uace0, \ubaa8\ub4e0 \ud589\uc704\uc790\ub4e4\uc5d0\uac8c\ub294 \u03b5-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud558\ub294 \ubc29\uc2dd\uc744 \ucc44\ud0dd\ud55c\ub2e4.<\/p>\n\n\n\n \uc774\ud6c4, \uc6b0\ub9ac\ub294 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc2e4\uc81c\ub85c \uc2e4\ud604 \uac00\ub2a5\ud568<\/mark>\uc744 \ubcf4\uc778\ub2e4. \uccab \ubc88\uc9f8 \uacb0\uacfc\ub85c, 2\uac1c \uc774\uc0c1\uc758 \ub300\uc548 \uc911 \ud558\ub098\ub97c \uc120\ud0dd\ud558\ub294 \ub2e8\uc21c\ud55c \ud22c\ud45c(polling) \ubb38\uc81c\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ucd95\ud55c\ub2e4. \uc5ec\uae30\uc11c \ud575\uc2ec \uc544\uc774\ub514\uc5b4\ub294 \uc815\ubcf4 \uc720\ucd9c\uc5d0 \ub300\ud55c \ud6a8\uc6a9 \uc190\uc2e4\ubcf4\ub2e4 \uc798\ubabb\ub41c \uc751\ub2f5\uc73c\ub85c \uc778\ud55c \ud6a8\uc6a9 \uc190\uc2e4\uc774 \ub354 \ud06c\uac8c \ub9cc\ub4e4\uc5b4 \uc9c4\uc2e4\uc131\uc744 \uc720\uc9c0\ud558\ub3c4\ub85d \uc124\uacc4<\/mark>\ud558\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n \uc774 \uc811\uadfc \ubc29\uc2dd\uc740 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \uc644\uc804\ud788 \ubcf4\uc0c1\ud558\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud558\uae30 \ub54c\ubb38\uc5d0 \ub2ec\uc131\ud560 \uc218 \uc788\ub294 \ucd5c\uc120\uc758 \ud574\uacb0\ucc45\uc774\ub77c\uace0 \ud560 \uc218 \uc788\ub2e4. \uc774\ud6c4, \uc6b0\ub9ac\ub294 \ub300\uaddc\ubaa8 \uc778\uad6c \uc9d1\ub2e8(large population)\uc73c\ub85c \ud655\uc7a5\ud558\uc5ec, \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58 \ubd84\ud3ec\uac00 \ud2b9\uc815\ud55c \uc870\uac74(\uc608: \uc720\ud55c\ud55c \ubaa8\uba58\ud2b8(finiteness of moments)\ub97c \uac00\uc9c4 \uacbd\uc6b0)\uc744 \ub9cc\uc871\ud560 \ub54c, \ubcf4\ub2e4 \uc77c\ubc18\uc801\uc778 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ucd95\ud560 \uc218 \uc788\uc74c\uc744 \ubcf4\uc778\ub2e4.<\/p>\n\n\n\n 5\uc7a5\uc5d0\uc11c\ub294 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc758 \uc77c\ubc18\uc801\uc778 \uad6c\ucd95 \ubc29\ubc95\uc744 \uc81c\uc2dc\ud55c\ub2e4. \uc774 \uacfc\uc815\uc5d0\uc11c, Nissim et al. (2012)\uc758 \uc77c\ubc18\uc801\uc778 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4 \uae30\ubc95\uc744 \uae30\ubc18\uc73c\ub85c, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc744 \ud3ec\ud568\ud558\ub3c4\ub85d \uba54\ucee4\ub2c8\uc998\uc744 \uc218\uc815 \ubc0f \ubd84\uc11d\ud55c\ub2e4. \uc774 \uba54\ucee4\ub2c8\uc998\uc740 \ub300\ubd80\ubd84\uc758 \ud589\uc704\uc790\ub4e4\uc5d0\uac8c \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud558\uba70, \uc815\ud655\ub3c4 \ub610\ud55c \uc77c\uc815 \uc218\uc900 \uc774\uc0c1 \uc720\uc9c0\ud560 \uc218 \uc788\ub3c4\ub85d \uc124\uacc4\ub418\uc5c8\ub2e4. \uc6b0\ub9ac\ub294 \uc77c\ubc18\uc801\uc778 \uc9c4\uc2e4\ud55c(truthful) \uba54\ucee4\ub2c8\uc998\uc774 \uac1c\ubcc4 \uc785\ub825\uac12\uc5d0 \ubbfc\uac10\ud558\uc9c0 \uc54a\uc740 \uacbd\uc6b0(\uc989, \ub300\uaddc\ubaa8 \uc778\uad6c \uc9d1\ub2e8\uc5d0\uc11c \uac1c\ubcc4 \ud589\uc704\uc790\uc758 \uae30\uc5ec\ub3c4\uac00 \ub0ae\uc740 \uacbd\uc6b0), \ub300\ubd80\ubd84\uc758 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc774 \uc9c4\uc2e4\ud558\uac8c \ubcf4\uace0\ud558\ub294 \uac83\uc774 \ud569\ub9ac\uc801\uc784\uc744 \ubcf4\uc778\ub2e4.<\/mark> \uc774\ub294 \uc798\ubabb\ub41c \uc751\ub2f5\uc73c\ub85c \uc778\ud574 \uac10\uc18c\ud558\ub294 \ud6a8\uc6a9\uc774 \uc815\ubcf4 \uc720\ucd9c\ub85c \uc778\ud55c \ud6a8\uc6a9 \uc190\uc2e4\ubcf4\ub2e4 \ud06c\uae30 \ub54c\ubb38\uc774\ub2e4. \ub9cc\uc57d \ucc38\uc5ec\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uac00 \uc784\uc758\ub85c \ub192\uc744 \uc218 \uc788\ub2e4\uba74, \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc\uac00 \ucc38\uc5ec\uc790\uc758 \uac1c\uc778 \uc785\ub825 \ub610\ub294 \ucc38\uc5ec \uc5ec\ubd80\uc5d0 \ub530\ub77c \uacb0\uc815\ub418\ub294 \uacbd\uc6b0, \uc815\ubcf4 \ud6a8\uc6a9\uc744 \uc0ac\uc804\uc5d0 \uc81c\ud55c\ud558\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud558\ub2e4. \uc774\ub7ec\ud55c \uadfc\ubcf8\uc801\uc778 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574, \ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 \ubcf4\ub2e4 \uc644\ud654\ub41c \uc870\uac74(lesser requirement)\uc744 \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n 1. \uba54\ucee4\ub2c8\uc998\uc774 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uc758 \ucd5c\ub300 \uc784\uacc4\uac12 \\(v_{max}\\)\ub97c \uc124\uc815\ud574\uc57c \ud55c\ub2e4. 2. \\(v_{max}\\)\ub97c \ucd08\uacfc\ud558\ub294 \ucc38\uc5ec\uc790\uc5d0 \ub300\ud574\uc11c\ub294 \\(\\epsilon\\)-DP\ub97c \uc81c\uacf5\ud55c\ub2e4. \uc774\ub97c \ud1b5\ud574, \ub300\ubd80\ubd84\uc758 \ucc38\uc5ec\uc790\ub4e4\uc5d0 \ub300\ud574\uc11c\ub294 \uc720\uc778 \ud638\ud658\uc131\uc744 \uc720\uc9c0\ud558\uba74\uc11c\ub3c4, \ud2b9\uc815 \ucc38\uc5ec\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc\uac00 \ub108\ubb34 \ubbfc\uac10\ud560 \uacbd\uc6b0\uc5d0\ub294 DP\ub97c \ud65c\uc6a9\ud558\uc5ec \ubcf4\ud638\ud558\ub294 \uc804\ub7b5\uc744 \uc801\uc6a9\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n \uc554\ud638\ud559 \ubd84\uc57c\uc5d0\uc11c\ub3c4 \u201c\ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\ud638\ud558\ub294 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4(privacy-preserving mechanism design)\u201c\uc5d0 \ub300\ud55c \uc5f0\uad6c\uac00 \uc9c4\ud589\ub418\uc5b4 \uc654\uc73c\uba70, \ub300\ud45c\uc801\uc778 \uc608\ub85c Naor et al.(1999)\uc774 \uc788\ub2e4. \uadf8\ub7ec\ub098 \uc6b0\ub9ac\uc758 \uc5f0\uad6c \ubaa9\ud45c\ub294 \uc774\ub7ec\ud55c \uc554\ud638\ud559\uc801 \uc811\uadfc\uacfc\ub294 \ub2e4\ub974\ub2e4. \ubcf8 \uc5f0\uad6c\uc5d0\uc11c \ud589\uc704\uc790\ub4e4\uc740 \uba54\ucee4\ub2c8\uc998\uc758 \uacf5\uac1c \uacb0\uacfc\uac00 \uc790\uc2e0\uc758 \uc720\ud615(type)\uacfc \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58(privacy valuation)\uc5d0 \ub300\ud574 \uc5b4\ub5a4 \uc815\ubcf4\ub97c \uc720\ucd9c\ud560\uc9c0 \uac71\uc815<\/mark>\ud558\ub294 \ubc18\uba74, \uc554\ud638\ud559\uc801 \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\ub294 \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc\ub97c \uc81c\uc678\ud55c \ubaa8\ub4e0 \uc815\ubcf4\ub97c \uc228\uae30\ub294 \uac83\uc744 \ubaa9\ud45c\ub85c \ud55c\ub2e4.<\/p>\n\n\n\n Miltersen et al.(2009)\uc758 \uc5f0\uad6c\ub294 \uc778\ud130\ub137\uacfc \uac19\uc740 \ub124\ud2b8\uc6cc\ud06c \ud658\uacbd\uc5d0\uc11c \uc554\ud638\ud559\uc744 \ud65c\uc6a9\ud574 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ud604\ud558\ub294 \uac83\uc774 \ub2e8\uc21c\ud558\uc9c0 \uc54a\uc740 \uc791\uc5c5\uc774\uba70, \uc774\ub97c \uad6c\ud604\ud560 \ub54c\uc5d0\ub3c4 \uba54\ucee4\ub2c8\uc998\uc758 \ubcf8\ub798 \uc18d\uc131(\uc608: \uc9c4\uc2e4\uc131)\uc774 \ubcf4\uc874\ub418\ub294\uc9c0 \ud655\uc778\ud574\uc57c \ud55c\ub2e4\ub294 \uc810\uc744 \uc9c0\uc801\ud558\uace0 \uc788\ub2e4.<\/p>\n\n\n\n \ud55c\ud3b8, Chen et al.(2011)\uc740 \ubcf8 \uc5f0\uad6c\uc640 \ub3c5\ub9bd\uc801\uc73c\ub85c, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790\uac00 \uc874\uc7ac\ud558\ub294 \ud658\uacbd\uc5d0\uc11c \uc9c4\uc2e4\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \uc5f0\uad6c\ud588\ub2e4. Chen et al.(2011)\uacfc \uc6b0\ub9ac\uc758 \uc5f0\uad6c\ub294 \ubaa8\ub450 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \uacc4\ub7c9\ud654\ud558\ub294 \ubc29\uc2dd\uc774 \ud589\uc704\uc790\uc758 \uc785\ub825\uc774 \uba54\ucee4\ub2c8\uc998 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc73c\ub85c \uc815\uc758\ub41c\ub2e4\ub294 \uc810\uc5d0\uc11c \uc720\uc0ac\ud55c \ub3d9\uae30\ub97c \uac00\uc9c4\ub2e4. \uadf8\ub7ec\ub098 Chen et al.(2011)\uc758 \ubaa8\ub378\uc5d0\uc11c\ub294 \ud589\uc704\uc790\uac00 \uacb0\uacfc\ubcc4\ub85c \ud504\ub77c\uc774\ubc84\uc2dc\uc5d0 \uac00\uce58\ub97c \ubd80\uc5ec\ud558\ub294 \ubc18\uba74, \uc6b0\ub9ac\uc758 \ubaa8\ub378\uc5d0\uc11c\ub294 \ud589\uc704\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uac00 \uba54\ucee4\ub2c8\uc998\uc758 \uc804\uccb4\uc801\uc778(\uc989, \ucd5c\uc545\uc758) \uacb0\uacfc\uc5d0 \uc758\ud574 \uacb0\uc815\ub41c\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4.<\/p>\n\n\n\n \ub450 \uc811\uadfc\ubc95 \ubaa8\ub450 \ud0c0\ub2f9\ud55c \ub3d9\uae30\ub97c \uac00\uc9c0\uba70, \uc6b0\ub9ac\uc758 \uc811\uadfc\ubc95\uc740 \uc57d\ud55c \uac00\uc815\uc744 \uae30\ubc18\uc73c\ub85c \ub354 \uac15\uac74\ud55c \uba54\ucee4\ub2c8\uc998\uc744 \ub3c4\ucd9c\ud560 \uac00\ub2a5\uc131\uc774 \uc788\uace0, \uacb0\uacfc\ubcc4 \uc811\uadfc \ubc29\uc2dd\uc740 \ub354 \ub2e4\uc591\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uba54\ucee4\ub2c8\uc998\uc744 \uac1c\ubc1c\ud558\ub294 \ub370 \uc720\ub9ac\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n \uc720\ud615 \uc9d1\ud569(type set) T \uc640 \uc0ac\ud68c\uc801 \ub300\uc548 \uc9d1\ud569(social alternatives set) S \uc744 \uc815\uc758\ud55c\ub2e4. \uc989, T \ub294 \ud589\uc704\uc790(agent)\uc758 \uc720\ud615(type)\ub4e4\uc774 \uc18d\ud558\ub294 \uc774\uc0b0\uc801\uc778 \uc9d1\ud569\uc774\uba70, S \ub294 \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc\ub85c \uc120\ud0dd\ub420 \uc218 \uc788\ub294 \ub300\uc548\ub4e4\uc758 \uc9d1\ud569\uc774\ub2e4. \uba54\ucee4\ub2c8\uc998 \\(M : T^n \\to \\Delta(S)\\) \uc740 \uc785\ub825 \ubca1\ud130 \\(t \\in T^n\\) \uc5d0 \ub300\ud574, \uc0ac\ud68c\uc801 \ub300\uc548 \uc9d1\ud569 S \uc5d0 \ub300\ud55c \ud655\ub960 \ubd84\ud3ec\ub97c \ubc18\ud658\ud558\ub294 \ud568\uc218\uc774\ub2e4. \uc5ec\uae30\uc11c \\(\\Delta(S)\\) \ub294 \uc9d1\ud569 S \uc704\uc758 \ud655\ub960 \ubd84\ud3ec\uc758 \uc9d1\ud569\uc744 \uc758\ubbf8\ud55c\ub2e4. \uc989, \uba54\ucee4\ub2c8\uc998 M \uc740 \ud2b9\uc815 \uc785\ub825 \ubca1\ud130 t \uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \ud655\ub960\uc801\uc73c\ub85c S \ub0b4\uc758 \uc5b4\ub5a4 \uc694\uc18c\ub97c \uacb0\uacfc\ub85c \uc120\ud0dd\ud55c\ub2e4. \ub610\ud55c, \\(M(t)(S^{\\prime})\\) \ub294 \uba54\ucee4\ub2c8\uc998 M \uc774 \uc785\ub825 t \uc5d0 \ub300\ud574, \ud2b9\uc815 \ubd80\ubd84\uc9d1\ud569 \\(S^{\\prime} \\subseteq S\\) \ub97c \ucd9c\ub825\ud560 \ud655\ub960\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub294 \uc8fc\uc5b4\uc9c4 \ud589\uc704\uc790\uc758 \uc720\ud615\uc744 \ud3ec\ud568\ud55c \uc785\ub825\uc774 \ubcc0\uacbd\ub418\uc5c8\uc744 \ub54c, \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc \ubd84\ud3ec\uac00 \uc5bc\ub9c8\ub098 \uc601\ud5a5\uc744 \ubc1b\ub294\uc9c0\ub97c \uce21\uc815\ud558\ub294 \ub9e4\uc6b0 \ubcf4\uc218\uc801\uc778 \uae30\uc900\uc774\ub2e4. \uc774\ub294 \ub2e4\ub978 \ud589\uc704\uc790\uc758 \ubaa8\ub4e0 \uc720\ud615\uc774 \uc54c\ub824\uc838 \uc788\ub354\ub77c\ub3c4, \uac1c\ubcc4 \ud589\uc704\uc790\uc758 \uc815\ubcf4\uac00 \uc720\ucd9c\ub418\ub294 \uc704\ud5d8\uc744 \uc81c\ud55c\ud558\ub294 \uac15\ub825\ud55c \ubcf4\ud638 \uba54\ucee4\ub2c8\uc998\uc774\ub2e4.<\/p>\n\n\n\n \uba54\ucee4\ub2c8\uc998 \\(M : T^n \\to \\Delta(S)\\) \uc774 \u03b5-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ub9cc\uc871\ud55c\ub2e4\ub294 \uac83\uc740, \ubaa8\ub4e0 \uc774\uc6c3 \uad00\uacc4\uc778 \\(t, t^{\\prime} \\in T^n\\) \uc640 \ubaa8\ub4e0 \uce21\uc815 \uac00\ub2a5\ud55c \ubd80\ubd84\uc9d1\ud569 \\(S^{\\prime} \\subseteq S\\) \uc5d0 \ub300\ud574 \ub2e4\uc74c\uc774 \uc131\ub9bd\ud558\ub294 \uac83\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n \\(M(t)(S{\\prime}) \\leq e^{\\epsilon} \\cdot M(t{\\prime})(S{\\prime})\\)<\/p>\n\n\n\n \uc989, \uba54\ucee4\ub2c8\uc998\uc774 \ud2b9\uc815 \uc785\ub825 \ubca1\ud130 t \ub97c \ubc1b\uc558\uc744 \ub54c \ud2b9\uc815 \uacb0\uacfc \\(S^{\\prime}\\) \uac00 \uc120\ud0dd\ub420 \ud655\ub960\uacfc, \uc774\uc6c3\ud558\ub294 \uc785\ub825 \\(t^{\\prime}\\) \uc5d0 \ub300\ud574 \uac19\uc740 \uacb0\uacfc\uac00 \uc120\ud0dd\ub420 \ud655\ub960\uc774 \\(e^{\\epsilon}\\) \ubc30 \uc774\ub0b4\ub85c \uc720\uc9c0\ub428\uc744 \ubcf4\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \uc815\uc758\ub85c\ubd80\ud130 \uc9c1\uc811\uc801\uc73c\ub85c \uc720\ub3c4\ud560 \uc218 \uc788\ub294 \uacb0\uacfc\ub294 \ub2e4\uc74c\uacfc \uac19\ub2e4.<\/p>\n\n\n\n \uba54\ucee4\ub2c8\uc998 \\(M : T^n \\to \\Delta(S)\\) \uc774 \u03b5-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ub9cc\uc871\ud55c\ub2e4\uace0 \uac00\uc815\ud558\uc790. \ud568\uc218 \\(g: S \\to \\mathbb{R}_{\\geq 0}\\) \uc5d0 \ub300\ud574, \ubaa8\ub4e0 \uc774\uc6c3 \uad00\uacc4\uc778 \\(t, t^{\\prime} \\in T^n\\) \uc5d0 \ub300\ud574 \ub2e4\uc74c\uc774 \uc131\ub9bd\ud55c\ub2e4.<\/p>\n\n\n\n \\(E_{s \\sim M(t)} [g(s)] \\leq e^{\\epsilon} \\cdot E_{s \\sim M(t^{\\prime})} [g(s)]\\)<\/p>\n\n\n\n \ud2b9\ud788, \ub9cc\uc57d \\(\\epsilon \\leq 1\\) \uc774\uace0 \\(g: S \\to [0,1]\\) \uc778 \uacbd\uc6b0,<\/p>\n\n\n\n \\(E_{s \\sim M(t)} [g(s)] – E_{s \\sim M(t^{\\prime})} [g(s)] < 2\\epsilon\\)<\/p>\n\n\n\n \uc774 \uc131\ub9bd\ud55c\ub2e4.<\/p>\n\n\n\n \uc989, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ub9cc\uc871\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc5d0\uc11c\ub294, \uc785\ub825\uc774 \ubc14\ub00c\ub354\ub77c\ub3c4 \uae30\ub300\uac12\uc758 \ubcc0\ud654\uac00 \uc81c\ud55c\ub428\uc744 \ubcf4\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n \uc6b0\ub9ac\uc758 \ubaa8\ub378\uc740 \uae30\uc874\uc758 \uae30\uacc4\uc801 \uc124\uacc4(Mechanism Design) \ubaa8\ub378\uacfc \uc720\uc0ac\ud558\uc9c0\ub9cc, \uba54\ucee4\ub2c8\uc998\uc5d0 \ucc38\uc5ec\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc774 \ud504\ub77c\uc774\ubc84\uc2dc\uc5d0 \ub300\ud55c \ud6a8\uc6a9\uc744 \uace0\ub824\ud55c\ub2e4\ub294 \uc810\uc5d0\uc11c \ucc28\uc774\uac00 \uc788\ub2e4. \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790(privacy-aware agents)\uc758 \uacbd\uc6b0, \uae30\uc874 \ud6a8\uc6a9 \ud568\uc218\uc5d0 \uc815\ubcf4 \uc720\ucd9c\ub85c \uc778\ud55c \ube44\ud6a8\uc6a9(dis-utility), \uc989 \uc815\ubcf4 \ud6a8\uc6a9(information utility) \uc744 \ucd94\uac00\ud574\uc57c \ud55c\ub2e4. \uc774\ub54c, \uc815\ubcf4 \uc720\ucd9c\uc744 \uc5b4\ub5bb\uac8c \uc815\ub7c9\ud654\ud560 \uac83\uc778\uac00?<\/mark> \uac00 \uccab \ubc88\uc9f8 \ubb38\uc81c\ub85c \ub4f1\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n \ube44\ud611\ub825\uc801 \ucef4\ud4e8\ud305(Non-Cooperative Computing, NCC) \ub9e5\ub77d\uc5d0\uc11c \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ud6a8\uc6a9 \ud568\uc218\uc5d0 \ud3ec\ud568\ud55c \ucd08\uae30 \uc5f0\uad6c\uc774\ub2e4. \ud589\uc704\uc790\ub4e4\uc740 \ub2e4\ub978 \ud589\uc704\uc790\uac00 \uc790\uc2e0\uc758 \uac1c\uc778 \uc720\ud615\uc744 100% \ud655\uc2e4\ud558\uac8c \uc544\ub294 \uacbd\uc6b0\uc5d0\ub9cc \uc815\ubcf4 \uc720\ucd9c\uc744 \uac71\uc815\ud55c\ub2e4. \uc989, \ud504\ub77c\uc774\ubc84\uc2dc\ub294 \uc644\uc804\ud788 \ubcf4\ud638\ub418\uac70\ub098(\uc815\ubcf4 \uc720\ucd9c \uc5c6\uc74c), \uc644\uc804\ud788 \ub178\ucd9c\ub418\uac70\ub098(\uc815\ubcf4 \uc720\ucd9c \uc874\uc7ac) \ub450 \uac00\uc9c0 \uc0c1\ud0dc\ub9cc \uc874\uc7ac\ud55c\ub2e4. \ub530\ub77c\uc11c, \uc815\ubcf4 \uc720\ucd9c \ud6a8\uc6a9\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \uc774\uc9c4\uc801\uc73c\ub85c \uc815\ub7c9\ud654\ub41c\ub2e4.<\/p>\n\n\n\n \ub370\uc774\ud130 \ubd84\uc11d\uac00\uac00 \u03b5-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud558\ub294 \ud1b5\uacc4\ub97c \uacc4\uc0b0\ud560 \ub54c, \ub370\uc774\ud130 \uc81c\uacf5\uc790\uc5d0\uac8c \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \ubcf4\uc0c1\ud558\ub294 \ud658\uacbd\uc744 \uace0\ub824\ud558\uc600\ub2e4. \\(u_i^{\\text{inf}} = v_i \\cdot \\epsilon\\)<\/p>\n\n\n\n \uc5ec\uae30\uc11c \\(v_i\\) \ub294 \ud589\uc704\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58\uc774\uba70, \\(\\epsilon\\) \uac12\uc774 \ud074\uc218\ub85d(\uc989, \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638\uac00 \uc57d\ud574\uc9c8\uc218\ub85d) \uc815\ubcf4 \uc720\ucd9c\ub85c \uc778\ud55c \ube44\ud6a8\uc6a9\uc774 \ucee4\uc9c4\ub2e4. \\(\\epsilon\\) \uc740 \ucd5c\uc545\uc758 \uacbd\uc6b0(worst-case) \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \uce21\uc815\ud558\ub294 \uac12\uc774\ubbc0\ub85c, \uc2e4\uc81c \ud3c9\uade0\uc801\uc778 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc740 \ud6e8\uc52c \uc791\uc744 \uc218 \uc788\ub2e4(Dwork et al., 2010). \u2192 \uc815\ubcf4 \uc720\ucd9c \ube44\ud6a8\uc6a9\uc774 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \ub9e4\uac1c\ubcc0\uc218 \\(\\epsilon\\) \uc5d0 \ube44\ub840\ud55c\ub2e4\uace0 \uac00\uc815\ud558\uc9c0\ub9cc, \uc2e4\uc81c \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc740 \ud3c9\uade0\uc801\uc73c\ub85c \ub354 \uc791\uc744 \uc218 \uc788\uc73c\uba70, \ud589\uc704\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58 \\(v_i\\) \uc790\uccb4\uac00 \uc720\ucd9c\ub420 \uc704\ud5d8\uc744 \uace0\ub824\ud558\uc9c0 \uc54a\ub294\ub2e4.<\/mark><\/p>\n\n\n\n \ubcf8 \uc5f0\uad6c\uc640 \uc720\uc0ac\ud558\uac8c, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uae30\uacc4\uc801 \uc124\uacc4 \ubaa8\ub378\uc744 \uc5f0\uad6c\ud558\uc600\ub2e4. \\(u_i^{\\text{inf}} = v_i \\cdot I(t_i; M(t_{-i}, \\sigma(t_i)))\\)<\/p>\n\n\n\n \uc5ec\uae30\uc11c \\(I(t_i; M(t_{-i}, \\sigma(t_i)))\\) \ub294 \ud589\uc704\uc790 i \uc758 \uc720\ud615 \\(t_i\\) \uac00 \uba54\ucee4\ub2c8\uc998 M \uc758 \uacb0\uacfc\ub97c \ud1b5\ud574 \uc5bc\ub9c8\ub098 \ub9ce\uc740 \uc815\ubcf4\uac00 \uc720\ucd9c\ub418\ub294\uc9c0\ub97c \ub098\ud0c0\ub0b4\ub294 \uc0c1\ud638 \uc815\ubcf4(mutual information) \ub97c \uc758\ubbf8\ud55c\ub2e4. \u2192 \ud589\uc704\uc790\uc758 \uc804\ub7b5 \\(\\sigma\\)\uc5d0 \uc758\ud574 \uc815\ubcf4 \uc720\ucd9c\uc758 \uc815\ub3c4\uac00 \ub2ec\ub77c\uc9c8 \uc218 \uc788\uae30 \ub54c\ubb38\uc5d0, \ubd84\uc11d\uc801 \uc5b4\ub824\uc6c0\uc774 \uc788\ub2e4.<\/mark><\/p>\n\n\n\n Alice\ub294 Bob\uc744 \uc704\ud574 \uc0cc\ub4dc\uc704\uce58\ub97c \uc900\ube44\ud558\uba74\uc11c, Bob\uc774 \ud638\ubc00\ube75(R)\uacfc \ud1b5\ubc00\ube75(W) \uc911 \uc5b4\ub5a4 \uac83\uc744 \uc120\ud638\ud558\ub294\uc9c0 \ubb3b\ub294\ub2e4. 1. Bob\uc774 \uc790\uc2e0\uc758 \uc2e4\uc81c \uc120\ud638\ub3c4\ub97c \uc81c\uacf5\ud558\ub294 \uacbd\uc6b0<\/p>\n\n\n\n \uc774 \uacbd\uc6b0, Bob\uc740 \uc88b\uc544\ud558\ub294 \uc0cc\ub4dc\uc704\uce58\ub97c \uba39\uc744 \uc218 \uc788\ub2e4. \\(I(t_{\\text{Bob}}; M(\\sigma_{\\text{truthful}}(t_{\\text{Bob}}))) = 1\\)<\/p>\n\n\n\n 2. Bob\uc774 \ubb34\uc791\uc704\ub85c \ub300\ub2f5\ud558\ub294 \uacbd\uc6b0<\/p>\n\n\n\n Bob\uc740 50% \ud655\ub960\ub85c \uc6d0\ud558\ub294 \uc0cc\ub4dc\uc704\uce58\ub97c \ubc1b\uc744 \uc218 \uc788\ub2e4. \\(I(t_{\\text{Bob}}; M(\\sigma_{\\text{random}}(t_{\\text{Bob}}))) = 0\\)<\/p>\n\n\n\n \uc911\uc694\ud55c \uc810\uc740 Bob\uc758 \uc720\ud615(\ud638\ubc00 \ub610\ub294 \ud1b5\ubc00)\uc774 \uade0\ub4f1 \ud655\ub960\ub85c \uc120\ud0dd\ub418\ubbc0\ub85c, Alice\uc758 \uad00\uc810\uc5d0\uc11c Bob\uc758 \ud589\ub3d9 \ubd84\ud3ec\ub294 \ub450 \uc804\ub7b5(\uc9c4\uc2e4\ud55c \uc751\ub2f5 \\(\\sigma_{\\text{truthful}}\\) vs \ubb34\uc791\uc704 \uc751\ub2f5 \\(\\sigma_{\\text{random}}\\))\uc774 \ub3d9\uc77c\ud558\uac8c \ubcf4\uc778\ub2e4\ub294 \uac83\uc774\ub2e4. \uc774 \uc608\uc81c\ub294 \\(I(t_{\\text{Bob}}; M(\\sigma(t_{\\text{Bob}})))\\) \uac00 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uce21\uc815\ud558\ub294 \uae30\uc900\uc73c\ub85c\uc11c \ubb38\uc81c\uac00 \uc788\uc744 \uc218 \uc788\uc74c\uc744 \ubcf4\uc5ec\uc900\ub2e4. \uc6b0\ub9ac\ub294 \uae30\uc874 \uc5f0\uad6c\ub4e4\uacfc \ub2ec\ub9ac \uc0c8\ub85c\uc6b4 \uc815\ubcf4 \ud6a8\uc6a9(information utility) \uce21\uc815 \ubc29\ubc95\uc744 \uc81c\uc548\ud558\ub294 \uac83\uc774 \uc544\ub2c8\ub77c, \uae30\uc874 \ubc29\ubc95\ubcf4\ub2e4 \ud6e8\uc52c \uc57d\ud55c \uac1c\ub150\uc744 \uc0ac\uc6a9\ud55c\ub2e4. (1) Ghosh\uc640 Roth(2011)\uc758 \ubaa8\ub378: \\(v_i \\cdot \\epsilon\\)<\/p>\n\n\n\n \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc(\u03b5-differential privacy)\ub97c \ubcf4\uc7a5\ud558\ub294 \uba54\ucee4\ub2c8\uc998\uc5d0\uc11c\ub294,<\/p>\n\n\n\n \\(\\frac{\\Pr[M(t) = s]}{\\Pr[M(t{\\prime}) = s]} \\leq e^\\epsilon\\)<\/p>\n\n\n\n \uac00 \ubaa8\ub4e0 \uc778\uc811\ud55c \uc785\ub825 \\(t, t^{\\prime}\\) \ubc0f \ucd9c\ub825 s \uc5d0 \ub300\ud574 \uc131\ub9bd\ud55c\ub2e4. (2) Xiao(2011)\uc758 \ubaa8\ub378: \\(v_i \\cdot I(t_i; M(t))\\)<\/p>\n\n\n\n \uc608\uc81c 3.1\uc5d0\uc11c \ub17c\uc758\ub41c \ubb38\uc81c\ub97c \ud53c\ud558\ub824\uba74, \\(I(t_i; M(t)) \\geq I(t_i; M(t_{-i}, \\sigma(t_i)))\\) \uac00 \ubaa8\ub4e0 \uc804\ub7b5 \\(\\sigma\\) \uc5d0 \ub300\ud574 \uc131\ub9bd\ud55c\ub2e4\ub294 \uc810\uc744 \ud65c\uc6a9\ud574\uc57c \ud55c\ub2e4. (3) \uc815\ubcf4 \uc720\ucd9c\uc758 \ucd5c\ub313\uac12\uc774 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uc640 \uc5f0\uacb0\ub428<\/p>\n\n\n\n Observation 2\uc5d0 \ub530\ub974\uba74, \\(I(t_i; M(t)) \\leq \\epsilon \\log e\\) \uc774\ubbc0\ub85c, \uacb0\uad6d \\(v_i \\cdot \\epsilon\\) \uc774 \uac00\uc7a5 \uc57d\ud55c(\ub290\uc2a8\ud55c) \uc0c1\ud55c \uac12\uc774 \ub41c\ub2e4. (1) Ghosh\uc640 Roth(2011)\uacfc\uc758 \ucc28\uc774\uc810<\/p>\n\n\n\n \uc6b0\ub9ac\uac00 \\(v_i \\cdot \\epsilon\\) \uc744 \uc815\ubcf4 \ud6a8\uc6a9\uc758 \uc0c1\ud55c\uc73c\ub85c \uc0ac\uc6a9\ud558\ub294 \ubc29\uc2dd\uc740 Ghosh\uc640 Roth(2011)\uc640 \uac1c\ub150\uc801\uc73c\ub85c \ub2e4\ub974\ub2e4.<\/p>\n\n\n\n (2) \ub808\ub9c8 2.2\uc640\uc758 \uad00\uacc4<\/p>\n\n\n\n \ub808\ub9c8 2.2\uc5d0 \ub530\ub974\uba74, \ud589\uc704\uc790\uac00 \uc790\uc2e0\uc758 \uc815\ubcf4 \uc720\ucd9c\ub85c \uc778\ud574 \ubbf8\ub798\uc758 \ud6a8\uc6a9\uc774 \uac10\uc18c\ud560 \uac00\ub2a5\uc131\uc774 \uc874\uc7ac\ud55c\ub2e4. \\(\\max_{t \\in T^n} (e^\\epsilon – 1) \\cdot E_{s \\sim M(t)} |G_i(s)| \\approx \\epsilon \\cdot \\max_{t \\in T^n} E_{s \\sim M(t)} |G_i(s)|\\)<\/p>\n\n\n\n \uc5ec\uae30\uc11c \\(G_i(s)\\) \ub294 \ud589\uc704\uc790 i \uc758 \ubbf8\ub798 \ud6a8\uc6a9\uc774 \uba54\ucee4\ub2c8\uc998 M \uc758 \uacb0\uacfc\uc5d0 \ub530\ub77c \uc5b4\ub5bb\uac8c \ub2ec\ub77c\uc9c0\ub294\uc9c0\ub97c \ub098\ud0c0\ub0b4\ub294 \ud568\uc218\uc774\ub2e4. (1) \uae30\uc874 \uc5f0\uad6c\uc5d0\uc11c \\(v_i\\) \uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \ubd80\uc871<\/p>\n\n\n\n Ghosh\uc640 Roth(2011)\uc758 \uc5f0\uad6c\uc5d0\uc11c \ud589\uc704\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uac00\uce58 \\(v_i\\) \ub294 \ubcf4\ud638\ub418\uc9c0 \uc54a\ub294\ub2e4. (2) \uc6b0\ub9ac\uc758 \uba54\ucee4\ub2c8\uc998\uc774 \uc81c\uacf5\ud558\ub294 \ud574\uacb0\ucc45<\/p>\n\n\n\n \uc6b0\ub9ac\ub294 \\((t_i, v_i)\\) \uc804\uccb4 \uc720\ud615\uc5d0 \ub300\ud574 \\(\\epsilon\\)-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc81c\uacf5\ud55c\ub2e4. (3) \uc9c4\uc2e4\uc131\uc744 \uc720\uc9c0\ud558\ub294 \ubc29\ubc95<\/p>\n\n\n\n \ubaa8\ub4e0 \\(v_i \\leq v_{\\max}\\) \ub97c \ub9cc\uc871\ud558\ub294 \ud589\uc704\uc790\uc5d0 \ub300\ud574, \uc9c4\uc2e4\uc131\uc774 \uc9c0\ubc30 \uc804\ub7b5(dominant strategy)\uc774 \ub418\ub3c4\ub85d \ubcf4\uc7a5\ud55c\ub2e4. \uc0ac\ud68c\uc801 \ub300\uc548(social alternatives) \uc9d1\ud569 S \uc640 \uc720\ud615(Type) \uc9d1\ud569 T \uac00 \uc874\uc7ac\ud558\uba70, n\uba85\uc758 \ud589\uc704\uc790\uac00 \ucc38\uc5ec\ud55c\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4. \uc124\uacc4\uc790\uc758 \ubaa9\ud45c\ub294 \uc8fc\uc5b4\uc9c4 \ud589\uc704\uc790\uc758 \uc2e4\uc81c \uc720\ud615 t \uc5d0 \ub300\ud574 \uc0ac\ud68c\uc801 \ub300\uc548 s \ub97c \uc120\ud0dd\ud558\uc5ec \ubaa9\uc801 \ud568\uc218 f(t, s) \ub97c \ucd5c\uc801\ud654\ud558\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n \\(f : T^n \\times S \\to \\mathbb{R}_{\\geq 0}\\)<\/p>\n\n\n\n \uc5ec\uae30\uc11c f(t, s) \ub294 \uc8fc\uc5b4\uc9c4 \ud589\uc704\uc790 \uc720\ud615 t \uc5d0 \ub300\ud55c \uc120\ud0dd\ub41c \ub300\uc548 s \uc758 \ud6a8\uc6a9\uc744 \ub098\ud0c0\ub0b4\ub294 \ube44\uc74c\uc218(Non-negative) \ud568\uc218\uc774\ub2e4. \\(\\Delta f = \\max | f(\\hat{t}, s) – f(\\hat{t}^{\\prime}, s) |\\)<\/p>\n\n\n\n \uc5ec\uae30\uc11c \ucd5c\ub300\uac12\uc740 \ubaa8\ub4e0 \uc774\uc6c3\ud558\ub294 \uc720\ud615 \ubca1\ud130(neighboring type vectors) \\(\\hat{t}, \\hat{t}^{\\prime} \\in T^n\\) \ubc0f \\(s \\in S\\) \uc5d0 \ub300\ud574 \uacc4\uc0b0\ub41c\ub2e4. \\(f(t, s) \\in [0, n \\Delta f]\\)<\/mark><\/p>\n\n\n\n \uae30\uc874 \uc790\uae30 \uc774\uc775\uc744 \ucd94\uad6c\ud558\ub294 \ud589\uc704\uc790(selfish agents) \ubaa8\ub378\uc744 \ud655\uc7a5\ud558\uc5ec, \ud589\uc704\uc790\uac00 \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc\uc5d0\uc11c \uc5bb\ub294 \ud6a8\uc6a9 \\(u_i^{\\text{out}}\\) \ubfd0\ub9cc \uc544\ub2c8\ub77c, \uc815\ubcf4 \uc720\ucd9c\ub85c \uc778\ud574 \ubc1c\uc0dd\ud558\ub294 \ube44\ud6a8\uc6a9(dis-utility) \\(u_i^{\\text{inf}}\\) \ub3c4 \uace0\ub824\ud558\ub294 \uc124\uc815\uc744 \uc81c\uc2dc\ud55c\ub2e4. \\(u_i = u_i^{\\text{out}} – u_i^{\\text{inf}}\\)<\/mark><\/p>\n\n\n\n \ud589\uc704\uc790\uc758 \uc720\ud615 \\(\\tau_i\\) \ub294 \uae30\uc874 \uc720\ud615 \\(t_i\\) \uc640 \ud504\ub77c\uc774\ubc84\uc2dc \uc120\ud638\ub3c4 \\(v_i\\) \ub85c \uad6c\uc131\ub41c \ubca1\ud130 \\(\\tau_i = (t_i, v_i)\\) \ub85c \uc815\uc758\ub41c\ub2e4. \ud589\uc704\uc790\ub294 \uc790\uc2e0\uc758 \ud6a8\uc6a9\uc744 \uadf9\ub300\ud654\ud558\uae30 \uc704\ud574 \uc720\ud615\uc744 \uc804\ub7b5\uc801\uc73c\ub85c \uc120\uc5b8\ud560 \uc218 \uc788\uc73c\uba70, \uc774\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \ud45c\ud604\ub41c\ub2e4.<\/p>\n\n\n\n \\(\\tau^{\\prime}_i = \\sigma_i(\\tau_i) = (t^{\\prime}_i, v^{\\prime}_i)\\)<\/p>\n\n\n\n \uc804\ud1b5\uc801\uc778 \uac8c\uc784 \uc774\ub860\uc801 \ud6a8\uc6a9(Traditional Game Utility) \\(u_i^{\\text{out}}\\) \ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc815\uc758\ub41c\ub2e4.<\/p>\n\n\n\n \\(u_i^{\\text{out}} : T \\times S \\to [-1,1]\\)<\/p>\n\n\n\n \uc815\ubcf4 \uc720\ucd9c\ub85c \uc778\ud55c \ube44\ud6a8\uc6a9(Information Disutility) \\(u_i^{\\text{inf}}\\) \ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc815\uc758\ub41c\ub2e4.<\/p>\n\n\n\n \\(u_i^{\\text{inf}} : \\mathbb{R}{\\geq 0} \\to \\mathbb{R}{\\geq 0}\\)<\/p>\n\n\n\n \ub2e8, \ub2e4\uc74c\uacfc \uac19\uc740 \uac00\uc815\uc744 \ub530\ub978\ub2e4.<\/p>\n\n\n\n \\(u_i^{\\text{inf}}(v_i) \\leq v_i \\cdot \\epsilon\\)<\/p>\n\n\n\n \uc5ec\uae30\uc11c \\(\\epsilon\\) \uc740 \uc2e4\ud589\ub418\ub294 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \uba54\ucee4\ub2c8\uc998\uc758 \ub9e4\uac1c\ubcc0\uc218\ub85c \uc815\uc758\ub418\uba70,<\/p>\n\n\n\n \\(e^\\epsilon = \\max \\frac{M(t)(S)}{M(t^{\\prime})(S)}\\)<\/p>\n\n\n\n \uc774 \ucd5c\ub300\uac12\uc740 \ubaa8\ub4e0 \uc774\uc6c3\ud558\ub294 \\(t, t^{\\prime} \\in T^n\\) \ubc0f \\(S^{\\prime} \\subseteq S\\) \uc5d0 \ub300\ud574 \uacc4\uc0b0\ub41c\ub2e4. \uc6b0\ub9ac\ub294 \ucc38\uc5ec\ud558\ub294 \ud589\uc704\uc790(participating agents)\ub77c\ub294 \uac1c\ub150\uc744 \uc815\uc758\ud558\uba70, \uc774\ub294 \u201c\uc9c4\uc2e4\ud55c \uc751\ub2f5(truthtelling)\uc774 \uc808\ub300\uc801\uc73c\ub85c \uc6b0\uc6d4\ud55c \uc804\ub7b5(strictly dominant strategy)<\/mark>\u201c\uc774 \ub418\ub294 \ud589\uc704\uc790\ub4e4\uc758 \ubd80\ubd84\uc9d1\ud569\uc774\ub2e4. <\/p>\n\n\n\n \ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc2e4\uc81c\ub85c \uad6c\ud604 \uac00\ub2a5\ud568\uc744 \uc785\uc99d\ud55c\ub2e4. \uc5ec\ub7ec \ub300\uc548 \uc911\uc5d0\uc11c \uc120\ud0dd\ud558\ub294 \uac04\ub2e8\ud55c \ud22c\ud45c \ubb38\uc81c\ub97c \uace0\ub824\ud55c\ub2e4.<\/p>\n\n\n\n 1) \uc798\ubabb\ub41c \uc751\ub2f5(mis-reporting)\uc73c\ub85c \uc778\ud574 \ubc1c\uc0dd\ud558\ub294 \uc804\ud1b5\uc801\uc778 \ube44\ud6a8\uc6a9\uc774 \uc815\ubcf4 \ud6a8\uc6a9\uc744 \uc555\ub3c4\ud558\ub3c4\ub85d \uc124\uacc4\ud55c\ub2e4. 2) \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uc5d0 \ub530\ub77c \ub450 \uadf8\ub8f9\uc73c\ub85c \ub098\ub208\ub2e4. \uc774\ub294 \ubcf8 \ub17c\ubb38\uc774 \ub2ec\uc131\ud560 \uc218 \uc788\ub294 \ucd5c\uc120\uc758 \ud574\uacb0\ucc45(best we can hope to achieve)\uc774\ub77c\uace0 \ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n \ucc38\uc5ec\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \ubd84\ud3ec\uac00 \ud2b9\uc815\ud55c \ud1b5\uacc4\uc801 \ud2b9\uc131\uc744 \ub9cc\uc871\ud55c\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4. <\/p>\n\n\n\n Nissim, Kobbi, Claudio Orlandi, and Rann Smorodinsky. “Privacy-aware mechanism design.” Proceedings of the 13th ACM conference on electronic commerce<\/em>. 2012.<\/p>\n\n\n\n <\/p>","protected":false},"excerpt":{"rendered":" Towards constructing mechanisms for privacy-aware agents, we put forward and justify a model of privacy-aware mechanism design. We then show that privacy-aware mechanisms are feasible.<\/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,198],"class_list":["post-4784","post","type-post","status-publish","format-standard","hentry","category-paper-review","tag-differential-privacy","tag-mechanism"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4784"}],"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=4784"}],"version-history":[{"count":81,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4784\/revisions"}],"predecessor-version":[{"id":5209,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/4784\/revisions\/5209"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=4784"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=4784"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=4784"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Key Words and Phrases: Privacy, Mechanism Design, Differential Privacy<\/h6>\n\n\n\n
1. Introduction<\/h3>\n\n\n\n
\ub2e4\ub9cc, \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \\(v_i\\)\uac00 \uc0c1\ud55c\uc120\uc744 \uac00\uc9c0\ub294 \uacbd\uc6b0\uc5d0\ub294 \ubcf4\uc0c1\uc774 \uac00\ub2a5\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n
\uc774\ub54c \ud589\uc704\uc790 \uc9d1\ub2e8\uc758 \ud06c\uae30\uac00 \uc99d\uac00\ud560\uc218\ub85d \uc784\uacc4\uac12\ub3c4 \uc99d\uac00\ud558\uba70, \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \ub9e4\uac1c\ubcc0\uc218 \u03b5 \uac12\uc740 \uac10\uc18c\ud558\uc5ec \uac15\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638\ub97c \uc81c\uacf5\ud560 \uc218 \uc788\ub3c4\ub85d \uc124\uacc4\ub41c\ub2e4. \uc989, \ucda9\ubd84\ud788 \ud070 \uc9d1\ub2e8\uc5d0\uc11c\ub294 \ub300\ubd80\ubd84\uc758 \ucc38\uc5ec\uc790\uac00 \ubcf4\uc0c1\uc744 \ubc1b\uc744 \uc218 \uc788\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n1.1. Our Contributions<\/h4>\n\n\n\n
1. \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998 \ubaa8\ub378\ub9c1<\/h5>\n\n\n\n
\uc774 \ubaa8\ub378\uc5d0\uc11c\ub294 \ucc38\uc5ec\uc790\uac00 \ub450 \uac00\uc9c0 \uc720\ud615\uc758 \uc815\ubcf4\ub97c \uac00\uc9c0\uace0 \uc788\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4:<\/p>\n\n\n\n\n
\uc774\uc5d0 \ubc18\ud574, \ubcf8 \ub17c\ubb38\uc5d0\uc11c\ub294 \ucc38\uc5ec\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \ud6a8\uc6a9\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc744 \ubcf4\uc218\uc801\uc778 \uc0c1\ud55c\uc120(conservative upper bound)\uc73c\ub85c \uc124\uc815\ud558\ub294 \ubc29\uc2dd\uc744 \uc81c\uc548\ud55c\ub2e4. \uc989, \ucc38\uc5ec\uc790\ub294 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \uc790\uc2e0\uc758 \ud6a8\uc6a9\uc744 \uc5bc\ub9c8\ub098 \uac10\uc18c\uc2dc\ud0a4\ub294\uc9c0 \uc815\ud655\ud788 \uc54c \ud544\uc694 \uc5c6\uc774, \uc5b4\ub290 \uc815\ub3c4 \uc0c1\ud55c\uc120\ub9cc \uc124\uc815\ud558\uba74 \ub41c\ub2e4.<\/p>\n\n\n\n2. \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998 \uad6c\ucd95<\/h5>\n\n\n\n
\n
3. \uc77c\ubc18\uc801\uc778 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc758 \uad6c\ucd95<\/h5>\n\n\n\n
\uc774\ud6c4, 5.2\uc808\uc5d0\uc11c\ub294 \uc6b0\ub9ac\uc758 \ud504\ub808\uc784\uc6cc\ud06c\uc5d0 \uc801\ud569\ud55c \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \ub514\uc9c0\ud138 \uc0c1\ud488 \ud310\ub9e4 \ubb38\uc81c\ub97c \uc0ac\ub840\ub85c \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n4. \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud55c \uba54\ucee4\ub2c8\uc998\uc774 \uc9c4\uc2e4\uc131\uc744 \ubcf4\uc7a5\ud560 \uc218 \uc788\ub294 \uc870\uac74<\/h5>\n\n\n\n
\uc989, \uac1c\ubcc4 \ud589\uc704\uc790\uc758 \uc815\ubcf4 \uc720\ucd9c\uc774 \ubbf8\uce58\ub294 \uc601\ud5a5\uc774 \uc791\uc744\uc218\ub85d, \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790\ub4e4\ub3c4 \uc9c4\uc2e4\ud558\uac8c \uc751\ub2f5\ud560 \uac00\ub2a5\uc131\uc774 \ub192\uc544\uc9c4\ub2e4.<\/mark><\/p>\n\n\n\n\ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uac00 \uc784\uc758\ub85c \ub192\uc744 \uacbd\uc6b0\uc758 \ubb38\uc81c<\/h5>\n\n\n\n
\uc774\ub7ec\ud55c \ubb38\uc81c\ub294 \ud2b9\ud788 \uac1c\uc778 \uc815\ubcf4 \ud310\ub9e4\ub97c \uc704\ud55c \uc9c4\uc2e4\ud55c(truthful) \uba54\ucee4\ub2c8\uc998 \uc124\uacc4\uc5d0\uc11c \uc911\uc694\ud55c \uc774\uc288\uc774\uba70, Ghosh and Roth(2011)\uc5d0\uc11c\ub3c4 \uc774\uc5d0 \ub300\ud55c \uc790\uc138\ud55c \ub17c\uc758\uac00 \uc774\ub8e8\uc5b4\uc84c\ub2e4.<\/p>\n\n\n\n\ud574\uacb0\ucc45: \ud504\ub77c\uc774\ubc84\uc2dc \uc784\uacc4\uac12 \ubc0f DP \uc801\uc6a9<\/h5>\n\n\n\n
\uc989, \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uac00 \\(v_{max}\\) \uc774\ud558\uc778 \uacbd\uc6b0\uc5d0\ub9cc \uc720\uc778 \ud638\ud658\uc131\uc744 \ubcf4\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n
\uc989, \uadf8\ub4e4\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uac00 \\(v_{max}\\)\ub97c \ucd08\uacfc\ud558\ub294\uc9c0 \uc5ec\ubd80 \uc790\uccb4\uac00 \ub178\ucd9c\ub418\uc9c0 \uc54a\ub3c4\ub85d \ubcf4\ud638\ud55c\ub2e4.<\/p>\n\n\n\nOther Related Work<\/h3>\n\n\n\n
Preliminaries<\/h3>\n\n\n\n
\ub450 \uac1c\uc758 \ubca1\ud130 \\(t, t^{\\prime} \\in T^n\\) \uc5d0 \ub300\ud574, \ud574\ubc0d \uac70\ub9ac(Hamming distance)<\/strong> \ub294 \ub450 \ubca1\ud130\uac00 \uc11c\ub85c \ub2e4\ub978 \uc704\uce58\uc758 \uac1c\uc218\ub85c \uc815\uc758\ub41c\ub2e4. \uc989, \\(| \\{ i : t_i \\neq t^{\\prime}_i \\} |\\)\ub97c \ud574\ubc0d \uac70\ub9ac\ub77c\uace0 \ud55c\ub2e4. \ud574\ubc0d \uac70\ub9ac\uac00 1\uc778 \ubca1\ud130 \uc30d\uc744 “\uc774\uc6c3(neighboring)”\uc774\ub77c\uace0 \ud55c\ub2e4.<\/p>\n\n\n\n\uc815\uc758 2.1 (\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc, Differential Privacy [Dwork et al., 2006])<\/h5>\n\n\n\n
\ub808\ub9c8 2.2 (\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\uac00 \uae30\ub300\uac12\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5)<\/h5>\n\n\n\n
3. Quantifying Information Utility<\/h3>\n\n\n\n
\uc77c\ubc18\uc801\uc778 \uae30\uacc4\uc801 \uc124\uacc4 \ubaa8\ub378\uc5d0\uc11c\ub294,<\/p>\n\n\n\n\n
\n
\uae30\uc874 \uc5f0\uad6c\uc5d0\uc11c \uc815\ubcf4 \ud6a8\uc6a9\uc744 \uc815\ub7c9\ud654\ud558\ub294 \ubc29\ubc95<\/h5>\n\n\n\n
1. McGrew et al.(2003)\uc758 \ubaa8\ub378<\/h6>\n\n\n\n
\n
2. Ghosh\uc640 Roth(2011)\uc758 \ubaa8\ub378<\/h6>\n\n\n\n
\uc774 \uc5f0\uad6c\uc5d0\uc11c\ub294, \ud589\uc704\uc790\uc758 \uc815\ubcf4 \uc720\ucd9c\ub85c \uc778\ud55c \ube44\ud6a8\uc6a9\uc774 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc \ub9e4\uac1c\ubcc0\uc218 \u03b5 \uc5d0 \ube44\ub840\ud55c\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4.<\/p>\n\n\n\n
\uadf8\ub7ec\ub098 \uc774 \uc811\uadfc \ubc29\uc2dd\uc5d0\ub294 \uba87 \uac00\uc9c0 \ubb38\uc81c\uc810\uc774 \uc788\ub2e4.<\/p>\n\n\n\n
\ub610\ud55c, \ud589\uc704\uc790 i \uc758 \uc815\ubcf4 \uc720\ucd9c\uc740 \ub2e4\ub978 \ud589\uc704\uc790\ub4e4\uc758 \uc785\ub825 \uac12\uc5d0\ub3c4 \uc758\uc874\ud560 \uc218 \uc788\ub2e4.
\uc774 \ubaa8\ub378\uc740 \ud589\uc704\uc790\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uc120\ud638\ub3c4 \\(v_i\\) \uc790\uccb4\uac00 \uc720\ucd9c\ub420 \uc218 \uc788\ub294 \ubb38\uc81c\ub97c \uace0\ub824\ud558\uc9c0 \uc54a\ub294\ub2e4.<\/p>\n\n\n\n3. Xiao(2011)\uc758 \ubaa8\ub378<\/h6>\n\n\n\n
\uc815\ubcf4 \uc720\ucd9c \ube44\ud6a8\uc6a9\uc744 \ub2e4\uc74c\uacfc \uac19\uc774 \uc815\ub7c9\ud654\ud558\uc600\ub2e4.<\/p>\n\n\n\n
\uc989, \\(v_i\\) \uac00 \ud074\uc218\ub85d \uc815\ubcf4 \uc720\ucd9c\uc5d0 \ub300\ud55c \ube44\ud6a8\uc6a9\uc774 \ucee4\uc9c0\uace0, \ud589\uc704\uc790\uc758 \uc804\ub7b5 \\(\\sigma\\) \ub3c4 \uc601\ud5a5\uc744 \ubbf8\uce5c\ub2e4.
\ud558\uc9c0\ub9cc \uc774 \uc811\uadfc \ubc29\uc2dd\uc5d0\ub3c4 \ud55c\uacc4\uac00 \uc788\ub2e4.
\ud589\uc704\uc790\uc758 \uc815\ubcf4 \uc720\ucd9c \ube44\ud6a8\uc6a9\uc774 \ud589\uc704\uc790\uc758 \uc804\ub7b5 \\(\\sigma\\) \uc5d0 \uc758\ud574 \uacb0\uc815\ub418\ub294 \uac83\uc740 \ubd84\uc11d\uc801\uc73c\ub85c \ub2e4\ub8e8\uae30 \uc5b4\ub824\uc6b4 \ubb38\uc81c\ub97c \ucd08\ub798\ud560 \uc218 \uc788\ub2e4. \ud2b9\uc815\ud55c \uc804\ub7b5\uc744 \uc120\ud0dd\ud560 \uacbd\uc6b0, \uc815\ubcf4 \uc720\ucd9c\uc758 \uc601\ud5a5\uc744 \uc644\uc804\ud788 \uc81c\uac70\ud558\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n\uc608\uc81c 3.1 (“\ud638\ubc00\ube75 \ub610\ub294 \ud1b5\ubc00\ube75” \uac8c\uc784, The \u201cRye or Wholewheat\u201d game)<\/h5>\n\n\n\n
Bob\uc740 \uc790\uc2e0\uc774 \uac00\uc7a5 \uc88b\uc544\ud558\ub294 \uc0cc\ub4dc\uc704\uce58\ub97c \uba39\uace0 \uc2f6\uc9c0\ub9cc, Alice\uac00 \uc790\uc2e0\uc758 \uc120\ud638\ub3c4\ub97c \uc54c\uac8c \ub418\ub294 \uac83\uc740 \uc6d0\ud558\uc9c0 \uc54a\ub294\ub2e4.
\uc774\uc81c Bob\uc758 \uc720\ud615(type)\uc774 \\(\\{ R, W \\}\\)\uc5d0\uc11c \uade0\ub4f1\ud558\uac8c \uc120\ud0dd\ub41c\ub2e4\uace0 \uac00\uc815\ud558\uace0, Bob\uc774 \ucde8\ud560 \uc218 \uc788\ub294 \ub450 \uac00\uc9c0 \uc804\ub7b5\uc744 \uc0b4\ud3b4\ubcf4\uc790.<\/p>\n\n\n\n
\ud558\uc9c0\ub9cc, Alice\ub294 Bob\uc758 \uc120\ud638\ub3c4\ub97c \uc815\ud655\ud788 \uc54c\uac8c \ub418\ubbc0\ub85c \uc815\ubcf4 \uc720\ucd9c \ube44\ud6a8\uc6a9\uc774 \ucd5c\ub300\ud654\ub41c\ub2e4.
\uc0c1\ud638 \uc815\ubcf4\ub7c9(mutual information)\uc740 \ub2e4\uc74c\uacfc \uac19\ub2e4.<\/p>\n\n\n\n
\ud558\uc9c0\ub9cc, Bob\uc758 \uc751\ub2f5\uc774 \uc2e4\uc81c \uc120\ud638\ub3c4\uc640 \ubb34\uad00\ud558\ubbc0\ub85c \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc774 \uc804\ud600 \ubc1c\uc0dd\ud558\uc9c0 \uc54a\ub294\ub2e4.
\uc989, Alice\ub294 Bob\uc758 \uc120\ud638\ub3c4\ub97c \uc804\ud600 \uc720\ucd94\ud560 \uc218 \uc5c6\ub2e4.
\uc0c1\ud638 \uc815\ubcf4\ub7c9\uc740 \ub2e4\uc74c\uacfc \uac19\ub2e4.<\/p>\n\n\n\n
\uc989, Bob\uc774 \uc5b4\ub5a4 \uc804\ub7b5\uc744 \uc0ac\uc6a9\ud558\ub4e0 Alice\uac00 \uacb0\uacfc\ub97c \ubcf4\uace0 \uc774\ub97c \uad6c\ubcc4\ud560 \uc218 \uc5c6\ub2e4.
\ud558\uc9c0\ub9cc \uc815\ubcf4 \uc774\ub860\uc801 \uad00\uc810\uc5d0\uc11c \ubcf4\uba74, \ub450 \uc804\ub7b5 \uac04 \uc0c1\ud638 \uc815\ubcf4\ub7c9\uc740 \uadf9\uba85\ud558\uac8c \ucc28\uc774\uac00 \ub098\uba70, \uc774\ub294 Alice\uac00 Bob\uc758 \uc720\ud615\uc744 \uc5b4\ub290 \uc815\ub3c4 \ud559\uc2b5\ud558\ub294\uc9c0 \uc5ec\ubd80\ub97c \ub098\ud0c0\ub0b8\ub2e4.<\/p>\n\n\n\n\uc774 \ubb38\uc81c\uc758 \ud575\uc2ec \uc6d0\uc778<\/h6>\n\n\n\n
\ub2e4\ub9cc, \uc774\ub294 Bob\uc774 \ubb34\uc791\uc704 \uc804\ub7b5 \\(\\sigma_{\\text{random}}\\) \uc744 \uc0ac\uc6a9\ud588\uae30 \ub54c\ubb38\uc774 \uc544\ub2c8\ub77c, Alice\uac00 Bob\uc758 \uc804\ub7b5\uc744 \uc54c\uc9c0 \ubabb\ud558\uae30 \ub54c\ubb38\uc774\ub2e4.
\uc989, Alice\uac00 Bob\uc758 \uc804\ub7b5\uc744 \uad00\ucc30\ud560 \uc218 \uc5c6\ub294 \uc0c1\ud669\uc5d0\uc11c\ub294, \ubb34\uc791\uc704 \uc804\ub7b5 \\(\\sigma_{\\text{random}}\\) \uc744 \uc0ac\uc6a9\ud560 \ud544\uc694 \uc5c6\uc774 \ub2e8\uc21c\ud55c \uc9c4\uc2e4 \uc751\ub2f5 \\(\\sigma_{\\text{truthful}}\\) \ub3c4 \uac19\uc740 \uacb0\uacfc\ub97c \ub9cc\ub4e4 \uc218 \uc788\ub2e4.
\ub530\ub77c\uc11c, \uc815\ubcf4 \ube44\uc6a9(information cost) \uac1c\ub150\uc740 Alice\uac00 Bob\uc758 \uc804\ub7b5\uc744 \uc54c\uace0 \uc788\ub294\uc9c0 \uc5ec\ubd80\uc640 \ubb34\uad00\ud558\uac8c \uc815\uc758\ub418\uc5b4\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n3.1. Our Approach<\/h4>\n\n\n\n
\uc774\ub97c \uc124\uba85\ud558\uae30 \uc704\ud574, \uae30\uc874 \uc5f0\uad6c\uc5d0\uc11c \ub17c\uc758\ub41c \uc815\ubcf4 \ud6a8\uc6a9 \uce21\uc815 \ubc29\uc2dd\uc744 \ub2e4\uc2dc \uc0b4\ud3b4\ubcf4\uc790.<\/p>\n\n\n\n1. \uae30\uc874 \uc5f0\uad6c\uc5d0\uc11c\uc758 \uc815\ubcf4 \ud6a8\uc6a9 \ud55c\uacc4\uc810 \ubd84\uc11d<\/h5>\n\n\n\n
\ud558\uc9c0\ub9cc, \uc774 \ucd5c\uc545\uc758 \uacbd\uc6b0(worst-case)\uac00 \uc2e4\uc81c\ub85c \ubc1c\uc0dd\ud560 \ud655\ub960\uc740 \ub9e4\uc6b0 \ub0ae\uc744 \uac00\ub2a5\uc131\uc774 \ub192\ub2e4.
\ub530\ub77c\uc11c, \\(v_i \\cdot \\epsilon\\) \uc774 \uc815\ubcf4 \ud6a8\uc6a9\uc744 \uc815\ud655\ud788 \uce21\uc815\ud558\ub294 \uac12\uc740 \uc544\ub2d0 \uc218 \uc788\uc9c0\ub9cc, \uc815\ubcf4 \ud6a8\uc6a9\uc758 \uc0c1\ud55c(upper bound)\uc73c\ub85c\ub294 \uc801\uc808\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n
\ub530\ub77c\uc11c, \\(v_i \\cdot I(t_i; M(t))\\) \ub3c4 \uc815\ubcf4 \ud6a8\uc6a9\uc758 \uc0c1\ud55c\uc73c\ub85c \uc0ac\uc6a9\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n
\ub530\ub77c\uc11c, \uc6b0\ub9ac\ub294 \uc815\ubcf4 \ud6a8\uc6a9\uc758 \uc0c1\ud55c\uc744 \\(v_i \\cdot \\epsilon\\) \uc73c\ub85c \uc0ac\uc6a9\ud558\uae30\ub85c \ud55c\ub2e4.<\/p>\n\n\n\n2. \uc6b0\ub9ac\uc758 \uc815\ubcf4 \ud6a8\uc6a9 \uac1c\ub150\uc758 \ucc28\ubcc4\uc810<\/h5>\n\n\n\n
\n
\ub530\ub77c\uc11c, \uc815\ubcf4 \ud6a8\uc6a9\uc758 \uc0c1\ud55c\uc740 \uc774\ub7ec\ud55c \ubbf8\ub798\uc758 \ud6a8\uc6a9 \uc190\uc2e4\uc744 \ubc18\uc601\ud574\uc57c \ud55c\ub2e4.
\ub808\ub9c8 2.2\ub97c \uc801\uc6a9\ud558\uba74, \uc815\ubcf4 \uc720\ucd9c\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \uc0c1\ud55c\uc744 \uac00\uc9c8 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n
\uc989, \\(v_i \\cdot \\epsilon\\) \uc740 \uc815\ubcf4 \uc720\ucd9c\ub85c \uc778\ud574 \ubbf8\ub798 \ud6a8\uc6a9\uc774 \uac10\uc18c\ud558\ub294 \uc815\ub3c4\uc758 \uc0c1\ud55c\uc744 \uc81c\uacf5\ud55c\ub2e4.<\/p>\n\n\n\n3. \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \ubc0f \uc9c4\uc2e4\uc131 \ubcf4\uc7a5<\/h5>\n\n\n\n
\uc989, \uc5b4\ub5a4 \ud589\uc704\uc790\uac00 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ub192\uac8c \ud3c9\uac00\ud558\ub294\uc9c0\ub97c \uacf5\uac1c\uc801\uc73c\ub85c \uc54c \uc218 \uc788\uc73c\uba70, \uc774\ub294 \ucd94\uac00\uc801\uc778 \uc815\ubcf4 \uc720\ucd9c \ubb38\uc81c\ub97c \ucd08\ub798\ud560 \uc218 \uc788\ub2e4.
\ub610\ud55c, \\(v_i\\) \uac00 \ubb34\ud55c\ub300\ub85c \uc124\uc815\ub420 \uc218 \uc788\ub2e4\uba74, \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc5d0 \ub300\ud55c \ubcf4\uc0c1\uc744 \uc81c\uacf5\ud558\uba74\uc11c\ub3c4 \ucda9\ubd84\ud55c \ub370\uc774\ud130\ub97c \uad6c\ub9e4\ud558\ub294 \uac83\uc774 \ubd88\uac00\ub2a5\ud574\uc9c4\ub2e4.<\/p>\n\n\n\n
\ud589\uc704\uc790 \uc218 n \uc774 \uc99d\uac00\ud560\uc218\ub85d \\(\\epsilon\\) \uc740 \uac10\uc18c\ud558\uc5ec, \ub354 \uac15\ub825\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638\ub97c \uc81c\uacf5\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n
\uc5ec\uae30\uc11c, \\(v_{\\max}\\) \ub294 \ub9e4\uc6b0 \uc57d\ud55c \uac00\uc815\ud558\uc5d0\uc11c\ub3c4 n \uc774 \uc99d\uac00\ud560\uc218\ub85d \ud568\uaed8 \uc99d\uac00\ud558\ub3c4\ub85d \uc124\uc815\ub41c\ub2e4.
\ub610\ud55c, n \uc774 \uc99d\uac00\ud560\uc218\ub85d \\(v_i > v_{\\max}\\) \ub97c \ub9cc\uc871\ud558\ub294 \ud589\uc704\uc790\uc758 \ube44\uc728\uc740 \uc810\uc810 \uac10\uc18c\ud55c\ub2e4.<\/p>\n\n\n\n4. The Model<\/h3>\n\n\n\n
1. \uba54\ucee4\ub2c8\uc998 (The Mechanism)<\/h4>\n\n\n\n
\uc9c1\uc811 \uc120\uc5b8 \uba54\ucee4\ub2c8\uc998(Direct revelation mechanisms)<\/mark> \uc744 \uace0\ub824\ud558\uba70, \uc774\ub294 \ud589\uc704\uc790\ub4e4\uc774 \uc790\uc2e0\uc758 \uc720\ud615\uc744 \uba54\ucee4\ub2c8\uc998\uc5d0 \uc9c1\uc811 \ubcf4\uace0\ud55c \ud6c4, \uba54\ucee4\ub2c8\uc998\uc774 \uc0ac\ud68c\uc801 \ub300\uc548 \\(s \\in S\\) \ub97c \uc120\ud0dd\ud558\uace0 \uacf5\uac1c\ud558\ub294 \ubc29\uc2dd\uc774\ub2e4.
\ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \uc815\ud655\ud788 \ud3c9\uac00\ud558\uae30 \uc704\ud574, \ud589\uc704\uc790\uc758 \uac1c\ubcc4 \uc720\ud615 \uc815\ubcf4 \ubc0f \uae08\uc804\uc801 \ubcf4\uc0c1 \uc5ec\ubd80\ub294 \uc554\ud638\ud559\uc801 \uae30\ubc95 \ub4f1\uc744 \ud65c\uc6a9\ud558\uc5ec \uc644\uc804\ud788 \uc228\uae34\ub2e4\uace0 \uac00\uc815\ud55c\ub2e4.<\/p>\n\n\n\n2. \ubaa9\uc801 \ud568\uc218 (The Objective Function)<\/h4>\n\n\n\n
\ud568\uc218 f \uc758 \ubbfc\uac10\ub3c4(Sensitivity) \\(\\Delta f\\)<\/mark> \ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc815\uc758\ub41c\ub2e4.<\/p>\n\n\n\n
\ub610\ud55c, \ubaa8\ub4e0 s \uc5d0 \ub300\ud574 \ucd5c\uc18c\uac12\uc774 0\uc774\ub77c\uace0 \uac00\uc815\ud558\uba70, \uc774\uc5d0 \ub530\ub77c f(t, s) \uac12\uc758 \ubc94\uc704\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc81c\ud55c\ub41c\ub2e4.<\/p>\n\n\n\n3. \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uace0\ub824\ud558\ub294 \ud589\uc704\uc790 (Privacy-Aware Agents)<\/h4>\n\n\n\n
\uc989, \ud589\uc704\uc790\uc758 \ucd1d \ud6a8\uc6a9\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \ub450 \uac00\uc9c0 \uc694\uc18c\uc758 \ud569\uc73c\ub85c \uc815\uc758\ub41c\ub2e4.<\/p>\n\n\n\n
\uc5ec\uae30\uc11c T \ub294 \uae30\uc874 \uc720\ud615 \uacf5\uac04(traditional game type)\uc774\uace0, \\(v_i\\) \ub294 \ud589\uc704\uc790\uac00 \uc790\uc2e0\uc758 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc5bc\ub9c8\ub098 \uc911\uc694\ud558\uac8c \uc0dd\uac01\ud558\ub294\uc9c0\ub97c \ub098\ud0c0\ub0b4\ub294 \uac12\uc774\ub2e4.
\ud589\uc704\uc790\ub294 \uc790\uc2e0\uc758 \uc804\uccb4 \uc720\ud615 \\((t_i, v_i)\\) \uc5d0 \ub300\ud55c \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uac71\uc815\ud558\uba70, \uc815\ubcf4 \uc720\ucd9c\uc740 \\(t_i\\) \uc640 \\(v_i\\) \ub450 \uac00\uc9c0 \ubaa8\ub450\uc5d0 \ub300\ud574 \ubc1c\uc0dd\ud560 \uc218 \uc788\ub2e4.
\ub530\ub77c\uc11c, \ub2e8\uc21c\ud788 \\(v_i\\) \ub97c \uacf5\uac1c\ud558\ub294 \uac83\uc740 \ubd88\uac00\ub2a5\ud558\ub2e4.
\ubaa8\ub4e0 \ud589\uc704\uc790\ub4e4\uc758 \uc720\ud615 \ubca1\ud130\ub294 \\(t = (t_1, \\dots, t_n), v = (v_1, \\dots, v_n)\\) \ub85c \ub098\ud0c0\ub0bc \uc218 \uc788\ub2e4.<\/p>\n\n\n\n4. \ud589\uc704\uc790\uc758 \ud6a8\uc6a9 \ud568\uc218 \uc815\uc758<\/h4>\n\n\n\n
\uc911\uc694\ud55c \ucc28\uc774\uc810\uc740 \\(u_i^{\\text{out}}\\) \ub294 \ub2e8\uc21c\ud788 \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc(\uc120\ud0dd\ub41c s) \uc5d0\ub9cc \uc758\uc874\ud558\ub294 \ubc18\uba74, \\(u_i^{\\text{inf}}\\) \ub294 \uba54\ucee4\ub2c8\uc998 \uc790\uccb4\uc5d0\ub3c4 \uc758\uc874\ud55c\ub2e4\ub294 \uc810\uc774\ub2e4.<\/p>\n\n\n\n5. \ucc38\uc5ec\ud558\ub294 \ud589\uc704\uc790(Participating Agents)\uc640 \uadfc\uc0ac \ucd5c\uc801\ud654<\/h4>\n\n\n\n
\uba54\ucee4\ub2c8\uc998\uc740 \ub2e4\uc74c \uc870\uac74\uc744 \ub9cc\uc871\ud560 \ub54c f \ub97c \uadfc\uc0ac\uc801\uc73c\ub85c(approximately) \uad6c\ud604\ud55c\ub2e4\uace0 \ud55c\ub2e4.
\ucc38\uc5ec\ud558\ub294 \ud589\uc704\uc790\ub4e4\uc774 \uc9c4\uc2e4\ud558\uac8c \uc751\ub2f5\ud55c\ub2e4\uace0 \uac00\uc815\ud558\uace0, \ub098\uba38\uc9c0 \ud589\uc704\uc790\ub4e4\uc774 \uc784\uc758\uc758 \ud589\ub3d9\uc744 \ud560 \ub54c, \uba54\ucee4\ub2c8\uc998\uc758 \uacb0\uacfc s \uac00 f \ub97c \uadfc\uc0ac\uc801\uc73c\ub85c \ucd5c\uc801\ud654\ud558\ub294 \uacbd\uc6b0.<\/p>\n\n\n\n5. A Generic Construction of Privacy-Aware Mechanisms<\/h3>\n\n\n\n
\uc774\ub97c \uc704\ud574, \uba3c\uc800 \uac04\ub2e8\ud55c \ud22c\ud45c \ubb38\uc81c(pooling problem)\ub97c \ud1b5\ud574 \ud575\uc2ec \uae30\ubc95\uc744 \uc124\uba85\ud55c \ud6c4, \ubcf4\ub2e4 \uc77c\ubc18\uc801\uc778 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\ucd95\ud558\ub294 \ubc29\ubc95\uc744 \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n1. \uac04\ub2e8\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \ud22c\ud45c \uba54\ucee4\ub2c8\uc998<\/h6>\n\n\n\n
\uc989, \ucc38\uc5ec\uc790\uac00 \uc790\uc2e0\uc758 \uc815\ubcf4\ub97c \uc18d\uc5ec\uc11c \uc5bb\ub294 \uc774\ub4dd\ubcf4\ub2e4, \uc815\uc9c1\ud558\uac8c \uc751\ub2f5\ud558\uc9c0 \uc54a\uc558\uc744 \ub54c \ubc1c\uc0dd\ud558\ub294 \uc190\uc2e4\uc774 \ub354 \ud06c\ub3c4\ub85d \uc870\uc815\ud55c\ub2e4.
\uc774\ub97c \ud1b5\ud574, \ucc38\uc5ec\uc790\uac00 \uc790\uc2e0\uc758 \uc815\ubcf4\ub97c \uc18d\uc5ec\uc11c \uc5bb\ub294 \uc774\ub4dd\ubcf4\ub2e4, \uc815\uc9c1\ud558\uac8c \uc751\ub2f5\ud558\uc9c0 \uc54a\uc558\uc744 \ub54c \ubc1c\uc0dd\ud558\ub294 \uc190\uc2e4\uc774 \ub354 \ud06c\ub3c4\ub85d \uc870\uc815\ud55c\ub2e4.<\/p>\n\n\n\n
\ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uac00 \uc784\uacc4\uac12 \\(v_{max}\\) \uc774\ud558\uc778 \uacbd\uc6b0: \ud574\ub2f9 \ucc38\uc5ec\uc790\ub294 \uc790\uc2e0\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc5d0 \ub300\ud574 \uacf5\uc815\ud55c \ubcf4\uc0c1\uc744 \ubc1b\ub3c4\ub85d \uba54\ucee4\ub2c8\uc998\uc744 \uc124\uacc4\ud55c\ub2e4.
\ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00\uac00 \\(v_{max}\\)\ub97c \ucd08\uacfc\ud558\ub294 \uacbd\uc6b0: \ud574\ub2f9 \ucc38\uc5ec\uc790\ub294 \ubcf4\uc0c1\uc744 \ubc1b\uc744 \uc218 \uc5c6\uc9c0\ub9cc, \ub300\uc2e0 \uadf8\ub4e4\uc758 \ud504\ub77c\uc774\ubc84\uc2dc \ud3c9\uac00 \uc815\ubcf4 \uc790\uccb4\ub97c \\(\\epsilon\\)-DP \ubc29\uc2dd\uc73c\ub85c \ubcf4\ud638\ud55c\ub2e4.<\/p>\n\n\n\n2. \ub300\uaddc\ubaa8 \uc778\uad6c \uc9d1\ub2e8\uc744 \uc704\ud55c \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uba54\ucee4\ub2c8\uc998<\/h6>\n\n\n\n
\uc774 \uac00\uc815\ud558\uc5d0\uc11c, \ub300\ubd80\ubd84\uc758 \ucc38\uc5ec\uc790\ub294 \uc720\uc778 \ud638\ud658\uc131\uc744 \uc720\uc9c0\ud558\uba74\uc11c\ub3c4 \uc815\uc9c1\ud558\uac8c \uc751\ub2f5\ud558\ub294 \uac83\uc774 \ud569\ub9ac\uc801\uc778 \uc120\ud0dd\uc774 \ub41c\ub2e4.
\uc774\ub7ec\ud55c \uc811\uadfc \ubc29\uc2dd\uc740 \ub300\uaddc\ubaa8 \uc778\uad6c \uc9d1\ub2e8\uc5d0\uc11c\ub294 \uac1c\ubcc4 \ucc38\uc5ec\uc790\uc758 \ub370\uc774\ud130\uac00 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc774 \ubbf8\ubbf8\ud558\uae30 \ub54c\ubb38\uc774\ub2e4.
\uc989, \uac1c\ubcc4 \ucc38\uc5ec\uc790\uc758 \uc785\ub825\uc774 \uacb0\uacfc\uc5d0 \ubbf8\uce58\ub294 \uc601\ud5a5\uc774 \uc791\uc73c\uba74, \uc815\ubcf4 \uc720\ucd9c\uc5d0 \ub530\ub978 \ud6a8\uc6a9 \uac10\uc18c\ubcf4\ub2e4, \uc815\uc9c1\ud55c \uc751\ub2f5\uc744 \ud588\uc744 \ub54c \uc5bb\ub294 \uc774\ub4dd\uc774 \ub354 \ucee4\uc9c8 \uac00\ub2a5\uc131\uc774 \ub192\ub2e4.<\/p>\n\n\n\n3. <\/h6>\n\n\n\n
References<\/h4>\n\n\n\n