Aumento de desempenho na determinação de precificações ótimas livres de inveja

Abstract

Maximizing sellers’ revenue while preserving consumers’ satisfaction presents some computational challenges. The envy-free pricing problem is itself a modeling alternative that is APX-hard in general, but some cases and/or variations have already been proven to be solvable exactly in polynomial time, and for others, there exists approximation algorithms with constant ratio in polynomial time. This work ad- dresses the cases of envy-free perfect matching, in which the number of consumers coincides with the number of items on sale and each consumer can buy only a single item, and unit demand with substitutability metric, in which several units of the same item are sold in different locations and consumers in these locations can buy only one unit of the item, and the costs of moving from one location to another to make the purchase form a metric space. For the first case, an exact algorithm was designed based on a dynamic programming strategy taking into account the consumers’ utilities to calculate the optimal pricing. For the second case, an algorithmic strategy was proposed that performs the search for the op- timal solutions through a reduction to the first case and the simplification of the calculations of the shortest paths for the determination of prices. Comparing the proposed methods with those in the literature, in the first case there was a performance increase of, on average, 49 % in the search for optimal prices, and in the second case there was a reduction in computational time complexity in the search for optimal solutions from O(n^4) to O(n^3).