Dynamic Coalition Formation Under Capacity Constraints: A Regime-Switching Value-Investing Game

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

1

Dynamic Coalition Formation Under Capacity Constraints: A Regime-Switching Value-Investing Game

arXiv:2611.03137v1 [cs.GT] 2 Nov 2026

Rosario Patanè SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris, Palaiseau, France rosario.patane@telecom-sudparis.eu

Abstract—Edge computing service deployment requires the Network Operator (NO) and Service Providers (SPs) to coordinate investment and resource allocation under uncertain demand. This paper develops an audit-based service management framework for daily coalition formation with fixed capacity and servicelevel agreement (SLA) reservations. A two-stage coalitional game separates infrastructure investment from operational participation. Demand follows a Geometric Random Walk (GRW), and SPs apply an ordered admission and suspension rule using reported marginal contributions. With the NO held fixed, the operational coalition value is submodular; mandatory reservations can produce negative Shapley payoffs. We derive a separable benchmark, compute operational Shapley allocations, and give a sufficient condition for convergence to an individual equilibrium. A probabilistic audit mechanism provides a conditional daily truthfulness guarantee under verified settlement and enforceable penalties. For five service classes over three years, the reference run gains 12.4% over static grand-coalition membership and recovers 94.6% of the full-information optimum. Across 30 runs, the median gain is 13.3%. Sensitivity tests examine policy parameters, capacity and alternative demand models. The gain depends on capacity and update order; abundant capacity can make the admission rule underperform static membership. Index Terms—Edge computing, network service management, coalition formation, resource allocation, Shapley value, audit mechanisms.

I. I NTRODUCTION Managing multi-tenant edge services requires solving jointly resource allocation, service admission, and Service-Level Agreement (SLA) enforcement under shared capacity. Edge Computing (EC) brings compute resources close to users, enabling latency-critical applications such as autonomous driving, augmented/virtual reality (AR/VR), cloud gaming, and the Internet of Things (IoT) [1]. Although International Data Corporation (IDC) projected worldwide EC spending of $232 billion for 2024 [2], large-scale deployment remains limited because of an economic rather than technological bottleneck. The Network Operator (NO) bears the infrastructure capital expenditure (CAPEX), whereas Service Providers (SPs) capture most service revenues, leaving neither side with sufficient incentive to invest independently. Coalitional co-investment addresses this misalignment by allowing the NO and SPs to share costs and revenues. A foundational model [3] showed that the resulting cooperative game is convex and that the Shapley value aligns incentives, assuming deterministic de-

mand, static coalition membership, and fully informed players. Three assumptions limit current co-investment formulations. a) (A1) Deterministic demand: Existing models assume known traffic and revenue trajectories [3]. Recent stochastic extensions account for revenue uncertainty [4], but still rely on fixed coalition membership. b) (A2) Static membership: Classical co-investment fixes coalition membership at deployment. Dynamic extensions [5] introduce entry and exit fees, but coalition evolution remains centrally managed rather than driven by decentralized daily decisions. c) (A3) Full information: Existing formulations assume fully informed, rational players. In practice, SPs observe only local information and must make decisions under uncertainty. Graham’s margin-of-safety (MoS) principle [6] provides a natural behavioural rule for such settings. d) Proposed framework: We address (A1)–(A3) jointly with a decentralized value-investing framework that separates the irreversible deployment decision from daily coalition formation, and that admits or revokes tenants on a margin-ofsafety criterion motivated by residual-horizon traffic uncertainty. Our contributions are as follows. 1) We formulate a two-stage coalitional game with stochastic Geometric Random Walk (GRW) demand that decouples long-term capacity deployment from daily coalition formation. 2) We establish submodularity conditional on the NO’s presence and characterize Shapley allocations under capacity and SLA constraints, including the possibility of negative operational payoffs. 3) We design a decentralized value-investing admission rule with a volatility-scaled margin of safety and establish a finite bound for detecting repeated states of the ordered update rule. 4) We develop an audit-and-trust mechanism that provides a conditional daily truthfulness guarantee for the Network Operator and characterize the audit frequency minimizing the stated criterion. 5) Numerical experiments over five edge service classes achieve Price of Decentralisation (PoD) = 1.057 and dynamic/static value ratio (PoS) = 1.124: a +12.4% gain over the static grand coalition, evaluated with the same operational capacity model.

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

2

The remainder of the paper is organised as follows. Secc) Value investing and margin of safety: Graham’s martion II reviews related work and Section III introduces the gin of safety [6] prescribes committing capital only when model; Sections IV–X develop the theoretical results and intrinsic value exceeds market price by a buffer absorbing Section XI defines the evaluation metrics; Section XII reports valuation error. Threshold policies in optimal stopping, hysthe numerical evaluation and Section XIII concludes. Proofs teresis in repeated games, and robust mechanism design [14] of the main results are in the Appendix; the acronym glossary are structurally related, but none makes the analogy explicit. is in Table I. The complete simulation code, parameter files, Our position. We make three connections explicit. First, SP i’s and scripts generating the figures and numerical results are marginal contribution ∆i (d), the operational value gained on provided in the accompanying reproducibility package. The entry or lost on departure at day d, is the intrinsic value original public repository is https://github.com/patan3saro/Ed analogue, while the current coalition is S(d), its SP subset geValueInvesting-Sim under the MIT licence. is P(d), and vd (S(d)) is its daily operational value. With | · | denoting cardinality, the average vd (S(d))/|P(d)| is the II. R ELATED W ORK market price analogue. Second, let θmin be a positive base marWe organise prior work along three axes that map directly gin, κ a sensitivity coefficient, σi daily log-demand volatility, days, and θi (d) the join threshold. We set to the limitations of Section I: coalitional games for networks Dinv the horizon in √ θ (d) = θ + κσ and service management, edge-computing co-investment, and i min i Dinv − d. This scaling is motivated by the small-variance approximation of future traffic uncertainty value-investing principles in mechanism design. in Proposition 10, while its coefficients are policy parameters. a) Coalitional games for networks and resource sharing: Third, the distinct leave threshold specifies a retention criterion The tutorial of Saad et al. [7] presents cooperative game (Remark 15); it does not prove hysteresis. theory and merge-and-split coalition formation for communication networks. Applications include stochastic spectrum sharing [8], cooperative cloud provisioning under uncertain deIII. S ERVICE M ANAGEMENT M ODEL AND C OALITIONAL mand [9], and content distribution in vehicular networks [10]. C O -I NVESTMENT Mashayekhy et al. [11] study cloud federations with a normalWe model edge co-investment as a coalitional game with ized Banzhaf profit-sharing rule and merge-and-split formation. Zafari et al. [12], in IEEE Transactions on Network and Ser- transferable utility (TU) [15]. Let v denote its characteristic vice Management (TNSM), study resource sharing in mobile function. The player set I = {1, . . . , M, NO} is the grand edge clouds under capacity constraints. These settings differ in coalition: M counts SPs and M + 1 counts all players. their stochastic assumptions and allocation rules. Our position. Calligraphic symbols denote sets, and upright N(0, 1) denotes We retain decentralized coalition participation, but here the the standard normal distribution. The symbol NO identifies source of dynamism is a stochastic, player-specific traffic the unique infrastructure owner. a) Two-Stage Structure: Let Dinv be the investment process (2) that changes coalition values and capacity shadow prices over time. The resulting participation decisions account horizon in days and d ∈ {0, 1, . . . , Dinv } the day index; each day is a decision epoch. The active coalition S(d) ⊆ I is for the capacity displaced by mandatory SLA allocations. b) Edge computing co-investment: A foundational coali- the subset of players sharing resources on day d, with active tional model for edge co-investment with one NO and multiple SPs P(d) = S(d) \ {NO}. Here \ denotes set difference and SPs was proposed in [3]: convexity of the resulting cooperative removes the NO from the active set. b) Stage I (d = 0): Let pi ≥ 0 be player i’s upfront game was established and the Shapley payoff derived in closed form. The model is deterministic and static; it motivates contribution in dollars and qcap > 0 the hardware P cost per −1 a static-membership comparator; our experiments evaluate millicore (mc). The investors deploy C = qcap i∈I pi . The Grand under the present operational model (Section XII). Sakr CAPEX qcap C is sunk; initially S(0) = I. Operational et al. [4] introduce revenue uncertainty; their journal exten- exit temporarily suspends service and preserves ownership. sion [13] addresses dependent revenue fluctuations and prob- Let ωi = pi /(qcap C) be the ownership share, χ ∈ [0, 1] abilistic stability and profitability. The dynamic-participation the fraction reserved for investors, and φi (d) the operational study [5] updates capacity and membership across decision Shapley payoff, zero for an inactive SP. If vd denotes daily epochs, with entry fees, exit penalties and compensation. The coalition value, total receipts in value units are xi (d) = present mechanism is based on distributed SP decisions with χωi vd (S(d)) + (1 − χ)φi (d). An inactive investor retains operator-computed value signals and emerges from a daily the first term. With conversion svu > 0 dollars per value rule that adapts to realised demand; players exit when their unit, discount factors bd > 0 and outside-option value oi own margin-of-safety condition fails; and declarations are in dollars, P let E denote expectation. Participation requires supported by an audit-and-trust mechanism with explicit settle- svu E[ d bd xi (d)] ≥ pi + oi . The experiments take C as fixed ment and enforceability assumptions. Our position. We extend and report the operational account; they do not calibrate this this line on three axes at once: the coalition re-forms daily contract or establish its participation feasibility. c) Stage II (d ≥ 1): The index i ∈ {1, . . . , M } identifies under stochastic traffic rather than at exogenous re-negotiation epochs; the join/leave decision is decentralised and operates an SP. With C fixed, S(d) re-forms each day via the valueunder partial information; and the mechanism addresses daily investing rule of Section VII. Each day defines a cooperative NO misreporting under explicit audit assumptions, an issue game (I, vd ). For an SP set P(S) = S \ {NO}, let hi be the compute allocation, hi its contractual minimum, both in none of [3], [4], [5] addresses.

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

Stage I Capacity (d = 0) Deploy C = q 1 cap (sunk)

C fixed

P

pi

Stage II Daily formation (d ≥ 1) Join/leave via value ratios

Fig. 1. Two-stage game structure. Stage I is the irreversible capacity decision; Stage II is the daily coalition formation under (I, vd ).

mc, and Λid the daily traffic scale in requests per second (req/s). Write h = (hi )i∈P(S) and h = (hi )i∈P(S) ; h ≥ h holds componentwise. Let Udi be the daily utility. For feasible coalitions containing the NO, the coalition value is X X Udi (hi ; Λid ) s.t. hi ≤ C, (1) vd (S) = max h≥h

i∈P(S)

i∈P(S)

3

The coefficient βNO = 0 means that the NO has no direct service revenue. Thus βi is not a calibrated dollar tariff per request. A monetary interpretation would require a conversion using actual request counts, including slot duration. The exponential utility is a modeling choice for diminishing returns. Salchow [17] discusses multicore scaling limitations; that source does not derive this utility. Memory and cache effects are outside the numerical specification. Lemma 1 (Concavity). Udi (hi ) is strictly concave and strictly increasing in hi on R+ . Proof. ∂h Udi = βi Λid F ξ e−ξh > 0 and ∂h2 Udi = −βi Λid F ξ 2 e−ξh < 0 for all h ≥ 0, since βi Λid F > 0 and ξ > 0. The SLA reservation hi ≥ 0 is the minimum compute allocation assigned to service i by contract. The experiments use the reservation vector (30, 300, 1500, 0.3, 112.5) mc as an input. These floors are not derived from a queueing model and do not by themselves prove simultaneous throughput and end-to-end latency guarantees. Autonomous driving has the largest reservation in this specified service mix. The capacity feasibility constraint at each day d is X (4) hi ≤ C, hi ≥ hi .

The Shapley value is evaluated on the sub-coalitions of the realized active set, including counterfactual coalitions without the NO. The active set is produced by the ordered daily rule of Section VII; it need not be an equilibrium. Fixed capacity represents the installed central processing unit (CPU) budget determined in Stage I and held constant over the investment horizon. The framework targets long-term infrastructure coinvestment and daily service-coalition management within this i∈P(d) predetermined budget. General elastic orchestration, including P dynamic scaling, cloud offloading, online expansion, or joint The grand coalition is feasible iff i hi ≤ C; otherwise no management of heterogeneous resources such as CPU, mem- single coalition honours all SLAs simultaneously, motivating ory and bandwidth, lies outside the present model. dynamic sub-coalition formation. d) Traffic Model: Each day has T = 96 timeslots of f) Coalition Value, Veto, and Information: For feasible i ∆t = 900 s. The arrival rate is ld,t = Λid · f (t) [req/s], with coalitions containing the NO, the value is the optimum of f the deterministic intra-day profile [16]. The slot index is (1). Coalitions without the NO have value zero. The analysis PM t ∈ {1,P. . . , T } and ∆t is slot duration. The daily aggregate and baseline experiments assume C > i=1 hi , so every T F = SP subset is feasible. Outside this domain, infeasible sets are t=1 f (t) is a dimensionless profile sum. Only this aggregate enters the utility, and the simulations fix F = 96; excluded from optimization; an infeasible investor universe is they do not simulate a queue within individual slots. not passed to the Shapley calculation. Let Λi0 > 0 be initial demand, µi the daily drift, and σi / S. volatility per square root of a day. The innovations ϵid are Proposition 2 (Veto player). vd (S) = 0 whenever NO ∈ independent and identically distributed (i.i.d.) over SPs and Proof. The NO controls access to the deployed infrastructure; i.i.d. days, with ϵid ∼ N(0, 1). Using one-day steps, the daily scale without its participation, the coalition cannot operate and has follows a Geometric Random Walk (GRW): value zero by the characteristic-function convention. 2   σ Λid = Λid−1 exp (µi − 2i ) + σi ϵid , d ≥ 1, (2) Each SP observes its own traffic and revenue coefficient, its contractual reservation, and a small set of public signals: Here µi has units day−1 and σi has units day−1/2 . The the NO’s value declaration v̂(d), per-SP marginal contribution corrective term ensures E[Λid ] = Λi0 eµi d , where E denotes ˆ i (d), the active coalition size |S(d)|, and its own estimates ∆ expectation. i Λd , βi , hi . The shadow price λ∗ (d) of (1) is its capacity The GRW provides a positive multiplicative demand model multiplier, in vu/mc; it and other SPs’ parameters remain with tractable conditional moments. It represents scenarios of ˆ i (d) private to the NO. The declared signals v̂(d) and ∆ evolving service popularity, rather than a calibrated model of estimate the current coalition value and the entry/departure every traffic feature. Independent Gaussian increments do not marginal vd (S(d)∪{i})−vd (S(d)\{i}). Cardinality is denoted capture bursts, periodicity or long-range dependence; alternaby | · |. tive synthetic traffic models are evaluated in Section XII. Evaluating ∆i (d) (Definition 11) requires vd on sube) Utility, Capacity, and SLA: Let ξ > 0 be the saturation coalitions, hence λ∗ (d) and competitors’ parameters. The NO −1 rate in mc and βi > 0 the traffic-to-value coefficient in ˆ i (d)}i alongside v̂(d), therefore publishes daily the vector {∆ vu/(req/s), where vu denotes a normalized value unit. The daily and each SP applies (14)–(15) to it without reconstructing utility of SP i is λ∗ . The audit of Section VIII covers the full declared vector
i i −ξhi ˆ i (d)}): detection on any component triggers the Ud (hi ) = βi Λd F 1 − e , βNO = 0, (3) (v̂(d), {∆

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

penalty Π. The bound in Section X covers the induced feasible coalition outcomes under verified settlement. g) Capacity Regimes and Coalition Structure: For the structural analysis of SP participation, the NO is held fixed: for any SP set P ⊆ {1, . . . , M }, we define wd (P) = vd (P ∪ {NO}). Submodularity below refers to this set function on SP subsets. Payoff allocation still uses the Shapley value of the full game, including the NO as a veto player. The reference level q > 0 is a marginal value in vu/mc, fixed at 0.10 in the experiments, and distinct from qcap . The coupling through C induces a regime structure indexed by the shadow price λ∗ (d) ≥ 0 of (1). In h∗i and λ∗ , the asterisk marks the optimal allocation and its capacity multiplier. Define P + (d) = {i ∈ P(d) : h∗i > hi } (unconstrained SPs) and P 0 (d) = {i ∈ P(d) : h∗i = hi } (SLA-bound SPs).

4

b) Unconstrained Individual Value and Separability: For x > 0, define g(x) = x − 1 − ln x (g ≥ 0, g(1) = 0). The unconstrained individual value of SP i is   q g(Xi (d)), Xi (d) > 1, i (7) v (d) = ξ 0, 0 < Xi (d) ≤ 1. which equals the surplus that SP i would extract if it could buy capacity at the reference value q alone (derivation in Appendix A). The auxiliary cost-adjusted value is ṽd (S) = vd (S) − q

X

h∗i (S, d).

(8)

i∈P(S)

Stage II redistributes the operational value vd . The costadjusted quantity ṽd is used only for comparison with the individual-value benchmark; the deployment CAPEX is accounted for in Stage I.

Definition 3 (Capacity regimes). For the current coalition, write λ∗ (d) = λ∗ (S(d), d). Regime A (abundant): λ∗ (d) ≤ q. Regime B (scarce): λ∗ (d) > q. These labels describe scarcity Proposition 5 (Coalition-specific separability identity). Fix a relative to the reference level q. Under the assumptions of The- feasible coalition S containing the NO and at least one SP. orem 6, the coalition value conditional on the NO’s presence is Assume that all its SP allocations are strictly above their SLA submodular in both regimes. Binding SLA floors may produce floors and that X (d) > 1 for every member. If λ∗ (S, d) = q, i negative marginal contributions. For a coalition containing X ∗ only the NO, we adopt the convention λ (d) = 0 and assign ṽd (S) = v i (d). (9) it to Regime A. i∈P(S) The comparison between λ∗ (d) and q describes the capacity Under the same assumptions, the discrepancy is given by (23) regime. The separability identity in Proposition 5 applies to a and is quadratic as λ∗ (S, d) → q. This identity concerns the specified coalition under interior allocation; it does not imply specified coalition; its sub-coalitions generally have different coalition-independent marginal contributions. A fixed member- shadow prices. ship can be suboptimal when excluding an SP increases the The proof is given in Appendix B. operational coalition value. c) Conditional Submodularity: IV. A NALYSIS a) Karush–Kuhn–Tucker (KKT) Solution: Let q > 0 be a reference marginal value in vu/mc, fixed at 0.10; it is distinct from the hardware cost qcap . Define the coefficient Ai (units s/req) and the dimensionless profitability index Xi (d) by Ai =

ξ βi F , q

Xi (d) = Ai Λid .

(5)

Xi = 1 is the break-even point for the first infinitesimal millicore in the unconstrained reference-cost benchmark; it is not a test of profitability for a mandatory SLA reservation. Proposition 4 (KKT solution). For P a coalition containing the NO and at least one SP, with C > i∈P(S) hi , the optimum of (1) is   1 Xi (d) q ∗ hi (d) = max hi , ln ∗ , (6) ξ λ (d) P with λ∗ (d) > 0 uniquely determined by i h∗i (d) = C. The proof is given in Appendix A. The interior solution admits a water-filling reading: the allocator pours capacity into each SP until its marginal utility, ∗ equal to Xi qe−ξhi , equals the common shadow price for every SP allocated strictly above its floor.

Theorem 6 P (Conditional submodularity). Fix day d and asM sume C > i=1 hi . For the utilities in (3), the conditional coalition value wd is submodular: for A ⊆ B and j ∈ / B, wd (A ∪ {j}) − wd (A) ≥ wd (B ∪ {j}) − wd (B). This property holds independently of the comparison between λ∗ and q. Positive SLA floors may make wd non-monotone, allowing negative marginal contributions. The proof of the above theorem is in Appendix C. V. DYNAMIC S HAPLEY VALUE Theorem 7 (Benchmark and operational Shapley values). Let m = |S(d)| ≥ 2 be the number of active players, including the NO. (i) Separable benchmark. For a sub-coalition T ⊆ S(d), let v̄d (T ) denote the following auxiliary veto-game value  X  v i (d), NO ∈ T ,  v̄d (T ) = i∈T \{NO}  0, NO ∈ / T. This game is supermodular and has a nonempty core. Its Shapley allocation is: φ+ i (d) =

v i (d) , 2

φ+ NO (d) =

1 2

X i∈P(S(d))

v i (d).

(10)

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

5

TABLE I P RINCIPAL NOTATION AND OPERATIONAL PARAMETER SET. P ER -SP VECTORS ARE LISTED IN THE ORDER (V IDEO , AR/VR, AUTO D RIVE , I OT, G AMING ). VALUES MATCH THE ACCOMPANYING REPRODUCIBILITY PACKAGE .

Symbol Symbol

Meaning

Value

Players and coalitions I Full player set {1, . . . , M, NO} P + (d), Unconstrained, P 0 (d) SLA-bound SPs S opt (d) Oracle-optimal coalition Time Dinv T

Investment horizon [day] Intra-day timeslots

M = 5 SPs + 1 NO — —

Value Eq. (1) Eq. (8) Eq. (7) Eq. (5)

Shapley value ∆i (d) Marginal contribution Def. 11 [vu] φ+ Benchmark Shapley value Eq. (10) i (d) φ− Operational Shapley value Eq. (11) i (d) R, K Hoeffding bound, sample Eq. (12) size

365, 1095 96

Traffic process Λi0 Initial traffic scale [req/s] (400, 250, 150, 800, 350) Λid Daily traffic scale [req/s] GRW, Eq. (2) µi GRW drift [1/day] (8, 12, 5, 6, 10) ×10−4 √ σi GRW volatility [1/ day] (40, 60, 50, 30, 45) × 10−3 F Intra-day profile sum 96.0 Capacity and SLA C Deployed capacity [mc, 3100.394 millicores] q Reference marginal value 0.10 [vu/mc] ξ Saturation parameter 10−3 [1/mc] hi SLA floor [mc] (30, 300, 1500, 0.3, 112.5) P Aggregate SLA floor [mc] 1942.8 (62.7% of i hi C) h∗i (d) Optimal allocation [mc] Eq. (6) ∗ λ (d) Active shadow price Coalition-dependent [vu/mc] Utility and revenue Udi (hi ) Daily utility [vu] βi Normalized value coefficient [vu/(req/s)]

Meaning

Coalition value vd (S) Constrained coalition value [vu] ṽd (S) Net value (cost-adjusted) [vu] v i (d) Unconstrained individual value Ai , Xi (d) Coefficient, profitability index

Eq. (3) (8, 15, 25, 4, 12) × 10−3

Value-investing rule Vi (d) Value ratio (active SP) Eq. (14) MoSi (d) Margin of safety (inactive Eq. (15) SP) − θmin , θmin Base margins 0.050, 0.025 κ, κ− Risk-aversion multipliers 0.10, 0.05 ζijoin , Observed action times — ζileave Audit and trust α Nominal audit frequency α∗ Fixed-state criterion optimum Bd Operational gain upper bound [vu] Πsuff Sufficient penalty [vu] d ca Audit cost per occurrence [vu] ρ Trust risk aversion δ̂(d), τ (d) Audit pass rate, trust factor ε Scalar test perturbation Efficiency metrics and reproducibility PoD, PoS Decentr. price, dynamic/static ratio — Random seed

0.15 0.9140 Mean 114.201 Mean 10.745 at α∗ 22.5 0.05 Eq. (17) −15% Eq. (22) 4

Abbreviations: NO, Network Operator; SP, Service Provider; SLA, service-level agreement; GRW, Geometric Random Walk; TU, transferable utility; MoS, margin of safety; PoD, Price of Decentralisation; PoS, dynamic/static value ratio; KKT, Karush–Kuhn–Tucker; CV, coefficient of variation; FOC, first-order condition; CAPEX, capital expenditure; AR/VR, augmented/virtual reality; IoT, Internet of Things; mc, millicore; vu, normalized value unit.

(ii) Operational game. For vd in (1), in either capacity regime, let Ωm be the set of player orderings, π ∈ Ωm one ordering, and Siπ the players preceding i. For i ∈ / T , write ∆i (T , d) = vd (T ∪ {i}) − vd (T ). The Shapley value is φ− i (d) =

1 X ∆i (Siπ , d). m!

(11)

π∈Ωm

The superscripts + and − identify the benchmark and operational games, respectively; they do not indicate payoff signs. For the realized coalition, φi (d) = φ− i (d) in the Stage-I contract. The symbol φ± denotes the NO’s allocation in the NO corresponding game. A player’s Shapley value is negative precisely when its permutation-averaged marginal contribution is

negative. The proof is given in Appendix D. a) Scalability Beyond the Enumerated Instance: Caching all coalition values requires O(2M ) allocation solves; evaluating every Shapley component by weighted subsets requires O(M 2M ) arithmetic operations for one active game and is used here since M = 5. Computing the full payoff table for all active SP subsets, as required by the audit bound, takes O(M 3M ) weighted-subset operations. For larger M , the exact sum is replaced by the Monte Carlo estimator [18], optionally stratified [19], avoiding exhaustive enumeration for a fixed sample count. A sampled payoff near zero requires an uncertainty check before its sign can be interpreted (Remark 9).

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

6

PM Proposition 8 (Sampling complexity). Let R = j=1 βj Λjd F . The last approximation requires σi2 Dres ≪ 1. It motivates a Since each operational coalition value lies in [0, R], every benchmark-payoff approximation only when the high-demand marginal contribution lies in [−R, R]. Here R bounds the approximation g(Xi ) ≈ Xi is also suitable. magnitude of a marginal contribution; K is the sample count, Proof. The conditional log increment has variance σi2 Dres . δerr > 0 the additive-error tolerance, and ηfail ∈ (0, 1) the The log-normal moment formula gives the exact CV in (13). sampling failure probability. The notation Pr denotes probExpanding ex − 1 at zero gives the stated small-variance ability. Drawing K i.i.d. permutations π1 , . . . , πK uniformly approximation. and averaging the marginal contributions of SP i yields an − unbiased estimator φ̂i (d) with, by Hoeffding’s inequality, VII. VALUE -I NVESTING D ECISION RULE   2
Kδerr − − a) Value Ratio and Margin of Safety: (12) Pr |φ̂i (d) − φi (d)| ≥ δerr ≤ 2 exp − 2R2 , Definition 11 (Marginal contribution). ∆i (d) = vd (S(d) ∪ −2 so K = O(R2 δerr log(1/ηfail )) permutations suffice for addi- {i}) − v (S(d) \ {i}). For i ∈ S(d) this is the value lost on d tive accuracy δerr with probability 1 − ηfail , giving total cost departure; for i ∈ / S(d), the value gained on entry. O(K · M ) water-filling solves, independent of 2M . Definition 12 (Value ratio and margin of safety). The pubProof. Each sampled marginal contribution lies in [−R, R] lished estimates satisfy v̂(d) ≥ 0, and ∆ ˆ i (d) estimates the and the permutation is uniform, so the sample mean is entry/departure marginal. The dimensionless trust multiplier unbiased for (11); (12) is Hoeffding’s bound for bounded τ (d) is defined in Section VIII. For v̂(d) > 0, define the value i.i.d. terms. Inverting the exponential gives the stated K. For ratio Vi (d) for active i ∈ P(d) by simultaneous accuracy for all M +1 players, replace the failure ˆ i (d) τ (d) |P(d)| ∆ probability by ηfail /(M + 1) using the union bound. The imVi (d) = . (14) v̂(d) plementation reports this simultaneous Hoeffding radius. For an inactive SP, define the margin-of-safety ratio MoSi (d) Remark 9 (Interpretation of negative Shapley payoffs). A by negative operational Shapley value is a theoretical payoffˆ i (d) ∆ allocation signal: the SP’s marginal contribution, averaged τ (d), (15) MoSi (d) = v̂(d) over player orderings, is negative. In the TU model, φ− (d) < i with v̂(d) the NO’s declared coalition value and τ (d) the trust 0 prescribes an outgoing transfer of magnitude |φ− i (d)|; it does not by itself imply a monetary charge. The participa- factor of Section VIII. Both rules use the declared v̂(d) rather tion rule responds to marginal-contribution signals; it does than the unobservable true value vd (S(d)), consistent with the not explicitly optimize cumulative fees or future individual partial-information structure of Section III. In (14) the ratio ˆ i (d)/v̂(d) measures SP i’s contribution relative to the payoffs. Negative Shapley and the departure criterion need |P(d)| ∆ not coincide. Implementing this transfer as an access fee, average member contribution v̂(d)/|P(d)|. resource-reservation charge or SLA-related cost requires a The Graham analogy motivates the choice of marginal contract specifying payment, enforcement and recovery terms. contribution as a value signal. The leave rule compares it Truthful declarations remain subject to the audit assumptions with average current coalition value, whereas the join rule of Theorem 21. compares the incremental value with a fraction of total coalition value. These are distinct operational criteria, not a VI. P ROPERTIES OF THE S HAPLEY VALUE P ROCESS derived maximization of individual Shapley payoff. Average The benchmark Shapley payoff is a nonlinear function of coalition value supplies a common scale for the marginal log-normal traffic. In the high-demand limit, g(Xi ) ∼ Xi , signal, not a fair-share entitlement. This choice can remove giving an approximately log-normal payoff. The following positive contributors; Section XII reports the resulting loss calculation concerns terminal traffic uncertainty, not the vari- when capacity is abundant. ance of cumulative operational Shapley payments. The key result, used in Section VII to calibrate the margin-of-safety threshold, is the residual-horizon volatility. Intuitively, an SP’s benchmark payoff is approximately proportional to its own traffic at high demand, so its uncertainty compounds with the volatility σi and the length of the residual horizon; the margin of safety must therefore widen with both. Proposition 10 (Coefficient of variation (CV)). Let Dres = Dinv − d be the residual horizon. For a positive random p variable Z, define CV(Z) = Var(Z)/E[Z], where Var and E denote variance and expectation. Conditional on the current traffic scale, the GRW gives p 2 p CV(Λid+Dres | Λid ) = eσi Dres − 1 ≈ σi Dres . (13)

Definition 13 (Join and leave rules). At day d, θi (d) > 0 and θi− (d) > 0 denote the join and leave margin parameters, specified below. join (i ∈ / S(d)): MoSi (d) ≥ θi (d), ˆ i (d) > 0, and P ∆ j∈P(S(d))∪{i} hj ≤ C; leave (i ∈ S(d)): Vi (d) ≤ 1/(1 + θi− (d)). When v̂(d) = 0, the rules are ˆ i (d) > 0 and evaluated by cross multiplication: join requires ∆ ˆ ˆ i (d) ≤ τ (d)∆i (d) ≥ θi (d)v̂(d); leave requires |P(d)|τ (d)∆ − v̂(d)/(1 + θi (d)). Each operational day starts from the preceding day’s coalition. The implementation processes exits, then entries, in the fixed order Video, AR/VR, AutoDrive, IoT, Gaming, recomputing coalition values after each change. An SP may exit and re-enter within the same day. Only this single ordered sweep is used for the reported daily values; the frozenday iterations below are diagnostic. Baseline declarations are

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

ˆ i = ∆i . Exits precede entries so truthful, v̂ = vd (S) and ∆ that released capacity is available to prospective entrants. b) Threshold Calibration: Definition 14 (Threshold calibration). The join threshold is p θi (d) = θmin + κσi Dinv − d, (16)

7

IX. E QUILIBRIUM A NALYSIS Definition 16 (Observed stopping times). For action a ∈ {join, leave}, let ζia be the first operational day on which the ordered rule executes action a for SP i. If no such action occurs by Dinv , set ζia = ∞ and record it as unobserved within the horizon. No almost-sure eventual action is asserted.

Definition 17 (Value-investing equilibrium). An active coaliwhere θmin > 0 is the base margin and κ > 0 is a tion S ∗ (d) is an equilibrium if no active SP wishes to leave dimensionless sensitivity parameter. This is a design rule and no inactive SP wishes to join (no feasible join or leave motivated by the small-variance scaling in Proposition 10; it action in Definition 13 is eligible). is not an exact operational-payoff risk bound. The parameters remain tunable, and their sensitivity is evaluated numerically. Theorem 18 (Finite detection of repeated states). Fix day d, its traffic, trust and thresholds. Let B denote one deterministic Remark 15 (Asymmetric thresholds). The leave threshold ordered sweep and k the sweep index. Iterating Pk+1 = B(Pk ) √ − uses κ− < κ: θi− (d) = θmin + κ− σi Dinv − d, where on the power set 2{1,...,M } reaches a repeated state after at − θmin > 0 is the leave base margin and κ− > 0 its volatility most 2M transitions. The resulting orbit has some period p ≥ − coefficient; the experiments use θmin < θmin and κ− < κ. 1. A period-one sweep state need not satisfy Definition 17, These coefficients set different admission and retention criteria. because exits and entries can cancel within a sweep. Since the two rules use different ratios, their asymmetry does M not by itself prove a hysteresis band or prevent within-day exit Proof. Among 2 + 1 successive states, two coincide. Determinism then makes the subsequent orbit periodic. Equality of and re-entry. Experiments use κ = 0.10, κ− = 0.05. sweep endpoints does not exclude intermediate membership changes. VIII. P ROBABILISTIC AUDITING M ECHANISM Proposition 19 (Conditional convergence to equilibrium). Fix a) Trust Factor: Let α ∈ (0, 1] be the audit probability, the day’s traffic, trust, thresholds, SP order and truthful signals. Π ≥ 0 the per-instance penalty, ca > 0 the cost of one Let P be the initial feasible SP set and K the sets reachable 0 audit, and ρ ∈ (0, 1) the trust parameter. Penalties and from P through eligible individual moves. For each SP i, let 0 costs use vu. At each day, an independent audit is conducted L be its largest departure marginal over eligible exits in K, i with probability α. Conditional on auditing, any misreport is and J its smallest entry marginal over eligible entries. Use i detected with probability 1; on detection the inflated outcome L = −∞ or J = +∞ for an empty exit or entry set. If L < i i i is voided and the NO pays a per-instance penalty Π [vu]. Let J for every SP, repeated sequential sweeps from P reach an i 0 npass (d) and naudit (d) count passed and completed audits equilibrium after at most |K| − 1 membership changes. available before day d’s decisions. Each SP maintains the pass , where Proof. Choose finite constants ai with Laplace-smoothed audit pass rate δ̂(d) = nnaudit(d)+1 P Li < ai < Ji and (d)+2 Beta(1, 1) is the uniform prior for the audit-pass probability. define the potential Φ(P) = wd (P) − i∈P ai . Each eligible The smoothed rate is its posterior mean. Smoothing gives entry increases it by ∆i − ai > 0; each eligible exit by ai − δ̂(0) = 1/2 for SPs entering before any audit, preventing ∆i > 0. Thus no set repeats after an eligible move. Every sweep tests all SPs, so termination implies no eligible move. collapse on a single early failure. The trust factor is τ (d) = 1 − ρδ̂(d) ∈ [0, 1 − ρ],

(17) For seed 4 over 1095 days, frozen-day diagnostics find 1093 period-one orbits and two period-two orbits, with mean 1.128 and maximum three transitions to first repetition. Only 97 of the 1095 realized daily endpoints satisfy Definition 17. Exact enumeration finds no individual equilibrium on the other 998 days. The same 97 days satisfy the potential condition on reachable sets. A general convergence characterization remains future work.

with ρ ∈ (0, 1) a risk-aversion parameter; τ increases strictly √ in δ̂. With no audit history, τ = 1 − ρ; with an increasing all-pass history, τ approaches 1 − ρ from below. The baseline uses ρ = 0.05. An audit performed after day d’s decisions updates trust for day d + 1. Delayed or erroneous trust updates are studied separately from the idealized one-day financial settlement. b) Numerator Placement of τ : Discounting the declaration instead (v̂ → τ v̂) would be perverse for positive X. S TRATEGY-P ROOFNESS marginal signals: as τ → 0 the denominator of Vi vanishes, Vi diverges, and joins are encouraged. For positive marginal Lemma 20 (NO’s gain from benchmark expansion). In the signals, placing τ in the numerator reduces admission and separable benchmark, if a declaration induces a feasible retention ratios when trust falls. This can change coalition expansion P by a set J of SPs without departures, the NO’s gain membership, but it does not by itself prove that the NO loses is 21 i∈J v i (d), strictly positive when this sum is positive. value, since an excluded SP may have a negative marginal This statement does not exclude profitable misreporting in contribution. either regime of the operational game.

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

Proof. The result follows by subtracting the NO’s benchmark allocation before entry from its allocation after entry in (10). Theorem 21 (Strategy-proofness). Fix the current state and other players’ responses. For a risk-neutral NO maximizing its current-day expected payoff, assume perfect detection upon audit, no penalty for truthful reporting, and rollback to the truthful outcome minus Π. Let Rd be the set of admissible false declarations and r a complete declaration of coalition values and marginal signals within the sweep. Truth-telling is weakly optimal against every admissible misreport iff Π ≥

1−α sup G(r), α r∈Rd

(18)

Here G(r) is the NO’s operational Shapley gain if declaration r goes undetected. The scalar ε is reserved for the experiment v̂ = (1 + ε)v, with truthful marginal signals. PFor a benchmark expansion without departures, G+ (r) = 12 i∈J (r) v i (d). For the operational game, G uses the induced coalition and its verified operational Shapley allocation. Reports affect admission signals, not the settlement formula itself. This excludes direct payment diversion and assumes enforceable settlement. The proof is given in Appendix E. Corollary 22 (Minimum penalty and optimal audit frequency). Define the nonnegative worst-case operational daily gain by Π∗0 (d) = max{0, sup G(r; d)}.

(19)

r∈Rd

P In the separable benchmark, this equals 12 i∈S(d) v i (d) only / if the admissible reports induce expansions without departures and can jointly admit all positive-value inactive SPs. The corresponding strategy-proof penalty threshold from Theorem 21 is then 1−α ∗ Π∗ (α; d) = Π0 (d). (20) α Letting ca > 0 [vu] be the cost of one audit and assuming 0 < E[Π∗0 ] < ∞ for a fixed distribution of reference states, the audit frequency minimizing the specified design criterion Caudit (α) = α ca + (1 − α) E[Π∗ (α; d)] over α ∈ (0, 1] is s E[Π∗0 ] ∗ α = . (21) ca + E[Π∗0 ] For implementation, let Bd be the maximum increase in the NO’s verified operational payoff over all feasible destination coalitions, relative to the truthful outcome. For the Stage-I contract, use total receipts xNO instead of the operational account when bounding deviations; the numerical audit retains the operational account. This gives Bd ≥ Π∗0 (d), possibly strictly, because some destinations may be unreachable. Replacing Π∗0 (d) by Bd in (20) gives a sufficient daily penalty. For conditional detection probability pdet ∈ (0, 1], replace α by αpdet under the same immediate rollback assumptions. Numerical calibration is reported in Section XII; the bound is not asserted to be the minimum over attainable reports. Full derivation in Appendix E.

8

XI. P RICE OF D ECENTRALISATION Definition 23 (Oracle-optimal coalition). S opt (d) = arg maxS feasible vd (S), the same-day full-information centralised optimum. S opt (d) knows λ∗ (d) and {Λid } but is not clairvoyant about future demand. Computing it requires every SP’s private parameters, unavailable to individual SPs. Definition 24 (Price of Decentralisation and dynamic/static ratio). The label PoS denotes this paper’s dynamic/static value ratio; it is not the standard equilibrium-based Price of Stability. P P vd (S opt (d)) d vd (S(d)) d ≥ 1, PoS = P . (22) PoD = P d vd (S(d)) d vd (I) PoD close to 1 means the rule recovers most of the achievable value despite partial information. PoS > 1 means the dynamic coalition strictly outperforms the static grand coalition, an outcome enabled by non-monotonicity of the operational coalition value under mandatory SLA allocations. XII. N UMERICAL R ESULTS1 a) Setup and Operating Regime: The simulations use M = 5 SPs corresponding to video streaming, AR/VR, autonomous driving, IoT telemetry and cloud gaming. Capacity is C = 3100.394 mc (rounded), the aggregate reservation is 1942.8 mc, and horizons are Dinv ∈ {365, 1095} days. The allocator uses the sorted active-set solution of the KKT system; tests compare its objective and feasibility with an independent constrained numerical optimizer. All daily coalition values and operational Shapley allocations are evaluated exactly. The complete parameter set is in Table I. Results aggregate operational days 1, . . . , Dinv ; day zero is initialization. Thirty seeds, 0, . . . , 29, are used, with seed 4 retained for the detailed trajectory. Strategies share the same traffic path within each seed and horizon. The two horizons use the original horizondependent random-array protocol and are not common prefixes of one trajectory. Grand-coalition shadow prices exceed q on all 1095 days for seed 4, with mean 0.4905 vu/mc; activecoalition prices exceed q on 96.895% of days. b) Three-Year Run: Figure 2 reports coalition membership, daily and cumulative coalition value over the three-year horizon. The dynamic coalition overtakes the static grand coalition at d = 473 and ends with PoS = 1.124 and PoD = 1.057 (94.6% of the full-information optimum). c) Horizon comparison: For seed 4, the dynamic/static ratio is 1.2385 at one year and 1.1242 at three years. Because these runs are not pathwise continuations, this comparison does not establish an asymptotic trend. Across 30 seeds, the median ratios are 1.0876 and 1.1327; the first-to-thirdquartile intervals, containing the middle half of the runs, are [0.9945, 1.1965] and [1.0688, 1.2558]. At one year, seed 4 gains 23.9%, above the third-quartile gain of 19.7%: it shows a more favorable outcome than most runs. The dynamic rule exceeds Grand in 22 of 30 one-year runs and 28 of 30 threeyear runs. 1 Code and data: https://github.com/patan3saro/EdgeValueInvesting-Sim.

(a) Coalition membership over 3 years

365

730

1095

Grand

Value investing

2000 1000 1

365

730

1095

Day d (c) Cumulative coalition value

1 0 1

Grand Random

Threshold Value investing

Oracle

2000 1000 1

Grand Value investing Oracle Cumulative crossover: day 473

365

730

1095

Day d

Fig. 2. Three-year horizon: membership, daily value, and cumulative comparison. The dynamic coalition overtakes the static grand coalition at d = 473. Final PoS = 1.124, PoD = 1.057.

vs Grand [%]

2

(a) Daily value, seed 4 (21-day moving average) 3000

Cumulative [10 6 vu]

3000

9

365

730

1095

730

1095

Day d

(b) Daily coalition value

Cumulative [10 6 vu]

Daily value [vu]

Video AR/VR AutoDrive IoT Gaming 1

Daily value [vu]

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

2

(b) Cumulative value, seed 4

1 0 1

365

Day d

50

(c) Cumulative gain: seed-4 bars and 30-seed dispersion Median and interquartile range (30 seeds)

0

+0.0%

+0.0%

+0.0%

+12.4%

+18.8%

Threshold

Grand

Value investing

Oracle

-28.3%

Static reference

Random

Fig. 3. Five strategies over three years. (a) Daily values, smoothed over 21 days. (b) Cumulative values. (c) Gain over Grand: seed-4 bars, 30seed medians and interquartile ranges. The static reference equals Grand. Smoothing affects display only; all totals use unsmoothed operational days.

Cumulative share [10 3 vu] Cumulative [10 6 vu]

Daily value [vu]

d) Strategy Comparison: Figure 3 compares five strategies over three years, with seed-4 trajectories and dispersion across 30 seeds. Reversing the update order reduces the (a) Daily value (14-day moving average) median dynamic/static ratio from 1.133 to 0.686. Table II 3000 Grand Value investing and Figure 3 therefore evaluate the specified exit-first rule. 2000 The value-investing rule gains 12.4% over Grand and captures 66.1% of the oracle’s available gain (18.8% over Grand). The 1000 threshold-only comparator admits SP i when Xi (d) > 1.05, 1 365 730 1095 using only its private profitability signal. It reproduces Grand Day d in the seed-4 three-year run (Table II), illustrating the lim(b) Cumulative coalition value itation of ignoring displaced capacity. The marginal signal Grand 1.5 Value investing includes a capacity externality absent from the individual 1.0 profitability index. An active SP is coalitionally harmful when 0.5 vd (S) − vd (S \ {i}) < 0. The individual index Xi does not +12.4% over Grand 0.0 account for the capacity displaced by its mandatory allocation. 1 365 730 1095 Consequently, individual profitability alone does not generally Day d determine whether participation increases coalition value. The (c) Exact cumulative Shapley payments value-investing rule succeeds because its decision variable is Grand counterfactual Active coalition 400 the marginal contribution ∆i (d), which prices the capacity externality through λ∗ (d), while the threshold in Definition 14 200 controls admission conservatism; its effect is assessed by sen0 sitivity tests. The random policy loses 28.3% on this trajectory: Gaming Video AR/VR AutoDrive IoT the membership selection rule matters for the observed gain. e) Comparison with the Static Grand Coalition: Figure 4 Fig. 4. Dynamic membership versus fixed Grand. (a) Daily value, smoothed compares the dynamic rule with fixed grand-coalition member- over 14 days. (b) Cumulative values, with a final +12.4% gain over Grand. ship under the same operational capacity model. This isolates (c) Exact operational Shapley payments: Grand counterfactual and realized active coalition, both in normalized value units. the effect of participation decisions. It is not an independent numerical reproduction of the investment optimization in [3]. The cumulative dynamic advantage becomes positive at day 473 and finishes at 12.4%; daily changes in the gap can grand-coalition counterfactual. Its participation rate is 20.2%, have either sign. Panel (c) distinguishes actual active-coalition compared with 73.8% for gaming and 74.1% for AR/VR. payments from the counterfactual payments under fixed grand- The departure rule uses marginal contributions, so a negative coalition membership. Autonomous driving, whose reservation counterfactual Shapley payoff is an economic interpretation, is 1500 mc, receives a cumulative +16,426 vu in the realized not the direct decision variable or a realized charge while dynamic coalition and would receive −45,844 vu in the inactive.

(b) Audit design criterion

103 102 101 100 0.15

0.50

1.00

Audit frequency ®

2000

® ¤ = 0:914 C = 21:49 vu

1500 1000 500 0

0.15

0.50

TABLE II T HREE - YEAR CUMULATIVE VALUES FOR SEED 4 AND RATIOS TO G RAND ACROSS 30 SEEDS . Q1 AND Q3 ARE THE FIRST AND THIRD QUARTILES .

Strategy Random Threshold Grand Value investing Oracle

-20%

Seed 4 [vu]

Ratio: median [Q1,Q3]

1,156,990 1,614,270 1,614,270 1,814,795 1,917,453

0.726 [0.682,0.739] 1.060 [1.015,1.166] 1.000 [1.000,1.000] 1.133 [1.069,1.256] 1.199 [1.143,1.322]

+20%

Baseline

− θmin

ρ

95 94 −

θmin

(a) Parameter changed separately

Audit frequency ®

Fig. 5. Operational audit calibration at fixed seed-4 reference states. (a) Mean sufficient daily penalty for detection probabilities 1 and 0.7. (b) The stated design criterion under perfect detection, minimized at α∗ = 0.9140, with value 21.489 vu. Vertical lines mark α = 0.15 and α∗ .

10

96

1.00

Gain over Grand (%)

Detection 1.0 Detection 0.7

Design criterion [vu]

Mean penalty [vu]

(a) Sufficient penalty

Value / oracle (%)

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

60 40 20 0 0.8

1

1.2

2

(b) Capacity relative to C

4

Fig. 6. Sensitivity across 30 three-year runs. (a) One policy parameter varies at a time. (b) Capacity varies with the policy fixed. Points show medians; bars in (b) contain the middle half of the runs. TABLE III PARTICIPATION SENSITIVITY: MEDIAN RESULTS AT −20%/+20% OF EACH PARAMETER ; CHURN AND EVENTS ARE AVERAGED PER DAY.

f) Operational Audit Calibration: For each seed-4 operational day, the maximum NO payoff gain over all 32 Parameter Active Churn Events destination coalitions bounds every report-induced memberBaseline 2.48 0.123 3.22 ship outcome under verified settlement. The mean bound is κ 2.54/2.41 0.132/0.116 3.35/3.10 B̄ = 114.201 vu and its maximum is 380.564 vu. Here κ− 2.61/2.42 0.126/0.129 3.65/3.05 −1 PDinv B̄ = Dinv B . The sufficient penalty at day d is denoted d d=1 θmin 2.51/2.45 0.127/0.121 3.30/3.15 − by Πsuff θmin 2.56/2.41 0.127/0.126 3.50/3.05 d (α) = (1 − α)Bd /α. With ca = 22.5 vu and the ρ 2.35/2.70 0.127/0.133 2.83/4.00 reference states generated at α = 0.15, the design criterion gives α∗ = 0.9140, a mean sufficient penalty of 10.745 vu, a maximum of 35.805 vu, and criterion value 21.489 vu. This varies the audit parameter at fixed reference states, rather ρ = 0.04, 0.05, 0.06, median α∗ is 0.896, 0.898, 0.893. Each ρ than re-simulating membership at α∗ . The daily penalty is regenerates coalition states at nominal audit probability 0.15; state-dependent; its mean is not a uniform guarantee. For those states are then fixed to evaluate the audit criterion. Thus each tested audit/detection pair, the settlement check covers ρ affects α∗ through participation, not directly through its 1095 × 32 = 35,040 destinations. Expected deviation gains formula. We also test standardized Student-t3 log-innovations, are nonpositive up to numerical tolerance under perfect or compound-Poisson log-demand jumps (rate 0.03/day, Gaus0.7 detection probability, with the corresponding sufficient sian jump standard deviation 0.35), weekly modulation, Zipf penalty. These are conditional daily guarantees with no false initial popularity (exponent 1.2), Pareto initial popularity positives and full recovery; they do not establish repeated- (shape 1.5), and 32 stationary active/idle (ON/OFF) sources game truthfulness under delayed or erroneous audit feedback. per SP with Pareto durations (shape 1.4), following Taqqu et al. [20]. The finite ON/OFF aggregate modulates the GRW; g) Robustness and computational checks: Across 30 the aggregation limit motivates persistence across scales, withthree-year seeds, varying each of the five policy parameters out establishing exact self-similarity of the resulting demand. by ±20% gives median dynamic/static ratios from 1.1227 Respective median dynamic/static ratios are 1.1499, 1.1996, to 1.1472. Figure 6(a) covers all five parameters. Larger 1.1328, 1.0411, 1.0111, and 1.1479. Changing initial service κ reduces participation and can exclude beneficial services. popularity reduces the gain most. Student-t log-increments Table III reports mean active SPs, daily endpoint changes have no finite positive exponential moment, so the GRW (Churn), and all within-day entries and exits (Events). Sim- mean formula does not apply. With a 10% false-positive audit ilar total value can conceal different participation patterns. rate and 30-day additional feedback delay, median mean trust At 0.8C, median selection gain is 35.3%; at 2C, selection falls from 0.9452 to 0.9249, and the median dynamic/static loses 3.7% (Figure 6(b)). Extra capacity reduces competi- ratio from 1.1327 to 1.1188. These tests concern trust and tion, while the admission margins still exclude services. For membership; Appendix E states separately the conditions for

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

financial deterrence. Single-day synthetic Shapley tests use M = 50, 100 and 128 or 512 permutations. Their simultaneous Hoeffding radii can be too wide to certify the sign of a small payoff; multi-year large-coalition simulations remain future work. XIII. C ONCLUSION We developed a dynamic value-investing coalitional game for edge computing co-investment that simultaneously addresses determinism, static membership, and full-information assumptions of prior work. The two-stage decomposition separates the irreversible CAPEX from the daily operational decisions; mandatory SLA allocations can produce negative operational Shapley payoffs, whose implementation as fees requires contractual settlement; the margin-of-safety threshold, motivated by a benchmark uncertainty approximation, guides participation under partial information; and the audit-and-trust mechanism provides a conditional daily truthfulness guarantee for the NO. Dynamic membership can improve operational value by releasing scarce capacity from services whose reservations displace more valuable uses. The gain depends on the update order and can disappear as capacity becomes abundant. The most direct extensions for future work are: a nontransferable-utility formulation, when SPs cannot freely transfer payoffs; the integration of network delay into effective deadlines and energy costs into the per-SP utility; the analysis of PoS as Dinv → ∞; and a multi-NO generalisation. Further work includes calibrated queueing and latency models, calibration of investment participation constraints, joint selection of κ, θmin and ρ, general equilibrium-convergence conditions, and multi-year simulations with M = 50 or 100 SPs and competing or cooperating NOs.

11

using Yi = Xi q. For Xi ≤ 1, ∂h Ui (0) = qXi ≤ q; concavity therefore gives the optimum h = 0 and value zero. Together these cases yield (7).

A PPENDIX B S EPARABILITY Proof of Proposition 5. Knife-edge. Under the interiorallocation assumptions of Proposition 5, at λ∗ = q we have h∗i = ξ −1 ln Xi for every member and Udi (h∗i ) = v i (d) + qh∗i byPthe derivation of (7). Summing over P(S) and subtracting q i h∗i gives (9). ∗ Interior allocation away from the knife-edge. With e−ξhi = λ∗ /(Xi q) the same substitution yields Udi (h∗i ) − qh∗i = v i (d) − (q/ξ) g(λ∗ /q), where the remainder depends on S only through λ∗ (S, d) and not on i. Hence ṽd (S) =

X

v i (d) −

i∈P(S)

|P(S)| q g λ∗ (S, d)/q . ξ

(23)

Since g ′ (1) = 0 and g ′′ (1) = 1, expanding g about u = 1 gives g(λ∗ /q) = 12 (1 − λ∗ /q)2 + O((1 − λ∗ /q)3 ), hence the explicit bound

ṽd (S)−

X

v i (d) =

i∈P(S)

2
|P(S)| q−λ∗ +O (q−λ∗ )3 , (24) 2ξq

When an SLA floor binds, the interior expression must be replaced by the corresponding boundary allocation. The comparison between λ∗ and q alone does not determine whether this occurs.

A PPENDIX A KKT S OLUTION AND I NDIVIDUAL VALUE Proof of Proposition 4. For a fixed day, we may suppress the A PPENDIX C day index in utility and multiplier notation. By Lemma 1 the C ONDITIONAL S UBMODULARITY objective of (1) is strictly concave on a convex polyhedron, so the KKT conditions are necessary and sufficient [21]. Proof of Theorem 6. Suppress the day index. Let W (P, c) With multipliers λ ≥ 0 (capacity) and νi ≥ 0 (SLA floor), denote the optimal utility of SP set P at capacity c, and λP (c) −ξhi i stationarity reads νi = λ − Yi e with Yi ≜ ξβi Λd F = its capacity multiplier. Let HP (λ) be total requested allocation Xi (d) q by (5). For an interior SP (νi = 0) inversion gives at price λ. For SP sets A ⊆ B, define ∗ −1 ∗ ∗ hi = ξ ln(Xi q/λ ); an SLA-bound SP sits at hi = hi , −ξhi ∗   which occurs iff Yi e ≤ λ . Together these give (6). The X 1 Xi q i HP (λ) = max hi , ln . capacity constraint binds because each Ud is strictly increasing. ξ λ i∈P Finally, let H(λ) denote the total allocation requested at price P λ. Then H(λ) ≜ i max{hi , ξ −1 ln(Xi q/λ)} is continuous and weakly decreasing, with H → ∞ as λ → 0+ and Since HA (λ) ≤PHB (λ), capacity clearing gives λA (c) ≤ P λB (c) for c > / B, let i∈B hi ; set λ∅ (c) = 0. For j ∈ H → i hi < C as λ → ∞. Continuity P gives a solution; HP = [h , C − P h ] be its feasible allocation interval. j i∈P i H is strictly decreasing whenever H > i hi , so the solution The marginal contribution of j is is unique. ( ) Z C Derivation of (7). v i (d) is the value of maxh≥0 [Udi (h) − qh], max Uj (h) − λP (c) dc , in which SP i buys capacity at the reference value q alone. h∈HP C−h −ξh For Xi > 1, the first-order condition (FOC) Yi e = q gives ◦ the individual optimizer h◦i = ξ −1 ln Xi and e−ξhi = 1/Xi , by the envelope theorem. Since HB ⊆ HA and the integrated so shadow price is no smaller for B, the maximum for B cannot exceed that for A. This proves submodularity. Udi (h◦i ) − qh◦i = qξ (Xi − 1) − qξ ln Xi = qξ g(Xi ),

MANUSCRIPT SUBMITTED TO IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT

A PPENDIX D B ENCHMARK AND O PERATIONAL S HAPLEY VALUES Proof of Theorem 7. For the benchmark v̄d , SP i has marginal contribution v i (d) exactly when the NO precedes it. This occurs in half the permutations, proving (10); efficiency gives the NO’s share. Each nonnegative v i (d) weights the unanimity game on {i, NO}, so their sum is supermodular and has a nonempty core [22]. For the operational game vd , the general Shapley formula gives (11) in both capacity regimes. Each predecessor coalition is evaluated using (1); coalition values without the NO are zero. A PPENDIX E S TRATEGY-P ROOFNESS AND C OST-O PTIMAL AUDIT Proof of Theorem 21. Let G(r) be the NO’s payoff change when a false declaration r goes undetected. An audit occurs with probability α and then voids the inflated outcome and levies Π, so E[φNO | r] − φNO = (1 − α) G(r) − α Π. Under the daily-payoff assumptions of Theorem 21, truthtelling is weakly optimal iff this is non-positive for every admissible r, which is (18). For a feasible expansion without departures inPthe separable benchmark, Theorem 7(i) gives G+ (r) = 21 i∈J (r) v i (d). This expression does not replace the operational gain in general. Audit errors and delay. Let pdet > 0 be detection probability conditional on auditing, and brec ∈ (0, 1] the discount applied to recovery and penalty collection. With no false positives, expected deviation gain is (1 − αpdet brec )G(r) − αpdet brec Π. Replacing G by Bd gives the sufficient penalty Π ≥ (1−αpdet brec )Bd /(αpdet brec ). Without recovery, the numerator is Bd . False positives require comparison with the truthful report’s sanction; observation errors that corrupt the reference values also affect Bd . Pending audits do not update trust until their results arrive. These statements concern daily financial incentives, not continuation payoffs. Proof of Corollary 22. Use the operational maximum in (19) and set the penalty at (20). The following minimization concerns the stated design criterion, not the expected penalties paid under truthful play. Writing E ≜ E[Π∗0 (d)] and setting Π at that threshold, the design-criterion value is 2

(1−α) Caudit (α) = α ca + (1 − α) 1−α E, (25) α E = α ca + α ′ ′′ with Caudit (α) = ca − E (1 − α2 )/α2 and Caudit (α) = 3 2E/α > 0. The map is strictly convex, so the stationary point is the unique minimiser: ca α2 = E(1 − α2 ) gives (21). The same minimization applies to a fixed reference distribution of Bd . Varying the audit frequency may also change future trust and coalition membership, so this calculation is a frozenstate design criterion rather than a repeated-game cost optimum.

ACKNOWLEDGMENT The author used ChatGPT (OpenAI) for language editing and LATEX preparation throughout the manuscript, for drafting the clarifications in Sections III and V, and for assistance with simulation and figure-generation code and numerical

12

consistency checks supporting Section XII. The author retains full responsibility for the manuscript’s scientific content and final presentation. R EFERENCES [1] M. Satyanarayanan, “The emergence of edge computing,” Computer, vol. 50, no. 1, pp. 30–39, 2017, doi: 10.1109/MC.2017.9. [2] International Data Corporation, “New IDC spending guide forecasts edge computing investments will reach $232 billion in 2024,” press release, Mar. 14, 2024. [3] R. Patanè, A. Araldo, T. Chahed, D. Kiedanski, and D. Kofman, “Coalitional game-theoretical approach to coinvestment with application to edge computing,” in Proc. IEEE CCNC, 2023, pp. 517–522, doi: 10.1109/CCNC51644.2023.10060093. [4] A. Sakr, A. Araldo, T. Chahed, R. Patanè, and D. Kofman, “Coinvestment under uncertainty: Coalitional game formulation and application to edge computing,” in Proc. IEEE ICC, 2025, pp. 5437–5443, doi: 10.1109/ICC52391.2025.11161863. [5] A. Sakr, A. Araldo, T. Chahed, and D. Kofman, “Co-investment in mobile edge computing with infrastructure update and dynamic participation,” in Proc. IFIP Networking, 2026, pp. 1–6, doi: 10.23919/IFIPN etworking70592.2026.11579047. [6] B. Graham, The Intelligent Investor. New York, NY, USA: Harper & Brothers, 1949. [7] W. Saad, Z. Han, M. Debbah, A. Hjørungnes, and T. Başar, “Coalitional game theory for communication networks,” IEEE Signal Process. Mag., vol. 26, no. 5, pp. 77–97, 2009, doi: 10.1109/MSP.2009.000000. [8] E. Karami and S. Glisic, “Stochastic models of coalition games for spectrum sharing in large scale interference channels,” in Proc. IEEE ICC, 2011, pp. 1–6, doi: 10.1109/ICC.2011.5963190. [9] D. Niyato, A. V. Vasilakos, and Zhu Kun, “Resource and revenue sharing with coalition formation of cloud providers: Game theoretic approach,” in Proc. IEEE/ACM CCGrid, 2011, pp. 215–224, doi: 10.1109/CCGrid .2011.30. [10] T. Wang, L. Song, Z. Han, and B. Jiao, “Dynamic popular content distribution in vehicular networks using coalition formation games,” IEEE J. Sel. Areas Commun., vol. 31, no. 9, pp. 538–547, 2013, doi: 10.1109/JSAC.2013.SUP.0513048. [11] L. Mashayekhy, M. M. Nejad, and D. Grosu, “Cloud federations in the sky: Formation game and mechanism,” IEEE Trans. Cloud Comput., vol. 3, no. 1, pp. 14–27, 2015, doi: 10.1109/TCC.2014.2338323. [12] F. Zafari, K. K. Leung, D. Towsley, P. Basu, A. Swami, and J. Li, “Let’s share: A game-theoretic framework for resource sharing in mobile edge clouds,” IEEE Trans. Netw. Serv. Manag., vol. 18, no. 2, pp. 2107–2122, 2021, doi: 10.1109/TNSM.2020.3044870. [13] A. Sakr, A. Araldo, T. Chahed, and D. Kofman, “Co-investment under revenue uncertainty based on stochastic coalitional game theory,” Ann. Oper. Res., vol. 362, nos. 1–3, pp. 293–355, 2026, doi: 10.1007/s10479 -026-07222-w. [14] M. Aghassi and D. Bertsimas, “Robust game theory,” Math. Program., vol. 107, nos. 1–2, pp. 231–273, 2006, doi: 10.1007/s10107-005-0686-0. [15] M. J. Osborne and A. Rubinstein, A Course in Game Theory. Cambridge, MA, USA: MIT Press, 1994. [16] A. P. Vela, A. Vía, F. Morales, M. Ruiz, and L. Velasco, “Traffic generation for telecom cloud-based simulation,” in Proc. ICTON, 2016, pp. 1–4, doi: 10.1109/ICTON.2016.7550544. [17] K. J. Salchow, Jr., “Clustered multiprocessing: Changing the rules of the performance game,” F5 Networks, white paper, pp. 1–11, 2011. [18] J. Castro, D. Gómez, and J. Tejada, “Polynomial calculation of the Shapley value based on sampling,” Comput. Oper. Res., vol. 36, no. 5, pp. 1726–1730, 2009, doi: 10.1016/j.cor.2008.04.004. [19] R. Mitchell, J. Cooper, E. Frank, and G. Holmes, “Sampling permutations for Shapley value estimation,” J. Mach. Learn. Res., vol. 23, no. 43, pp. 1–46, 2022. [20] M. S. Taqqu, W. Willinger, and R. Sherman, “Proof of a fundamental result in self-similar traffic modeling,” ACM SIGCOMM Comput. Commun. Rev., vol. 27, no. 2, pp. 5–23, Apr. 1997, doi: 10.1145/263876.263879. [21] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge Univ. Press, 2004, doi: 10.1017/CBO9780511804441. [22] L. S. Shapley, “Cores of convex games,” Int. J. Game Theory, vol. 1, no. 1, pp. 11–26, 1971, doi: 10.1007/BF01753431.

Related documents

• An Empirical Evaluation of the Compliance of Game-Network Providers with Data-Protection Law#461868
• Vertices that belong to every minimum dominating set of a graph and their connection with transportation sharing systems with study cases in Campo de Gibraltar area#1115774
• Further Progress Towards Operation Proof Obligation Generation for VDM#471306
• Operation of Anycast Services#500796
• Service-Disabled Veteran-Owned Small Business Contracting Program#675178