Assume we know the network topology—what nodes there are and which pairs are linked. If we have tolls on each link then we can plot a minimal toll path thru a network. If tolls fluctuate then we may want several paths thru the network from A to B. In ignorance of link tolls what minimum toll paths are possible?
We define a Gpath as any sequence of nodes beginning at A and ending at B such that adjacent nodes are linked. Since tolls are all positive we can eliminate any Gpath with duplicate nodes since there is another Gpath with lower total tolls, even in ignorance of the real tolls. I can’t think of any other Gpaths to eliminate. A path is hereby a sequence of unique nodes beginning at A and ending at B, with linked adjacent nodes.
In practice this set will be far too large, but I want to understand it mathematically. I think that it is clear that there is a lattice of the nodes with A at the bottom and B at the top such that any path is a chain in the lattice. A chain in a lattice on N is a subset of N which is totally ordered by PO and is not a proper subset of any other totally ordered subset of N.
For what its worth for any finite PO there is a unique subset of PO whose transitive closure is PO. For our network case this would consist of the list of all the links that could possibly be in a path from A to B and is probably the best way to describe the PO over a wire. This list somehow identifies the nodes at the link ends, or at least the outgoing interface numbers.
Such a list would be far too big for a guide to send a client even for massive jobs. I like the idea of sending a subset of nodes with link information and recent observed tolls thereon.
The sphere solution is poor when the monopolist is involved. The ad-hoc solution for the guide is easy to provide but they must be discovered.
The guide is very much a broker and deals with many producers and many consumers of network function. I presume he charges both. An agent that plans to move a lot of data may consult two guides and the proposed format of path sets is easily merged. The agent can quickly judge the brokers as it moves data.