Proposition 2, p. 17 — the platform's problem reduces to minimizing under (21)
ProvedPrivAcq.Central.proposition_2data-acquisitionmechanism-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1virtual-cost
Under the standing assumptions of the model:
- For every admissible mechanism that is incentive compatible (17) and individually rational (18),
- Conversely, for every admissible allocation whose interim privacy losses are weakly decreasing in (constraint (21)), equipping it with the payments (19) with gives an admissible, incentive compatible and individually rational mechanism whose objective equals the right-hand side of (20).
Hence the optimal privacy losses are the solution of minimizing the right-hand side of (20) subject to (21): the analogue of Myerson's reduction of mechanism design to virtual welfare maximization.
Formalization Note The paper's "the optimal privacy loss … is the solution of (20)–(21)" is stated as the two inequalities/equalities that make the two problems equivalent. Payments (19) are used in ex post form, .
Preamble
import Mathlib import Definitions.Def_PrivAcq_Central_Model
Formal statement
namespace PrivAcq.Central
open MeasureTheory
theorem proposition_2 {n : ℕ} (S : Setting n) (hS : S.Standing) :
(∀ M : Mech n, Admissible S M → IC S M → IR S M →
(∫ c, (((n : ℝ) + 1) * mse S M c + ∑ i, M.ε c i * S.ψ i (c i)) ∂S.typeLaw)
- (n : ℝ) * S.var ≤ objective S M) ∧
(∀ M : Mech n, AdmissibleAlloc S M →
(∀ i : Fin n, AntitoneOn (interimEps S M i) (Set.Icc (S.a i) (S.b i))) →
Admissible S (withPayments S M) ∧ IC S (withPayments S M) ∧ IR S (withPayments S M) ∧
objective S (withPayments S M) =
(∫ c, (((n : ℝ) + 1) * mse S M c + ∑ i, M.ε c i * S.ψ i (c i)) ∂S.typeLaw)
- (n : ℝ) * S.var) := by sorry
end PrivAcq.Central
Source
Fallah, Makhdoumi, Malekian, Ozdaglar, arXiv:2201.03968v2, p. 17, Proposition 2, (20), (21); proof p. 44, (A35)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.