# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, February 13, 2012

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136, 10623 Berlin
room MA 041

Lecture - 14:15

### Multi-unit auctions with budgets

Abstract:
We consider multi-unit auctions with additive valuations where each bidder has a private value on each item and an overall budget constraint.
Such auctions capture adword auctions, where advertisers offer a bid for those adwords that (hopefully) target their intended audience, and advertisers also have budgets.
In a sponsored search auction the advertisement slots on the search result page of an adword are generally ordered by click-through rate. Bidders have a valuation, which is usually assumed to be linear in the click-through rate and receive at most one slot per search result page.
It is known that even if all items are identical and all budgets are public it is not possible to design an efficient incentive compatible auction. Dobzinski, Lavi and Nisan (2008) presented an incentive compatible pareto optimal auction for multiple identical items with budgets. Several recent results related to the design of auctions with budgets will be presented in this talk. We will discuss: i) The combinatorial case in which each bidder is only interested in a subset of the items ii) The case of multiple slots with different CTRs available for each item/keyword; iii) The problem of maximizing the revenue of the auctioneer in envy-free allocations.

Colloquium - 16:00

### A Lower Bound for Shallow Partitions

Abstract:
Let P be a planar n-point set. A k-partition of P is a subdivision of P into n/k parts of roughly equal size and a sequence of triangles such that each part is contained in a triangle. A line is k-shallow if it has at most k points of P below it.
The crossing number of a k-partition is the maximum number of triangles in the partition that any k-shallow line intersects. We give a lower bound of Omega(log (n/k)/loglog(n/k)) for this crossing number, answering a 20-year old question of Matousek.
Joint work with Daniel Werner.

Letzte Aktualisierung: 06.02.2012