Class 16: Auctions with Integrity

Class 16: Auctions with Integrity
https://uvammm.github.io/class16

Markets, Mechanisms, and Machines
University of Virginia
cs4501/econ4559 Spring 2019
David Evans and Denis Nekipelov
https://uvammm.github.io/

1. MARKETS, MECHANISMS, MACHINES University of Virginia, Spring 2019 Class 16: Auctions with Integrity 7 March 2019 cs4501/econ4559 Spring 2019 David Evans and Denis Nekipelov https://uvammm.github.io
2. In-Class Auction Item for bid: +$1000 for your team’s budget for Project 4 Your bid is !", virtual dollars from the Project 4 budget Auction mechanism: winner: highest bid, pays !($), gets $1000 “loser”: second highest bid, pays !(&), gets nothing 1 Auction ends when last late student enters classroom (or at 9:59am). Bid by sending a slack message to #inclass: (team, bid) – to be valid, must increase previous bid by at least $1
3. 2 Auction Result: Team 3: - $201 Team 7: + $3 Dave: + $198
5. On-line Ad Auction Integrity How can we trust the auctioneer (Google, Facebook)? Verifiable Auctions Click Fraud 4
6. Second Weighted-Price Auction Bidder Score Score-Weighted Bid Price !" #" !" #" !$ #$ /#" !$ #$ !$ #$ !& #& /#$ !& #& !& #& !' #' /#& … … … … 5 If auctioneer is unethical, short-term revenue maximizing, what should auctioneer charge winner?
7. Verifiable Generalized Second-Price Auction Bidder Price !" !# !# !$ !$ !% … … 6 Goal: Prove to winner bidder that !# is the correct price. Keep all bids other than the winners private.
8. Verifiable Auction 7 Image from: Sebastian Angel and Michael Walfish, Verifiable Auctions for Online Ad Exchanges, SIGCOMM 2013. Seller: Winning Bidder: Auction outcome: ("#$$#$% &#''(), +)#,()
9. Cryptographic Hash Function A cryptographic hash function, !(#), must satisfy these two properties: one-way (preimage resistance): given ℎ = !(#) it is hard to find preimage #. strong collision-resistance: hard to find any pair # and ' where !(#) = !('). 8
10. Cryptographic Hash Function A cryptographic hash function, !(#), must satisfy these two properties: one-way (preimage resistance): given ℎ = !(#) it is hard to find preimage #. strong collision-resistance: hard to find any pair # and ' where !(#) = !('). 9 Ideal: “Random Oracle” Instantiation: SHA-256
11. Implementing a Hash Function 10 IV K Å !1 #$ Å ! 2 # 2 ... K Å !& '(!) = #+ Cipher Block Chaining Encrypt Encrypt Encrypt
12. SHA-2 11 http://opencores.org/project,sha256core SHA-256 256-bit output 64 rounds (best known attacks break preimage resistance for 52 rounds)
13. Hash Chain 12 Hash ! Hash Hash Hash "# = %#(!) "( ") "* … Assuming inverting is hard, what can you prove using "# ?
14. Charge 13 “The best minds of my generation are thinking about how to make people click ads. That sucks.” Jeff Hammerbacher (Facebook → Cloudera → Mount Sinai Medicine)