Structured summary
This paper explores the role of privacy-preserving algorithms in mechanism design, specifically using differential privacy to ensure that participants have limited effect on the outcome of the mechanism and limited incentive to lie.
이 논문은 메커니즘 설계에서 프라이버시 보호 알고리즘의 역할을 탐구하며, 특히 차등 프라이버시를 활용하여 참가자가 메커니즘의 결과에 미치는 영향을 제한하고 거짓말을 할 유인을 줄이는 방법을 연구한다.
Abstract
참여자에 대한 특정 정보의 유출을 방지하는 프라이버시 보호 알고리즘(privacy-preserving algorithms)이 전략적(agent-based) 메커니즘 설계에서 어떤 역할을 할 수 있는지 연구한다.
전략적 메커니즘에서는 참여자들이 정보를 정직하게 보고하도록 유도하는 것이 필수적이다.
구체적으로, 우리는 최근 도입된 차등 프라이버시(differential privacy) 개념이, 프라이버시 보호라는 장점 외에도 참여자가 메커니즘 결과에 미치는 영향을 제한하고, 결과적으로 거짓 보고(incentive to lie)를 줄이는 역할을 할 수 있음을 보인다.
더 정확하게 말하면, 차등 프라이버시를 만족하는 메커니즘은 임의의 플레이어 효용 함수(utility function) 하에서도 근사적 우월전략(approximate dominant strategy)을 형성하며,
자동적으로 연합(coalition)에 대한 내성을 가지며, 반복 시행이 용이하다.
무제한 공급 경매(unlimited supply auction) 문제의 여러 특수 사례를 연구하며, 다음과 같은 새로운 결과를 제시한다.
- 디지털 상품 경매
- 속성 기반 경매
- 가격 구조에 임의의 제약이 존재하는 경매
특히, 프라이버시 보호 경매 메커니즘을 개발하는 중요한 전제 조건으로, 기존의 프라이버시 연구를 확장하여 경매 환경의 높은 민감도(high sensitivity)를 수용하는 일반화된 모델을 소개하고 연구한다.
이러한 환경에서는,
- 단일 참가자가 최적 고정 가격(optimal fixed price)을 극적으로 변화시킬 가능성이 존재하며,
- 제공되는 가격이 약간만 변경되어도 수익이 최적에서 0으로 급락할 수 있다.
1. Introduction
민감한 데이터를 분석하면서 동시에 프라이버시를 유지하려는 문제는 오래전부터 연구되어 왔다. 예를 들어, 인구조사국(Census Bureau)에서 직면한 문제들은, “정보 공개 제한 메커니즘(disclosure limitation mechanisms)” 연구의 발전을 이끌었다. 이러한 메커니즘은 데이터 세트에서 유출되는 특정 정보의 양이나 성격을 제한하는 것을 목표로 한다.
이러한 과정에서 ‘민감한 입력 데이터가 무작위화(randomized), 집계(aggregated), 익명화(anonymized)’ 등의 기법을 통해 변형되었고, 원래 데이터의 구체적인 의미를 제거하고 유출을 방지하는 방식이 사용되었다.
대부분의(모든 것은 아니지만) 정보 공개 제한 메커니즘에서는 어떤 정보 공개가 “허용되지 않는(unacceptable)” 것인지 정확히 정의하는 것이 핵심 요소이다.
- 일반적으로, 개별 참가자에 대한 특정 정보 공개는 허용되지 않는다.
- 반면, 집단에 대한 비특정적이고 일반적인 정보는 허용되거나 오히려 바람직할 수 있다.
- 따라서, 각 기법이 제공하는 프라이버시 보호 수준은 다를 수 있으며, 대부분의 연구는 특정한 프라이버시 목표를 설정하는 대신, 특정 메커니즘이 방지하는 정보 공개를 통해 프라이버시를 형식적으로 정의하는 경향이 있다.
최근 연구 [15, 14]는 정보 공개를 형식적으로 정의하는 어려움을 회피하기 위해 “확률 변화(relative change in probability)“에 대한 상대적 제한을 부과하는 정의를 도입했다.
이 접근법에서는 어떤 사건(event)이 발생할 확률 자체를 직접 제한하는 것이 아니라, 개별 사용자의 데이터 변경으로 인해 사건의 확률이 변하는 정도를 상대적으로 제한한다.
Definition 1 (Differential Privacy)
임의성을 갖는 함수 M 이 \(\epsilon\)-차등 프라이버시를 보장하려면,
모든 단일 사용자만 다르게 포함하는 데이터셋 \(D_1\) 및 \(D_2\), 그리고 M 의 출력 범위 \(Range(M)\) 의 모든 부분집합 S 에 대해 다음이 성립해야 한다.
\(Pr[M(D_1) \in S] \leq \exp(\epsilon) \times Pr[M(D_2) \in S]\)
이 정의의 자연스러운 결과는 다음과 같다.
- 특정 사건(event) S (예: 원치 않는 개인정보 유출)이 어떤 사용자의 참여 여부에 따라 확률적으로 크게 변하지 않는다.
- 특정 사용자의 데이터 없이 발생 가능성이 낮거나 불가능한 사건은, 해당 데이터를 추가하더라도 여전히 발생 가능성이 낮거나 불가능하다.
- 즉, 단일 사용자의 참여가 결과에 미치는 영향을 제한하는 것이 차등 프라이버시의 핵심이다.
메커니즘 설계(Mechanism Design)와 차등 프라이버시의 관계
메커니즘 설계(Mechanism Design)는 이기적인(agent-based) 플레이어들이 입력을 전략적으로 조작하는 상황에서도 견고한 알고리즘을 설계하고 분석하는 분야이다.
이를 프라이버시 문제와 연관 지어 생각하면, 참여자들이 자신의 입력값이 결과에 큰 영향을 미칠 것을 우려하여, 전략적으로 행동할 수 있는 상황을 고려할 수 있다.
즉, 프라이버시 문제 자체를 전략적 행위(strategic play)의 한 형태로 해석할 수 있다.
일반적으로 메커니즘 설계의 결과는 프라이버시 보호 알고리즘 개발에 응용될 수 있다.
그러나 이 연구에서는 반대로, 강력한 프라이버시 보장(예: 차등 프라이버시)이 메커니즘 설계를 개선하고 확장하는 데 기여할 수 있음을 탐구한다.
1.1 Statement of Results and Comparison with Related Work
논문의 기여는 세 가지 부분으로 나뉜다.
1. 차등 프라이버시를 메커니즘 설계의 해법 개념(solution concept)으로 도입한다.
2. 기존 연구보다 훨씬 더 다양한 상황에 적용할 수 있는 메커니즘을 제시함으로써, 차등 프라이버시의 적용 가능성을 확장한다.
3. 무제한 공급 경매(unlimited supply auctions)라는 특정 사례를 연구하며, 이 해법 개념을 사용하여 후회(regret) 경계를 크게 개선한다.
Differential Privacy as a Solution Concept
메커니즘 설계에서 가장 일반적인 해법 개념은 ‘진실성(truthfulness)’일 것이다. 즉, 메커니즘이 각 사용자가 자신의 가치를 정확하게 보고하는 것이 우월 전략(dominant strategy)이 되도록 설계되는 경우를 의미한다.
진실한(truthful) 메커니즘을 설계하면 분석이 단순해진다.
• 사용자가 기대 효용(expected utility)을 높이기 위해 전략적으로 거짓 보고(gaming the system)를 시도할 가능성을 고려할 필요가 없기 때문이다.
• 따라서, 진실성을 해법 개념으로 채택하는 것은 매우 직관적이고 편리한 접근법이다.
그러나, 일반적인 진실성 메커니즘은 다음과 같은 제약 조건하에서만 증명 가능하다.
1. 복수의 플레이어 간 담합(collusion)이 금지된 환경
2. 입찰자의 효용 함수(utility function)가 특정한 단순한 범위로 제한된 경우
3. 메커니즘이 단 한 번 실행되며, 이후 추가적인 대응(recourse)이 제한된 경우
4. 일부 사용자에게 큰 금액을 지급하거나, 일부 사용자에게만 특정 가격으로 상품을 제공하는 구조를 포함할 가능성
이러한 강한 가정(strong assumptions)은 메커니즘이 충실하게 구현될 수 있는 범위를 제한하며, 진실성이 주는 이점을 온전히 실현하는 데 장애가 될 수 있다.
차등 프라이버시를 활용한 진실성의 완화(Relaxation of Truthfulness)
논문의 2장에서 살펴보겠지만, 차등 프라이버시는 진실성(truthfulness)을 완화(relax)하는 역할을 한다.
즉, 참여자가 거짓 보고를 할 유인이 완전히 0이 되지는 않지만, 매우 제한적으로 조정될 수 있다.
더욱 중요한 점은, 이러한 “근사적 진실성(approximate truthfulness)“이 다음과 같은 추가적 보장을 제공한다는 것이다.
담합(collusion)이 존재하는 환경에서도 즉각적인 보장(immediate guarantees)을 제공한다.
임의의 효용 함수(arbitrary utility functions)에서도 적용 가능하다.
메커니즘이 반복 실행(repeated runs)되더라도 적용 가능하다.
최근 Chaudhuri et al. [12]의 연구에 따르면,
이러한 메커니즘은 높은 확률로(truthful with high probability) 진실성을 보장할 수 있도록 구현될 수 있다.
또한, 엄격한 진실성을 요구하는 기존 방식으로 해결할 수 없는 문제들을 다룰 수 있는 가능성을 연다.
대표적인 예시로, 무제한 공급 가격 책정 문제(unlimited supply pricing problem)가 있다.
이 문제에서는 무제한으로 제공되는 상품을 단일 가격(single price)으로 모든 구매자에게 제공해야 하는 상황이 발생한다.
기존의 엄격한 진실성 기반 메커니즘으로는 해결이 어려운 문제지만, 차등 프라이버시를 활용하면 해결할 수 있다.
A General Differential Privacy Framework
기존의 DP 접근법들은 실수 값(real-valued)을 갖는 함수에 초점을 맞추었다.
이러한 함수들은 개별 사용자의 데이터 변경에 상대적으로 둔감(insensitive)하고, 덧셈적 노이즈(additive perturbations)를 추가하더라도 유용성이 크게 감소하지 않는 특성을 갖는다. 많은 통계적 지표(statistical quantities)들이 이러한 요구사항을 충족하며, 일부 계산적 지표(computational quantities)들도 동일하게 적용될 수 있다.
따라서 대부분의 연구는 덧셈적 노이즈 크기를 줄이는 방향으로 진행되었다.
함수의 속성(properties of the function)을 연구하거나,
함수의 민감도(sensitivity)가 균일하지 않다는 점(non-uniformity sensitivity)을 활용하는 방법 등이 최근 연구에서 주목받고 있다 [33].
그러나 기존 접근법들이 논의하지 않은 중요한 문제는, 이러한 가정들이 성립하지 않는 영역에서 차등 프라이버시를 어떻게 적용할 것인가이다.
예를 들어, 무제한 공급 경매(unlimited supply auctions)를 고려하면,
“판매할 최적의 고정 가격(optimal fixed price to sell at)“을 결정하는 함수는 민감도가 낮은(insensitive) 함수가 아니다.단일 입찰자(single bidder)의 데이터 변경만으로도 최적 가격이 크게 변할 가능성이 있다.
또한, 덧셈적 노이즈를 추가해도 안정적이지 않다.
제시된 가격(offer price)이 조금만 높아져도 모든 입찰자가 구매를 포기할 가능성이 있기 때문이다.
최근 Nissim et al. [33]의 연구에서는 최적 가격이 민감하지 않은 경우를 다루었으나,
가격이 민감하게 변하는 경우(sensitive instances)나 덧셈적 노이즈의 문제는 해결하지 못했다.
본 연구에서는 이러한 문제를 해결하기 위한 보다 일반적인 프레임워크를 제안한다.
더 나아가, 이 연구에서 해결하고자 하는 더 큰 문제는 “출력이 수치 값이 아닌(non-numeric output) 경우에도 적용 가능한 메커니즘을 설계하는 것”이다.
예를 들어:
머신 러닝(Machine Learning)에서는 모델(model)이나 분류기(classifier)를 생성한다.
최적화(Optimization)에서는 시설을 활성화하거나(flow routing), 경로를 설정(route flow)하는 문제가 존재한다.
이러한 해결책들은 수치 값을 포함할 수도 있지만, 상당 부분이 구조적 정보(structural information)로 구성되며, 이는 쉽게 “노이즈 추가(perturbation)“가 어렵다.
따라서, 본 연구에서는
임의의 측정 가능한 범위(arbitrary measurable range)를 허용하는 일반적인 프레임워크를 개발하고,
이전 연구들이 다루지 못한 문제들을 프라이버시를 보호하는 방식(privacy-preserving manner)으로 해결하는 것을 목표로 한다.
이 프레임워크는 모든 차등 프라이버시를 제공하는 메커니즘을 포함할 수 있도록 설계되었으며,
특정한 환경에서 발생할 수 있는 계산적 이점(computational benefits)을 반드시 노출할 필요 없이, 일반적인 형태로 차등 프라이버시를 적용할 수 있도록 한다.
Applications to Digital Goods Auctions
디지털 상품 경매 문제(Digital Goods Auction Problem)는 무제한으로 공급되는 상품을 판매하는 경매 환경을 다룬다.
- 입찰자(bidders) 수는 n명이며, 각 입찰자는 해당 상품에 대한 개별적인(private) 효용(utility)을 가진다.
- 경매자(auctioneer)는 상품을 무제한으로 공급할 수 있으며, 각 입찰자로부터 [0,1] 범위의 입찰가(bid)를 제출받는다.
- 입찰 결과를 기반으로 상품을 누구에게 제공할지, 그리고 어떤 가격으로 판매할지를 결정한다.
- 제출된 입찰자들로부터 경매인이 얻을 수 있는 최적의 고정 가격 수익을 OPI로 정의한다.
즉, OPT(Optimal Fixed Price Revenue)는 제출된 입찰가에서 경매자가 최적의 고정 가격을 설정했을 때 얻을 수 있는 최대 수익을 의미한다.
Theorem 1. (디지털 상품 경매 문제에서 차등 프라이버시를 적용한 메커니즘)
디지털 상품 경매 문제에서 ϵ-차등 프라이버시(ϵ-differential privacy)를 보장하는 메커니즘이 존재하며,
해당 메커니즘의 기대 수익(expected revenue)은 다음과 같은 하한을 갖는다:
\(\text{OPT} – \frac{3 \ln(e + ϵ^2 \text{OPT} n)}{ϵ}\)
기존 연구와의 비교
이 연구에서 제안하는 차등 프라이버시 메커니즘은 기존의 Balcan et al. [6] 연구와 비교된다.
Balcan et al. [6] 연구에서는 머신러닝(machine learning)을 활용하여, 무작위 표본에서 학습하는 방식을 사용했다.
그 결과 진실한 응답(truthful bidding)을 유도하는 메커니즘을 설계했으며,
기대 수익은 \(\text{OPT} – O(\sqrt{\text{OPT}})\) 수준을 달성했다.
하지만 본 연구에서는:
엄격한 진실성(strict truthfulness)을 포기하는 대신,
최적 기대 수익(OPT)과의 차이를 기하급수적으로 감소시킴으로써, 더 나은 기대 수익을 보장한다.
또한, Balcan et al. [6]에서 제공하지 않는 강력한 속성들(Section 2에서 논의됨)을 추가로 보장한다.
추가적으로,
제안된 메커니즘은 모든 사용자에게 동일한 가격을 적용하므로 “질투 없음(envy-free)” 속성을 보장한다.
디지털 상품 속성 경매(Digital Goods Attribute Auction)로의 확장
디지털 상품 속성 경매(Digital Goods Attribute Auction)는 기본 디지털 상품 경매 문제를 확장한 개념이다.
각 참가자는 공개된(public) 변하지 않는(immutable) 속성(attributes)을 가진다.
이 문제에서 메커니즘의 출력(output)은 시장 세분화(market segmentation)를 설명한다.
즉, 속성 공간(attribute space)의 분할(partitioning)과 각 시장 세분화별 가격을 결정한다.
일반적으로 가능한 세분화(segmentations)를 제한하여, 최적해(optimal solution)가 보다 관리 가능한 형태로 유지되도록 한다.
이 문제에서는:
- OPTk: k개의 시장(segment)으로 나눈 경우 최적 수익(optimal revenue)
- SEGk: 현재 입찰자들의 속성을 기준으로 k개의 시장(segment)으로 나눌 수 있는 방법의 수(number of segmentations)
즉, 속성을 기반으로 최적 시장 세분화를 찾는 문제로 확장된 디지털 상품 경매 문제를 다루게 된다.
Theorem 2. (디지털 상품 속성 경매 문제에서 차등 프라이버시를 적용한 메커니즘)
디지털 상품 속성 경매(Digital Goods Attribute Auction) 문제에서 ϵ-차등 프라이버시(ϵ-differential privacy)를 보장하는 메커니즘이 존재하며,
해당 메커니즘의 기대 수익(expected revenue)은 다음과 같은 하한을 갖는다:
\(\max_k \left( OPT_k – \frac{3 \ln(e + ϵ^{k+1} OPT_k SEG_k n^{k+1})}{ϵ} \right)\)
기존 연구([6] Theorem 5)와의 비교
기존 연구인 Balcan et al. [6]의 Theorem 5에서는 구조적 위험 최소화(Structural Risk Minimization, SRM)를 기반으로 한 기대 수익 하한을 제공했다.
이 연구에서는 다음을 보장한다:
\(\max_k \left( OPT_k – O\left( (OPT_k^2 \ln(k^2 SEG_k))^{1/3} \right) \right)\)
즉, 기존 연구에서는 확률적으로 높은 신뢰도를 가지는 기대 수익을 보장했다.
하지만 본 연구의 차별점은:
- 엄격한 진실성(strict truthfulness)을 포기하는 대신,
- 추가적인 기대 수익 증가 및 Section 2에서 논의된 추가 속성들을 보장하며,단일 가격(single-price) 정책을 유지하여 “질투 없음(envy-free)” 속성을 보장한다.
추가적인 연구 기여
본 연구에서는 다음과 같은 추가적인 새로운 결과를 제시한다.
- 제약된 가격 설정(constrained pricing) 문제에 대한 새로운 결과 제공
특정한 가격 제한 조건이 있는 경우에도 적용할 수 있는 메커니즘 설계 - 여러 개의 진실한 알고리즘(truthful algorithms) 중 최적의 알고리즘을 선택하고 적용하는 문제 해결
다양한 진실한 알고리즘이 있을 때, 최적의 수익을 보장하는 알고리즘을 선택하는 방법을 제안
1.1.1. Previous Work in Privacy
여러 연구에서 차등 프라이버시(differential privacy)를 보장하는 메커니즘이 제안되었으며, 주로 데이터 마이닝, 머신 러닝, 통계 분야의 작업에서 활용되었다.
이러한 메커니즘의 큰 특징 중 하나는 출력값이 작은 덧셈적 노이즈(additive noise)에 대해 강인(robust)하게 유지된다는 점이다.
따라서, 프라이버시를 보장하기 위해 적절한 노이즈를 추가해도 유용성을 크게 손상시키지 않는 방식이 사용된다.
- 덧셈적 노이즈 기반 차등 프라이버시 메커니즘
[9, 15] 연구에서는 대칭적인(exp) 분포를 따르는 노이즈를 특정 함수에 추가하면 차등 프라이버시를 보장할 수 있음을 보였다.
이러한 함수는 Lipschitz 연속 조건(Lipschitz condition)을 만족해야 하며, 즉, 입력 데이터가 조금 변경되더라도 출력이 큰 영향을 받지 않도록 제어된다. - 지역(local) 민감도를 활용한 연구
Nissim et al. [33] 연구에서는 함수의 전역(global) 민감도가 크더라도, 지역(local) 민감도가 작은 경우를 활용하는 방법을 제안하였다.
이는 계산된 값에 추가되는 노이즈의 크기를 상당히 줄일 수 있도록 개선할 수 있다.
다른 정보 유출 방지 기법(disclosure limitation techniques)으로는 다음과 같은 것들이 있다.
입력 변형(input perturbation): 사용자가 제공하는 데이터를 난수화(scrambling)하여 직접 변형하는 방식.
쿼리 제한(query restriction): 특정 쿼리(질문)의 출력이 프라이버시를 위협할 가능성이 높다면, 해당 쿼리에 대한 응답을 제한하는 방식.
이러한 연구들은 절대적인 정보 유출 방지(absolute disclosure limitation)를 목표로 하지만,
이는 공격자의 사전 지식(prior knowledge)에 대한 가정을 포함하는 경우가 많다.
특히 [14] 연구에서는 공격자의 사전 지식을 제한하지 않으면, 절대적인 정보 유출 방지는 불가능하다는 것을 증명했다.
이는 차등 프라이버시가 절대적인 보호를 제공하는 것이 아니라, 확률적(통계적) 보장을 통해 정보 유출 가능성을 제한하는 방식임을 의미한다.
추가적으로, 관련 연구에 대한 좋은 서베이 논문은 [1]에서 확인할 수 있다.
1.1.2. Previous Work in Mechanism Design
메커니즘 디자인(mechanism design)은 게임 이론 및 경제학에서 오랜 연구 역사를 가진 분야로,
Vickrey 경매를 시작으로 사회적 선택 이론(social choice theory)까지 확장되었다.
(자세한 내용은 Mas-Colell, Whinston, Green의 저서 [30] 참고)
특히, 알고리즘적 메커니즘 디자인(algorithmic mechanism design)은 Nisan과 Ronen [32]의 연구를 기점으로 발전하였으며, 주로 진실한(truthful) 메커니즘 설계에 초점을 맞춰왔다.
대표적인 예로, 디지털 상품 경매(auctions for digital goods), 스케줄링 문제(scheduling problems), 조합적 경매(combinatorial auctions) 등이 있다.
그러나 강한 진실성(truthfulness) 가정이 너무 제한적이어서, 메커니즘이 가질 수 있는 다른 중요한 특성을 방해하는 경우가 많다.
예를 들어,
1) Archer & Tardos [4], Elkind, Sahai & Steiglitz [16] 연구에서는
그래프 내 최단 경로를 구매하는 진실한 메커니즘이 지나치게 높은 비용을 초래한다는 것을 보였다.
2) 조합적 경매(combinatorial auction) 문제에서, Lavi, Mu’alem, Nisan [27]의 연구는
자연스러운 가정하에서 진실하면서도 계산적으로 효율적인 메커니즘이 높은 사회적 복지(social welfare)를 보장하지 못함을 증명했다.
단일 파라미터(single-parameter) 에이전트에 대한 진실한 메커니즘은 비교적 잘 연구되었지만,
다차원(multi-dimensional) 에이전트에 대한 진실한 메커니즘의 특성 분석은 상대적으로 최근 연구에서 다루어졌다 [8, 35].
강한 진실성(truthfulness)의 완화(Relaxation of Strong Truthfulness)
따라서, 진실성 가정을 완화하는 연구가 자연스럽게 고려되었으며, 이미 광범위하게 연구되었다.
1. Bayes-Nash 균형(Bayes-Nash equilibria) 적용
- 경매 이론에서는 Bayes-Nash 균형을 기반으로 한 메커니즘이 일반적이다 (예: [30]).
- Elkind et al. [16]: 최단 경로 경매(shortest path auctions)에서 Bayes-Nash 균형을 분석.
- Czumaj & Ronen [13]: Nash 균형과 Myopic 균형을 적용한 최단 경로 경매 연구.
- Immorlica et al. [24]: \(\epsilon\)-Nash 균형을 기반으로 하는 메커니즘 연구.
2. 확률적(truthfulness with high probability) 진실성 보장
- Archer et al. [3]: 조합적 경매에서 높은 확률로 진실성이 보장되는 메커니즘을 연구.
- Babaioff, Lavi & Pavlov [5]: 단일 가치(single-value) 조합적 경매에서 진실한 응답이 우월한 전략(undominated strategy)임을 보장하는 메커니즘 설계.
…
1.2. Paper Outline
이 논문은 차등 프라이버시(differential privacy)의 게임 이론적(game-theoretic) 영향을 분석하고,
이를 활용한 메커니즘 설계(mechanism design)를 제안하는 내용을 포함하고 있다.
제2장 (Section 2):
차등 프라이버시가 게임 이론적으로 어떤 결과를 초래하는지 논의한다.
이를 통해 전략적 행동(strategic behavior)을 제한하고, 진실한 응답(truthfulness)을 유도하는 방법을 설명한다.
제3장 (Section 3):
차등 프라이버시를 제공하는 새로운 메커니즘을 개발하며, 기존의 덧셈적 노이즈(additive noise) 메커니즘 [9, 15]을 일반화한다.
또한, 이 메커니즘이 차등 프라이버시를 보장함을 증명하고, 출력(output)이 바람직하지 않을 확률이 매우 낮음을 보이는 유용성(usefulness) 정리를 증명한다.
제4장 (Section 4):
개발된 일반 메커니즘을 다양한 경매 문제(auction problems)에 적용한다.
단일 품목 가격 결정(single-commodity pricing), 속성 기반 경매(attribute auctions), 구조적 제약이 있는 가격 결정 문제(structurally constrained pricing problems)에 적용하여 성능을 분석한다.
결론 및 향후 연구 방향 (Conclusion & Future Work):
연구를 마무리하며, 남은 개방형 문제(open problems)와 추가 연구 방향(further research)을 제시한다.
2. Differential Privacy as a Solution Concept
DP의 몇 가지 함의를 메커니즘 설계에서 보다 익숙한 용어로 변환하여 설명한다.
2.1 Approximate Truthfulness
본 논문에서 강조할 개념 중 하나는 ‘\(\varepsilon\)-지배(\(\varepsilon\)-dominance)’이다. 이는 Schummer [37]에 의해 제안 및 연구된 개념으로, 어떠한 에이전트 도 진실되지 않은 응답을 할 유인이 \(\varepsilon\) 이상 증가하지 않는다는 것을 의미한다. 이는 \(\varepsilon\)-내시 균형보다 강한 개념이다.
\(\varepsilon\)-DP를 만족하는 메커니즘은 진실한 보고를 (\(exp(\epsilon)-1\))-지배 전략으로 만든다. 이는 유틸리티 함수가 메커니즘 출력의 범위 \(Range(M)\)에서 [0, 1]로 매핑되는 모든 경우에 해당된다. 이는 보다 일반적인 보장에서 비롯되며, 어떤 사용자도 자신의 효용을 \(exp(\varepsilon)\) 이상 상대적으로 변경할 수 없음을 의미한다.
Chaudhuri et al. [12]는 \(\varepsilon\)
2.2 Collusion Resistance
많은 진실한 메커니즘은 한 가지 결함을 갖는데, 개별 플레이어는 자신의 이익을 위해 거짓말을 할 유인이 없더라도, 여러 플레이어가 집단적으로 공모(collusion)하여 각자의 효용을 생성할 수 있다. 이는 추가적인 보상이 없는 경우에도 발생할 수 있다.
DP의 한 가지 유리한 특성은 데이터셋에서 발생하는 변화의 횟수에 따라 점진적으로 성능이 저하된다는 점이다.
플레이어들의 집단적 효용이 크게 증가하지 않는다. 따라서 플레이어들 간의 추가적인 보상 문제는 의미가 없어진다.
2.3 Composability
많은 메커니즘은 반복 실행 문제가 발생하는데, 참가자들이 자신의 효용을 왜곡하여 초기 라운드에서 유리한 결과를 유도하고, 이를 통해 이후 라운드에서 더 나은 결과를 얻으려는 전략적 행동을 할 수 있기 때문이다.
구체적인 예로, 매일 반복 실행되는 무제한 공급 경매를 가정해 보자. 영리한 참가자들은 처음에는 낮은 입찰가(underbid)를 제시하여 초기 가격을 낮추고, 이를 통해 자금력이 있는 입찰자들이 빠르게 탈락하도록 유도할 수 있다. 그 결과, 이후 라운드에서는 경쟁이 줄어들어 참가자들이 더 유리한 가격에 상품을 얻을 가능성이 커진다.
→ 매일 반복되는 경매에서 참가자가 전략적으로 행동할 수 있음
위에서 설명한 경매에서, 각 경매의 메커니즘 인스턴스가 \(\varepsilon\)-차등 프라이버시를 보장한다고 가정하면, 단일 사용자가 향후 7일 동안의 가격을 최대 \(exp(7\varepsilon)\)의 범위 내에서 왜곡할 수 있다. 이는 각 메커니즘 인스턴스가 이전 실행 결과에 반응하는 경우에도 성립하며, 예를 들어 이미 상품을 획득한 입찰자를 경매에서 제외하는 방식이 해당될 수 있다.
→ 즉, 사용자가 매일 입찰 가격을 조작하려 해도 그 영향력은 지수적으로 제한됨
→ 공모 저항성(Collusion Resistance, Corollary 4)을 적용해야 함
3. A General Differential Privacy Mechanism
프라이버시 메커니즘의 목표는 입력 공간 D에서 온 n개의 입력 집합을 무작위로 출력 공간 R의 값으로 변환하는 것이다.
D와 R의 성질에 대해 특정한 가정을 두지 않으며, 출력 공간 R 위에서 정의된 기본 측도(base measure) \(\mu\) 만을 고려한다.
입력 공간 D (각 참가자의 데이터) 및 출력 공간 R (출력되는 값)에서 특정 입력 d와 특정 출력 r의 적절성(점수)를 나타내는 질의 함수(query function): q(d, r)에 대해, 메커니즘의 목표는 q(d, r)의 점수가 높은 값을 출력하면서도 차등 프라이버시를 보장하는 것이다.
→ 만약 가장 높은 q(d, r) 값을 가진 r만 출력하면, 사용자의 데이터 d가 특정 값이라는 것이 쉽게 드러난다.
→ 그래서 최적의 r을 선택하는 경향을 유지하면서도, 다른 값들도 출력될 가능성을 남겨둔다. (exponential mechanism의 일반화된 형태)
입력 데이터 d가 조금 변하더라도 출력 확률 분포가 크게 달라지지 않도록 조정되어 DP가 보장
보통 균등 분포(uniform distribution)인 기본 측도 \(\mu\)에서 시작하며, 각 출력에 할당된 확률을 \(exp(\varepsilon q(d, r))\) 배만큼 증폭한다.
즉, 출력 확률은 기본 분포 \(\mu(r)\)에 비례하면서도, \(q(d, r)\) 값이 클수록 더욱 높은 확률로 선택된다. 이는 laplace mechanism이나 exponential mechanism의 일반화된 형태로 볼 수 있다.
직관적으로 보면, q(d, r) 값이 소폭 변경되는 것(예: 단일 참가자의 데이터 변경으로 인해 발생)이 출력 확률 밀도에 미치는 영향은 곱셈적으로 제한되므로 DP가 보장된다.
즉, 한 명의 참가자가 데이터를 살짝 변경한다고 해도 전체 출력 분포가 급격하게 변하지 않으므로 프라이버시 보호 효과가 있다.
Remark:
이 적분값이 유한해야 한다.
\(\int_{r} \exp(\epsilon q(d,r)) \mu(r) \, dr\)
본 논문에서 q 값이 항상 n 이하로 제한됨을 가정하므로, 위 적분값도 \(exp(\epsilon n)\)으로 제한된다.
Remark:
기존 연구 [15, 14]에서는 라플라스 노이즈를 함수 \(f: D^n \to R\)의 결과값에 추가하는 방식을 사용했는데, 이를 일반적인 DP 메커니즘으로 해석하면 q(d, r) = -|f(d) – r|로 볼 수 있다.
→ 즉, 기존 라플라스 메커니즘은 출력 r이 f(d)와 가까울수록 확률이 높아지도록 조정된 경우로 해석 가능
이 논문의 일반적인 메커니즘도 동일한 방식으로 기존의 라플라스 메커니즘을 포함할 수 있음
도입부에서 언급된 단위 수요(unit demand) 경매 설정과 같은 몇몇 경우에서는, \(\exp(\epsilon q(d,r))\mu(r)\) 값이 변경되면, 정규화 계수(normalization factor)도 같은 방향(증가/감소)으로 변경될 수밖에 없다.
이로 인해, 차등 프라이버시의 보장 수준이 더욱 강화될 수 있으며, \((2\epsilon \Delta q)\)-차등 프라이버시에서 \((\epsilon \Delta q)\)-차등 프라이버시로 상한이 감소할 수 있다.
5. Conclusions and Future Research
우리는 덧셈적 노이즈(additive noise)에 대해 강건하지 않거나, 출력이 교란(perturbation)을 허용하지 않는 함수에도 적용 가능한 새로운 일반적인 차등 프라이버시 메커니즘을 제안하였다. 이 메커니즘은 출력의 품질(quality)을 보장하는 특성을 갖는다.
이 메커니즘은 차등 프라이버시를 보장하면서도 기본 확률 분포(base measure)를 가능한 한 최대로 왜곡(skew) 하여, 가장 높은 가치(value)를 가지는 출력이 선택될 가능성을 높인다.
마지막으로, 우리는 이 일반적인 메커니즘을 여러 경매 문제(auction problems)에 적용하였으며, 최적 수익(optimal revenue)에 대해 로그(logarithmic) 차이 이내의 수익을 제공함을 확인하였다.
우리는 기존 연구(예: [6])와 달리, 본 논문에서 제안한 메커니즘이 엄격한 진실성(strict truthfulness)을 보장하지 않는다는 점을 강조한다.
반면, 우리는 기존 연구([6] 등)가 유지할 수 없는 강한 구조적 제약(hard structural constraints) 속에서도 적용 가능한 여러 제한된 가격 설정(constrained pricing settings)을 제시하였다.
→ DP 메커니즘은 완전한 진실성을 보장하지는 않지만, 근사적 진실성을 만족할 수 있다.
근사적 진실성(Approximate Truthfulness) 이란, 참가자가 자신의 입력을 조작하더라도 얻을 수 있는 이익이 매우 작아 전략적 조작이 비효율적이 되는 상태를 의미한다.
즉, 차등 프라이버시 메커니즘이 참가자의 선택에 대해 다음과 같은 성질을 보장해야 한다.
• 사용자가 입력을 조작(거짓 보고) 하더라도 기대 효용(utility)이 거의 변하지 않음.
• 거짓 보고로 인한 이익이 \epsilon 에 의해 제어되며, 지수적으로 감소함.
• 결과적으로, 참가자가 진실하게 자신의 값을 보고하는 것이 최적의 선택에 가까움.
DP의 정의에 의해, 한 명의 사용자가 자신의 데이터를 변경하더라도 출력 확률 분포가 급격하게 변하지 않도록 제한된다.
References
McSherry, Frank, and Kunal Talwar. “Mechanism design via differential privacy.” 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE, 2007.