This is the last in my series on commitments, where we look at what happens when debtors don’t satisfy their commitments.

A debtor agent makes a commitment before satisfying the commitment.  In fact, that’s the whole point of using commitments.  It is a way for a debtor to tell others what it will do in the future.  Since debtors are assessed penalties when they fail to satisfy a commitment, they are certainly encouraged to do satisfy. However, bad things can happen between making and satisfying a commitment.

To paraphrase Spock in The Wrath of Khan, “There are two possibilities. They are unable to respond. They are unwilling to respond”.  First, a debtor may be unable to satisfy all of its commitments.  Toyota had a lot of commitments to deliver automobiles, but when the tsunami hit it, Toyota was no longer able to keep all of those commitments.

Second, event considering the cost of penalties, a debtor may be unwilling to satisfy all of its commitments.  Airlines knowingly overbook flights, creating more commitments than they can possibly keep.  They willing pay the penalties for their broken commitments.  This covers the case where debtors originally intended in good faith to satisfy their commitments but it is no longer profitable to do so, and where debtors made a commitment never intending to satisfy them.  We don’t distinguish between good and bad intentions in our commitment formalism, because it makes little difference and it is often impossible to distinguish anyway.

To model real world situations, we have to allow these messy cases.  We can not require debtors to always satisfy their commitments. The only thing we do require is that debtors must not leave their commitments hanging forever.  If they can’t satisfy a commitment, then then must eventually cancel it.   Commitment cancellation could be triggered by a timeout mechanism.

Last time, we discussed commitment transformations,.  This time we look at a different kind of transformation that captures the idea of a “chain reaction”:  where knocking over a single domino causes a whole chain of dominos to topple.

The basic idea is to combine multiple commitments that form a chain of commitments into a single commitment.  A chain is well-defined when

• If the first commitment is satisfied, then the second one becomes unconditional
• If the first 2 commitments satisfied, then the third becomes unconditional
• …
• If the first N-1 commitments satisfied, then the Nth commitment becomes unconditional

Since we assume debtors typically honor their commitments (I’ll have more to say about this in a future post) then unconditional commitments will typically be satisfied and deliver the consequent to the creditors.  So whenever the first antecedent becomes true (“fires”), a “chain reaction” eventually occurs and the whole chain of commitment consequents eventually become true (“fire”).  The chain reaction may not occur instantly, but if all debtors eventually honor their commitments, the full chain reaction will eventually occur. Further, the result is a commitment from the set of all debtors to the set of all the creditors.

The chain is incrementally constructed using a serial composition operator of two commitments. So let’s define it and get those gorpy details out of the way now. This post requires more notation than previous posts. I try to avoid notation, but here its just the simplest approach.  I’m using the cool MathJax-Latex WordPress plugin to format this material. This should render in most browsers. Let me know if it doesn’t render well in your browser.

Serial Composition Operator:
When the condition \(C_A.csq \models C_B.ant \) holds, then the serial composition of two commitments, \(C_{\oplus} = C_A \oplus C_B \), is well-defined, and

\(
\begin{align*}
C_{\oplus}.debt & := C_A.debt \cup C_B.debt \\
C_{\oplus}.cred & := C_A.cred \cup C_B.cred \\
C_{\oplus}.ant & := C_A.ant \\
C_{\oplus}.csq & := C_A.csq \land C_B.ant \land C_B.csq
\end{align*}
\)

The well-defined condition simply means that \(C_B.ant\) must be true whenever \(C_A.csq\) is true. So if the first commitment becomes unconditional and is eventually satisfied, then the second comment will also eventually become unconditional.

The transformations in the previous posts never changed the debtors or creditors.  Here, the composite commitment unions the debtors and creditors.  All the debtors are responsible for ensuring the commitment is satisfied. There are different ways to combine responsibilities.  Responsibility can be several (each debtor is responsible for just its portion), joint (each debtor is individually responsible for the entire commitment), or joint and several (the creditors hold one debtor fully responsible, who then pursues other debtors). Serial composition uses several responsibility so that a debtor is never compelled to assume additional responsibilities. The result of serial composition is useful for reasoning about multiple commitments, but all the original commitments must be kept around if we need to determine which specific debtor(s) failed and broke the chain reaction.

Serial composition composes just two commitments, but we can use it repeatedly to combine a chain of multiple commitments. To compose more than two commitments, compose from left to right (the serial composition operator is left associative).

Enough theory, we need an example.  Assume Alice promises to pay Bob some money.  If Alice won’t see Bob today, she can pass the money through Chris, a trusted friend of hers.  (I refer to this as “pay via middle man” or PayViaMM).  There are two commitments.  The first is Alice’s commitment to pay Bob.  The second is Chris’s commitment to pass on any payments he receives (Alice trusts Chris because of this commitment).

This is another post about using commitments to describe various real-world situations.  For thousands of years, mathematicians have used rules to mechanically transform algebraic equations into simpler and more useful forms.  Similarly, we can define rules to transform agent commitments into simpler and more useful forms.

Let’s extend the pizza example.  Assume Alice commits to Bob that she will give him a pizza and a beer if he either gives her $10 or he helps her move to a new house.

C(Alice, Bob, $10 or helpmove, pizza and beer)

We can break this single commitment down into a set of simpler commitments.  First, Alice will give Bob pizza and beer in either of two situations (an OR operator in the commitment’s antecedent).  This gives us two simpler commitments.

C(Alice, Bob, $10, pizza and beer)
C(Alice, Bob, helpmove, pizza and beer)

We can decompose these down even further, because Alice will give Bob both a pizza and a beer (an AND operator in the commitment’s consequent).  This gives us four commitments

C(Alice, Bob, $10, pizza)
C(Alice, Bob, $10, beer)
C(Alice, Bob, helpmove, pizza)
C(Alice, Bob, helpmove, beer)

Symbolically, we write these commitment transformations like this

C(debt, cred, ant1 OR ant2, csq) = C(debt, cred, ant1, csq),   C(debt, cred, ant2, csq)
C(debt, cred, ant, csq1 AND csq2) = C(debt, cred, ant, csq1),   C(debt, cred, ant, csq2)

In some situations, it is easier to work with these four separate commitments so decomposing a complex commitment makes sense.  In other cases, we might want fewer commitments, and reverse the transformations, merging simpler commitments into more complex commitments.

The key point is once we explicitly describe commitments, we can also define rules to mechanically manipulate them, just like we do with algebraic equations.

This time we look at two, additional commitment operations: delegate and assign.  Commitments relate debtors (the agents making the commitment and the agents who are responsible for satisfying it) and creditors (the beneficiaries of the commitment).    But sometimes, one agent makes the commitment, but another agent becomes responsible for satisfying it.  At other times, one agent negotiates the benefits of a commitment, but wants to transfer those benefits to another agent.   So after the commitment has been created, we may want to change either the debtors or the creditors or both.

For example, my Manager makes a commitment to his Executive to do some work and give a presentation on the results of the analysis.

CC1 = C(Manager, Executive, receiveRequirements, performTask and givePresentation)

Then he delegates this commitment to me.

CC1.delegate(Scott)

Now, I am on the hook to satisfy the commitment because I’m now the debtor, not my Manager.  Note that the identity of the commitment (CC1) is not changed by these operations; it is still CC1 even after being delegated.

CC1 = C(Scott, Executive, receiveRequirements, performTask and givePresentation)

Now let’s say, the original Executive creditor decides that her manager (SeniorExecutive) really needs to see the resulting presentation instead.  So she can assign the commitment, which changes the creditor for commitment CC1.

CC1.assign(SeniorExecutive)
CC1 = C(Scott, SeniorExecutive, receiveRequirements, performTask and givePresentation)

Many papers use the operation delegate to change debtors and assign to change creditors, as I’ve described here.  However, in my work, I use the more generic transfer operation to do either delegate or assign.  This is just a low-level detail, since both have the same effect.

Delegate and assign further demonstrates the flexibility of commitments.  Commitments explicitly capture an important type of relationship between agents; they capture something that debtors should do in the future.

OrderPayShip (the “workhorse“) showed one way to use commitments.  In today’s example, I’m going to show a different commitment pattern, which more directly models a legal contract.

Let’s assume Bob sells cars and Alice wants to buy one.  Expensive items like this (much more expensive than a pizza) often involve an explicit legal contract.  In this case, Alice and Bob want binding signatures on a legal contract.  We still need two commitments: one from Alice to Bob and one from Bob to Alice.  The trick is to make both commitments become active exactly when BOTH Alice and Bob have signed the contract.  We can model this legal contract as

C(Alice, Bob,  AliceSigns and BobSigns,  AlicePays)
C(Bob, Alice, AliceSigns and BobSigns, BobGivesKey)

Both commitments SIMULTANEOUSLY become unconditional only after both Alice and Bob sign the contract.  Then both parties have to satisfy their individual commitments.

The Workhorse pattern involved only two agent actions:  pay and ship.  What happens when each agent must perform lots of actions?   The legal contract pattern enables you to collect all of a single agent’s commitments to others into a single commitment.  So a more complex example, where Bob provides continuing service to keep Alice’s car running, might look like this

C(Alice, Bob,  AliceSigns and BobSigns,  AlicePays and AliceBuysGas and AliceMaintains)
C(Bob, Alice, AliceSigns and BobSigns, BobGivesKey and BobServices and BobRepairs)

The difference between Workhorse and Legal Contract is more style than substance.  This means you can approach problems from multiple directions.

I am going to post some examples of how you can use commitments to describe various real-world situations.  Remember that a commitment is a promise by a set of debtor agents to a set of creditor agents.  By explicitly modeling the commitments through out an interaction, the agents involved can better understand, at each step, what they have done in the past and what they still need to do in the future.

Today’s post is about a protocol called OrderPayShip.  I use it so often that I call it The Workhorse.   This example shows a “classic” interaction pattern for incrementally creating and satisfying commitments in a business transaction. It’s an interaction—or protocol (more about protocols in upcoming posts)—between a Buyer (she) and a Seller (he).  The protocol incrementally creates two commitments, and then incrementally satisfies those two commitments.

Let’s look at a common sequence of messages exchanged between these two agents using the OrderPayShip protocol.  I’m only going to talk about the “happy path” of this protocol for now—the one that both agents hope will happen—and skip any error conditions for now.  Five messages are exchanged:

1. Buyer requests a price quote on some good.  Suppose Buyer wants a pizza, walks up to Seller’s counter and she asks how much a pizza would cost.
2. Seller returns his price quote.  That is, Seller tells Buyer that a pizza costs $10.  This message also means Seller commits  to Buyer that he will give the pizza to Buyer, if Buyer pays the quoted price: C(Seller, Buyer, $10, pizza).  Typically this information is implied by the interaction, but we track commitments explicitly.
3. Buyer likes the idea of a $10 pizza, and she places an order.  Placing the order also means Buyer commits to Seller that she will pay, if Seller gives her a pizza:  C(Buyer, Seller, pizza, $10).
   At this point, there are two reciprocal commitments: one from Seller to Buyer and one from Buyer to Seller, and both commitments are conditional.  The protocol could stall at this point, because neither agent is required to do anything more.  But since both agents are interested completing the order, one of them will typically make a move.
4. Here, I assume Buyer sends her payment first.  This satisfies Buyer’s commitment and also makes Seller’s commitment unconditional.
5. To satisfy his unconditional commitment, Seller gives her a pizza.  This satisfies Seller’s commitment.

At this point both commitments are satisfied and the protocol is complete.

 

 

 

I hope launching this blog on April 1st  encourages a bit of whimsy to this blog, rather than being some kind of bad omen.

My plan is to blog about a range topics, as suits my fancy.  I am very interested in multiagent systems (MAS) technology and applications, and I believe it can and should have major positive contributions to many facets of our modern world. I expect MAS to be the topic of most of my posts.  The semantic web and knowledge graph technologies are a way to efficiently represent and reason about complex data.  As a member of IBM’s Watson project (see disclaimer below), I spend quite a bit of time thinking about natural language processing (NLP).  Mathematics has always fascinated me, and I have “mental back-burners” that are constantly churning on such things.  Java and various web technologies could easily find their way into some of my posts.  Rest assured, I have no plans to post vacation or baby pictures, or meaningless updates on where I’m currently eating, drinking, or stuck in traffic.

I encourage comments of both serious and less-serious natures.

Scott Gerard (gerard at gerard.guru)

Standard disclaimer:  I am personally responsible for all content.  I am not speaking on behalf of my employer.