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 Ω(minn, m1/2−ε) for any ε > 0, unless P = NP [7]. 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.

Revenue maximizing envy-free pricing in matching markets with budgets / COLINI BALDESCHI, Riccardo; Leonardi, Stefano; Zhang, Qiang. - 10123:(2016), pp. 207-220. [10.1007/978-3-662-54110-4_15]

Revenue maximizing envy-free pricing in matching markets with budgets

COLINI BALDESCHI, RICCARDO;
2016

Abstract

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 Ω(minn, m1/2−ε) for any ε > 0, unless P = NP [7]. 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.
9783662541098
Theoretical Computer Science; Computer Science (all)
File in questo prodotto:
File Dimensione Formato  
matching_markets.pdf

Solo gestori archivio

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 346.15 kB
Formato Adobe PDF
346.15 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/172102
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact