Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

August 7, 2021

Optimal Transport and Enriched Categories III: Duality Within Pricing

Posted by Simon Willerton

Some loaves of bread.

So far in this series I’ve been writing about the optimal transport problem of deciding how many goods to send from suppliers to recievers in order to minimize transport costs whilst satisfying supply and demand constraints. I showed that there is an equivalent dual transport problem which involves fixing ‘prices’ of the goods at the suppliers and receivers subject which maximizes revenue subject to some competitivity constraints.

This time I will show that there is a duality within the dual problem, a duality between prices at suppliers and prices at receivers. I learnt about this from Chapter 5 of Cedric Villani’s Optimal Transport. I will then show that this nicely and naturally fits in to an enriched cateogry framework: the transport cost matrix being viewed as an enriched profunctor and the duality arising via an adjunction associated to the matrix.

My group at this year’s Applied Category Theory Adjoint School was looking at related matters – we should get some blog posts from them here soon – and Elise Catania’s part of the group presentation at ACT2021 was based on this material, but it doesn’t seem as though the videos have gone up for the Adjoint School presentations.

Let me set the scene again. We are considering transporting goods from suppliers S 1,,S sS_1,\dots, S_s to receivers R 1,,R rR_1,\dots, R_r. Each supplier S iS_i has a quantity σ i\sigma_i of goods it can supply; each receiver R jR_j has a quantity ρ j\rho_j of goods that it demands; and each pair (S i,R j)(S_i,R_j) of supplier and receiver has an associated cost k ijk_{i j} of transport per unit of goods. The goal is to figure out what quantity of goods to send from each supplier to each receiver so that the total transport cost is minimized.

Last time I showed that there is a dual transport problem which involves an external company taking over the transportation by assigning to each supplier S iS_i a price v iv_i that the company will buy a unit of goods for and to each receiver R jR_j a price u ju_j that they’ll sell a unit of goods for, so that, for the the consortium of suppliers and receivers, selling one unit of goods at a supplier and buying it back at a receiver costs less than the own original transport cost, ie. u jv ik iju_j-v_i\le k_{i j} for all i,ji,j. The goal is to assign the prices so that the external company doing the transportation maximizes their total revenue j=1 ru jρ j i=1 sv iσ i\sum_{j=1}^r u_j \rho_j- \sum_{i=1}^s v_i\sigma_i.

Strong optimal transport duality is the fact that the minimum cost for the original (‘primal’) transport problem is equal to the maximum revenue for the dual transport problem.

What I want to show you is a duality within the dual problem. It turns out that the optimal prices at the suppliers will be dual, in a specific sense, to the optimal prices at the receivers.

Within the dual problem we’ll have a vector of prices v=(v 1,,v s)v=(v_1,\dots, v_s) at the suppliers and a vector of prices u=(u 1,,u r)u=(u_1,\dots, u_r) at the receivers. Call a pair of price vectors (v;u)(v;u) that satisfy the contraints – u jv ik iju_j-v_i\le k_{i j} for all i,ji,j – a pricing plan.

Example. Our example was of transporting bread from three bakeries – Fletcher’s Bakery, Depot Bakery and Gerry’s Bakery – to three cafés – Cawa, Tamper and The Rude Shipyard. This had the following transport costs.

 CawaTamperRude Shipyard

The supply and demand, in loaves, was as follows.

 CawaTamperRude ShipyardSupply
Fletcher's   350
Depot   200
Gerry's   100

We are thinking of an external transport company that is buying all the goods from the suppliers and selling them back at the receivers, where the prices they can impose are subject to the constraint above.

Suppose they fix the price vector of price per unit of goods at the suppliers to be (v 1,,v s)(v_1, \dots,v_s). Then we can ask what is the highest price, v^ j\hat{v}_j, that they can charge the consortium per unit of goods at receiver R jR_j so that they are at least as cheap as the consortium’s own transportation means. So they need v^ jv ik ij\hat{v}_j - v_i \le k_{i j} for all jj and they should take

v^ j:=min i(k ij+v i). \hat{v}_j := \min_i (k_{i j}+v_i).

Then v^(v^ 1,,v^ r)\hat v\coloneqq (\hat{v}_1,\dots, \hat{v}_r) is called the kk-conjugate price vector at the receivers. This will give the external company the maximum revenue for the given prices at the suppliers.

Example. In our example we could arbitrarily fix the price the external company pays per loaf at the bakeries as follows: v=(20,25,20)v=(20,25,20).

You can calculate the conjugate prices at the cafés and you will find that they come out as follows: v^=(34,45,49)\hat{v}=(34,45,49)

This gives a total revenue of

(34200+45250+49200)(20350+25200+20100)=13,850(34\cdot 200 + 45\cdot 250 +49\cdot 200) - (20\cdot 350+ 25\cdot 200 + 20\cdot 100 ) = 13,850.

But now they can do the same again, and say for fixed prices at the receivers u=(u 1,,u r)u=(u_1,\dots,u_r), what is the minimum price u˜ i\tilde{u}_i that the external company can get away with paying for each unit of goods at supplier S iS_i to keep to the constraint. They need u ju˜ ik iju_j - \tilde{u}_i \le k_{i j} for all ii so they should take

u˜ imax i(u jk ij). \tilde{u}_i \ge \max_i(u_j-k_{i j}).

The only other requirement is that prices are non-negative, so they should take

u˜ imax(max i(u jk ij),0). \tilde{u}_i \coloneqq \max(\max_i(u_j-k_{i j}),0).

Example. Using the café prices computed above, u=v^=(34,45,49)u=\hat{v}=(34,45,49), you can compute the following bakery prices: u˜=(2,23,20) \tilde{u}=(2,23,20).

This would give a revenue of

(34200+45250+49200)(2350+23200+20100)=20,550.(34\cdot 200 + 45\cdot 250 +49\cdot 200) - (2\cdot 350+ 23\cdot 200 + 20\cdot 100 ) =20,550.

This is certainly an improvement on the revenue that we saw above.

So we started with supplier price vector vv, computed the conjugate receiver price vector v^\hat{v} and obtained a pricing plan (v;v^)(v;\hat{v}). But then we took the conjugate prices of our new receiver price vector to get a new supplier price vector and a pricing plan (v^˜;v^)(\tilde{\hat{v}}; \hat{v}) which gives better revenue. The natural thing here is to keep on going: take the conjugates of the new supplier price vector to get a new price plan (v^˜;v^˜^)(\tilde{\hat{v}} ;\hat{\tilde{\hat{v}}}) with even better revenue, and keep on taking conjugates, getting better and better price plans.

Exercise Try this! Calculate the conjugate of the bakery prices, v^˜=(2,23,20)\tilde{\hat{v}}=(2,23,20).

Spoiler alert! You should find that you get back the café prices you previously computed: v^˜^=(34,45,49)=v^\hat{\tilde{\hat{v}}}=(34,45,49)= \hat{v} and you don’t get improvement in revenue.

Conjugation is idempotent in the sense that doing it three times is the same as doing it once: v^˜^=v^\hat{\tilde{\hat{v}}}= \hat{v} . Thus starting from a supplier price vector vv the best one can do using this approach is the pricing plan (v^˜;v^)(\tilde{\hat{v}}; \hat{v}) which might or might not be optimal.

However, what this does tell us is that if we seeking an optimal pricing plan (v;u)(v; u) then it can be assumed that the supplier price vector is conjugate to the receiver price vector, and vice versa: u=v^u=\hat v and v=u˜v=\tilde u. This is because the pricing plan (v^^;v^)(\hat{\hat{v}}; \hat{v}) satisfies this conjugacy condition and has at least as much revenue as the plan (v;u)(v;u).

Say that a pricing plan (v;u)(v;u) is tight if u=v^u=\hat v and v=u˜v=\tilde u. So I’ve shown that to find an optimal pricing plan it suffices to consider tight pricing plans.

Looking at this from a step back, what we have is a pair of maps

and the tight pricing plans are those pairs of price vectors which are ‘fixed’ by these maps.

If you’re well-attuned to enriched category theory you might be unsurprised to learn that I will show that this pair of maps form an enriched adjunction, and this adjunction is of a standard type coming from the transport cost matrix kk, thought of as an enriched profunctor. The tight pricing plans then form the centre of this adjunction.

Modelling with enriched categories

As I’d said previously I want to model this with enriched categories, because it ties in with other things. The enriching category is going to be a sort of ‘ground ring’ and will be thing in which the prices live. I want to be able to add (and ‘subtract’) prices to (and from) each other and to compare prices to each other (as well as, relatedly, take suprema and infima); I will never want to multiply prices by each other.

From my perspective, at this point, there are four ‘obvious’ candidates for the place that prices will live.

  • The extended real numbers: {}{}={aa} \{-\infty\}\cup\mathbb{R}\cup\{ \infty\}= \{a\mid -\infty\le a \le \infty\}. I’ve stuck ±\pm \infty on to the real numbers so that we have infima and suprema of all sets.
  • The extended non-negative real numbers 0={a0a}\mathbb{R}_{\ge 0}\cup \infty= \{a\mid 0\le a \le \infty\}. It’s often a reasonable assumption that prices are non-negative.
  • The extended integers {,,1,0,1,2,,}\{-\infty, \dots, -1, 0, 1, 2, \dots, \infty\}. I might want to consider discrete prices.
  • The extended natural numbers {0,1,2,,}\{0,1,2,\dots ,\infty\}. I might want non-negative, discrete prices.

I am going to work with the extended non-negative reals here. I hope to show in the next post why sometimes allowing negative prices allows comparison between different approaches. There’s already been some responses in the comments about working over the integers

Let’s define ¯ +\bar{\mathbb{R}}_{+} to be the category whose object set is the extended non-negative real numbers, 0\mathbb{R}_{\ge 0}\cup \infty, with a unique morphism from aa to bb precisely when aba\ge b. The categorical product of two numbers is their maximum and the categorical coproduct is their minimum. Equip this category with a monoidal product which is simply addition. Clearly the unit object is 00. This is a closed monoidal category, with the internal hom [a,b][a,b] given by trunctated subtraction a+bcac˙b, a+b\ge c \qquad \iff \qquad a\ge c \,\dot{-}\, b, where c˙bmax(cb,0)c \,\dot{-}\, b \coloneqq \max(c-b, 0).

Categories enriched over ¯ +\bar{\mathbb{R}}_+ are then generalized metric spaces or Lawvere metric spaces, so these are sets with a distance between each pair of points, which is possibly infinite, satisfies the triangle inequality and points have zero self-distance. The distance is not necessarily symmetric. In our case distance is measured in units of cost, so should be thought of as cost.

I will model the suppliers as the discrete ¯ +\bar{\mathbb{R}}_+-category 𝒮\mathcal{S} with the set of suppliers {S 1,,S s}\{S_1,\dots,S_s\} as its set of objects. Saying that this is a discrete ¯ +\bar{\mathbb{R}}_+-category is saying that there is infinite cost to go from one supplier (or bakery) to another, or, to put it another way, we don’t allow transportation between suppliers. Similarly I will model the receivers by the discrete ¯ +\bar{\mathbb{R}}_+-category \mathcal{R} which has the receivers as its objects.

Then the price vectors are modelled as presheaves, or enriched functors to the ground category ¯ +\bar{\mathbb{R}}_+. Here an enriched functor means a cost-non-increasing function. As both 𝒮\mathcal{S} and \mathcal{R} are discrete, the cost-non-increasing condition is vacuous.

Thus the sets of vectors get modelled as enriched functor categories:

{supplier price vectors} ¯ + 𝒮; {receiver price vectors} ¯ + . \begin{aligned} \{\text{supplier price vectors}\}\quad&\leftrightarrow\quad \bar{\mathbb{R}}_+^\mathcal{S}\,;\qquad& \{\text{receiver price vectors}\}\quad&\leftrightarrow\quad \bar{\mathbb{R}}_+^{\mathcal{R}}\,. \end{aligned}

The transportation cost is modelled as a profunctor k:𝒮k\colon \mathcal{S}\rightsquigarrow \mathcal{R} from suppliers to receivers, this means it’s an ¯ +\bar{\mathbb{R}}_+-functor

k:𝒮 op¯ +. k\colon \mathcal{S}^\mathrm{op}\otimes \mathcal{R}\to \bar{\mathbb{R}}_+.

A functor 𝒮¯ +\mathcal{S}\to \bar{\mathbb{R}}_+ can be thought of as a profunctor 𝒮{\star}\rightsquigarrow \mathcal{S} where \star is the monoidal unit for ¯ +\bar{\mathbb{R}}_+-categories, ie. the one-object ¯ +\bar{\mathbb{R}}_+-category. Similarly a profunctor \star\rightsquigarrow \mathcal{R} can be thought of as a functor ¯ +\mathcal{R}\to \bar{\mathbb{R}}_+.

Thus profunctor composition with k:𝒮k\colon \mathcal{S}\rightsquigarrow \mathcal{R} gives us a functor k:¯ + 𝒮¯ + k\circ {-} \colon\bar{\mathbb{R}}_+^\mathcal{S}\to \bar{\mathbb{R}}_+^\mathcal{R}. In general terms this composition is given by a coend expression, which in our case can be written as a certain minimum as follows: (kv)(R j) S i𝒮k(S i,R j)v(S i) =min S i𝒮(k(S i,R j)+v(S i)). \begin{aligned} (k\circ v)(R_j)&\coloneqq \int^{S_i\in \mathcal{S}} k(S_i, R_j)\otimes v(S_i)\\ &=\min_{S_i\in \mathcal{S}}\bigl(k(S_i, R_j) + v(S_i)\bigr). \end{aligned} Apart from the notational change of kk and vv from indexed matrix and vector to profunctor and functor respectively, this is exactly the expression for the kk-conjugate v^\hat{v} of vv given above.

In the case of nice ground category, enriched profunctors form a closed bicategory, what this means is that the functor (k)(k\circ {-}) of post-composing with a fixed profunctor has a right adjoint (k)(k\triangleright {-}). This is analogous to (and can be thought of as being a generalization of) the tensor-hom adjunction.

Shen and Zhang (see for example Categories enriched over a quantaloid: Isbell adjunctions and Kan adjunctions) call this adjunction the Kan adjunction coming from a profunctor to distinguish it from what they call the Isbell adjuntion coming from a profunctor; the Isbell adjunction is the adjunction I’ve described here at the café before as it’s the one that appears in the profunctor nucleus, and I’m hoping to revisit it in the next post. I’m not a fan of naming things after people, but in the absence of more descriptive terms, I’ll stick to these terms here.

So from our profunctor k:𝒮k\colon \mathcal{S}\rightsquigarrow \mathcal{R} we get a right adjoint functor k:¯ + ¯ + 𝒮k\triangleright{-}\colon \bar{\mathbb{R}}_+^\mathcal{R}\to \bar{\mathbb{R}}_+^\mathcal{S}, given in general by an end, which in our case becomes a minimum as follows: (ku)(S i) R j[k(S i,R j),u(R j)] =max R j(u(R j)˙k(S i,R j)). \begin{aligned} (k\triangleright u)(S_i)&\coloneqq \int_{R_j\in \mathcal{R}}[ k(S_i, R_j), u(R_j)]\\ &=\max_{R_j\in \mathcal{R}}\bigl(u(R_j)\,{\dot{-}}\, k(S_i, R_j) \bigr). \end{aligned} And again, up to changes in notation, this is exactly the expression for the conjugate, u˜\tilde{u}, of uu as given above.

This means that the pair of kk-conjugation maps

should be thought of as the Kan adjunction of the cost profunctor kk,

with the tight pricing plans forming the centre of this adjunction.

What do we gain from this?

A standard question to be asked at this juncture is “What’s the point?” Well, there’s several answers to the question. Firstly, it confirms that this is a natural mathematical construction in the sense that it is an example of something that crops up in many places. Secondly, it means that we have the tools and intuition of adjunctions to apply here; for instance, the fact that we have idempotency is a standard fact about adjunctions when you’re enriched over a poset. Thirdly, it attunes us to the possibility that category theory might pervade deeper in related areas. Hopefully I’ll be able to show you a bit more of that.

Next time I want to show you how this relates to the profunctor nucleus construction that I’ve described before, in particular how a Kan adjunction can be related to an Isbell adjunction when you are enriching over a compact closed category such as the extended real numbers, but not the extended non-negative real numbers which we’ve been using here.

I’ll leave a little exercise for the algebraically minded amongst you, which involves the Kan adjunction in the context of algebra bimodules.

Digression/Exercise. Consider categories enriched in VectVect, the category of finite dimensional vector spaces over the complex numbers \mathbb{C}. Let AA and BB be finite-dimensional algebras over \mathbb{C} which we consider as one-object VectVect-categories. A profunctor M:ABM\colon A\rightsquigarrow B is then precisely a BB-AA-bimodule. What is the Kan adjunction in this case?

If f:BAf\colon B\to A is an algebra map then we get an BB-AA-bimodule fA{}_f A which is the underlying vector space of AA equipped with the action baa=f(b)aab\cdot a\cdot a'= f(b) a a'. What is the Kan adjunction for fA:AB{}_f A\colon A\rightsquigarrow B?

Posted at August 7, 2021 12:16 PM UTC

TrackBack URL for this Entry:

2 Comments & 0 Trackbacks

Re: Optimal Transport and Enriched Categories III: Duality Within Pricing

I remember at the CT in Halifax (whichever year that was), Spencer Breiner was advertising some questions along these lines – basically, questions about how to think about certain optimization problems in terms of enriched category theory. I think the toy problem he brought up had to do with scheduling – I remember at the time being convinced that this problem seemed like pure enriched category theory, but try as I might I was unable to substantiate that feeling. So this first piece of the puzzle – relating Kan extensions to a known duality in these sorts of optimization problems – seems like a great breakthrough! I’ll be watching this series with interest!

Posted by: Tim Campion on August 9, 2021 3:21 PM | Permalink | Reply to this

Re: Optimal Transport and Enriched Categories III: Duality Within Pricing

It turns out that the Adjoint School videos from ACT2021 have been put up on YouTube. So you can watch Elise Catania’s five minute talk on the above material.

Posted by: Simon Willerton on August 11, 2021 11:34 AM | Permalink | Reply to this

Post a New Comment