Al fine di migliorare la tua esperienza di navigazione, questo sito utilizza i cookie di profilazione di terze parti. Chiudendo questo banner o accedendo ad un qualunque elemento sottostante acconsenti all’uso dei cookie.

Revenue Maximizing Envy-Free Pricing in Matching Markets with Budgets

16 febbraio 2017 ore 12:01 - 13:00

Aula 207, Sede di Viale Romania, 32

Speaker: Riccardo Colini-Baldeschi, LUISS

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. This pricing problem is hard to approximate better than Ω(min{n,m}1/2−ε) for any ε > 0, unless P = NP. 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.