2023/08/24 by Marcos Salvatierra, Juan G. Colonna, Salvatierra, Marcos +5
Business, Management and Accounting · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Consumer Market Behavior and Pricing #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2308.12858
openalex publication_date 2023/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a method for finding envy-free prices in a combinatorial auction where the consumers' number n coincides with that of distinct items for sale, each consumer can buy one single item and each item has only one unit available. This is a particular case of the \it unit-demand envy-free pricing problem, and was recently revisited by Arbib et al. (2019). These authors proved that using a Fibonacci heap for solving the maximum weight perfect matching and the Bellman-Ford algorithm for getting the envy-free prices, the overall time complexity for solving the problem is O(n3). We propose a method based on dynamic programming design strategy that seeks the optimal envy-free prices by increasing the consumers' utilities, which has the same cubic complexity time as the aforementioned approach, but whose theoretical and empirical results indicate that our method performs faster than the shortest paths strategy, obtaining an average time reduction in determining optimal envy-free prices of approximately 48%.