# Frugality in set-system auctions

Edith Elkind, Nanyang Technological University, Singapore

In set-system auctions, there is a task that can be completed by several overlapping teams of selfish agents, and the centers goal is to hire one of these teams and pay as little as possible. Examples of this setting include shortest path auctions, minimum spanning tree auctions, and vertex cover auctions. From the sellers perspective, an interesting parameter in this setting in the {\em frugality ratio} of a mechanism. Informally, the frugality ratio is the ratio of the total payment of a mechanism to a desired payment bound. The ratio captures the extent to which the mechanism overpays, relative to perceived fair cost. In this talk, I will discuss several alternative definitions of frugality ratio, and recent lower and upper bounds on frugality ratio for various classes of set systems.

This talk is part of the Microsoft Research Cambridge, public talks series.