NETS 4120: Algorithmic Game Theory #2 Differential Privacy

Mechanism Design via Differential Privacy

Overview

• We’ll have one final lecture using digital goods auctions as a testbed for techniques in mechanism design.

• Recall two lectures ago: we designed a dominant strategy of truthful auction that, for any vector of valuations v, obtained revenue: \(Rev(v) \geq OPT(v) – O(\sqrt{n})\)

where \(OPT_v = max_{p \in [0, 1]}p \cdot |{i: v_i \geq p}|\).

• In this class, we will relax our solution concept to asymptotic dominant strategy truthfulness and try to obtain a better revenue guarantee.
• Our tool is differential privacy, a technique developed for protecting user privacy in data analysis.

Approach

• Recall: Why can we not simply compute the price \(p* = arg max_{p \in [0, 1]}p \cdot |{i: v_i \geq p}|\) and charge that?
• This price will be highly manipulable by (at least) one of the bidders \(p* = v_{i*}\) for some bidder i*, who will have a strong incentive to change his bid.
• So to get dominant strategy truthfulness, we needed to compute prices that were independent of bidder reports.
• But what if we could compute a price p that is almost independent of the reported valuation \(v_i\) for every buyer i?
• Will this yield, in some sense, an approximate truthfulness guarantee? This will be the idea behind our approach.

Privacy Definitions

Definition

Two bid vectors \(v, v’ \in [0, 1]^n\) are neighbors if they differ in just a single agent’s bid, i.e., if there exists an index i such that \(v_j = v_j’\) for every index j ≠ i.
We can now define differential privacy:

Definition

A mechanism \(M: [0, 1]^n \to \textit{O}\) is ε-differentially private if for every pair of neighboring bid vectors \(v, v’ \in [0, 1]^n\), and for every outcome x ∈ O:
Pr[M(v) = x] ≤ exp(ε)Pr[M(v’) = x]

Here, you should think of ε < 1 as a small constant and think of exp(ε) ≈ (1 + ε).
For ε ≤ 1, we have:
1 + ε ≤ exp(ε) ≤ 1 + 2ε

Approximate Truthfulness

We can also define what we mean by approximate dominant strategy truthfulness:

Definition

A mechanism \(M: [0, 1]^n \to \textit{O}\) is ε-approximately dominant strategy truthful if for every bidder i, every utility function \(u_i : [0, 1] \text{x} \textit{O} \to [0, 1]\), every vector of valuations \(v ∈ [0, 1]^n\), and every deviation \(v_i’ ∈ [0, 1]\), if we write v’ = \(v_{-i}, v_i’\), then:

\(E_{o \sim M(v)}[u_i(v_i, o)] \geq E_{o \sim M(v’)}[u_i(v_i, o)] – \epsilon\)

The Connection

Differential privacy will be useful for us because differentially private mechanisms are automatically ε-approximately dominant strategy truthful.

Theorem

If a mechanism \(M: [0, 1]^n \to \textit{O}\) is ε-differentially private, then M is also ε-approximately dominant strategy truthful.

The Connection: Proof

Fix any buyer i, valuation vector v, and utility function \(u_i: [0, 1] \text{x} \textit{O} \to [0, 1]\).

\(E_{o \sim M(v)}[u_i(v_i, o)] = \sum_{o \in \textit{O}}u_i(v_i, o) \cdot Pr[M(v) = o] \\ \geq \sum_{o \in \textit{O}}u_i(v_i, o) \cdot exp(-\epsilon)Pr[M(v’) = o] \\ = exp(-\epsilon) E_{o \sim M(v’)}[u_i(v_i, o)] \\ \geq E_{o \sim M(v’)}[u_i(v_i, o)] – \epsilon\)

The last inequality follows because for ε < 1, exp(-ε) ≥ 1 – ε, and \(u_i(v_i, o)\) ≤ 1.

Exploiting the Connection

So: to design an approximately truthful mechanism that guarantees high revenue, it is sufficient to design a differentially private mechanism with high revenue.

Lets try a straightforward approach: directly picking a price that approximately maximizes revenue for the reported bidder valuations.

As in the last two lectures, lets pick a finite subset of prices P ⊂ [0, 1] to select from.

Consider the following mechanism (an instantiation of what is called “the exponential mechanism” in its more general form):
ExpMech(v, ε, P):

Define Rev(p, v) = \(p \cdot |{i: v_i \geq p}|\)
Output each p ∈ P according to the following probability distribution:

Pr[p] = \(\frac{1}{\Phi(v)}exp(\frac{\epsilon \cdot Rev(p, v)}{2})\)

where \(\Phi(v) = \sum_{p \in P} exp(\frac{\epsilon \cdot Rev(p, v)}{2})\)

Privacy/Truthfulness

Theorem

For any ε, P: ExpMech(・, ε, P) is ε-differentially private.
(and thus ε-approximately dominant strategy truthful)

Proof

Fix any pair of neighboring bid vectors v, v’ and any output p. We have:

\(Pr[EM(v, \epsilon, P) = p] = \frac{1}{\Phi (v)}exp(\frac{\epsilon \cdot Rev(p, v)}{2}) \\ \leq \frac{1}{\Phi (v)}exp(\frac{\epsilon \cdot (Rev(p,v’)+1)}{2}) \\ = \frac{1}{\Phi (v)}exp(\frac{\epsilon}{2})exp(\frac{\epsilon \cdot Rev(p, v’)}{2}) \\ \leq exp(\frac{\epsilon}{2})\frac{1}{\Phi (v)}exp(\frac{\epsilon}{2})exp(\frac{\epsilon \cdot Rev(p, v’)}{2}) \\ = exp(\epsilon)Pr[EM(v’, \epsilon, P) = p]\)

And Revenue…

Theorem

For any P, v, ε, δ, with probability 1 – δ, ExpMech(v, ε, P) outputs a price p such that:

\(Rev(p, v) \geq max_{p* \in P}Rev(p*, v) – \frac{2}{\epsilon} \cdot ln(\frac{|P|}{\delta})\)

Proof

Let \(p* = max_{p* \in P}Rev(p*, v)\). For any value x, we have:

\(Pr_{p}[Rev(p, v) \leq x] \leq \frac{Pr_p[Rev(p,v) \leq x]}{Pr_p[Rev(p,v) = Rev(p*,v)} \\ \leq \frac{|P| \cdot exp(\epsilon x/2)}{exp(\epsilon Rev(p,v)/2)} \\ = |P| \cdot exp(\frac{\epsilon \cdot (x-Rev(p*,v))}{2})\)

Now choose x = Rev(p*, v) – \(\frac{2}{\epsilon} \cdot ln(\frac{|P|}{\delta})\). Plugging that in above, we get:

\(Pr_{p}[Rev(p, v) \leq x] \leq |P| \cdot exp(-ln(\frac{|P|}{\delta})) \\ = |P| \cdot \frac{\delta}{|P|} \\ = \delta\)

Putting it all Together

We have: an approximately truthful way to select a revenue maximizing price from a finite set of prices P, with revenue guarantees with respect to the best price in P that degrade with |P|.

This is a familiar tradeoff.

Now our dependence on |P| is only logarithmic…

Lets again see what happens when we take the natural discretization:

P = {α, 2α, 3α, …, 1}

Just as before, |P| = 1/α, and that we have the guarantee that for all v:

\(max_{p \in P}Rev(p,v) \geq max_{p \in [0,1]}Rev(p,v) – \alpha n\)

Combining our bounds we see that if we discretize the price space by α, with probability 0.99, we obtain revenue:

\(Rev(p,v) \geq OPT – \alpha \cdot n – O(\frac{1}{\epsilon}ln(\frac{1}{\alpha}))\)

Choosing α = 1/n, we find that for any ε, we can obtain an ε-approximately dominant strategy truthful mechanism which obtains revenue:

\(Rev(p,v) \geq OPT – O(\frac{log n}{\epsilon})\)

If we take e.g. ε = O(1/log(n)), then we have an asymptotically truthful mechanism (in the sense that it becomes exactly truthful as n → ∞) that improves by an exponential factor on the revenue guarantee that we were able to obtain with an exactly truthful mechanism for the same problem.

Reference

• Aaron Roth, (23/25) NETS 4120: Algorithmic Game Theory, Spring 2023, Apr 26, 2023, https://youtu.be/AeqrOCtAs4w?si=gAJNHf3dGNXx-oJU