[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Approximation algorithms for the selling with preference

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

We consider the market mechanism to sell two types of products, A and B, to a set of buyers \(I=\{1, 2, \ldots , n\}\). The amounts of products are \(m_A\) and \(m_B\) respectively. Each buyer i has his information including the budget, the preference and the utility function. On collecting the information from all buyers, the market maker determines the price of each product and allocates some amount of product to each buyer. The objective of the market maker is designing a mechanism to maximize the total utility of the buyers in satisfying the semi market equilibrium. In this paper, we show that this problem is NP-hard and give an iterative algorithm with the approximation ratio 1.5. Moreover, we introduce a PTAS for the problem, which is an (\(1+\epsilon \))-approximation algorithm with the running time \(O(2^{1/\epsilon }+n\log n)\) for any positive \(\epsilon \).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adsul B, Babu Ch S, Garg J, Mehta R, Sohoni M (2010) Nash equilibria in fisher market. In: Proceedings of SAGT 2010, pp 30–41

  • Arrow KJ, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica 22(3):265–290

    Article  MathSciNet  Google Scholar 

  • Brânzei S, Chen Y, Deng X, Filos-Ratsikas A, Frederiksen SKS, Zhang J (2014) The fisher market game: equilibrium and welfare. Proceedings of AAAI 2014:587–593

    Google Scholar 

  • Chen N, Deng X, Tang B, Zhang H (2016) Incentives for strategic behavior in fisher market games. In: Proceedings of AAAI 2016. pp 453–459

  • Chen N, Deng X, Zhang J (2011) How profitable are strategic behaviors in a market. In: Proceedings of ESA 2011. pp 106–118

  • Chen N, Deng X, Zhang H, Zhang J (2012) Incentive ratios of fisher markets. In: Proceedings of ICALP 2012. pp 464–475

  • Cheng Y, Deng X, Scheder D (2018) Recent studies of agent incentives in internet resource allocation and pricing. 4OR 16:231–260

    Article  MathSciNet  Google Scholar 

  • Cobb C, Douglas P (1928) A theory of production. Am Econ Rev 18(Supplement):139–165

    Google Scholar 

Download references

Acknowledgements

This research is supported by Major Scientific and Technological Special Project of Guizhou Province (20183001), China’s NSFC Grants (Nos. 71361003, 71461003), Shenzhen Research Grant (Nos. KQJSCX20180330170311901, JCYJ 20180305180840138 and GGFW2017073114031767), Hong Kong GRF-17208019, Natural Science Foundations of Guizhou Province (No. [2018] 3002) and the Key Project of Hebei Education Department of China (ZD2019021).

Author information

Authors and Affiliations

  1. Key Laboratory of Machine Learning and Computational Intelligence of Hebei Province, Hebei University, Baoding, People’s Republic of China

    Pan Li & Qiang Hua

  2. State Key Laboratory of Public Big Data, School of Mathematics and Statistics, Guizhou University, Guiyang, People’s Republic of China

    Zhijun Hu

  3. Department of Computer Science, The University of Hong Kong, Hong Kong, People’s Republic of China

    Hing-Fung Ting

  4. Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, People’s Republic of China

    Yong Zhang

Authors
  1. Pan Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qiang Hua
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhijun Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hing-Fung Ting
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Yong Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhijun Hu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, P., Hua, Q., Hu, Z. et al. Approximation algorithms for the selling with preference. J Comb Optim 40, 366–378 (2020). https://doi.org/10.1007/s10878-020-00602-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-020-00602-3

Keywords

Search

Navigation