The envy-free pricing problem, unit-demand markets and connections with the network pricing problem

详细信息    查看全文

• 作者：Cristina G. Fernandes^a ; ^{cris@ime.usp.br" class="auth_mail" title="E-mail the corresponding author} ; Carlos E. Ferreira^a ; ^{cef@ime.usp.br" class="auth_mail" title="E-mail the corresponding author} ; Á ; lvaro J.P. Franco^b ; ^{alvaro.junio@ufsc.br" class="auth_mail" title="E-mail the corresponding author} ; Rafael C.S. Schouery^c ; ^{schouery@ic.unicamp.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Pricing problems ; Envy-free allocations ; Unit-demand auctions
• 刊名：Discrete Optimization
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：22
• 期：part_PA
• 页码：141-161
• 全文大小：870 K

文摘

A common problem faced in economics is to decide the pricing of products of a company, since poorly chosen prices might lead to low profit. One important model for this is the unit-demand envy-free pricing problem, in which one considers that every consumer buys an item that maximizes his own profit, and the goal is to find a pricing of the items that maximizes the expected profit of the seller. This is a practical and interesting problem which is, unfortunately, not in hmlsrc">he MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528615000493&_mathId=si98.gif&_user=111111111&_pii=S1572528615000493&_rdoc=1&_issn=15725286&md5=af604457e7cba7c26f0daf27b338eba2">height="9" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S1572528615000493-si98.gif">hContainer hidden">hCode">h altimg="si98.gif" overflow="scroll">hvariant="normal">APXh> unless hmlsrc">he MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528615000493&_mathId=si99.gif&_user=111111111&_pii=S1572528615000493&_rdoc=1&_issn=15725286&md5=24fa3172233f5d4bbb85c85f1712b352">height="9" width="46" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S1572528615000493-si99.gif">hContainer hidden">hCode">h altimg="si99.gif" overflow="scroll">hvariant="normal">P=hvariant="normal">NPh>. We present two new MIP formulations for this problem and experimentally compare them to previous ones from the literature. We describe three models to generate different random instances for general unit-demand auctions, that we designed for the computational experiments. Each model has a nice economic interpretation. Our results show that one of our MIP formulations can sometimes lead to better results than the previous ones from the literature. We also consider a variant of the network pricing problem in which one has to price toll arcs in a highway, and prove that it is as hard to approximate as the envy-free pricing problem.