Cap-and-Penalize: Competitive Mechanisms for Multi-Phase Regularized Online Allocation

1 Introduction

Online allocation problems address the challenge of allocating limited resources to an online sequence of requests while maximizing social welfare or revenue and adhering to supply constraints. Compared to resource allocation in offline settings, online allocation problems introduce an additional layer of complexity, as decisions must be made without complete knowledge of future requests. Motivated by numerous high-stakes applications, online allocation problems have been extensively studied in computer science and operations research, with applications spanning Internet advertising [Mehta, 2013; Buchbinder et al., 2007], ride-sharing [Dickerson et al., 2021], electric vehicle charging [Guo et al., 2017; Gerding et al., 2011; Sun et al., 2018], and revenue management [Ball and Queyranne, 2009; Ma and SimchiLevi, 2020].

Despite extensive studies, the literature on online allocation problems predominantly focuses on optimizing objectives that are additive and separable. For instance, in the online knapsack problem [Chakrabarty et al., 2008], items arrive sequentially, each associated with a value and weight. The objective is to maximize the total value of packed items, which is separable among items and across different steps, while adhering to the knapsack's capacity constraint. However, in many real-world scenarios, decisionmakers must address non-separable objectives due to coupling effects, such as production costs [Tan et al., 2020c; Huang and Kim, 2015; Azar et al., 2016; Tan et al., 2025; Jazi et al., 2025], fairness among participants [Zargari et al., 2025; Balseiro et al., 2021], or regulatory constraints, such as load balancing [Balseiro et al., 2021], that inherently couple all participants throughout the allocation process. For example, [Tan et al., 2025] investigates an online allocation problem with convex production costs, where the objective is inherently non-separable. Similarly, [Balseiro et al., 2021] shows that fairness among participants can be achieved by incorporating a regularizer that is not separable over time into the objective function.

Motivated by practical applications such as the cap-and-tax carbon pricing policy implemented in countries like Canada [Government of Canada, 2025], this paper focuses on a novel regularized online allocation problem with a multi-phase, non-separable regularizer termed Cap-and-Penalize (CNP). The CNP regularizer incorporates a multi-phase cost model for resource provision and imposes a penalty when the total allocation exceeds a predetermined production level, referred to as the soft cap-the maximum production level allowed without incurring additional charges (i.e., the penalty-free region). Additionally, the CNP regularizer enforces a strict upper limit on total resource production, referred to as the hard cap, beyond which no further allocation is permitted. Our objective is to maximize social welfare, defined as the difference between the aggregate individual utilities (which are separable across agents) and the cost imposed by the non-separable CNP regularizer. Given the inherent trade-off between these two factors in the objective, we aim to identify the optimal balance between aggregate utility and regulatory costs.

Table 1: Comparison of our work with the existing literature on online allocation problems. The term "CRs" refers to competitive ratios, formally defined in Section 2.3. In [Balseiro et al., 2021], "asymptotic CRs" are defined under the assumption that the time horizon approaches infinity (i.e., T →∞), whereas all other competitive ratios, including the one in this paper, are defined without this assumption.

Papers	Value functions	Resource types	Resource constraints	Regularizer	Main Results
[Sun et al., 2021]	Concave	Divisible	✓	None	Near-optimal CRs
[Azar et al., 2016]	Linear	Divisible	✗	Non-Separable	Tight CRs
[Balseiro et al., 2021]	General	Divisible	✓	Non-Separable	Sub-linear regret; Asymptotic CR
[Ma et al., 2024]	General	Divisible	✓	Non-Separable	Optimal regret
[Tan et al., 2020c]	Linear	Indivisible	✓	Separable	Optimal CRs
[Tan et al., 2020a]	Linear	Indivisible	✓	Separable	Optimal CRs
This paper	Concave	Divisible	✗ ✓	Multi-Phase; Non-Separable Multi-Phase; Non-Separable	Optimal CRs Best-known CRs

1.1 Main Results, Techniques, and Insights

Our main results can be summarized as follows:

• We initiate the study of CNP-regularized online allocation with a multi-phase, non-separable regularizer. Unlike prior studies that focus on developing online mechanisms with sublinear regret over the time horizon, our work emphasizes competitive analysis, deriving the optimal online mechanism with the best-possible competitive ratio in the setting without resource constraints. Our upper-bound results build upon recent advancements in threshold-based algorithms and online primal-dual analysis. To establish the optimality of the proposed mechanism, we propose a novel representative function-based approach, transforming the proof of the lower bound into the search for key functions (we call them utilization functions) represented by an ordinary differential equation with two boundary conditions.
• We extend our optimal design to the more challenging setting with per-step resource constraints. The core of this extension lies in decoupling the non-separable, non-smooth regularizer across time slots, resulting in the design of a series of time-dependent marginal pricing functions. We theoretically prove that this online mechanism achieves a bounded competitive ratio in the general setting when the CNP regularizer is convex and further demonstrate that it provides a near-optimal guarantee in the linear case.

Our mechanisms belong to a family of online mechanisms known as posted price mechanisms (PPMs) [Einav et al., 2018; Parkes, 2007], where the supplier posts a price signal to sequentially arriving agents, allowing them to solve their own local utility-maximization problems. PPMs are incentive compatible [Nisan et al., 2007] and, more importantly, are typically easy to implement, logistically simple, and intuitive. As a result, they are widely used in practice for welfare and revenue maximization [Ferreira et al., 2021; Feldman et al., 2015; Tan et al., 2020b; Etzion et al., 2006; Tan et al., 2020c]. An interesting insight from our results is the close connection between the proposed multi-phase regularizer and the resulting optimal multi-phase pricing scheme. Specifically, we show that the penalty-free region of the regularizer plays a key role in shaping the multi-phase pricing function design. While expected in theory, this insight offers valuable guidance for designing pricing models in real-world applications like carbon pricing.

1.2 RelatedWork

This work builds on extensive research in resource allocation problems across computer science, economics, and operations research. Below, we review them based on the presence of (non-separable) regularizers.

Online allocation without regularizers. Online allocation problems without regularizers have been extensively studied in various forms, including online knapsack [Chakrabarty et al., 2008; Sun et al., 2021], bin packing [Lee and Lee, 1985; Angelopoulos et al., 2023], one-way trading [El-Yaniv et al., 2001; Lorenz et al., 2009; Lin et al., 2019], online matching [Mehta et al., 2007; Devanur and Jain, 2012; Ma and Simchi-Levi, 2020] (see [Mehta, 2013] and [Huang et al., 2024] for a comprehensive survey), online routing [Awerbuch et al., 2005; Buchbinder and Naor, 2006], and online auctions [Blum et al., 2003]. For example, [Ma and SimchiLevi, 2020] examines an extension of online matching where resources are offered at multiple prices, achieving the best competitive ratio of 1- 1e for deterministic algorithms. A particularly challenging variant is the generalized one-way trading problem with inventory constraints, optimally addressed in [Lin et al., 2019]. Our problem, involving multiple time slots, is closely related to [Sun et al., 2021], which studies an online fractional multiple knapsack problem with assignment restrictions, where each item can only be assigned to a subset of knapsacks [Kellerer et al., 2004]. They propose an algorithm with a competitive ratio between 1 + ln(U/L) and 2 + ln(U/L), where U/L is the ratio of maximum to minimum marginal utilities. However, their work focuses solely on maximizing aggregate utilities without regularizers.

Online allocationwith regularizers. A closely related line of research examines allocation problems with regularizers, modeled as negative rewards or penalties that are nonseparable over time [Tan et al., 2020c; Tan et al., 2025; Ma et al., 2024; Balseiro et al., 2021; Huang and Kim, 2015; Azar et al., 2016]. [Tan et al., 2020c] studies online mechanism design for a single knapsack, proposing an optimal posted price mechanism for convex and linear cost functions, but their work is limited to single-period, single-resource settings. Extensions to multi-period or multi-resource allocation appear in studies like [Tan et al., 2020a; Balseiro et al., 2021]. For example, [Tan et al., 2020a] develops an optimal algorithm for online combinatorial auctions with convex separable cost functions, while [Balseiro et al., 2021] addresses non-separable regularized problems, achieving sublinear regret and bounded asymptotic competitive ratios. In adversarial environments, the optimal competitive ratio for problems with non-separable regularizers and multiple allocation options remains open, with no optimal design yet available. [Azar et al., 2016] explores online convex packing problems, proposing a competitive algorithm under specific structural assumptions but without capacity constraints. In contrast, our work focuses on decoupling multi-phase, convex regularizers while incorporating capacity constraints, avoiding additional restrictive assumptions.

Table 1 summarizes key related works in the online allocation domain and compares them with our problem.

2 Problem Statement

We first formally define the resource allocation model and then discuss the required background and assumptions. Throughout the paper, we denote [N] = {1, 2, · · · ,N} for any positive integer N.

2.1 CNP-ROA: The Model

We consider a generic online allocation problem with divisible resource and a finite time horizon T , and assume the following agent and supply models.

Agents and Valuations. A sequence of N agents arrives sequentially, each characterized by a type vector θn = (vn, Xn, Tn), where vn : Xn → R+ represents a private valuation function, Xn denotes the feasible set of allocation actions, and Tn = {ton n , ton n +1, · · · , toff n } specifies the availability interval during which the agent can receive resources (i.e., agent n arrives at time ton n and departs at time toff n ). Upon the arrival of agent n ∈ [N] at time ton n , an immediate and irrevocable decision xn := {xtn }∀t∈Tn ∈ Xn is made, and the agent will receive a valuation of vn(xn). In particular, we assume that Xn = {xn | ∑t∈Tn xtn ≤ Dn, and xtn ∈ [0, dn], ∀t ∈ Tn}. Here, dn represents the rate limit for the resource consumption per step, and Dn denotes the total demand of resources requested by agent n.

Multi-Phase Regularized Supply. We consider a regularized supply model in which resource production incurs multiphase regulatory costs. Specifically, given the allocation profile {xn}∀n∈[N] for all the agents, let y be defined as

which represents the total resource production weighted by the coefficient wt ≥ 0, ∀t ∈ [T]. For any given y ≥ 0, let R(y) be the function defined as

where Csoft represents the penalty-free cap, or the soft cap, which allows the supplier to produce up to Csoft without incurring penalties. The parameter Chard denotes the hard cap, imposing a strict upper limit on the total amount of resources being produced. Hereinafter, we refer to R as the Cap-andPenalize (CNP) regularizer and the above CNP-regularized resource allocation problem as CNP-ROA.

Social Welfare and Mechanisms. We focus on designing an online mechanism comprising an allocation rule and a payment rule. For each agent n ∈ [N], let the allocation and payment be denoted by xn and πn, respectively. The utility of agent n is then given by vn(xn)-πn. The objective of the mechanism is to maximize social welfare:

where the payment terms cancel out. We consider a strategic setting where agents may act strategically regarding their valuation vn to improve their outcomes. If all agents are assumed to be non-strategic, the CNP-ROA problem reduces to a standard online optimization problem, and the online mechanism simplifies to an online algorithm with only an allocation rule.

2.2 Illustrating Examples

The CNP-ROA problem can capture many interesting problems. Below we give two illustrative examples.

• Carbon-regularized online job scheduling. The primary application motivating CNP-ROA is the carbonregularized job scheduling problem in data centers [Acun et al., 2023; Anderson et al., 2023] and electric vehicle charging [Cheng et al., 2022; Lechowicz et al., 2023]. For instance, agents can represent electric vehicles that arrive sequentially in an online manner to connect to a charger during their parking periods Tn. The weight coefficient wt represents the carbon intensity of energy generation at time t, while y denotes the total carbon emissions over the entire charging process. The supplier is allowed to emit up to Csoft units of carbon without incurring a penalty (i.e., zero cost if y ≤ Csoft). The hard cap, Chard, represents the maximum allowable carbon emissions, enforcing the constraint y ≤ Chard at all times.
• Online resource allocation with production costs. If wt = 1 for all t ∈ [T], y represents the total amount of resources produced. Under this assumption, the CNP regularizer generalizes the production cost model employed in prior online allocation studies. Specifically, when Csoft = 0, CNP-ROA recovers the allocation problems examined in [Tan et al., 2020c]. Furthermore, when both Csoft = 0 and Chard = ∞ hold, CNP-ROA reduces to the online convex packing problem studied in [Huang and Kim, 2015; Azar et al., 2016].

In addition, if we set f(y-Csoft) = 0 for all y ∈ (Csoft, Chard], the CNP-ROA problem simplifies to a typical online allocation problem without a regularizer or cost, a setting extensively studied in various contexts. For instance, if we assume T = 1 (i.e., a single-period allocation problem)

and further assume that the valuation function is linear (e.g., vn (xn) = νnxn) and dn = Dn = 1, then CNP-ROA reduces to the well-known online (fractional) knapsack problem [Chakrabarty et al., 2008; Sun et al., 2021]. In this case, Chard can be interpreted as the capacity of the knapsack.

2.3 Competitive Ratios

To specify all the information available to the mechanism designer in the online setting, we define Iknown as:

Given Iknown, the mechanism has complete knowledge of the regularizer R (including Csoft, Chard, and f), the time horizon T, and the weight vector w = {wt}∀t∈[T]. However, all information about the agents' types {θn}∀n∈[N], including the total number of agents N, remains unknown a priori.

To quantify the performance of an online mechanism, we follow the celebrated competitive analysis framework [Borodin and El-Yaniv, 1998] to define the competitive ratio (CR) of an online mechanism as follows:

where I = {θ1, · · · , θN} denotes an arrival instance. Given an arrival instance I, ALG(I) is the welfare achieved by our online mechanism (only knows Iknown), and OPT(I) is the optimal social welfare achievable in an offline setting assuming the type information of all arrival agents in I (in addition to Iknown) is given in advance. We say an online mechanism is α-competitive if it achieves a competitive ratio of α. Intuitively, α ≥ 1 holds all the time and a smaller α indicates a better performance.

2.4 Assumptions

Throughout the paper we make the following assumptions.

Assumption 1 (VALUATION FUNCTIONS). For any agent n, the value function vn satisfies the following conditions

• (i) vn is concave, monotone, and differentiable.
• (ii) vn(0) = 0, i.e., agents have zero utility if they are not receiving any resource.
• (iii) The partial derivative of vn(xn) is bounded, i.e., ∂vn ∂xtn /wt ∈ [L,U] for all t ∈ Tn and n ∈ [N], where {wt}t∈[T ] are coefficients given from the regularizer. We also assume that L and U are given a priori.

We also define ∆ = U/L, which represents the fluctuation ratio of agents' valuations. For instance, ∆ = 1 indicates that all agents are homogeneous, with identical linear valuation functions, whereas a larger ∆ signifies greater variation and heterogeneity among agents.

Assumption 2 (COST FUNCTION). The cost function f is convex, monotonically non-decreasing, and differentiable. In addition, f(0) = 0, i.e., the regularizer R(y) is a continuous function for y ∈ [0, Chard].

In practice, the cost function f may be piecewise linear, such as the taxation rate implemented under the cap-andtax policy in countries like Canada [Government of Canada,

2025]. We argue that assuming f to be convex and differentiable provides a reasonable approximation of the piecewise linear, convex tax function while being technically more convenient.

Assumption 3 (TRUTHFUL IN DURATIONS). Agents do not lie about their availability durations, i.e., each agent n ∈ [N] is truthful in following their true Tn (but may be strategic about the valuation vn).

Assumption 3 is common in the online mechanism design literature, also known as limited misreport [Parkes, 2007], indicating that the strategic behaviors may exist for the valuations, but not with respect to the durations.

3 Optimal Online Mechanism for CNP-ROA

In this section, we present our main results regarding the design of an optimal online mechanism for solving the CNPROA problem.

3.1 PPM-Φ: How It Works

We propose a posted-price mechanism in Algorithm 1, termed PPM-Φ, where Φ denotes the marginal pricing function, a key function that guides the execution of the online mechanism and also its competitive analysis.

Algorithm 1 Online Mechanism for CNP-ROA (PPM-Φ)

• 1: Inputs: Iknown and Φ
• 2: Initialization: Capacity utilization u(0) = 0
• 3: while a new agent n arrives do
• 4: Post pricing function p(n) for agent n:

• 5: Agent n decides its own profile ˆxn:

• 6: Agent n makes the payment πn:

• 7: Update the utilization:u(n) = u(n-1) + ∑t∈Tn wtˆxtn . 8: end while

When an agent arrives, PPM-Φ posts the pricing function based on Eq. (2), and the agent determines their allocation profile by solving the utility maximization problem in Eq. (3). The marginal pricing function Φ must strike a balance between accepting agents too readily and delaying in anticipation of future better arrivals. For instance, if Φ is set too low (e.g., Φ(y) = f ′ (y)), most agents will find the price inexpensive and consume as many resources as possible according to Eq. (3). Conversely, if Φ is set too high (e.g., Φ(y) = Uy), most agents will find the price unaffordable and walk away with zero consumption (i.e., ˆxn = 0). Thus, ensuring the effective performance of PPM-Φ hinges on designing an appropriate marginal pricing function Φ. In the next section, we show that there exists an optimal marginal pricing function Φ so that PPM-Φ achieves the best-possible competitive ratio among all online mechanisms.

3.2 Optimal Design of Φ

We begin by giving a lemma characterizing the major parameters in our design.

Lemma 1. Let F(u|α) be defined as:

There exists a unique pair of α ≥ 1 and β ∈ [Csoft,Chard] which satisfy the following system of equations:

Based on Lemma 1, we introduce our design of the marginal pricing function Φ in the theorem below.

Theorem 1 (CNP-ROA: CONVEX). Given Iknown and under Assumptions 1-3, PPM-Φ is α-competitive when Φ is designed as follows:

• (Low-Soft-Cap) If Csoft ≤ β:

• (High-Soft-Cap) If Csoft > β:

For both cases, Λ = Le- αβ Chard -F(max(β,Csoft)|α); α and β are the solution to the system of equations in Eq. (6).

Here, we outline some key intuitions. Figure 1 illustrates the design of Φ for both the Low-Soft-Cap and High-SoftCap cases. In both scenarios, the marginal pricing function Φ begins with a flat phase, where Φ(u) = L for all u ∈ [0, β], with L representing the minimum marginal valuation, as specified in Assumption 1. Beyond the threshold β, Φ transitions to an increasing phase for u ∈ [β,Chard]. In the High-Soft-Cap case, where Csoft ≥ β, the marginal pricing function continues to increase in a third phase for u ∈ [Csoft, Chard].

• About the flat phase during [0, β]. Lemma 1 demonstrates that for any given α ≥ 1, there exists a unique β ∈ [Csoft,Chard] satisfying Eq. (6b), which determines

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Z

u

Q

n

A

j

C

q

G

X

0

r

7

L

o

>

B

H

c

V

D

S

g

N

E

O

y

f

U

Y

9

P

K

2

w

J

M

z

8

R

k

5

W

3

d

m

F

/

p

v

I

+

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

v

O

z

M

u

3

0

Y

A

H

2

D

F

X

G

Z

I

>

B

c

V

N

S

8

E

J

W

K

o

n

d

C

Q

p

7

T

j

f

9

5

+

P

g

/

m

k

r

q

L

R

U

y

w

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

F

C

V

Q

E

W

T

f

U

Y

A

m

P

r

X

S

B

j

8

g

>

+

H

c

D

L

N

J

3

R

q

0

w

2

7

K

d

O

M

G

u

/

o

9

k

Z

z

n

I

p

5

y

v

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

z

3

f

S

Z

Q

d

0

E

A

8

K

p

O

q

C

V

c

>

B

7

H

N

J

U

r

/

9

L

n

2

P

R

D

w

m

G

g

Y

v

T

y

5

+

u

M

X

W

o

j

F

k

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

3

R

0

k

G

Q

8

J

w

z

A

X

c

Z

U

o

>

B

+

H

V

D

L

S

N

F

r

P

q

E

g

2

7

K

C

f

m

y

Y

d

O

u

/

T

M

9

W

n

j

v

I

5

p

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

P

3

Z

g

G

y

/

k

9

D

u

L

I

X

W

Q

>

A

B

7

H

c

V

N

S

w

M

E

J

2

+

T

C

R

q

U

v

F

Y

0

K

z

p

O

m

n

r

j

d

8

5

o

f

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

/

I

0

A

5

T

2

u

Y

W

Z

G

w

d

7

g

U

>

B

n

c

V

D

L

S

N

E

O

z

M

r

H

J

y

K

P

Q

8

m

v

C

F

o

9

3

k

j

q

p

X

f

+

R

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

X

G

7

3

j

R

K

5

g

8

q

9

L

v

0

>

A

B

H

c

V

D

S

N

E

O

z

M

r

Y

d

Q

Z

U

C

y

J

m

n

k

/

w

I

T

o

2

W

p

P

F

u

+

f

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Z

u

Q

n

A

j

C

q

G

X

0

r

7

L

o

>

B

H

c

V

D

S

g

N

E

O

y

f

U

Y

9

P

K

2

w

J

M

z

8

R

k

5

W

3

d

m

F

/

p

v

I

+

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

v

O

z

M

u

3

0

Y

A

H

2

D

F

X

G

Z

I

>

B

c

V

N

S

8

E

J

W

K

o

n

d

C

Q

p

7

T

j

f

9

5

+

P

g

/

m

k

r

q

L

R

U

y

w

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

U

I

A

M

B

C

F

c

g

K

2

W

z

Y

H

8

>

/

n

V

D

L

S

N

J

3

r

P

d

u

k

o

m

5

G

7

O

E

T

0

X

j

Q

v

w

p

f

y

+

Z

R

9

q

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

z

3

f

S

Z

Q

d

0

E

A

8

K

p

O

q

C

V

c

>

B

7

H

N

J

U

r

/

9

L

n

2

P

R

D

w

m

G

g

Y

v

T

y

5

+

u

M

X

W

o

j

F

k

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

F

C

V

Q

E

W

T

f

U

Y

A

m

P

r

X

S

B

j

8

g

>

+

H

c

D

L

N

J

3

R

q

0

w

2

7

K

d

O

M

G

u

/

o

9

k

Z

z

n

I

p

5

y

v

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

3

R

0

k

G

Q

8

J

w

z

A

X

c

Z

U

o

>

B

+

H

V

D

L

S

N

F

r

P

q

E

g

2

7

K

C

f

m

y

Y

d

O

u

/

T

M

9

W

n

j

v

I

5

p

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

P

3

Z

g

G

y

/

k

9

D

u

L

I

X

W

Q

>

A

B

7

H

c

V

N

S

w

M

E

J

2

+

T

C

R

q

U

v

F

Y

0

K

z

p

O

m

n

r

j

d

8

5

o

f

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

/

I

0

A

5

T

2

u

Y

W

Z

G

w

d

7

g

U

>

B

n

c

V

D

L

S

N

E

O

z

M

r

H

J

y

K

P

Q

8

m

v

C

F

o

9

3

k

j

q

p

X

f

+

R

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

X

G

7

3

j

R

K

5

g

8

q

9

L

v

0

>

A

B

H

c

V

D

S

N

E

O

z

M

r

Y

d

Q

Z

U

C

y

J

m

n

k

/

w

I

T

o

2

W

p

P

F

u

+

f

the threshold β such that the marginal price remains constant for all u ∈ [0, β] (i.e., Φ(u) = L), as established in Theorem 1. The rationale behind Eq. (6b) is to ensure that the first β-portion of the resource is always allocated, even to agents with the minimum marginal valuation L. This design guarantees that PPM-Φ remains α-competitive in the worst-case scenario, where all arriving agents have the lowest marginal valuation.

• About the increasing phase during [β,Chard]. For both cases in Theorem 1, the marginal pricing function Φ enters the increasing phase after exceeding the threshold β, reflecting the fundamental principle that "scarcity of resources leads to higher prices." Notably, the soft cap Csoft plays a critical role in shaping the design of the increasing phase. A lower Csoft implies that a single increasing phase is sufficient, whereas a higher Csoft necessitates a two-segment design for the increasing phase. This distinction highlights the key difference between our results and existing studies with single-phase regularizers, including the special case without a regularizer.

Theorem 2 (LOWER BOUND). Under Assumptions 1-3, PPM-Φ with the marginal pricing function Φ specified in Theorem 1 achieves the optimal competitive ratio.

Theorem 2 demonstrates that PPM-Φ is not only an optimal posted price mechanism but also optimal among all online algorithms, including those with randomization. This result indicates that the existence of strategic behaviors in CNP-ROA does not introduce additional difficulty in the online setting. In other words, focusing on posted price mechanisms does not result in any loss of generality when aiming to achieve the best possible competitive ratio among all online algorithms.

We provide the following remark to illustrate how Theorem 1 and Theorem 2 generalize existing state-of-the-art results for specific choices of the soft cap Csoft.

Remark 1 (CONNECTION TO EXISTING RESULTS). If Csoft = 0, the multi-phase regularizer simplifies to a singlephase penalty (i.e., R(y) = f(y) for all y ∈ [0,Chard]). In this case, Theorem 1 reproduces the optimal design proposed in [Tan et al., 2020c]. Conversely, if Csoft = Chard, then R(y) = 0 for all y ∈ [0,Chard]. In this scenario, PPM-Φ, with the pricing function design specified in Theorem 1, reproduces the design proposed in [Sun et al., 2021], achieving the optimal competitive ratio:

where ∆ = U/L denotes the fluctuation ratio of agents' marginal valuations.

3.3 Case Study: Linear Cost (f(y) = σy)

To illustrate the design of the marginal pricing function Φ more clearly, we consider the special case where f(y) = σy. This allows us to refine the results of Theorem 1 by providing a more explicit characterization of Φ and calculating key parameters, such as α and β.

Proposition 1 (CNP-ROA: LINEAR). Given Iknown and under Assumptions 1-3, PPM-Φ is α-competitive when Φ is designed as follows:

• (Low-Soft-Cap) If Csoft ≤ β:

where the competitive ratio α and β are given by

• (High-Soft-Cap) If Csoft > β:

where α, β, and A are given as follows:

Proposition 1 directly follows from Theorem 1 by substituting f ′ (y) = σ into Eq. (6a), resulting in an analytical expression for F(u|α). According to Proposition 1, if Csoft = Chard or σ = 0, PPM-Φ is (1 + ln∆)-competitive, which is known to be optimal based on prior studies [Chakrabarty et al., 2008; Tan et al., 2020c; Sun et al., 2021].

4 Extensions to CNP-ROA with Resource Constraints

The mechanism PPM-Φ, designed in Section 3, solves CNPROA optimally in the absence of resource constraints for each time slot. In this section, we demonstrate that the design can be extended to address the more complex scenario where resource supply is limited at each step.

4.1 PPM-ϕ: AModified PPM-Φ

Let ct denote the resource constraint at time t ∈ [T]. Thus, the total allocation must satisfy the following constraint:

To extend PPM-Φ to account for the above resource constraints, a key step is to change the design of a single marginal pricing function Φ to a set of time-dependent marginal pricing functions, denoted as ϕ = {ϕt}t∈[T ]. We can then modify PPM-Φ based on ϕ as follows:

• The supplier posts the pricing functions {p(n) t }t∈Tn to agent n upon its arrival:

• Agent n decides its consumption profile by solving the following utility-maximization problem

and makes the payment πn = ∑t∈Tn p(n)

• The supplier updates the total utilization for each time slot u(n) t = u(n-1) t + ˆxtn , ∀t ∈ Tn.

Hereinafter, we refer to PPM-Φ as PPM-ϕ to highlight the role of time-dependent marginal pricing functions ϕ. While the execution of PPM-ϕ is similar to PPM-Φ, its analysis requires a different approach due to the non-separability of the regularizer across time slots. To address this, we decompose the regularizer into multiple local regularizers, each tied to a specific time slot. Details of this decomposition are provided in the next subsection.

4.2 Core Idea: Decoupling the Regularizer

The CNP framework considers an aggregate soft cap for the entire allocation process across all time slots. To facilitate the design of a marginal pricing function for each time slot, Definition 1 introduces a method to decompose this global soft cap and assign an appropriate share, bt, to each time slot, referred to as the local soft cap.

Definition 1 (LOCAL SOFT-CAP). Given Csoft as the global soft-cap, let bt denote the local soft-cap at time t, defined as

Intuitively, ∑t wtbt = Csoft, indicating that bt represents the normalized soft cap for each time slot, weighted by the consumption rate wt. Using the local soft cap bt, we define the local regularizer rt to decouple the regularizer cost across time slots.

Definition 2 (LOCAL REGULARIZER). Let rt denote the local regularizer at time t, defined as

For the local regularizer rt defined in Definition 2, we compute the partial derivative of R with respect to the utilization level of the t-th time slot, while keeping the utilization levels of all other time slots fixed at their respective capacities to eliminate interdependencies. Note that the partial derivative always exists because wty + ∑τ̸=t wτ cτ > Csoft always holds.

Based on Definition 2, we show that a similar group of design parameters, α and {βt}∀t, still exist and the details are given in the lemma below.

Lemma 2. Let Ft(u|α) be defined as:

There exists a unique set of α ≥ 1 and {βt}∀t that satisfy the following system of equations:

Lemma 2 extends Lemma 1 by introducing a timedependent βt ∈ [0, ct] for each slot t ∈ [T]. The next subsection demonstrates that the design of βt is crucial for developing a time-dependent marginal pricing function ϕt for each time slot t ∈ [T].

4.3 Design of {ϕt}∀t

Building on Lemma 2, we extend Theorem 1 to design ϕ = {ϕt}∀t∈T by modifying (F, β,Λ) to (Ft, βt,Λt). To better illustrate this approach, we consider the specific case where the cost function is linear, e.g., f(y) = σy, and extend Proposition 1 to solve CNP-ROA under resource constraints. The full details are presented in Proposition 2 below.

Proposition 2 (CNP-ROA WITH RESOURCE CONSTRAINTS: LINEAR COSTS). Given Iknown with resource capacity c = {ct}∀t and under Assumptions 1-3, PPM-ϕ is α-competitive when ϕt is designed as follows:

• (Low-Soft-Cap) If Csoft ≤ 1 α-1 · Chard:

where the competitive ratio α and βt are given by

• (High-Soft-Cap) If Csoft > 1 α-1 · Chard:

where α, βt, and At are given as follows:

In both cases, qt = σwt and qmax = maxt∈[T ] σwt.

The following corollary shows that PPM-ϕ achieves a near-optimal competitive ratio in the High-Soft-Cap case.

Corollary 1 (LOWER BOUND). For the High-Soft-Cap case in Proposition 2, the competitive ratio of PPM-ϕ is O(2 + ln ˆ∆), where ˆ∆ = U-qmax L-qmax , and the optimal competitive ratio of this problem is Ω(1 + ln ˆ∆).

Corollary 1 demonstrates that when the soft-cap is sufficiently large, such that the forced flat segment concludes before the penalty cost impacts the pricing functions, the influence of the regularizer on the competitive ratio remains bounded.

Corollary 2 (CONNECTION TO EXISTING RESULTS). When Csoft = Chard, namely, R(y) = 0 holds for all y ∈ [0, Chard], PPM-ϕ with the time-dependent marginal pricing functions specified by Proposition 2 is α-competitive with α given by

where ∆ = U/L denotes the fluctuation ratio of agents' marginal valuations.

Notably, [Sun et al., 2021] examines a similar online allocation problem without a regularizer, achieving the same competitive ratio as in Eq. (11). Here, we demonstrate that our design generalizes the results of [Sun et al., 2021] as a special case when Csoft = Chard.

5 Conclusion and FutureWork

Motivated by real-world applications such as cap-and-tax carbon pricing, this paper introduces a novel online optimization problem, cap-and-penalize (CNP)-regularized online allocation (CNP-ROA). We derived an optimal online mechanism for CNP-ROA without per-step resource constraints and presented the best-known results for the more challenging setting with such constraints. To prove optimality, we introduced a novel representative function-based approach, reducing the lower-bound proof to solving an ordinary differential equation with boundary conditions.

This work opens several promising avenues for future research. Two key directions include addressing the gap in the CNP-ROA problem under resource constraints, which involves solving a multi-knapsack problem with multidimensional weights, and tackling the issue of temporal fairness. The latter challenge stems from the increasing marginal pricing function, which disproportionately penalizes later arrivals. Incorporating fairness constraints into this framework represents a significant theoretical and practical challenge.