차등 프라이버시가 제공하는 메커니즘이 모든 에이전트에 대해, 그들이 어떠한 유틸리티 함수를 가지고 있든
단일 변화에 의해 그들의 기대 유틸리티가 exp(ε) 이상으로 증가하지 않음을 보장한다.
차등 프라이버시는 단일 행위자가 자신의 기대 유틸리티를 단독으로 조작하여 크게 증가시킬 가능성을 제한한다.
\(\mathbb{E}_{o \sim M(t)}[u_i(o)]\): 원래 전략 t를 사용했을 때 에이전트 i의 기대 유틸리티
\(\mathbb{E}_{o \sim M(t_{-i}, t’_i)}[u_i(o)]\): 에이전트 i가 자신의 전략을 \(t’_i\)로 변경했을 때의 기대 유틸리티
exp(ε): 차등 프라이버시 파라미터 ε에 의해 정의된 상수 배율, ε가 작을수록 프라이버시 보호가 강화됨
\(t_{-i}\): 에이전트 i를 제외한 모든 다른 에이전트들의 전략 집합
\(t’_i\): 에이전트 i가 새롭게 선택한 전략
\(M(t_{-i}, t’_i)\): 에이전트 i가 전략을 \(t’_i\)로 변경했을 때, 그리고 나머지 에이전트들이 그대로 \(t_{-i}\) 전략을 유지했을 때 메커니즘의 결과
ε이 1 이하일 때, ε-differentially privacy 메커니즘이 ε-근사적으로 지배 전략적 진실성(approximately dominant strategy truthful)을 보장한다.
진실된 유형(type)을 보고하는 것이 가장 이익이 되며, 거짓말을 함으로써 얻을 수 있는 최대 이익이 ε으로 제한된다.
\(u_i(t_i, M(t_{-i}, t_i)) \geq u_i(t’_i, M(t_{-i}, t_i))-\epsilon\)
\(u_i(t_i, M(t_{-i}, t_i))\): 에이전트 i가 자신의 진실된 유형 \(t_i\)를 보고했을 때 얻는 유틸리티
\(u_i(t’_i, M(t_{-i}, t_i))\): 에이전트 i가 다른 유형 \(t’_i\)를 보고했을 때 얻는 유틸리티
\(M(t_{-i}, t_i)\): 에이전트 i를 제외한 다른 모든 에이전트의 유형 \(t_{-i}\)과 에이전트 i의 유형 \(t_i\)를 입력으로 받는 메커니즘 M의 출력
ε: 차등 프라이버시 파라미터, 메커니즘이 얼마나 강한 프라이버시 보호를 제공하는지 나타냄
ε-차등 프라이버시를 만족할 때, 어떤 유틸리티 함수에 대해서도 최대 k개의 요소가 다른 두 입력 집합에 대해 기대 유틸리티가 exp(εk) 이상 차이나지 않음을 보장한다.
에이전트들이 결탁하여 메커니즘에 영향을 미치려 해도, 기대 유틸리티의 증가는 제한적임을 의미한다.(게임 이론적 상황에서도 유용하게 적용된다.)
\(\mathbb{E}_{o \sim M(t)}[u_i(o)]\): 메커니즘 M이 데이터 집합 t에 적용되었을 때 에이전트 i의 기대 유틸리티
\(\mathbb{E}_{o \sim M(t’)}[u_i(o)]\): 메커니즘 M이 최대 k개의 요소가 다른 데이터 집합 t’에 적용되었을 때 에이전트 i의 기대 유틸리티
k: 변경된 요소의 수
ε: 차등 프라이버시 파라미터
References
More than privacy: Adopting Differential Privacy in Game-theoretic Mechanism Design, 2.5 Differentially Private Properties in Game Theory
you are in reality a just right webmaster The site loading velocity is incredible It seems that you are doing any unique trick In addition The contents are masterwork you have performed a wonderful task on this topic.