# 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