Envy-Free Sponsored Search Auctions with Budgets
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 653-658.
Abstract
We study the problem of designing envy-free sponsored search auctions, where bidders are budget-constrained. Our primary goal is to design auctions that maximize social welfare and revenue — two classical objectives in auction theory. For this purpose, we characterize envy-freeness with budgets by proving several elementary properties including consistency, monotonicity and transitivity. Based on this characterization, we come up with an envy-free auction, that is both social-optimal and bidder-optimal for a wide class of bidder types. More generally, for all bidder types, we provide two polynomial time approximation schemes (PTASs) for maximizing social welfare or revenue, where the notion of envy-freeness has been relaxed slightly. Finally, in cases where randomization is allowed in designing auctions, we devise similar PTASs for social welfare or revenue maximization problems.
@inproceedings{ijcai2015p98,
title = {Envy-Free Sponsored Search Auctions with Budgets},
author = {Tang, Bo and Zhang, Jinshan},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {653--658},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/98},
}
TY - CPAPER TI - Envy-Free Sponsored Search Auctions with Budgets AU - Tang, Bo AU - Zhang, Jinshan T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 653 EP - 658 UR - https://ijcai.org/proceedings/2015/98 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
