Revenue Maximizing Envy-Free Pricing in Matching Markets with Budgets

Colini-Baldeschi, Riccardo; Leonardi, Stefano; Zhang, Qiang
We study envy-free pricing mechanisms in matching markets with {\$}m{\$} items and {\$}n{\$} budget constrained buyers. Each buyer is interested in a subset of the items on sale, and she appraises at some single-value every item in her preference-set. Moreover, each buyer has a budget that constraints the maximum affordable payment, while she aims to obtain as many items as possible of her preference-set. Our goal is to compute an envy-free pricing allocation that maximizes the revenue, i.e., the total payment charged to the buyers. This pricing problem is hard to approximate better than {\$}\backslashOmega({\{}\backslashrm min{\}} \backslash{\{}n,m\backslash{\}}{\^{}}{\{}1/2-\backslashepsilon{\}}){\$} for any {\$}\backslashepsilon{\textgreater}0{\$}, unless {\$}P=NP{\$}. The hardness result is due to the presence of the matching constraints given that the simpler multi-unit case can be approximated up to a constant factor of {\$}2{\$}. The goal of this paper is to circumvent the hardness result by restricting ourselves to specific settings of valuations and budgets. Two particularly significant scenarios are: each buyer has a budget that is greater than her single-value valuation, and each buyer has a budget that is lower than her single-value valuation. Surprisingly, in both scenarios we are able to achieve a {\$}1/4{\$}-approximation to the optimal envy-free revenue. The algorithms utilize a novel version of the Ausebel ascending price auction. These results may suggest that, although it is difficult to approximate the optimal revenue in general, ascending price auctions could achieve relatively good revenue in most of the practical settings.
Research areas:
Type of Publication:
Hits: 3621

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information