Title
An online mechanism for multi-unit demand and its application to plug-in hybrid electric vehicle charging
Abstract
We develop an online mechanism for the allocation of an expiring resource to a dynamic agent population. Each agent has a non-increasing marginal valuation function for the resource, and an upper limit on the number of units that can be allocated in any period. We propose two versions on a truthful allocation mechanism. Each modifies the decisions of a greedy online assignment algorithm by sometimes cancelling an allocation of resources. One version makes this modification immediately upon an allocation decision while a second waits until the point at which an agent departs the market. Adopting a prior-free framework, we show that the second approach has better worst-case allocative efficiency and is more scalable. On the other hand, the first approach (with immediate cancellation) may be easier in practice because it does not need to reclaim units previously allocated. We consider an application to recharging plug-in hybrid electric vehicles (PHEVs). Using data from a real-world trial of PHEVs in the UK, we demonstrate higher system performance than a fixed price system, performance comparable with a standard, but non-truthful scheduling heuristic, and the ability to support 50% more vehicles at the same fuel cost than a simple randomized policy.
Year
DOI
Venue
2013
10.1613/jair.4064
J. Artif. Intell. Res. (JAIR)
Keywords
Field
DocType
online mechanism,higher system performance,fixed price system,plug-in hybrid electric vehicle,truthful allocation mechanism,non-increasing marginal valuation function,multi-unit demand,fuel cost,greedy online assignment algorithm,dynamic agent population,allocation decision,immediate cancellation
Population,Computer science,Fixed price,Common value auction,Artificial intelligence,Valuation (finance),Mathematical optimization,Operations research,Resource allocation,Plug in hybrid electric vehicle,Machine learning,Scalability,Allocative efficiency
Journal
Volume
Issue
ISSN
48
1
1076-9757
Citations 
PageRank 
References 
21
0.98
25
Authors
7
Name
Order
Citations
PageRank
Valentin Robu194870.44
Enrico H. Gerding275977.42
Sebastian Stein339442.61
David C. Parkes43293342.69
alex rogers52500183.76
Nicholas R. Jennings6193481564.35
Nicholas R. Jennings7193481564.35