Partitioning Linear Programme for the stable roommates problem

Usage

plp(V = NULL, N = NULL)

Arguments

V
valuation matrix of dimension NxN that gives row-players valuation over column players (or vice versa).
N
integer (divisible by 2) that gives the number of players in the market.

Value

plp returns a list with the following items.
Valuation.matrix
input values of V.

Assignment.matrix
upper triangular matrix of dimension NxN with entries of 1 for equilibrium pairs and 0 otherwise.

Equilibrium.groups
matrix that gives the N/2 equilibrium pairs and equilibrium partners' mutual valuations.

Description

Finds the stable matching in the stable roommates problem with transferable utility. Uses the Partitioning Linear Programme formulated in Quint (1991).

References

Quint, T. (1991). Necessary and sufficient conditions for balancedness in partitioning games. Mathematical Social Sciences, 22(1):87--91.

Examples

## Roommate problem with 10 players, transferable utility and random preferences:
plp(N=10)
$Valuation.matrix 1 2 3 4 5 6 1 -0.5558411 -0.6250393 0.82158108 1.20796200 -0.2257710 -1.07179123 2 1.7869131 -1.6866933 0.68864025 -1.12310858 1.5164706 0.30352864 3 0.4978505 0.8377870 0.55391765 -0.40288484 -1.5487528 0.44820978 4 -1.9666172 0.1533731 -0.06191171 -0.46665535 0.5846137 0.05300423 5 0.7013559 -1.1381369 -0.30596266 0.77996512 0.1238542 0.92226747 6 -0.4727914 1.2538149 -0.38047100 -0.08336907 0.2159416 2.05008469 7 -1.0678237 0.4264642 -0.69470698 0.25331851 0.3796395 -0.49103117 8 -0.2179749 -0.2950715 -0.20791728 -0.02854676 -0.5023235 -2.30916888 9 -1.0260044 0.8951257 -1.26539635 -0.04287046 -0.3332074 1.00573852 10 -0.7288912 0.8781335 2.16895597 1.36860228 -1.0185754 -0.70920076 7 8 9 10 1 -0.688008616 -0.2204866 1.3606524 -0.95161857 2 1.025571370 0.3317820 -0.6002596 -0.04502772 3 -0.284773007 1.0968390 2.1873330 -0.78490447 4 -1.220717712 0.4351815 1.5326106 -1.66794194 5 0.181303480 -0.3259316 -0.2357004 -0.38022652 6 -0.138891362 1.1488076 -1.0264209 0.91899661 7 0.005764186 0.9935039 -0.7104066 -0.57534696 8 0.385280401 0.5483970 0.2568837 0.60796432 9 -0.370660032 0.2387317 -0.2466919 -1.61788271 10 0.644376549 -0.6279061 -0.3475426 -0.05556197$Assignment.matrix
1  2  3  4  5  6  7  8  9 10
1  NA  1  0  0  0  0  0  0  0  0
2  NA NA  0  0  0  0  0  0  0  0
3  NA NA NA  0  0  0  0  0  0  1
4  NA NA NA NA  0  0  0  0  1  0
5  NA NA NA NA NA  1  0  0  0  0
6  NA NA NA NA NA NA  0  0  0  0
7  NA NA NA NA NA NA NA  1  0  0
8  NA NA NA NA NA NA NA NA  0  0
9  NA NA NA NA NA NA NA NA NA  0
10 NA NA NA NA NA NA NA NA NA NA

$Equilibrium.groups player.A player.B mutual.valuation 1 1 2 1.161874 2 5 6 1.138209 3 7 8 1.378784 4 4 9 1.489740 5 3 10 1.384051 ## Roommate problem with 10 players, transferable utility and given preferences: V <- matrix(rep(1:10, 10), 10, 10) plp(V=V)$Valuation.matrix
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    1    1    1    1    1    1    1    1    1     1
[2,]    2    2    2    2    2    2    2    2    2     2
[3,]    3    3    3    3    3    3    3    3    3     3
[4,]    4    4    4    4    4    4    4    4    4     4
[5,]    5    5    5    5    5    5    5    5    5     5
[6,]    6    6    6    6    6    6    6    6    6     6
[7,]    7    7    7    7    7    7    7    7    7     7
[8,]    8    8    8    8    8    8    8    8    8     8
[9,]    9    9    9    9    9    9    9    9    9     9
[10,]   10   10   10   10   10   10   10   10   10    10

$Assignment.matrix [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] NA 0 0 0 0 0 0 0 0 1 [2,] NA NA 0 0 0 0 1 0 0 0 [3,] NA NA NA 0 0 1 0 0 0 0 [4,] NA NA NA NA 1 0 0 0 0 0 [5,] NA NA NA NA NA 0 0 0 0 0 [6,] NA NA NA NA NA NA 0 0 0 0 [7,] NA NA NA NA NA NA NA 0 0 0 [8,] NA NA NA NA NA NA NA NA 1 0 [9,] NA NA NA NA NA NA NA NA NA 0 [10,] NA NA NA NA NA NA NA NA NA NA$Equilibrium.groups
player.A player.B mutual.valuation
1        4        5                9
2        3        6                9
3        2        7                9
4        8        9               17
5        1       10               11