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 [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. © Springer-Verlag GmbH Germany 2016.
Revenue maximizing envy-free pricing in matching markets with budgets / COLINI BALDESCHI, Riccardo; Leonardi, Stefano; Zhang, Qiang. - STAMPA. - 10123:(2016), pp. 207-220. (Intervento presentato al convegno 12th International Conference on Web and Internet Economics, WINE 2016 tenutosi a Montreal; Canada nel 11-14 December 2016) [10.1007/978-3-662-54110-4_15].
Revenue maximizing envy-free pricing in matching markets with budgets
COLINI BALDESCHI, RICCARDO
;LEONARDI, Stefano;
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 Ω(min{n, m}1/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. © Springer-Verlag GmbH Germany 2016.File | Dimensione | Formato | |
---|---|---|---|
Colini-Baldeschi_Revenue-Maximizing-Envy_2016.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
251.27 kB
Formato
Adobe PDF
|
251.27 kB | Adobe PDF | Contatta l'autore |
Colini-Baldeschi_Frontespizio-indice_Revenue-Maximizing-Envy_2016.pdf
solo gestori archivio
Tipologia:
Altro materiale allegato
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
110.39 kB
Formato
Adobe PDF
|
110.39 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.