Communication Games in Solver Composition
Setting
Each Agent has a view of their intents. Many different views exist in parallel.
The more of them are composed, the more comprehensive the characterization of the desired future state frontier of the participating agents becomes, but composition is not a fully cooperative game in general.
Let’s assume solvers perform local hill climbing over their intent view, but can share information about it. They do that by using one-way messaging as a primitive.
For an agent, or a solver to be willing to share an intent, we need some way to ensure there is utility in that.
Example 1: One-way Intent Sharing
Agent A1, A2, A3 submit their intents to Solver A.
Agent B1, B2, B3 submit their intents to Solver B.
Solver A shares all received intents with Solver B, but B does not reciprocate.
Solver B could now inject intents over several rounds to extract value from potential TXs which match intents from A with intents from B.
Example 2: Symmetric Intent Sharing
If A and B share symmetrically during the same round of solving, there might still be timing games to be played on the consensus layer over the state space, if the solvers crafting TXs and Controllers for Resources contained in them are not synced/batch encrypted.
Mechanism Design (Really Early Notes)
VCG Mechanism for Intent fees
MDPOP explains in detail a distributed VCG Mechanisms for DistDCOP.
This implements incentive-compatibility and individual rationality, but requires a bank (i.e. an instance that is disinterested in the outcomes) for taxation/burn to achieve it.
Trust Aware Intent Sharing
As sketched here one way towards iterated games with better equilibria could be Trust Aware Intent Sharing (TAIS):
Amendment for Example 1
Solver A shares low risk (e.g. low utility, or meant for public solving) intents with Solver B and measures (or queries Agents who let it solve their Intents), how outcomes change depending on the Intents it receives from Solver B, compared to their absence.
In case of improving outcomes, more Intents can be shared in the next round, or fewer, in case of deterioration.
If Agents annotate trust thresholds, which must be fulfilled by Solvers they are forwarded to, they can help the solvers make decisions on which to share first.
If we implement progressive Intent sharing like this, the Agents most exposed to a particular Solvers defection (by extracting value via Intent injection) would be the ones closest to it in the trust graph, which moves the problem to the place that is most effectively regulated.
Trust Aware VCG
Since reputation metrics between Agents and Solvers exist, they could be reused to determined what the tax levied for, i.e. which bank or which public good.
Agents could vote on what they trust the solver tax to go to for each solver and solvers could agree on higher order tax sinks.
The natural choices would be public goods the creators of the views that are being composed by collaborative solving want to see funded.
Misc Protocol Notes
Consensus over Intents
Some guarantees for a single round could also be provided by running consensus over intents, for Intents which are implemented as Resources.
Questions
- Do we want to model
IntentsasResourcessometimes?
Separation pre-solving and solving communication
By default, we assume solvers compute independently.
They can however, mutually agree on interactive solving schemes where they pass messages during solving.
Ideally, we structure the protocol in a way, s.t. communication before solving a batch would look the same as communication during interactive solving.
I.e. we want scale-invariance along the dimension of participating nodes, as well as along the dimension of time/rounds of solving. Incentives will still be up to trust semantics, but the syntax should support that.
Also, solver fee structures etc. should be homogenously encodable as regular intents. They can always be out of band, but if they are embeddable, solvers can publish intents about their internal structure.
In-band is anything the parser of this protocol layer recognizes.
Task
We want to figure out what kind of solving we can do with unidirectional message passing,
and which more efficient protocols built out of that can agree on.
CSP / DCOP Formulation
Some more notes on flavors of CSP which might be useful for implementing the above setting.
Interactive CSP
In Interactive Constraint Satisfaction Problems acquisition of domain values happens on demand.
If we find a way to tie a variable in the CSP to a namespace for the Resources that implement its domain values, we could query them on demand.
For example, we could use directories where owners or controllers of Resources of a certain type could announce their current owners, or solvers who hold intents over them.
These directories could serve requests in a trust aware manner, or against payment, if no prior trust was established.
I don’t know yet if we want to structure this as a “single-shot, but interactive” or “multi round keepalive + commitments for queries”. In non-cooperative settings (or as we call it: the general case), I assume they would collapse into the same game.
In the worst case, we can “just broadcast” queries for intents, but that would likely not give us reduced complexity.
Misc CSP Notes
Some sections from the “Handbook of Constraint Programming” we might want to give a closer read:
- 20.2.3 Async DCOP, the lower bound propagation approach might be interesting in async timing games
- 20.4 Distributed Local Search, which is compatible with our setting
- 20.5 OpenCSPs, regarding problems where not all constraints are set at t_0
- 21.3.1 Fuzzy Problems, might be useful for constraint languages UX/mapping with LLMs
- 21.4 Problems that Change, regarding local repair
As it seems, there is a lot of relevant research. Our task will be to come up with an architecture that does not close the doors on implementing refinements as we proceed from a “simple” starting point.