Market clearing price and equilibria of the progressive second price mechanism

Maillé, Patrick

RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 4, pp. 465-478.

The Progressive Second Price mechanism (PSP), recently introduced by Lazar and Semret to share an infinitely-divisible resource among users through pricing, has been shown to verify very interesting properties. Indeed, the incentive compatibility property of that scheme, and the convergence to an efficient resource allocation where established, using the framework of Game Theory. Therefore, that auction-based allocation and pricing scheme seems particularly well-suited to solve congestion problems in telecommunication networks, where the resource to share is the available bandwidth on a link. This paper aims at supplementing the existing results by highlighting some properties of the different equilibria that can be reached. We precisely characterize the possible outcomes of the PSP auction game in terms of players bid price: when the bid fee (cost of a bid update) tends to zero then the bid price of all users at equilibrium gets close to the so-called market clearing price of the resource. Therefore, observing an equilibrium of the PSP auction game gives some accurate information about the market clearing price of the resource.

Classification : 91A, 91B
Mots clés : network pricing, game theory, auctions

[1] T. Alpcan, T. Başar, R. Srikant and E. Altman, CDMA uplink power control as a noncooperative game. Wireless Networks 8 (2002) 659-670. | Zbl

[2] S. Baskar, S. Verma, G.S. Tomar and R. Chandra, Auction based bandwidth allocation on the Internet, in Proc. of 3rd IEEE and IFIP International Conference on wireless and Optical Communications Networks (WOCN 2006), Bangalore, India (2006).

[3] F. Beltrán, A note on some properties of an efficient network resource allocation mechanism. Revista de Ingenieria, Facultad de Ingenieria, Universidad de Los Andes (2004).

[4] E.H. Clarke, Multipart pricing of public goods. Public Choice 11 (1971) 17-33.

[5] C. Courcoubetis and R. Weber, Pricing Communication Networks: Economics, Technology and Modelling. Wiley & Sons, Inc. (2003).

[6] L.A. Dasilva, Pricing for QoS-enabled networks: A survey. IEEE Communications Surveys 3 (2000) 2-8.

[7] T. Groves, Incentives in teams. Econometrica 41 (1973) 617-631. | Zbl

[8] F.P. Kelly, A.K. Maulloo and D.K.H. Tan, Rate control in communication networks: Shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49 (1998) 237-252. | Zbl

[9] A.A. Lazar and N. Semret, Design and analysis of the progressive second price auction for network bandwidth sharing. Telecommunication Systems - Special issue on Network Economics (1999).

[10] J.K. Mackie-Mason and H.R. Varian, Pricing the internet, in Public Access to the Internet, edited by B. Kahin and J. Keller, MIT Press (1995) 269-314.

[11] P. Maillé and B. Tuffin, Pricing the internet with multibid auctions. IEEE/ACM Transactions on Networking 14 (2006) 992-1004.

[12] P. Marbach, Priority service and max-min fairness, in Proc. of IEEE INFOCOM (2002).

[13] R.P. Mcafee and J. Mcmillan, Auctions and bidding. J. Econ. Lit. 25 (1987) 699-738.

[14] R.B. Myerson, Optimal auction design. Mat. Oper. Res. 6 (1981) 58-73. | MR | Zbl

[15] A. Pompermaier, A pricing mechanism for intertemporal bandwidth sharing with random utilities and resources. Technical Report LSE-CDAM-2002-06, London School of Economics (2002).

[16] C.U. Saraydar, N.B. Mandayam and D.J. Goodman, Efficient power control via pricing in wireless data networks. IEEE Trans. Comm. 50 (2002) 291-303.

[17] N. Semret, Market Mechanisms for Network Resource Sharing. Ph.D. Thesis, Columbia University (1999).

[18] B. Tuffin, Charging the internet without bandwidth reservation: an overview and bibliography of mathematical approaches. J. Inform. Sci. Engrg. 19 (2003) 765-786.

[19] W. Vickrey, Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16 (1961) 8-37.