What is PyNeg?

PyNeg was developed during the writing of my ACOP paper. The only other known library for simulating automated negotiation was Genius. This library was quite mature as it was used in all of the Automated Negotiating Agents Competition (ANAC). However, it did also have some drawbacks, namely that it was in Java instead of Python. While I am proficient in Java, it does lack a lot of the analyses tools I use and inter-language communication is always something that I try to avoid whenever possible. Additionally, I knew that down the line I wanted to incorporate Problog into it which is considerably easier with Python given that there is already a ProbLog package on PyPi. Another reason was that Genius included a lot of infrastructures that made it difficult for me to set up the kinds of scenarios that I wanted. All of these things taken together led me to decide to write my library in Python, the only one at the time of writing as far as I am aware. That also helped me understand the actual mechanics of automated negotiation a lot better. Below I'll talk a bit about some extra perks I managed to get out of writing a library from scratch.

Design philosophy

A native Pythonista will probably look at the code of PyNeg and give me some side-eye afterwards. I will admit it's not written in very idiomatic python, that is partly deliberately. I started my programming career in C++ and used that for the majority of my formative programming years after which I switched to Java before I got into Python. So even though Python is my main language, for now, there are some concepts that I've never really been able to let go of, most notably static typing, and object orientation. While Python doesn't natively support type annotations, there is a very good library that does a fairly good job of that: MyPy, which I have used to annotate the entire library. While it has caused a few odd pieces of code, it has helped me stay sane throughout the debug phase, so overall I think it's a win.

Additionally, while I was working on this library I was also learning Rust as a hobby and specifically the idea of composition over inheritance resonated with me. This together with a few other concepts I integrated into the library might lead to some unusual coding styles but I personally really like the way it turned out.

Decentralised communication loops

Because the research group I was working with did a lot of work on coalitional and decentralised settings there was quite a bit of talk about integrating this work into different projects along the way. For example, there was the idea that I might collaborate on a Reinforcement Learning project one of my colleagues, Laura D'Arcy was working on. (BTW she is doing some amazing work on Multi-Task Reinforcement Learning over at her GitHub and you should check it out.) This meant that fairly early on, I decided that I wanted the communication loop to be decentralised. What I mean by that is that there is no external structure that has to actively manage the communication between the agents. All the external structure did was set up the negotiations, set up the agents and tell them to start the negotiation. While I didn't have time to implement it, this has the nice perk that it would be relatively easy to extend the current code to be able to handle multi-to-multi party negotiations or let the negotiation agents work asynchronously.

Composition over inheritance

I tend to think in a very object-oriented way, which has its drawbacks. For example, in the library, there are many different kinds of tasks an agent can and can't do but here I will focus on three specific ones:

  1. Base (B) vs Constraint aware (C)
  2. Probabilistic (P) vs Deterministic (D)
  3. Linear (L) vs Non-Linear

If you want to make any pair of combinations of those traits an option, you almost inevitably end up with a dependency tree that looks a bit like this: Exponentially growing dependency tree

The biggest problems with this is that

  1. The tree will grow exponentially as you add more traits
  2. You either end up with unnecessary duplication (L+C+D vs C+L+D) or you have to make a very arbitrary decision about what lives where.

This is where the idea of composition instead of Inheritance comes into play. Instead of building agents into a rigid dependency tree like that, we just define components that can or can't do certain things. Rust has a elegant Trait system to deal with this. I tried to emulate that to a certain degree, though it was a bit harder to do that in Python. The idea is that an Agent has an Engine that does all of the reasoning, while the Agent itself only has to deal with the communication. We can then build different Engine classes that can be any of the combinations above, instead of having to make an entirely separate class for these kinds of agents we just implement the pieces into an engine and that can work with any of the other components within the library. It did mean I had to make a few empty passthrough classes to make them play nicely with MyPy, but overall I like the result.

Easy extendibility

This part is a bit of an extension to the previous point, but because of the kinds of comparisons that I wanted to do, I also wanted to make sure that it was as easy as possible to create new kinds of agents with different kinds of properties. This is fairly well achieved by the use of the composition. If someone wants to make another type of agent all they have to do is provide an implementation for the Engine class, which is what they'd have to do anyway and make a simple factory function, and that's it! Pretty neat right?

Future work

While I think PyNeg is a really solid foundation, the work at the moment isn't all that interesting itself. It only supports atomic constraints (which if you want to learn more about you can do so at either the Pyneg documentation or my paper). The easiest avenues for extension would be either more complicated constraints and the machinery to reason about them, a probabilistic environment to take better advantage of ProbLog, or the exploration of non-linear scenarios.

I've toyed with the idea of reimplementing this library in Rust as a Kata. Especially because that could reduce the communication overhead, and streamline a lot of the communication code due to its stellar type system. Besides, Rust is very fast and has a good Python FFI and those two things are big boons if you're running large simulations for statistical benchmarks. However, there is no ETA on that as of the time of writing.

#Python, #Automated negotiation, #Multi-agent systems, #Reasoning about uncertainty