5.3.3 A game theoretic view of query release
cost c(a, b) ∈ [−1, 1]에 대해, Alice는 이 비용을 최소화(-1), Bob은 앨리스의 비용을 최대화(1)하고자 한다.
– 제로섬 게임(zero sum game): 게임에 참여하는 모든 플레이어들 간의 총 이익과 손실의 합이 항상 0, 한 플레이어가 얻는 이익이 다른 플레이어의 손실과 정확히 일치
* query release: 데이터베이스 또는 데이터 세트로부터 정보를 추출하는 과정에서 특정 쿼리(질의)에 대한 응답을 공개하는 것
| Alice | Bob | |
| 구분 | 데이터 관리자 | 적대적 사용자, 데이터 분석가 |
| 목표 | 프라이버시 보호 수준과 데이터 유용성 간의 균형을 찾음 | 가능한 한 많은 정보를 추출함 |
| 전략 | 데이터를 어떻게 공개할지 결정 (예: 잡음 추가, 데이터 집계) | 공개된 데이터로부터 어떤 정보를 추출할지 결정 |
| 행동 집합 | picks some action a ∈ A (possibly at random) | picks some action b ∈ B (possibly at random) |
So how should Alice play?
Alice가 무작위 전략을 밥에게 미리 알리고, Bob이 이 정보를 사용해 최적으로 응답하도록 한다.
Alice가 확률 분포 \(\textit{D}_A\)에 따라 어떤 행동 a ∈ A를 선택한다고 하면, Bob은 더 이상 엘리스의 예상 비용을 최대화하는 방식으로 응답할 것이다. 그러므로 앨리스가 전략을 발표한 후 그녀가 어떤 비용을 지불할지 알고 있게 된다. 따라서 앨리스는 밥이 응답한 후에 최소 비용을 지불하게 되는 행동의 분포를 원할 것이다. 이러한 전략은 앨리스에게 min-max strategy라고 한다.
Alice와 Bob 사이의 상호 작용과 그에 따른 최적의 전략 \(b^*\)
\(b^* = argmax_{b \in B}\mathbb{E}_{a \sim \mathit{D}_A}[c(a,b)]\)
전략 분석
1. Min-Max Strategy
Alice와 Bob이 어떤 전략을 사용하든 자신의 최대 손실을 최소화하는 전략을 선택한다.
Alice가 가질 수 있는 최악의 시나리오를 고려하고, 그 시나리오에서도 손실을 최소화하는 선택을 하는 것
2. Mixed Strategy
특정 전략을 고정적으로 사용하는 대신, Alice와 Bob은 여러 가능한 전략을 확률적으로 선택할 수 있다.
상대방이 자신의 전략을 정확히 예측하는 것을 어렵게 만들 수 있다. 상대방의 예측을 무력화시키는 데 효과적
3. Finding Equilibrium
게임의 균형점을 찾는 것은 양측 모두에게 최적의 전략이 되는 지점을 의미한다.
어느 한 쪽도 현재의 전략을 변경함으로써 더 나은 결과를 얻을 수 없다.
전략적 고려사항
1. 예측 가능성 최소화: Alice는 자신의 전략이 Bob에 의해 쉽게 예측되지 않도록 해야 한다. 이는 프라이버시 보호 메커니즘의 효과를 높일 수 있다.
2. 적응적 전략: Bob의 전략이나 데이터 사용 패턴이 시간에 따라 변할 수 있으므로, Alice는 변화에 적응할 수 있는 유연한 전략을 갖춰야 한다.
3. 피드백 루프: Alice는 공개된 데이터가 실제로 어떻게 사용되고 있는지 관찰하고, 이러한 정보를 바탕으로 자신의 전략을 조정해야 한다. (예: 데이터 사용 패턴이나 Bob의 행동에 대한 피드백 수집/분석)
Reference
- Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 5.3. Connections, 5.3.3. A game theoretic view of query release