Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

16 January 2018, Computational Social Choice Seminar, Ronald de Haan

Speaker: Ronald de Haan
Title: Tool Auctions
Date: Tuesday 16 January 2018
Time: 15:00
Location: Room F1.15, Science Park 107, Amsterdam

Abstract

We introduce tool auctions, a novel market mechanism for constructing a cost-efficient assembly line for producing a desired set of products from a given set of goods and tools. Such tools can be used to transform one type of good into a different one. We then study the computational complexity of tool auctions in detail, using methods from both classical and parameterized complexity theory. While solving such auctions is intractable in general, just as for the related frameworks of combinatorial and mixed auctions, we are able to identify several special cases of practical interest where designing efficient algorithms is possible.

(This is joint work with Janosch Döcker, Britta Dorn, Ulle Endriss, and Sebastian Schneckenburger.)