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).