SCML Standard Challenge: Long Term Planning and Automated Negotiation

In previous articles, I introduced the topics of automated negotiations, the International Automated Negotiating Agents Competition (ANAC), and the Supply Chain Management League which will run as part of the official competitions track of IJCAI 2021 — the top AI conference — this year. Winners will receive monetary prizes and will be announced during IJCAI.

The previous article focused on the SCML-OneShot track. This article focuses on the SCML-Standard track, which aims to combine the challenge of concurrent negotiation with long-term planning.

The SCML standard track runs in the world depicted in this image:

SCML World
SCML World

Here we have a set of products and manufacturing processes. Each process receives one item of product and converts it into one item of product at some cost. The chain of products and processes shown in the image above is called the production graph.

In this world, we have a set of factories. Each factory can execute one and only one process at some cost specific to this factory, known to it and unknown to all others. Agents control factories and try to maximize their profit.

Demand in this market is driven by a set of exogenous sell contracts for the set of factories that can execute the last process and supply is provided by a set of exogenous buy contracts for the set of factories that can execute the first process.

Up until now, the world of SCML-Standard and SCM-OneShot seem almost the same with the single difference that the production graph can be deep (i.e. with more than 2 processes) in the standard game. This simple change implies that the agent must be developed to work anywhere in the chain. Notice that agents in the first and last level of the chain are facing a mirror image problem. They both have some exogenous contracts on one side and need to negotiate to match them on the other side while maximizing their profits. In a deeper chain (as in SCML-Standard), agents in the middle need to negotiate on both sides simultaneously. This gives us the first main difference between the two tracks:

Agents need to work anywhere in the chain not only on the edges in SCML-Standard.

While we are at it, let’s discuss a second difference. In SCML-OneShot, agents have exactly one exogenous contract at every step and all exogenous contracts are binding. Moreover, once two agents reach an agreement through negotiation, this agreement is immediately binding. In SCML-Standard, neither of these properties is true anymore. Here, all agreements (exogenous and negotiated) become binding only if both agents party to it confirm the agreement by signing it during a call to their sign_all_contracts() method. This is both a blessing and a curse.

Why? On one hand, it provides the agent with the opportunity to choose which contracts to sign to maximize their profit. For example, if on the last day, an agent (with a production cost of 1) has 5 agreements to buy its input product at 10 dollars each and 2 agreements to sell its output product at 12 dollars each, it can choose to sign only 2 of the buy contracts achieving a profit of 2 × (12−1−10) = 2 dollars. If agreements were immediately binding, the agent would have lost (3 × 10 − 2 × (12−1−10) = 28) dollars. Can you see why?

Ok, that is the blessing 😀, what is the curse 😢? The partner can also decide not to sign. This means that it is simply impossible to be sure about your profits. In the example above, the agent may decide to sign two buy contracts but both of these suppliers decide not to sign them leading to it receiving no inputs. On the other hand, the two consumers may decide to sign which means that there will be a shortfall and the agent will have to pay a penalty for not delivering!!!

The fact that contracts are binding only after being signed not upon agreement is a mixed blessing. An unfavorable agreement is not a disaster but it is impossible to estimate profits exactly.

Two other main differences between SCML-OneShot and SCML-Standard make all the difference: products do not perish, and delivery time is negotiable. The first means that agents can accumulate an inventory of either their input material or output product and the latter means that agents can negotiate about receiving/sending products in the future (not only today). This combination means that the agent cannot only think about today while negotiating but needs to consider the future. This is why long-term planning becomes a central issue in agent development in SCML-Standard.

Long term planning is a central issue in SCML-Standard because products do not perish and delivery time is a negotiation issue.

You can see a complete list of differences between the two tracks with the associated implications here.

From now on, we will refer to SCML-Standard simply as SCML.

For an agent to be successful in the SCML world, it needs to buy input materials through negotiation, manufacture them, then sell output products through negotiation. It is possible to structure our agent as a combination of three main strategies/components:

  1. Trading Strategy: Deciding the quantity (and price) to buy and sell at every day. This component can employ two subcomponents:
  • a pre-negotiation component that decides the quantities/prices to negotiate about based on the prediction of future market behavior (trade prediction strategy) and partner behavior (partner behavior prediction strategy)
  • a post-negotiation component that decides what agreements to sign as contracts (signing strategy).
  1. Negotiation Control Strategy: This component is responsible for proactively request negotiations, responding to negotiation requests, and actually conducting concurrent negotiations. This component can further be divided into two subcomponents:
  • a pre-negotiation component that decides which negotiations to accept and which to engage in (negotiation manager)
  • The negotiation algorithm is used to carry out the negotiations decided by the negotiation manager.
  1. Production Strategy: Decides what to produce every day.

This is a visual representation of these components. You can watch a detailed description of these components here.

Agent Anatomy in SCML-Standard

.

You can develop your agent by just overriding the base SCML2020Agent class and overriding some or all of its callbacks. Consider, for example, the callback on_negotiation_success(). When you receive this callback from the simulator, you need to do whatever is necessary to update your trading, negotiation control, and production strategies. This is what we call a monolithic agent. Maybe you can just call three internal methods to do the necessary work:

  • trading_on_negotiation_sucess
  • negotiation_on_negotiation_sucess
  • production_on_negotiation_sucess

Other than the obvious explosion in method names and the number of methods, this approach makes it harder for others to reuse your code. What if someone likes your trading strategy but not your negotiation strategy and at the same time likes the negotiation strategy of a third participant but not their trading strategy? It will not be easy for them to reuse the parts they like. Moreover, if all of these methods are sharing state by changing the agent’s data attributes, it may not be even possible to do the combination.

You are free to organize your agent in this monolithic way but — for this post — we will assume that you would like to use a more modular approach. In the scml package, we use cooperative inheritance to achieve this goal.

The SCML platform provides several components that can be used to implement each of the three strategies and you can combine and match them as you like to generate new agents. The tutorials explain existing components, their relationships and how to use them. This post focuses on explaining the idea of cooperative inheritance used to organize these relationships.

The idea of collaborative inheritance is to make it possible for users of a class to replace the behavior of any part of it simply by adding another base class. In Python, our main weapon to implement this pattern is super(). For a clear explanation of this use of super, refer to Hettinger’s post and his excellent talk on YouTube.

Let’s consider the following three classes:

BaseClass, and Component1 have implementations of the same method (init). What really matters here is the method name (parameters need not match). The Agent class inherits from both of them. What happens if we call init:

You will see that Component.init() is called because we can see the following printed:

Nevertheless, BaseAgent.init() was not called. We can solve that easily by changing our code to the following:

Now we get:

That makes sense. The call to super() was resolved to BaseAgent.init() which is now called after the print in Component1.init() as expected.

What will happen if we change the order during inheritance:

Now we get:

What just happened? The python interpreter was asked to find BadAgent.init(), it looked in the base classes in the order they were given when BadAgent was defined. It looked first for Agent.init() and found it so it did not even try to find Component1.init(). That is why we do not see Base intialized. Can you imagine what will happen if we add super().init() to BaseAgent itself?❓

In general, the python interpreter will use some predefined Message Resolution Order (MRO) to locate any attribute (method or otherwise) you try to access. The MRO is simply a list of class names that are checked to locate any attribute. You can find the MRO associated with any class by calling its mro() method. Here are the resulting MROs for Agent and BaseAgent.

  • Agent → [Agent, Component1, BaseAgent, object]
  • BadAgent → [BadAgent, BaseAgent, Component1, object]

The algorithm used to find this order is called C3 linearization and it is guaranteed to generate a list from any inheritance graph (even with common base classes). Two very important features of the MRO that is guaranteed by C3 are:

  • Classes that appear first in the inheritance list are checked first.
  • Children are checked before parents.

There are several blogs and tutorials that describe how this whole thing hangs together. For our purposes, I will focus on one specific emergent behavior that we use in collaborative inheritance. Consider the following two classes:

It is easy to see that B().init() will print BA. But what if we want to change how init() behaves and force it to print BE without touching B, or reimplementing A.init()? Here is one way to do that based on our current understanding of super():

Let’s check the MRO. Because B appears before E in D’s inheritance list, it must appear before it in the MRO. Moreover, because E is a subclass of A, it must appear before it in the MRO. These constraints give us the following MRO: [D,B,E,A]. E comes before A which forces the call to super() in B to call E’s version instead of A’s version which is what we want.

You can check for yourself that if E does not inherit from A, we get [D,B,A,E] which will print BA (i.e. E and D are really useless in this case).

Now if we run D().init(), we get BE as we wanted. The recipe is simple: To replace some method m() that a class X inherits from some parent B (directly or indirectly):

  1. create a class E that inherits from B and implements m() without calling super() in it.
  2. create a class Y that inherits from X and E (in that order).

Now Y behaves identically to X with the single exception that the method m() is now replaced with the new implementation in E.

To add behavior to some method m() that a class X inherits from some parent B (directly or indirectly):

  1. create a class E that inherits from B and implements m() and call super() in it.
  2. create a class Y that inherits from X and E (in that order).

Now Y behaves identically to X with the single exception that the method B.m() is called either before or after E.m() depending on where did you call super() inside E.m(). As an example consider:

You can confirm that D1().init() prints BEA while D2().init() prints BAE.

You can use inheritance to either add to or override the behavior of some method no matter how deep is it in the inheritance hierarchy using cooperative inheritance. We call adding behavior hooking into a method and overriding behavior (well) overriding a method.

Cooperative Inheritance in SCML

As I explained earlier, there are three main problems that the agent faces in SCML-Standard:

  • Trading Strategy Long-term planning.
  • Negotiation Strategy concurrent negotiation to achieve the plan.
  • Production Strategy controlling production in the factory.

These are top-level strategies. To maximize reuse, we also provide lower-level strategies that are used by these top-level strategies. This makes it easier to choose and match. Some of the most important lower-level strategies are:

  • Signing Strategy Decides what to sign. Used usually by the trading strategy.
  • Trade Prediction Strategy Predicts future trade. Used by the trading strategy.
  • Execution Rate Prediction Strategy Predicts the probability that a given contract will actually be signed and executed. Used by both the negotiation manager and trading strategy.

The scml package defines one class of strategies to match each of these top-level and lower-level strategies. Each of these is called a component and a component is defined by the following:

  • Hooks These are the callbacks that it hooks into. For example, the DemandDrivenProductionStrategy hooks into the callback on_contracts_finalized to determine what to produce based on knowledge of signed contracts. Because this is a hook, other components like say the trading strategy can hook into the same callback. This is another hook example from the same strategy:
  • Overrides These are the callbacks that are overridden by the component. For example, some trading strategies override the callback sign_all_contracts to control what is being signed by the agent. This is how overriding is implemented for this case (notice that super() is not called):
  • What it provides These are methods/attributes that the component controls and provides for other components (usually to read but not modify). For example, all trading strategies provide an attribute needed_inputs that defines the number of input product units needed per day. The negotiation manager may (and does) use this value to adjust its behavior during negotiation.
  • What it requires These are methods/attributes that the component expects to exist in the agent. For example, the negotiation manager expects that the agent will have an attribute needed_inputs (see the previous point).
  • Attributes These are named arguments passed to the constructor of the component and used to control its behavior. The constructor of the component should consume these parameters and pass the rest (through super()) to the constructors of other components. For example, the KeepOnlyGoodPrices signing strategy has two parameters buying_margin and selling_margin that define what a good price is. That is how its constructor is implemented:

As you can see, the constructor consumes these two arguments and passes the rest along to construct other components. This is how the system can construct all components without knowing a-priori the names/types of arguments needed to construct each component.

  • Abstract These are optional methods that all children must implement.

Using these components, the built-in DecentralizingAgent is now extremely simple to write:

That is the complete code. It simply chooses which component to use for each of the three top-level strategies. The _NegotiationCallbacks implements the abstract methods needed by the specific negotiation manager used.

Here is another example:

That is the complete code of another agent. You can immediately see that this agent shares the trading and production strategies with the previous agent. It only differs in the negotiation manager it uses which has one extra abstract method (create_ufun()) that is implemented by this agent.

In 2021, the game introduced public information about the market that was not available to the agent in 2020. To build a similar agent that utilizes this information, we only had to add:

Here you can see that two components are being replaced. Both components are lower-level components (the signing and trade prediction strategies). Now this agent can utilize the extra information without us touching the code of the trading strategy itself.

The main goal of this post was to clarify the main differences between the SCML-Standard and SCML-OneShot games and provide the justification and some overview of cooperative inheritance as used in SCML-Standard. The next step is to check the tutorials for detailed explanations of each component and examples of creating new agents based on them.

A principal researcher at NEC Data Science Laboratories, A researcher at AIST, and an Associate Professor at AUN.