COLLABORATIVE PLAN GENERATION BASED ON VARYING PREFERENCES AND CONSTRAINTS

• US 20100332242A1
• Filed: 06/25/2009
• Published: 12/30/2010
• Est. Priority Date: 06/25/2009
• Status: Active Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kamar, Ece, Horvitz, Eric J.
• Application Number:
  US12/491,635
• Publication Number:
  US 20100332242A1
• Time in Patent Office: Days
• US Class Current: 705/1.1
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events

Abstract

Embodiments for generating and implementing collaborative plans that achieve goals for sets of individual agents based on a consideration of individual and group preferences are disclosed. In accordance with at least one embodiment, a collaborative mechanism includes receiving individual plan preferences of agents via one or more client devices and modeling agent costs based on the received individual plan preferences. One or more collaborative plans are then be generated based on the modeled agent costs and one or more agents may be grouped into each collaborative plan. The one or more generated collaborative plans are provided to the agents via the one or more client devices for implementation. Finally, payments are distributed among the agents to compensate at least one agent for participation in one of the generated collaborative plans.

Claims

1. A rideshare system, comprising:

an input component to receive commute plan preferences of agents via one or more client devices;

a modeling component to model agent costs based on the received commute plan preferences;

an optimizer component to generate one or more rideshare plans based on the modeled agent costs and group one or more agents into each rideshare plan;

an output component to provide the one or more generated rideshare plans to the agents via the one or more client devices for implementation; and

a Vickrey-Clarke-Groves (VCG)-based payment component to distribute payments among the agents to compensate at least one driver agent for participation in one of the generated rideshare plans.

2. The system of claim 1, wherein the VCG-based payment component is to distribute payments among the agents by collecting payment from at least one passenger agent.

3. The system of claim 1, wherein the modeling component includes a probabilistic time-cost model to account for a time cost of each agent.

4. The system of claim 1, wherein the modeling component includes a probabilistic time-cost model that uses time of day, day of week, and appointments of agents to account for a time cost of each agent.

5. The system of claim 1, wherein the modeling component is to model agent costs based on agent-specific costs for at least one of cost of driving, cost of delaying a trip, cost of driving, cost of diverting from an ideal route pick up or drop one or more agents, or cost of changing stop points for one or more agents.

6. The system of claim 1, wherein the optimizer component further includes:

a rideshare plan optimizer to generate the one or more rideshare plans based on the model agent costs to maximize the overall value of the rideshare system to the agents; and

a rideshare group optimizer to assign rideshare group of agents based on the rideshare plans to produce the highest cumulative value for the rideshare system.

7. The system of claim 1, wherein the optimizer component further includes a rideshare plan optimizer component that uses traffic predictions and daily contexts to estimate inconvenience cost for each of the agents, and perform a geospatial search over the paths of the rideshare plans to minimize inconvenience cost to each of the agents.

8. The system of claim 1, wherein the optimizer component further includes a rideshare group optimizer that uses an approximate, greedy-set algorithm to ensure that the one or more agents grouped into each rideshare plan does not experience negative utility due to participation in the rideshare system.

9. The system of claim 1, wherein the VCG-based payment component includes a threshold-based mechanism to ensure that no deficits are incurred by the rideshare system.

10. The system of claim 1, wherein the commute plan preferences of each agent includes one or more of agent identification, origin location, destination location, time of trip, and return trip preference.

11. The system of claim 1, wherein each of the provided rideshare plans includes at least one of a carpool pick location, carpool date and time, description of carpool vehicle for each of the one or more agents.

12. A method, comprising:

receiving commute plan preferences of agents at a computing device from one or more client devices;

modeling agent costs based on the received commute plan preferences and agent-specific costs of each agent at the computing device;

generating one or more rideshare plans at the computing device based on the modeled agent costs and group one or more agents into each rideshare plan;

providing the one or more generated rideshare plans from the computing device to the agents via the one or more client devices for implementation;

computing Vickrey-Clarke-Groves (VCG)-based payments to compensate at least one driver agent for participation in one of the generated rideshare plans at the computing device; and

collecting VCG payments from at least one passenger agent at the computing device for benefit derived from participation in one of the generated rideshare plans.

13. The method of claim 12, wherein the modeling includes a probabilistic time-cost model that use time of day, day of week, and appointments of agents to account for a time cost of each agent.

14. The method of claim 12, wherein the agent-specific costs for each agent includes least one of cost of driving, cost of delaying a trip, cost of driving, cost of diverting from an ideal route pick up or drop one or more agents, cost of changing stop points for one or more agents, or psychosocial cost of traveling with the one or more agents, the psychosocial cost being based at least on established reputations of the one or more agents, social relationships with the one or more agents, or organizational relationships with the one or more agents.

15. The method of claim 12, wherein the generating includes:

generating the one or more rideshare plans based on the model agent costs to maximize the overall value of a rideshare system to the agents; and

assigning rideshare group of agents based on the rideshare plans to produce the highest cumulative value for the rideshare system.

16. The method of claim 12, wherein the generating includes using traffic predictions and daily contexts to estimate inconvenience cost for each of the agents, and perform a geospatial search over the paths of the rideshare plans to minimize inconvenience cost to each of the agents.

17. The method of claim 12, wherein the generating includes using an approximate, greedy-set algorithm to ensure that the one or more agents grouped into each rideshare plan does not experience negative utility due to participation in the rideshare system.

18. The method of claim 12, wherein the receiving includes receiving commute plan preferences of each agent that includes one or more of agent identification, origin location, destination location, time of trip, and return trip preference.

19. The method of claim 12, wherein the providing includes providing at least one of a carpool pick location, carpool date and time, description of carpool vehicle for each of the one or more agents.

20. A computer readable medium storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

receiving individual plan preferences of agents into a computing device of a collaboration system from one or more client devices;

modeling agent costs based on the received individual plan preferences and agent-specific costs of each agent at the computing device;

generating one or more collaborative plans based on the modeled agent costs to maximize the overall value of the collaboration system to the agents at the computing device;

assigning agents to collaborative groups based on the collaborative plans to produce the highest cumulative value for the collaboration system at the computing device;

providing the one or more generated collaborative plans from the computing device to the agents via the one or more client devices for implementation;

computing Vickrey-Clarke-Groves (VCG)-based payments to compensate at least one agent for participation in one of the generated collaborative plans at the computing device; and

distributing VCG payments among the agents to compensate at least one agent for participation in one of the generated collaborative plans.

21. The computer readable medium of claim 20, wherein the generating includes using an approximate, greedy-set algorithm to ensure that the one or more agents grouped into each collaborative plan does not experience negative utility due to participation in the collaborative system.

22. The computer readable medium of claim 20, wherein the distributing includes distributing VCG payments among the agents by collecting payment from at least one first agent that receives a benefit via participation in the collaboration plan and distributing the payment to at least one second agent that incurs a loss via participation in the collaboration plan.