It’s Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents

To prove the mechanism is safely manipulable, we need to show an agent and an alternative bid, such that the agent always weakly prefers the outcome that results from reporting the alternative bid over reporting her true valuation, and strictly prefers it in at least one scenario. We prove that the mechanism is safely-manipulable by all agents with positive valuations.

Let $i\in N$ be an agent with valuation $v_{i}>0$, we shall now prove that bidding $b_{i}<v_{i}$ is a safe manipulation.

We need to show that for any combination of bids of the other agents, bidding $b_{i}$ does not harm agent $i$, and that there exists a combination where bidding $b_{i}$ strictly increases her utility. To do so, we consider the following cases according to the maximum bid of the other agents:

• •

  The maximum bid is smaller than $b_{i}$: if agent $i$ bids her valuation $v_{i}$, she wins the good and pays $v_{i}$, results in utility $0$. However, by bidding $b_{i}<v_{i}$, she still wins but pays only $b_{i}$, yielding a positive utility.

  Thus, in this case, agent $i$ strictly increases her utility by lying.

• •

  The maximum bid is between $b_{i}$ and $v_{i}$: if agent $i$ bids her valuation $v_{i}$, she wins the good and pays $v_{i}$, resulting in utility $0$. By bidding $b_{i}<v_{i}$, she loses the good but pays noting, also resulting in utility $0$.

  Thus, in this case, bidding $b_{i}$ does not harm agent $i$.

• •

  The maximum bid is higher than $v_{i}$: Regardless of whether agent $i$ bids her valuation $v_{i}$ or $b_{i}<v_{i}$, she does not win the good, resulting in utility $0$.

  Thus, in this case, bidding $b_{i}$ does not harm agent $i$.

∎

We need to show that, for each agent $i$ and any bid $b_{i}\neq v_{i}$, at least one of the following is true: either (1) for any combination of bids of the other agents, agent $i$ weakly prefers the outcome from bidding $v_{i}$; or (2) there exists such a combination for which $i$ strictly prefers the outcome from bidding $v_{i}$. We consider two cases.

Case 1: $v_{i}=0$. In this case condition (1) clearly holds, as bidding $v_{i}$ guarantees the agent a utility of $0$, and no potential outcome of the auction can give $i$ a positive utility.

Case 2: $v_{i}>0$. In this case we prove that condition (2) holds. We consider two sub-cases:

• •

  Under-bidding ($b_{i}<v_{i}$): whenever $\displaystyle\max_{j\neq i}b_{j}\in(b_{i},v_{i})$, when agent $i$ bids truthfully she wins the good and pays $(1-t)v_{i}$, resulting in utility $tv_{i}>0$; but when she bids $b_{i}$ she does not win, resulting in utility $0$.

• •

  Over-bidding ($v_{i}<b_{i}$): whenever $\displaystyle\max_{j\neq i}<v_{i}$, when agent $i$ bids truthfully her utility is $tv_{i}$ as before; when she bids $b_{i}$ she wins and pays $(1-t)b_{i}>(1-t)v_{i}$, so her utility is less than $tv_{i}$.

In both cases lying may harm agent $i$. Thus, she has no safe manipulation. ∎

we need to identify an agent $i$, for whom there exists another agent $j\neq i$ and a bid $b_{j}$, such that if $j$ bids $b_{j}$, then agent $i$ has a safe manipulation.

Indeed, let $i\in N$ be an agent with valuation $v_{i}>0$ and let $j\neq i$ be another agent who bids some value $b_{j}\in(v_{i},v_{i}/(1-t))$. We prove that bidding any value $b_{i}\in(b_{j},v_{i}/(1-t))$ is a safe manipulation for $i$.

If $i$ truthfully bids $v_{i}$, she loses the good (as $b_{j}>v_{i}$), and gets a utility of $0$.

If $i$ manipulates by bidding some $b_{i}\in(b_{j},v_{i}/(1-t))$, then she gets either the same or a higher utility, depending on the maximum bid among the unknown agents ($b^{\max}:=\displaystyle\max_{\ell\neq i,\ell\neq i}b_{\ell}$):

• •

  If $b^{\max}<b_{i}$, then $i$ wins and pays $(1-t)b_{i}$, resulting in a utility of $v_{i}-(1-t)b_{i}>0$, as $(1-t)b_{i}<v_{i}$. Thus, $i$ strictly gains by lying.

• •

  If $b^{\max}>b_{i}$, then $i$ does not win the good, resulting in utility $0$. Thus, in this case, bidding $b_{i}$ does not harm $i$.

• •

  If $b^{\max}=b_{i}$, then one of the above two cases happens (depending on the tie-breaking rule).

In all cases $b_{i}$ is a safe manipulation, as claimed. ∎

Let $i\in N$ be an agent with true value $v_{i}>0$, and a manipulation $b_{i}\neq v_{i}$. We show that this manipulation is unsafe even when knowing the bids of $n-2$ of the other agents.

Let $K$ be a subset of $(n-2)$ of the remaining agents (the agents in $K$ are the “known agents”), and let $\mathbf{b}_{K}$ be a vector that represents their bids. Lastly, let $j$ be the only agent in $N\setminus(K\cup\{i\})$. We need to prove that at least one of the following is true: either (1) the manipulation is not profitable — for any possible bid of agent $j$, agent $i$ weakly prefers the outcome from bidding $v_{i}$ over the outcome from bidding $b_{i}$; or (2) the manipulation is not safe — there exists a bid for agent $j$, such that agent $i$ strictly prefers the outcome from bidding $v_{i}$.

Let $\displaystyle b^{\max}_{K}:=\max_{\ell\in K}b_{\ell}$. We consider each of the six possible orderings of $v_{i}$, $b_{i}$ and $b^{\max}_{K}$ (cases with equalities are contained in cases with inequalities, according to the tie-breaking rule):

• •

  $v_{i}<b_{i}<b^{\max}_{K}$ or $b_{i}<v_{i}<b^{\max}_{K}$: In these cases (1) holds, as for any bid of agent $j$, agent $i$ never wins. Therefore the manipulation is not profitable.

• •

  $v_{i}<b^{\max}_{K}<b_{i}$: We show that (2) holds. Assume that $j$ bids any value $b_{j}\in(v_{i},b_{i})$. When $i$ bids truthfully, she does not win the good so her utility is $0$. But when $i$ bids $b_{i}$, she wins and pays a weighted average between $b_{i}$ and $\max(b_{j},b_{K}^{\max})$. As both these numbers are strictly greater than $v_{i}$, the payment is larger than $v_{i}$ as well, resulting in a negative utility. Hence, the manipulation is not safe.

• •

  $b^{\max}_{K}<v_{i}<b_{i}$: We show that (2) holds. Assume that $j$ bids any value $b_{j}<b^{\max}_{K}$. When $i$ tells the truth, she wins and pays $wv_{i}+(1-w)b^{\max}_{K}$; but when $i$ bids $b_{i}$, she still wins but pays a higher price, $wb_{i}+(1-w)b^{\max}_{K}$, so her utility decreases. Hence, the manipulation is not safe.

• •

  $b_{i}<b^{\max}_{K}<v_{i}$: We show that (2) holds. Assume that agent $j$ bids any value $b_{j}<b_{i}$. When $i$ tells the truth, she wins and pays $wv_{i}+(1-w)b^{\max}_{K}<v_{i}$, resulting in a positive utility. But when $i$ bids $b_{i}$, she does not win and her utility is $0$. Hence, the manipulation is not safe.

• •

  $b^{\max}_{K}<b_{i}<v_{i}$: We show that (2) holds. Assume that $j$ bids any value $b_{j}\in(b_{i},v_{i})$. When $i$ tells the truth, she wins and pays $wv_{i}+(1-w)b_{j}<v_{i}$, resulting in a positive utility. But when $i$ bids $b_{i}$, she does not win and her utility is $0$. Hence, the manipulation is not safe.

• •

  $b_{i}<b^{\max}_{K}<v_{i}$ or $b^{\max}_{K}<b_{i}<v_{i}$: We show that (2) holds. Assume that $j$ bids any value $b_{j}\in(b_{i},v_{i})$. When $i$ tells the truth, she wins and pays $wv_{i}+(1-w)\max(b_{j},b^{\max}_{K})$, which is smaller than $v_{i}$ as both $b_{j}$ and $b^{\max}_{K}$ are smaller than $v_{i}$. Therefore, $i$’s utility is positive. But when $i$ bids $b_{i}$, she does not win and her utility is $0$. Hence, the manipulation is not safe.

∎

given an agent $i\in N$, we need to show an alternative bid $b_{i}\neq v_{i}$ and a combination of $(n-1)$ bids of the other agents, such that the agent strictly prefers the outcome resulting from its untruthful bid over her true valuation.

Consider any combination of bids of the other agents in which all the bids are strictly smaller than $v_{i}$. Let $b^{\max}_{-i}$ be the highest bid among the other agents. We prove that any alternative bid $b_{i}\in(b^{\max}_{-i},v_{i})$ is a safe manipulation.

When agent $i$ bids her valuation $v_{i}$, she wins the good and pays $wv_{i}+(1-w)b^{\max}_{-i}$, yielding a (positive) utility of

But when $i$ bids $b_{i}$, as $b_{i}>b^{\max}_{-i}$, she still wins the good but pays $wb_{i}+(1-w)b^{\max}_{-i}$, which is smaller as $b_{i}<v_{i}$; therefore her utility is higher. ∎

To prove the mechanism is safely manipulable, we need to show one agent that has an alternative report, such that the agent always weakly prefers the outcome that results from reporting the alternative report over reporting her true valuations, and strictly prefers it in at least one scenario.

Let $a_{1}\in N$ be an agent who has a value different than $0$ and $r_{max}$ for at least one of the goods. Let $g_{1}$ be such good – that is, $0<v_{1,1}<r_{max}$. We prove that reporting the highest possible value, $r_{max}$, for all goods is a safe manipulation. Notice that this report is indeed a manipulation as it is different than the true report in at least one place.

We need to show that for any combination of reports of the other agents, this report does not harm agent $a_{i}$, and that there exists a combination where it strictly increases her utility.

Noting that since the utilities are additive and tie-breaking is performed separately for each good, we can analyze each good independently. The following proves that for all goods, agent $a_{1}$ always weakly prefers to report truthfully. Case 4 (marked by *) proves that for the good $g_{1}$, there exists a combination of reports of the others, for which agent $a_{1}$ strictly prefers the outcome from report truthfully. Which proves that it is indeed a safe manipulation.

Let $g_{\ell}\in G$ be a good. We consider the following cases according to the value of agent $a_{1}$ for the good $g_{\ell}$, $v_{1,\ell}$; and the maximum report among the other agents for this good:

• •

  $v_{1,\ell}=r_{max}$: In this case, both the truthful and the untruthful reports are the same.

• •

  $v_{1,\ell}=0$: Agent $a_{1}$ does not care about this good, so regardless of the reports which determines whether or not agent $a_{1}$ wins the good, her utility from it is $0$.

  Thus, in this case, agent $a_{1}$ is indifferent between telling the truth and manipulating.

• •

  $0<v_{1,\ell}<r_{max}$ and the maximum report of the others is strictly smaller than $v_{1,\ell}$: Agent $a_{1}$ wins the good in both cases – when she reports her true value or bids $r_{max}$.

  Thus, in this case, agent $a_{1}$ is indifferent between telling the truth and manipulating.

• •

  (*) $0<v_{1,\ell}<r_{max}$ and the maximum report of the others is greater than $v_{i,j}$ and smaller than $r_{max}$: when agent $a_{1}$ reports her true value for the good $g_{\ell}$, then she does not win it. However, by bidding $r_{max}$, she does.

  Thus, in this case, agent $a_{1}$ strictly increases her utility by lying (as her value for this good is positive).

• •

  $0<v_{1,\ell}<r_{max}$ and the maximum report of the others equals $r_{max}$: when agent $a_{1}$ reports her true value for the good, she does not win it. However, by bidding $r_{max}$, she gets a chance to win the good. Even for risk-averse agent, a chance of winning is better than no chance.

  Thus, in this case, agent $a_{1}$ strictly increases her (expected) utility by lying.

∎

Let $a_{1}$ be an agent who values only one good and let $g_{1}$ be the only good she likes. That is, her true valuation is $v_{1,1}=V$ and $v_{1,\ell}=0$ for any $\ell\neq 1$ (any good $g_{\ell}$ different than $g_{1}$).

To prove that agent $a_{1}$ does not have a safe manipulation, we need to show that for any report for her either (1) for any reports of the other agents, agent $a_{1}$ weakly prefers the outcome from telling the truth; or (2) there exists a reports of the other agents, for which agent $a_{1}$ strictly prefers the outcome from telling the truth.

Let $(r_{1,1},\ldots,r_{1,m})$ be an alternative report for the $m$ goods. We assume that the values are already normalized. We shall now prove that the second condition holds (lying may harm the agent).

First, as the alternative report is different, we can conclude that $r_{1,1}<V$. We denote the difference by $\epsilon=V-r_{1,j}$. Next, consider the following reports of the other agents (all agents except $a_{1}$): $V-\frac{1}{2}\epsilon$ for item $g_{1}$ and $\frac{1}{2}\epsilon$ for some other good.

When agent $a_{1}$ reports her true value she wins her desired good $g_{1}$, which gives her utility $V>0$. However, when she lies, she loses good $g_{1}$ and her utility decreases to $0$ (winning goods different than $g_{1}$ does not increases her utility).

That is, lying may harm the agent. ∎

Let $a_{1}$ be an agent who values at least two good, $v_{1,1},\ldots,v_{1,m}$ her true values for the $m$ goods, and $r_{1,1},\ldots,r_{1,m}$ a manipulation for $a_{1}$. We need to show that the manipulation is either not safe – there exists a combination of the other agents’ reports for which agent $a_{1}$ strictly prefers the outcome from telling the truth; or not profitable – for any combination of reports of the other agents, agent $a_{1}$ weakly prefers the outcome from telling the truth. We will show that the manipulation is not safe by providing an explicit combination of other agents’ reports.

First, notice that since the the true values and untruthful report of agent $a_{1}$ are different and they sum to the same constant $V$, there must be a good $g_{\mathrm{inc}}$ whose value was increased (i.e., $v_{1,\mathrm{inc}}<r_{1,\mathrm{inc}}$), and a good $g_{\mathrm{dec}}$ whose value was decreased (i.e., $v_{1,\mathrm{dec}}>r_{1,\mathrm{dec}}$).

Next, let $\epsilon:=\min\left\{\frac{1}{m-1}r_{1,\mathrm{inc}},~{}\frac{1}{2}(v_{1,\mathrm{dec}}-r_{1,\mathrm{dec}})\right\}$, notice that $\epsilon>0$. Also, let $c:=r_{1,\mathrm{inc}}-\epsilon$, notice that $c>0$ as well (here we use the condition $m\geq 3$).

We consider the combination of reports in which all agents except $a_{1}$ report the following values, denoted by $r(1),\ldots,r(m)$:

• •

  For good $g_{\mathrm{inc}}$ they report $r(\mathrm{inc}):=0$.

• •

  For good $g_{\mathrm{dec}}$ they report $r(\mathrm{dec}):=r_{1,\mathrm{dec}}+\epsilon$.

• •

  For the rest of the goods, $g_{\ell}\in G\setminus\{g_{\mathrm{inc}},g_{\mathrm{dec}}\}$, they report $r(\ell):=r_{1,\ell}+\frac{1}{m-2}c$.

We prove that the above values constitute a legal report — they are non-negative and normalized to $V$.

First, we show that the sum of values in this report is $V$:

Second, we show that all the values are non-negative:

• •

  Good $g_{\mathrm{inc}}$: it is clear as $r(\mathrm{inc})=0$.

• •

  Good $g_{\mathrm{dec}}$: since $r(\mathrm{dec})$ is strictly higher than the (non-negative) report of agent $a_{1}$ by $\epsilon>0$, it is clearly non-negative.

• •

  Rest of the goods, $g_{\ell}\in G\setminus\{g_{\mathrm{inc}},g_{\mathrm{dec}}\}$: since $\epsilon=\min\{\frac{1}{m-1}r_{1,\mathrm{inc}},~{}\frac{1}{2}(v_{1,\mathrm{dec}}-r_{1,\mathrm{dec}})\}$, it is clear that $\epsilon\leq\frac{1}{m-1}r_{1,\mathrm{inc}}$. As $m\geq 3$ and $r_{1,\mathrm{inc}}>0$, we get that $c=r_{1,\mathrm{inc}}-\epsilon=\frac{m-2}{m-1}r_{1,\mathrm{inc}}$ is higher than $0$. As $r(\ell)$ is strictly higher than the (non-negative) report of agent $a_{1}$ by $c>0$, it is clearly non-negative.

Now, we prove that, given these reports for the $n-1$ unknown agents, agent $a_{1}$ strictly prefers the outcome from reporting truthfully to the outcome from manipulating.

We look at the two possible outcomes for each good – the one from telling and truth and the other from lying, and show that the outcome of telling the truth is always either the same or better, and that for at least one of the goods that agent $a_{1}$ wants (specifically, $g_{\mathrm{dec}}$) it is strictly better.

• •

  For good $g_{\mathrm{inc}}$ we consider two cases.

  1. (1)

     If $v_{1,\mathrm{inc}}=0$: when agent $a_{1}$ is truthful we have a tie for this good as $r(\mathrm{inc})=0$. When agent $a_{1}$ manipulates, she wins the good (as $r_{1,\mathrm{inc}}>v_{1,\mathrm{inc}}=0=r(\mathrm{inc})$). However, as $v_{1,\mathrm{inc}}=0$, in both cases, her utility from this good is $0$.

  2. (2)

     If $v_{1,\mathrm{inc}}>0$: Whether agent $a_{1}$ says is truthful or not, she wins the good as $r_{1,\mathrm{inc}}>v_{1,\mathrm{inc}}>0=r(\mathrm{inc})$. Thus, for this good, the agent receives the same utility (of $v_{1,\mathrm{inc}}$) when telling the truth or lying.

• •

  For good $g_{\mathrm{dec}}$: when agent $a_{1}$ is truthful, she wins the good since $r(\mathrm{dec})<v_{1,\mathrm{dec}}$:

  	$\displaystyle r(\mathrm{dec})$	$\displaystyle=r_{1,\mathrm{dec}}+\epsilon$
  		$\displaystyle=r_{1,\mathrm{dec}}+\min\{\frac{1}{m-1}r_{1,\mathrm{inc}},~{}\frac{1}{2}(v_{1,\mathrm{dec}}-r_{1,\mathrm{dec}})\}$
  		$\displaystyle\leq r_{1,\mathrm{dec}}+\frac{1}{2}(v_{1,\mathrm{dec}}-r_{1,\mathrm{dec}})$
  		$\displaystyle=\frac{1}{2}(v_{1,\mathrm{dec}}+r_{1,\mathrm{dec}})<\frac{1}{2}(v_{1,\mathrm{dec}}+v_{1,\mathrm{dec}})=v_{1,\mathrm{dec}}$	(as $r_{1,\mathrm{dec}}<v_{1,\mathrm{dec}}$)

  But when agent $a_{1}$ manipulates, she loses the good since $r(\mathrm{dec})>r_{1,\mathrm{dec}}$ (as $r(\mathrm{dec})=r_{1,\mathrm{dec}}+\epsilon$ and $\epsilon>0$).

  As the real value of agent $a_{1}$ for this good is positive, the agent strictly prefers telling the truth for this good.

• •

  Rest of the goods, $g_{\ell}\in G\setminus\{g_{\mathrm{inc}},g_{\mathrm{dec}}\}$: When agent $a_{1}$ is truthful, all the outcomes are possible – the agent either wins or loses or that there is a tie.

  However, as for this set of goods the reports of the other agents are $r(\ell)=r_{1,q}+\frac{1}{n-2}c>r_{1,\ell}$, when agent $a_{1}$ manipulates, she always loses the good. Thus, her utility from lying is either the same or smaller (since losing the good is the worst outcome).

Thus, the manipulation may harm the agent. ∎

Let $a_{1}$ be an agent and let $v_{1,1},\ldots,v_{1,m}$ be her values for the $m$ goods. We need to show (1) an alternative report for agent $a_{1}$, (2) another agent $a_{2}$, and (3) a report agent  $a_{2}$; such that for any combination of reports of the remaining $n-2$ (unknown) agents, agent $a_{1}$ weakly prefers the outcome from lying, and that there exists a combination for which agent $a_{1}$ strictly prefers the outcome from lying.

Let $g_{\ell^{+}}$ be a good that agent $a_{1}$ values (i.e., $v_{1,\ell^{+}}>0$).

Let $a_{2}$ be an agent different than $a_{1}$. We consider the following report for agent $a_{2}$: first, $r_{2,\ell^{+}}:=0$, and $r_{2,\ell}:=r_{1,\ell}+\epsilon$ for any good $g_{\ell}$ different than $g_{\ell^{+}}$, where $\epsilon:=\frac{1}{m-1}v_{1,\ell^{+}}$. Notice that $\epsilon>0$.

We shall now prove that reporting $V$ for the good $g_{\ell^{+}}$ (and $0$ for the rest of the goods) is a safe manipulation for $a_{1}$ given that $a_{2}$ reports the described above.

When agent $a_{1}$ reports her true values, then she does not win the goods different than $g_{\ell^{+}}$ – this is true regardless of the reports of the remaining $n-2$ agents, as agent $a_{2}$ reports a higher value $r_{1,\ell}<r_{1,\ell}+\epsilon=r_{2,\ell}$. For the good $g_{\ell^{+}}$, we only know that $r_{2,\ell^{+}}=0>v_{1,\ell^{+}}>r_{1,\ell^{+}}=V$, meaning that it depends on the reports of the $(n-2)$ remaining agents. We consider the following cases, according to the maximum report for $g_{\ell^{+}}$ among the remaining agents:

• •

  If the maximum is smaller than $v_{1,\ell^{+}}$: agent $a_{1}$ wins the good $v_{1,\ell^{+}}$ in both cases (when telling the truth or lies).

  (the same)

• •

  If the maximum is greater than $v_{1,\ell^{+}}$ but smaller than $r_{1,\ell^{+}}=V$: when agent $a_{1}$ tells the truth, she does not win the good. However, when she lies, she does.

  (lying is strictly better).

• •

  If the maximum equals $r_{1,\ell^{+}}=V$: when agent $a_{1}$ tells the truth, she does not win the good. However, when she lies, we have tie for this good. Although agent $a_{1}$ is risk-averse, having a chance to win the good is strictly better than no chance at all.

  (lying is strictly better).

∎

Let $\pi$ be the order according to agents’ indices: $a_{1},a_{2},\ldots,a_{n}$. Let agent $a_{1}$’s valuation be such that $v_{1,1}=v_{1,2}=1$ and $v_{1,3}=\cdots=v_{1,m}=0$. Suppose agent $a_{1}$ knows that agent $a_{2}$ will report the valuation with $v_{2,1}=0$, $v_{2,2}=1$, and $v_{2,3}=\cdots=v_{2,m}=0.5$. We show that agent $a_{1}$ has a safe and profitable manipulation by reporting $v_{1,1}^{\prime}=0.5$, $v_{1,2}^{\prime}=1$, and $v_{1,3}^{\prime}=\cdots=v_{1,m}^{\prime}=0$.

Firstly, we note that agent $a_{1}$’s utility is always $1$ when reporting her valuation truthfully, regardless of the valuations of agents $a_{3},\ldots,a_{n}$. This is because agent $a_{1}$ will receive item $g_{1}$ (by the item-index tie-breaking rule) and agent $a_{2}$ will receive item $g_{2}$ in the first two rounds. The allocation of the remaining items does not affect agent $a_{1}$’s utility.

Secondly, after misreporting, agent $a_{1}$ will receive item $g_{2}$ in the first round, which already secures agent $a_{1}$ a utility of at least $1$. Therefore, agent $a_{1}$’s manipulation is safe.

Lastly, if the remaining $n-2$ agents report the same valuations as agent $a_{2}$ does, it is easy to verify that agent $a_{1}$ will receive item $g_{1}$ in the $(n+1)$-th round. In this case, agent $a_{1}$’s utility is $2$. Thus, the manipulation is profitable. ∎

Clearly, the only agent that could have a profitable manipulation is $a_{1}$.

Order the goods by descending order of $a_{1}$’s values, and subject to that, by ascending index. W.l.o.g., assume that $v_{1,1}\geq v_{1,2}\geq\cdots\geq v_{1,m}$. If all valuations are equal ($v_{1,1}=v_{1,m}$), then $a_{1}$ always gets the same total value (two goods), so no manipulation is profitable. Therefore we assume that $v_{1,1}>v_{1,m}$.

If $a_{1}$ is truthful, he gets $g_{1}$ first, and then the last good remaining after all other agents picked a good. If, after the manipulation, $g_{1}$ still has the highest value, then $a_{1}$ still gets $g_{1}$ first, and has exactly the same bundle, so the manipulation is not profitable.

Hence, we assume that $a_{1}$ manipulates such that some other good, say $g_{t}\neq g_{1}$, becomes the most valuable good: $v^{\prime}_{1,t}\geq v^{\prime}_{1,j}$ for all goods $g_{j}$, and $v^{\prime}_{1,t}>v^{\prime}_{1,1}$. We prove that the manipulation is not safe.

Suppose the $n-1$ unknown agents all assign the lowest value to $g_{t}$, and the next-lowest value to $v_{m}$. If $a_{1}$ is truthful, he gets $g_{1}$ and then $g_{t}$, so his value is $v_{1,1}+v_{1,t}$. But if $a_{1}$ manipulates, he gets $g_{t}$ and then $g_{m}$, so his value is $v_{1,m}+v_{1,t}$, which is strictly lower. ∎