[Question] Can agents coordinate on randomness without outside sources?

[Mikhail Samin]

There are situations where two agents that can read each other’s source code want to have a bit of random information (e.g., they want to cooperate and split an indivisible thing by deciding randomly who’ll have it and having half of it in expectation).

If these agents don’t have access to unpredictable sources of randomness (e.g., it’s acausal trade through very detailed simulations and they can perfectly predict parts of each other’s environment), is there any way for them to coordinate on generating a random bit in a way that can’t be manipulated/​exploited?

I feel like the answer should be “no”, as schemes like “both transparently don’t look at a part of the other’s source code when they coordinate on the scheme, then look and generate the bit from these parts” fail due to the possibility of something else looking at the whole of the agent A’s source code first and then designing a successor/​a simulated agent B which won’t look there but will produce the needed bit.

But maybe I’m missing something?

[JBlack]

In principle (depending upon computation models) this should be possible.

With this very great degree of knowledge of how the other operates, it should be possible to get a binary result by each agent:

1. choosing some computable real number N and some digit position M,

2. that they have no current expectation of being biased,

3. compute it,

4. use the other’s source code to compute the other’s digit,

5. combine the digits (e.g. xor for binary),

6. verify that the other didn’t cheat,

7. use the result to enact the decision.

In principle, each agent can use the other’s source code to verify that the other will not cheat in any of these steps.

Even if B currently knows a lot more about values of specific numbers than A does, that doesn’t help B get the result they want. B has to choose a number+position that B doesn’t expect to be biased, and A can check whether they really did not expect it to be biased.

Note that this, like almost anything to do with agents verifying each other via source code, is purely theoretical and utterly useless in practice. In practice step 6 will be impossible for at least one party.

[Mikhail Samin]

Agent A doesn’t know that the creators of agent B didn’t run the whole interaction with a couple of different versions of B’s code until finding one that results in N and M that produce the bit they want. You can’t deduce that by polluting at B’s code.

[JBlack]

I’m very confused what the model is here. Are you saying that agents A and B (with source code) are just proxies created by other agents C and D (internal details of which are unknown to the agents on the other side of the communication/​acausal barrier)?

What is the actual mechanism by which A knows B’s source code and vice versa, without any communication or any causal links? How does A know that D won’t just ignore whatever decision B makes and vice versa?

[Vladimir_Nesov]

Acausal coordination is centrally about choosing a procedure based on its merits other than the concrete actions it determines, and then following the procedure without faltering at its verdict. As in signing a contract, where the thing you agree to is the overall contract that governs many possibilities, and not a particular outcome.

This is very similar to what makes a procedure a pseudorandomness generator, the numbers it determines shouldn’t be related to any relevant considerations, instead you choose the generator for reasons other than the consequences of the actual numbers it determines. And like in ASP, being technically capable of simulating the generator in order to rig it to choose a favorable outcome (or to prepare to what it generates) doesn’t mean that this is the correct thing to be doing, since doing this breaks down coordination.

[Mikhail Samin]

I mostly generally agree. And when there are multiple actions a procedure needs to determine, this sort of thing is much less of an issue.

My question is about getting one bit of random information for a one-off randomized decision to split indivisible gains of trade. I assume both agents are capable of fully reading and understanding each other’s code, but they don’t know why the other agent exists and whether they could’ve been designed adversarily. My question here is, can these agents, despite that (and without relying on the other agent being created by an agent that wishes to cooperate), produce one bit of information that they know to not have been manipulated to benefit either of the agents?

[Vladimir_Nesov]

The other known-code agent is only an ingredient in defining the outcome you care about (the source code of the world), but not on its own a salient thing when considering coordination. Acausal coordination acts in a broader way, potential contracts you might decide to sign (and so introduce as processes with influence over the a priori defined outcome, the result of computing the code of the world) are not restricted by what’s already explicitly in the initial code of either yourself or your opponents. Coordination here refers to how a contract acts in the same way in all places where it has influence, since it’s the same thing in all these places, and in particular the same contract can act through actions of multiple agents, coordinating them. But contracts are new programs chosen by the players as they engage in setting up coordination between each other, they are not the initial players themselves.

So the distinction between the other agent and its parent rigging the outcome shouldn’t help. Even though both of these are technically potential contracts and could be involved in coordination, both are obviously bad choices for contracts. You wouldn’t want to directly give your opponent control over your own action, hence your opponent shouldn’t be an acausal contract that coordinates your action. Similarly for your opponent’s parent, by proxy of acting through your opponent’s code, it’s not a good contract to grant influence with the outcome through your action.

I don’t know how to solve this puzzle, it seems potentially important if it can be solved. What comes to mind is picking an obvious Schelling point like the procedure of taking the hash of the agent codes concatenated in ascending order as natural numbers, using it as a contract. Parents of agents might try to manipulate behavior of such a contract (by rigging otherwise behaviorally irrelevant details of codes of the agents). Or they might manipulate the choice of a contract (by rigging agents’ intuition for which procedure would be a Schelling point). But that is symmetric and the parents have an incentive to let the agents settle on some procedure rather than to never agree, and so the outcome remains pseudorandom. Which also incentivises the parents to expend less resources on competing over it.

[Dagon]

I’m confused generally about acausal trade (I get it, but I don’t think real agents should give up any significant causal impact to pursue acausal goodness, because that’s not what “pursue” means).

I’m even MORE confused about this scenario. If agents can read each other’s source and split an indivisible thing, they’re absolutely in a causal situation. More generally, acausal trade cannot be about control of specific resources—there are zero shared or contended resources in common. Acausal trade can only be about behavior.

[Mikhail Samin]

From the top of my head, a (very unrealistic) scenario:

There’s a third world simulated by two disconnected agents who know about each other. There’s currently a variable to set in the description of this third world: the type of particle that will hit a planet in it in 1000 years and, depending on the type, color the sky in either green or purple color. Nothing else about the world simulation can be changed. This planet is full of people who don’t care about the sky color, but really care about being connected to their loved ones, and really wouldn’t want a version of their loved ones to exist in a disconnected world. The two agents both care about the preferences of the people in this world, but the first agent likes it when people see more green color, and the second agent likes it when people see more purple color. They would really want to coordinate on randomly setting a single color for both worlds instead of splitting it into two.

It’s possible that the other agent is created by some different agent who’s seen your source code and tried to design the other agent and its environment in a way that would result in your coordination mechanism ending up picking their preferred color. Can you design a coordination mechanism that’s not exploitable this way?

[Dagon]

I dunno—my intuitions don’t really apply to distant and convoluted scenarios, so I’m deeply suspicious of any argument that I (or “an agent” that I care anything about) should do something non-obvious. I will say that’s not acausal—decisions clearly have causal effects. It’s non-communicative, which IS a problem, but a very different one. Thomas Schelling has things to say on that topic, and it’s quite likely that randomness is the wrong mechanism here, and finding ANY common knowledge can lead to finding a Schelling point that has a higher chance of both picking the same color.

[JBlack]

I’m still very confused about the scenario. Agent A and B and their respective environments may have been designed as a proxy by adversarial agents C and D respectively? Both C and D care about coordinating with each other by more than they care about having the sky colour match their preference? A can simulate B + environment, but can’t simulate D (and vice versa)? Presumably this means that D can no longer affect B or B’s environment, otherwise A wouldn’t be able to simulate.

Critical information: Did either C or D know the design of the other’s proxy before designing their own? Did they both know the other’s design and settle on a mutually-agreeable pair of designs?

[Mikhail Samin]

Assume you’re playing as agent A and assume you don’t have a parent agent. You’re trying to coordinate with agent B. You want to not be exploitable, even if agent B has a patent that picked B’s source code adversarially. Consider this a very local/​isolated puzzle (this puzzle is not about trying to actually coordinate with all possible parents instead).

[JBlack]

Oh then no, that’s obviously not possible. The parent can choose agent B to be a rock with “green” painted on it. The only way to coordinate with a rock is to read what’s painted on it.

[Mikhail Samin]

Agent B wants to coordinate with you instead of being a rock; the question isn’t “can you always coordinate”, it’s “is there any coordination mechanism robust to adversarially designed counterparties”.

[Mikhail Samin]

Trivially, you can coordinate with agents with identical architecture, that are different only in the utility functions, by picking the first bit of a hash of the question you want to coordinate on.

[JBlack]

Oh, then I’m still confused. Agent B can want to coordinate with A but still be effectively a rock because they are guaranteed to pick the designer’s preferred option no matter what they see. Since agent A can analyze B’s source code arbitrarily powerfully they can determine this, and realize that the only option (if they want to coordinate) is to go along with that.

A’s algorithm can include “if my opponent is a rock, defect” but then we have different scenarios based on whether B’s designer gets to see A’s source code before designing B.

[Mikhail Samin]

Idea: use something external to both agents/​environments, such sad finding the simplest description of the question and using the first bit of its hash