Login | Register

On the tradeoff between privacy and efficiency: A bidding mechanism for scheduling non-commercial services


On the tradeoff between privacy and efficiency: A bidding mechanism for scheduling non-commercial services

Wang, Chun, Dargahi, Farnaz and Bhuiyan, Mohammad Fozlul Haque (2012) On the tradeoff between privacy and efficiency: A bidding mechanism for scheduling non-commercial services. Computers in Industry, 63 (6). pp. 610-618. ISSN 01663615

Text (application/pdf)
wang2012c.pdf - Accepted Version

Official URL: http://dx.doi.org/10.1016/j.compind.2012.01.012


Services providers, such as public healthcare systems and government agencies, are under tremendous pressure to reduce costs and improve service quality. Scheduling is an important managerial component which has considerable impact on both the costs and quality of services. Service providers need customers’ availability information to improve resource utilization. On the other hand, customers may be of “two minds” about communicating their private information. While communicating certain amount of availability might be necessary in order to obtain preferred schedules, too much communication place a potential cost due to privacy loss. In this paper, we present a bidding-based mechanism which aims at generating high quality schedules and, at the same time, protecting customers’ privacy. We show that, under the proposed bidding procedure, myopic bidding is the dominant strategy for customers. We also evaluate the privacy and efficiency performance of the proposed mechanism through a computational study.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering
Item Type:Article
Authors:Wang, Chun and Dargahi, Farnaz and Bhuiyan, Mohammad Fozlul Haque
Journal or Publication:Computers in Industry
Digital Object Identifier (DOI):10.1016/j.compind.2012.01.012
Keywords:Non-commercial services, distributed scheduling, privacy, efficiency, iterative bidding, auction
ID Code:976812
Deposited On:28 Jan 2013 16:59
Last Modified:18 Jan 2018 17:43


[1] R. E. Sabath and J. Fontanella, "The unfulfilled promise of supply chain collaboration," Supply Chain Management Review, vol. 6, pp. 24-29, 2002.
[2] R. R. Chen, R. O. Roundy, R. Q. Zhang, and G. Janakiraman, "Efficient auction mechanisms for supply chain procurement," Management Science, pp. 467-482, 2005.
[3] M. Babaioff and W. E. Walsh, "Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation," Decision Support Systems, vol. 39, pp. 123-149, 2005.
[4] M. Fan, J. Stallaert, and A. B. Whinston, "Decentralized mechanism design for supply chain organizations using an auction market," Information Systems Research, vol. 14, pp. 1-22, 2003.
[5] M. Nagarajan and G. Sosic, "Game-theoretic analysis of cooperation among supply chain agents: Review and extensions," European Journal of Operational Research, vol. 187, pp. 719-745, 2008.
[6] A. C. Yao, "Protocols for secure computations," in Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pp. 160-164.
[7] M. J. Atallah, H. G. Elmongui, V. Deshpande, and L. B. Schwarz, "Secure supply-chain protocols," in Proceedings of the IEEE International Conference on E-Commerce, 2003, pp. 293-302.
[8] M. Atallah, M. Bykova, J. Li, K. Frikken, and M. Topkara, "Private collaborative forecasting and benchmarking," in Proceedings of the 2004 ACM workshop on Privacy in the electronic society 2004, pp. 103-114.
[9] D. Y. Zhang, Y. Zeng, L. Wang, H. Li, and Y. Geng, "Modeling and evaluating information leakage caused by inferences in supply chains," Computers in Industry, vol. 62 pp. 351–363, 2011.
[10] E. Simchi-Levi and P. Kaminsky, Designing and managing the supply chain: concepts, strategies, and case studies: Irwin/McGraw-Hill, 2003.
[11] M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason, "Auction Protocols for Decentralized Scheduling," Games and Economic Behavior, vol. 35, pp. 271-303, 2001.
[12] N. Nisan, "Bidding languages for combinatorial auctions" in Combinatorial Auctions, Cramton, Shoham, and Steinberg, Eds.: MIT Press, 2006.
[13] J. M. Keil, "On the complexity of scheduling tasks with discrete starting times" Operations Research Letters, vol. 12, pp. 293-295, 1992.
[14] E. H. Clarke, “Multipart pricing of public goods,” Public Choice, 11(1):17-33, 1971.
[15] T. Groves, “Incentives in Teams,” Econometrica, 41(4):617-631, 1973.
[16] W. S. Vickrey, Counterspeculation, “auctions, and competitive sealed tenders.” Journal of Finance, 16(1):8-37, 1961.
[17] D. Parkes, "Iterative combinatorial auctions," in Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg, Eds.: Cambridge, MA: MIT Press, 2006, pp. 41–77.
[18] S. de Vries and R. V. Vohra, "Combinatorial auctions: a survey," INFORMS Journal on Computing, vol. 15, pp. 284-309, 2003.
[19] P. Van Hentenryck and L. Michel, "OPL script: Composing and controlling models," in Lecture Note in Artificial Intelligence (LNAI1865): Springer Verlag, 2000, pp. 75-90.
[20] K. Sengupta, D. R. Heiser, and L. S. Cook, "Manufacturing and service supply chain performance: a comparative analysis," Journal of Supply Chain Management, vol. 42, pp. 4-15, 2006.
[21] B. Heydenreich, R. Müller, and M. Uetz, "Games and Mechanism Design in Machine Scheduling—An Introduction," Production and Operations Management, vol. 16, pp. 437-454, 2007.
[22] S. J. Rassenti, V. L. Smith, and R. L. Bulfin, "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," The Bell Journal of Economics, vol. 13, pp. 402-417, 1982.
[23] R. Buyya, D. Abramson, J. Giddy, and H. Stockinger, "Economic models for resource management and scheduling in Grid computing," Concurrency and Computation: Practice and Experience, vol. 14, pp. 1507-1542, 2002.
[24] D. C. Parkes and L. H. Ungar, "An auction-based method for decentralized train scheduling," Proceedings of the fifth international conference on Autonomous agents, 2001, pp. 43-50.
[25] R. P. McAfee and J. McMillan, "Analyzing the airwaves auction," The Journal of Economic Perspectives, vol. 10, pp. 159-175, 1996.
[26] P. Milgrom, "Putting auction theory to work: the simultaneous ascending auction," Journal of Political Economy, vol. 108, pp. 245-272, 2000.
[27] T. Sandholm, S. Suri, A. Gilpin, and D. Levine, "CABOB: a fast optimal algorithm for winner determination in combinatorial auctions," Management Science, vol. 51, pp. 374-390, 2005.
[28] E. Kutanoglu and S. D. Wu, "On combinatorial auction and Lagrangean relaxation for distributed resource scheduling," IIE Transactions, vol. 31, pp. 813-826, 1999.
[29] J. K. Mackie-Mason, A. Osepayshvili, D. M. Reeves, and M. P. Wellman, "Price prediction strategies for market-based scheduling," in Proc. 14th International Conference on Automated Planning and Scheduling, Whistler, BC, 2004.
[30] D. M. Reeves, M. P. Wellman, J. K. MacKie-Mason, and A. Osepayshvili, "Exploring bidding strategies for market-based scheduling," Decision Support Systems, vol. 39, pp. 67-85, 2005.
[31] O. Catrina and F. Kerschbaum, "Fostering the Uptake of Secure Multiparty Computation in E-Commerce," in Availability, Reliability and Security, 2008. ARES 08. Third International Conference on, 2008, pp. 693-700.
[32] O. Goldreich, “Secure multi-party computation” (working draft). Available from, http://www.wisdom.weizmann.ac.il/~oded/pp.html, 2002.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top