Agentic Service Markets Across the Computing Continuum: A Polymatroidal Architecture

Lauri Lovén; Alaa Saleh; Reza Farahani; Ilir Murturi; Sujit Gujar; Miguel Bordallo López; Praveen Kumar Donta; Schahram Dustdar

cs.AIMar 5, 2026

Agentic Service Markets Across the Computing Continuum: A Polymatroidal Architecture

Authors: Lauri Lovén, Alaa Saleh, Reza Farahani, Ilir Murturi, Sujit Gujar, Miguel Bordallo López, Praveen Kumar Donta, Schahram Dustdar

Organizations: Future Computing Group, University of Oulu, Finland · Distributed Systems Group, TU Wien, Vienna, Austria · Department of Mechatronics, University of Prishtina, Kosova · Machine Learning Laboratory, International Institute of Information Technology (IIITH), Hyderabad, India · Multimodal Sensing Lab, University of Oulu, Finland · Department of Computer and Systems Sciences, Stockholm University, Sweden · ICREA Barcelona, Spain

Abstract

Autonomous AI agents are becoming economic actors. They compose deadline-bound services across the device-edge-cloud continuum and contend for capacity no single operator owns. This article asks when decentralised pricing can coordinate them exactly and truthfully, and what their service dependencies must satisfy. We model the pipelines as service-dependency graphs under governance constraints and identify the decisive property: laminarity of the induced leaf-block family. Where it holds, the feasible allocation space is a polymatroid and efficient incentive-compatible clearing exists per epoch; where a crossing breaks it, exactness and truthfulness can fail, while clearing prices survive on every totally unimodular family. The formal results instantiate polymatroid, gross-substitutes and Vickrey-Clarke-Groves theory; the contribution is the bridge from dependency structure to that machinery and an integrator architecture that exposes a laminar interface. The node-level evaluation (32,020 runs), at testbed-calibrated congestion, locates the boundary. One crossing costs exactness in 14.7% of high-load rounds and none on laminar instances, and truthfulness fails where exactness does, across contention. An integrator's inner exposure restores exactness at a cost in admitted volume, and before translation overhead it cuts median latency by 16 to 17 percent. Against truth-free posted prices the tuned market leads at medium load and trails a demand-responsive one in four of six high-load cells. Recorded and composed agent workloads drive the allocation. For platform designers, laminar pipelines admit exact decentralised pricing, truthful under the VCG mechanism, and a crossing needs an integrator's inner exposure.

Figures & tables

Result	Known	What this article adds	What the article does not claim
Proposition 1 : polymatroidal feasibility on laminar leaf-block families, with trees and series–parallel DAGs as sufficient conditions	Edmonds [ 15 ] ; Fujishige [ 16 ] ; Amin et al. [ 14 ] on SP flow networks	The bridge from a multi-output, capacity-typed service-dependency DAG to a polymatroid, under leaf-block semantics in which series–parallel terminals are virtual and are not leaves	Nothing for general DAGs or outside the terminals-and-leaves convention. The region is exact under the article’s token counting on every DAG. Laminarity decides only polymatroidality. Laminarity follows from the semantics and the capacities rather than from the drawn edges. No cross-epoch claim
Lemma 1 : gross-substitutes valuations on the slice interface	Kelso–Crawford [ 17 ] ; Gul–Stacchetti [ 18 ] ; OXS [ 19 ] ; discrete convex analysis [ 10 ]	The conditions under which slice encapsulation makes an agent’s aggregate valuation the convolution of its unit-demand task valuations, hence an OXS assignment valuation, which is gross substitutes	Agent-level rather than a per-task bidder set. Fails under shared agent budgets, cross-task latency coupling or shared token caps, and is not closed under summation across agents
Proposition 2 : Walrasian equilibrium, polynomial computation, agent-level DSIC	Kelso–Crawford [ 17 ] ; Murota [ 10 ] ; VCG [ 20 ]	Agent-level DSIC on a service-DAG-induced integer polymatroid, with the agent’s aggregate OXS valuation as the bidder and a Clarke pivot that removes the agent in full	Attaches to the exact welfare maximiser rather than to the auction’s price path. Weak budget balance under down-closed supply. No group strategy-proofness, no cross-epoch guarantee, no operator-side credibility. Clinching only under one task per agent. The truth-assuming single-domain planners the evaluation compares against are counterfactuals that bound the comparison
Proposition 3 : exact scalar interface where a cluster’s leaf blocks coincide	Polymatroid contraction [ 16 ]	A scalar slice interface exported from a sub-DAG, the capacity lemma identifying that scalar as the sub-DAG’s internal bottleneck, and the quotient-graph condition for polymatroidality	Requires one homogeneous slice type and a single-node interface per integrator. Otherwise the summary can over-commit and the integrator exposes a smaller polymatroid inside the deliverable region (the inner-exposure result in the appendices). Nothing for multi-output integrators, internal latency–throughput trade-offs, or shared leaves. The evaluated contraction is this interface on the parallel fan and an inner exposure on the tree and the crossing instance
Catalogue interface for multi-resource recipes (appendices)	Direct sums of polymatroid ranks [ 16 ] ; Edmonds’ greedy [ 15 ]	The exact boundary: at positive internal capacities the catalogue rank gives the resource-feasible region exactly when recipes within a resource-sharing group are identical, and over-commits by a computable factor when they are merely proportional	No exactness for proportional but unequal recipes. No polymatroidal catalogue region for non-proportional sharing, where the integrator can expose only a conservative inner polymatroid. The multi-dimensional case is only bounded
Three-layer hybrid architecture ( Section IV-F )	Network slicing [ 21 ] ; continuum orchestration [ 22 ] ; service function chaining [ 23 ] ; service composition [ 24 ]	Integrator encapsulation as the structural route through regimes outside the laminar leaf-block hypothesis, and the division of labour that keeps the agent-facing interface polymatroidal	No deployment. Integrators are non-strategic infrastructure here. The local-marketplace and inter-market layers are characterised analytically and are not exercised; the evaluation runs the integrator’s slice interface alone

TABLE I: Each result against the machinery it instantiates, the closest parallel work, and what the article does not claim.

Fig. 1: One epoch of the slice market. Agents report tasks and latency-aware valuations at the shared state (1), the agent-facing feasible set is the leaf-block polymatroid of Proposition 1 truncated by governance bounds (2), clearing is the exact welfare maximiser at per-type prices (3), payments are full-agent Clarke pivots (4, Proposition 2 ), execution realises latency against deadlines (5), and the state update opens the next epoch (6).

Fig. 2: Hybrid architecture. Service-consuming agents trade over integrator-exposed slices ( Proposition 3 ), integrators bid for capacity at local marketplaces that coordinate provider-agent offerings, and governance flows through integrators across domains and through marketplaces locally.

Inst.	Load	Lat. (ms)	Drop	Tok.	Welf.	Alloc.	Exact.	$\sigma_{p}$
T 90	low	70.7	0.000	45.09	34.27	1.000	0.000	0.000
	med	82.3	0.013	88.72	60.43	0.999	0.000	0.170
	high	95.1	0.290	94.99	61.65	0.954	0.000	0.126
X 90	low	70.7	0.000	45.09	34.25	1.000	0.000	0.000
	med	84.0	0.020	88.10	59.18	0.997	0.013	0.114
	high	96.3	0.308	92.44	58.89	0.925	0.147	0.167

TABLE II: Structure experiment at the matched operating point:

10

-seed means, uncontracted architecture, no governance. The subscript on each instance is the agent population

N

that puts it at the same offered load,

\rho=1.35

at the uniform leaf mix reported here, against

K_{c}

, the capacity of the binding leaf block at this mix; that match is exact between T and X, whose

K_{c}

is equal by construction, and a rate match only against S, whose

K_{c}

is half theirs. Drop : fraction of tasks that miss their deadline or are never admitted, a control matched on capacity at this mix and not on price rationing or on the deadline. Tok. : admitted tokens per round. Welf. : realised value less the congestion penalty, a.u., over all rounds. Lat. : mean over rounds of the per-round median latency. Alloc. : allocative ratio, the arm’s admitted set scored on true zero-queue values against the exact allocative optimum. Exact. : exactness shortfall, the share of rounds in which the greedy packer falls short of the round’s exact leaf-block optimum, zero on T and S by Edmonds’ theorem.

\sigma_{p}

: across-rounds coefficient of variation (CV) of the demand-weighted mean leaf price over all rounds, burn-in included, exactly

0

below the dispersion onset, where the reserve pins every leaf price.

Fig. 3: Structure experiment by instance (T, X, S) and load at the matched operating point: exactness shortfall (left), allocative ratio (centre) and median latency (right), with ten-seed Student-t

95\%

intervals. Only the crossing instance X falls short of its round’s exact optimum, and latency differs little between the tree and the crossing instance.

Lauri Lovén is an Assistant Professor (tenure track) and head of the Future Computing Group at the University of Oulu, Finland.

Table 37

Alaa Saleh is a doctoral candidate at the Future Computing Group, in the Center for Applied Computing, University of Oulu, Finland.

Table 38

Reza Farahani is a Postdoctoral Researcher at the Distributed Systems Group, TU Wien, Vienna, Austria.

Table 39

Ilir Murturi is an Assistant Professor at the University of Prishtina and an external Senior Researcher at the Distributed Systems Group, TU Wien.

Table 40

Sujit Gujar is an Associate Professor and the CA Technologies Faculty Chair at the International Institute of Information Technology, Hyderabad (IIITH), India.

Table 41

Miguel Bordallo López is an Associate Professor with the University of Oulu, where he leads distributed intelligence research at the 6G Flagship program.

Table 42

Praveen Kumar Donta is associate professor (docent) at the Department of Computer and Systems Sciences, Stockholm University, Sweden.

Table 43

Schahram Dustdar is Full Professor of Computer Science heading the Distributed Systems research division at TU Wien, Austria, and an ICREA Research Professor in Barcelona, Spain.

Table 44

Appendix figures & tables31 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$\mathcal{A}$	Set of agents (consumers, providers, integrators, AI agents)
$t$	Discrete time index, $t=1,2,\dots$
$\theta_{i}(t)$	Type of agent $i$ at time $t$
$\Theta_{i}$	Type space for agent $i$
$\ell_{i}$	Physical location or region of agent $i$
$B_{i}(t)$	Budget or credit of agent $i$

Appendix

TABLE III: Summary of Notation

Category	Strengths	Limitations	How This Article Addresses the Gap
Edge/Fog/ Cloud Service Mgmt [ 45 , 46 , 47 , 48 , 50 , 51 ]	Low-latency orchestration; mobility- and multi-resource-aware management.	Assume centralized control; Limited modeling of multi-stage service dependencies; absence of explicit agent-driven decisions; and restricted adaptability under dynamic conditions.	Introduce an agentic layer; unify resource management with autonomous task generation and price-mediated allocation; incorporate service-DAG constraints.
Service Function Chaining [ 23 , 53 , 54 ]	Optimize dependency-aware service caching; capture placement constraints.	Do not consider strategic agents; lack integrated economic or governance constraints; ignore market or negotiation dynamics.	Model service-dependency DAGs formally; analyse laminar leaf-block families, for which trees and series–parallel DAGs are sufficient conditions, as the regime enabling stable coordination; embed into an economic/management framework.
Agentic/ Autonomous Systems [ 55 , 3 , 22 ]	Identify autonomous AI agents as active system participants; highlight emergent coordination challenges.	No resource-DAG model; no governance-aware allocation; no management-plane integration or tractable orchestration framework.	Provide a full agent–service–resource–governance model; link agent behavior to system feasibility and market outcomes.
Governance, Trust, Norms [ 7 , 40 , 41 ]	Formalize policies, trust, locality, compliance; mature models of norm enforcement.	Not integrated with latency and quality-of-service constraints, dependency-aware placement, or market-based coordination.	Embed governance directly into feasibility ( $\mathcal{X}_{\mathrm{gov}}$ ); model reputation-dependent access (a trust cap that does not bind at the reported operating point); evaluate governance–performance trade-offs.
Market-Based Resource Allocation [ 8 , 56 , 25 , 26 ]	Provide incentive-compatible mechanisms; efficient pricing and allocation for substitutable resources.	Assume independent or substitutable items; break down under interdependent resource bundles or service graphs; no governance.	Identify structural conditions where market stability is preserved (polymatroid regimes); propose hybrid slice-based architecture insulating the market from deep complementarities.

Appendix

TABLE IV: Comparison of Related Work and Positioning of This Article

Parameter	Symbol	Value	Justification
Instances
Node capacities	$C_{v}$	200 / 100 / 100 / 100 / 150 / 100 / 150 / 100	Units at $d$ , $e_{1}$ , $e_{2}$ , $e_{3}$ , $l_{1}$ to $l_{4}$ ; sums to the tier totals $\{200,300,500\}$
Token weight	$w$	2	Capacity units one throughput token consumes at each node on its path
Nodes and arcs	—	8 nodes; 7 / 8 / 15 arcs	One device node, three edge nodes and four leaves, shared by T, X and S; X is T plus the arc $e_{2}\to l_{2}$ , which makes the leaf-block family cross
Base processing delays	$L_{\mathrm{base}}$	$\{5,15,50\}$ ms	By physical tier; zero-queue critical path $70$ ms on every instance
Flow bound ratio	—	1.0 / 1.0 / 0.5	T / X / S; the max-flow bound of a routing count over the leaf-block capacity of Definition 1. On S the routing bound is twice the fork-join capacity, because every token there loads all three parallel edge nodes

Appendix

TABLE V: Baseline Simulation Parameters

Exp.	Varied Aspect	Settings	Fixed
1	Leaf-block family $\times$ load	T (rooted tree), X (T plus one arc, whose leaf-block family crosses), S (parallel fan, whose internal leaf blocks coincide); low, medium, high ( $\lambda\in\{0.5,1.0,1.5\}$ )	$N=90$ (T), $90$ (X), $45$ (S); governance: none; architecture: uncontracted; uniform leaf mix; $90$ runs
2	Agent population $\times$ instance	$N$ over a $28$ -point grid from $10$ to $200$ ; T, X and S; medium and high load	Governance: none; architecture: uncontracted; $1{,}680$ runs
3	Governance policy	None, two coordinate caps (a provider trust threshold and a jurisdiction predicate), a role-class cap enforced at admission, and a cross-node coupling, a joint token budget over two leaves in different domains, the measured member of the class a data-residency rule belongs to, with that coupling sliced by domain	T, X and S; load: medium and high; both leaf mixes; $N=90$ / $90$ / $45$ ; $720$ runs
4	Architecture factorial	Uncontracted, uncontracted $+$ EMA, contracted without EMA, contracted $+$ EMA; the interface is fixed by the arm, none uncontracted and the cluster’s bottleneck scalar contracted, and the advertised routed composition is the faithfulness probe’s	T, X and S; load: medium and high; $2\times 2\times 3\times 2\times 10=240$ runs
5	Architecture $\times$ governance	Contracted vs. uncontracted; caps vs. none; T, X and S	$N=90$ / $90$ / $45$ ; load: medium and high; $2\times 2\times 3\times 2\times 10=240$ runs
6	Allocation mechanism, grouped by comparator tier	Tier A reference optima as reported columns; Tier B random, earliest-deadline-first [ 38 ] , value-greedy, the Kubernetes-style rank [ 37 ] and the value-ranked posted price; Tier C the market, the congestion-consistent market, the arrival-order and the deadline-priority posted prices over a markup grid re-levelled around the interior optimum, a demand-responsive posted price tuned over its step and target, and the mixed arm; uncontracted and contracted architecture	T, X and S; load: medium and high; $N=90$ / $90$ / $45$ ; no governance; both congestion levels; $9{,}120$ runs on the level grid, $13{,}080$ tuning and $3{,}840$ evaluation runs

Appendix

TABLE VI: Experiment-Specific Parameter Settings

Block	Grid	Runs
Ablation experiments
Structure	3 instances $\times$ 3 loads $\times$ 10 seeds	$90$
Governance	6 levels $\times$ 3 instances $\times$ 2 loads $\times$ 2 mixes $\times$ 10	$720$
Cap-target probe	4 targets $\times$ 2 loads $\times$ 10, on X	$80$
Architecture	4 arms $\times$ 3 instances $\times$ 2 loads $\times$ 10	$240$
Architecture $\times$ governance	2 $\times$ 2 $\times$ 3 instances $\times$ 2 loads $\times$ 10	$240$

Appendix

TABLE VII: Run accounting: one run is one per-seed simulation of one arm of a block. Counts are read off the released pipeline’s grids.

$-$ S: T $\to$ X (high load)
Component	Metric	Before	After
	Exactness shortfall	$0.0000$	$0.1470$
	Incentive certificate	Passes	Fails
	Drop rate (control)	$0.290$	$0.308$
$-$ H: Contracted $\to$ Uncontracted (T, high)
	Median latency	$80$ ms	$95$ ms

Appendix

TABLE VIII: Component ablation summary. Each block toggles one design component under its most informative condition. The arrow in a block heading gives the direction of the Before and After columns. In the

-

M block both arms are read on the twenty evaluation seeds, the market at its tuned reserve markup (

2

at the reported level,

3

at the steep level).

Parameter	Value	$n_{\mathrm{vol}}$	Median	Min	Max
Capacity scale	$0.70$	3	$0.906$	$0.895$	$0.923$
	$\mathbf{1.00}$	10	$\mathbf{0.840}$	$0.636$	$0.928$
	$1.30$	5	$0.850$	$0.838$	$0.895$
Slice-price step $\eta$	$0.10$	10	$0.851$	$0.638$	$0.921$
	$\mathbf{0.15}$	10	$\mathbf{0.840}$	$0.636$	$0.928$
	$0.20$	10	$0.841$	$0.632$	$0.915$

Appendix

TABLE IX: Architecture sensitivity: one-at-a-time parameter sensitivity of the median price-volatility reduction (slice

+

EMA vs. naïve, fair agent-facing metric) over the volatile cells.

n_{\mathrm{vol}}

is the number of the ten cells that clear the volatility floor of

0.02

; the median, minimum and maximum are taken over those cells. Baseline levels in bold. The

(2,4,5)

and

(5,4,3)

demand profiles, high load, each at its own operating point,

N=55

and

N=35

5

seeds.

Instance	Load	Med. Lat. (ms)	Drop Rate	Tokens	Welfare	Alloc.	Shortfall	$\sigma_{p}$
T	Low	70.68	0.0000	45.09	34.27	1.0000	0.0000	0.0000
T	Medium	82.27	0.0132	88.72	60.43	0.9993	0.0000	0.1697
T	High	95.11	0.2900	94.99	61.65	0.9541	0.0000	0.1260
X	Low	70.75	0.0000	45.09	34.25	1.0000	0.0000	0.0000
X	Medium	83.96	0.0198	88.10	59.18	0.9969	0.0130	0.1144
X	High	96.32	0.3078	92.44	58.89	0.9253	0.1470	0.1666

Appendix

TABLE X: Structure: impact of the leaf-block family and the load level. Uncontracted architecture, no governance, uniform leaf mix,

N=90

(T),

90

(X),

45

(S);

10

seeds per cell,

90

runs, at the reported congestion level. Student-

t

95\%

intervals are at most

\pm 0.35

ms wide on median latency,

\pm 0.009

on drop rate and

\pm 0.012

\sigma_{p}

Fig. 4: Governance: effect of the governance level (none, two coordinate caps, a role-class cap, and the cross-node coupling with its domain slice) on performance for T, X and S under medium and high load, at the uniform leaf mix. Panels: median latency, drop rate, service coverage, price volatility. Coverage here is the share of offered tasks served, one minus the drop rate, so the coverage panel mirrors the drop panel.

Fig. 5: Architecture (operational): the four factorial arms across the three instances and two loads. Panels: median latency (top) and drop rate (bottom). Line shade encodes load, grey for medium and black for high.

Fig. 6: Architecture (economic): welfare (top row) and post-burn-in agent-facing price volatility

\sigma_{p}

(bottom row), over the same runs as Fig. 5 , with the cleared pre-smoothing series beside the agent-facing one.

Fig. 7: Architecture

\times

governance interaction: the exactness shortfall (top row) and welfare (bottom row) against the instance, faceted by load with medium on the left and high on the right.

Tier and arm	Feasible where	W/opt.	Alloc.	Frontier	Cert.
Tier A, reference optima, unobtainable in deployment, yardsticks only
Exact allocative optimum	Zero queue and true values, neither available to any arm	—	$1.000$	—	—
Ex-post prefix optimum	The best value-prefix admission through the realised congestion model, a lower bound	$1.000$	—	—	—
Tier B, truth-assuming single-domain planners
Value-greedy	Inside one operator’s domain, with its own agents, and only where it can read true values	0.954 / 0.931 / 0.979	0.999 / 0.999 / 1.000	1.00 / 1.00 / —	Yes / No / Yes
Kubernetes rank	Inside one operator’s domain, on declared priorities and resource requests	0.872 / 0.854 / 0.905	0.924 / 0.924 / 0.925	0.91 / 0.91 / —	Yes / No / Yes

Appendix

TABLE XI: Comparator table: every arm with its four numbers and the condition under which it is feasible. Uncontracted architecture, high load, the reported congestion level, each arm at its own knob tuned on seeds

1

5

and reported on the twenty evaluation seeds

11

30

. Numeric cells read T / X / S. W/opt. is realised welfare over the ex-post prefix optimum, Alloc. the allocative ratio to the exact allocative optimum on true values at zero queue, Frontier the arm’s point on the posted family’s welfare-versus-admission curve at its own realised volume, and Cert. the incentive certificate. The EDF, random and mixed rows and the Frontier column are read off the level grid, seeds

1

10

; the demand-responsive arm has no single level and so no Frontier entry, and on S the planners’ volume lies outside the range of volumes the posted family covers. The three posted prices share one participation screen at the posted level: the value-ranked one packs those it screens in by expected value, the arrival-order one admits them in arrival order and the deadline-priority one earliest deadline first.

Fig. 8: Mechanism: seven arms across the three instances and two load levels, at the reported congestion level and the uncontracted architecture. The four ablation levels are random, EDF, value-greedy and the untuned market; the tuned market, the tuned value-ranked posted price and the tuned arrival-order posted price are read from the tuned table, whose knob was chosen on seeds disjoint from the ablation’s and which carries no drop rate, so those three arms have no point in the drop panel. The tuned deadline-priority posted price is not drawn: it lies within

0.0004

of the arrival-order one in every cell and would overprint it. Panels: welfare (top-left), allocative ratio (top-right), drop rate (bottom-left), median latency (bottom-right). The comparator table of Table XI carries every arm with its four numbers.

Instance	Cert.	$\alpha{=}0.5$	$0.7$	$0.9$	$1.1$	$1.3$
T	Passes	0.0858	0.0440	0.0030	0.0020	0.0102
S	Passes	0.0867	0.0421	0.0029	0.0019	0.0099
X	Fails	0.0473	0.0226	0.0017	0.0014	0.0073

Appendix

TABLE XII: Incentives: mean per-agent regret under valuation shading by factor

\alpha

, with the incentive certificate each instance carries. Regret is zero at

\alpha=1

(truthful) by construction and strictly positive for every misreport, the empirical content of the DSIC guarantee (Proposition 2).

10

seeds and

30

rounds per instance,

30

runs.

		VCG					Market
$N$	Cap.	X mean	X max	X inexact	T max	S max	T mean	T max	X mean	X max
8	0.10	$0.154$	$0.244$	$0.060$	$5.6\times 10^{-16}$	$4.4\times 10^{-16}$	$0.014$	$0.043$	$0.004$	$0.019$
8	0.25	$5.3\times 10^{-16}$	$8.9\times 10^{-16}$	$0.000$	$8.9\times 10^{-16}$	$5.6\times 10^{-16}$	$0$	$0$	$0$	$0$
8	0.50	$5.3\times 10^{-16}$	$8.9\times 10^{-16}$	$0.000$	$8.9\times 10^{-16}$	$8.9\times 10^{-16}$	$0$	$0$	$0$	$0$
8	1.00	$5.3\times 10^{-16}$	$8.9\times 10^{-16}$	$0.000$	$8.9\times 10^{-16}$	$8.9\times 10^{-16}$	$0$	$0$	$0$	$0$
15	0.10	$0.111$	$0.207$	$0.113$	$9.2\times 10^{-16}$	$4.4\times 10^{-16}$	$0.071$	$0.135$	$0.042$	$0.064$

Appendix

TABLE XIII: Joint misreport against contention: best-response gain over the joint strategy set, the gain being the utility a deviating agent obtains over truthful reporting at its true valuation net of payment, under the VCG allocation with Clarke payments and under the discovered-price market. For each point, each seed’s worst case over agents and rounds is taken; mean and max are the mean and maximum of those over the ten seeds. Inexact is the share of rounds in which the greedy packer falls short of the exact leaf-block optimum. The certificate fails on X at every point and passes on T and S at every point; on T and S the VCG inexactness is zero throughout and only the maximum is shown. The market’s gain on S is

0

at every point and is not shown; its zeros are exact, where VCG’s floor values are floating-point residue. Of the

171

market runs with a positive gain, the best deviation is a uniform over-report in

137

(

87

\times 1.1

50

\times 1.3

), a uniform under-report in

4

(all at

\times 0.9

) and a mixed or per-task report in

30

620

VCG runs and

600

market runs.

Rec.	Load	Lat. (ms)	Drop	Welf.	Alloc.	Short.	Cert.
Lam.	medium	3890.8	0.5526	80.53	0.9940	0.0000	Passes
Lam.	high	3896.7	0.7301	75.88	0.9001	0.0000	Passes
Cross.	medium	3929.9	0.7324	60.18	0.7433	0.2290	Fails
Cross.	high	4183.6	0.8670	47.70	0.5582	0.0260	Fails

Appendix

TABLE XIV: Agentic workload: the single recorded agent, whose family is laminar, and the composition of two recordings built by us, whose family crosses by the shared tool stage, at medium and high load, uncontracted architecture without the filter.

N=200

10

seeds per cell; the grid also runs the filtered arm,

80

runs in all. Rec. is the recording (laminar or crossing), Lat. the median latency, Drop the drop rate, Welf. welfare (a.u.) and Cert. the incentive certificate; Alloc. is the allocative ratio to the exact optimum on true values and Short. is the shortfall, the share of rounds in which the greedy packer falls short of the round’s exact leaf-block optimum.

Cap	Arm	Price CV	Greedy exact	Adm. exact	Welf. ratio	Served/adm.	Clearing
6	Homogeneous	0.722	1.0000	0.229	0.211	0.417	0.136
6	Homog., encaps.	0.247	1.0000	0.318	0.272	0.421	0.184
6	Heterogeneous	0.802	0.9741	0.285	0.245	0.493	0.164
6	Hetero., encaps.	0.231	0.9741	0.404	0.245	0.462	0.224
9	Homogeneous	0.670	1.0000	0.626	0.604	0.556	0.518
9	Homog., encaps.	0.192	1.0000	0.752	0.686	0.498	0.577

Appendix

TABLE XV: Recipe heterogeneity: four arms at three catalogue caps,

10

seeds per cell,

120

runs. Cap is the catalogue cap and Arm the recipe-by-pricing arm. Price CV is the coefficient of variation of the agent-facing price series over rounds. Greedy exact is the greedy allocation’s welfare against the exact optimum, and Adm. exact the admitted set’s welfare against that same exact optimum. Welf. ratio is realised welfare over the ex-post prefix optimum, a different denominator from the two exactness ratios and so a different quantity from Greedy exact . Served/adm. is the share of admitted tasks actually served, and Clearing the share of offered tasks admitted and served, one minus the drop rate.

Instance	Interface	Over-comm.	Serv/adm	Tokens	Welfare	Lat. (ms)
T	None	0.0000	1.0000	94.99	61.65	95.1
T	Inner	0.0000	1.0000	74.61	56.78	79.6
T	Maxflow	1.4890	1.0000	99.04	61.70	99.9
X	None	0.0000	1.0000	92.44	58.89	96.3
X	Inner	0.0000	1.0000	74.61	56.55	79.9
X	Maxflow	2.5685	1.0000	99.04	59.03	105.2

Appendix

TABLE XVI: Capacity-faithfulness probe: market outcomes under the three interface constructions, no contraction, the cluster’s bottleneck scalar ( Inner : exact on S, an inner exposure on T and X) and the advertised routed composition ( Maxflow ). Uniform leaf mix, high load, the reported congestion level,

10

seeds per cell; the probe runs both leaf mixes,

180

runs, and the skewed half is reported in the text. Over-comm. is the per-round mean excess of admitted tokens over what the true instance can deliver, clipped at zero, and Serv/adm is the share of admitted tasks actually served.

Demand profile	$\delta_{\mathrm{enc}}$ (ms)	Lat. (ms)	p95 (ms)	Drop	Welfare
$(2,4,5)$	0	301.9	349.4	0.2914	29.12
$(2,4,5)$	25	320.2	370.9	0.2985	26.19
$(2,4,5)$	50	341.1	394.9	0.3073	23.36
$(5,4,3)$	0	330.4	380.9	0.4269	14.83
$(5,4,3)$	25	346.7	399.5	0.4337	13.34
$(5,4,3)$	50	365.5	421.1	0.4438	11.99

Appendix

TABLE XVII: Encapsulation-overhead sweep: additive per-slice protocol-translation latency

\delta_{\mathrm{enc}}

on the slice path. High load,

10

seeds per cell,

60

runs. Rows are labelled by the per-tier demand profile, the vector of device, edge and cloud demand weights that is the channel through which the dependency graph enters this environment.

Level	Instance	Arm	$\delta_{\mathrm{enc}}$ (ms)	Latency lead (ms)	Welfare lead	Token lead	Zero at
reported	T	contracted	0	$15.5$ [ $15.2$ , $15.9$ ]	$-4.88$ [ $-5.56$ , $-4.20$ ]	$-20.38$ [ $-21.25$ , $-19.52$ ]	$38.9$
reported	T	contracted	25	$5.5$ [ $5.2$ , $5.8$ ]	$-16.89$ [ $-17.35$ , $-16.43$ ]	$-27.88$ [ $-28.61$ , $-27.15$ ]
reported	T	contracted	50	$-4.4$ [ $-4.9$ , $-3.8$ ]	$-23.85$ [ $-24.25$ , $-23.46$ ]	$-32.71$ [ $-33.59$ , $-31.84$ ]
reported	T	contracted $+$ EMA	0	$15.1$ [ $14.8$ , $15.4$ ]	$-1.73$ [ $-2.04$ , $-1.43$ ]	$-16.25$ [ $-16.83$ , $-15.67$ ]	$31.3$
reported	T	contracted $+$ EMA	25	$3.7$ [ $3.3$ , $4.1$ ]	$-13.99$ [ $-14.32$ , $-13.66$ ]	$-23.26$ [ $-23.95$ , $-22.57$ ]
reported	T	contracted $+$ EMA	50	$-10.9$ [ $-11.3$ , $-10.6$ ]	$-19.95$ [ $-20.22$ , $-19.68$ ]	$-24.49$ [ $-25.12$ , $-23.87$ ]

Appendix

TABLE XVIII: Encapsulation overhead on the node substrate: the lead of each contracted arm over the uncontracted one at

0

25

and

50

ms of translation overhead, charged on each task whose leaf the contracted cluster exports, in execution and in the bid-time estimate, at the reported congestion level (clamp

0.95

, coefficient

0.75

) and at the steep sensitivity level (clamp

0.99

, coefficient

2

). A positive lead is better for the contracted arm: the latency lead is the uncontracted median latency less the contracted one, the welfare and token leads the contracted value less the uncontracted one. Zero at is the overhead at which the latency lead reaches zero, by linear interpolation between the swept levels; none means no crossing inside

0

50

ms. High load, paired by seed, Student-

t

95\%

intervals,

n=10

per row,

420

runs.

Variant	Cell	Own	Used	Posted $-$ market	Share
Other load	T, unc., high	$2.00$	$1.00$	$-5.31$ [ $-5.45$ , $-5.18$ ]	$-0.081$
Other load	X, unc., high	$1.75$	$1.25$	$-4.20$ [ $-4.40$ , $-4.00$ ]	$-0.066$
Other load	S, con., high	$2.00$	$0.50$	level not on the grid
Other load	S, unc., high	$1.00$	$0.50$	level not on the grid
Other load	T, unc., medium	$1.00$	$2.00$	$-5.32$ [ $-5.59$ , $-5.05$ ]	$-0.087$
Other load	X, unc., medium	$1.25$	$1.75$	$-3.26$ [ $-3.57$ , $-2.96$ ]	$-0.055$

Appendix

TABLE XIX: Posted price at a level tuned outside its own cell. The arrival-order posted price at a level carried over from the other load of the same instance, architecture and congestion level ( Other load ) or pooled over the two architectures ( Pooled ), read off the level grid (

10

seeds), minus the tuned market on its twenty evaluation seeds, in welfare (a.u., Welch

95\%

interval) and as a share of the ex-post prefix optimum. Own is the level tuned on the cell’s own load and Used the carried-over level. Reported congestion level; only cells where the carried level differs from the cell’s own are listed.

Setting	Factor	$\lambda_{l}$	Clamp	$\alpha$	$c$	T		X		S
						unc.	con.	unc.	con.	unc.	con.
Baseline	Congestion	$9.64\times 10^{-3}$	$0.99$	$50$	$2$	$0.265$	$0.871$	$0.283$	$0.889$	$0.357$	$0.205$
Clamp $0.95$	Congestion	$9.64\times 10^{-3}$	$0.95$	$50$	$2$	$0.734$	$0.880$	$0.713$	$0.898$	$0.675$	$0.785$
Clamp $0.995$	Congestion	$9.64\times 10^{-3}$	$0.995$	$50$	$2$	$0.302$	$0.870$	$0.288$	$0.888$	$0.455$	$0.214$
Calibrated	Congestion	$9.64\times 10^{-3}$	$0.95$	$50$	$0.75$	$0.944$	$0.887$	$0.923$	$0.905$	$0.766$	$0.977$
$\lambda_{l}=0.0025$	Value decay	$2.50\times 10^{-3}$	$0.99$	$50$	$2$	$0.544$	$0.953$	$0.539$	$0.973$	$0.701$	$0.624$

Appendix

TABLE XX: Parameter sweep of the mechanism comparison: the untuned market arm’s (reserve markup

1

) realised welfare over the ex-post prefix optimum at each of the eight settings, uncontracted (unc.) and contracted (con.). The settings are one factor at a time from the baseline: the utilisation clamp and the queue coefficient

c

set the execution congestion term,

\lambda_{l}

the value decay and

\alpha

the bid-time congestion scale. High load, three instances, two architectures,

5

seeds per cell,

30

market runs per setting and

240

in all. Baseline row in bold; the article reports the calibrated setting. Over the forty runs behind each instance-and-architecture column the welfare ratio spans

0.31

contracted against

0.71

uncontracted on T,

0.31

against

0.78

on X, and

0.82

against

0.46

on S.

Result	Experiment	Observables	Enters
Prop. 1 (Polymatroid)	Structure ( $-$ S)	Exactness, certificate	varied
Lemma 1 (GS valuations)	every arm	—	instantiated
Prop. 4 (ii)	Heterogeneity, one recipe	Greedy-exact ratio	instantiated
Prop. 4 (iii)	Proportional-recipe arm	Over-commitment factor	simulated
Prop. 5 (inner)	Architecture on T, X	Over-commitment, volume	instantiated
Prop. 2 (DSIC, shading)	Incentives	Per-agent regret	varied

Appendix

TABLE XXI: Theory-to-experiment mapping. Each formal result is paired with the experiment that exercises it, its observables, and how it enters: varied (an arm varies the hypothesis), instantiated (every arm satisfies it) or simulated (an arm measures a closed-form prediction).

Ablation	Source	Isolates
Full system (S+H+G+M)	Arch. $\times$ Gov. (contracted, capped)	Everything on
$-$ M (remove market)	Mechanism (Tier B vs. market)	Price coordination
$-$ G (remove governance)	Arch. $\times$ Gov. (no-cap conditions)	Coordinate-wise leaf caps
$-$ H (remove integrator)	Architecture (uncontracted arm)	Contraction and smoothing together
$-$ H S (remove smoothing)	Architecture (contracted without EMA)	Smoothing alone
$-$ H E (remove contraction)	Architecture (uncontracted $+$ EMA)	The contraction alone

Appendix

TABLE XXII: Complete Ablation Matrix

Fig. 9: Scaling: instance-dependent scaling as agent count increases over the extended grid, at medium load. Panels: median latency, drop rate, binding fraction, price volatility.

Instance	Load	$K_{c}$	Measured $N$ (seeds)	All seeds	Onset $\rho$
T	medium	100	60 (0.2)	75	0.60
T	high	100	40 (0.2)	50	0.60
X	medium	100	60 (0.2)	70	0.60
X	high	100	40 (0.3)	50	0.60
S	medium	50	30 (0.1)	40	0.60
S	high	50	30 (1.0)	30	0.90

Appendix

TABLE XXIII: Onset of price dispersion in the population sweep, read in offered load. Measured

N

is the smallest grid population whose mean

\sigma_{p}

over ten seeds is non-zero, with the fraction of seeds non-zero in parentheses; All seeds is the smallest population non-zero in every seed; Onset

\rho

is the offered load at the measured onset. The first-crossing law under-counts the onset by a factor of three to five and assigns X exactly T’s predicted probability, so it is reported as a bracket.

Family	Inst.	Rounds	Cross.	Bip.	Int.	TU	Pos. gap	Rel. gap (mean / max)	Exactness (mean / worst)	Adm.
Generated strata
Laminar	17	3,400	0	Yes	Yes	Yes	0.000	$3.8\times 10^{-17}$ / $1.4\times 10^{-15}$	1.0000 / 1.0000	81.0
One crossing	19	3,800	1	Yes	Yes	Yes	0.000	$2.4\times 10^{-17}$ / $3.4\times 10^{-15}$	0.9779 / 0.8805	86.1
Bi-laminar	20	4,000	2 to 6	Yes	Mixed	Yes	0.000	$3.2\times 10^{-17}$ / $3.3\times 10^{-15}$	0.9859 / 0.8855	84.3
Odd cycle, interval	20	4,000	3 to 6	No	Yes	Yes	0.000	$5.0\times 10^{-17}$ / $3.2\times 10^{-15}$	0.9854 / 0.8944	84.3
Odd cycle, non-interval	18	3,600	3 to 11	No	No	No	0.082	$8.2\times 10^{-5}$ / $4.7\times 10^{-3}$	0.9833 / 0.9085	82.9

Appendix

TABLE XXIV: Existence and exactness by leaf-block family, uniform leaf mix. Strata are the generated families only; the named instances sit on their own rows and are excluded from the stratum means. Cross. is the range of pairwise-crossing block pairs, Bip. whether the crossing graph is bipartite, Int. whether the leaves admit an interval order and TU the brute-force total-unimodularity verdict on the incidence matrix. Pos. gap is the fraction of rounds with a positive relaxation-to-integer gap, Rel. gap its mean and maximum, Exactness the greedy packer’s mean and worst round against the integer optimum, and Adm. the round’s mean admitted count. The series-parallel rejoin row is a two-terminal series-parallel network that is not a tree (the device node feeds two parallel nodes that rejoin at one node before the leaves), laminar, at the substrate’s node count and the generator’s capacity rule; it is the series-parallel case of the proposition exercised on the two structural instruments. The two triangle rows are the same family at unit capacities and at the generator’s own capacity rule; its failure rate is a property of the former. The pipeline-template row is a domain-level reading of the companion deployment [ 39 ] , its three templates read here as demand classes over five domain nodes re-split from that deployment’s four administrative domains; the companion did not run the three templates together.

Statistic	Load	Simulation [CI]	Testbed [CI]	Overlap	Sign	$n$
Latency elasticity	high/low	$0.0496$ [ $0.0354$ , $0.0614$ ]	$0.2597$ [ $0.1777$ , $0.3753$ ]	No	Same	$100$ / $245$
Tail ratio	low	$1.1305$ [ $1.0958$ , $1.2025$ ]	$1.6729$ [ $1.4415$ , $1.9889$ ]	No	Same	$50$ / $95$
Tail ratio	high	$1.1780$ [ $1.1293$ , $1.2293$ ]	$1.4045$ [ $1.2900$ , $1.5635$ ]	No	Same	$50$ / $150$
Drop rate	low	$0.0000$ [none]	$0.9474$ [ $0.8816$ , $0.9796$ ]	n/a	Differ	$50$ / $95$
Drop rate	high	$0.0067$ [ $0.0000$ , $0.0200$ ]	$0.9933$ [ $0.9800$ , $1.0000$ ]	No	Same	$50$ / $150$
Drop-rate step	high $-$ low	$0.0067$ [ $0.0000$ , $0.0200$ ]	$0.0460$ [ $0.0075$ , $0.1099$ ]	Yes	Same	$100$ / $245$

Appendix

TABLE XXV: Calibration statistics, simulation against emulated testbed. Intervals are BCa bootstrap over rounds within one seed (

B=2{,}000

);

n

is rounds and tasks per side.

Tier	Cap	$n$	W. p50	W. p95	S. p50	S. p95	W. frac.
Device	$2$	$245$	$0.0$	$1042.0$	$1380.0$	$2839.5$	$0.000$
Edge	$3$	$490$	$0.0$	$3364.3$	$2943.2$	$7158.9$	$0.000$
Cloud	$5$	$245$	$0.0$	$0.0$	$3870.6$	$8331.5$	$0.000$

Appendix

TABLE XXVI: Per-tier decomposition of the clean replay into admission wait and service time, in ms. Wait fraction is the median admission wait over the sum of the median wait and the median service time. The

p_{95}

columns are nearest-rank.

Phase	Rnds	Tasks	Testbed	Sim.	Gap
Pre-kill ( $1$ – $24$ )	$24$	$72$	$1.0000$	$1.0000$	$0.0000$
Post-kill ( $25$ – $50$ )	$26$	$78$	$0.0000$	$0.9872$	$0.9872$

Appendix

TABLE XXVII: Completion gap under a permanent loss of the cloud container. Testbed completion is the share of tasks that finish; the simulation column is the share that meet their deadline in the same rounds.

Explore similar work

Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems
Jul 24, 2026Mojtaba EslamiCoalition Formation Artificial Intelligence Systems
University of Calgary
The Price of Anarchy in Disaggregated Inference
Jun 11, 2026Athos GeorgiouCongestion Prices
NCA
Agentic AI Systems Should Be Designed as Marginal Token Allocators
May 2, 2026Siqi ZhuProduction Agentic Systems Economies
University of Illinois Urbana-Champaign

Jul 24, 2026, cs.AIJ/K move · Enter open · S save

Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems

Mojtaba Eslami

University of Calgary

Coalition Formation Artificial Intelligence Systems Goal-Conditioned Value Function

Open paper AskPDF arXiv

Modern agentic AI systems combine multiple large language model agents with heterogeneous skills, yet most architectures either fix communication in advance or allow full broadcast. Both can be inefficient because token cost, latency, redundancy, and error propagation increase with the number of active agents and communication links. We model agent selection and communication as a cooperative game with task-conditioned net utility

U(C\mid x)=V(C\mid x)-\sum_{i\in C}c_i

, separating coalition-level costs from agent activation costs. We propose a marginal-value activation rule and greedy router, extend the model to optimize communication edges with per-edge costs, and use estimated Shapley values to predict which agents are worth contacting before and during execution. We connect the problem to submodular maximization and prove two limited guarantees: a curvature-refined bound for a monotone, cardinality-constrained special case, and a tight

1/2

-approximation, with a correction for signed objectives, for an unconstrained non-monotone case via double greedy. Neither guarantee applies directly to the main router, which remains a heuristic. We also prove a Shapley-submodularity sandwich bound linking the error of marginal-value routing to a per-agent diminishing-returns quantity. In synthetic experiments, greedy routing achieves

99.5%

of brute-force-optimal utility while activating

1.96

8

agents on average, compared with

38.8%

for full broadcast. Performance is robust to activation cost and redundancy weight but falls to

66%

under strong violations of submodularity or noisy value estimates. We distinguish the framework from Shapley pricing, hedonic coalition formation, and communication-graph pruning, and propose evaluation on real multi-agent LLM benchmarks.

Abstract

Explore similar work

Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems

The Price of Anarchy in Disaggregated Inference

Agentic AI Systems Should Be Designed as Marginal Token Allocators