---
title: "Envy-Free Sponsored Search Auctions with Budgets"
authors:
  - "Bo Tang"
  - "Jinshan Zhang"
doi: ""
url: "https://ijcai.org/proceedings/2015/98"
pdf: "https://ijcai.org/proceedings/2015/0098.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "653-658"
track: "Main Track"
keywords:
---

# Envy-Free Sponsored Search Auctions with Budgets

Bo Tang, Jinshan Zhang

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, 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.