Combinatorial Auctions with Budgets

Colini-Baldeschi, Riccardo; Leonardi, Stefano; Sankowski, Piotr; Zhang, Qiang
We consider budget constrained combinatorial auctions where bidder \$i\$ has a private value \$v\_i\$, a budget \$b\_i\$, and is interested in all the items in \$S\_i\$. The value to agent \$i\$ of a set of items \$R\$ is \$|R \backslash cap S\_i| \backslash cdot v\_i\$. Such auctions capture adword auctions, where advertisers offer a bid for ads in response to an advertiser-dependent set of adwords, and advertisers have budgets. It is known that even of all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality for such auctions when the valuations are private and the budgets are public knowledge. This extends the result of Dobzinski et al. (FOCS 2008) for auctions of multiple \{$\backslash$sl identical\} items and public budgets to single-valued \{$\backslash$sl combinatorial\} auctions with public budgets.
Research areas:
Type of Publication:
Lecture Notes in Computer Science
Hits: 5040

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information