Since $𝐱$ is $\epsilon$ - $\mathrm{pEF1}$ with respect to the price vector $𝐩$ , for any pair of buyers $i,k\in [n]$ , there exists a good $j\in {𝐱}_k$ such that $(1+\epsilon )𝐩({𝐱}_i)\ge 𝐩\left({𝐱}_k\setminus \{j\}\right)$ . Multiplying both sides by the maximum bang per buck ratio ${\alpha }_i$ of agent $i$ , we get

which is the $\epsilon$ -EF1 guarantee for the allocation $𝐱$ . ∎

Let the output of Alg be $(𝐱,𝐩)$ . The fact that $𝐱$ is fPO follows from the observation that at each step of the algorithm, the allocation of any agent is a subset of its $\mathrm{MBB}$ goods, i.e., at each time step, we have ${𝐱}_i\subseteq {\mathrm{MBB}}_i$ for each agent $i\in [n]$ . This is certainly true at the end of Phase 1 by way of setting the prices. In Phase 2, each swap operation only happens along an alternating $\mathrm{MBB}$ -allocation edge, which maintains the $\mathrm{MBB}$ condition. Phase 3 involves raising the prices of the goods owned by the members of the hierarchy ${\mathscr{H}}_i$ without changing the allocation. We will argue that for each agent $k\in [n]$ , if ${𝐱}_k\subseteq {\mathrm{MBB}}_k$ before the price-rise, then the same continues to hold after the price-rise. Indeed, for any agent $k\notin {\mathscr{H}}_i$ , we have ${𝐱}_k\cap {𝐱}_{{\mathscr{H}}_i}=\mathrm{\varnothing }$ . As a result, raising the prices of the goods in ${𝐱}_{{\mathscr{H}}_i}$ does not affect the bang per buck ratio of agent $k$ for the goods in ${𝐱}_k$ (and can only reduce its bang per buck ratio for the goods in ${𝐱}_{{\mathscr{H}}_i}$ ), thus maintaining the above condition. For any agent $k\in {\mathscr{H}}_i$ , we have ${\mathrm{MBB}}_k\subseteq {𝐱}_{{\mathscr{H}}_i}$ by construction of the hierarchy. Raising the prices of the goods in ${𝐱}_{{\mathscr{H}}_i}$ therefore corresponds to lowering the $\mathrm{MBB}$ ratios for the agents in ${\mathscr{H}}_i$ . By choice of ${\alpha }_1$ , the price-rise stops as soon as a new $\mathrm{MBB}$ -edge appears between an agent $k\in {\mathscr{H}}_i$ and a good $j\notin {𝐱}_{{\mathscr{H}}_i}$ . This ensures that the new maximum bang per buck ratio for any agent $k\in {\mathscr{H}}_i$ does not fall below its second highest bang per buck ratio prior to the price-rise, thus guaranteeing ${𝐱}_k\subseteq {\mathrm{MBB}}_k$ .

We can now define a Fisher market where each agent’s endowment equals its spending under $𝐱$ . Since $(𝐱,𝐩)$ is an equilibrium for this market, we have that $𝐱$ is fPO ( 1 ).

Next, we will argue that $𝐱$ is $3\epsilon \text{-EF1}$ . Notice that Alg terminates only if either the current outcome $(𝐱,𝐩)$ is $3\epsilon \text{-}\mathrm{pEF1}$ , or when $\alpha ={\alpha }_2$ (Line 1 ). In the first case, we get that $𝐱$ is $3\epsilon \text{-EF1}$ for the underlying fair division instance ( Lemma 1 ). Therefore, we only need to analyze the second case.

Let us suppose that the termination happens at time step $t$ , and let $𝐪$ be the price vector maintained by Alg just before the price-rise step that lead to termination. After the time step $t$ , Alg terminates with the allocation $𝐱$ and price vector $𝐩$ . Since Phase 3 does not change the ownership of the goods, the allocation maintained by Alg just before termination is also $𝐱$ .

Let $i$ be the least spender at time step $t$ , and let ${\mathscr{H}}_i$ be the hierarchy of agent $i$ . Since Phase 3 only affects the prices of the goods in ${𝐱}_{{\mathscr{H}}_i}$ , we have that $𝐩({𝐱}_k)=𝐪({𝐱}_k)$ for all $k\in [n]\setminus {\mathscr{H}}_i$ , and $𝐩({𝐱}_k)={\alpha }_2𝐪({𝐱}_k)$ for all $k\in {\mathscr{H}}_i$ . Additionally, at the end of (any execution of) Phase 2, no agent in the least spender’s hierarchy is an $\epsilon$ -path-violator (and hence is also not an $\epsilon$ -violator). Thus,

By definition of ${\alpha }_2$ , we have the following condition for the agents outside the hierarchy:

Sections 5.1 and 2 together imply that

which means that the outcome $(𝐱,𝐩)$ is $\epsilon$ - $\mathrm{pEF1}$ for agent $i$ . If agent $i$ is a least spender under $(𝐱,𝐩)$ (i.e., $i$ continues to a least spender after the price rise), then $𝐱$ is $\epsilon \text{-}\mathrm{pEF1}$ with respect to $𝐩$ , and the lemma follows. Otherwise, an agent $h\in \arg {\min }_{k\in [n]\setminus {\mathscr{H}}_i}𝐪({𝐱}_k)$ must become the least spender after the final price-rise step. In this case, we have that

where the last inequality follows from Equation 3 . Since , we have that . Thus, the new least spender (agent $h$ ) satisfies $(1+3\epsilon )𝐩({𝐱}_h)\ge {\min }_{j\in {𝐱}_k}𝐩({𝐱}_k\setminus \{j\})$ for all $k\in [n]$ . This implies that $(𝐱,𝐩)$ is $3\epsilon \text{-}\mathrm{pEF1}$ . The stated claim now follows from Lemma 1 . ∎

If $𝐱$ is $\delta \text{-EF1}$ , we have that for every pair of agents $i,k\in [n]$ , there exists a good $j\in {𝐱}_k$ such that $(1+\delta )v_i({𝐱}_i)\ge v_i({𝐱}_k\setminus \{j\})$ . The bound on $\delta$ implies that $v_i({𝐱}_k\setminus \{j\})-v_i({𝐱}_i)\le \frac{1}{2}$ . Integrality of valuations gives $v_i({𝐱}_k\setminus \{j\})-v_i({𝐱}_i)\le 0$ , as desired. ∎

Let $𝐱$ be the allocation returned by Alg . From Lemma 2 , we know that $𝐱$ is $3\epsilon$ - EF1 and fPO for the $\epsilon$ -rounded instance ${ℐ}^{\prime }$ . By an argument similar to the one in the proof of Theorem 1 , this implies that $𝐱$ is $7\epsilon$ - EF1 for the original instance $ℐ$ . The running time guarantee follows from Lemma 3 . Hence, we only need to show that $𝐱$ is $\epsilon$ - PO .

Suppose, for contradiction, that $𝐱$ is $\epsilon$ -Pareto dominated by an allocation $𝐲$ . Thus, $v_k({𝐲}_k)\ge (1+\epsilon )v_k({𝐱}_k)$ for every agent $k\in [n]$ and $v_i({𝐲}_i)>(1+\epsilon )v_i({𝐱}_i)$ for some agent $i\in [n]$ . By construction of the $\epsilon$ -rounded instance ${ℐ}^{\prime }$ , we know that $v_{k,j}\le v_{k,j}^{\prime }\le (1+\epsilon )v_{k,j}$ for each agent $k$ and each good $j$ . Using the inequality $v_{k,j}^{\prime }\le (1+\epsilon )v_{k,j}$ in a good-by-good manner for the bundle ${𝐱}_k$ , along with the additivity assumption of valuations in the instance $ℐ$ , we get that $(1+\epsilon )v_k({𝐱}_k)\ge v_k^{\prime }({𝐱}_k)$ . By a similar application of the inequality $v_{k,j}\le v_{k,j}^{\prime }$ for the bundle ${𝐲}_k$ , we get $v_k^{\prime }({𝐲}_k)\ge v_k({𝐲}_k)$ . Combining these relations gives $v_k^{\prime }({𝐲}_k)\ge v_k^{\prime }({𝐱}_k)$ for every agent $k\in [n]$ and $v_i^{\prime }({𝐲}_i)>v_i^{\prime }({𝐱}_i)$ for some agent $i\in [n]$ . However, this means that the allocation $𝐲$ Pareto dominates the allocation $𝐱$ in the instance ${ℐ}^{\prime }$ , which is a contradiction since $𝐱$ is fPO for ${ℐ}^{\prime }$ . ∎

There are exactly three ways in which the spending of the least spender can change between consecutive time steps: (1) due to a swap operation in Phase 2, (2) a price-rise in Phase 3, or (3) an identity change. In Phase 2, the spending of the least spender can be affected via a swap operation only if it receives a good, which results in an increase in its spending. In that case, the agent losing the good cannot become the new least spender due to the $\epsilon$ -path-violator condition. Similarly, in Phase 3, the spending of the least spender cannot decrease since the prices of the goods can only increase. Finally, any identity change, either in Phase 2 or in Phase 3, occurs only when the spending of the old least spender grows beyond that of the new one, once again implying the stated condition. ∎

Observe that a change in the identity of the least spender during Phase 2 is always preceded by the previous least spender receiving a good via a swap operation. This means that agent $i$ must receive a good at time $t$ . If, in addition, agent $i$ does not lose any good during the time interval between $t$ and $t^{\prime }$ , then we already have that ${𝐱}_i⊊{𝐱}_i^{\prime }$ and the claim follows. Therefore, for the rest of the proof, we will assume that agent $i$ loses one or more goods between $t$ and $t^{\prime }$ .

Among all time steps between $t$ and $t^{\prime }$ at which agent $i$ loses a good, let $\bar{t}$ denote the last one. Let $j\in [m]$ denote the good lost by agent $i$ at time $\bar{t}$ , and let $k$ denote the least spender at that time. Also, let $(\overline{𝐱},\overline{𝐩})$ denote the allocation and price vector just before $i$ loses the good $j$ .

Lemma 9 that the spending of the least spender cannot decrease with time. Thus,

Since agent $i$ loses the good $j$ at time $\bar{t}$ , it must be an $\epsilon$ -path-violator with respect to $(\overline{𝐱},\overline{𝐩})$ . Hence,

Finally, since $j$ is the last good lost by $i$ before the time step $t^{\prime }$ , we have that

Equations 4 , 5 and 6 together give us the desired result. ∎

Recall from Lemma 12 that each time Alg cycles back to an agent $i$ as the least spender, either the allocation of $i$ strictly grows by at least one good, or its spending grows at least by a multiplicative factor of $(1+\epsilon )$ . By pigeonhole principle, for every $(n+1)$ identity change events, Alg must cycle back to some (fixed) agent. Therefore, for every $(n+1)$ consecutive identity change events (possibly interspersed with swap operations), either that agent obtains an extra good (without losing any) or its spending grows by a factor of $(1+\epsilon )$ . This observation, along with the fact that the spending of the least spender can never decrease with time ( Lemma 9 ), implies that for every $m(n+1)$ identity changes, the spending of the least spender must increase by a factor of $(1+\epsilon )$ . Furthermore, we know from Lemma 10 that the spending of the least spender at the beginning of each Phase 3 step is at most $m{v}_{\max }$ . Hence, assuming that the initial spending of the least spender is at least $1$ (refer to Section 7.1 for explanation of why this assumption is without loss of generality), there can be at most $\mathrm{poly}(m,n)\cdot {\log }_{(1+\epsilon )}m{v}_{\max }$ identity changes during Phase 2 before a Phase 3 step occurs. By using $\ln (1+\epsilon )\ge \epsilon -{\epsilon }^2$ , we obtain the desired result. ∎

It suffices to prove Lemma 14 for consecutive price-rise steps $t$ and $t^{\prime }$ (possibly including Phase 2 events between them). Suppose, for contradiction, that there exists an agent $k\in E_{t^{\prime }}\setminus E_t$ . Our proof consists of two main arguments: First, we will show that $k$ cannot turn into a $3\epsilon$ -violator due to the price-rise at time $t$ . (This would imply that the only way $k$ can turn into a $3\epsilon$ -violator is via a swap operation.) Second, we will show that if there is a swap operation at time $\bar{t}$ (for some ) that turns $k$ into a $3\epsilon$ -violator, then there is a subsequent swap operation at $(\bar{t}+1)$ that turns it back into a non- $\epsilon$ -violator. This will contradict the fact that $k$ is a $3\epsilon$ -violator at the beginning of the price-rise step at $t^{\prime }$ .

We will start by showing that $k$ cannot turn into a $3\epsilon$ -violator due to the price-rise at time $t$ . We perform case analysis for whether or not $k\in {\mathscr{H}}_{i_t}$ . To begin with, suppose that $k\in {\mathscr{H}}_{i_t}$ . Then, $k$ cannot be an $\epsilon$ -violator before the price-rise at time $t$ (otherwise it would also be an $\epsilon$ -path-violator, and Alg would continue with Phase 2). Thus,

A similar condition continues to hold after the price-rise, since prices are always raised uniformly.

Therefore, at time $(t+1)$ , agent $k$ cannot be an $\epsilon$ -violator with respect to any agent in ${\mathscr{H}}_{i_t}$ . It is, however, possible that $k$ is an $\epsilon$ -violator at time $(t+1)$ with respect to some agent outside ${\mathscr{H}}_{i_t}$ . Nevertheless, we will show that $k$ cannot be a $3\epsilon$ -violator. Specifically, let $h$ be the least spender outside ${\mathscr{H}}_{i_t}$ at time $t$ , i.e., $h\in \arg {\min }_{a\in [n]\setminus {\mathscr{H}}_{i_t}}{𝐩}^t({𝐱}_a^t)$ . Recall that the condition $\alpha \le {\alpha }_3$ in Line 1 of Alg implies that

Along with Equation 7 , this gives

Since , we have that , which implies that $k$ is not a $3\epsilon$ -violator at time $(t+1)$ with respect to any agent.

Now suppose that $k\notin {\mathscr{H}}_{i_t}$ . Since $k\notin E_t$ by assumption, and the spending of the agents outside the hierarchy remains unaffected due to the price-rise, we once again get that $k\notin E_{t+1}$ . This proves that $k$ cannot turn into a $3\epsilon$ -violator due to the price-rise at time $t$ .

We will now proceed to show that if there is a swap operation at time $\bar{t}$ (for some ) that turns $k$ into a $3\epsilon$ -violator, then there is a subsequent swap operation at $(\bar{t}+1)$ that turns it back into a non- $\epsilon$ -violator. Suppose that $k$ (at level $\mathrm{\ell }$ in the hierarchy) becomes a $3\epsilon$ -violator after receiving a good $j$ via a swap at time step $\bar{t}$ . Recall that a swap operation involves transferring a good from an agent at a higher level to another agent at a lower level in the hierarchy. Furthermore, Alg performs a swap for an agent at level $(\mathrm{\ell }+1)$ only if no agent in the levels $1,2,\mathrm{\dots },\mathrm{\ell }$ is an $\epsilon$ -path violator. Therefore, $k$ cannot be an $\epsilon$ -path violator before the swap, i.e., there exists a good $j^{\prime }$ on an alternating path of length $2\mathrm{\ell }$ from $i_{\bar{t}}$ to $k$ such that

Moreover, since $k$ becomes a $3\epsilon$ -violator (and hence, an $\epsilon$ -path violator) after receiving the good $j$ , we have that

Since neither the identity (or allocation) of the least spender nor the price-vector changes in this process, Equation 8 can be rewritten as

Notice that the swap involving the good $j$ does not affect the alternating path from $i_{\bar{t}}$ to $k$ via the good $j^{\prime }$ , and therefore $k$ continues to be at level $\mathrm{\ell }$ . In fact, $k$ is the only agent on level $\mathrm{\ell }$ or below that is an $\epsilon$ -path-violator. Therefore, in a subsequent swap operation, the good $j^{\prime }$ will be taken away from $k$ , resulting in the allocation $({𝐱}_k^{\bar{t}}\cup \{j\}\setminus \{j^{\prime }\})$ for $k$ . After this step, agent $k$ once again becomes a non- $\epsilon$ -violator with respect to the good $j$ , providing the desired contradiction. ∎

(Sketch) The proof is very similar to that of Lemma 14 . Suppose, for contradiction, that there exists a good $j\in {𝐱}_k^{t^{\prime }}\setminus {𝐱}_k^t$ for some agent $k\in E_{t^{\prime }}$ . Then, agent $k$ must have acquired the good $j$ via a swap operation at time $\bar{t}$ (between $t$ and $t^{\prime }$ ). This means that agent $k$ cannot be an $\epsilon$ -path violator at time $\bar{t}$ , and thus cannot be a $3\epsilon$ -violator. By an argument similar to Lemma 14 , we can argue that $k$ cannot be a $3\epsilon$ -violator at any subsequent price-rise event, contradicting $k\in E_{t^{\prime }}$ . ∎

Suppose, for contradiction, that there exists an agent $k\in E_t\cap {\mathscr{H}}_{i_t}$ . Since $k\in E_t$ , we have for every good $j\in {𝐱}_k^t$ . Furthermore, since $k\in {\mathscr{H}}_{i_t}$ , there must exist an alternating path from the least spender $i_t$ to $k$ that involves some good $j^{\prime }\in {𝐱}_k^t$ . Thus, $k$ is also an $\epsilon$ -path violator, which means that Alg will perform a swap operation in Phase 2 at time $t$ , as opposed to a price-rise operation. ∎

Assume, without loss of generality, that $t$ and $t^{\prime }$ correspond to consecutive price-rise steps (possibly including Phase 2 events between them). From Lemma 15 , we have that ${𝐱}_k^{t^{\prime }}\subseteq {𝐱}_k^t$ . Therefore, it suffices to show that ${𝐩}^{t^{\prime }}({𝐱}_k^{t^{\prime }})={𝐩}^t({𝐱}_k^{t^{\prime }})$ , i.e., the prices of the goods in the set ${𝐱}_k^{t^{\prime }}$ do not vary between $t$ and $t^{\prime }$ . We know from Lemma 14 that $E_t\supseteq E_{t^{\prime }}$ , and hence $k\in E_t$ . Lemma 16 then implies that $k\notin {\mathscr{H}}_{i_t}$ , which means that the price-rise step at time $t$ does not affect the prices of the goods owned by $k$ at time $t$ , namely ${𝐱}_k^t$ . Since ${𝐱}_k^{t^{\prime }}\subseteq {𝐱}_k^t$ , the same holds for the goods in ${𝐱}_k^{t^{\prime }}$ . The lemma now follows since, by assumption, there is no other price-rise step between $t$ and $t^{\prime }$ . ∎

Let $\{t_1,t_2,\mathrm{\dots },t_{\mathrm{\ell }}\}$ denote the set of all time steps (during the execution of Alg ) at which the price of good $j$ increases, and let $\{{\alpha }_{t_1},{\alpha }_{t_2},\mathrm{\dots },{\alpha }_{t_{\mathrm{\ell }}}\}$ denote the corresponding set of multiplicative price jumps. The set of least spenders at these time steps is given by $\{i_{t_1},i_{t_2},\mathrm{\dots },i_{t_{\mathrm{\ell }}}\}$ . Let $s(t)≔{𝐩}^t({𝐱}_{i_t}^t)$ denote the spending of the least spender at time step $t$ . ^{11 11} 11 Recall from Section 5.1 that spending ‘at time step $t$ ’ refers to the spending before the event at time step $t$ takes place. Our proof relies on the following two claims:

1. Claim 1:

   $s(t_2)\ge {\alpha }_{t_1}s(t_1)$ , $s(t_3)\ge {\alpha }_{t_2}s(t_2)$ , $\mathrm{\dots }$ , $s(t_{\mathrm{\ell }})\ge {\alpha }_{t_{\mathrm{\ell }-1}}s(t_{\mathrm{\ell }-1})$ , and

2. Claim 2:

   ${\alpha }_{t_{\mathrm{\ell }}}\le m{v}_{\max }$ .

Claim 1 shows that the spending of the least spender (say, $s(t_{i+1})$ ) before a price-rise involving the good $j$ is at least that of the previous least spender (i.e., the agent that was the least spender for the previous price-rise involving the good $j$ ) after the corresponding price-rise (i.e., ${\alpha }_{t_i}s(t_i)$ ). ^{12 12} 12 Recall that in a price-rise step involving good $j$ , the spending of the least spender grows by the same multiplicative factor as the price of good $j$ . Claim 2 provides a bound on the final price-rise involving the good $j$ . Before proving these claims, we will describe how they lead to the desired relation $p_j\le m^2{v}_{\max }^3$ .

First, observe that Claim 1 implies that $s(t_{\mathrm{\ell }})\ge {\alpha }_{t_1}{\alpha }_{t_2}\mathrm{\dots }{\alpha }_{t_{\mathrm{\ell }-1}}s(t_1)$ . Using Lemma 10 for the time step $t_{\mathrm{\ell }}$ , we have that $s(t_{\mathrm{\ell }})\le m{v}_{\max }$ . This implies that ${\alpha }_{t_1}{\alpha }_{t_2}\mathrm{\dots }{\alpha }_{t_{\mathrm{\ell }-1}}\le m{v}_{\max }$ , since the initial spending of each agent (i.e., spending at the end of Phase 1) is assumed to be at least $1$ ( Section 7.1 ), and the spending of the least spender cannot decrease with time ( Lemma 9 ). Along with Claim 2, this gives ${\alpha }_{t_1}{\alpha }_{t_2}\mathrm{\dots }{\alpha }_{t_{\mathrm{\ell }-1}}{\alpha }_{t_{\mathrm{\ell }}}\le m^2{v}_{\max }^2$ . The final price of good $j$ is given by $p_j=p_j^0{\alpha }_{t_1}{\alpha }_{t_2}\mathrm{\dots }{\alpha }_{t_{\mathrm{\ell }-1}}{\alpha }_{t_{\mathrm{\ell }}}$ , where $p_j^0$ denotes the price of good $j$ at the end of Phase 1. The desired bound on $p_j$ follows by observing that the initial price of any good is at most $v_{\max }$ .

We will first prove Claim 2. Recall that the price-rise factor $\alpha$ in Alg is chosen as $\alpha =\min \{{\alpha }_1,{\alpha }_2,{\alpha }_3\}$ ; thus, in particular, $\alpha \le {\alpha }_2$ . Therefore, in order to prove a bound on ${\alpha }_{\mathrm{\ell }}$ , we can assume without loss of generality that $\alpha ={\alpha }_2$ . Under this assumption, the price-rise step in this case involves raising the spending of the least spender $i_t$ until the allocation becomes $3\epsilon$ - $\mathrm{pEF1}$ (or equivalently, until the set $E_t$ of the $\epsilon$ -violators at time step $t$ becomes empty). Using arguments similar to those in the proof of Lemma 10 , we can show that spending of the highest spender in $E_t$ can be at most its initial spending (i.e., spending at the end of Phase 1), hence at most $m{v}_{\max }$ . Thus, the price-rise factor ${\alpha }_{\mathrm{\ell }}$ is also at most $m{v}_{\max }$ . This proves Claim 2.

We will now prove Claim 1 for the time-steps $t_1$ and $t_2$ (that is, we will show that $s(t_2)\ge {\alpha }_{t_1}s(t_1)$ ); the analysis for other time-steps follows analogously. Note that if the identity of the least-spender does not change after a price-rise at $t_1$ , then we have that $s(t_1+1)={\alpha }_{t_1}s(t_1)$ . Additionally, since the spending of the least spender is non-decreasing with time ( Lemma 9 ), we have that $s(t_2)\ge s(t_1+1)={\alpha }_{t_1}s(t_1)$ , and the claim follows. Therefore, we will assume, without loss of generality, that the identity of the least-spender necessarily changes after the price-rise at $t_1$ .

For ease of presentation, we will use $[t_a,t_b]≔\{t_a,t_a+1,\mathrm{\dots },t_b-1,t_b\}$ and $[t_a,t_b)≔\{t_a,t_a+1,\mathrm{\dots },t_b-1\}$ to denote the set of all time-steps (both Phase 2 and Phase 3) between $t_a$ and $t_b$ including and excluding $t_b$ respectively. ^{13 13} 13 Here, $t_a$ and $t_b$ are any two time-steps and do not necessarily correspond to price-rise steps involving good $j$ . In addition, we will say that an agent $k\in [n]$ experiences price-rise at time $t$ if $k$ belongs to the hierarchy during the price-rise at time-step $t$ , i.e., $k\in {\mathscr{H}}_{i_t}$ . Similarly, we will say that agent $k$ experiences price-rise during $[t_a,t_b]$ (respectively, $[t_a,t_b)$ ) if $k$ experiences price-rise for some $t\in [t_a,t_b]$ (respectively, $t\in [t_a,t_b)$ ).

Let $\tau \in [t_1,t_2]$ be a time-step (either Phase 2 or Phase 3) such that

1. 1.

   the least-spender at $\tau$ , namely $i_{\tau }$ , experiences price-rise during $[t_1,\tau )$ , and

2. 2.

   there does not exist $\hat{\tau }\in [t_1,t_2]$ with such that the least-spender at $\hat{\tau }$ , namely $i_{\hat{\tau }}$ , experiences price-rise during $[t_1,\hat{\tau })$ .

Among all the time-steps in $[t_1,\tau )$ at which the agent $i_{\tau }$ (as defined above) experiences price-rise, let ${\tau }^{\prime }$ be the last one. Our proof relies on the following three observations:

1. Fact I:

   There exists $\tau \in [t_1,t_2]$ that satisfies condition (1).

2. Fact II:

   The spending of $i_{\tau }$ at time-step ${\tau }^{\prime }+1$ is at least ${\alpha }_{t_1}s(t_1)$ , i.e., ${𝐩}^{{\tau }^{\prime }+1}({𝐱}_{i_{\tau }}^{{\tau }^{\prime }+1})\ge {\alpha }_{t_1}s(t_1)$ .

3. Fact III:

   The spending of $i_{\tau }$ at $\tau$ is at least that at ${\tau }^{\prime }+1$ , i.e., ${𝐩}^{\tau }({𝐱}_{i_{\tau }}^{\tau })\ge {𝐩}^{{\tau }^{\prime }+1}({𝐱}_{i_{\tau }}^{{\tau }^{\prime }+1})$ .

Fact I makes the above formulation well-defined, whereas Facts II and III give us the desired implication via the following chain of inequalities:

The first inequality holds because the spending of the least spender is non-decreasing with time ( Lemma 9 ), the equality denotes change of notation, and the final two inequalities follow from Facts II and III. The remainder of the proof consists of proving Facts I-III.

Suppose, for contradiction, that the allocation $𝐱$ is Pareto dominated by another integral allocation $𝐲$ in the instance $ℐ$ . That is, $v_k({𝐲}_k)\ge v_k({𝐱}_k)$ for each agent $k\in [n]$ and $v_i({𝐲}_i)>v_i({𝐱}_i)$ for some agent $i\in [n]$ . Integrality of valuations in $ℐ$ implies that $v_i({𝐲}_i)\ge v_i({𝐱}_i)+1$ .

For any agent $k$ , let ${\alpha }_k$ and ${\alpha }_k^{\prime }$ denote maximum bang per buck ratios (with respect to the price vector $𝐩$ ) in the instances $ℐ$ and ${ℐ}^{\prime }$ respectively. Recall that for the $\epsilon$ -rounded version ${ℐ}^{\prime }$ , we have $v_{k,j}\le v_{k,j}^{\prime }\le (1+\epsilon )v_{k,j}$ for each agent $k$ and each good $j$ . Thus, ${\alpha }_k={\max }_{j\in [m]}{v}_{k,j}/p_j\le {\max }_{j\in [m]}{v}_{k,j}^{\prime }/p_j={\alpha }_k^{\prime }.$ We therefore have

or equivalently,

In other words, the allocation $𝐱$ —which is guaranteed to fPO for the instance ${ℐ}^{\prime }$ —is close to being fPO for the original instance $ℐ$ . The remainder of the proof will show that for a small enough $\epsilon$ , the allocation $𝐱$ turns out to be PO for the instance $ℐ$ .

Consider the allocation $𝐲$ . By definition of the maximum bang per buck ratio, we have that ${\alpha }_k𝐩({𝐲}_k)\ge v_k({𝐲}_k)$ for each agent $k\in [n]$ . Since $𝐲$ Pareto dominates $𝐱$ in the instance $ℐ$ , we have ${\alpha }_k𝐩({𝐲}_k)\ge v_k({𝐱}_k)$ , which, along with Equation 10 , implies that

Using a similar reasoning for the agent $i$ (and the observation that $v_i({𝐲}_i)\ge v_i({𝐱}_i)+1$ ), we get

The combined spending over all goods can be rewritten as follows:

This simplifies to

It is easy to see that ${\alpha }_i\le v_{\max }$ , since the initial price of each good is at least $1$ (by integrality of valuations), and prices cannot decrease during the execution of Alg . Furthermore, from Corollary 1 , we know that $𝐩([m])\le m^3{v}_{\max }^3$ . Combining these observations, we get that $\epsilon \ge \frac{1}{m^3{v}_{\max }^4}$ , which contradicts the choice of $\epsilon$ . ∎

Observe that once the spending of an agent becomes nonzero during the run of Alg , it can never become zero again. This is because for the spending of an agent to drop back to zero, it must lose its last good via a swap operation in Phase 2. However, such an exchange is disallowed by the $\epsilon$ -path-violator condition. Therefore, it suffices to show that the spending of each agent under Alg becomes nonzero after the first $𝒪(n^2)$ steps.

Let agent $i$ be the least spender at the end of Phase 1 of Alg . Assume, without loss of generality, that the spending of agent $i$ at the end of Phase 1 is zero (otherwise the lemma follows immediately). We will show that after $𝒪(n)$ steps, the spending of agent $i$ strictly exceeds zero. The desired running time bound of $𝒪(n^2)$ will follow from a similar argument for the other agents.

Our proof for the above claim consists of case analysis for whether or not at the end of Phase 1, there exists some agent in the hierarchy ${\mathscr{H}}_i$ that owns two or more goods. Suppose there exists an agent $k\in {\mathscr{H}}_i$ that owns two or more goods (if there are multiple such agents, tie-break in favor of agents at a lower level in ${\mathscr{H}}_i$ , and then according to a prespecified lexicographic ordering). Then, $k$ must be an $\epsilon$ -violator, and therefore also an $\epsilon$ -path-violator (along some alternating path $P$ ). Additionally, by the choice of agent $k$ , no agent at a lower level is an $\epsilon$ -path-violator. As a result, $k$ must lose a good under a swap operation in Phase 2 to its predecessor along path $P$ , who acquires two goods as a result, and becomes the new $\epsilon$ -path-violator. This series of swaps continues for $𝒪(n)$ steps, and ends with the least spender receiving a new good.

Next, suppose that each agent in ${\mathscr{H}}_i$ owns exactly one good. Since the given instance $ℐ$ satisfies Hall’s condition, and agent $i$ does not yet own any good, there must exist an agent $k\notin {\mathscr{H}}_i$ that owns two or more goods. We will show that such an agent must get added to the hierarchy in $𝒪(n)$ steps. Then, by the above argument, in further $𝒪(n)$ steps, agent $i$ must receive a good that takes its spending strictly above zero.

Since each agent in the hierarchy owns exactly one good, there are no $\epsilon$ -path-violators in ${\mathscr{H}}_i$ , and Alg proceeds directly to Phase 3. Once again, since the least spender does not own any good, its spending cannot change as a result of price-rise, and therefore a new agent gets added to the hierarchy. If this agent has more than one good, then the lemma follows. Otherwise, the price-rise step is repeated. Therefore, after $𝒪(n)$ such steps, an agent with two or more goods must get added to the hierarchy, as desired. ∎