Differentially Private Spectrum Auction with Approximate Revenue Maximizati on Ruihao Zhu, Zhijing Li*, Kang G. Shin, Fan Wu*, and Guihai Chen Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor *Department of Computer Science and Engineering Shanghai Jiao Tong University Outline
Background Problem Definition Primers: differential privacy, exponential m ech., approx. truthfulness DEAR Extension Evaluation Results Spectrum Need Forecast Table of Results FCC whitepaper, Oct. 2010
Secondary Spectrum Market Traditionally, static, long-term licenses Radio spectrum is not fully utilized Unlicensed bands are getting crowded =>Dynamic spectrum redistribution/auction needed! Unique Challenge in Spectrum A uctions Spatial Reusability
Bidders far away can use the same channel Channel 1 Channel 2 Traditional Spectrum Auctions Auctioneer Bidders Channels
Auctioneers Revenue Traditional Spectrum Auctions Auctioneer Bidders Channels True
valuations are sensitive information Spectrum auction mechanisms stimulate the bidders to truthfully reveal their valuations of channels. Privacy in Spectrum Auctions
Channels are for short-term usage. Sequential auctions make inference of bid ding information possible even with secure channel. Privacy in Spectrum Auctions, contd 1 Single channel First time:
Second time: 2 Goal Design an auction mechanism that maxi mizes auctioneers revenue while keepin g participants bidding prices confidential Outline Background
Problem Definition Primers: differential privacy, exponential m ech., approx. truthfulness DEAR Extension Evaluation Results Model and Assumptions : # of homogenous channels owned by aucti oneer : interference range
: # of bidders, each bidding for a channel wi th : set of prices for all channels : conflict graph of bidders : indicator of channel assignment : payment of bidder i : auctioneers total revenue Outline Background Problem Definition
Primers: differential privacy, exponential m ech., approx. truthfulness DEAR Extension Evaluation Results Differential Privacy Differential Privacy, contd
Defn. A mechanism M is-differential private if for any two data profile D1 and D2 differing on a sing le element, and all S Range(M), Pr[M(D1) S] exp()Pr[M() S] Differential Privacy contd Randomness (no deterministic DP): - Input perturbation - Exponential mechanism (output perturb ation)
Exponential Mechanism Defn. Choose outcome x with probability Pr[x] exp((,, )). Inputs. Objective function .
EM is-differentially private, where largest difference for any two adjacent data sets. Approximate Truthfulness Defn. Let be the strategy under which player behaves truthfully. A mechanism is said to be -truthful if for every player , for any strategy and any other players strategies, , , where > 0 is a small constant.
Outline Background Problem Definition Primers: differential privacy, exponential m ech., approx. truthfulness DEAR Extension Evaluation Results Mechanism design Bidder Grouping
Probability Calculation Random Selection and Allocation =1 channel =4 bidders with : price set
01/16/2020 20 Mechanism design Random Selection and Allocation Probability Calculation
Bidder Grouping 4 2 1 3 01/16/2020 21
Mechanism design Bidder Grouping 1. Partition 2. Grouping: 4 2 1
3 3. Subgroups: 01/16/2020 22 Mechanism design ; Probability
Calculation For , (1) Remove bidders bid lower than p. 4 2 1 3
01/16/2020 23 Mechanism design ; Probability Calculation For , (2) For each subgroup , randomly select
bidders as candidates. 4 2 1 3 01/16/2020 24
Mechanism design ; Probability Calculation For , (3) The winning bidders are the ones in the group with most candidates.
4 1 3 01/16/2020 25 Mechanism design ; Probability
Calculation For , (4) The revenue is . 4 1 3 01/16/2020 26
Mechanism design ; Probability Calculation For , (1) Remove bidders w/ bid < p. 4
2 1 3 01/16/2020 27 Mechanism design ; Probability
Calculation For , (2) For each subgroup , randomly select bidders as candidates. 3 01/16/2020 28
Mechanism design ; Probability Calculation For , (3) The winning bidders are the ones in the group with most candidates. 3
01/16/2020 29 Mechanism design ; Probability Calculation For , (4) The revenue is .
3 01/16/2020 30 Mechanism design Probability Calculation
3. Probability of this instance is set as: i.e., 01/16/2020 31 Mechanism design Probability Calculation
4. Normalizes the probability 01/16/2020 32 Mechanism design Random Selection and Allocation
DEAR randomly selects a price as bidders payment based on this calculated probability, and allocates channels to the corresponding winners. 01/16/2020 33 Properties of DEAR Theorem1. DEAR achieves 2-differential privacy.
Theorem2. DEAR achieves 4-truthfulness. Theorem3. DEAR has an expected revenue at least - ln(e + ), where is the optimal revenue in the single uniform price setting. 01/16/2020 34 Outline Background
Problem Definition Primers: differential privacy, exponential m ech., approx. truthfulness DEAR Extension Evaluation Results Extended DEAR Each bidder may bid for multiple channels and have a budget.
, the budget of bidder ; Each bidder may want to win multiple channels. 01/16/2020 36 Extended DEAR (Reduction) Virtual Bidder For price , bidder with bid > could get at most
different channels =>DEAR creates virtual bidders for bidder . 01/16/2020 37 Extended DEAR (Reduction) Virtual Bidder Each bidders budget is the same as his bid
01/16/2020 38 Extended DEAR (Reduction) Virtual Bidder ; For , bidder 3 can win 2 channels. 4
2 1 3 01/16/2020 39 Extended DEAR (Reduction) Virtual Bidder ;
For , bidder 3 can win 2 channels. 4 2 12 33 1
01/16/2020 40 Properties of Extended DEAR Theorem1. Extended DEAR achieves 2differential privacy. Theorem2. Extended DEAR achieves 4truthfulness. Theorem3. Extended DEAR has an expected revenue at least - ln(e + ), where is the optimal revenue in single uniform price setting
01/16/2020 41 Outline Background Problem Definition Primers: differential privacy, exponential m ech., approx. truthfulness DEAR
Extension Evaluation Results Evaluation Results Revenue of DEAR (15 channels) 01/16/2020 43 Evaluation Results
Revenue of DEAR (20 channels) 01/16/2020 44 Evaluation Results Revenue of DEAR (30 channels) 01/16/2020
45 Evaluation Results Revenue of extended DEAR () 01/16/2020 46 Evaluation Results Revenue of extended DEAR ()
01/16/2020 47 Privacy Leakage Given a mechanism , suppose and are probability distributions over a price set for bids and , which only differ in a single bid. Privacy leakage between the two bids is the maximum of absolute differences between logarithmic probabilities of the two
distributions: 01/16/2020 48 Evaluation Results Privacy of DEAR 01/16/2020
49 Evaluation Results Privacy of extended DEAR 01/16/2020 50 Conclusion DEAR: First differentially private spectrum
auction mechanism with approximate revenue maximization. DEAR performs well with both single- and multichannel requests when bidders have budget constraints. Theoretically proved the properties in revenue and privacy. Implemented DEAR and extensively evaluated its performance. 01/16/2020
51 Thank you! [email protected]
