A breakthrough in algorithm development for network barter

For Economy App, it has been a time since the last update, with not much to say as we were programming away quietly. As always in software, we were chasing a moving target, always finding new software bugs to fix before our upcoming public beta test launch. And in addition, we had a dreading task before us: implementing the network barter algorithm for real. Because from our existing prototype implementation to a fast, scalable, real-world one it is usually a long way. And in the case of network barter, a technological challenge (since our prototype needed a whole night of calculations to find even the tiniest network deal in our simulation data.)

However, due to the collaborative power of open source software, we just made a big jump forward, saving us several person months of work :slight_smile: :slight_smile: Meet our new friend COIN-OR, a solid and powerful free software library for mathematical optimization problems, provided by the mathematical science community.

This development came about when my teammate Daniel found that network barter can be classified as a different mathematical problem: not as a match-making problem (as we did before, and is often done in related scientific literature), but more broadly as a deterministic linear discrete optimization problem. Which can be solved with Linear Programming. And that is what COIN-OR has the tools for.

So sometimes, looking at your problem differently is 90% of the solution :slight_smile: We have now an initial implementation running based on COIN-OR CBC, and it is 100-1000x faster and finds much larger network barter deals than the prototype we had before.

See below for one of the first network barter deals found by CBC. Notes on the graph:

  • circles are users, squares are product / services
  • red arrow means a user providing a product or service
  • green arrow means a product being received by another user
  • you can check that this graph shows a valid barter deal: for every user, the value attached to incoming arrows must be the same as the one for the outgoing arrows
  • orders not included in this network barter deal are not shown, amounting to about 3-4x the included orders
  • price quantization in 5 EUR steps is used, but no longer needed as we since found

Image credits: COIN-OR logo, copyright by the COIN-OR foundation and released under the Eclipse Public Licence (EPL).

1 Like

deterministic linear discrete optimization problem

As a non-mathematician I can relate to “match-making” and conjur up an image in my mind. I can not do the same for “deterministic linear discrete optimization problem”. Can you say more about that in lay terms or maybe give some kind of simplified example?

Good question

Here is my (preliminary) understanding of what this stuff means: deterministic – a solution can be found in principle, and there is a way that describes how; linear – all conditions for the solution can be described in linear equations (with the unknowns in the first power; this is “good” because of calculation efforts I think); discrete – solutions are to be delected from discrete candidates, not from a continuum. Looking for discrete solutions is also why the mathematical subject is called “integer programming” or “integer linear programming”. But I have to say that I’m new to this area of math as well: the COIN-OR CBC solver is a comfortable solution, even too comfortable maybe, as it limits the motivation to learn the math (which we should do at some point however, to be able to make improvements to the COIN-OR standard implementation).

Petri Nets

Hello, as I told you on Twitter, I think that the diagram above is an example of Petri Net, where users are places and products are transitions. Petri Nets can be described using Linear Algebra and several properties can be reformulated as operations on matrices (see here). However, I have not understood how barter works in your model. I wonder if you can give me a very very simple example. For instance, I do not see any value attached to arrows and I do not know what “price quantization” is and how it works. Thanks a lot! :slight_smile:

Network Bartering

Thanks again for your input :slight_smile: I have now discussed Petri nets shortly with my teammate and we’ll see if it can help us further! I’m not too sure yet because it seems that Petri nets are used to describe processes, while our barter graphs represent atomic multi-party transactions (in analogy to financial account movements with the added property that for every account holder the transaction total effect must be zero).

Regarding network barter: There is an introductory description with a small network barter deal graph in our detailed description PDF document (just scroll through until you find the graph …).

You don’t see value attached to arrows because it is here attached to the products (square nodes), but this is just a matter of presentation. And price quantization is my name for a Fiverr style pricing scheme, where prices can only be multiples of a base price (“quantum”, in this case 5 EUR). This helps our network barter algorithm to find barter deals because prices can match exactly. However later, we run the algorithm on an order graph with arbitrary prices but allowed a certain mismatch amount (say, 5-10%) of prices via a “private reserve price” feature where sellers can enter a hidden, second price that they would agree to sell for at lowest – and guess what, the algorithm also found large enough deals in this case.

Welcome to ask more questions, to give us feedback on the idea, or to add own ideas if you like :slight_smile: We’re always on the lookout for how to make this type of bartering more flexible, until it becomes hopefully nearly as flexible as money is today …

Thank you for your reply. I will have a look at the paper during the weekend if it rains (otherwise, I will go climbing :P).

1 Like

sympathy factor?

i must admit not reading up yet the deails of algorithm you work on :(

can you imaging adding aspects of SYMPATHY to it? one could assing different levels of sympathy to different to peers in network, which would affect this number ones assings for offering something.

let’s call products and services - assets [squares] and people and organizations peers [circles]

peers can offer assets assingning not just a value but a range, also each peer can assign +/- factor of sympathy toward other peers. depending of peers participating in a chain each peer would agree to release asset with lower or higher number within a selected range.

if i make no sense i will need to read up on details of this algorithm first :smiley:

1 Like

Nice one :slight_smile:

It makes sense! Your feature proposal can indeed work in our current framwork. Because we already have price ranges in place (public price and a private “reserve price” that the seller would also agree to give the item away for, should the algorithm need that). Price ranges are needed by the network barter algorithm as additional flexibility so that it can find enough deals. So if, via your sympathy feature, these price ranges would be extended according to sympathy levels, it fosters both better social connections and more network barter trades. The feature will probably not be in the first public beta release (which is a sort of minimum version), but I have put it on our list of feature ideas for the future.

Thanks :slight_smile:

1 Like

estimating assets offered by other peers or sought by us?

just dumping another idea :slight_smile:

i would find it possibly useful if all the peers in networks have also possibility of publish their numeric estimations for assets offered by other peers. as well as system trying to clearly track relations between assets, for example marking them as resources of exactly the same or very similar type (apples offered by Alice match in certain way apples offered by Bob) and then show history of numbers used for given type in past clearings (incorporating of course aspect of physical units of mesure: piece, kg, kWh, liter, hour etc.)

in general i find concept of considering something to have value (noun) in many ways naive and see it more as someone does value (verb) something, emphasizing subjective nature of this phenomena of our individual perception. still while we decide to assign numbers to assets i would like that we try to also incorporate assigning such numbers to relations between peers and assets. it would give more clear impression about peole valuing something rather than someone claiming that it has certain value!

do you currently support assigning numbers / ranges to assets which you seek? maybe please also take a look at this concept from VRM: https://cyber.law.harvard.edu/projectvrm/Intentcasting

1 Like

Good ideas, but with some practical issues :slight_smile:

Clustering (near-)equivalent assets can indeed be done automatically based on the relations how products appear in “lists of mutually alternative orders” of different buyers. Unfortunately, this is only possible after an asset got offered and ordered, so cannot help the seller to assign an adequate value. The other alternative would be to use a system like on NetCycler, which tries to match assets based on their physical properties (product type, size, colors etc.). That is however horrible from a UI point of view, as all this formfilling is very unpleasant work. What would work is using ISBN / EAN codes for this, and also apply it to easily standardized bulkware (like yes, apples). We did not add this for now as we focus on the DIY economy, not on (used) industrial products. So most of the stuff offered on the platform will not have ISBN / EAN …

Ok, but I remember that I often use the “search in past transactions” feature on eBay when trying to estimate a good offer price for a product. That would work in network bartering as well. Noted, thanks!

About value / valueing: of course value is extremely subjective. A seller assigning a price means, thus, that the seller values the item equivalently and would not like to give it away for less. A price is thus a threshold for how much a potential buyer has to value an item at the minimum in order to enter into a transaction with the seller.

(About intentcasting: prices can be assigned to tasks, which are service-assets sought by a buyer. Again in terms of UI, I do not see a way to implement seek ads for products as a meaningful feature. Products need to be standardized to be produced efficiently (also in a DIY / maker economy). That’s how they differ from services. So for services, it makes sense that the buyer can publish a very specific request what has to be done, while for products, it makes no sense and it should instead be left to the buyer to select the best match out of the existing products on offer.)

There is a very interesting affordance in a barter economy that allows to not have any public pricing at all. I think you will like this idea, so I just copy it here (though we won’t implement it because, to reach volunatry adoption for this first-ever network barter platform, we align as closely as possible with concepts that ordinary people already know about economic transactions):

Bid pricing with individual units of account

This is to solve the problem of value skewing / prejudice which is inherent whenever using one unit of exchange for one market. Examples of these problems include: (1) In forex currency exchanges, economies of developing regions get disadvantaged when importing as their currency is weak. And this means everyone gets disadvanatged, even though there are some companies who produce as efficiently as those in developed regions. And (2) when using legal tender as unit of account in a barter economy, the prices from currency-based markets will be used as references. This is bad, since these prices include all kinds of skewing influences, including state subsidies, artificial scarcity, extremely cheap offers enabled by industrial production and artificial price increases for example of labor by heavy taxation and regulation that limits the supply on offer. With such prices as reference, maker production is hardly possible for example, as it cannot compete with industrial production (used goods, for example).

The solution is to let everyone price their own offers in a self-selected unit of account, which has to be one of their own active offers. So people will select to use their main offer (like: an hour of their professional service) as unit of account, and express bid prices for things they want in this, and also how much their other offers are worth in comparison. In effect, all people have a very natural unit of account, just as when using legal tender, or even more natural (like saying “I would work half an hour for this.”).

The more important effect is, however, that pricing is now always adequate for every situation of peoples’ offers and demand priorities. It does not get skewed by external influences, but is similar in effect to what people would agree when negotiating a barter deal manually. Just that it can still be completely automated: user A expressed that she wants a certain amount of (say) A-hours for a certain offer, and how many A-hours she would work for certain wishes, and from this the system can know when a deal is balanced for her. And when it’s balanced for every participant, it is a valid deal.

The best property of this idea is probably that it is applicable for exchange between all kinds of alternative economy networks and communities: They might never agree on using any standard value of account (some might be against using legal tender as that, some against shopping baskets, some against using an alternative currency because of, some against using any unit that they are not familar with etc.). But when allowing everyone to use their own unit of account, there is no issue whatsoever.

This is a feature to replace price tags on items. Items would just be offered on the platform without public price tags!! The reason is that trade should be enabled by the subjective value assigned to items by the buyer, not the common “market price” normally used by the seller to price items. Because this leads to a higher trade volume, enabling trades that are blocked when stuff is offered for “market prices”.

The inspiration came from this: “The first problem with money is the fact that a seller is forced to place a uniform price on a good. This means that some potential buyers will get away with paying significantly less than what the good is worth to them, and others will be turned away because the price is too high. Both the seller and buyer would be better off if the maximum number of possible trades went through. because each party gave a mix of goods and services acceptable to the other. Pamas develops an example involving four parties each interested in acquiring certain goods for other goods. If prices were set, none of the trades would go through, but with barter, he shows that all of them would be possible.” [Donath-1, p.2]

This innovation does away with the idea of a public market price. Interestingly, this entails doing away with the classic economic idea of the “law of supply and demand” that is said to lead to the market price. Instead, demand is also always relative to ones own income, and this is covered by this new idea of “private prices”. See: “Current economic models are based on money both as the medium of exchange and as the measurement of value. Walrasian general equilibrium model is the main paradigm through which the various market phenomena are explained, the so called Law of Supply and Demand. This paradigm is facing increasing difficulties and solutions are being searched” [source, p. 9]

Modes of use?

As shown the lines represent already completed (but unpaid) transactions, so it would seem to show network credit clearing rather than network barter?

So we are assuming a community of ‘traders’ all of whom agree to accept payment via barter for outstanding transactions at the point of joining?  Achieving critical mass issue?

Alternatively if we are looking for the model to flush out and match potential clients for goods/ services, the box values are offer prices. This enables the model to build its user base gradually, but poses the problem of precise prior product definition.

1 Like

This is credit-free barter indeed

Thanks Graham for the input, and “officially” welcome to the Edgeryders community as well :slight_smile:

The network barter system, as we designed it, does not use credit (as credits always involve trust and risk issues, which keep LETS currencies from widespread adoption for example). There is one exception from the no-credit rule: worktime is settled in several transactions, so can be considered a kind of “credit”. However not more than the unpaid chunk of worktime between start of work and payment of an invoice can be considered a “credit” in monetary economy. As people are used to that, we think it’s not a problem for voluntary adoption. (Side note: I don’t understad how credit clearing is a problem with critical mass, since in such a system new credit can also be added when new transactions are recorded. Essentially as done in Ripple.)

So yes, the above graph represents a “trading circle” that matches offer and demand of products and services: every arrow path between two users (circles) represents a “sale”. The graph is a subset out of a much larger order graph that also contains the not yet fulfilled orders, and is now diminished by the orders executed in the graph shown above. You say, it creates the problem of precise prior product definition. That is true, esp. since product returns are not easily possible in a network barter economy. However, the problem is just the same as for example in webshops and on eBay: sellers describe their own products. We, the platform, do not create “standardized” product definitions because there are simply so many different ones around. It would work for bulk goods (as done by openBarter) and things with an EAN / ISBN (as done on Amazon), and we might add that later as it offers some advantages for the barter algorithm.