# Incentives in Dominant Resource Fair Allocation under Dynamic Demands

Giannis Fikioris
Cornell University
<EMAIL_ADDRESS>Supported in part by NSF grants CCF-1408673 and AFOSR
grant FA9550-19-1-0183. Rachit Agarwal
Cornell University
<EMAIL_ADDRESS>Supported by NSF grants CNS-1704742 and CNS-2047283, and
a Sloan fellowship. Éva Tardos
Cornell University
<EMAIL_ADDRESS>Supported in part by NSF grants CCF-1408673,
CCF-1563714 and AFOSR grant FA9550-19-1-0183.

###### Abstract

Every computer system—from schedulers in clouds (e.g., Amazon, Google,
Microsoft, etc.) to computer networks to hypervisors to operating
systems—performs resource allocation across system users. The defacto
allocation policies used in most of these systems are max-min fairness for
single resource settings and dominant resource fairness for multiple
resources. These allocation schemes guarantee many desirable properties like
incentive compatibility, envy-freeness, and Pareto efficiency, assuming user
demands are static (time-independent). However, in modern real-world
production systems, user demands are dynamic, that is, vary over time. As a
result, there is now a fundamental mismatch between the resource allocation
goals of computer systems, and the properties enabled by classical resource
allocation policies. This paper aims to bridge this mismatch. When demands are
dynamic, instant-by-instant max-min fairness can be extremely unfair over a
longer period of time, i.e., lead to unbalanced user allocations, as previous
large allocations have no effect in the current time step. We consider a
natural generalization of the classic algorithm for max-min fair allocation
and dominant resource fairness for multiple resources when users have dynamic
demands: this algorithm guarantees Pareto optimality while ensuring that
resources allocated to users are as max-min fair as possible _up to_ any time
instant, given the allocation in previous periods. While this dynamic
allocation scheme remains Pareto optimal and envy free, unfortunately, it is
not incentive compatible. We study the strength of the incentive to misreport;
our results show that the possible increase in utility by misreporting demand
is bounded and, since this misreporting can lead to significant decrease in
overall useful allocation, this suggests that it is not a useful strategy. Our
main result is to show that our dynamic version of the dominant resource
fairness algorithm is $(1+\rho)$-incentive compatible, where $\rho$ quantifies
the relative importance of a resource for different users; we also show that
this factor is tight even with only two resources. We also present a $3/2$
upper bound and a $\sqrt{2}$ lower bound for the incentive compatibility when
there is only one resource. We also offer extensions of the results for the
case when the mechanism uses weights to prioritize every user differently. Our
results indicate a big disparity between single resource and multiple
resources even with just two resources showing a surprising difference in the
users’ incentive to deviate, with significantly less incentive to deviate in
the case of one resource, and this is especially true in the case when the
mechanism uses weights to prioritize every user differently.

##  1 Introduction

Resource allocation is a fundamental problem in computer systems. Companies
like Google [Ver+15] and Microsoft [Gra+14] use schedulers in private clouds
to allocate a limited and divisible amount of resources (e.g., CPU, memory,
servers, etc.) among a number of selfish and possibly strategic users that
want to maximize their allocation; the goal of the scheduler is to maximize
resource utilization while achieving fairness in resource allocation. The
defacto allocation policies used in many of these systems are the classic max-
min fairness (MMF) and its relatively recent generalization, dominant resource
fairness (DRF) [Gho+11] policies, for single and multiple resource settings,
respectively. For instance, these policies are used in most schedulers in
private clouds [Vav+13, Hin+11, Ver+15, Gra+16, Bou+14, Gho+11, SFS12, Gra+14,
Gra+16a]; they are deeply entrenched in congestion control protocols like TCP
and its variants [CJ89, Ali+10]; and are the default policies for resource
allocation in most operating systems and hypervisors [KVM16, Cha08]. DRF has
also attracted a lot of attention in the economics and computing community,
starting with [PPS12] [PPS12] and with followup work [LLL18, FPV15, FPV17,
Im+20, KPS13].

Such prevalence of MMF and DRF is rooted in the properties they guarantee:
Pareto-efficiency, sharing incentives (users are not better of by getting
their fair share of resources every round), incentive compatibility, envy-
freeness (no user envies the allocation of another user), and fairness.
However, to guarantee these properties, both MMF and DRF policies assume that
user demands do not change over time. This assumption is far from realistic in
modern real-world deployments: several recent studies in the systems community
have shown that user demands have become highly dynamic, that is, vary over
time [Vup+20, CAD18, Rei+12, YYR20]. For such dynamic user demands, naïvely
using these policies (e.g., to perform a new instantaneously max-min fair
allocation every unit of time) can result in vastly disparate user allocations
over time—intuitively, since MMF does not take past allocations into account,
dynamic user demands can result in increasingly unfair user allocations over
time.

Motivated by the realistic case of dynamic user demands over divisible
resources, we study Dynamic DRF111The name Dynamic DRF has also been used by
[KPS13] for the extension of DRF when users arrive and depart sequentially.
See more about the difference in Section 1.1., a mechanism that generalizes
DRF for dynamic demands; just like DRF generalizes MMF for multi-resource
allocations, Dynamic DRF generalizes Dynamic MMF [Fre+18] for multi-resource
allocations over dynamic demands by taking past allocations into account. Our
model is the same as the original DRF paper [Gho+11]: every round, each user
specifies a vector of ratios (the proportions according to which the different
resources are used by the user, e.g., for her application) and a demand (the
maximum allocation of resources that would be useful to her). Users have
Leontief preferences—as they are known in economics, i.e., their utility each
round is equal to the minimum over the amount of every resource they receive
divided by their ratio for it, up to their demand. However, in contrast to the
DRF paper, we consider scenarios where the ratios and the demands can vary
over time and users want to maximize the sum of their utilities across rounds.

In every round, Dynamic DRF allocates resources while being as fair as
possible given the past allocations: first the minimum total utility of any
user is maximized, then the second minimum, etc. Besides being fair, Dynamic
DRF is also Pareto-efficient by construction: every round, either every user’s
demand is satisfied or for every user a resource she wants to use is
saturated. However, similar to Dynamic MMF [Fre+18], Dynamic DRF is not
incentive compatible, i.e., it is possible that a user can misreport her
demand or her ratios on one round to increase her total useful allocation in
the future (in fact, our study leads to stronger lower bounds on incentive
compatibility of Dynamic MMF; see Theorems 3.2 and 4.7). Nevertheless,
studying Dynamic DRF is both important and interesting. First, similar to the
widely-used classic MMF and DRF (also referred to as static MMF and DRF),
Dynamic DRF is simple and easy to understand; thus, it has the potential for
real-world adoption (similar to many other non-incentive compatible mechanisms
used in practice, e.g., non-incentive compatible auctions used by U.S.
Treasury to sell treasury bills since 1929 and by the U.K to sell electricity
[Kri09, Har18, Par18]). Second, our results show that Dynamic DRF is
approximately incentive compatible, that is, strategic users can increase
their allocation by misreporting their demands but this increase is bounded by
a relatively small constant factor, independent of the number of users and the
number of resources; moreover, effective misreporting not only requires
knowledge of future demands, but can lead to a significant decrease in overall
useful allocation, suggesting that misreporting is unlikely to be a useful
strategy for any user.

Our Contribution. Our goal is to study Dynamic MMF and Dynamic DRF and the
incentive to misreport in them. A popular relaxation of incentive
compatibility is $\gamma$-incentive compatibility [Arc+03, KPS03, DFP08,
Düt+12, MS14, AB18, BSV19], which requires that the possible increase in
utility by untruthful reporting must be bounded by a factor of $\gamma\geq 1$
($\gamma$ is referred to as incentive compatibility ratio). Using this notion
we show that users have limited incentive to be untruthful:

  * •

We start the technical part of this paper in Section 3 by considering the
simpler problem of single resource environments, Dynamic MMF. We show that
users have no incentive to over-report their demand (Theorem 3.5), that
Dynamic MMF is $3/2$-incentive compatible (Theorem 3.6), and give an almost
matching lower bound of $\sqrt{2}$ (Theorem 3.2). We also show that Dynamic
MMF is envy-free (Corollary 4.9) and the variant where every user is
guaranteed an $\alpha$ fraction of her fair share of resources (for
$\alpha\in[0,1]$) satisfies $\alpha$-sharing incentives while maintaining the
incentive compatibility ratio, as well as every one of the aforementioned
properties.

  * •

Our main results are presented in Section 4, where we focus on the setting of
multiple resources. In the case that every user demands every resource when
using the system, we show that in Dynamic DRF user $i$ cannot increase her
utility more than a factor of $(1+\rho_{i})$ (Theorem 4.6) and give a matching
lower bound (Theorem 4.7) where $\rho_{i}$ is a parameter that quantifies the
relative importance of every resource between user $i$ and the other users. We
also show that in this case users have no incentive to over-report their
demand or misreport their ratios (Theorem 4.4); this guarantees that resources
allocated to the users are always in use. The assumption that every user
demands every resource when using the system, even if in different ratios, is
quite natural; in computer systems where the resources shared are CPU, memory,
storage, etc. the users run applications that use every resource. This
assumption is also used by [KPS13], where they extend DRF to the case of users
arriving and leaving sequentially resulting in dynamically changing the
allocations in the system.

Additionally, we show that Dynamic DRF is envy-free (Theorem 4.8), and the
variant where every user is guaranteed an $\alpha$ fraction of her fair share
satisfies $\alpha$-sharing incentives while retaining every one of the
aforementioned properties.

  * •

We also consider some generalizations. First, we consider the case where every
user $i$ is associated with a positive weight $w_{i}$ indicating their
priority. This extra assumption does not change our results in Section 4,
other than slightly altering the definition of $\rho_{i}$ affected by the
weights $w$—the bound of $(1+\rho_{i})$ remains tight for the new $\rho_{i}$.
We also study weighted users in single resource settings in Section 5.1, along
with the assumption that users can collude. In this case, Dynamic weighted MMF
is $2$-incentive compatible (Theorem 5.3) and demand over-reporting does not
increase utility (Theorem 5.2). The former of these results strikes a big
contrast between single and multiple resource settings: assuming that users do
not collude and directly applying our results from Dynamic DRF in Dynamic
weighted MMF proves a $1+\rho_{i}=1+\max_{k\neq i}(w_{i}/w_{k})$ upper bound
for the incentive compatibility of user $i$, which is possibly unbounded; in
contrast, we manage to prove a $2$-upper bound.

###  1.1 Related Work

The simplest algorithm for resource allocation is strict partitioning [Ver+17,
Vup+20a], that allocates a fixed amount of resources to each user independent
of their demands. While incentive compatible, strict partitioning can have
arbitrarily bad efficiency. Static MMF and DRF [Gho+11, SFS12, Gra+14,
Gra+16a, Fre+18, PPS12] are Pareto-efficient, incentive compatible, envy-free,
and satisfy sharing incentives, but fair only when user demands are static.

[Fre+18] [Fre+18] prove that Dynamic MMF is not incentive compatible under the
same utility model as ours. The papers [Fre+18, Hos19] study resource
allocation for single resource settings with dynamic demands focusing on the
case when users have utility for resources above their demand, only at a lower
rate. They offer alternate mechanisms where past allocations have some effect
on the current ones (unlike static MMF) while maintaining incentive
compatibility, but the mechanisms they consider are closer to MMF separately
in each epoch, and less aim to be fair overall. Under this model, they present
two mechanisms that are incentive compatible but either satisfy sharing
incentives and have no Pareto-efficiency guarantees, or approximately satisfy
sharing incentives and are approximately Pareto-efficient under strong
assumptions (user demands being i.i.d. random variables and number of rounds
growing large).

[SCC21] [SCC21] present minor improvements in fairness over static DRF for
dynamic demands while maintaining incentive compatibility. Their mechanism
allocates resources in an incentive compatible way according to DRF while
marginally penalizing users with larger past allocations using a parameter
$\delta\in[0,1)$. Specifically, if $t$ rounds ago a user received an
allocation of $r$, that allocation penalizes the user in the current round by
$r(1-\delta)\delta^{t}$. This means that the penalty of
$(1-\delta)\delta^{t}\leq 0.25$ reduces exponentially fast with time for any
fixed $\delta<1$ and as $\delta\to 1$ the penalty tends to $0$. Thus, for
every $\delta$ (and, especially for $\delta=0$ and $\delta\to 1$), their
mechanism suffers from similar problems as static DRF: past allocations are
barely taken into account.

Several other papers study resource allocation where user demands can be
dynamic, but with significantly different setting than ours. [AW19, ZP20]
examine the setting where indivisible items arrive over time and have to be
allocated to users whose utilities are random; however [AW19] [AW19] study a
very weak version of incentive compatibility in which a mechanism is incentive
compatible if misreporting cannot increase a user’s utility in the current
round and [ZP20] [ZP20] do not consider strategic users. [Kan+20] [Kan+20]
study single resource allocation and assume the users do not know their exact
demands every round and need to provide feedback to the mechanism after each
round of allocation to allow the mechanism to learn. The goal of the paper is
to offer a version of MMF that approximately satisfies incentive
compatibility, sharing incentives, and Pareto-efficiency, despite the lack of
information, but is not considering the long-term fairness that is the focus
of our mechanisms.

Another series of work study the setting where users arrive consecutively and
potentially leave after some period of time: [LLL18, FPV15] focus on single
resource settings, while [FPV17, Im+20, KPS13] also study the allocation of
multiple resources. Even though their setting is dynamic, users have constant
demands and cannot re-arrive after leaving, making the user demands static.
After every arrival or departure of a user, resources need to be re-
distributed while maintaining some sort of fairness, e.g., the users’
utilities need to be approximately similar. [KPS13] [KPS13] focus on never
decreasing a user’s allocation when re-distributing resources, thus creating a
mechanism that allocates at most $k/n$ fraction of every resource when $k$ out
of $n$ users are present in the system. They offer a mechanism for this
setting that they also call dynamic DRF, however, in their setting the dynamic
nature of the problem comes from churn in users, as well as the corresponding
changes in total resources, and not from dynamic demands. The papers [LLL18,
FPV15, FPV17, Im+20] consider resource allocation, but incentive compatibility
is not taken into account and the focus is to maximize fairness while bounding
the “disruptions” of the system every time a user enters or leaves, which is
how many users’ allocations are altered.

There are many reasons why mechanisms used in practice are often not incentive
compatible, including the relative simplicity of these mechanisms that makes
it easier for users to understand and use them and the fact that incentive
compatible mechanisms are not actually incentive compatible depending on the
information structure, e.g., when participants collude (see [BSV19] [BSV19]
for a nice discussion of a long list of other reasons). In most settings, even
if the mechanism is manipulable, finding a profitable manipulation is hard. In
our setting, finding such manipulation requires knowledge of all users’ future
demands, and while under-reporting demand can lead to increased future
utility, it may also lead to decreased utility. When using a manipulable
mechanism, it is important to understand how large is the incentive to
manipulate. $\gamma$-incentive compatibility has been considered in many
settings. As we mentioned before, [Kan+20] [Kan+20] study a setting similar to
ours, but where long-term fairness is not their focus and they try to learn
users’ demands; to achieve their results they propose several mechanisms most
of which are approximate incentive compatible. [Arc+03, KPS03, Düt+12, MS14]
study combinatorial auctions that are almost incentive compatible. [DFP08]
[DFP08] studies approximate incentive compatibility in machine learning, when
users are asked to label data. [AB18] [AB18] examines approximate incentive
compatibility in large markets, where the number of users grows to infinity.
[BSV19] [BSV19] develops algorithms that can estimate how incentive compatible
mechanisms for buying, matching, and voting are. [HT19] [HT19] develop
auctions that use samples from past non-incentive compatible auctions to
improve social welfare or revenue guarantees. In the same spirit, Dynamic DRF
is aimed at improving fairness.

##  2 Preliminaries

We first make some definitions that apply to all sections. We use $[n]$ to
denote the set $\\{1,2,\ldots,n\\}$ for any $n\in\mathbb{N}$. Additionally, we
define $x^{+}=\max(x,0)$ and denote with $\mathbbm{1}\left[\cdot\right]$ the
indicator function.

There are $n$ users, where $n\geq 2$. The set of users is denoted with $[n]$.
In some settings, every user $i$ is associated with a weight, $w_{i}>0$ which
indicates each user’s priority and in this case we view the allocation fair,
if user $i$ has (approximately) $w_{i}/w_{j}$ more utility than user $j$.
Additionally, we sometimes assume that user $i$ has initial endowment or fair
share a $w_{i}/\sum_{j\in[n]}w_{j}$ fraction of the total resources. The game
is divided into epochs $1,2,\ldots,t,\ldots$

A mechanism is called envy-free if for any pair of users $i$ and $j$, and if
user $i$ is truthful, she would not have gained utility if she had been
allocated the resources user $j$ was allocated. Similarly, we define weighted
envy-freeness: if every user $i$ is associated with a weight $w_{i}>0$, a
mechanism is envy-free if for any pair of users $i$ and $j$, user $i$ would
not have gained utility if she had been allocated the resources user $j$ was
allocated, scaled by $w_{i}/w_{j}$ (note that this scaling sometimes results
in comparing to usage with more resources than what is available).

A mechanism satisfies sharing incentives if every truthful user’s utility is
not less than her utility if she had been allocated her fair share every
epoch, i.e., a $\frac{1}{n}$ fraction of the total resources. For weighted
users, a mechanism satisfies sharing incentives if the utility of user $i$ is
not less than her utility if she had been allocated her fair share every
epoch, i.e., a $\nicefrac{{w_{i}}}{{\sum_{j\in[n]}w_{j}}}$ fraction of the
total resources. For $\alpha\in[0,1]$, there is also the notion of
$\alpha$-sharing incentives, in which user $i$’s utility must be at least
$\alpha$ times her utility if she had been allocated her fair share every
epoch.

##  3 Single Resource Setting

Before we present our results on the multiple resource setting in Section 4,
we first present results on the simpler setting of dynamic max-min fairness
(Dynamic MMF) where there is only one resource and users are unweighted
($w_{i}=w_{j}$ for all users $i,j$).

Notation. Every epoch there is a fixed amount of a resource shared amongst the
users. We denote the total amount of that resource with $\mathcal{R}$.

We denote with $r_{i}^{t}$ the allocation of user $i$ in epoch $t$, i.e., the
amount of resources the user receives. We also denote with $R_{i}^{t}$ the
cumulative allocation of user $i$ up to round $t$, i.e.,
$R_{i}^{t}=\sum_{\tau=1}^{t}r_{i}^{\tau}$. By definition, $R_{i}^{0}=0$.

Every epoch $t$, each user $i$ has a demand, denoted with $d_{i}^{t}$. This
represents the maximum allocation that is useful for that user in that epoch,
i.e., a user is indifferent between getting an allocation equal to her demand
and an allocation higher than her demand, so the utility of user $i$ in epoch
$t$ is $u_{i}^{t}=\min(r_{i}^{t},d_{i}^{t})$. The total utility of user $i$
after epoch $t$ equals the sum of utilities up to that round, i.e.,
$U_{i}^{t}=\sum_{\tau=1}^{t}u_{i}^{\tau}=\sum_{\tau=1}^{t}\min(r_{i}^{\tau},d_{i}^{\tau})$.

##### Dynamic Max-min Fairness

In MMF the resources are allocated such that the minimum amount of resources
is maximized, then the second minimum is maximized, etc., as long as every
user gains an amount of resources that does not exceed her demand. If for
example, we have $\mathcal{R}=1$ total resource and three users with demands
$1/4$, $3/8$, and $1$, then the first user gets $1/4$ resources and the other
two get $3/8$ resources each.

In Dynamic MMF, every epoch the MMF algorithm is applied to the users’
cumulative allocations constrained by what they have already been allocated in
previous iterations. Our mechanism will have an additional parameter
$\alpha\in[0,1]$ that guarantees a fraction of the fair share of each user
every single epoch, independent of allocations in previous epochs: we
guarantee every user at least $\alpha\mathcal{R}/n$ resources (assuming they
have big enough demand to use it). Formally, given an epoch $t$ and that every
user $i$ has cumulative allocation $R_{i}^{t-1}$, Dynamic MMF solves the
following problem

$\displaystyle\begin{split}\textrm{choose
}\;\;&r_{1}^{t},\,r_{2}^{t},\,\ldots,\,r_{n}^{t}\\\ \textrm{applying max-min
fairness on
}\;\;&R_{1}^{t-1}+r_{1}^{t},\,R_{2}^{t-1}+r_{2}^{t},\,\ldots,\,R_{n}^{t-1}+r_{n}^{t}\\\
\textrm{given the constraints
}\;\;&\sum_{i\in[n]}r_{i}^{t}\leq\mathcal{R}\;\;\;\textrm{ and }\;\;\;\forall
i\in[n],\,\min\left\\{d_{i}^{t},\alpha\frac{\mathcal{R}}{n}\right\\}\leq
r_{i}^{t}\leq d_{i}^{t}\end{split}$ (1)

We are going to call the value
$\min\left\\{d_{i}^{t},\alpha\frac{\mathcal{R}}{n}\right\\}$ the guarantee of
user $i$ in epoch $t$, and denote it with
$g(d_{i}^{t})=\min\left\\{d_{i}^{t},\alpha\frac{\mathcal{R}}{n}\right\\}$.
Note that $g(\cdot)$ is a non-decreasing function. Because of the guarantee of
every user it is easy to see that Dynamic MMF satisfies $\alpha$-sharing
incentives.

######  Theorem 3.1.

When every user is guaranteed an $\alpha$-fraction of their fair share,
Dynamic MMF satisfies $\alpha$-sharing incentives.

##### Incentives in Dynamic MMF

It is easy to see [PPS12] that applying MMF when there is a single epoch is
incentive compatible, i.e., users can never increase their utility by
misreporting their demand. In dynamic settings, however, this is not the case.
As was shown by [Fre+18], a user can increase her allocation by misreporting.
See also the improved lower bound (Theorem 3.2).

###  3.1 Bounds on Incentive Compatibility

We will now focus in how far Dynamic MMF is from incentive compatible.
W.l.o.g. we are usually going to study the possible deviations of user $1$,
i.e., how much user $1$ can increase her allocation by lying about her demand.
We use the symbols $\hat{d}_{i}^{t}$, $\hat{r}_{i}^{t}$, $\hat{R}_{i}^{t}$,
$\hat{u}_{i}^{t}$, $\hat{U}_{i}^{t}$ or $\bar{d}_{i}^{t}$, $\bar{r}_{i}^{t}$,
$\bar{R}_{i}^{t}$, $\bar{u}_{i}^{t}$, $\bar{U}_{i}^{t}$ to denote the claimed
demand and resulting outcome of some deviation of user $1$. We want to prove
that for some $\gamma\geq 1$, Dynamic MMF is always $\gamma$-incentive
compatible, i.e., for every users’ true demands
$\\{d_{i}^{t}\\}_{i\in[n],t\in\mathbb{N}}$, for every deviation of user $1$
$\\{\hat{d}_{1}^{t}\\}_{t\in\mathbb{N}}$, and for every epoch $t$, to prove
that $\hat{U}_{1}^{t}\leq\gamma U_{1}^{t}$. $\gamma$ is often referred to as
the incentive compatibility ratio.

##### Lower bound on incentive compatibility

As mentioned before, Dynamic MMF does not guarantee incentive compatibility.
This is demonstrated in the following theorem, where user $1$ can misreport
her demand to increase her utility by a factor of almost $\sqrt{2}$.

######  Theorem 3.2.

For any value of $\alpha\in[0,1]$, there is an instance with $n$ users, where
in Dynamic MMF a user can under-report her demand to increase her utility by a
factor of $\sqrt{2}$ as $n\to\infty$.

We defer the proof of the theorem to Appendix A. To provide intuition about
how a user can increase her utility by misreporting, we include here the
example of [Fre+18], where user $1$ can increase her utility by a factor of
$10/9$.

######  Example 1 ([Fre+18]).

There are 3 users, 3 epochs, and $\alpha=0$. Every epoch the available amount
of the resource is $\mathcal{R}=8$ and the real demands of the users are shown
in Table 1, as well as their allocations when user $1$ is truthful and when
she misreports.

Users |  Epoch $1$ |  Epoch $2$ |  Epoch $3$
---|---|---|---
User $1$ | $8$ | $4$ | $0$ | $8$ | $2$ | $4$ | $8$ | $3$ | $6$
User 2 | $8$ | $4$ | $8$ | $0$ | $0$ | $0$ | $8$ | $5$ | $2$
User 3 | $0$ | $0$ | $0$ | $8$ | $6$ | $4$ | $0$ | $0$ | $0$
Table 1: Every epoch there is a total of $8$ resources. The black numbers are
the users’ demands, the blue ones are the users’ allocations when user $1$ is
truthful, and the red ones are the allocations when user $1$ misreports her
demand in epoch $1$ by demanding $0$.

Because user $1$ under-reports her demand in epoch $1$, in epoch $2$ she
manages to “steal” some of user $3$’s resources. Then, in epoch $3$ the
allocation mechanism equalizes the total allocations of users $1$ and $2$,
making user $1$ get back some of the resources she lost in epoch $1$. This
results in user $1$ having a total allocation of $10$ instead of $9$, i.e.,
her utility increases by a factor of $10/9$. ∎

Both in Theorem 3.2 and Example 1, it is important to note that user $1$ can
increase her utility only by a bounded constant factor. Additionally, this is
done by user $1$ under-reporting her demand, not over-reporting; this is
important because it implies that the resources allocated are always used by
the users and hence the allocation remains Pareto optimal. As we will show
next, both of these facts are true in general.

##### Upper bound on incentive compatibility ratio

To prove the above, first we show a lemma offering a simple condition on which
pair of users can gain overall allocations from one another. When users’
demands are not satisfied, for a user to get more resources someone else needs
to get less. The lemma will allow us to reason about how a deviation by user
$1$ can lead to a user $i$ getting more resources and another user $j$ getting
less (possibly $i=1$ or $j=1$).

######  Lemma 3.3.

Fix an epoch $t$ and the total allocations up to epoch $t-1$ of any two
outcomes $\\{\hat{R}_{k}^{t-1}\\}_{k\in[n]}$ and
$\\{\bar{R}_{k}^{t-1}\\}_{k\in[n]}$. Let $i,j$ be two different users. If the
following conditions hold

  * •

For $i$, $\,\bar{r}_{i}^{t}<\hat{r}_{i}^{t}$ and
$\hat{d}_{i}^{t}\leq\bar{d}_{i}^{t}$.

  * •

For $j$, $\,\bar{r}_{j}^{t}>\hat{r}_{j}^{t}$ and
$\bar{d}_{j}^{t}\leq\hat{d}_{j}^{t}$.

then, for any value of $\alpha\in[0,1]$, in Dynamic MMF it holds that
$\bar{R}_{i}^{t}\geq\bar{R}_{j}^{t}$ and $\hat{R}_{i}^{t}\leq\hat{R}_{j}^{t}$,
implying

$\hat{R}_{i}^{t}-\bar{R}_{i}^{t}\leq\hat{R}_{j}^{t}-\bar{R}_{j}^{t}$

It should be noted that the second condition for $i$ (similarly for $j$) is
not needed when $i$ is not the user who misreports her demand, i.e., $i\neq
1$.

###### Proof.

Because of the conditions, we notice that $\bar{r}_{i}^{t}<\bar{d}_{i}^{t}$
(since $\hat{r}_{i}^{t}\leq\hat{d}_{i}^{t}$) and
$\bar{r}_{j}^{t}>g(\bar{d}_{j}^{t})$ (since
$\bar{r}_{j}^{t}>\hat{r}_{j}^{t}\geq g(\hat{d}_{j}^{t})\geq
g(\bar{d}_{j}^{t})$). These two inequalities imply that it would have been
feasible in (1) to increase $\bar{r}_{i}^{t}$ by decreasing $\bar{r}_{j}^{t}$.
This implies that $\bar{R}_{i}^{t}\geq\bar{R}_{j}^{t}$; otherwise it would
have been more fair to give some of the resources user $j$ got to user $i$.
With the analogous inverse argument (we can increase $\hat{r}_{j}^{t}$ by
decreasing $\hat{r}_{i}^{t}$) we can prove that
$\hat{R}_{i}^{t}\leq\hat{R}_{j}^{t}$. This completes the proof. ∎

The main technical tool in our work is the following lemma bounding the total
amount all the users can “win” because of user $1$ deviating, i.e.,
$\sum_{k}(\hat{R}_{k}^{t}-R_{k}^{t})^{+}$. Rather than bounding the deviating
user $1$’s gain directly, it is better to consider the overall increase of all
users. Specifically, the lemma upper bounds the increase of that amount after
any epoch, given that user $1$ does not over-report her demand (which as we
are going to show later in Theorem 3.5 users have no benefit in doing). The
bound on the total over-allocation then follows by summing over the epochs.
The bound on the increase of $\sum_{k}(\hat{R}_{k}^{t}-R_{k}^{t})^{+}$ after
any epoch is different according to two different cases:

  * •

If user $1$ is truthful, the increase is at most $0$: in these steps over-
allocation can move between users but cannot increase. This is the reason
studying the total over-allocation is so helpful.

  * •

If user $1$ under-reports, the increase is bounded by the amount of resources
she receives when she is truthful.

######  Lemma 3.4.

Fix an epoch $t$ and the total allocations of any two outcomes
$\\{\hat{R}_{k}^{t-1}\\}_{k\in[n]}$ and $\\{\bar{R}_{k}^{t-1}\\}_{k\in[n]}$.
Assume that $\\{\bar{d}_{k}^{t}\\}_{k\in[n]}$ are some user demands and that
$\\{\hat{d}_{k}^{t}\\}_{k\in[n]}$ are the same demands except user $1$’s, who
deviates but not by over-reporting, i.e.,
$\hat{d}_{1}^{t}\leq\bar{d}_{1}^{t}$. Then, for any $\alpha\in[0,1]$, it holds
that

$\sum_{k\in[n]}\left(\hat{R}_{k}^{t}-\bar{R}_{k}^{t}\right)^{+}-\sum_{k\in[n]}\left(\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1}\right)^{+}\leq\bar{r}_{1}^{t}\mathbbm{1}\left[\hat{d}_{1}^{t}<\bar{d}_{1}^{t}\right]$
(2)

We will use Lemma 3.3 to show that if user $1$ is truthful in epoch $t$, then
the l.h.s. of (2) is at most $0$: Dynamic MMF allocates resources such that
the large $\hat{R}_{k}^{t}-\bar{R}_{k}^{t}$ are decreased and the small
$\hat{R}_{k}^{t}-\bar{R}_{k}^{t}$ are increased. Finally, if user $1$ reports
a lower demand, then the (at most) $\bar{r}_{1}^{t}$ resources user $1$ does
not get might increase the total over-allocation by the same amount.

###### Proof.

First we define $P^{t}=\\{k\in[n]:\hat{R}_{k}^{t}>\bar{R}_{k}^{t}\\}$ for all
$t$. Suppose by contradiction:

$\sum_{k\in P^{t}}\left(\hat{R}_{k}^{t}-\bar{R}_{k}^{t}\right)-\sum_{k\in
P^{t-1}}\left(\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1}\right)>\bar{r}_{1}^{t}\mathbbm{1}\left[\hat{d}_{1}^{t}<\bar{d}_{1}^{t}\right]$

Because $\sum_{k\in P^{t}}(\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1})\leq\sum_{k\in
P^{t-1}}(\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1})$, the above inequality implies

$\sum_{k\in
P^{t}}\left(\hat{r}_{k}^{t}-\bar{r}_{k}^{t}\right)>\bar{r}_{1}^{t}\mathbbm{1}\left[\hat{d}_{1}^{t}<\bar{d}_{1}^{t}\right]$
(3)

Since user $1$ reports a lower demand $\hat{d}_{1}^{t}\leq\bar{d}_{1}^{t}$, it
holds that $\sum_{k}\bar{r}_{i}^{t}\geq\sum_{k}\hat{r}_{i}^{t}$, i.e., the
total resources allocated to the users do not increase when user $1$ reports a
lower demand. Combining this fact with (3) we get that

$\sum_{k\notin
P^{t}}\left(\bar{r}_{k}^{t}-\hat{r}_{k}^{t}\right)>\bar{r}_{1}^{t}\mathbbm{1}\left[\hat{d}_{1}^{t}<\bar{d}_{1}^{t}\right]$
(4)

We notice that because of (3), there exists a user $i\in P^{t}$ for whom
$\hat{r}_{i}^{t}>\bar{r}_{i}^{t}$; because of (4), there exists a user
$j\notin P^{t}$ for whom $\bar{r}_{j}^{t}>\hat{r}_{j}^{t}$. Additionally for
that $j$ we can assume that $\hat{d}_{j}^{t}=\bar{d}_{j}^{t}$ because:

  * •

If user $1$ does not deviate then for all $k$,
$\hat{d}_{k}^{t}=\bar{d}_{k}^{t}$.

  * •

If $\hat{d}_{1}^{t}<\bar{d}_{1}^{t}$, then (4) becomes $\sum_{k\notin
P^{t},\,k\neq 1}(\bar{r}_{k}^{t}-\hat{r}_{k}^{t})>0$, implying $j\neq 1$ which
entails $\hat{d}_{j}^{t}=\bar{d}_{j}^{t}$.

Thus we have $\hat{d}_{i}^{t}\leq\bar{d}_{i}^{t}$ (since no user over-
reports), $\hat{d}_{j}^{t}=\bar{d}_{j}^{t}$,
$\hat{r}_{i}^{t}>\bar{r}_{i}^{t}$, and $\hat{r}_{j}^{t}<\bar{r}_{j}^{t}$.
These, using Lemma 3.3, prove that
$\hat{R}_{i}^{t}-\bar{R}_{i}^{t}\leq\hat{R}_{j}^{t}-\bar{R}_{j}^{t}$. This is
a contradiction because $i\in P^{t}$ and $j\notin P^{t}$. ∎

Before proving the upper bound on the incentive compatibility ratio, first we
will prove that users have no incentive to over-report their demand. The
immediate effect of over-reporting is allocating resources to user $1$ in
excess of her demand, which do not contribute to her utility. Intuitively,
this suggests that user $1$ is put into a disadvantageous position: other
users get less resources which makes them be favored by the allocation
algorithm in the future, while user $1$ becomes less favored. However, a small
change in the users’ resources causes a cascading change in future allocations
making the proof of this theorem hard. We will see in Section 4 that this is
no longer the case with multiple resources when users only use a subset of
them. We defer the proof of the theorem to the end of this section.

######  Theorem 3.5.

Users have nothing to gain in Dynamic MMF by declaring a demand higher than
their actual demand, for any value $\alpha\in[0,1]$.

Now we show that using this theorem and Lemma 3.4 allows us to bound the
incentive to deviate. A bound of $2$ is easy to get by summing (2) for all $t$
up to some certain epoch and assuming that $\bar{d}_{i}^{t}$ are users’ true
demands ($\bar{d}=d$) and that $\hat{d}_{1}$ is any under-reporting of user
$1$. We give an incentive compatibility bound of $3/2$ by using the same
lemma, but arguing that some other user $j$ must also share the same increased
allocation of resources as user $1$ using Lemma 3.3.

######  Theorem 3.6.

In Dynamic MMF for any value of $\alpha\in[0,1]$, no user can misreport her
demand to increase her utility by a factor larger than $3/2$, i.e., for any
user $i$ and demand misreporting user $i$ makes,
$\hat{U}_{i}^{t}\leq\frac{3}{2}U_{i}^{t}$, for all epochs $t$.

###### Proof.

We will prove the theorem for $i=1$. Theorem 3.5 implies that it is of no loss
of generality to assume that user $1$ does not over-report her demand, since
any benefit gained by over-reporting can be gained by changing every over-
report to a truthful one. This means that instead of
$\hat{U}_{1}^{t}\leq\frac{3}{2}U_{1}^{t}$ we can show
$\hat{R}_{1}^{t}\leq\frac{3}{2}R_{1}^{t}$. Towards a contradiction, let $t$ be
the first epoch when user $1$ gets more than $3/2$ more resources by some
deviation of demands, i.e., $\hat{R}_{1}^{t}>\frac{3}{2}R_{1}^{t}$ and
$\hat{R}_{1}^{t-1}\leq\frac{3}{2}R_{1}^{t-1}$. This implies that
$\hat{r}_{1}^{t}>r_{1}^{t}$, which in turn entails that there exists a user
$j$ for who $\hat{r}_{j}^{t}<r_{j}^{t}$, since the total resources allocated
when user $1$ is under-reporting cannot be less than those when 1 is truthful.
Because $\hat{r}_{1}^{t}>r_{1}^{t}$, $\hat{r}_{j}^{t}<r_{j}^{t}$,
$\hat{d}_{1}^{t}\leq d_{1}^{t}$, and $\hat{d}_{j}^{t}=d_{j}^{t}$, we can use
Lemma 3.3 and get $\hat{R}_{1}^{t}-R_{1}^{t}\leq\hat{R}_{j}^{t}-R_{j}^{t}$.
This inequality, $\hat{R}_{1}^{t}-R_{1}^{t}\geq 0$, and Lemma 3.4 by summing
(2) for every epoch up to $t$, implies

$2\left(\hat{R}_{1}^{t}-R_{1}^{t}\right)\;\leq\;\left(\hat{R}_{1}^{t}-R_{1}^{t}\right)+\left(\hat{R}_{j}^{t}-R_{j}^{t}\right)\;\leq\;\sum_{k\in[n]}\left(\hat{R}_{k}^{t}-R_{k}^{t}\right)^{+}\;\leq\;\sum_{\tau=1}^{t}r_{1}^{\tau}\;=\;R_{1}^{t}$

The above inequality leads to $\hat{R}_{1}^{t}\leq\frac{3}{2}R_{1}^{t}$, a
contradiction. ∎

Finally, we prove Theorem 3.5, that users have no incentive to over-report. To
do that, we use the following lemma, which says that if a user wants to
increase her utility in epoch $T$, she has nothing to gain by over-reporting
her demand in epoch $T_{0}$, given that she does not over-report her demand in
epochs $T_{0}+1$ to $T$.

######  Lemma 3.7.

Fix an epoch $T_{0}$ and the allocations of an outcome
$\\{\hat{R}_{k}^{T_{0}-1}\\}_{k\in[n]}$. Fix another epoch $T\geq T_{0}$ and
assume that in epochs $t=T_{0}+1,T_{0}+2,\ldots,T$ user $1$ does not over-
report her demand, i.e., $\hat{d}_{1}^{t}\leq d_{i}^{t}$. Then user $1$ cannot
increase her utility in round $T$ by over-reporting her demand in epoch
$T_{0}$, for any $\alpha\in[0,1]$.

By over-reporting her demand in $T_{0}$, user $1$ (potentially) gains some
resources that do not contribute to her utility, while others get less
resources. This puts user $1$ in a disadvantage entailing that in the epochs
after $T_{0}$ she cannot increase her total allocation further (even though it
is possible that her allocation in a single epoch can increase). Since she
doesn’t over-report her demand in epochs after $T_{0}$ her allocation is the
same as her utility, hence her total utility also does not increase.

###### Proof.

To prove the lemma we are going to create another outcome in which user $1$
changes her over-report in epoch $T_{0}$ to a truthful one which does not
decrease her total utility in epoch $T$.

For all users $k$ and epochs $t$, let $\bar{d}_{k}^{t}=\hat{d}_{k}^{t}$,
except for $\bar{d}_{1}^{T_{0}}$, which is user $1$’s actual demand:
$\bar{d}_{1}^{T_{0}}=d_{1}^{T_{0}}$. This means that the two outcomes are the
same before epoch $T_{0}$, i.e., for all users $k$,
$\bar{R}_{k}^{T_{0}-1}=\hat{R}_{k}^{T_{0}-1}$ and
$\bar{U}_{k}^{T_{0}-1}=\hat{U}_{k}^{T_{0}-1}$. Because
$\hat{d}_{1}^{T_{0}}>\bar{d}_{1}^{T_{0}}$ and for $k\neq 1$,
$\hat{d}_{k}^{T_{0}}=\bar{d}_{k}^{T_{0}}$, user $1$ may earn some additional
resources on $T_{0}$, i.e.,
$\hat{r}_{1}^{T_{0}}-\bar{r}_{i}^{T_{0}}=\hat{R}_{1}^{T_{0}}-\bar{R}_{i}^{T_{0}}=x$,
for some $x\geq 0$, while other users $k\neq 1$ get less resources:
$\hat{r}_{k}^{T_{0}}-\bar{r}_{k}^{T_{0}}=\hat{R}_{k}^{T_{0}}-\bar{R}_{k}^{T_{0}}\leq
0$. We first note that the $x$ additional resources that user $1$ gets are in
excess of $1$’s true demand, meaning they do not contribute towards her
utility:

$\hat{U}_{1}^{T_{0}}-\bar{U}_{1}^{T_{0}}=\hat{R}_{1}^{T_{0}}-\bar{R}_{1}^{T_{0}}-x=0$
(5)

Additionally, because user $1$ does not over-report $\hat{d}_{1}^{t}$ or
$\bar{d}_{1}^{t}$ in epochs $t\in[T_{0}+1,T]$, it holds that for
$t\in[T_{0}+1,T]$ user $1$’s utility is the same as the resources she
receives: $\bar{u}_{1}^{t}=\bar{r}_{1}^{t}$ and
$\hat{u}_{1}^{t}=\hat{r}_{1}^{t}$. This fact, combined with (5) proves that

$\forall
t\in[T_{0},T],\;\hat{U}_{1}^{t}-\bar{U}_{1}^{t}=\hat{R}_{1}^{t}-\bar{R}_{1}^{t}-x$

Thus, in order for this over-reporting to be a strictly better strategy, it
must hold that $\hat{R}_{1}^{T}-\bar{R}_{1}^{T}>x$. We will complete the proof
by proving that the opposite holds. Since in epochs $t\in[T_{0}+1,T]$ it holds
that $\hat{d}_{1}^{t}=\bar{d}_{1}^{t}$, we can use Lemma 3.4 to sum (2) for
all $t\in[T_{0}+1,T]$ and get that

$\sum_{k}\left(\hat{R}_{k}^{T}-\bar{R}_{k}^{T}\right)^{+}-\sum_{k}\left(\hat{R}_{k}^{T_{0}}-\bar{R}_{k}^{T_{0}}\right)^{+}\leq
0$

The above inequality, because $(\hat{R}_{k}^{T}-\bar{R}_{k}^{T})^{+}\geq 0$,
$\hat{R}_{k}^{T_{0}}-\bar{R}_{k}^{T_{0}}\leq 0$ for $k\neq 1$, and
$\hat{R}_{1}^{T_{0}}-\bar{R}_{1}^{T_{0}}=x\geq 0$, proves that
$\hat{R}_{1}^{T}-\bar{R}_{1}^{T}\leq x$. This completes the proof. ∎

###### Proof of Theorem 3.5.

Fix an epoch $T$ and let $T_{0}\leq T$ be the last epoch where user $1$ over-
reported. Lemma 3.7 allows us to change user $1$’s over-report in $T_{0}$ to a
truthful one without decreasing her total utility in $T$. Doing this
inductively for every such $T_{0}$ creates a demand profile with no over-
reporting that does not decrease user $1$’s total utility in $T$. ∎

Envy-freeness in Dynamic MMF. We finally note that Dynamic MMF is envy-free,
for any value of the parameter $\alpha$. This is a corollary of the fact that
Dynamic DRF, the generalization of Dynamic MMF for multiple resources, is
envy-free (see details in Theorems 4.8 and 4.9).

##  4 Multiple Resources Setting

In this section we turn to the main focus of our paper, analyzing the
generalization of Dynamic MMF for multiple resources, Dynamic Dominant
Resource Fairness (Dynamic DRF).

Notation and User Utilities. We consider users that have varying demand for a
set of $m\geq 1$ different resources over time. We use $1,2,\ldots,q,\ldots,m$
to denote the $m$ resources, and w.l.o.g., we assume that for every resource
the amount available is the same, $\mathcal{R}$. A typical example of such a
system may focus on users running applications that use resources such as CPU,
memory, storage, etc.

Every epoch, each user demands a non-negative amount of every resource which
they report to the mechanism. With the multidimensional nature of demand,
users have more complex ways to misreport their demand. Throughout this paper
we will assume that users have Leontief preferences, which we define next.
Leontief preferences have been considered by much of the previous work in
resource sharing, including [Gho+11, PPS12, KPS13].

Formally, with Leontief preferences a user $i$’s demand in an epoch $t$ is
characterized by the ratios $a_{i}^{t}=(a_{i1}^{t},\ldots,a_{im}^{t})$ she
needs for the resources and a demand $d_{i}^{t}$. The ratios indicate that for
some $\xi\geq 0$, user $i$’s application in that epoch is going to use $\xi
a_{iq}^{t}$ amount of every resource $q\in[m]$. The resource $q$ with the
maximum ratio $a_{iq}^{t}$ is called the dominant resource of user $i$ in
epoch $t$. We assume that ratios are normalized: for every epoch $t$,
$\max_{q}a^{t}_{iq}=1$ for all users. The demand $d_{i}^{t}$ of user $i$ in
epoch $t$ represents the maximum fraction $\xi$ (possibly, $\xi>1$) of the
ratios the user can take advantage of. More specifically, user $i$ demands (or
is asking for) $d_{i}^{t}a_{iq}^{t}$ amount of every resource $q$. If a user
$i$ receives $x_{i1}^{t},\ldots,x_{im}^{t}$ of every resource, respectively,
her utility that epoch is
$u_{i}^{t}=\min\big{\\{}d_{i}^{t},\min_{q:a_{iq}>0}\\{x^{t}_{iq}/a^{t}_{iq}\\}\big{\\}}$.
In each epoch, users will be asked to report both their ratios for the epoch
as well as their demand. Note that users can now misreport their type in two
different ways: they can either request less or more from all the resources or
they can demand the resources in different proportions (or they can do both).

##### Dynamic Dominant Resource Fairness

DRF is the generalization of MMF for the case of multiple resources, where the
fairness criterion is applied to each user’s dominant resource and the rest of
the resources are distributed according to the users’ ratios. If $r_{i}^{t}$
is the amount that user $i$ receives of her dominant resource in epoch $t$,
then she receives $r_{i}^{t}a_{iq}^{t}$ of every resource $q$ (recall that
$\max_{q}a_{iq}^{t}=1$). We call $r_{i}^{t}$ the allocation of user $i$ in
epoch $t$.

Dynamic DRF extends to dynamic user demands the weighted DRF policy, the
generalization of DRF where the fairness criterion is applied to the users’
allocation normalized by some weights, indicating users’ priorities. More
specifically, if every user $i$ is associated with a weight $w_{i}>0$, then
the mechanism tries to give to each user $i$ an allocation proportional to her
weight $w_{i}$.

Similar to Dynamic MMF, Dynamic DRF has an additional parameter
$\alpha\in[0,1]$ that guarantees a fraction of fair share of each resource to
each user in every epoch, independent of allocations in previous ones. User
$i$’s fair share of a resource $q$ is $\mathcal{R}w_{i}/(\sum_{j}w_{j})$. When
$\alpha=1$, we guarantee at least the fair share of their dominant resource
(assuming a big enough demand to use it), when $\alpha<1$ we guarantee a
smaller share. Beyond this guarantee, the goal of the mechanism in epoch $t$
is to be as fair as possible to the cumulative allocation of every user,
normalized by their weights. We use $R_{i}^{t}=\sum_{\tau=1}^{t}r_{i}^{\tau}$
for the sum of allocations till time $t$. Using this notation, Dynamic DRF is
easy to describe. For a given epoch $t$, assuming that every user $i$ has
cumulative allocation $R_{i}^{t-1}$:

$\displaystyle\begin{split}\textrm{choose
}\;\;&r_{1}^{t},\,r_{2}^{t},\,\ldots,\,r_{n}^{t}\\\ \textrm{applying max-min
fairness on
}\;\;&\frac{R_{1}^{t-1}+r_{1}^{t}}{w_{1}},\,\frac{R_{2}^{t-1}+r_{2}^{t}}{w_{2}},\,\ldots,\,\frac{R_{n}^{t-1}+r_{n}^{t}}{w_{n}}\\\
\textrm{given the constraints }\;\;&\forall
i\in[n],\,\min\left\\{d_{i}^{t},\alpha\frac{\mathcal{R}w_{i}}{\sum_{k\in[n]}w_{k}}\right\\}\leq
r_{i}^{t}\leq d_{i}^{t},\\\ &\forall
q\in[m],\sum_{i\in[n]}r_{i}^{t}\,a_{iq}^{t}\leq\mathcal{R}\end{split}$ (6)

We define
$g_{i}(d_{i}^{t})=\min\left\\{d_{i}^{t},\alpha\frac{\mathcal{R}w_{i}}{\sum_{k}w_{k}}\right\\}$
to be the guaranteed amount that every user receives every epoch. Note that
$g_{i}(\cdot)$ is a non-decreasing function.

We note a few properties that immediately follow from the description. If all
users share the same dominant resource $q^{t}$ in each epoch and have equal
weights, then the mechanism will become identical to Dynamic MMF, as at each
epoch the allocation of the shared dominant resource is the bottleneck for all
users.

Second, if all the users share their dominant resource $q^{t}$, $\alpha=1$,
and demands are high, then the minimum guarantee becomes
$g(d_{i}^{t})=\mathcal{R}w_{i}/\sum_{k}w_{k}$ which will become user $i$’s
allocation, as this saturates resource $q^{t}$ (the guaranteed total use of
$q^{t}$ is
$\sum_{i}g(d_{i}^{t})a_{iq^{t}}^{t}=\sum_{i}g(d_{i}^{t})=\mathcal{R}$).
However, even with large demands each iteration and $\alpha=1$, the dynamic
fair sharing nature of our allocation will play an important role when
applications (users) do not always share their dominant resource.

Third, because of the guarantee of every user, Dynamic DRF satisfies
$\alpha$-sharing incentives.

######  Theorem 4.1.

When every user is guaranteed an $\alpha$-fraction of their fair share,
Dynamic DRF satisfies $\alpha$-sharing incentives.

##### User’s utility when misreporting ratios

In defining the Dynamic DRF mechanism, we have not considered the difference
of truthful reporting and misreporting one’s demands or ratios to the
mechanism. The main topic of this section is understanding how a user’s
utility behaves in these two scenarios for Dynamic DRF.

When user $i$ truthfully reports her demand $d_{i}^{t}$ and ratios
$a_{i}^{t}$, and Dynamic DRF gives her an allocation of $r_{i}^{t}$, her
utility in in that epoch is
$u_{i}^{t}=\min\\{d_{i}^{t},\min_{q:a_{iq}^{t}>0}\nicefrac{{r_{i}^{t}a_{iq}^{t}}}{{a_{iq}^{t}}}\\}=r_{i}^{t}$,
since Dynamic DRF guarantees that $r_{i}^{t}\leq d_{i}^{t}$.

When user $i$ misreports $\hat{a}_{i}^{t}$ and $\hat{d}_{i}^{t}$, and Dynamic
DRF gives her an allocation $\hat{r}_{i}^{t}$ based on the reported values,
let $\hat{u}_{i}^{t}$ denote the user’s true utility in epoch $t$ under that
reporting. In this case she receives
$x_{iq}^{t}=\hat{a}_{iq}^{t}\hat{r}_{i}^{t}$ of every resource $q$ and thus
she gets true utility

$\hat{u}_{i}^{t}=\min\left\\{d_{i}^{t},\min_{q:a_{iq^{t}}>0}\frac{x^{t}_{iq}}{a^{t}_{iq}}\right\\}=\min\left\\{d_{i}^{t},\,\hat{r}_{i}^{t}\min_{q:a_{iq^{t}}>0}\frac{\hat{a}_{iq}^{t}}{a_{iq}^{t}}\right\\}$

We define
$\hat{\lambda}_{i}^{t}=\min_{q:a_{iq^{t}}>0}\\{\hat{a}_{iq}^{t}/a_{iq}^{t}\\}$
making the above expression equal to
$\hat{u}_{i}^{t}=\min\\{d_{i}^{t},\,\hat{r}_{i}^{t}\,\hat{\lambda}_{i}^{t}\\}$.
We should note that if the user reports ratios truthfully
($\hat{a}_{i}^{t}=a_{i}^{t}$), then $\hat{\lambda}_{i}^{t}=1$. Additionally,
because each user is constrained to declare
$\max_{q}\hat{a}_{iq}^{t}=\max_{q}a_{iq}^{t}=1$, it must hold that
$\hat{\lambda}_{i}^{t}\leq 1$ for any $\hat{a}_{i}^{t}$ .

Similar to Section 3, the total utility of user $i$ by epoch $t$ is
$U_{i}^{t}=\sum_{\tau=1}^{t}u_{i}^{\tau}$.

###  4.1 Incentives assuming positive ratios for all resources

Our main results in this paper consider Dynamic DRF resource allocation with
multiple resources under the assumption that when users want to use the
system, they demand at least some of each of the resources, that is
$a_{iq}^{t}>0$ for all $i,q,t$. With typical system resources, such as CPU,
memory, RAM, etc., it is indeed the likely scenario. While different
applications have different dominant resources (e.g., some have heavy use of
compute power, while in others the main bottleneck is bandwidth), each uses at
least some of each one of these basic resources.

As already observed by [PPS12] [PPS12], having zero ratios for some resources
significantly changes the problem from having a tiny $\epsilon>0$ ratio, no
matter how small $\epsilon$ is. In Appendix Bwe show that with zero ratios
users do have an incentive to over-report their demand, which will turn out to
not be useful with positive ratios. Further, the benefit of such over-
reporting can increase the user’s utility by a factor of $\Omega(m)$,
increasing with the number of resources in the system.

In contrast, the main results of this section are that, assuming users have
positive ratios, misreporting them, as well as over-reporting demand, is not
beneficial (Theorem 4.4). Further, the approximate incentive compatibility
ratio for user $1$ is bounded by $1+\rho_{1}$, where $\rho_{1}=\max_{k\neq
1,q,t}\big{\\{}\nicefrac{{w_{1}a_{1q}^{t}}}{{w_{k}a_{kq}^{t}}}\big{\\}}$
(Theorem 4.6), and this bound is tight (Theorem 4.7) even with just two
resources and static ratios, extending the results of Section 3 to multiple
resources.

##### Upper bound on incentive compatibility ratio

We start by pointing out why positive ratios are so different from zero ones.
With positive ratios, users are bottlenecked by the same resource being
saturated. In contrast, when ratios are zero, different users are bottlenecked
by different resources, resulting in users’ allocations being almost
independent from one another (which is the case if users do not share
resources for which they both have positive ratios). The difficulty in
adapting the results of Section 3 to the case of multiple resources comes from
the fact that different users use the resources in different proportions. For
example, consider the users’ allocations being bottlenecked by a single
saturated resource $q$ for which user $1$ has a ratio of $1$ and user $i$ has
a ratio of $\epsilon<1$. User $1$ can free a $\delta$ amount of resource $q$
by under-reporting her demand so that her allocation gets smaller by $\delta$,
for a small $\delta>0$. If this available amount of resources goes to user
$i$, it has the potential to raise her allocation by $\delta/\epsilon$ (recall
that user $i$ has a ratio of $\epsilon$ for resource $q$), which is
disproportionally bigger than the $\delta$ utility that user $1$ lost.

The assumption that all users are using each resource allows us to prove a
lemma analogous to Lemma 3.3, as with this assumption, we can increase any
user’s allocation by decreasing another user’s allocation, allowing the proof
to be identical to the proof of Lemma 3.3. In contrast, if $a_{iq}^{t}=0$ and
$a_{jq}^{t}>0$, then decreasing the allocation of user $i$ does not free any
amount of resource $q$ for user $j$. Proving this lemma will lead to results
similar to Theorems 3.5 and 3.6.

######  Lemma 4.2.

Fix an epoch $t$ and the total allocations up to epoch $t-1$ of any two
outcomes $\\{\hat{R}_{k}^{t-1}\\}_{k\in[n]}$ and
$\\{\bar{R}_{k}^{t-1}\\}_{k\in[n]}$. Let $i,j$ be two different users. If the
following conditions hold

  * •

For $i$, $\,\bar{r}_{i}^{t}<\hat{r}_{i}^{t}$,
$\,\hat{d}_{i}^{t}\leq\bar{d}_{i}^{t}$, and $\hat{a}_{iq}^{t}>0$ for all $q$.

  * •

For $j$, $\,\bar{r}_{j}^{t}>\hat{r}_{j}^{t}$,
$\,\bar{d}_{j}^{t}\leq\hat{d}_{j}^{t}$, and $\bar{a}_{jq}^{t}>0$ for all $q$.

then, for any $\alpha\in[0,1]$ used by Dynamic DRF, it holds that
$\bar{R}_{i}^{t}/w_{i}\geq\bar{R}_{j}^{t}/w_{j}$ and
$\hat{R}_{i}^{t}/w_{i}\leq\hat{R}_{j}^{t}/w_{j}$, implying

$\frac{\hat{R}_{i}^{t}-\bar{R}_{i}^{t}}{w_{i}}\leq\frac{\hat{R}_{j}^{t}-\bar{R}_{j}^{t}}{w_{j}}$

The proof of this lemma is identical to the one in Lemma 3.3, so it’s deferred
in Appendix B.

Now we present an auxiliary lemma, similar to Lemma 3.4, but this time we
bound the increase of any user’s allocation when user $1$ deviates, i.e.,
$\hat{R}_{k}^{t}-R_{k}^{t}$ for each $k$. This lemma shows the key difficulty
in extending the results to the multiple resource case: reporting low demand
in one epoch can result in a different user being able to get much higher
amounts, even when the two users have the same dominant resource.
Unfortunately, as a result of this difficulty the resulting bound is a weaker
version of Lemma 3.4, involving the parameter $\rho_{1}$. If the users ratios
are the same and users have same priority, i.e., $w_{i}=w_{j}$ and
$a_{i}^{t}=a_{j}^{t}$ for every $t$ and $i\neq j$, then $\rho_{1}=1$ and the
following lemma would allow us to prove a $2$-incentive compatibility ratio
upper bound. In general however, the incentive compatibility ratio depends on
$\rho_{1}$ and it becomes larger the larger $\rho_{1}$ is.

######  Lemma 4.3.

Fix an epoch $t$ and the allocations of two different outcomes
$\\{\hat{R}_{k}^{t-1}\\}_{k\in[n]}$ and $\\{\bar{R}_{k}^{t-1}\\}_{k\in[n]}$
for which it holds that for some $X\geq 0$,

$\forall k\in[n],\;\;\frac{\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1}}{w_{k}}\leq X$
(7)

If in epoch $t$ users have positive ratios, user $1$ reports her ratios
truthfully, i.e., $\hat{a}_{1}^{t}=\bar{a}_{1}^{t}=a_{1}^{t}$, and
$\hat{d}_{1}^{t}\leq\bar{d}_{1}^{t}$ then, for all $\alpha\in[0,1]$ used by
Dynamic DRF it holds that

$\forall k\in[n],\;\;\frac{\hat{R}_{k}^{t}-\bar{R}_{k}^{t}}{w_{k}}\leq
X+\mathbbm{1}\left[\hat{d}_{1}^{t}<\bar{d}_{1}^{t}\right]\rho_{1}^{t}\frac{\bar{r}_{1}^{t}}{w_{1}}$

where $\rho_{1}^{t}=\max_{k\neq
1,\,q\in[m]}\frac{w_{1}a_{1q}^{t}}{w_{k}a_{kq}^{t}}$.

The above lemma, by assuming truthful reporting of ratios and that user $1$
does not over-report her demand ($\hat{d}_{1}^{t}\leq d_{1}^{t}$), inductively
proves a $\big{(}1+\max_{t}\\{\rho_{1}^{t}\\}\big{)}$ incentive compatibility
ratio.

The proof of this lemma is similar to the one in Lemma 3.4. If
$\hat{d}_{1}^{t}=\bar{d}_{1}^{t}$, then users with larger
$\nicefrac{{\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1}}}{{w_{k}}}$ will not gain
additional resources. If $\hat{d}_{1}^{t}<\bar{d}_{1}^{t}$, user $1$ can
increase the allocation of some other user $k$, but by at most
$\rho_{1}^{t}\bar{r}_{1}^{t}\frac{w_{k}}{w_{1}}$; note that this is much
larger than $r_{1}^{t}$, the guarantee of Lemma 3.3.

###### Proof.

Assume that there exists a user $i$ such that

$\frac{\hat{R}_{i}^{t}-\bar{R}_{i}^{t}}{w_{i}}>X+\mathbbm{1}\left[\hat{d}_{1}^{t}<\bar{d}_{1}^{t}\right]\rho_{1}^{t}\frac{\bar{r}_{1}^{t}}{w_{1}}$
(8)

Subtracting (7) from (8) implies that

$\frac{\hat{r}_{i}^{t}-\bar{r}_{i}^{t}}{w_{i}}>\mathbbm{1}\left[\hat{d}_{1}^{t}<\bar{d}_{1}^{t}\right]\rho_{1}^{t}\frac{\bar{r}_{1}^{t}}{w_{1}}$
(9)

Note that (9) implies that user $i$ satisfies the requirements of user $i$ in
Lemma 4.2 (since for all users $k$ and resources $q$,
$\hat{d}_{k}^{t}\leq\bar{d}_{k}^{t}$ and $a_{kq}^{t}>0$). Now note that
because for all users $k$, $\hat{d}_{k}^{t}\leq\bar{d}_{k}^{t}$, there must
exist a resource $q^{*}$ for which

$\sum_{k}a_{kq^{*}}^{t}\,\bar{r}_{k}^{t}\geq\sum_{k}a_{kq^{*}}^{t}\,\hat{r}_{k}^{t}$

since otherwise no resources would be saturated in allocations
$\\{\bar{r}_{k}^{t}\\}_{k}$, which would imply that every user gets her demand
in that allocation, which would imply the same in allocations
$\\{\hat{r}_{k}^{t}\\}_{k}$ (since ratios are the same and demands are not
higher); the last fact leads to a contradiction. Multiplying (9) with
$a_{iq^{*}}^{t}w_{i}$ and adding it with the above inequality yields

$\sum_{k\neq
i}a_{kq^{*}}^{t}(\bar{r}_{k}^{t}-\hat{r}_{k}^{t})\;>\;w_{i}a_{iq^{*}}^{t}\mathbbm{1}\left[\hat{d}_{1}^{t}<\bar{d}_{1}^{t}\right]\rho_{1}^{t}\frac{\bar{r}_{1}^{t}}{w_{1}}\;\geq\;0$
(10)

(10) proves that there exists a user $j$ such that
$\bar{r}_{j}^{t}>\hat{r}_{j}^{t}$. Additionally, for that $j$ we can assume
that $\bar{d}_{j}^{t}=\hat{d}_{j}^{t}$; to see why that is we distinguish
three cases:

  * •

If $\hat{d}_{1}^{t}=\bar{d}_{1}^{t}$ then for all users $k$,
$\hat{d}_{k}^{t}=\bar{d}_{k}^{t}$.

  * •

If $i=1$, then $j\neq 1$ since $\hat{r}_{i}^{t}>\bar{r}_{i}^{t}$ and
$\bar{r}_{j}^{t}>\hat{r}_{j}^{t}$. Because $j\neq 1$,
$\hat{d}_{j}^{t}=\bar{d}_{j}^{t}$.

  * •

If $\hat{d}_{1}^{t}<\bar{d}_{1}^{t}$ and $i\neq 1$, then, (10) becomes

$\sum_{k\neq
i}a_{kq^{*}}^{t}(\bar{r}_{k}^{t}-\hat{r}_{k}^{t})\;>\;w_{i}a_{iq^{*}}^{t}\rho_{1}^{t}\frac{\bar{r}_{1}^{t}}{w_{1}}\;\overset{i\neq
1\implies}{\underset{\rho_{1}^{t}\geq\nicefrac{{w_{1}a_{1q^{*}}^{t}}}{{w_{i}a_{iq^{*}}^{t}}}}{\geq}}\;a_{1q^{*}}^{t}\bar{r}_{1}^{t}$

which implies that $\sum_{k\neq
i,1}a_{kq^{*}}^{t}(\bar{r}_{k}^{t}-\hat{r}_{k}^{t})>0$. This proves that we
can assume that $j\neq 1$, entailing $\hat{d}_{j}^{t}=\bar{d}_{j}^{t}$.

This proves that exists a user $j$ that satisfies the requirements of user $j$
from Lemma 4.2. Using the lemma on users $i$ and $j$ we get
$\frac{\hat{R}_{i}^{t}-\bar{R}_{i}^{t}}{w_{i}}\leq\frac{\hat{R}_{j}^{t}-\bar{R}_{j}^{t}}{w_{j}}$.
This is a contradiction, because it holds that
$\hat{R}_{j}^{t}-\bar{R}_{j}^{t}<\hat{R}_{j}^{t-1}-\bar{R}_{j}^{t-1}\leq
w_{j}X$ (from (7) and $\bar{r}_{j}^{t}>\hat{r}_{j}^{t}$) and
$\hat{R}_{i}^{t}-\bar{R}_{i}^{t}>w_{i}X$ (from (8)). ∎

Similarly to Theorem 3.5, we can now prove that there is no benefit to over-
reporting or misreporting ratios. As mentioned previously, this is a very
important property because it guarantees that every resource allocated is
utilized and that, even when user $1$ is not truthful, her utility is equal to
her allocation: $\hat{u}_{i}^{t}=\hat{r}_{i}^{t}$.

######  Theorem 4.4.

Assume that the users’ true ratios are positive, i.e., for all users
$i\in[n]$, resources $q\in[m]$, and epochs $t$, it holds that $a_{iq}^{t}>0$.
Then, for any $\alpha\in[0,1]$ used by Dynamic DRF, the users have nothing to
gain by declaring a demand higher than their actual demand, and any gain
achievable by misreporting ratios can also be obtained by under-reporting
demand.

The proof of this theorem is quite similar to the one in Theorem 3.5: first we
prove the following auxiliary lemma, that makes the proof of the theorem easy.
The lemma is similar to Lemma 3.7: if in epochs $T_{0}+1$ to $T$ user $1$ does
not over-report her demand and reports her ratios truthfully, she cannot
increase her utility in epoch $T$ by over-reporting demand or misreporting
ratios in $T_{0}$.

######  Lemma 4.5.

Fix an epoch $T_{0}$ and the allocations of an outcome
$\\{\hat{R}_{k}^{T_{0}-1}\\}_{k\in[n]}$. Fix another epoch $T\geq T_{0}$ and
assume that in epochs $T_{0}+1,T_{0}+2,\ldots,T$ user $1$ reports her ratios
truthfully and does not over-report her demand. Then, for any $\alpha\in[0,1]$
used by Dynamic DRF, any increase in user $1$’s utility in epoch $T$ gained by
over-reporting demand or misreporting ratios in $T_{0}$ can be achieved with
truthful ratio reporting and no demand over-reporting in epoch $T_{0}$.

The above proves that over-reporting demand or misreporting ratios is not
useful by applying the lemma inductively, similar to the proof of Theorem 3.5.

The lemma’s proof is based on an alternative reporting that both reports
ratios truthfully and guarantees no demand over-reporting. With this reporting
user $1$ is guaranteed the same utility without increasing her allocation or
decreasing the other user’s allocations; this entails a more advantageous
position for her in the following epochs.

###### Proof of Lemma 4.5.

We are going to consider another outcome that is the same as the one in the
lemma up to epoch $T_{0}-1$. All users $k\neq 1$ report the same type in all
epochs: $\bar{d}_{k}^{t}=\hat{d}_{k}^{t}$ and
$\bar{a}_{k}^{t}=\hat{a}_{k}^{t}$ for all $t$. In epoch $T_{0}$ user $1$
deviates from reporting $\hat{a}_{1}^{T_{0}}$ and $\hat{d}_{1}^{T_{0}}$, and
instead declares

  * •

her ratios truthfully: $\bar{a}_{1}^{T_{0}}=a_{1}^{T_{0}}$.

  * •

her demand:
$\bar{d}_{1}^{T_{0}}=\min\\{d_{1}^{T_{0}},\hat{\lambda}_{1}^{T_{0}}\hat{r}_{1}^{T_{0}}\\}$;
recall that
$\hat{\lambda}_{1}^{t}=\min_{q}\frac{\hat{a}_{1q}^{t}}{a_{1q}^{t}}\leq 1$.

Note that the above reporting satisfies what we want: it reports the ratios
truthfully and does not over-report the demand. In later epochs
$t\in[T_{0}+1,T]$ user $1$ does not deviate from the other reporting:
$\bar{a}_{1}^{t}=\hat{a}_{1}^{t}=a_{1}^{t}$ and
$\bar{d}_{1}^{t}=\hat{d}_{1}^{t}\leq d_{1}^{t}$.

Now we notice that in epoch $T_{0}$, for every resource $q$ it holds that

$\bar{a}_{1q}^{T_{0}}\,\bar{r}_{1}^{T_{0}}\;\overset{\bar{a}_{1}^{T_{0}}=a_{1}^{T_{0}}}{\underset{\bar{r}_{1}^{T_{0}}\leq\bar{d}_{1}^{\,T_{0}}}{\leq}}\;a_{1q}^{T_{0}}\,\bar{d}_{1}^{T_{0}}\;\overset{\textrm{definition}}{\underset{\textrm{of
}\bar{d}_{1}^{T_{0}}}{\leq}}\;a_{1q}^{T_{0}}\,\hat{\lambda}_{1}^{T_{0}}\,\hat{r}_{1}^{T_{0}}\;\overset{\textrm{definition}}{\underset{\textrm{of
}\hat{\lambda}_{1}^{T_{0}}}{\leq}}\;a_{1q}^{T_{0}}\,\frac{\hat{a}_{1q}^{T_{0}}}{a_{1q}^{T_{0}}}\,\hat{r}_{1}^{T_{0}}\;=\;\hat{a}_{1q}^{T_{0}}\,\hat{r}_{1}^{T_{0}}$
(11)

(11) proves that in allocation $\\{\bar{r}_{k}^{T_{0}}\\}_{k}$ user $1$ uses
less of every resource compared to allocation $\\{\hat{r}_{k}^{T_{0}}\\}_{k}$.
This proves that the following allocation is feasible:
$\bar{r}_{1}^{T_{0}}\leftarrow\bar{d}_{1}^{T_{0}}$ and for $k\neq 1$,
$\bar{r}_{1}^{T_{0}}\leftarrow\hat{r}_{1}^{T_{0}}$. Because
$\bar{d}_{1}^{T_{0}}\leq\hat{r}_{1}^{T_{0}}$ (which follows from
$\hat{\lambda}_{1}^{T_{0}}\leq 1$) we have that

$\bar{r}_{1}^{T_{0}}=\bar{d}_{1}^{\,T_{0}}\;\;\textrm{ and }\;\;\forall k\neq
1,\;\bar{r}_{k}^{T_{0}}\geq\hat{r}_{k}^{T_{0}}$ (12)

Now we notice that

$\hat{u}_{i}^{T_{0}}\;\overset{\textrm{definition}}{\underset{\textrm{of
utility}}{=}}\;\min\left\\{d_{i}^{T_{0}},\,\hat{r}_{i}^{T_{0}}\,\hat{\lambda}_{1}^{T_{0}}\right\\}\;\overset{\textrm{definition}}{\underset{\textrm{of
}\bar{d}_{1}^{T_{0}}}{=}}\;\bar{d}_{1}^{\,T_{0}}\;\overset{\eqref{eq:mult:45}}{=}\;\bar{r}_{1}^{T_{0}}\;\overset{\bar{d}_{1}^{T_{0}}\leq
d_{1}^{T_{0}}}{\underset{\bar{a}_{1}^{T_{0}}=a_{1}^{T_{0}}}{=}}\;\bar{u}_{1}^{T_{0}}$

The difference in total utility in epoch $T$ is

$\displaystyle\hat{U}_{1}^{T}-\bar{U}_{1}^{T}$ $\displaystyle=$
$\displaystyle\hat{U}_{1}^{T_{0}-1}-\bar{U}_{1}^{T_{0}-1}+\hat{u}_{1}^{T_{0}}-\bar{u}_{1}^{T_{0}}+\sum_{\tau=T_{0}+1}^{T}\left(\hat{u}_{1}^{\tau}-\bar{u}_{1}^{\tau}\right)$
$\displaystyle\overset{\textrm{same outcomes up to
}T_{0}-1}{\underset{\hat{u}_{1}^{T_{0}}=\bar{u}_{1}^{T_{0}}}{=}}$
$\displaystyle\sum_{\tau=T_{0}+1}^{T}\left(\hat{u}_{1}^{\tau}-\bar{u}_{1}^{\tau}\right)$
$\displaystyle\overset{\textrm{no demand over-
reporting}}{\underset{\textrm{and true ratio reporting in }\tau}{=}}$
$\displaystyle\sum_{\tau=T_{0}+1}^{T}\left(\hat{r}_{1}^{\tau}-\bar{r}_{1}^{\tau}\right)\;\overset{\hat{R}_{1}^{T_{0}-1}=\bar{R}_{1}^{T_{0}-1}}{\underset{}{=}}\;\hat{R}_{1}^{T}-\bar{R}_{1}^{T}-\left(\hat{r}_{1}^{T_{0}}-\bar{r}_{1}^{T_{0}}\right)$

Let $X=\hat{r}_{1}^{T_{0}}-\bar{r}_{1}^{T_{0}}\geq 0$. To prove that
$\hat{U}_{1}^{T}\leq\bar{U}_{1}^{T}$ (thus proving the lemma) all we need to
prove is that $\hat{R}_{1}^{T}-\bar{R}_{1}^{T}\leq X$. For every epoch
$t\in[T_{0}+1,T]$ the requirements of Lemma 4.3 are true in $t$ and
$\hat{d}_{1}^{t}=\bar{d}_{1}^{t}$, which proves inductively that if

$\forall
k\in[n]:\frac{\hat{R}_{k}^{T_{0}}-\bar{R}_{k}^{T_{0}}}{w_{k}}\leq\frac{X}{w_{1}}$
(13)

then for all $t\in[T_{0},T]$

$\forall
k\in[n]:\frac{\hat{R}_{k}^{t}-\bar{R}_{k}^{t}}{w_{k}}\leq\frac{X}{w_{1}}$

We can prove (13) by noticing that for $k\neq 1$, it holds
$\hat{R}_{k}^{t}-\bar{R}_{k}^{t}\leq 0\leq X$ (from (12) and
$\hat{R}_{k}^{T_{0}-1}=\bar{R}_{k}^{T_{0}-1}$) and for $k=1$ it holds that
$\hat{r}_{1}^{T_{0}}-\bar{r}_{1}^{T_{0}}=X$ and
$\hat{R}_{1}^{T_{0}-1}=\bar{R}_{1}^{T_{0}-1}$. This completes the proof. ∎

Now we prove the upper bound for the incentive compatibility of Dynamic DRF
with a simple proof utilizing Lemmas 4.3 and 4.4.

######  Theorem 4.6.

Assume that all users have positive ratios: $a_{iq}^{t}>0$ for all users $i$,
resources $q$, and epochs $t$. Then for any user $i$ and $\alpha\in[0,1]$ used
by Dynamic DRF, user $i$ cannot misreport her demand or ratios to increase her
utility by a factor larger than $(1+\rho_{i})$, where $\rho_{i}=\max_{k\neq
i,q,t}\Big{\\{}\frac{w_{i}a_{iq}^{t}}{w_{k}a_{kq}^{t}}\Big{\\}}$.

###### Proof.

W.l.o.g. we are going to prove the theorem for $i=1$. Because of Theorem 4.4
we can assume that user $1$ does not over-report her demand or misreport her
ratios and thus we can bound $\hat{R}_{1}^{t}$ instead of $\hat{U}_{1}^{t}$.
Lemma 4.3 inductively implies that for any $t$,
$\hat{R}_{1}^{t}-R_{1}^{t}\leq\rho_{1}R_{1}^{t}$, which proves the theorem. ∎

##### Lower bound on incentive compatibility ratio

In the last theorem we proved that the incentive compatibility ratio of user
$1$ is upper bounded by $(1+\rho_{1})$. We now show that if the only
constraints on users’ ratios and weights is that they are positive and
$\rho_{1}$ is fixed, then it is possible for the incentive compatibility ratio
of user $1$ to be $(1+\rho_{1})$, even if the users’ ratios do not change over
time.

######  Theorem 4.7.

For any $\epsilon\in(0,1)$, $w_{1},w_{2}>0$, and $\alpha\in[0,1]$ used by
Dynamic DRF, there is an instance where the users’ ratios are constant every
epoch, user $1$ has weight $w_{1}$ and another user has weight $w_{2}$,
$\rho_{1}=\frac{w_{1}}{w_{2}\epsilon}$, and user $1$ can under-report her
demand to increase her utility by a factor of $1+\rho_{1}$.

We briefly sketch the proof of the theorem when users have time-varying
ratios, there is only one resource, users have equal weights, and it does not
necessarily hold that $\max_{q\in[m]}a_{iq}^{t}=1$. With some complicated
details the full proof reduces to the same instance as the one we present
below.

###### Proof sketch.

There are two users, one resource, two epochs, $w_{1}=w_{2}=1$, and
$\alpha=0$.

  1. 1.

In epoch $1$, user $1$ has a ratio of $a_{1}^{1}=1$, user $2$ has a ratio of
$a_{2}^{1}=\epsilon$, the amount available of the resource is $1$, and both
users have infinite demand. Dynamic DRF allocates the resource such that
$r_{1}^{1}=r_{2}^{1}=\frac{1}{1+\epsilon}$.

  2. 2.

In epoch $2$, user $1$ has a ratio of $a_{1}^{2}=\delta\leq 1$, user $2$ has a
ratio of $a_{2}^{2}=1$, the amount available of the resource222We can assume
that in every epoch there is a different total amount of resources without
loss of generality: we can split an epoch into $x$ sub-epochs where in each
there are $1/x$ available resources. is $\delta/\epsilon$, and both have
infinite demand. Dynamic DRF, since the users’ past allocations are the same,
allocates the resource such that
$r_{1}^{2}=r_{2}^{2}=\frac{\delta/\epsilon}{1+\delta}$.

This results in
$R_{1}^{2}=R_{2}^{2}=\frac{1}{1+\epsilon}+\frac{\delta/\epsilon}{1+\delta}$.
We note that
$\rho_{1}=\max\left\\{\frac{a_{1}^{1}}{a_{2}^{1}},\frac{a_{1}^{2}}{a_{2}^{2}}\right\\}=\max\left\\{\frac{1}{\epsilon},\frac{\delta}{1}\right\\}=\frac{1}{\epsilon}$.

Now we study what happens when user $1$ deviates:

  1. 1.

If in epoch $1$ user $1$ demands $0$ resources, then Dynamic DRF allocates
$\hat{r}_{1}^{1}=0$ and $\hat{r}_{2}^{1}=1/\epsilon$.

  2. 2.

In epoch $2$, the previous misreporting results in user $1$ having a lower
total allocation, making Dynamic DRF allocate $\hat{r}_{1}^{2}=1/\epsilon$ and
$\hat{r}_{2}^{2}=0$.

This results in $\hat{R}_{1}^{2}=\hat{R}_{2}^{2}=1/\epsilon$. The incentive
compatibility ratio is

$\frac{\hat{R}_{1}^{2}}{R_{1}^{2}}=\frac{1/\epsilon}{\frac{1}{1+\epsilon}+\frac{\delta/\epsilon}{1+\delta}}\overset{\delta\to
0}{\underset{}{\to}}1+\frac{1}{\epsilon}=1+\rho_{1}$ (14)

∎

We defer the full proof in Appendix B. We should note that in the above proof
sketch and in the full proof of Theorem 4.7, even though
$\rho_{1}=1/\epsilon$, a ratio of user $1$ is $\delta$, which is much less
than $\epsilon$. If we wanted a bound in terms of
$\rho=\max_{i\in[n]}\rho_{i}$, the proof of Theorem 4.7 for $w_{1}=w_{2}$ (and
the proof sketch above, see (14) by taking $\delta=\epsilon$) easily yields a
$\frac{1+\rho}{2}$ lower bound.

###  4.2 Envy-freeness

In this section we prove that Dynamic DRF is envy-free.

######  Theorem 4.8.

For every $\alpha\in[0,1]$, Dynamic DRF is envy-free according to the weights
$w_{1},\ldots,w_{n}$, i.e., for every epoch $t$, no user $i$ envies the total
allocation of user $j$ scaled by $w_{i}/w_{j}$:

$U_{i}^{t}\geq\sum_{\tau=1}^{t}\min\left\\{d_{i}^{\tau},\,\frac{w_{i}}{w_{j}}r_{j}^{\tau}\min_{q:a_{iq}^{\tau}>0}\frac{a_{jq}^{\tau}}{a_{iq}^{\tau}}\right\\}$

The key to this proof is to study the (potential) first epoch $t$ user $i$
envies user $j$. In the simple case that $w_{i}=w_{j}$, that proves that
$r_{j}^{t}>r_{i}^{t}$, which leads to a reasoning similar to Lemma 4.2 proving
that $R_{j}^{t}\leq R_{i}^{t}$. However, since user $j$ has an allocation
smaller than $i$’s it is impossible for user $i$ to envy her.

###### Proof.

Towards a contradiction assume that in epoch $t$ user $i$ envies user $j$ for
the first time, i.e.,

$U_{i}^{t}=R_{i}^{t}<\sum_{\tau=1}^{t}\min\left\\{d_{i}^{\tau},\,\frac{w_{i}}{w_{j}}r_{j}^{\tau}\min_{q:a_{iq}^{\tau}>0}\frac{a_{jq}^{\tau}}{a_{iq}^{\tau}}\right\\}$
(15)

and

$U_{i}^{t-1}=R_{i}^{t-1}\geq\sum_{\tau=1}^{t-1}\min\left\\{d_{i}^{\tau},\,\frac{w_{i}}{w_{j}}r_{j}^{\tau}\min_{q:a_{iq}^{\tau}>0}\frac{a_{jq}^{\tau}}{a_{iq}^{\tau}}\right\\}$

Subtracting the two inequalities above we get

$r_{i}^{t}<\min\left\\{d_{i}^{t},\,\frac{w_{i}}{w_{j}}r_{j}^{t}\min_{q:a_{iq}^{t}>0}\frac{a_{jq}^{t}}{a_{iq}^{t}}\right\\}$

Using the above inequality we can prove that

  * •

$\min_{q:a_{iq}^{t}>0}\nicefrac{{a_{jq}^{t}}}{{a_{iq}^{t}}}>0$, i.e., user $j$
uses every resource that user $i$ uses.

  * •

$r_{i}^{t}<d_{i}^{t}$. This inequality proves that
$g_{i}(d_{i}^{t})=\alpha\mathcal{R}w_{i}/(\sum_{k}w_{k})$, since otherwise
$g_{i}(d_{i}^{t})=d_{i}^{t}=r_{i}^{t}$.

  * •

$r_{i}^{t}/w_{i}<r_{j}^{t}/w_{j}$, since
$\max_{q}a_{iq}^{t}=\max_{q}a_{jq}^{t}=1$. This inequality, since
$r_{i}^{t}\geq g_{i}(d_{i}^{t})=\alpha\mathcal{R}w_{i}/(\sum_{k}w_{k})$,
proves that $r_{j}^{t}>\alpha\mathcal{R}w_{j}/(\sum_{k}w_{k})\geq
g_{j}(d_{j}^{t})$.

These three facts, $r_{i}^{t}<d_{i}^{t}$, $r_{j}^{t}>g_{j}(d_{j}^{t})$, and
$\forall q:a_{iq}^{t}>0\implies a_{jq}^{t}>0$, prove that it would have been
feasible to increase $r_{i}^{t}$ (thus increasing $R_{i}^{t}$) by decreasing
$r_{j}^{t}$ (thus decreasing $R_{j}^{t}$). This proves that, because our
mechanism allocates resources max-min fairly, $R_{i}^{t}/w_{i}\geq
R_{j}^{t}/w_{j}$. The last inequality contradicts with (15), which proves that
$R_{i}^{t}/w_{i}<R_{j}^{t}/w_{j}$ since
$\max_{q}a_{iq}^{t}=\max_{q}a_{jq}^{t}=1$. ∎

######  Corollary 4.9.

Theorem 4.8 also proves that Dynamic MMF is envy-free (by restricting $m=1$
and $w_{i}=a_{i1}^{t}=1$ for every user $i$ and epoch $t$) and also that
Dynamic weighted MMF, which will be studied in Section 5.1, is envy-free (by
restricting $m=1$ and $a_{i1}^{t}=1$ for every user $i$ and epoch $t$).

##  5 Generalizations in Single Resource Settings

###  5.1 Coalitions and Dynamic Weighted Max-min Fairness

In this section we present a generalized version of our previous results: we
extend the results of Section 3 to Dynamic weighted MMF and when users collude
to increase their overall utility.

Notation. We begin with the necessary definitions for this section.

##### Dynamic weighted Max-min Fairness

Dynamic weighted MMF is a special case of Dynamic DRF where there is only one
resource, $m=1$, i.e., every epoch $t$ the following problem is solved

$\displaystyle\begin{split}\textrm{choose
}\;\;&r_{1}^{t},r_{2}^{t},\ldots,r_{n}^{t}\\\ \textrm{applying max-min
fairness on
}\;\;&\frac{R_{1}^{t-1}+r_{1}^{t}}{w_{1}},\;\frac{R_{2}^{t-1}+r_{2}^{t}}{w_{2}},\;\ldots,\;\frac{R_{n}^{t-1}+r_{n}^{t}}{w_{n}}\\\
\textrm{given the constraints
}\;\;&\sum_{i\in[n]}r_{i}^{t}\leq\mathcal{R}\;\;\;\textrm{ and
}\;\;\;\min\left\\{d_{i}^{t},\alpha\frac{\mathcal{R}w_{i}}{\sum_{k}w_{k}}\right\\}\leq
r_{i}^{t}\leq d_{i}^{t},\forall i\end{split}$ (16)

where $\alpha\in[0,1]$ and $w_{1},\dots,w_{n}$ are positive numbers, similar
to the definition of Dynamic DRF. Similar to previous sections, for a given
$\alpha$, we denote
$g_{i}(d_{i}^{t})=\min\left\\{d_{i}^{t},\alpha\mathcal{R}w_{i}/\sum_{k}w_{k}\right\\}$
the guarantee of user $i$ in epoch $t$. It is easy to see that Dynamic
weighted MMF satisfies $\alpha$-sharing incentives.

######  Theorem 5.1.

When every user is guaranteed an $\alpha$-fraction of their fair share,
Dynamic weighted MMF satisfies $\alpha$-sharing incentives.

##### Coalitions

When users form coalitions they try to increase the sum of their utilities by
each member of the coalition deviating. We bound that increase, i.e., if the
set $I\subset[n]$ of users forms a coalition and report demands
$\\{\hat{d}_{i}^{t}\\}_{i\in I,t}$ instead of $\\{d_{i}^{t}\\}_{i\in I,t}$,
then for some $\gamma\geq 1$ and for all $t$ we want to prove that $\sum_{i\in
I}\hat{U}_{i}^{t}\leq\gamma\sum_{i\in I}U_{i}^{t}$. Proofs of the results in
this section are included in Appendix C.

####  5.1.1 Over-reporting and Incentive Compatibility Upper Bound

Analogously to Theorem 3.5 users have nothing to gain in Dynamic weighted MMF
by over-reporting, even when colluding.

######  Theorem 5.2.

Let $I\subset[n]$ be a set of users that form a coalition. Then, for any value
of $\alpha\in[0,1]$ used by Dynamic weighted MMF, the users in $I$ have
nothing to gain over-reporting their demand.

Next we show a generalized version of Theorem 3.6. More specifically, that
users in the coalition cannot misreport their demands to increase their total
utility by a factor more than $2$ and if there is no coalition ($I=\\{i\\}$),
user $i$ cannot increase her utility by a factor larger than $1+\max_{j\neq
i}\frac{w_{i}}{w_{i}+w_{j}}$ (which is strictly less than $2$). We should note
that this result is much different than the results of Section 4: using the
notation of that section, here we have that $\rho_{i}=\max_{j\neq
i}\\{w_{i}/w_{j}\\}$. Even though $1+\rho_{i}$ is possibly unbounded, the
incentive compatibility ratio here is at most $2$.

######  Theorem 5.3.

Let $I\subset[n]$ be a set of users that form a coalition and
$w_{1},\ldots,w_{n}$ be any weights, according to which Dynamic weighted MMF
allocates resources. Then, for any $\alpha\in[0,1]$, any deviation of the
users in $I$, and any epoch $t$ it holds that

$\sum_{i\in I}\hat{U}_{i}^{t}\leq 2\sum_{i\in I}U_{i}^{t}$

Additionally, when $I=\\{i\\}$ for any user $i$, it holds that
$\hat{U}_{i}^{t}\leq\left(1+\max\limits_{j\neq
i}\dfrac{w_{i}}{w_{i}+w_{j}}\right)U_{i}^{t}$.

Note that if $I=\\{i\\}$ and users have the same weights the above theorem is
similar to Theorem 3.6. To prove Theorem 5.3 we prove Lemma C.2, a
generalization of Lemma 3.4 bounding the over-allocation of all users, where
the $r_{1}^{t}$ in the right hand side of the inequality is replaced with
$\sum_{i\in I}r_{i}^{t}$.

###  5.2 Getting more utility multiple times

In this section we study what happens when user $1$ deviates and gets more
utility over an extended time period, or multiple times. More specifically,
assuming that there are alternating intervals where either $\hat{R}_{1}>R_{1}$
or $\hat{R}_{1}<R_{1}$ we study the length of those intervals and the duration
between them. We first make the following definitions:

  * •

For $\ell=0,1,2,\ldots$ let $s_{\ell}$ be distinct and ordered times (i.e.,
$s_{\ell-1}<s_{\ell}$) when user $1$ begins having more resources by
misreporting, i.e., $\hat{R}_{1}^{s_{\ell}-1}\leq R_{1}^{s_{\ell}-1}$ and
$\hat{R}_{1}^{s_{\ell}}>R_{1}^{s_{\ell}}$.

  * •

For $\ell=0,1,2,\ldots$ let $e_{\ell}$ be the first time after epoch
$s_{\ell}$ when user $1$ begins having less resources by misreporting, i.e.,
$\hat{R}_{1}^{e_{\ell}-1}\geq R_{1}^{e_{\ell}-1}$ and
$\hat{R}_{1}^{e_{\ell}}<R_{1}^{e_{\ell}}$.

Note that $0<s_{0}<e_{0}<s_{1}<e_{1}<\ldots$ by definition. Using the above
notation we prove that if during every interval $[s_{\ell},e_{\ell}]$ user $1$
got a factor of $\gamma$ more resources in epoch $t_{\ell}$ for some
$t_{\ell}\in[s_{\ell},e_{\ell}]$ by misreporting, then $t_{\ell}$ cannot be
much larger than $s_{\ell}$ and that also $t_{\ell}$ scales exponentially with
$\ell$. The proof of the theorem is presented in Appendix D.

######  Theorem 5.4.

Assume that for every $t$, $R_{1}^{t}\in\Theta(t)$ and for every
$\ell=0,1,\ldots$ there exists an epoch $t_{\ell}\in[s_{\ell},e_{\ell})$ for
which $\hat{R}_{1}^{t_{\ell}}\geq\gamma R_{1}^{t_{\ell}}$, for some
$\gamma>1$. Then, in Dynamic MMF for any $\alpha\in[0,1]$, any
$\ell=0,1,\ldots$, and any $t_{\ell}\in[s_{\ell},e_{\ell})$ such that
$\hat{R}_{1}^{t_{\ell}}\geq\gamma R_{1}^{t_{\ell}}$, it holds that

$t_{\ell}=O(s_{\ell})\;\;\textrm{ and
}\;\;t_{\ell}=\left(\frac{2-\gamma}{3-2\gamma}\right)^{\ell}\Omega(t_{0})$

## References

  * [AW19] Martin Aleksandrov and Toby Walsh  “Strategy-Proofness, Envy-Freeness and Pareto Efficiency in Online Fair Division with Additive Utilities”  In _PRICAI 2019: Trends in Artificial Intelligence - 16th Pacific Rim International Conference on Artificial Intelligence, Cuvu, Yanuca Island, Fiji, August 26-30, 2019, Proceedings, Part I_ 11670, Lecture Notes in Computer Science  Springer, 2019, pp. 527–541  DOI: 10.1007/978-3-030-29908-8“˙42
  * [Ali+10] Mohammad Alizadeh et al.  “Data center tcp (dctcp)”  In _Proceedings of the ACM SIGCOMM 2010 Conference_ , 2010, pp. 63–74
  * [Arc+03] Aaron Archer, Christos H. Papadimitriou, Kunal Talwar and Éva Tardos  “An approximate truthful mechanism for combinatorial auctions with single parameter agents”  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA_ , 2003, pp. 205–214  URL: http://dl.acm.org/citation.cfm?id=644108.644144
  * [AB18] Eduardo M Azevedo and Eric Budish  “Strategy-proofness in the Large”  In _The Review of Economic Studies_ 86.1, 2018, pp. 81–116  DOI: 10.1093/restud/rdy042
  * [BSV19] Maria-Florina Balcan, Tuomas Sandholm and Ellen Vitercik  “Estimating Approximate Incentive Compatibility”  In _Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019_ , 2019, pp. 867  DOI: 10.1145/3328526.3329628
  * [Bou+14] Eric Boutin et al.  “Apollo: Scalable and Coordinated Scheduling for Cloud-Scale Computing”  In _11th USENIX Symposium on Operating Systems Design and Implementation, OSDI ’14, Broomfield, CO, USA, October 6-8, 2014_ USENIX Association, 2014, pp. 285–300  URL: https://www.usenix.org/conference/osdi14/technical-sessions/presentation/boutin
  * [Cha08] Charu Chaubal  “The architecture of VMware ESXi”  In _VMware White Paper_ 1.7, https://www.vmware.com/content/dam/digitalmarketing/vmware/en/pdf/techpaper/ESXi_architecture.pdf, 2008
  * [CAD18] Yue Cheng, Ali Anwar and Xuejing Duan  “Analyzing alibaba’s co-located datacenter workloads”  In _2018 IEEE International Conference on Big Data (Big Data)_ , 2018, pp. 292–297  IEEE
  * [CJ89] Dah-Ming Chiu and Raj Jain  “Analysis of the increase and decrease algorithms for congestion avoidance in computer networks”  In _Computer Networks and ISDN systems_ 17.1 Elsevier, 1989, pp. 1–14
  * [DFP08] Ofer Dekel, Felix A. Fischer and Ariel D. Procaccia  “Incentive compatible regression learning”  In _Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008_ , 2008, pp. 884–893  URL: http://dl.acm.org/citation.cfm?id=1347082.1347179
  * [Düt+12] Paul Dütting et al.  “Payment rules through discriminant-based classifiers”  In _Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012_ , 2012, pp. 477–494  DOI: 10.1145/2229012.2229048
  * [Fre+18] Rupert Freeman, Seyed Majid Zahedi, Vincent Conitzer and Benjamin C. Lee  “Dynamic Proportional Sharing: A Game-Theoretic Approach”  In _Proc. ACM Meas. Anal. Comput. Syst._ 2.1 New York, NY, USA: Association for Computing Machinery, 2018  DOI: 10.1145/3179406
  * [FPV15] Eric J. Friedman, Christos-Alexandros Psomas and Shai Vardi  “Dynamic Fair Division with Minimal Disruptions”  In _Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, Portland, OR, USA, June 15-19, 2015_ ACM, 2015, pp. 697–713  DOI: 10.1145/2764468.2764495
  * [FPV17] Eric J. Friedman, Christos-Alexandros Psomas and Shai Vardi  “Controlled Dynamic Fair Division”  In _Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017_ ACM, 2017, pp. 461–478  DOI: 10.1145/3033274.3085123
  * [Gho+11] Ali Ghodsi et al.  “Dominant Resource Fairness: Fair Allocation of Multiple Resource Types”  In _Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2011, Boston, MA, USA, March 30 - April 1, 2011_ USENIX Association, 2011  URL: https://www.usenix.org/conference/nsdi11/dominant-resource-fairness-fair-allocation-multiple-resource-types
  * [Gra+14] Robert Grandl et al.  “Multi-resource packing for cluster schedulers”  In _ACM SIGCOMM 2014 Conference, SIGCOMM’14, Chicago, IL, USA, August 17-22, 2014_ ACM, 2014, pp. 455–466  DOI: 10.1145/2619239.2626334
  * [Gra+16] Robert Grandl, Mosharaf Chowdhury, Aditya Akella and Ganesh Ananthanarayanan  “Altruistic Scheduling in Multi-Resource Clusters”  In _12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016_ USENIX Association, 2016, pp. 65–80  URL: https://www.usenix.org/conference/osdi16/technical-sessions/presentation/grandl%5C_altruistic
  * [Gra+16a] Robert Grandl et al.  “GRAPHENE: Packing and Dependency-Aware Scheduling for Data-Parallel Clusters”  In _12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016_ , 2016, pp. 81–97  URL: https://www.usenix.org/conference/osdi16/technical-sessions/presentation/grandl%5C_graphene
  * [Har18] Matt Harada  “The ad exchanges place in a first-price world”  Marketing Technology Insights, 2018  URL: https://martechseries.com/mts-insights/guest-authors
  * [HT19] Jason D. Hartline and Samuel Taggart  “Sample Complexity for Non-Truthful Mechanisms”  In _Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019_ ACM, 2019, pp. 399–416  DOI: 10.1145/3328526.3329632
  * [Hin+11] Benjamin Hindman et al.  “Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center”  In _Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2011, Boston, MA, USA, March 30 - April 1, 2011_ USENIX Association, 2011  URL: https://www.usenix.org/conference/nsdi11/mesos-platform-fine-grained-resource-sharing-data-center
  * [Hos19] Ridi Hossain  “Sharing is Caring: Dynamic Mechanism for Shared Resource Ownership”  In _Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019_ International Foundation for Autonomous AgentsMultiagent Systems, 2019, pp. 2417–2419  URL: http://dl.acm.org/citation.cfm?id=3332132
  * [Im+20] Sungjin Im, Benjamin Moseley, Kamesh Munagala and Kirk Pruhs  “Dynamic Weighted Fairness with Minimal Disruptions”  In _Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, Boston, MA, USA, June, 8-12, 2020_ ACM, 2020, pp. 5–6  DOI: 10.1145/3393691.3394184
  * [Kan+20] Kirthevasan Kandasamy et al.  “Online Learning Demands in Max-min Fairness”  In _CoRR_ abs/2012.08648, 2020  arXiv: https://arxiv.org/abs/2012.08648
  * [KPS13] Ian A. Kash, Ariel D. Procaccia and Nisarg Shah  “No agent left behind: dynamic fair division of multiple resources”  In _International conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’13, Saint Paul, MN, USA, May 6-10, 2013_ IFAAMAS, 2013, pp. 351–358  URL: http://dl.acm.org/citation.cfm?id=2484977
  * [KPS03] Anshul Kothari, David C. Parkes and Subhash Suri  “Approximately-strategyproof and tractable multi-unit auctions”  In _Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), San Diego, California, USA, June 9-12, 2003_ , 2003, pp. 166–175  DOI: 10.1145/779928.779948
  * [Kri09] Vijay Krishna  “Auction theory”  Academic press, 2009
  * [KVM16] KVM  “Main Page — KVM,”, https://www.linux-kvm.org, 2016
  * [LLL18] Bo Li, Wenyang Li and Yingkai Li  “Dynamic Fair Division Problem with General Valuations”  In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden_ ijcai.org, 2018, pp. 375–381  DOI: 10.24963/ijcai.2018/52
  * [MS14] Timo Mennle and Sven Seuken  “An axiomatic approach to characterizing and relaxing strategyproofness of one-sided matching mechanisms”  In _ACM Conference on Economics and Computation, EC ’14, Stanford , CA, USA, June 8-12, 2014_ , 2014, pp. 37–38  DOI: 10.1145/2600057.2602885
  * [PPS12] David C. Parkes, Ariel D. Procaccia and Nisarg Shah  “Beyond dominant resource fairness: extensions, limitations, and indivisibilities”  In _Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012_ ACM, 2012, pp. 808–825  DOI: 10.1145/2229012.2229075
  * [Par18] Rachel Parkin  “A year in first-price”  Ad Exchanger, 2018  URL: https://adexchanger.com/the-sell-sider/a-year-in-first-price
  * [Rei+12] Charles Reiss et al.  “Heterogeneity and dynamicity of clouds at scale: Google trace analysis”  In _Proceedings of the third ACM symposium on cloud computing_ , 2012, pp. 1–13
  * [SCC21] Hugo Sadok, Miguel Elias M. Campista and Luís Henrique M.. Costa  “Stateful DRF: Considering the Past in a Multi-Resource Allocation”  In _IEEE Trans. Computers_ 70.7, 2021, pp. 1094–1105  DOI: 10.1109/TC.2020.3006007
  * [SFS12] David Shue, Michael J. Freedman and Anees Shaikh  “Performance Isolation and Fairness for Multi-Tenant Cloud Storage”  In _10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012_ USENIX Association, 2012, pp. 349–362  URL: https://www.usenix.org/conference/osdi12/technical-sessions/presentation/shue
  * [Vav+13] Vinod Kumar Vavilapalli et al.  “Apache hadoop yarn: Yet another resource negotiator”  In _Proceedings of the 4th annual Symposium on Cloud Computing_ , 2013, pp. 1–16
  * [Ver+17] Alexandre Verbitski et al.  “Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases”  In _Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017_ ACM, 2017, pp. 1041–1052  DOI: 10.1145/3035918.3056101
  * [Ver+15] Abhishek Verma et al.  “Large-scale cluster management at Google with Borg”  In _Proceedings of the European Conference on Computer Systems (EuroSys)_ , 2015
  * [Vup+20] Midhul Vuppalapati et al.  “Building An Elastic Query Engine on Disaggregated Storage”  In _17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020, Santa Clara, CA, USA, February 25-27, 2020_ USENIX Association, 2020, pp. 449–462  URL: https://www.usenix.org/conference/nsdi20/presentation/vuppalapati
  * [Vup+20a] Midhul Vuppalapati et al.  “Building An Elastic Query Engine on Disaggregated Storage”  In _17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020, Santa Clara, CA, USA, February 25-27, 2020_ USENIX Association, 2020, pp. 449–462  URL: https://www.usenix.org/conference/nsdi20/presentation/vuppalapati
  * [YYR20] Juncheng Yang, Yao Yue and K.. Rashmi  “A large scale analysis of hundreds of in-memory cache clusters at Twitter”  In _14th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2020, Virtual Event, November 4-6, 2020_ USENIX Association, 2020, pp. 191–208  URL: https://www.usenix.org/conference/osdi20/presentation/yang
  * [ZP20] David Zeng and Alexandros Psomas  “Fairness-Efficiency Tradeoffs in Dynamic Fair Division”  In _EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020_ ACM, 2020, pp. 911–912  DOI: 10.1145/3391403.3399467

##  Appendix A Deferred Proofs of Section 3

In this section we prove Theorem 3.2, the lower bound for Dynamic MMF.

See 3.2

###### Proof.

We are going to prove the theorem for $\alpha=0$. We can do that without loss
of generality because for a fixed $\mathcal{R}$ we can add users with zero
demands (that do not affect the allocation) to make the guarantee
$g(d_{i}^{t})=\min\\{d_{i}^{t},\alpha\mathcal{R}/n\\}$ tend to $0$ for any
$\alpha\in[0,1]$.

The example in which a user (here called Alice) can deviate to increase her
allocation by a factor of almost $\sqrt{2}$ is the following (the details of
the example are also in Tables 2 and 3).

  * •

There are $1+m+k$ users: Alice, users $B_{1}$ to $B_{m}$, and users $C_{1}$ to
$C_{k}$.

  * •

The epochs are divided into 4 phases:

    1. 1.

In the first phase there are $m$ epochs. For $i\in[m]$, in the $i$-th of these
epochs only user $B_{i}$ has a demand, and she demands and gets an allocation
of $F_{i}$, which will be defined later333We can assume that in every epoch
there is a different total amount of resources without loss of generality: we
can split an epoch into $x$ sub-epochs where in each there are $1/x$ available
resources.. We are going to assume that $F_{i+1}\geq F_{i}$ and also define
$f_{i}=F_{i}-F_{i-1}$ with $F_{0}=0$.

    2. 2.

In the second phase there are again $m$ epochs. For $i\in[m]$, in the $i$-th
of these epochs there are $f_{i}$ resources and only users Alice and $B_{i}$
have demand, each demanding all the resources.

    3. 3.

In the third phase there are $k$ epochs. For $i\in[k]$, in the $i$-th of these
epochs there are $F_{m}$ resources and only users Alice and $C_{i}$ have
demand, each demanding all the resources.

    4. 4.

In the fourth phase there are $m$ epochs. In the 1st of these epochs there are
$f_{m}$ resources and only Alice and user $B_{m}$ have demands, demanding all
the resources. For $i\in[m-1]$, in the $(m-i+1)$-th of these epochs there are

$F_{m}-F_{i}+\frac{f_{m}}{2}\;=\;(F_{i}+f_{i})-(F_{i+1}+f_{i+1})$ (17)

resources (the above equation defines $F_{i}$) and only users Alice and
$B_{i}$ have demand, each demanding all the resources.

Users A |  Total allocations after phase 1 |  Epoch $i$, phase $2$, Alice and $B_{i}$, $i\in[m]$ |  Epoch $i$, phase $3$, Alice and $C_{i}$, $i\in[k]$ |  Total allocations after phase 3
---|---|---|---|---
Alice | $0$ | $0$ | $f_{i}$ | $f_{i}$ | $0$ | $F_{m}$ | $0$ | $F_{m}\,2^{-i}$ | $F_{m}$ | $F_{m}\left(1-2^{-k}\right)$
$B_{i}$, $i\in[m]$ | $F_{i}$ | $F_{i}$ | $f_{i}$ | $0$ | $f_{i}$ | $0$ | $0$ | $0$ | $F_{i}$ | $F_{i}+f_{i}$
$C_{i}$, $i\in[k]$ | $0$ | $0$ | $0$ | $0$ | $0$ | $F_{m}$ | $F_{m}$ | $F_{m}(1-2^{-i})$ | $F_{m}$ | $F_{m}(1-2^{-i})$
Table 2: The allocation of resources for the first 3 phases. The black numbers denote the users’ demands, the blue numbers are the users’ allocations in each epoch when Alice is truthful, and the red numbers are the allocations in each epoch when Alice misreports a demand of $0$ for every epoch of phase $2$. The total resources in each epoch is equal to the maximum demand of any user. Users |  Epoch $1$ phase $4$ |  Epoch $2$ phase $4$ | … |  Epoch $m-i+1$ phase $4$ | … |  Epoch $m$ phase $4$
---|---|---|---|---|---|---
Alice | $f_{m}$ | $\nicefrac{{f_{m}}}{{2}}$ | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{m-1}\end{subarray}$ | $0$ | … | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{i}\end{subarray}$ | $0$ | … | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{1}\end{subarray}$ | $0$
$B_{1}$ | $0$ | $0$ | $0$ | $0$ | … | $0$ | $0$ | … | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{1}\end{subarray}$ | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{1}\end{subarray}$
… | … | … | … | … | … | … | … | … | … | …
$B_{i}$ | $0$ | $0$ | $0$ | $0$ | … | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{i}\end{subarray}$ | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{i}\end{subarray}$ | … | $0$ | $0$
… | … | … | … | … | … | … | … | … | … | …
$B_{m-1}$ | $0$ | $0$ | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{m-1}\end{subarray}$ | $\begin{subarray}{c}F_{m}+\nicefrac{{f_{m}}}{{2}}\\\ -F_{m-1}\end{subarray}$ | … | $0$ | $0$ | … | $0$ | $0$
$B_{m}$ | $f_{m}$ | $\nicefrac{{f_{m}}}{{2}}$ | $0$ | $0$ | … | $0$ | $0$ | … | $0$ | $0$
Alice | $f_{m}$ | $f_{m}$ | $\begin{subarray}{c}(F_{m-1}+f_{m-1})\\\ -(F_{m}+f_{m})\end{subarray}$ | $\begin{subarray}{c}(F_{m-1}+f_{m-1})\\\ -(F_{m}+f_{m})\end{subarray}$ | … | $\begin{subarray}{c}(F_{i}+f_{i})\\\ -(F_{i+1}+f_{i+1})\end{subarray}$ | $\begin{subarray}{c}(F_{i}+f_{i})\\\ -(F_{i+1}+f_{i+1})\end{subarray}$ | … | $\begin{subarray}{c}(F_{1}+f_{1})\\\ -(F_{2}+f_{2})\end{subarray}$ | $\begin{subarray}{c}(F_{1}+f_{1})\\\ -(F_{2}+f_{2})\end{subarray}$
$B_{1}$ | $0$ | $0$ | $0$ | $0$ | … | $0$ | $0$ | … | $\begin{subarray}{c}(F_{1}+f_{1})\\\ -(F_{2}+f_{2})\end{subarray}$ | $0$
… | … | … | … | … | … | … | … | … | … | …
$B_{i}$ | $0$ | $0$ | $0$ | $0$ | … | $\begin{subarray}{c}(F_{i}+f_{i})\\\ -(F_{i+1}+f_{i+1})\end{subarray}$ | $0$ | … | $0$ | $0$
… | … | … | … | … | … | … | … | … | … | …
$B_{m-1}$ | $0$ | $0$ | $\begin{subarray}{c}(F_{m-1}+f_{m-1})\\\ -(F_{m}+f_{m})\end{subarray}$ | $0$ | … | $0$ | $0$ | … | $0$ | $0$
$B_{m}$ | $f_{m}$ | $0$ | $0$ | $0$ | … | $0$ | $0$ | … | $0$ | $0$
Table 3: The allocation of resources for phase 4. The top part of the table is
for when Alice is truthful, and the bottom part is for when Alice misreports a
demand of $0$ for every epoch of phase $2$. The total resources in each epoch
is equal to the maximum demand of any user.

If Alice is truthful she will end up with $F_{m}+\nicefrac{{f_{m}}}{{2}}$
resources after phase $4$. If she misreports a demand of $0$ in every epoch of
phase $2$ she will get an allocation of $F_{1}+f_{1}-F_{m}\,2^{-k}$ after
phase $4$ (both cases are depicted in Tables 2 and 3). Solving the recursive
equations (17) and taking $m\to\infty$ and $k\to\infty$ we get that

$\frac{F_{1}+f_{1}-F_{m}\,2^{-k}}{F_{m}+\nicefrac{{f_{m}}}{{2}}}\to\sqrt{2}$

which is the desired incentive compatibility ratio. For completeness, the
solution for $F_{i}$ when we set $F_{m}+f_{m}/2=1$ (for normalization) is

$F_{i}\;=\;\frac{\left(\sqrt{2}+1\right)^{m+1}\left(1-\left(\frac{2-\sqrt{2}}{2}\right)^{i}\right)+\left(\sqrt{2}-1\right)^{m+1}\left(1-\left(\frac{2+\sqrt{2}}{2}\right)^{i}\right)}{\left(\sqrt{2}-1\right)^{m+1}+\left(\sqrt{2}+1\right)^{m+1}}$

One can check that our initial conditions are true: for any $m\geq 1$,
$F_{i+1}\geq F_{i}$ and the quantities in (17) are positive. ∎

##  Appendix B Deferred Proofs of Section 4

###  B.1 Incentives when users have zero ratios

In this section we include the discussion about Dynamic DRF when some users
have zero ratios. This special case is much different, even when there is only
one epoch. To illustrate this, consider the example of [PPS12]: there are two
resources and three users with infinite demands and ratios $(1,\epsilon)$,
$(\epsilon,1)$, and $(\epsilon,1)$, for a small but positive $\epsilon$. If
the total amount available of every resource is $\mathcal{R}=1$, then DRF
gives every user an allocation of almost $1/2$. If instead $\epsilon=0$, it is
easy to check that the allocations are much different: the first user receives
an allocation of $1$, while the other two users still receive an allocation of
$1/2$.

For Dynamic DRF, we prove that a user can over-report her demand to increase
her allocation, even when the ratios stay fixed over time. In the next
section, we will show that this is no longer possible once all resources are
used by all users, even if the ratios are very different and change over time.

######  Theorem B.1.

For any $\alpha\in[0,1]$, there is an instance were all the users have the
same weights ($w_{i}=w_{j}$ for every users $i,j$), there are $m$ resources,
and users have static ratios some of which are zero where a user can increase
her utility by a factor of $\Theta(m)$ by only over-reporting her demand.

###### Proof.

Similar to the proof of Theorem 3.2, we are going to prove the theorem for
$\alpha=0$. We can do that without loss of generality because for a fixed
$\mathcal{R}$ we can add users with zero demands (that do not affect the
allocation) to make the guarantee
$g(d_{i}^{t})=\min\big{\\{}d_{i}^{t},\alpha\frac{\mathcal{R}w_{i}}{\sum_{k}w_{k}}\big{\\}}$
tend to $0$ for any $\alpha\in[0,1]$.

Table 4 presents the example graphically. In detail, the example has
$n^{2}+m-1$ users and $m\geq 3$ resources:

  * •

Alice uses every resource with a ratio of $1$, except for the second resource
which she does not use.

  * •

There are $n^{2}$ copies of a user, Bob, where each uses the first resource
with a ratio of $1$, the second one with a ratio of $1-\frac{1}{n^{3}}$, and
does not want any other resource.

  * •

User $i$, for all $i\in[m-2]$, uses the second resource with a ratio of
$\frac{1}{n(m-2)}$, the $(i+2)$-th one with a ratio of $1$, and does not use
any other resources.

  * •

In epoch 1 the total available amount of every resource is $1$. On the other
epochs, $2,3,\ldots,m-1$, the total available amount for each resource is
$\frac{1}{n^{2}}$444We can make that assumption w.l.o.g. because we can split
the first epoch where there is $1$ amount of every resource into $n^{2}$
epochs where the available amount of every resource is $n^{-2}$ every round..

Users | Ratios for resources $1,\ldots,m$ | Epoch 1 | Epoch 2 | Epoch 3 | Epoch 4 | …
---|---|---|---|---|---|---
Alice | $1$ | $0$ | $1$ | $1$ | $1$ | … | $1$ | 0 | 0 | $\frac{1}{n^{2}+1}$ | $\frac{1}{n^{2}}$ | $\frac{1}{n^{2}}$ | $\frac{1}{n^{2}}$ | $\frac{1}{n^{2}}$ | $\frac{1}{2n^{2}}$ | $\frac{1}{n^{2}}$ | $\frac{1}{n^{2}}$ | $\frac{1}{4n^{2}}$ | $\frac{1}{n^{2}}$ | …
$n^{2}$ Bobs | $1$ | $1-\frac{1}{n^{3}}$ | $0$ | $0$ | $0$ | … | $0$ | 1 | $\frac{1}{n^{2}}$ | $\frac{1}{n^{2}+1}$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | …
User $1$ | $0$ | $\frac{1}{n(m-2)}$ | $1$ | $0$ | $0$ | … | $0$ | 1 | $\frac{1}{n^{2}}$ | $\frac{n+1}{n^{2}+1}$ | $\frac{1}{n^{2}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | …
User $2$ | $0$ | $\frac{1}{n(m-2)}$ | $0$ | $1$ | $0$ | … | $0$ | 1 | $\frac{1}{n^{2}}$ | $\frac{n+1}{n^{2}+1}$ | 0 | 0 | 0 | $\frac{1}{n^{2}}$ | $\frac{1}{2n^{2}}$ | 0 | 0 | 0 | 0 | …
User $3$ | $0$ | $\frac{1}{n(m-2)}$ | $0$ | $0$ | $1$ | … | $0$ | 1 | $\frac{1}{n^{2}}$ | $\frac{n+1}{n^{2}+1}$ | 0 | 0 | 0 | 0 | 0 | 0 | $\frac{1}{n^{2}}$ | $\frac{3}{4n^{2}}$ | 0 | …
… | … | … | … | … | … | … | … | … | … | … | … | … | … | … | … | … | … | … | … | …
User $m-2$ | $0$ | $\frac{1}{n(m-2)}$ | $0$ | $0$ | $0$ | … | $1$ | 1 | $\frac{1}{n^{2}}$ | $\frac{n+1}{n^{2}+1}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | …
Table 4: For every epoch the black numbers denote the users’ demands, the blue
numbers are the users’ allocation when Alice is truthful, and the red numbers
are the allocations when Alice over-reports her demand in epoch 1 by asking
for 1 resource. The available amount of every resource in epoch 1 is 1, while
on the other epochs it is $\frac{1}{n^{2}}$.

If Alice lies on the first epoch and requests resources instead of requesting
zero, she can take resources from every Bob, which increases the allocation of
the other users by a factor of $\Theta(n)$. This entails that in epochs $2$,
$3$, …, $m-1$, instead of Alice getting allocated $\frac{1}{n^{2}}$,
$\frac{1}{2n^{2}}$, …, $\frac{1}{2^{m-3}n^{2}}$, respectively, she gets
$\frac{1}{n^{2}}$ every round. Note that this is true if the following
inequality is true, which guarantees that when Alice is untruthful the
resulting allocation in epochs $2$ to $m-1$ is max-min fair:

$\frac{1}{n^{2}+1}+\frac{m-2}{n^{2}}\leq\frac{n+1}{n^{2}+1}$

which is true if $m\leq 2+\frac{n^{3}}{n^{2}+1}$. This allows us to set
$m=\Theta(n)$. In total, Alice gets an allocation of
$\frac{2}{n^{2}}\left(1-\frac{1}{2^{m-2}}\right)\leq\frac{2}{n^{2}}$ if she is
truthful and a (useful) allocation of $\frac{m-2}{n^{2}}$ if she is
untruthful, i.e., she increases her utility by a factor of at least
$\frac{m-2}{2}$. This proves the theorem. ∎

###  B.2 Deferred Proofs of Section 4.1

First we restate and prove Lemma 4.2.

See 4.2

###### Proof.

We notice that

  * •

Because $\hat{r}_{i}^{t}>g(\hat{d}_{i}^{t})$ (since
$\hat{r}_{i}^{t}>\bar{r}_{i}^{t}\geq g(\bar{d}_{i}^{t})\geq
g(\hat{d}_{i}^{t})$) and $\hat{a}_{jq}^{t}>0$ for all $q$, decreasing
$\hat{r}_{i}^{t}$ would free a positive amount of every resource.

  * •

Because $\hat{r}_{j}^{t}<\hat{d}_{j}^{t}$ it is feasible to increase
$\hat{r}_{j}^{t}$ in order to increase $\hat{R}_{j}^{t}$.

This implies that $\hat{R}_{i}^{t}/w_{i}\leq\hat{R}_{j}^{t}/w_{j}$; otherwise
it would have been more fair to give some of the resources user $i$ got to
user $j$. With the analogous inverse argument (we can increase
$\bar{r}_{i}^{t}$ by decreasing $\bar{r}_{j}^{t}$) we can prove that
$\bar{R}_{i}^{t}/w_{i}\geq\bar{R}_{j}^{t}/w_{j}$. This completes the proof. ∎

Finally we prove the lower bound for the incentive compatibility ratio of
Dynamic DRF.

See 4.7

###### Proof.

We are going to prove the theorem for $\alpha=0$. We can make the assumption
that $\alpha=0$ without loss of generality because for a fixed $\mathcal{R}$
we can add users with zero demands and same ratios and weights as some user
other that user $1$ (thus not affecting the allocation nor the definition of
$\rho_{1}$) to make the guarantee
$g(d_{i}^{t})=\min\big{\\{}d_{i}^{t},\alpha\frac{\mathcal{R}w_{i}}{\sum_{k}w_{k}}\big{\\}}$
tend to $0$ for any $\alpha\in[0,1]$.

There are $2$ epochs, $2$ resources, and $4$ groups of users where the users
in each group have the same ratios and demands. Groups $1$ and $2$ have one
user each, user $1$ and user $2$ respectively, while groups $3$ and $4$ have
$n_{1}$ and $n_{2}$ users, respectively.

User $1$ is the one who will under-report her demand to increase her utility
and w.l.o.g. we assume that her weight is $w_{1}=1$. All other users have
weight $w>0$ (this corresponds to the weight $w_{2}$ in the theorem’s
statement). Their ratios are depicted in Table 5, along with a summary of the
whole example. We assume that $\delta$ and $\epsilon$ are fixed. We note that

$\rho_{1}\;=\;\max_{k\neq
1,q}\frac{w_{1}a_{1q}}{w_{k}a_{kq}}\;=\;\max\left\\{\frac{1}{w\epsilon},\frac{1}{w},\frac{1}{w\epsilon},\frac{\delta}{w},\frac{\delta}{w\epsilon},\frac{\delta}{w}\right\\}\;=\;\frac{1}{w\epsilon}$

as needed by the theorem.

| Res. 1 | Res. 2 | Ep. 1 $\Big{(}\mathcal{R}^{1}=1+\frac{n_{1}w}{1+w\epsilon}\Big{)}$ | Ep. 2 $\Big{(}\mathcal{R}^{2}=\frac{\delta}{w\epsilon}+\frac{n_{2}\delta}{\epsilon(w+\delta)}\Big{)}$
---|---|---|---|---
User $1$ ($w_{1}=1$) | $1$ | $\delta$ | $\infty$ | $\frac{1}{1+w\epsilon}$ | $0$ | $\infty$ | $\frac{\delta}{w\epsilon(w+\delta)}$ | $\frac{1}{w\epsilon}$
User $2$ ($w_{2}=w$) | $\epsilon$ | $1$ | $\infty$ | $\frac{w}{1+w\epsilon}$ | $\frac{1}{\epsilon}$ | $\infty$ | $\frac{\delta}{\epsilon(w+\delta)}$ | $0$
Group $3$ ($n_{1}$ users, $w_{3}=w$) | $1$ | $\epsilon$ | $\frac{w}{1+w\epsilon}$ | $\frac{w}{1+w\epsilon}$ | $\frac{w}{1+w\epsilon}$ | $0$ | $0$ | $0$
Group $4$ ($n_{2}$ users, $w_{4}=w$) | $\epsilon$ | $1$ | $0$ | $0$ | $0$ | $\frac{\delta}{\epsilon(w+\delta)}$ | $\frac{\delta}{\epsilon(w+\delta)}$ | $\frac{\delta}{\epsilon(w+\delta)}$
Table 5: Summary of the example of Theorem 4.7. The 2nd and 3rd columns depict
the users’ ratios, where $0<\delta\leq\epsilon<1$. The last two columns for
each epoch show the total available resources for that round in the
parentheses of the first row, the demands of each group (black numbers), their
allocations when the user in group $1$ is truthful (blue numbers), and their
allocations when the user in group $1$ misreports a demand of $0$ in epoch $1$
(red numbers).

Epoch 1. In the first epoch, users $1$ and $2$ demand $\infty$ resources,
group $3$ demand $\frac{w}{1+w\epsilon}$, and group $4$ demand $0$. The total
amount available for every resource is $1+\frac{n_{1}w}{1+w\epsilon}$.

We first show that with these demands, user $1$ gets
$r_{1}^{1}=\frac{1}{1+w\epsilon}$, while user $2$ and users in group $3$ get
an allocation of $\frac{w}{1+w\epsilon}$. Note that this is fair, since every
user with positive demand gets an allocation proportional to their weight.
Because this allocation is fair, to prove its validity we need that one
resource is saturated and the other is not over-used. The total amount of
resource $1$ used is

$\frac{1}{1+w\epsilon}+\epsilon\frac{w}{1+w\epsilon}+n_{1}\frac{w}{1+w\epsilon}=1+\frac{n_{1}w}{1+w\epsilon}\;=\;\mathcal{R}^{1}$

meaning that resource $1$ is saturated, proving that we cannot increase the
users’ allocations. The total amount of resource $2$ used is

$\delta\frac{1}{1+w\epsilon}+\frac{w}{1+w\epsilon}+n_{1}\epsilon\frac{w}{1+w\epsilon}\;=\;\frac{\delta+w}{1+w\epsilon}+n_{1}\frac{w\epsilon}{1+w\epsilon}\;\leq\;1+n_{1}\frac{w}{1+w\epsilon}\;=\;\mathcal{R}^{1}$

where the inequality holds because $\epsilon<1$ and we assume that $n_{1}$ is
large enough. This proves that we do not over-use resource $2$.

Now we will prove that if the user in group $1$ misreports her demand and asks
for $0$ instead, then the allocations are as follows: user $1$ gets
$\hat{r}_{1}^{1}=0$, user $2$ gets an allocation of $\frac{1}{\epsilon}$ and
users in group $3$ get an allocation of $\frac{w}{1+w\epsilon}$. Note that
this is fair, since they have the same weight and users in group $3$ get their
demand, while user $2$ gets more than. The total amount of resource $1$ used
is

$0+\epsilon\frac{1}{\epsilon}+n_{1}\frac{w}{1+w\epsilon}=1+\frac{n_{1}w}{1+w\epsilon}\;=\;\mathcal{R}^{1}$

meaning that resource $1$ is saturated, proving that we cannot increase the
users’ allocations. The total amount of resource $2$ used is

$0+\frac{1}{\epsilon}+n_{1}\epsilon\frac{w}{1+w\epsilon}\leq
1+n_{1}\frac{w}{1+w\epsilon}\;=\;\mathcal{R}^{1}$

where the inequality holds because $\epsilon<1$ and we assume that $n_{1}$ is
large enough. This proves that we do not over-use resource $2$.

Epoch 2. In the second epoch, users $1$ and $2$ demand $\infty$ resources,
group $3$ demand $0$, and group $4$ demand
$\frac{w\delta}{\epsilon(w+\delta)}$. The total amount available for every
resource is
$\frac{\delta}{w\epsilon}+\frac{n_{2}\,\delta}{\epsilon(w+\delta)}$.

We first show that with these demands, when user $1$ was truthful, user $1$
gets $r_{1}^{2}=\frac{\delta}{w\epsilon(w+\delta)}$, while user $2$ and users
in group $4$ get an allocation of $\frac{\delta}{\epsilon(w+\delta)}$. Note
that this is fair, since user $2$’s total allocation is the same as user $1$’s
times $w$ and users in group $4$ get their demand which is less than the total
allocation of user $2$ with which they have the same weight. The total amount
of resource $1$ used is

$\frac{\delta}{w\epsilon(w+\delta)}+\epsilon\frac{\delta}{\epsilon(w+\delta)}+n_{2}\epsilon\frac{\delta}{\epsilon(w+\delta)}\;\leq\;\frac{\delta}{w\epsilon}+n_{2}\frac{\delta}{\epsilon(w+\delta)}\;=\;\mathcal{R}^{2}$

where the inequality holds because $\epsilon<1$ and by assuming that $n_{2}$
is large enough. This proves that resource $1$ is not over-used. The total
amount of resource $2$ used is

$\delta\frac{\delta}{w\epsilon(w+\delta)}+\frac{\delta}{\epsilon(w+\delta)}+n_{2}\frac{\delta}{\epsilon(w+\delta)}\;=\;\frac{\delta}{w\epsilon}+n_{2}\frac{\delta}{\epsilon(w+\delta)}\;=\;\mathcal{R}^{2}$

meaning that resource $1$ is saturated, proving that we cannot increase the
users’ allocations.

Now we will prove that when the user $1$ misreported in the first epoch, the
allocations are as follows: user $1$ gets
$\hat{r}_{1}^{2}=\frac{1}{w\epsilon}$, user $2$ gets $0$, and group $4$ gets
$\frac{\delta}{\epsilon(w+\delta)}$. Note that this is fair; the total
resource of user $1$ and user $2$ are now $\frac{1}{w\epsilon}$ and
$\frac{1}{\epsilon}$ (which are proportional to users’ weights) and users in
group $4$ get their demand which is not more than what user $2$ gets in total
who has the same weight. The total amount of resource $1$ used is

$\frac{1}{w\epsilon}+\epsilon\,0+n_{2}\epsilon\frac{\delta}{\epsilon(w+\delta)}\;\leq\;\frac{\delta}{w\epsilon}+n_{2}\frac{\delta}{\epsilon(1+\delta)}\;=\;\mathcal{R}^{2}$

where the inequality holds because $\epsilon<1$ and by assuming that $n_{2}$
is large enough. This proves that resource $1$ is not over-used. The total
amount of resource $2$ used is

$\delta\frac{1}{w\epsilon}+0+n_{2}\frac{\delta}{\epsilon(w+\delta)}\;=\;\frac{\delta}{w\epsilon}+n_{2}\frac{\delta}{\epsilon(w+\delta)}\;=\;\mathcal{R}^{2}$

meaning that resource $1$ is saturated, proving that we cannot increase the
users’ allocations.

This proves that the misreporting of user $1$ increases her resources by

$\frac{\hat{r}_{1}^{1}+\hat{r}_{1}^{2}}{r_{1}^{1}+r_{1}^{2}}\;=\;\frac{0+\frac{1}{w\epsilon}}{\frac{1}{1+w\epsilon}+\frac{\delta}{w\epsilon(w+\delta)}}\;\overset{\delta\to
0}{\to}\;1+\frac{1}{w\epsilon}\;=\;1+\rho_{1}$ (18)

the above proves that as $\delta\to 0$ we get an incentive compatibility ratio
of $1+\rho_{1}$, as needed. ∎

It is worth pointing out what we mentioned in Section 4: if we want a lower
bound that depends on $\rho=\max_{i}\rho_{i}$ instead of $\rho_{1}$, we get an
interesting result when $w=1$: if we set $\delta=\epsilon$, making
$\rho=1/\epsilon$, (18) now proves an incentive compatibility bound of
$\frac{1+1/\epsilon}{2}=\frac{1+\rho}{2}$.

##  Appendix C Deferred Proofs of Section 5.1

First we state a more specific version of Lemma 4.2.

######  Lemma C.1.

Fix an epoch $t$ and the allocations of two different outcomes
$\\{\hat{R}_{k}^{t-1}\\}_{k\in[n]}$ and $\\{\bar{R}_{k}^{t-1}\\}_{k\in[n]}$.
Let $i,j$ be two different users. If the following conditions hold

  * •

For $i$, $\;\bar{r}_{i}^{t}<\hat{r}_{i}^{t}$ and
$\;\hat{d}_{i}^{t}\leq\bar{d}_{i}^{t}$.

  * •

For $j$, $\;\bar{r}_{j}^{t}>\hat{r}_{j}^{t}$ and
$\;\bar{d}_{j}^{t}\leq\hat{d}_{j}^{t}$.

then, for any $\alpha\in[0,1]$,

$\frac{\bar{R}_{i}^{t}}{w_{i}}\geq\frac{\bar{R}_{j}^{t}}{w_{j}}\;\;\;\textrm{
and }\;\;\;\frac{\hat{R}_{i}^{t}}{w_{i}}\leq\frac{\hat{R}_{j}^{t}}{w_{j}}$

and consequentially

$\frac{\hat{R}_{i}^{t}-\bar{R}_{i}^{t}}{w_{i}}\leq\frac{\hat{R}_{j}^{t}-\bar{R}_{j}^{t}}{w_{j}}$
(19)

Next we generalize Lemma 3.4. Note that this is much different and stronger
than what is stated in Lemma 4.3; even without the assumption that users
collude Lemma 4.3 proves that in Dynamic weighted MMF, for all $i,t$:

$\hat{R}_{i}^{t}-\bar{R}_{i}^{t}\leq\bar{R}_{1}^{t}\max_{k}\frac{w_{i}}{w_{k}}$

######  Lemma C.2.

Fix an epoch $t$ and the allocations of two different outcomes
$\\{\hat{R}_{k}^{t-1}\\}_{k\in[n]}$ and $\\{\bar{R}_{k}^{t-1}\\}_{k\in[n]}$.
Assume that $\\{\bar{d}_{i}^{t}\\}_{i\in[n]}$ are some users’ demands and that
$\\{\hat{d}_{i}^{t}\\}_{i\in[n]}$ are the same demands except users in $I$,
who deviate but not by over-reporting, i.e.,
$\hat{d}_{i}^{t}\leq\bar{d}_{i}^{t}$ for $i\in I$. Then, for any
$\alpha\in[0,1]$, it holds that

$\sum_{k\in[n]}\left(\hat{R}_{k}^{t}-\bar{R}_{k}^{t}\right)^{+}-\sum_{k\in[n]}\left(\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1}\right)^{+}\leq\mathbbm{1}\left[\sum_{k\in
I}\hat{d}_{k}^{t}<\sum_{k\in I}\bar{d}_{k}^{t}\right]\sum_{k\in
I}\bar{r}_{k}^{t}$ (20)

###### Proof.

First we define $P^{t}=\\{k\in[n]:\hat{R}_{k}^{t}>\bar{R}_{k}^{t}\\}$ for all
$t$. Suppose by contradiction:

$\sum_{k\in P^{t}}\left(\hat{R}_{k}^{t}-\bar{R}_{k}^{t}\right)-\sum_{k\in
P^{t-1}}\left(\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1}\right)>\mathbbm{1}\left[\sum_{k\in
I}\hat{d}_{k}^{t}<\sum_{k\in I}\bar{d}_{k}^{t}\right]\sum_{k\in
I}\bar{r}_{k}^{t}$

Because $\sum_{k\in P^{t}}(\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1})\leq\sum_{k\in
P^{t-1}}(\hat{R}_{k}^{t-1}-\bar{R}_{k}^{t-1})$, the above inequality implies

$\sum_{k\in
P^{t}}\left(\hat{r}_{k}^{t}-\bar{r}_{k}^{t}\right)>\mathbbm{1}\left[\sum_{k\in
I}\hat{d}_{k}^{t}<\sum_{k\in I}\bar{d}_{k}^{t}\right]\sum_{k\in
I}\bar{r}_{k}^{t}$ (21)

Because users only under-report their demand,
$\hat{d}_{k}^{t}\leq\bar{d}_{k}^{t}$, it holds that
$\sum_{k}\bar{r}_{i}^{t}\geq\sum_{k}\hat{r}_{i}^{t}$, i.e., the total
resources allocated to the users does not increase when user $1$ deviates.
Combining this fact with (21) we get that

$\sum_{k\notin
P^{t}}\left(\bar{r}_{k}^{t}-\hat{r}_{k}^{t}\right)>\mathbbm{1}\left[\sum_{k\in
I}\hat{d}_{k}^{t}<\sum_{k\in I}\bar{d}_{k}^{t}\right]\sum_{k\in
I}\bar{r}_{k}^{t}$ (22)

We notice that because of (21), there exists a user $i\in P^{t}$ for whom
$\hat{r}_{i}^{t}>\bar{r}_{i}^{t}$; because of (22), there exists a user
$j\notin P^{t}$ for whom $\bar{r}_{j}^{t}>\hat{r}_{j}^{t}$. Additionally for
that $j$ we can assume that $\hat{d}_{j}^{t}=\bar{d}_{j}^{t}$ because:

  * •

If users in $I$ do not deviate then for all $k$,
$\hat{d}_{k}^{t}=\bar{d}_{k}^{t}$.

  * •

If $\sum_{k\in I}\hat{d}_{k}^{t}<\sum_{k\in I}\bar{d}_{k}^{t}$, then (22)
implies $\sum_{k\notin P^{t}\cup
I}\left(\bar{r}_{k}^{t}-\hat{r}_{k}^{t}\right)>0$, i.e., $j\notin I$ and we
assumed that only users in $I$ deviate.

Thus we have $\hat{d}_{i}^{t}\leq\bar{d}_{i}^{t}$ (since no user over-
reports), $\hat{d}_{j}^{t}=\bar{d}_{j}^{t}$,
$\hat{r}_{i}^{t}>\bar{r}_{i}^{t}$, and $\hat{r}_{j}^{t}<\bar{r}_{j}^{t}$. Now
Lemma C.1 proves that
$(\hat{R}_{i}^{t}-\bar{R}_{i}^{t})/w_{i}\leq(\hat{R}_{j}^{t}-\bar{R}_{j}^{t})/w_{j}$.
This leads to a contradiction, because $i\in P^{t}$ and $j\notin P^{t}$, i.e.,
$\hat{R}_{i}^{t}-\bar{R}_{i}^{t}>0\geq\hat{R}_{j}^{t}-\bar{R}_{j}^{t}$. ∎

Next we prove that users do not want to over-report their demand.

See 5.2

Similar to Theorem 3.5, we first prove an auxiliary lemma.

######  Lemma C.3.

Fix an epoch $T_{0}$ and the allocations of an outcome
$\\{\hat{R}_{k}^{T_{0}-1}\\}_{k\in[n]}$. Fix another epoch $T\geq T_{0}$ and
assume that in epochs $T_{0}+1,T_{0}+2,\ldots,T$ users in $I$ do not over-
report their demand. Then, for any $\alpha\in[0,1]$, the users in $I$ cannot
increase their utility in round $T$ by over-reporting their demand in epoch
$T_{0}$.

###### Proof.

To prove the lemma we are going to create another outcome in which the over-
reports in epoch $T_{0}$ are changed to a truthful ones and prove that this
does not decrease $I$’s total utility in epoch $T$.

For all $k,t$, let $\bar{d}_{k}^{t}=\hat{d}_{k}^{t}$, except for epoch $T_{0}$
and users $i\in I$, where $\bar{d}_{i}^{T_{0}}$ are the actual demands if they
were over-reports:
$\bar{d}_{i}^{T_{0}}=\min\\{d_{i}^{T_{0}},\hat{d}_{i}^{T_{0}}\\}$ for $i\in
I$. This means that the two outcomes are the same before epoch $T_{0}$, i.e.,
for all $k$, $\bar{R}_{k}^{T_{0}-1}=\hat{R}_{k}^{T_{0}-1}$ and
$\bar{U}_{k}^{T_{0}-1}=\hat{U}_{k}^{T_{0}-1}$. In epoch $T_{0}$ users’
allocations are different. First, let $I^{\prime}\subseteq I$ be the users who
over-report their demand in $T_{0}$, i.e., the users $i$ for whom
$\bar{d}_{i}^{T_{0}}=d_{i}^{T_{0}}<\hat{d}_{i}^{T_{0}}$. Now we prove that for
any user $i$ who got more resources,
$\hat{r}_{i}^{T_{0}}>\bar{r}_{i}^{T_{0}}$, that user must be in $I^{\prime}$
and that additional resources must be in excess of their true demand:

$\textrm{if
}\;\hat{r}_{i}^{T_{0}}-\bar{r}_{i}^{T_{0}}=\hat{R}_{i}^{T_{0}}-\bar{R}_{i}^{T_{0}}>0\;\textrm{
then }\;\bar{r}_{i}^{T_{0}}=\bar{d}_{i}^{\,T_{0}}\;\textrm{ and }\;i\in
I^{\prime}$ (23)

To prove (23) we study two cases:

  * •

If
$\hat{r}_{i}^{T_{0}}-\bar{r}_{i}^{T_{0}}=\hat{R}_{i}^{T_{0}}-\bar{R}_{i}^{T_{0}}>0$
and $\bar{r}_{i}^{T_{0}}<\bar{d}_{i}^{\,T_{0}}$, then
$\hat{r}_{i}^{T_{0}}<\hat{d}_{i}^{T_{0}}$. This means user $i$’s demands are
not satisfied both in $\hat{d}^{T_{0}}$ and $\bar{d}^{T_{0}}$, which implies
that, since $\hat{r}_{i}^{T_{0}}>\bar{r}_{i}^{T_{0}}$ and for all users $k$,
$\bar{d}_{k}^{T_{0}}\leq\hat{d}_{k}^{T_{0}}$, for some other user $j$,
$\hat{r}_{j}^{T_{0}}-\bar{r}_{j}^{T_{0}}=\hat{R}_{j}^{T_{0}}-\bar{R}_{j}^{T_{0}}<0$.
This, because of Lemma C.1 and $\bar{d}_{j}^{T_{0}}\leq\hat{d}_{j}^{\,T_{0}}$,
entails that
$(\hat{R}_{i}^{T_{0}}-\bar{R}_{i}^{T_{0}})/w_{i}\leq(\hat{R}_{j}^{T_{0}}-\bar{R}_{j}^{T_{0}})/w_{j}$,
a contradiction.

  * •

If
$\hat{r}_{i}^{T_{0}}-\bar{r}_{i}^{T_{0}}=\hat{R}_{i}^{T_{0}}-\bar{R}_{i}^{T_{0}}>0$
and $i\notin I^{\prime}$, then, because user $i$ got more resources in
$\hat{d}^{T_{0}}$ with the same demand, for some user $j$,
$\hat{r}_{j}^{T_{0}}-\bar{r}_{j}^{T_{0}}=\hat{R}_{j}^{T_{0}}-\bar{R}_{j}^{T_{0}}<0$,
which because of Lemma C.1, $\bar{d}_{i}^{T_{0}}=\hat{d}_{i}^{T_{0}}$, and
$\bar{d}_{j}^{\,T_{0}}\leq\hat{d}_{j}^{T_{0}}$ entails that
$(\hat{R}_{i}^{T_{0}}-\bar{R}_{i}^{T_{0}})/w_{i}\leq(\hat{R}_{j}^{T_{0}}-\bar{R}_{j}^{T_{0}})/w_{j}$,
a contradiction.

Because of (23) we see that any additional resources that users in $I$ get in
$T_{0}$ when they over-report are in excess of their demand (because for $i\in
I^{\prime}$, $\bar{d}_{i}^{\,T_{0}}$ is the true demand). This means that
$\sum_{i\in I}(\hat{R}_{i}^{T_{0}}-\bar{R}_{i}^{T_{0}})^{+}=x\geq 0$ is in
excess of their demand and therefore

$\sum_{i\in I}\left(\hat{U}_{i}^{T_{0}}-\bar{U}_{i}^{T_{0}}\right)=\sum_{i\in
I}\left(\hat{R}_{i}^{T_{0}}-\bar{R}_{i}^{T_{0}}\right)-x\leq 0$ (24)

Additionally, because users in $I$ do not over-report $\hat{d}$ or $\bar{d}$
in epochs $T_{0}+1$ to $T$, it holds that for $t\in[T_{0}+1,T]$ $I$’ utility
is the same as the resources they receives: $\bar{u}_{i}^{t}=\bar{r}_{i}^{t}$
and $\hat{u}_{i}^{t}=\hat{r}_{i}^{t}$ for $i\in I$. This fact, combined with
(24) proves that

$\forall t\in[T_{0},T],\;\sum_{i\in
I}\left(\hat{U}_{i}^{t}-\bar{U}_{i}^{t}\right)=\sum_{i\in
I}\left(\hat{R}_{i}^{t}-\bar{R}_{i}^{t}\right)-x$

Thus, in order for this over-reporting to be a strictly better strategy, it
most hold that $\sum_{i\in I}(\hat{R}_{i}^{t}-\bar{R}_{i}^{t})>x$. We will
complete the proof by proving that the opposite holds. Since in epochs
$t\in[T_{0}+1,T]$ it holds that $\hat{d}_{i}^{t}=\bar{d}_{i}^{t}$ for $i\in
I$, we can use Lemma C.2 to sum (20) for all $t\in[T_{0}+1,T]$ and get that

$\sum_{k}\left(\hat{R}_{k}^{T}-\bar{R}_{k}^{T}\right)^{+}-\sum_{k}\left(\hat{R}_{k}^{T_{0}}-\bar{R}_{k}^{T_{0}}\right)^{+}\leq
0$

The above, because $(\hat{R}_{k}^{T}-\bar{R}_{k}^{T})^{+}\geq 0$,
$\hat{R}_{k}^{T_{0}}-\bar{R}_{k}^{T_{0}}\leq 0$ for $k\notin I$ (from (23)),
and $\sum_{i\in I}(\hat{R}_{i}^{T_{0}}-\bar{R}_{i}^{T_{0}})^{+}=x$, proves
that $\sum_{i\in I}(\hat{R}_{i}^{T}-\bar{R}_{i}^{T})\leq x$. This completes
the proof. ∎

Now Theorem 5.2 can be viewed as a corollary of the above lemma. Finally, we
prove the inventive compatibility bound for adversarial demands.

See 5.3

###### Proof.

Because of Theorem 5.2 we assume without loss of generality that users do not
over-report their demand. This entails that we can focus on the users’
allocations instead of their utilities.

Fix an epoch $t$ and let $T\leq t$ be the last time where $\sum_{i\in
I}\hat{r}_{i}^{t}>\sum_{i\in I}r_{i}^{t}$. We notice that

$\sum_{i\in I}\left(\hat{R}_{i}^{t}-R_{i}^{t}\right)\;=\;\sum_{i\in
I}\left(\hat{R}_{i}^{T}-R_{i}^{T}\right)+\sum_{\tau=T+1}^{t}\sum_{i\in
I}\left(\hat{r}_{i}^{T}-r_{i}^{T}\right)\;\leq\;\sum_{i\in
I}\left(\hat{R}_{i}^{T}-R_{i}^{T}\right)$ (25)

Because $\sum_{k\in I}\hat{r}_{k}^{T}>\sum_{k\in I}r_{k}^{T}$ and
$\sum_{k\in[n]}\hat{r}_{k}^{T}\leq\sum_{k\in[n]}r_{k}^{T}$ (since users do not
over-report their demand) there must exist a $i\in I$ such that
$\hat{r}_{i}^{T}>r_{i}^{T}$ and a $j\notin I$ such that
$\hat{r}_{j}^{T}<r_{j}^{T}$. Because $\hat{d}_{i}^{T}\leq d_{i}^{T}$ and
$\hat{d}_{j}^{T}=d_{j}^{T}$ we can use Lemma C.2 to get

$\frac{w_{j}}{w_{i}}\left(\hat{R}_{i}^{T}-R_{i}^{T}\right)\leq\hat{R}_{j}^{T}-R_{j}^{T}$
(26)

If we use Lemma C.2 and sum (20) for epochs up to $T$ we get

$\sum_{k\in[n]}(\hat{R}_{k}^{T}-R_{k}^{T})^{+}\leq\sum_{k\in I}R_{k}^{T}$

which combined with (26) gives

$\frac{w_{j}}{w_{i}}\left(\hat{R}_{i}^{T}-R_{i}^{T}\right)^{+}+\sum_{k\in
I}(\hat{R}_{k}^{T}-R_{k}^{T})\leq\sum_{k\in I}R_{k}^{T}\overset{t\geq
T}{\underset{}{\leq}}\sum_{k\in I}R_{k}^{t}$ (27)

(25) and (27) prove that $\sum_{k\in I}\hat{R}_{k}^{t}\leq 2\sum_{k\in
I}R_{k}^{t}$, which proves the first part of the lemma.

If $|I|=1$, then $I=\\{i\\}$ where $i$ is the user appearing in (27). If
$\hat{R}_{i}^{T}-R_{i}^{T}<0$ the desired bound is true; otherwise, (25) and
(27) prove that

$\min_{j\neq
i}\frac{w_{i}}{w_{j}}\left(\hat{R}_{i}^{t}-R_{i}^{t}\right)+\hat{R}_{i}^{t}-R_{i}^{t}\leq
R_{i}^{t}$

which proves the desired bound: $\hat{R}_{i}^{t}\leq\left(1+\max_{j\neq
i}\frac{w_{i}}{w_{i}+w_{j}}\right)R_{i}^{t}$. ∎

##  Appendix D Deferred Proof of Section 5.2

We first prove a more general version of Lemma 3.4.

######  Lemma D.1.

Fix an epoch $t$ and the allocations of two different outcomes
$\\{\hat{R}_{k}^{t-1}\\}_{k\in[n]}$ and $\\{\bar{R}_{k}^{t-1}\\}_{k\in[n]}$.
Assume that $\\{\bar{d}_{k}^{t}\\}_{k\in[n]}$ are some users’ demands and that
$\\{\hat{d}_{k}^{t}\\}_{k\in[n]}$ are the same demands except user $1$’s, who
deviates but not by over-reporting, i.e.,
$\hat{d}_{1}^{t}\leq\bar{d}_{1}^{t}$. Then, in Dynamic MMF for any
$\alpha\in[0,1]$, it holds that

$\sum_{k\in[n]}\left(\hat{R}_{k}^{t}-R_{k}^{t}\right)^{+}-\sum_{k\in[n]}\left(\hat{R}_{k}^{t-1}-R_{k}^{t-1}\right)^{+}\leq
f^{t}$ (28)

where
$f^{t}=\min\left((r_{1}^{t}-\hat{r}_{1}^{t})^{+},\,(R_{1}^{t}-\hat{R}_{1}^{t})^{+}\right)$.

###### Proof.

Let $P^{t}=\\{k:\hat{R}_{k}^{t}>R_{k}^{t}\\}$ and suppose by contradiction
that

$\sum_{k\in P^{t}}\left(\hat{R}_{k}^{t}-R_{k}^{t}\right)^{+}-\sum_{k\in
P^{t-1}}\left(\hat{R}_{k}^{t-1}-R_{k}^{t-1}\right)^{+}>f^{t}$ (29)

In order to get a contradiction we are going to show that the following two
conditions are implied by (29):

  1. (I)

There exists a user $i\in P^{t}$, such that $\hat{r}_{i}^{t}>r_{i}^{t}$.

  2. (II)

There exists a user $j\notin P^{t}$, such that $j\neq 1$ and
$\hat{r}_{j}^{t}<r_{j}^{t}$.

The reason conditions (I) and (II) lead to a contradiction is the following:
users $i$ and $j$ satisfy the conditions of Lemma 3.3, meaning that
$\hat{R}_{i}^{t}-R_{i}^{t}\leq\hat{R}_{j}^{t}-R_{j}^{t}$. However this is a
contradiction due to the facts that $i\in P^{t}$ and $j\notin P^{t}$

To prove that (29) implies conditions (I) and (II), we will now distinguish
two cases; these are shown in Propositions D.2 and D.3.

######  Proposition D.2.

If $\hat{r}_{1}^{t}\geq r_{1}^{t}$ or $\hat{R}_{1}^{t}\geq R_{1}^{t}$, (29)
implies conditions (I) and (II).

###### Proof of Proposition D.2.

In this case we have that $f^{t}=0$. Because of the definition of $P^{t}$, we
can re-write (29)

$\sum_{k\in P^{t}}\hat{r}_{k}^{t}-r_{k}^{t}>0$ (30)

(30) implies (I). (30) and the fact that
$\sum_{k}r_{k}^{t}\geq\sum_{k}\hat{r}_{k}^{t}$ (which comes from user $1$ not
over-reporting her demand) prove that

$\sum_{k\notin P^{t}}r_{k}^{t}-\hat{r}_{k}^{t}>0$

The above implies condition (II): there exists a $j\notin P^{t}$ such that
$\hat{r}_{j}^{t}<r_{j}^{t}$. The reason that the aforementioned $j$ cannot be
user $1$ is because of our assumptions: either $\hat{r}_{1}^{t}\geq r_{1}^{t}$
or $\hat{R}_{1}^{t}\geq R_{1}^{t}$. ∎

######  Proposition D.3.

If $\hat{r}_{1}^{t}<r_{1}^{t}$ and $\hat{R}_{1}^{t}<R_{1}^{t}$, (29) implies
conditions (I) and (II).

###### Proof of Proposition D.3.

Because $\hat{R}_{1}^{t}<R_{1}^{t}$, it holds that $1\notin P^{t}$. Consider
two cases:

  * •

If $\hat{R}_{1}^{t-1}<R_{1}^{t-1}$, then $f^{t}=r_{1}^{t}-\hat{r}_{1}^{t}$. In
this case (29) implies

$\sum_{k\in P^{t}}\hat{r}_{k}^{t}-r_{k}^{t}>r_{1}^{t}-\hat{r}_{1}^{t}>0$

  * •

If $\hat{R}_{1}^{t-1}\geq R_{1}^{t-1}$, then $f^{t}=R_{1}^{t}-\hat{R}_{1}^{t}$
and $1\in P^{t-1}$. In this case (29) implies

$\displaystyle\sum_{k\in
P^{t}}\left(\hat{R}_{k}^{t}-R_{k}^{t}\right)-\sum_{k\in
P^{t-1}}\left(\hat{R}_{k}^{t-1}-R_{k}^{t-1}\right)$ $\displaystyle>$
$\displaystyle R_{1}^{t}-\hat{R}_{1}^{t}$ $\displaystyle\sum_{k\in
P^{t}}\left(\hat{R}_{k}^{t}-R_{k}^{t}\right)-\sum_{k\in
P^{t-1}\setminus\\{1\\}}\left(\hat{R}_{k}^{t-1}-R_{k}^{t-1}\right)$
$\displaystyle>$ $\displaystyle r_{1}^{t}-\hat{r}_{1}^{t}$
$\displaystyle\sum_{k\in P^{t}}\hat{r}_{k}^{t}-r_{k}^{t}$ $\displaystyle>$
$\displaystyle r_{1}^{t}-\hat{r}_{1}^{t}>0$

where to get the last inequality we use the fact that $1\notin P^{t}$.

Thus in both cases the following inequality holds:

$\sum_{k\in P^{t}}\hat{r}_{k}^{t}-r_{k}^{t}>r_{1}^{t}-\hat{r}_{1}^{t}>0$ (31)

(31) implies (I). (31) and $\sum_{k}r_{k}^{t}\geq\sum_{k}\hat{r}_{k}^{t}$
(which is true because user $1$ does not over-report) prove that

$\displaystyle\sum_{k\notin P^{t}}r_{k}^{t}-\hat{r}_{k}^{t}$ $\displaystyle>$
$\displaystyle r_{1}^{t}-\hat{r}_{1}^{t}$
$\displaystyle\sum_{\begin{subarray}{c}k\notin P^{t}\\\ k\neq
1\end{subarray}}r_{k}^{t}-\hat{r}_{k}^{t}$ $\displaystyle>$ $\displaystyle 0$

The above implies condition (II), which completes the proposition’s proof. ∎

Due to Propositions D.2 and D.3 we have proven that (29) always leads to a
contradiction. This proves the lemma. ∎

We now use the above lemma to prove a corollary that directly bounds
$\hat{R}_{1}^{t}-R_{1}^{t}$.

######  Corollary D.4.

Let
$f^{t}=\min\left((r_{1}^{t}-\hat{r}_{1}^{t})^{+},\,(R_{1}^{t}-\hat{R}_{1}^{t})^{+}\right)$
and assume that user $1$ does not over-report her demand. Then, in Dynamic MMF
for any $\alpha\in[0,1]$ and every epoch $t$,

$2\left(\hat{R}_{1}^{t}-R_{1}^{t}\right)\leq\sum_{\tau=1}^{t}f^{\tau}$ (32)

###### Proof.