Monday, 15:15 - 15:40 h, Room: MA 043


Maria Polukarov
Optimal payments in dominant-strategy mechanisms for single-parameter domains

Coauthors: Nicholas R. Jennings, Victor Naroditskiy


We study dominant-strategy mechanisms in allocation domains where agents have one-dimensional types and quasi-linear utilities. Taking an allocation function as an input, we present an algorithmic technique for finding optimal payments in a class of mechanism design problems, including utilitarian and egalitarian allocation of homogeneous items with nondecreasing marginal costs.
Our results link optimality of payment functions to a geometric condition involving triangulations of polytopes. When this condition is satisfied, we constructively show the existence of an optimal payment function that is piecewise linear in agent types.


Talk 1 of the invited session Mon.3.MA 043
"Design of optimal mechanisms" [...]
Cluster 8
"Game theory" [...]


  unsecured personal loans . In this section we give only a brief summary recommendation for admission of Levitra Sale. Full information can be found in the instructions for receiving medications with vardenafil.