[review #13] Differential Privacy for Stackelberg Games

프라이버시 보호 정보가 원래 Stackelberg game의 실행 가능성과 근접한 최적성을 유지하도록 보장한다.
PPSM은 표준 프라이버시 보호 메커니즘에 비해 오류를 두 자릿수로 줄일 수 있음을 보여준다.

전기나 가스 시장에서 생산 비용이나 소비자 부하와 같은 데이터는 독점적, 공개될 경우 경쟁 우위를 제공할 수 있어 프라이버시 이슈가 발생할 수 있다.

Figure 1: Stackelberg game in sequential interdependent markets.

리더와 팔로워 간의 기본적인 상호작용과 정보의 흐름을 설명한다.
게임의 구조적 이해를 돕기 위해 설계되었으며, 리더와 팔로워가 어떻게 정보를 교환하고 결정을 내리는지 보여준다.
정보의 교환과 리더 및 팔로워 간의 동적 상호작용을 강조한다.

\(D_S^F\): follower의 민감한 데이터
\(D^L, D_P^F\): 각 leader/follower의 공개 데이터
\(x^{L^*}, x^{F^*}\): leader/follower의 최적 결정 변수
(게임을 통해 주어진 제약 조건 하에서 각 에이전트의 목표를 최적화하며 결정됨)
\(y^{F^*}\): follower의 최적화 문제에 있는 제약 조건과 관련된 최적 이중 변수를 나타냄

자신의 결정을 최적화하는 동시에 추종자(예: 두번째 시장 운영자)의 반응을 예측하여 최적의 전략을 달성한다.
PPSM: 조정 에이전트가 차등 프라이버시 데이터를 높은 충실도로 교환할 수 있도록 하는 두 단계 프로토콜
– Privacy-Preserving Stackelberg Mechanism (PPSM)
– 에이전트의 목표 및 조정 변수에 대한 충실도 제약 포함에 의존하여, 에이전트 간에 교환되는 프라이버시 보호 정보가 원래 Stackelberg game의 실행 가능성과 근사 최적성을 보존하도록 한다.

프라이버시의 목표: \(D_S^F\)가 포함하는 민감한 정보가 공개되지 않도록 보호
FERC 지침은 가스 및 전기 사업자가 네트워크 데이터를 공유할 수 있도록 허용하는 반면, 발전기의 입찰은 공공 정보이다.

(1a) 리더의 문제(Leader’s Problem)
리더의 목적 함수를 최소화하는 결정 변수 \(x^L\)과 \(y^F\)의 값들을 찾는 것
\(O^L\): 리더의 목적 함수
\(D^L\): 리더의 입력 데이터

(1b) 리더의 제약 조건(Leader’s Constraint)
리더의 결정 공간 \(F^L(D^L)\) 내에서 \(x^L\)과 \(y^F\)가 선택됨

(1c) 팔로워의 문제(Follower’s Problem)
리더의 결정 \(x^L\)을 바탕으로 자신의 목적 함수를 최소화하는 결정 변수 \(x^F\)와 \(y^F\)를 찾음
\(O^F\): 팔로워의 목적 함수
\(D^F_P, D^F_S\): 각 팔로워의 공개 데이터와 민감한 데이터를 의미함

(1d) 팔로워의 제약 조건(Follower’s Constraint)
팔로워의 결정 공간 \(F^F\) 내에서 \(x^F, x^L\)이 선택됨

첫 번째 시장 운영자)는 추종자(예: 두 번째 시장 운영자)의 반응을 반발하면서 결정을 최적화한다. 리더의 행동은 다음의 반응에 영향을 미치며, 이는 차례로 리더의 객관적인 가치에 영향을 미친다. 결과적으로, Stackelberg 게임의 리더 전략은 bilevel 최적화 문제로 수정될 수 있다.

1. Leader’s problem

시장에서 첫번째 움직임을 가지는 리더는 자신의 이익 또는 효용을 극대화하는 전략을 결정

\(max_{y \in Y}U_F(x, y, D_S^F)\)

\(U_F\): follower의 효용 함수
x: leader의 결정
y: follower의 결정

2. Follower’s problem

x를 관찰한 후, 리더의 결정을 주어진 상태로 자신의 효용을 극대화하는 전략 y를 선택

Figure 2: PPSM Illustration.

PPSM 프로토콜의 단계별 동작 확인, 어떻게 처리하고 결과를 어떻게 보장하는지 상세하게 보여준다.
데이터의 익명화, 최적화 문제의 해결, 결과적인 데이터의 재구성과 같은 단계가 포함된다.
차등 프라이버시를 유지하면서 정보를 어떻게 안전하게 교환할 수 있는지를 설명하는 데 중점을 둔다.

1. Privacy Phase

follower 본인의 민감한 데이터 \(D_S^F\)로부터 라플라스 메커니즘을 사용해서 개인 정보 보호 버전 \(\widetilde{D}_S^F\)을 생성한다.

2. Coordination Variable Estimation Phase

2a: leader는 모델 \(M^L\)을 사용하여 \(\widetilde{D}_S^F\)로부터 follower의 조정 변수 \(\overline{y}^F\)의 값을 추정
2b: leader는 추정된 \(\overline{y}^F\) 값을 사용하여 leader의 문제를 해결하고 조정 변수 \(\overline{x}^L\)의 값을 얻음
3a: follower는 모델 \(M^F\)를 사용하여 leader로부터 받은 \(\overline{x}^L\) 값과 함께 \(\widetilde{D}_S^F\)를 사용하여 자신의 목표 값 \(\overline{\mathrm{O}}^{F^*}\)와 이중 변수 \(\overline{y}^{F^*}\)의 값을 추정

3. Fidelity Phase

follower는 최종적으로 개인정보 보호 데이터 \(\widetilde{D}_S^F\)와 이전 단계에서 계산된 값을 사용하여 더 충실도가 높은 새로운 개인정보 보호 데이터 \(D_S^F\)를 생성한다.

의미:
1) 게임의 실행 가능성
차등 프라이버시를 적용한 후에도 Stackelberg game이 실제로 실행 가능한 해를 도출할 수 있는지 여부
차등 프라이버시로 인해 변형된 데이터를 사용하여도 여전히 모든 제약 조건을 만족하는 해를 찾을 수 있는지(충실도 단계에서 판별)

2) 근사 최적성의 보존
차등 프라이버시로 보호된 데이터를 사용하여 얻은 해가 원래 문제의 최적 해에 얼마나 가까운지
잡음이 추가된 데이터로부터 도출된 해가 원래 문제의 최적 해와 유사한 수준의 성능을 보이도록 하는 것이 목표

References

Differential Privacy for Stackelberg Games
Modeling and Analysis of pHRI with Differential Game Theory