Computational Advertising Homework 2

CS 498: Computational Advertising
Homework 2

1 General Instructions
• This assignment is due at 11:59 PM on the due date. We will be using Gradescope to collect this
assignment. The homework MUST be submitted in pdf format on gradescope.
Contact TAs if you face technical difficulties in submitting the assignment. We shall NOT accept any
late submission!
Please make sure to appropriately map/assign the pages of your submitted pdf to each sub-question
listed in the homework outline. Handwritten answers are not acceptable. Name your pdf file as
YourNetid-HW2.pdf
• For all questions, you need to explain the logic of your answer/result for every sub-part. A result/answer without any explanation will not receive any points.
• It is OK to discuss with your classmates and TAs regarding the methods, but it is NOT OK to
work together or share code. Plagiarism is an academic violation to copy, to include text from other
sources, including online sources, without proper citation. To get a better idea of what constitutes
plagiarism, consult the CS Honor code (http://cs.illinois.edu/academics/honor-code) on academic
integrity violations, including examples, and recommended penalties. There is a zero tolerance policy
on academic integrity violations; Any student found to be violating this code will be subject to
disciplinary action.
• Please use Piazza if you have questions about the homework. Also, feel free to send TAs emails and
come to office hours.
Questions 1, 2 and 3 are based on Chapter 9 on Auctions 1 and Chapter 15 on Sponsored
Search Markets2
.
Question 1 (4 points)
In Section 9.8 (Exercises), solve Problem (3).
Question 2 (4 + 4 = 8 points)
In Section 15.10 (Exercises), solve Problem (2).
1https://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch09.pdf
2https://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch15.pdf
1
Repeat (a) to compute the socially optimal allocation using Generalized Second Price
(GSP) auctions.
Question 3 (3+ 5 = 8 points)
In Section 15.10 (Exercises), solve Problem (6).
Question 4 (5+5 = 10 points)
The objective of this question is to sketch frameworks to achieve privacy during web searching
and browsing. Since many websites restrict services with incognito browsing or ad-blockers,
the goal is to preserve user anonymity (as much as possible) without blocking ads (and hence
tracking).
Note: This question does not have a single correct answer. Points will be awarded based
on creativity and clarity of answers.
1. We examine strategies to achieve privacy during web search. Towards this goal, an
influential work by [1] introduced a browser extension that obfuscates users’ actual
searches by programmatically generating a stream of decoy searches, with goal of confusing the search engine. Briefly describe the advantages and limitations of such an
approach to achieve privacy, and suggest a framework that improves upon this idea.
2. Consider a web browsing scenario where third-party websites track users across websites
through the use of cookies. Briefly outline a solution to avoid (or mitigate) the amount
of private information made available to trackers, while preserving anonymity as much
as possible. Hint: Analyze the mechanism of cookie synchronization.
References
[1] Nissenbaum, Helen, and Howe Daniel. ”TrackMeNot: Resisting surveillance in web
search.” (2009).
2