Scholarlink

<p>We present a method for finding envy-free prices in a combinatorial auction where the consumers’ number <i>n</i> 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 <i>unit-demand envy-free pricing problem</i>, and was recently revisited by Arbib et al. (Discr Appl Math&#xa0;261:22–27,&#xa0;2019,&#xa0;<a href="https://doi.org/10.1016/j.dam.2018.03.034">https://doi.org/10.1016/j.dam.2018.03.034</a>). 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n^3)\)</EquationSource> </InlineEquation>. 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%.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An efficient alternative strategy for finding prices in envy-free perfect matchings

  • 期刊论文

  • 发表日期：

    2025年11月7日

查看全文
  • Marcos Salvatierra,
  • Juan G. Colonna,
  • Mario Salvatierra,
  • Alcides de C. Amorim Neto

摘要

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 unit-demand envy-free pricing problem, and was recently revisited by Arbib et al. (Discr Appl Math 261:22–27, 2019, https://doi.org/10.1016/j.dam.2018.03.034). 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(n^3)\) . 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%.