Graph Pricing With Limited Supply

• Author / Creator

  Maryam Mahboub

• In this thesis, we study approximation algorithms for graph pricing where we have a set of items V and a set of customers X where each customer i in X has a budget b(i) and is interested in a bundle of items S(i) subset V with |S(i)| <= 2. However, there is a limited supply of each item: we only have mu(v) copies of item v to sell for each v in V. We should assign prices p(v) to each v in V and choose a subset Y of customers so that each i in Y can afford their bundle (p(S(i)) <= b(i)) and at most mu(v) chosen customers have item v in their bundle for each item v in V. Each customer i in Y pays p(S(i)) for the bundle they purchased: our goal is to do this in a way that maximizes revenue.

  Such pricing problems have been studied from the perspective of envy-freeness where we also must ensure that p(S(i)) >= b(i) for each i not in Y. However, the version where we simply allocate items to customers after setting prices and do not worry about the envy-free condition has received less attention.

  With an unlimited supply of each v in V, Balcan and Blum (2006) give a 4-approximation for graph pricing which was later shown to be tight by Lee (2015) unless the Unique Games conjecture fails to hold.

  Our main result is an 8-approximation for the capacitated case via local search. If all capacities are bounded by a constant C, we further show a multi-swap local search algorithm yields an (4(2C-1)/C + epsilon)-approximation. We also give a (4+epsilon)-approximation in simple graphs through LP rounding when all capacities are very large as a function of epsilon.

  The reduction by Balcan and Blum to the case of bipartite graphs where all items on one side must be assigned a price of 0 holds in this setting as well. However, unlike the unlimited supply setting, the resulting problem remains APX-hard even if all items have at most 4 copies to sell. We also show our multi-swap analysis is tight using an interesting construction based on regular, high-girth graphs.

• Subjects / Keywords

  • Pricing

• Graduation date

  Spring 2020

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-54hh-fr06

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.