English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

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 theitems on sale, and she appraises at some single-value every item in herpreference-set. Moreover, each buyer has a budget that constraints the maximumaffordable payment, while she aims to obtain as many items as possible of herpreference-set. Our goal is to compute an envy-free pricing allocation thatmaximizes the revenue, i.e., the total payment charged to the buyers. Thispricing problem is hard to approximate better than $\Omega({\rm min}\{n,m\}^{1/2-\epsilon})$ for any $\epsilon>0$, unless $P=NP$. The hardnessresult is due to the presence of the matching constraints given that thesimpler multi-unit case can be approximated up to a constant factor of $2$. Thegoal of this paper is to circumvent the hardness result by restrictingourselves to specific settings of valuations and budgets. Two particularlysignificant scenarios are: each buyer has a budget that is greater than hersingle-value valuation, and each buyer has a budget that is lower than hersingle-value valuation. Surprisingly, in both scenarios we are able to achievea $1/4$-approximation to the optimal envy-free revenue. The algorithms utilizea novel version of the Ausebel ascending price auction. These results maysuggest that, although it is difficult to approximate the optimal revenue ingeneral, ascending price auctions could achieve relatively good revenue in mostof the practical settings.

Revenue Maximizing Envy-Free Pricing in Matching Markets with Budgets