Is the A_i that each relayer adds to the transaction bundle and signs the address at which they wish to be paid their hop fee? I initially understood the hop fee payments to be made to the PK_1, ..., PK_n keys, which was somewhat confusing.
In steady state, the protocol optimizes the multicast tree in two ways. Whenever a message is received via both an eager link and a lazy message summary, its hop count is compared. When the eager transmission hop count exceeds the lazy hop count by some threshold, then the lazy link can replace the eager link as a tree edge, reducing latency as measured in hops. In addition, active peers may be periodically replaced by passive peers with better network proximity, thus reducing propagation latency in time.—https://github.com/libp2p/specs/blob/master/pubsub/gossipsub/README.md
This is without any incentivization.
However, this very optimization may also be a concern for randomness and security, as it may be more vulnerable to attacks via peers that are close in proximity. However, this is beyond the scope of this topic so we should move discussion on this elsewhere, e.g. https://github.com/libp2p/go-floodsub/issues/77 or https://github.com/libp2p/libp2p./issues/33 (I’ve chosen the former).
See also https://www.pokt.network/. At the moment I am leery of a particular, but important, aspect of their planned design, which is using federated nodes that have a high stake, although they do not participate in blockchain consensus, only relay validation. However, I think you can use a committee to validate or attest to the validity of relays, as is planned with eth2.
Note that it has been clarified that the stake amount of a federated node should be less than that of a blockchain consensus node.