Techniques are described for facilitating interactions between computing systems, such as by performing transactions between parties that are automatically authorized via a third-party transaction authorization system. In some situations, the transactions are programmatic transactions involving the use of fee-based Web services by executing application programs, with the transaction authorization system authorizing and/or providing payments in accordance with private authorization instructions previously specified by the parties. The authorization instructions may include predefined instruction rule sets that regulate conditions under which a potential transaction can be authorized, with the instruction rule sets each referenced by an associated reference token. After one or more of the parties to a potential transaction supply reference tokens for the parties, the transaction authorization system can determine whether to authorize the transaction based on whether the instruction rule sets associated with the reference tokens are compatible or otherwise satisfied.