Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation
Dynamic resource assignment is a common problem in multi-agent systems. We consider scenarios in which dynamic agents have preferences about assignments and the resources that can be assigned using online auctions. We study the trade-off between the following online auction properties: (i) truthfulness, (ii) expressiveness, (iii) efficiency, and (iv) average case performance. We theoretically and empirically compare four different online auctions: (i) Arrival Priority Serial Dictatorship, (ii) Split Dynamic VCG, (iii) e-Action, and (iv) Online Ranked Competition Auction. The latter is a novel design based on the competitive secretary problem. We show that, in addition to truthfulness and algorithmic efficiency, the degree of competition also plays an important role in selecting the best algorithm for a given context.
WOS:000385793700121
2016
Amsterdam
978-1-61499-672-9
978-1-61499-671-2
9
Frontiers in Artificial Intelligence and Applications
285
1035
1043
REVIEWED
EPFL
| Event name | Event place | Event date |
Hague, NETHERLANDS | AUG 29-SEP 02, 2016 | |