The unprecedented growth of demand for charging electric vehicles (EVs) calls for novel expansion solutions to today’s charging networks. Riding on the wave of the proliferation of sharing economy, Airbnb-like charger sharing markets open the opportunity to expand the existing charging networks without requiring costly and time-consuming infrastructure investments, yet the successful design of such markets relies on innovations at the interface between game theory, mechanism design, and large scale optimization. In this paper, we propose a price-based iterative double auction for charger sharing markets where charger owners rent out their under-utilized chargers to the charge-needing EV drivers. Charger owners and EV drivers form a two-sided market which is cleared by a price-based double auction. Chargers’ locations, availabilities, and unit time service costs as well as drivers’ time and location preferences are considered in the allocation and scheduling process. The goal is to compute social welfare maximizing schedules which benefit both charger owners and EV drivers and, in turn, ensure the continuous growth of the market. We prove that the proposed double auction is budget balanced and individually rational. In addition, results from our computational study show that the proposed auction achieves on average 94% efficiency compared with that of the optimal solutions and is suitable for a larger day-ahead charger sharing market setting in terms of running time.@en

Providing high-quality matching between drivers and riders is imperative for sustaining the growth of ride-sharing platforms. A user-focused matching mechanism design plays a key role in terms of ensuring user satisfaction. In this paper, we consider the matching problem in the community ride-sharing setting, where drivers and riders have strong personal preferences over the matched counterparties. Obtaining high-quality solutions that accommodate drivers’ and riders’ preferences in such a setting is particularly challenging as drivers and riders maybe reluctant to share with the platform their personal preferences over their ride-sharing counterparties due to privacy and ethical concerns. To this end, we propose a VOting-based MAtching (VOMA) mechanism to compute near-optimal matching solutions for drivers and riders, while preserving their privacy. The mechanism is a distributed implementation of the simulated annealing meta-heuristic, which computes matching solutions by guiding drivers and riders in the distributed search process using an iterative voting protocol. We evaluate the performance of VOMA using test cases generated based on New York taxi data sets. The experiment results show that the proposed matching mechanism achieves on average 90.9% efficiency compared with optimal solutions. We also show that VOMA improves the vehicle miles traveled (VMT) savings by up to 35% compared to an alternative voting-based greedy matching mechanism. System scalability and other practical issues regarding the implementation of such a matching mechanism in community ride-sharing platforms are also discussed.@en

As an alternative to traditional taxi services, Transportation Network Companies (TNCs) such as Uber and Lyft are playing an increasingly important role in the paradigm shifting from car ownership to mobility as a service. We consider an electric vehicle fleet charging scheduling problem in the TNC setting where taxi drivers, as freelancers, have their individual preferences regarding when and where to charge their vehicles. In this setting, obtaining social welfare maximizing schedules is particularly difficult as drivers may behave strategically in competing over shared charging resources to advance their own benefits rather than the system wide social welfare. We propose a negotiation mechanism which allows drivers to collectively evolve an incumbent schedule into a socially beneficial one through an iterative voting process. The proposed mechanism provides a platform which enables multilateral negotiation among a large number of drivers. We prove that, given the design of the proposed mechanism, drivers’ best response strategy is to truthfully vote their best valued candidate schedules according to the acceptance quota prescribed by the scheduler at each voting round. In addition, experiment results show that the mechanism achieves on average 93% efficiency compared with optimal solutions and scales well to larger problem instances.

@en

This paper presents a multiagent systems model for patient diagnostic services scheduling. We assume a decentralized environment in which patients are modeled as self-interested agents who behave strategically to advance their own benefits rather than the system wide performance. The objective is to improve the utilization of diagnostic imaging resources by coordinating patient individual preferences through automated negotiation. The negotiation process consists of two stages, namely patient selection and preference scheduling. The contract-net protocol and simulated annealing based meta-heuristics are used to design negotiation protocols at the two stages respectively. In terms of game theoretic properties, we show that the proposed protocols are individually rational and incentive compatible. The performance of the preference scheduling protocol is evaluated by a computational study. The average percentage gap analysis of various configurations of the protocol shows that the results obtained from the protocol are close to the optimal ones. In addition, we present the algorithmic properties of the preference scheduling protocol through the validation of a set of eight hypotheses.

@en

Consider a decentralized electric vehicle (EV) charging scheduling problem where the chargers and vehicles are modeled as utility maximizing agents. To schedule chargers to vehicles in a day-ahead market, we propose a double auction mechanism, where chargers report their time availabilities and charging costs and vehicles report their preferences on different chargers. This auction is conducted in an iterative manner which enables the computation of effective schedules through multilateral negotiation between agents. We evaluate the efficiency performance of the mechanism through a computational study. The result generated from the iterative double auction mechanism is on average 35% better than the first come first serve (FCFS) allocation policy.

@en