{"id":3411,"date":"2024-01-20T00:22:48","date_gmt":"2024-01-19T15:22:48","guid":{"rendered":"https:\/\/saraheee.com\/?p=3411"},"modified":"2024-01-20T00:22:51","modified_gmt":"2024-01-19T15:22:51","slug":"nets-4120-algorithmic-game-theory","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2024\/01\/nets-4120-algorithmic-game-theory\/","title":{"rendered":"NETS 4120: Algorithmic Game Theory #2 Differential Privacy"},"content":{"rendered":"<h2 class=\"wp-block-heading\">Mechanism Design via Differential Privacy<\/h2>\n\n\n\n<h4 class=\"wp-block-heading\">Overview<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We&#8217;ll have one final lecture using digital goods auctions as a testbed for techniques in mechanism design.<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li>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) &#8211; O(\\sqrt{n})\\)<\/li>\n<\/ul>\n\n\n\n<p>where \\(OPT_v = max_{p \\in [0, 1]}p \\cdot |{i: v_i \\geq p}|\\).<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In this class, we will relax our solution concept to asymptotic dominant strategy truthfulness and try to obtain a better revenue guarantee.<\/li>\n\n\n\n<li>Our tool is differential privacy, a technique developed for protecting user privacy in data analysis.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Approach<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>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?<\/li>\n\n\n\n<li>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.<\/li>\n\n\n\n<li>So to get dominant strategy truthfulness, we needed to compute prices that were independent of bidder reports.<\/li>\n\n\n\n<li>But what if we could compute a price p that is almost independent of the reported valuation \\(v_i\\) for every buyer i?<\/li>\n\n\n\n<li>Will this yield, in some sense, an approximate truthfulness guarantee? This will be the idea behind our approach.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Privacy Definitions<\/h4>\n\n\n\n<h5 class=\"wp-block-heading\">Definition<\/h5>\n\n\n\n<p>Two bid vectors \\(v, v&#8217; \\in [0, 1]^n\\) are neighbors if they differ in just a single agent&#8217;s bid, i.e., if there exists an index i such that \\(v_j = v_j&#8217;\\) for every index j \u2260 i.<br>We can now define differential privacy: <\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Definition<\/h5>\n\n\n\n<p>A mechanism \\(M: [0, 1]^n \\to \\textit{O}\\) is \u03b5-differentially private if for every pair of neighboring bid vectors \\(v, v&#8217; \\in [0, 1]^n\\), and for every outcome x \u2208 O:<br>Pr[M(v) = x] \u2264 exp(\u03b5)Pr[M(v&#8217;) = x]<\/p>\n\n\n\n<p>Here, you should think of \u03b5 &lt; 1 as a small constant and think of exp(\u03b5) \u2248 (1 + \u03b5).<br>For \u03b5 \u2264 1, we have:<br>1 + \u03b5 \u2264 exp(\u03b5) \u2264 1 + 2\u03b5<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Approximate Truthfulness<\/h4>\n\n\n\n<p>We can also define what we mean by approximate dominant strategy truthfulness:<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Definition<\/h5>\n\n\n\n<p>A mechanism \\(M: [0, 1]^n \\to \\textit{O}\\) is \u03b5-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 \u2208 [0, 1]^n\\), and every deviation \\(v_i&#8217; \u2208 [0, 1]\\), if we write v&#8217; = \\(v_{-i}, v_i&#8217;\\), then:<\/p>\n\n\n\n<p>\\(E_{o \\sim M(v)}[u_i(v_i, o)] \\geq E_{o \\sim M(v&#8217;)}[u_i(v_i, o)] &#8211; \\epsilon\\)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">The Connection<\/h4>\n\n\n\n<p>Differential privacy will be useful for us because differentially private mechanisms are automatically \u03b5-approximately dominant strategy truthful.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Theorem<\/h5>\n\n\n\n<p>If a mechanism \\(M: [0, 1]^n \\to \\textit{O}\\) is \u03b5-differentially private, then M is also \u03b5-approximately dominant strategy truthful.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">The Connection: Proof<\/h4>\n\n\n\n<p>Fix any buyer i, valuation vector v, and utility function \\(u_i: [0, 1] \\text{x} \\textit{O} \\to [0, 1]\\).<\/p>\n\n\n\n<p>\\(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&#8217;) = o] \\\\ = exp(-\\epsilon) E_{o \\sim M(v&#8217;)}[u_i(v_i, o)] \\\\ \\geq E_{o \\sim M(v&#8217;)}[u_i(v_i, o)] &#8211; \\epsilon\\)<\/p>\n\n\n\n<p>The last inequality follows because for \u03b5 &lt; 1, exp(-\u03b5) \u2265 1 &#8211; \u03b5, and \\(u_i(v_i, o)\\) \u2264 1.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Exploiting the Connection<\/h4>\n\n\n\n<p>So: to design an approximately truthful mechanism that guarantees high revenue, it is sufficient to design a differentially private mechanism with high revenue.<\/p>\n\n\n\n<p>Lets try a straightforward approach: directly picking a price that approximately maximizes revenue for the reported bidder valuations.<\/p>\n\n\n\n<p>As in the last two lectures, lets pick a finite subset of prices P <strong>\u2282<\/strong> [0, 1] to select from.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>Consider the following mechanism (an instantiation of what is called &#8220;the exponential mechanism&#8221; in its more general form):<br><strong>ExpMech<\/strong>(v, \u03b5, P):<\/p>\n\n\n\n<p><strong>Define<\/strong> Rev(p, v) = \\(p \\cdot |{i: v_i \\geq p}|\\)<br><strong>Output<\/strong> each p \u2208 P according to the following probability distribution:<\/p>\n\n\n\n<p>Pr[p] = \\(\\frac{1}{\\Phi(v)}exp(\\frac{\\epsilon \\cdot Rev(p, v)}{2})\\)<\/p>\n\n\n\n<p>where \\(\\Phi(v) = \\sum_{p \\in P} exp(\\frac{\\epsilon \\cdot Rev(p, v)}{2})\\)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Privacy\/Truthfulness<\/h4>\n\n\n\n<h5 class=\"wp-block-heading\">Theorem<\/h5>\n\n\n\n<p>For any \u03b5, P: ExpMech(\u30fb, \u03b5, P) is \u03b5-differentially private.<br>(and thus \u03b5-approximately dominant strategy truthful)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Proof<\/h4>\n\n\n\n<p>Fix any pair of neighboring bid vectors v, v&#8217; and any output p. We have: <\/p>\n\n\n\n<p>\\(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&#8217;)+1)}{2}) \\\\ = \\frac{1}{\\Phi (v)}exp(\\frac{\\epsilon}{2})exp(\\frac{\\epsilon \\cdot Rev(p, v&#8217;)}{2}) \\\\ \\leq exp(\\frac{\\epsilon}{2})\\frac{1}{\\Phi (v)}exp(\\frac{\\epsilon}{2})exp(\\frac{\\epsilon \\cdot Rev(p, v&#8217;)}{2}) \\\\ = exp(\\epsilon)Pr[EM(v&#8217;, \\epsilon, P) = p]\\)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">And Revenue&#8230;<\/h4>\n\n\n\n<h5 class=\"wp-block-heading\">Theorem<\/h5>\n\n\n\n<p>For any P, v, \u03b5, \u03b4, with probability 1 &#8211; \u03b4, ExpMech(v, \u03b5, P) outputs a price p such that:<\/p>\n\n\n\n<p>\\(Rev(p, v) \\geq max_{p* \\in P}Rev(p*, v) &#8211; \\frac{2}{\\epsilon} \\cdot ln(\\frac{|P|}{\\delta})\\)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Proof<\/h4>\n\n\n\n<p>Let \\(p* = max_{p* \\in P}Rev(p*, v)\\). For any value x, we have:<\/p>\n\n\n\n<p>\\(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})\\)<\/p>\n\n\n\n<p>Now choose x = Rev(p*, v) &#8211; \\(\\frac{2}{\\epsilon} \\cdot ln(\\frac{|P|}{\\delta})\\). Plugging that in above, we get: <\/p>\n\n\n\n<p>\\(Pr_{p}[Rev(p, v) \\leq x] \\leq |P| \\cdot exp(-ln(\\frac{|P|}{\\delta})) \\\\ = |P| \\cdot \\frac{\\delta}{|P|} \\\\ = \\delta\\)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Putting it all Together<\/h4>\n\n\n\n<p>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|.<\/p>\n\n\n\n<p>This is a familiar tradeoff.<\/p>\n\n\n\n<p>Now our dependence on |P| is only logarithmic&#8230;<\/p>\n\n\n\n<p>Lets again see what happens when we take the natural discretization:<\/p>\n\n\n\n<p>P = {\u03b1, 2\u03b1, 3\u03b1, &#8230;, 1}<\/p>\n\n\n\n<p>Just as before, |P| = 1\/\u03b1, and that we have the guarantee that for all v:<\/p>\n\n\n\n<p>\\(max_{p \\in P}Rev(p,v) \\geq max_{p \\in [0,1]}Rev(p,v) &#8211; \\alpha n\\)<\/p>\n\n\n\n<p>Combining our bounds we see that if we discretize the price space by \u03b1, with probability 0.99, we obtain revenue: <\/p>\n\n\n\n<p>\\(Rev(p,v) \\geq OPT &#8211; \\alpha \\cdot n &#8211; O(\\frac{1}{\\epsilon}ln(\\frac{1}{\\alpha}))\\)<\/p>\n\n\n\n<p>Choosing \u03b1 = 1\/n, we find that for any \u03b5, we can obtain an \u03b5-approximately dominant strategy truthful mechanism which obtains revenue: <\/p>\n\n\n\n<p>\\(Rev(p,v) \\geq OPT &#8211; O(\\frac{log n}{\\epsilon})\\)<\/p>\n\n\n\n<p>If we take e.g. \u03b5 = O(1\/log(n)), then we have an asymptotically truthful mechanism (in the sense that it becomes exactly truthful as n \u2192 \u221e) 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.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Reference<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Aaron Roth, (23\/25) NETS 4120: Algorithmic Game Theory, Spring 2023, Apr 26, 2023, <a href=\"https:\/\/youtu.be\/AeqrOCtAs4w?si=gAJNHf3dGNXx-oJU\" rel=\"noopener\">https:\/\/youtu.be\/AeqrOCtAs4w?si=gAJNHf3dGNXx-oJU<\/a><\/li>\n<\/ul>\n\n\n\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>Mechanism Design via Differential Privacy<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[154],"tags":[155,4,168],"class_list":["post-3411","post","type-post","status-publish","format-standard","hentry","category-dp","tag-differential-privacy","tag-game-theory","tag-jan-20-2024"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3411"}],"collection":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/comments?post=3411"}],"version-history":[{"count":48,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3411\/revisions"}],"predecessor-version":[{"id":3491,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3411\/revisions\/3491"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=3411"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=3411"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=3411"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}