Problem 1

Problem 2

Subproblem 1

Simply reporting utility on every item will result in the agent getting all items and thus maximum utility.

Subproblem 2

Mechanism will calculate MNW with the final allocation for agent being:

where, per the problem , i.e. running MNW without agent . For agent , their final utility is

due to the utilities being additive utilities. On the other hand, a VCG auction will allocate where is the reported utility that may not be truthful. We consider agent , while fixing everybody else’s reported utilities . The payment charged to agent is:

Thus for agent their final utility is

Subproblem 2a

Now, the correspondence comes from the fact that the subtraction of final utility due to VCG payment corresponds to the scaling down of utility in mechanism .


Since product of optimal utility allocation with divided by , cannot be better than product of optimal utility allocation without in the first place (adaptation of logic from lecture). Thus we have .

Subproblem 2b The correspondence between utilities will be:

And since is monotonic maximizing one will maximize the other. (Used in next proof)

Subproblem 2c

Considering the VCG mechanism, agent will attempt to maximize their own final utility, expressed as

Which is to say, in mechanism it is also in ’s best interest to maximize the nash welfare objective. Thus mechanism is DSIC.

Subproblem 2d

As outlined in the problem statement, for any allocation :

Now, using the hint from problem statement, set Then since , . Then:

Problem 3

Subproblem 1

Let allocation be EF1, i.e. . Now, if we sum over all agents that is not on both sides:

To bound each of these terms, we use:

Then returning to our original inequality:

Problem 4

  • let be the the utility of getting item . Per the question this is .
  • let be the largest utility an agent gives for item , i.e. .
  • From this we know that the probability that agent will get item is We first calculate ’s expected utility, from getting its own bundle:

Note that

In a similar fashion, we can calculate ’s expected utility from getting another agent ’s bundle, :

Now, since the product themselves are independent random variables for all , bounded from , and considering that Hoeffding’s inequality doesn’t require identical distribution), we can use it to state:

Replacing with the values we calculated above, as well as set we get:

Now, the probability that will envy can be stated . Using the union bound inequality:

Then, we calculate the probability that there will be no envy between any two agents :