CS535 HW4

Problem 1 §

Problem 2 §

Subproblem 1 §

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

Subproblem 2 §

Mechanism $A$ will calculate MNW $x^{\ast }={\text{argmax}}_x{\sum }_{\forall i}\ln U_i(x)$ with the final allocation for agent $i$ being:

$$x_i^F=x_i^{\ast }\frac{{\prod }_{j\ne i}{U}_j(x^{\ast })}{{\prod }_{j\ne i}{U}_j(x_{-i}^{\ast })}$$

where, per the problem $x_{-i}^{\ast }={\text{argmax}}_x{\sum }_{j\ne i}\ln U_j(x)$, i.e. running MNW without agent $i$. For agent $i$, their final utility is

$$U_i^F=U_i(x_i^{\ast }\frac{{\prod }_{j\ne i}{U}_j(x^{\ast })}{{\prod }_{j\ne i}{U}_j(x_{-i}^{\ast })})=U_i(x_i^{\ast })\cdot \frac{{\prod }_{j\ne i}{U}_j(x^{\ast })}{{\prod }_{j\ne i}{U}_j(x_{-i}^{\ast })}$$

due to the utilities being additive utilities. On the other hand, a VCG auction will allocate $x^{\ast }={\text{argmax}}_x{\sum }_{\forall i}\ln b_i(x)$ where $b_i$ is the reported utility that may not be truthful. We consider agent $i$, while fixing everybody else’s reported utilities $\overrightarrow{b_{-i}}$. The payment charged to agent $i$ is:

$$\begin{array}{rlr}{p}_i& =\sum _{j\ne i}\ln b_j(x_{-i}^{\ast })-\underset{={\sum }_{j\ne i}\ln b_j(x^{\ast })}{\underbrace{\left(\sum _{\forall j}\ln b_j(x^{\ast })-\ln b_i(x^{\ast })U\right)}}& \text{per definition of VCG}\\ & =\ln \prod _{j\ne i}{b}_j(x_{-i}^{\ast })-\ln \prod _{j\ne i}{b}_j(x^{\ast })& \\ & =-\ln \left(\frac{{\prod }_{j\ne i}{b}_j(x^{\ast })}{{\prod }_{j\ne i}{b}_j(x_{-i}^{\ast })}\right)& \end{array}$$

Thus for agent $i$ their final utility is

$$\begin{array}{rlr}{U}_i^F& =\ln U_i(x^{\ast })-p_i& \text{per the question}\\ & =\ln U_i(x^{\ast })+\ln \left(\frac{{\prod }_{j\ne i}{b}_j(x^{\ast })}{{\prod }_{j\ne i}{b}_j(x_{-i}^{\ast })}\right)& \\ & =\ln \left(U_i(x^{\ast })\frac{{\prod }_{j\ne i}{b}_j(x^{\ast })}{{\prod }_{j\ne i}{b}_j(x_{-i}^{\ast })}\right)& \end{array}$$

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 $A$.

Specifically:

$$\begin{array}{r}\ln f_i=\ln \prod _{j\ne i}{U}_j(x^{\ast })-\ln \prod _{j\ne i}{U}_j(x_{-i}^{\ast })\le 0\end{array}$$

Since product of optimal utility allocation with $j$ divided by $U_j(x^{\ast })$, cannot be better than product of optimal utility allocation without $j$ in the first place (adaptation of logic from lecture). Thus we have $f_i\le 1$.

Subproblem 2b The correspondence between utilities will be:

$$\ln U_i^{F,\text{Mech.A}}=U_i^{F,\text{VCG}}$$

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

Subproblem 2c

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

$$\begin{array}{rlr}{U}_i^{F,\text{VCG}}& =\ln U_i(x^{\ast })-\underset{\text{ i cannot influence }}{\underbrace{\ln \prod _{j\ne i}{b}_j(x_{-i}^{\ast })}}+\ln \prod _{j\ne i}{b}_j(x^{\ast })& \\ \text{max}{U}_i^{F,\text{Mech.A}}& ⟺\text{max }{U}_i^{F,\text{VCG}}& \text{establised in 2b}\\ & ⟺\text{max}\left(\ln U_i(x^{\ast })+\ln \prod _{j\ne i}{b}_j(x^{\ast })\right)& \\ & ⟺\text{max}\ln \prod _{\forall j}{b}_j(x^{\ast })& \text{since b−i is fixed}\\ & =\text{max}\sum _{\forall j}\ln b_j(x^{\ast })& \text{Nash welfare max.}\end{array}$$

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

Subproblem 2d

As outlined in the problem statement, for any allocation $\hat{x}$:

$$\begin{array}{rlr}\sum _{\forall i}\frac{U_i(\hat{x})}{U_i(x^{\ast })}& \le n& \text{remove specific agent i}\\ \sum _{j\ne i}^{n-1}\left(\frac{U_j(x_{-i}^{\ast })}{U_j(x^{\ast })}-1\right)& \le 1& \text{set }\hat{x}:=x_{-i}^{\ast }\end{array}$$

Now, using the hint from problem statement, set $d_i:=\frac{U_j(x_{-i}^{\ast })}{U_j(x^{\ast })}-1$ Then since ${\sum }_{j\ne i}^{n-1}{d}_i<1$, ${\prod }_{j\ne i}^{n-1}(d_i+1)\le (1+\frac{1}{n-1}{)}^{n-1}$. Then:

$$\begin{array}{rl}{\left(\frac{n}{n-1}\right)}^{n-1}& \ge \prod _{j\ne i}^{n-1}\frac{U_j(x_{-i}^{\ast })}{U_j(x^{\ast })}\\ & =\frac{{\prod }_{j\ne i}{U}_j(x^{\ast })}{{\prod }_{j\ne i}{U}_j(x_{-i}^{\ast })}\\ & =\frac{1}{f_i}\\ \underset{n\to \infty }{\lim }{\left(\frac{n}{n-1}\right)}^{n-1}& \ge \underset{n\to \infty }{\lim }\frac{1}{f_i}\\ \frac{1}{e}& \le \underset{n\to \infty }{\lim }{f}_i\end{array}$$

■

Problem 3 §

Subproblem 1 §

Let allocation $A$ be EF1, i.e. $\forall i\forall j\exists g\text{ s.t. }{v}_i(A_i)\ge v_i(A_j\setminus \{g\})$. Now, if we sum over all agents $j$ that is not $i$ on both sides:

$$\begin{array}{rlr}\forall i\exists \vec{g}\text{ s.t. }(n-1)v_i(A_i)& \ge \sum _{j\ne i}{v}_i(A_j\setminus \{g_{ij}\})& \\ n{v}_i(A_i)& \ge \sum _{j\ne i}{v}_i(A_j\setminus \{g_{ij}\})+v_i(A_i)& \text{adding vi(Ai) to both sides}\\ & =\sum _{j\ne i}(v_i(A_j)-v_i(\{g_{ij}\}))+v_i(A_i)& \\ & =\sum _{j\ne i}{v}_i(A_j)+v_i(A_i)-\sum _{j\ne i}{v}_i(g_{ij})& \\ & =\sum _{\forall j}{v}_i\left(A_j\right)-\sum _{j\ne i}{v}_i(g_{ij})& \end{array}$$

To bound each of these terms, we use:

$$\begin{array}{rlr}\sum _{j\ne i}{v}_i(g_{ij})& \le \sum _{j\ne i}{\text{max}}_{g_{ij}\in A_j}{v}_i(g_{ij})& \text{take item i values most from everybody else}\\ & \le (n-1){\text{max}}_g{v}_i(g)& \text{just take maximum value item}\end{array}$$

Then returning to our original inequality:

$$\begin{array}{rl}n{v}_i(A_i)& \ge \underset{=v_i({\bigcup }_{\forall j}{A}_j)}{\underbrace{\sum _{\forall j}{v}_i(A_j)}}-(n-1){\text{max}}_g{v}_i(g)\\ \underset{\text{ value of EF1 allocation to i }}{\underbrace{v_i(A_i)}}& \ge \underset{\text{ value of proportional allocation to i }}{\underbrace{\frac{v_i({\bigcup }_{\forall j}{A}_j)}{n}}}-\underset{\text{ some constant }}{\underbrace{\frac{n-1}{n}{\text{max}}_g{v}_i(g)}}\end{array}$$

■

Problem 4 §

• let $X_i^j$ be the the utility of $i$ getting item $j$. Per the question this is $\text{Unif}[0,1]$.
• let $Y_{-i}^j$ be the largest utility an agent gives for item $j$, i.e. $Y_{-i}^j:={\text{max}}_{k\ne i}{X}_k^j$.
• From this we know that the probability that agent $i$ will get item $j$ is $\mathbb{P}(X_i^j>Y_{-i}^j)$ We first calculate $i$’s expected utility, $U_i$ from getting its own bundle:

$$\begin{array}{rl}\mathbb{E}(U_i):=& \mathbb{E}\left(\sum _{\forall j}{X}_i^j\underset{\text{ i bid max? }}{\underbrace{1_{X_i^j>Y_{-i}^j}}}\right)\\ & =\sum _{\forall j}\underset{=\frac{n}{n+1}\text{ , see explaination below}}{\underbrace{\mathbb{E}(X_i^j\mid X_i^j>Y_{-i}^j)}}\underset{=\frac{1}{n}}{\underbrace{\mathbb{P}(X_i^j>Y_{-i}^j)}}\\ & =m\cdot \frac{n}{n+1}\cdot \frac{1}{n}\end{array}$$

Note that

$$\begin{array}{rlr}\mathbb{E}(X_i^j|X_i^j>Y_{-i}^j)& =\mathbb{E}(X_i^j\text{ given it is largest bid for }j)& \\ & =\mathbb{E}(n\text{-th smallest bid from n i.i.d uniform r.v. 0 to 1})& \\ & =\frac{n}{n+1}& \text{Per the given hint}\end{array}$$

In a similar fashion, we can calculate $i$’s expected utility from getting another agent $k$’s bundle, $U_{ik}$:

$$\begin{array}{rl}\mathbb{E}(U_{ik})& :=\mathbb{E}\left(\sum _{\forall j}{X}_i^j\cdot 1_{X_k^j>Y_{-k}^j}\right)\\ & =\sum _{\forall j}\mathbb{E}(X_i^j|\underset{\text{ doesn’t matter }}{\underbrace{X_k^j>Y_{-k}^j}})\cdot \mathbb{P}(X_k^j>Y_{-i}^j)\\ & =m\cdot \frac{1}{2}\cdot \frac{1}{n}\end{array}$$

Now, since the product $X_i^j\cdot 1_{X_i>Y_{-i}^j}$ themselves are independent random variables for all $i$, bounded from $[0,1]$, and considering that Hoeffding’s inequality doesn’t require identical distribution), we can use it to state:

$$\begin{array}{rlr}\mathbb{P}(U_i\ge \mathbb{E}(U_i)-t)& \le e^{-2t^2/{\sum }_{\forall \text{items}}(1-0)}& \\ & =e^{-2t^2/m}& \\ \mathbb{P}(U_{ik}\le \mathbb{E}(U_{ik})+t)& \le e^{-2t^2/m}& \text{Equivalently}\end{array}$$

Replacing $\mathbb{E}(U_i),\mathbb{E}(U_{ik})$ with the values we calculated above, as well as set $t:=\frac{m}{2(n+1)}$ we get:

$$\begin{array}{r}\mathbb{P}\left(U_i\ge \frac{m}{2(n+1)}\right)\le e^{-m/2(n+1{)}^2}\\ \mathbb{P}\left(U_{ik}\le \frac{3m}{2(n+1)}\right)\le e^{-m/2(n+1{)}^2}\end{array}$$

Now, the probability that $i$ will envy $k$ can be stated $\mathbb{P}(U_i<U_{ik})$. Using the union bound inequality:

$$\begin{array}{rl}\mathbb{P}(U_i<U_{ik})& \le \mathbb{P}\left(U_i\le \frac{m}{2(n+1)}\text{and }{U}_{ik}\ge \frac{3m}{2(n+1)}\right)\\ & \le \mathbb{P}\left(U_i\le \frac{m}{2(n+1)}\right)+\mathbb{P}\left(U_{ik}\le \frac{3m}{2(n+1)}\right)\\ & \le 2e^{-m/2(n+1{)}^2}\end{array}$$

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

$$\begin{array}{rl}\mathbb{P}(\bigcup _{i,k}{U}_i<U_{ik})& \le \underset{n\text{ total agents, }}{\underbrace{\sum _i}}\underset{n\text{ total agents}}{\underbrace{\sum _k}}\mathbb{P}(U_i<U_{ik})\\ & =n^{2}2e^{-m/2(n+1{)}^2}\\ & \stackrel{m\to \infty }{⟶}0\end{array}$$

■