CSCI 1440/2440 Introduction to Game Theory - Homework 6: Approximation Mechanisms
Homework 6: Simple, Approximate Mechanisms CSCI 1440/2440
2022-03-17
Due Date: Tuesday, March 22, 2022. 11:59 PM.
We encourage you to work in groups of size two. Each group need only submit one solution. Your submission must be typeset using LATEX. Please submit via Gradescope with you and your partner’s Banner ID’s and which course you are taking.
For 1000-level credit, you need only solve the first two problems. For 2000-level credit, you should solve all three problems.
1 The Prophet Inequality is Tight
Prove that the 2-approximation given by the prophet inequality is tight. That is, establish a corresponding upper bound by giving an example of independent distributions G1, . . . , Gn for n ≥ 2 for which there does not exist a strategy (threshold or otherwise) that accrues higher reward than 1/2 that of the prophet.
Hint: Exhibit independent distributions G1, . . . , Gn such that for all ε > 0, all strategies (threshold or otherwise) yield expected value strictly less than (1/2 + ε) Eπ∼G max πi , where Eπ∼G [maxi πi] is i the expected reward of the prophet.
2 A Dynamic Threshold Strategy
Recall the game that motivated the Prophet Inequality: Assume n independent random variables π with non-negative, continuous distributions Gi. The distributions Gi are known in advance, but the “prize” πi is not revealed until period i. The player can then choose to accept πi and end the game, or reject it and continue playing.
In lecture, we proved that the following (static) thresholding strat- egy is guaranteed to obtain at least half the expected value of an omniscient prophet who knows all the prizes πi in advance:
1. Select a threshold value t s.t. pt=Pr(πj<t,∀1≤j≤n)=1/2. 2. Accept the first prize πi, if any, that exceeds t.
In this problem, we will consider a dynamic thresholding strategy, and analyze its performance. The dynamic variant uses the static strategy in the first period, and then, in all later periods i:
- Compute a new threshold ti s.t. Pr(πj < ti, ∀i ≤ j ≤ n) = 1/2.
- Accept πi if it exceeds the current threshold ti.
In answering the following questions, you should assume an i.i.d. setting, with Gi = Uniform(0, 1), for all i ∈ {1, . . . , n}.
- Compute the static threshold t, as a function of n, and the ex- pected value of the static thresholding strategy.
- Compute the dynamic threshold t, as a function of n, and the expected value of the dynamic thresholding strategy.
Hint: For this question, you may plot the expected values of the static and dynamic strategies for various values of n instead of computing the expected value analytically.
- Compare the expected values of the static and dynamic strategies asymptotically, as n → ∞?
- Extra Credit: Assuming i.i.d. random variables, is the dynamic strategy guaranteed to outperform the static one? Provide either a proof or a counterexample.
3 Multi-Unit Prophet Inequality
In class, we presented a simple thresholding strategy for obtaining a 1/2-approximation of the optimal expected reward (OPT) in the game described in Problem 2. This strategy involved selecting a threshold t such that the probability that one rejects all the prizes is exactly 1/2.
In this problem, we will provide an alternative strategy that also obtains a 1/2-approximation. We will then generalize it to the k-choice version of the game, where one can accept up to k prizes.
Let πi ∼ Gi (for Gi not necessarily uniform). Define pi to be the probability that πi takes on the highest value: i.e., pi = Pr(πi > π , ∀j < i). (For simplicity, you can assume ∑n p = 1.) Fur- j i=1 i
thermore, define ti such that Pr(πi ≥ ti) = pi. Now, consider the following strategy: At stage i of the game, reject with probability 1/2, regardless of the value of πi. Otherwise, accept if πi ≥ ti.
1. Show that this strategy achieves a 1/4-approximation of OPT. Hint: You might find Markov’s inequality useful: For any non-negative random variable X,
Pr (X ≥ x) ≤ E[X] x
2. We now generalize the strategy as follows: Let 1 − qi denote the probability of blindly rejecting prize πi, and define ri to be the probability of rejecting prizes 1 through i − 1. Find a sequence of qi such that this strategy achieves a 1/2-approximation of OPT.
Hint: Rewrite the prophet’s expected reward in terms of qi and ri.
3. Now consider the k-choice version of this game where we can choose up to k of the n prizes and thus seek to maximize the ex- pected sum of the rewards of the selected prizes. Let pi denote the probability that πi is among the top k prizes. (Again, for simplic- ity,assume∑n p =k.)Definet suchthatPr(π ≥t)=p.
The k-choice strategy works as follows: At stage i of the game, blindly reject πi with probability δ = O k . Otherwise, accept if πi ≥ ti. Using Hoeffding’s inequality, show that this strategy achieves a 1 − O -approximation of OPT.
Hoeffding’s inequality: For random variables X1, . . . , Xn such that Xi ∈[0,1]foralli∈[n],
Pr n∑Xi−E[Xi]≥t ≤exp −2nt
