PK: a Scalable Algorithm to Compute Kernel-Stable Payments for Social Ridesharing

PK is an algorithm to compute Kernel-stable payments for Social Ridesharing. PK has been presented by Filippo Bistaffa, Georgios Chalkiadakis, Alessandro Farinelli, and Sarvapali D. Ramchurn in “Recommending Fair Payments for Large-Scale Social Ridesharing”, Proceedings of the 2015 ACM Conference on Recommender Systems (RecSys), pages 139–146, 2015, ACM.

Requirements

PK requires g++ to compile, and does not require any external library to execute.

Execution

PK must be executed by means of the pk.sh script, i.e.,

Usage: ./pk.sh -i <filename> [-e <epsilon>]

-i	Input filename
-e	Epsilon

where filename is the solution file generated by SR-CFSS using the -p command-line option.

Input File Format

INPUTFILE is the path of the input file, which must be structured according to the following format.

• N (i.e., the number of agents) in the first line.
• K (i.e., the maximum coalition cardinality) in the second line.
• SEED (i.e., the seed used to generate the pseudo-random SR instance) in the third line.
• N lines representing the adjacency matrix of the graph (each edge should be associated to a natural number ≠ 0).
• M lines representing the M coalitions in the solution coalition structure. Each line must contain the coalition's members. Drivers must be marked by preceding their indices with * (e.g., *0 means that 0 is a driver).

The following example file represents a solution of the instance with SEED = 47, K = 5, and with the following graph.

The solution coalition structure is `{{9},{6},{2},{7,0,1,3,8},{4},{5}}`, where `7` is a driver.

10
5
47
0 1 2 5 7 0 0 13 15 0
1 0 3 4 6 8 11 0 0 0
2 3 0 0 0 0 10 0 0 17
5 4 0 0 0 0 0 0 14 0
7 6 0 0 0 9 0 12 0 16
0 8 0 0 9 0 0 0 0 0
0 11 10 0 0 0 0 0 0 0
13 0 0 0 12 0 0 0 0 0
15 0 0 14 0 0 0 0 0 0
0 0 17 0 16 0 0 0 0 0
9
6
2
*7 0 1 3 8
4
5

Acknowledgements

PK employs the GeoLife dataset by Microsoft Research presented by Yu Zheng, Quannan Li, Yukun Chen, Xing Xie, and Wei-Ying Ma in “Understanding mobility based on GPS data”, Proceedings of the 10th ACM conference on Ubiquitous Computing (Ubicomp), pages 312−321, 2008, ACM press.