## 1 Introduction  
Suppose that a seller has \(n\) different items, each one with \(c_{j}\) copies, and there are \(m\) consumers, each interested in buying a single copy of an item. The seller knows the _valuation_\(v_{ij}\), the largest amount that consumer \(i\) is willing to pay for a copy of item \(j\). If consumer \(i\) buys a copy of item \(j\), their _utility_ is \(v_{ij}-p_{j}\), which is the difference between the valuation and the purchase price. The seller needs to decide which item \(j\) (a copy of it) will be sold (or not) to consumer \(i\), i.e., to set an _allocation_ of items, and what the price of each item will be so that consumers who buy a copy of the same item pay the same price for it, and the copy of item \(j\) sold to consumer \(i\) is the one that maximizes their (non-negative) utility, thus satisfying the _envy-freeness_ (the concept of envy-freeness used in this work is different from that introduced by [PERSON] [1], in which all buyers prefer their allocations to the allocations obtained by other agents, which some recent authors, such as [PERSON] et al. [2], [PERSON] et al. [3], and [PERSON] et al. [4] call _pair envy-freeness_ property. The goal is to maximize the revenue from the sale of copies of items, i.e., the sum of prices of all copies sold. The problem above is the unit-demand envy-free pricing problem (UDEFP), and was presented by [PERSON] et al. [5], after which several variants and special cases were studied. These authors have shown that the general problem is APX-hard, even if each item exists in unlimited supply and each consumer has equal valuations (of either 1 or 2) for all of the items in which they have any interest. In addition, they provided a \(O(\log n)\)-approximation algorithm based on a maximum-weight-matching strategy. [PERSON] et al. [6] considered the following case of the UDEFP: The seller has a single item with unlimited supply, and \(n\) consumers are in different locations. Each consumer \(i\) assigns a valuation \(v_{i}\) to the item if the purchase is made in their own location and a substitution cost \(\delta_{ij}\) that is subtracted from \(v_{i}\) if the purchase is made in location \(j\). In addition, the cost set \(\{\delta_{ij}\}_{1\leq i,j\leq n}\) has a metric space structure (that is, the function \(\delta:\{1,\ldots,n\}^{2}\longrightarrow\mathbb{R}\) satisfies, for any \(1\leq i,j,k\leq n\), \(1\)) \(\delta_{ij}=0\Longleftrightarrow i=j\) (identity of indiscernibles), \(\delta_{ij}=\delta_{ji}\) (symmetry), and \(\delta_{ij}\leq\delta_{jk}+\delta_{kj}\) (triangle inequality)), which they called _metric substitutability_. Thus, if consumer \(i\) bvs the item at location \(j\), their utility is \(v_{i}-(p_{j}+\delta_{ij})\). In this scenario, they showed that the problem can be solved optimally in polynomial time by proving that every consumer receives an item in their own location; then, a perfect graph with \(O(n^{2})\) vertices is constructed, and in this graph is found a maximum-weighted independent set whose weight corresponds to the optimal revenue. Therefore, by using the ellipsoid method [7], this strategy takes \(O(n^{4})\) time to find a maximum-weighted independent set and, thus, an optimal envy-free pricing. Another special case of the UDEFP that can be solved optimally in polynomial time was studied by [PERSON] et al. [8]. They considered that the items have a single copy and the number of consumers is equal to the number of items, i.e., \(m=n\), which they called _envy-free perfect matching_ (EFPM), so that each consumer buys an item. A maximum-weight perfect matching in the bipartite graph of consumers and items was used to find the allocation, and then a network consisting of \(n+1\) nodes and \(n^{2}\) arcs was constructed, whose shortest paths from nodes \(1\leq j\leq n\) to an auxiliary node \(0\) coincided with the envy-free prices of the corresponding items.