  Federated learning (FL) has emerged as a prevalent distributed machine
learning scheme that enables collaborative model training without aggregating
raw data. Cloud service providers further embrace Federated Learning as a
Service (FLaaS), allowing data analysts to execute their FL training pipelines
over differentially-protected data. Due to the intrinsic properties of
differential privacy, the enforced privacy level on data blocks can be viewed
as a privacy budget that requires careful scheduling to cater to diverse
training pipelines. Existing privacy budget scheduling studies prioritize
either efficiency or fairness individually. In this paper, we propose
DPBalance, a novel privacy budget scheduling mechanism that jointly optimizes
both efficiency and fairness. We first develop a comprehensive utility function
incorporating data analyst-level dominant shares and FL-specific performance
metrics. A sequential allocation mechanism is then designed using the Lagrange
multiplier method and effective greedy heuristics. We theoretically prove that
DPBalance satisfies Pareto Efficiency, Sharing Incentive, Envy-Freeness, and
Weak Strategy Proofness. We also theoretically prove the existence of a
fairness-efficiency tradeoff in privacy budgeting. Extensive experiments
demonstrate that DPBalance outperforms state-of-the-art solutions, achieving an
average efficiency improvement of $1.44\times \sim 3.49 \times$, and an average
fairness improvement of $1.37\times \sim 24.32 \times$.
