In spectrum sharing, a spatial separation region is defined around primary users (PUs) to protect them from secondary user (SU)-induced interference. This protection region---referred to by a number of names, such as an exclusion zone (EZ) or a protection zone (PZ)---has a static boundary, and this boundary is determined very conservatively to provide an additional margin of protection for the PUs. This legacy notion of interference protection is overly rigid, and often results in poor spectrum utilization efficiency. In this paper, we propose a novel framework for prescribing interference protection for the PUs that addresses some of the limitations of legacy EZs. Specifically, we introduce the concept of Multi-tiered Incumbent Protection Zones (MIPZ), and show that it can be used to dynamically adjust the PU's protection boundary based on the radio environment, network conditions, and the PU interference protection requirement. MIPZ can serve as an analytical framework for quantitatively analyzing a given PZ to gain insights on and determine the tradeoffs between interference protection and spectrum utilization efficiency. It allows a number of SUs, say N, to operate closer to the PU, and improves the overall spectrum utilization efficiency while ensuring a probabilistic guarantee of interference protection to the PU. We leverage the combined power of database-driven spectrum sharing and stochastic optimization theory for dynamically computing the zone boundary and the value of N. Using extensive simulation results, we demonstrate that the proposed framework improves spectrum utilization efficiency by adapting to the changing interference environment through dynamic adjustments of the zone boundary.