Abstract
최근 연구에서는 진실성과 차등 프라이버시를 동시에 보장하는 경제적 메커니즘을 설계했다. 이러한 메커니즘에서는 프라이버시가 진실성과 별개로 취급되며, 플레이어의 효용 함수에 포함되지 않는다(그리고 이를 포함할 경우 일부 경우에서 비진실성이 발생하는 것으로 나타났다). 본 연구에서는 플레이어의 효용 함수에서 프라이버시를 모델링하는 새로운 일반적인 방법을 제안한다.
구체적으로, 어떤 결과 o 가 플레이어 i 의 모든 보고 값에서 거의 동일한 확률로 도출된다면, 해당 결과 o 는 플레이어 i 에게 작은 프라이버시 비용을 가진다고 가정한다. 우리는 이러한 프라이버시 모델링에 대해 진실성을 보장하는 세 가지 메커니즘을 제시한다.
1. 두 후보 간의 선거(Election between two candidates)
2. 이산적인 시설 위치 선정 문제(Discrete version of the facility location problem)
3. 이산적 효용을 가진 일반적인 사회적 선택 문제(General social choice problem with discrete utilities, VCG와 유사한 메커니즘을 사용)
또한, 플레이어 수 n 이 증가함에 따라, 우리의 메커니즘이 달성하는 사회적 후생(social welfare)이 최적값에 점진적으로 수렴한다(n 의 비율로 최적에 접근함).
Additional Key Words and Phrases: Differential privacy, mechanism design, truthfulness, social choice, VCG
1. Introduction
이 논문에서는 메커니즘 설계(mechanism design)와 차등 프라이버시(differential privacy) 간의 상호작용을 분석한다. 특히, 플레이어의 효용 함수(utility function)에 프라이버시를 명시적으로 포함하고, 이를 고려한 진실한(truthful) 메커니즘을 설계하는 것이 목표다.
우리의 연구는 두 가지 분야의 동기에서 출발한다.
1. 메커니즘 설계에서의 문제점:
기존 연구에서는 플레이어가 단순히 결과(예: 경매에서 누가 낙찰되는지, 병원이 어디에 위치하는지)에 대해서만 선호를 가진다고 가정했다. 그러나 실제로는 플레이어가 자신의 개인 정보가 타인에게 노출되는 것 자체를 우려하여 기존의 경제적 분석과 다르게 행동할 가능성이 있다.
예를 들어, 어떤 사람이 경매에서 특정 상품에 대한 높은 가치를 보고하면, 그 사람의 선호도가 노출될 수 있으며, 병원 위치에 민감한 사람은 자신의 의료 상태를 간접적으로 드러낼 위험이 있다.
기존의 메커니즘 설계 연구들은 이러한 프라이버시 문제를 제대로 모델링하지 않았기 때문에, 차등 프라이버시를 활용한 새로운 접근 방식이 필요하다.
2. 차등 프라이버시의 필요성:
차등 프라이버시(Dwork et al. 2006)는 데이터베이스의 통계 분석 시 개별 참여자의 데이터가 결과에 미치는 영향을 제한하는 개념이다. 즉, 단일 개인의 데이터가 변경되어도 알고리즘의 출력 분포가 크게 변하지 않는다면, 해당 알고리즘은 차등 프라이버시를 만족한다고 볼 수 있다.
차등 프라이버시는 절대적인 개념이 아니라 개인의 프라이버시 보호 수준과 전체 통계적 정확성 간의 트레이드오프를 조정하는 방식이다. 하지만 기존 연구는 개인의 프라이버시 보호가 그 개인의 목표(예: 효용 극대화)와 어떻게 조화될 수 있는지에 대한 논의가 부족했다.
이러한 문제를 해결하기 위해, 우리는 메커니즘 설계와 차등 프라이버시를 결합하여 프라이버시 보호와 개인의 경제적 목표 간의 균형을 고려하는 새로운 모델을 제안한다. 이를 통해 프라이버시의 의미와 가치를 보다 깊이 이해할 수 있을 것으로 기대한다.
1.1. Previous Work
1.2. Our Contributions
이 논문에서 우리는 플레이어의 효용 함수에서 프라이버시를 모델링하는 새로운, 보다 일반적인 방법을 제안한다. Xiao의 상호 정보(mutual information) 측정 방식과 달리, 우리의 모델은 플레이어 유형(type)에 대한 사전 확률(prior)을 가정할 필요가 없으며, 점별(pointwise) 모델이다. 즉, 우리는 단순히 어떤 결과 o 가 플레이어 i 의 모든 보고에서 거의 동일한 확률로 도출된다면, 해당 결과 o 는 플레이어 i 에게 작은 프라이버시 비용을 가진다고 가정한다.
이 가정을 설정한 동기 중 하나는, 이러한 결과 o 가 Bayesian 적대자가(즉, 베이지안 모델을 사용하여 플레이어의 정보를 추론하려는 존재) 플레이어 i 에 대한 신념을 거의 변화시키지 않을 것이기 때문이다(다른 플레이어들의 보고를 고려했을 때). 이 가정은 Dwork와 McSherry의 차등 프라이버시에 대한 Bayesian 해석에서 영감을 얻었으며, Kasiviswanathan과 Smith [2008]에서 설명되었다.
Xiao의 상호 정보 측정 방식은 엄밀히 말해 우리의 모델의 특수한 경우는 아니지만, 부록에서 우리는 우리의 모델에 대한 진실성이 Xiao의 모델에 대한 진실성을 함의함을 보인다.
이 모델을 바탕으로, 우리는 프라이버시 비용이 진실한 응답으로 인한 결과 효용(outcome-utility) 이득보다 작은 메커니즘을 설계할 수 있음을 보인다. 구체적으로, 우리는 우리의 프라이버시 모델에 대해 진실성을 보장하는 세 가지 메커니즘을 제시한다.
1. 두 후보 간의 선거(election between two candidates)
2. 이산적인 시설 위치 선정 문제(discrete version of the facility location problem)
3. 이산적 효용을 가진 일반적인 사회적 선택 문제(general social choice problems with discrete utilities, VCG와 유사한 메커니즘을 사용)
또한, 플레이어 수 n 이 증가함에 따라, 우리의 메커니즘이 달성하는 사회적 후생(social welfare)이 최적값에 점진적으로 수렴한다(n 의 비율로 최적에 접근).
우리의 아이디어를 설명하기 위해, 두 후보 간의 선거를 고려하자. 각 플레이어는 한 후보에 대해 뚜렷한 선호를 가지고 있지만, 프라이버시 문제로 인해 선호를 공개하는 것을 주저할 수도 있다. 이러한 선거를 차등 프라이버시를 유지하면서 수행하려면, 우리는 노이즈를 추가한 다수결 방식(noisy majority vote)을 사용할 수 있다. 즉,
- 각 투표자의 선택을 기반으로 다수결 규칙을 적용하되,
- 차등 프라이버시 파라미터 \(\epsilon\) 에 따라 크기가 \(O(1/\epsilon)\) 인 랜덤 노이즈를 추가한다.
- 여기서 \(\epsilon\) 은 각 플레이어의 투표가 최종 결과에 미치는 영향을 제한하는 역할을 한다.
이제 \(\epsilon\) 을 줄이면, 플레이어가 경험하는 프라이버시 비용도 줄어든다. 하지만 단순히 \(\epsilon\) 에 의해 전체 프라이버시 비용을 제한하는 것만으로는 선거 메커니즘의 진실성을 보장할 수 없다.
예를 들어, 한 후보가 전체 유권자의 2/3의 지지를 받는 편향된(skewed) 선거를 고려해보자.
이 경우, 단일 플레이어의 투표가 결과를 바꿀 확률은 \(e^{-\epsilon n}\) 에 비례하여 기하급수적으로 작아진다(여기서 n 은 유권자 수).
만약 플레이어의 전체 프라이버시 비용이 \(O(\epsilon)\) 까지 증가할 수 있다면, \(\epsilon\) 을 매우 작게 설정해야 하며, 이는 \(O(1/n)\) 수준까지 작아질 수 있다.
그러나 \(\epsilon\) 이 너무 작아지면, 과도한 노이즈가 추가되어 사회적 후생이 심각하게 희생된다.
우리는 편향된 선거에서 진실한 응답의 전체 프라이버시 비용 역시 기하급수적으로 작아져야 한다고 주장한다.
대부분의 랜덤 노이즈 설정에서는 플레이어가 자신의 보고를 변경해도 결과에 영향을 미칠 수 없다.
따라서 플레이어가 진실하게 보고하든 거짓으로 보고하든, 경험하는 프라이버시 비용은 동일해야 한다.
결과에 영향을 미칠 수 있는 극히 일부의 경우에서는, 진실하게 보고할 때 플레이어가 얻게 되는 결과 효용(outcome utility) 증가가 프라이버시 비용보다 훨씬 크다.
즉, 플레이어가 자신의 보고를 변경할 때 발생하는 기대 프라이버시 비용 변화는 \(\epsilon\) 에 비례하며, 이는 결과가 변경될 확률의 최대 \(O(\epsilon)\) 배를 넘지 않는다.
그러나 편향된 선거와 같은 상황에서는 이 확률이 매우 작아지기 때문에, 전반적인 프라이버시 비용 증가도 작게 유지할 수 있다.
이 분석은 우리가 “개별 결과(per-outcome) 프라이버시 모델”을 채택한 것의 핵심적인 장점이며, Dwork et al. [2010]의 연구를 일반화한 결과로 볼 수 있다.
Dwork et al. [2010]은 모든 \(\epsilon\)-차등 프라이버시 메커니즘은 실제 기대 프라이버시 손실이 \(O(\epsilon^2)\) 에 불과함을 증명한 바 있다.
우리의 이산적 시설 위치 선정(discrete facility location) 메커니즘은 Xiao [2013]의 메커니즘에서 영감을 받았다. Xiao는 해당 메커니즘이 차등 프라이버시를 만족하고 진실성을 보장함을 증명했지만, 이는 플레이어의 효용 함수에 프라이버시 비용을 포함하지 않은 경우에 한정되었다. 우리의 접근 방식은 앞서 설명한 분석을 적용할 수 있도록 몇 가지 변형을 추가한 것이다.
선거(election) 및 시설 위치 선정(facility location) 메커니즘의 경우, 이전에 설명한 분석 방식을 적용하면 모든 랜덤 코인의 선택(random coins)의 경우에도 진실성이 성립하는(universal truthfulness) 메커니즘이 된다.
반면, 일반적인 사회적 선택 문제(general social choice problem)를 해결하는 VCG 유사(VCG-like) 메커니즘의 경우, 지급(payments)이 프라이버시를 손상시키지 않도록 추가적인 조치를 취해야 한다.
이로 인해 해당 메커니즘은 기대값에서만 진실성을 보장(expectation truthfulness)하게 된다.
기존 연구들과 달리, 우리는 차등 프라이버시를 그 자체로 목표(end)로 삼지 않고, 프라이버시를 중시하는 플레이어로부터 진실한 응답을 유도하는 수단(means)으로 활용한다.
즉, 우리는 반드시 차등 프라이버시 파라미터 \(\epsilon\) 을 매우 작게(높은 프라이버시 보호, 하지만 사회적 후생 손실 증가) 설정할 필요가 없다.
대신, 프라이버시 비용이 플레이어의 결과에 대한 선호(outcome preference)를 초과하지 않도록 충분히 작게 설정하는 것만으로도 충분하다.
특히, 우리의 분석에 따르면 \(\epsilon\) 을 감소시키면 플레이어가 결과에 미치는 영향력은 줄어들지만, 기대 프라이버시 비용은 훨씬 빠르게 감소한다.
따라서, 플레이어가 결과에 대한 선호가 프라이버시보다 훨씬 크다면, \(\epsilon\) 의 최적값은 비교적 클 수도 있으며, 이때 프라이버시 비용은 무시할 수 있을 정도로 작아지고, 플레이어는 진실하게 응답할 유인을 가지게 된다.
또한, 우리는 프라이버시 가치를 고려한 인센티브 분석을 통해, 플레이어들이 실제로 진실한 응답을 하도록 유도할 수 있으며, 그 결과 사회적 후생이 최적에 가깝게 수렴할 것임을 보다 확신할 수 있다.
적절한 \(\epsilon\) 값의 설정은 플레이어들이 프라이버시를 얼마나 중요하게 여기는지와 결과를 얼마나 중요하게 여기는지의 상대적 가치(relative valuation)에 따라 달라지며, 이는 메커니즘 적용 이전에 외부적으로(exogenously) 결정되어야 한다.
플레이어의 프라이버시 가치(value for privacy)를 직접 추론하는 문제는 우리가 다루는 문제와는 독립적인 문제(orthogonal problem)이며, 이는 Ghosh and Roth [2011]의 연구에서 시작된 별도의 연구 흐름이다(이와 관련한 논의는 다음 섹션에서 다룬다).
우리의 접근 방식은 우월전략 지배(dominant-strategy) 솔루션 개념을 기반으로 하기 때문에, 일부 플레이어에 대해 프라이버시 가치에 대한 가정이 잘못되더라도, 나머지 플레이어들은 여전히 진실하게 응답할 유인을 가지게 된다.
References
Chen, Yiling, et al. “Truthful mechanisms for agents that value privacy.” ACM Transactions on Economics and Computation (TEAC) 4.3 (2016): 1-30.