Approximation Algorithms and Online Mechanisms for Item Pricing

by Maria-Florina Balcan and Avrim Blum

Theory of Computing, Volume 3(9), pp. 179-195, 2007

Bibliography with links to cited articles

[1]   B. Awerbuch and R. Kleinberg: Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proc. 36th STOC, pp. 45–53. ACM Press, 2004. [STOC:1007352.1007367].

[2]   M.-F. Balcan, A. Blum, H. Chan, and M.T. Hajiaghayi: A theory of loss-leaders: Making money by pricing below cost. In Proc. 3rd Intern. Workshop on Internet and Network Economics, Lecture Notes in Computer Science. Springer, 2007.

[3]   M.-F. Balcan, A. Blum, J. Hartline, and Y. Mansour: Mechanism design via machine learning. In Proc. 46th FOCS, pp. 605–614. IEEE Computer Soc., 2005. [FOCS:10.1109/SFCS.2005.50].

[4]   M.-F. Balcan, A. Blum, and Y. Mansour: Single price mechanisms for revenue maximization in unlimited supply combinatorial auctions. Technical Report CMU-CS-07-111, Carnegie Mellon University, 2007.

[5]   A. Blum and J. Hartline: Near-optimal online auctions. In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’05), pp. 1156–1163. SIAM, 2005. [SODA:1070432.1070597].

[6]   A. Blum, V. Kumar, A. Rudra, and F. Wu: Online learning in online auctions. In Proc. 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’03), pp. 202–204. SIAM, 2003. [SODA:644108.644143].

[7]   P. Briest and P. Krysta: Single-minded unlimited supply pricing on sparse instances. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 1093–1102. SIAM, 2006. [SODA:1109557.1109678].

[8]   P. Briest and P. Krysta: Buying cheap is expensive: Hardness of non-parametric multi-product pricing. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’07), pp. 716–725. SIAM, 2007. [SODA:1283383.1283460].

[9]   V. Dani and T. P. Hayes: Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 937–943. SIAM, 2006. [SODA:1109557.1109660].

[10]   E. D. Demaine, U. Feige, M. Hajiaghayi, and M. R. Salavatipour: Combination can be hard: Approximability of the unique coverage problem. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 162–171. SIAM, 2006. [SODA:1109557.1109577].

[11]   K. Elbassioni, R. Sitters, and Y. Zhang: A quasi-PTAS for profit-maximizing pricing on line graphs. In Proc. 15th Ann. European Symp. on Algorithms (ESA’07), Lecture Notes in Computer Science. Springer, 2007.

[12]   G. Even, O. Goldreich, M. Luby, N. Nisan, and B. Velickovic: Efficient approximation of product distributions. Random Structures and Algorithms, 13(1):1–16, 1998. [Wiley:10.1002/(SICI)1098-2418(199808)13:1¡1::AID-RSA1¿3.0.CO;2-W].

[13]   A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright: Competitive auctions. Games and Economic Behavior, 55(2):242–269, 2006. [Elsevier:10.1016/j.geb.2006.02.003].

[14]   A. Goldberg, J. Hartline, and A. Wright: Competitive auctions and digital goods. In Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’01), pp. 735–744. SIAM, 2001. [SODA:365411.365768].

[15]   V. Guruswami, J. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F. McSherry: On profit-maximizing envy-free pricing. In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’05), pp. 1164–1173. SIAM, 2005. [SODA:1070432.1070598].

[16]   J. Hartline and V. Koltun: Near-optimal pricing in near-linear time. In 9th Workshop on Algorithms and Data Structures (WADS’05), number 3608 in Lecture Notes in Computer Science, pp. 422–431. Springer, 2005. [WADS:al2ke8gd23a44atp].

[17]   S. Kakade, A. Kalai, and K. Ligett: Playing games with approximation algorithms. In Proc. 39th STOC, pp. 546–555. ACM Press, 2007. [STOC:1250790.1250870].

[18]   A. Kalai and S. Vempala: Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291–307, 2005. An earlier version appears in COLT 2003. [JCSS:10.1016/j.jcss.2004.10.016, Springer:fbx1n68j5ubyv706].

[19]   R. Krauthgamer, A. Mehta, and A. Rudra: Pricing commodities, or how to sell when buyers have restricted valuations. In 5th Workshop on Approximation and Online Algorithms. Springer, 2007.

[20]   M. Luby and A. Wigderson: Pairwise independence and derandomization. Technical Report CSD-95-880, U.C. Berkeley, 1995.

[21]   H. B. McMahan and A. Blum: Online geometric optimization in the bandit setting against an adaptive adversary. In Proc. 17th Conf. on Computational Learning Theory (COLT’04), number 3120 in Lecture Notes in Computer Science, pp. 109–123. Springer, 2004. [Springer:38p3f4h61cgy7gg7].

[22]   R. Motwani and P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.