CS 581, Homework 1
(25 points) Random variables
Given two independent random variables and that follow the distribution, let .
What is the CDF of ?
Let the pdfs of and be
What is the expected value of ?
(25 points) Proofs
Argue whether the following is a correct statement with a correct proof. If the statement is incorrect provide a counter-example, and point out the mistake in the proof. If the statement is correct but the proof is incorrect, explain the proof’s mistake and provide a correct proof.
Statement: The maximum of on the interval is achieved at .
Proof: The derivative of is . The critical points are and . , so we can see that is a local minimum and is a local maximum. Since is the only local maximum, it must also be the constrained maximum.
The statement is correct, but the proof is incorrect. It is necessary to check the values of the function on the boundaries of the interval as well as the critical points for local extrema.
Proof: The derivative of is . The critical points are and . , so we can see that is a local minimum and is a local maximum.
Evaluating the boundaries and the extrema, we get , confirming that is the local maximum.
(25 points) Duals
Find the dual of the following linear program:
(25 points) NP-hardness
The Fair problem is the following.
Input. Numbers and , representing the values that two agents with additive preferences, agent 1 and agent 2, respectively, have for items.
Output. Decide whether there is a partition of the items among the agents such that the value of items given to an agent is at least her value for the items given to the other agents. Formally, two sets, and such that (i) , . (ii) , and (iii) .
Prove that this problem is NP-complete.
Given allocations and , you can find the values of the summations in (ii) and (iii) in linear time, thus it is NP.
To show that it is NP-Hard, reduce Partition to Fair. Let be the set of positive integers given by the partition problem. Let , which can clearly be done in polynomial time. Since the valuations of both agents are equal, the only allocation where the agents are envy-free is one where , which partitions the set into two sets with an equal sum. If Fair has a solution, then and sets are valid for the partition, and if Partition has a solution , then those sets are valid for Fair.