Excel for Exchange of Indivisible Goods:
A Users’ Manual for Ver.3 (excerpt)∗∗This excerpt was written by Shuya Abe (Graduate School of Information Science,Osaka University) and Naoki Watanabe (Graduate School of Business Administration,Keio University). The full version was published as a course material (case) by KeioBusiness School. Inquiries about reproducing the case should be referred to Keio Business School (4-1-1 Hiyoshi Kohoku, Yokohama, Kanagawa 223-8526; Phone: +81-45564-2444; E-Mail: case@kbs.keio.ac.jp) To order copies of the case, go to the website(http://www.kbs.keio.ac.jp).

1Contents
1 Introduction
1.1 Recommended Operating Environment . . . . . . . . . . . . .
1.2 Exchange of Indivisible Goods . . . . . . . . . . . . . . . . . .
1.3 Some Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3345

2 Configuration
2.1 man sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 result sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 analyze sheet . . . . . . . . . . . . . . . . . . . . . . . . . . .

557
8

3 Using Excel for Exchange of Indivisible Goods
3.1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Running the Program . . . . . . . . . . . . . . . . . . . . . . .
3.3 A Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

101010124 Troubleshooting
4.1 Developer ribbon does not appear . . . . . . . . . . . . . . . .
4.2 Error messages appear . . . . . . . . . . . . . . . . . . . . . .
4.3 No error message but incorrect allocation . . . . . . . . . . . .

121213132

1Introduction

This material is a users’ manual for a software Excel for Exchange of Indivisible Goods which runs on a computer. This section outlines the operating
environment of the software and exchange of indivisible goods, providingsome notes on the software.

1.1

Recommended Operating Environment

Excel for Exchange of Indivisible Goods version 3 (exchange v3.xlsm) was
developed by the authors and is currently available from the following URL.
http://labs.kbs.keio.ac.jp/naoki50lab/exchange_v3.xlsm
This program uses the macro function of Excel, and thus the download
may be blocked by companies, research and educational institutions in somecases. If so, please download it in users’ own personal Internet environments.
The screen-shots in this manual were taken in the environment shown in
Table 1.
Table 1: Environment of screen-shots
OSWindows 10 Enterprise
Excel
Microsoft Oﬃce 2016 Excel
CPUIntel(R) Core(TM) i7-3770K CPU @ 3.50GHz 3.90GHz
Memory
8 GB
Disk
1 TB

Excel for Exchange of Indivisible Goods runs on computers that can use
Excel VBA (Visual Basic for Applications). The recommended environment
is listed in Table 2.
Table 2: Recommended environment
OSExcelCPUMemory
Disk

Windows 7–，Mac OS X 10.8–
Microsoft Oﬃce 2013–，Microsoft Oﬃce for Mac 2016no requirement if Excel works
at least 2GB
no in particular31.2

Exchange of Indivisible Goods

Consider, for example, an assignment of rooms in residence halls to college
students. These rooms are diﬀerent in floor plan, sunshine hours, locationin the residence halls, age of the buildings, appliances and equipments, rent,
and so on. Students have diﬀerent preferences over the rooms. Supposethat a single room which may not be shared with other students (i.e., eachroom is indivisible) is initially allocated by their college to each student,
but that students are allowed to freely exchange their rooms after the initial
allocation. Any side payments among students are prohibited here. Then,
what is a desirable reassignment in this situation? This is called a houseswapping problem.
In Table 3, for example, the preferences of six students over their rooms
are listed, where the upper bars on lower-case letters of the Roman alphabet
mark their currently assigned room; C strictly prefers room e most and likes
his or her own house c more than other rooms a, d, and b.
Table 3: Table of Preferences over rooms
A:
B:
C:
D:
E:c eb̄ ae c̄
c ad cā bc ea db eb ēddbd¯aTreating house owners (or college students) as traders of the indivisible
houses (or rooms in residence halls), Shapley and Scarf (1974) formulated
this problem as exchange of indivisible goods and introduce an algorithm tocompute a desirable reassignment in the problem.1 In every house-swapping
problem, there is always only one reassignment of the houses so that nogroup could have improved even one member’s position without making someother member worse oﬀ. This unique reassignment is called strict core
allocation in game theory, given a list of traders’ strict preferences (rankingsrepresenting their preferences without any ties) over houses.
Excel for Exchange of Indivisible Goods computes the strict core allocation by using the TTC algorithm developed by David Gale and introducedin Shapley and Scarf (1974). The computation process is not described here
but explained in the Appendix.
1

The theory of exchange of indivisible goods is currently applied to various real practices
in many countries: the reassignment of rooms in residence halls to college students, thematching of kidney donors and patients, etc.

4

1.3Some Notes(1) Excel for Exchange of Indivisible Goods consists of 3 Excel sheets (man,result, analyze) and 1 Visual Basic for Applications (VBA) program.
If assistance is needed for reading and writing VBA codes, refer to an
appropriate textbook.
(2) In the inputs and outputs of this software, house owners and their houses
are represented by numerical IDs, respectively in inputs and outputs ofthis software.
(3) Users need to input numerical values in Arabic numerals (not doublebyte characters) without multiple numbers and without missing
values for initial settings, traders’ preferences over houses.
(4) Excel for Exchange of Indivisible Goods uses a program written in Visual
Basic. Thus, unlike editing a regular Excel sheet, users cannot restore
states by pressing the “backspace” key or pressing the “Z” key while
holding down the “Ctrl” key. It is possible to return the Excel file to theintended state before editing by closing the Excel file without saving thecurrent state.
(5) The computation results of this software are overwritten each time theprogram is run. Thus, users need to make a copy of the computation
results in another file.

2Configuration

Every house owner has his or her strict preference over all houses, i.e., rankingof houses without ties. In this software, houses are denoted by house IDs in
Arabic numerals, and house owners are denoted by house owner IDs also in
Arabic numerals.

2.1

man sheet

Input house owners’ preferences over houses represented by house IDs in thissheet. See Fig.1, where 7 house owners all report their preferences over 7houses and a null house. All houses which are not preferred to the null houseby a house owner are not assigned to the house owner; when a house owneris reassigned to a house which is not preferred to the null house, he or she
will choose free disposal of the house. The null house is denoted by 0 as itshouse ID.
5

Figure 1: man sheet
Rows in column A (man id): Input house owner (man) IDs in ascendingorder without multiple numbers and without missing values.
Rows in column B and thereafter (h rank): Each row is used for a houseowner. Input the house ID man i prefers at the jth rank in the cell corresponding to row (man id) i and column (h rank) j. In Fig.1, e.g., thesecond-best house (h rank2) for a house owner with ID=3 (man id=3)
is a house with ID=6. The value put in cell 4C is thus 6.
randomize button: Use this button to generate the house owners’ preferences randomly. When the preferences are randomly generated, thenull house is put at the last rank for every house owners. In Fig.1,
the list of preferences shown there was input by use’s own hand andthe randomize button is outside the frame of the screen shot. There isanother randomize button in Subsect.2.2, which functions in the sameway.
By using TTC algorithm, Excel for Exchange of Indivisible Goods computes a unique reassignment of houses called the strict core allocation in
6

game theory, given a list of house owners’ strict preferences over houses. In
the strict core allocation, no house owner is reassigned to a house which isat the lower rank than his or her own house. This property is called individual rationality. Thus, there is no need for house owners to report theirrankings of those houses which are not preferred to their own houses. Even
if the house IDs for those house are missing in the man sheet, this software
computes the strict core allocation.
When you use a function that examines whether a reassignment given
in your own hand is (Pareto) eﬃcient, however, make a complete list ofrankings in the man sheet, because the function needs such information. If
there are missing values in preferences in the man sheet, Excel for Exchangeof Indivisible Goods will display a run-time error message, when you press
the eval button in the result sheet, which is described in the next subsection.
Note that the strict core allocation is always (Pareto) eﬃcient.

2.2

result sheet

The computation results are shown in the result sheet. The buttons in thissheet are used to run each computation. See Fig.2, which shows a reassignment of 7 houses among 7 house owners and rankings of houses assigned tothem according to their preferences. As for TTC algorithm, see the Appendix
for the illustrations with an example.
Rows in column A (man id): House owner IDs are shown in ascendingorder.
Rows in column B (result house id): Houses reassigned to house owners are shown with house IDs, respectively. In Fig.2, e.g., a houseowner with ID=3 (man id=3) is reassigned to a house with ID=6 (result house id=6).
Rows in column C (last rank (man)): The rank of the house that is reassigned to a house owner in his or her preference is shown for eachhouse owner. In Fig.2, e.g., a house owner with ID=3 is reassigned
to a house with ID=6, which is the 2nd rank of his or her preference(last rank (man)=2). The values put in cells 4B and 4C are thus 6 and2, respectively.
randomize man button: The same function button that appears in the mansheet (Subsect.2.1). Use this button to generate the house owners’
preferences randomly. When the preferences are randomly generated,
the null house is put at the last rank for every house owners. The listof preferences shown in Fig.1 was input by use’s own hand.
7

Figure 2: result sheet
run button: Press to compute the unique strict core allocation by using theTTC algorithm.
eval button: Press when the (Pareto) eﬃciency of a reassignment shownin the result sheet or an allocation input by your own hand there is
examined according to house owners’ preferences input in the man sheet(Subsect.2.1).

2.3

analyze sheet

Consider a situation where a pair of house owners exchange their houses,
given an initial allocation or a reassignment (an allocation). If both houseowners are better oﬀ by that exchange, then the allocation is not (Pareto)eﬃcient. When you press eval button in the result sheet, Excel for Exchangeof Indivisible Goods starts searching for those pairs examining every pairof house owners. (It is not necessarily true that an allocation is Paretoeﬃcient, when there is no pair of house owners who are both better oﬀ bythat exchange.) The examination result is shown in the analyze sheet.
8Figure 3: analyze sheet
Fig.3 lists all pairs of house owners who are both better oﬀ by exchange of
their initially allocated or reassigned houses. The numbers colored in yellow
indicate the increase in their ranking over houses by that exchange, which
implies that the initial allocation or a reassignment is not (Pareto) eﬃcient.
The number of those observations is counted and shown in the upper-rightpart of the sheet (man count).
Rows in column A (manA) and column B (manB): All pairs of houseowners who can be better oﬀ by exchange of their houses are shownwith their IDs.
Rows in column C (houseA) and column D (houseB): Houses initiallyallocated or reassigned to the house owners listed in man A and man
B are shown with their IDs.
Rows in column E (manA up) and column F (manB up): The increments of ranks at the time when manA obtains houseB and manBobtains house A, respectively.

9Column H (man count): The number of those observations is shown in
the upper-right part of the sheet.
In Fig.3, e.g., a house with ID=3 is allocated to a house owner with ID=2
and another house with ID=5 is allocated to another house owner with ID=7.
When they exchange their houses initially allocated or reassigned, a houseowner with ID=2 obtains a house which is 3-rank higher than the one heor she has, and a house owner with ID=7 obtains a house which is 2-rankhigher than he or she has. There are 2 observations of such a pairs, which isshown in man count.

3

Using Excel for Exchange of Indivisible
Goods

3.1

Getting Started

Initially, set the number of house owners, not in Excel sheets, but in theVBA window (Fig.4). In the default, the number of house owners is set as 7.
1. Click on the Visual Basic button on the Developer ribbon.
2. Find VBAProject (exchange v3 (version 1).xlsb) by Project
explorer.
3. Open Module 1 in the Standard Module that is under
VBAProject (exchange v3 (version 1).xlsb).
4. Change the numbers in Const num man to set the number of houseowners. This is the first line in Module 1.
5. Save to the same file and close the VBA window.

3.2

Running the Program

1. Complete the initial setting for the numbers of workers and divisions
in the VBA window.
2. Input numerical data on house owners’ preferences in the (1) man sheet.
Click on randomize button if you generate the house owners’ preferences
randomly
3. Open the (2) result sheet.
10Figure 4: VBA window
4. Click on the run button for computing a matching with the TTC algorithm.
5. View computation results in the result sheet.
6. Click on the eval button for examining the eﬃciency of an reassignmentshown in the result sheet. Input numerical data on an allocation by11your own hand. Then, you can examine the eﬃciency of the allocation
you determined by yourself.
7. Open the (3) analyze sheet and view the examination result in theanalyze sheet.

3.3

A TipsThis software has a function to examine the ineﬃciency of the reassignmentshown in the result sheet (Subsect.2.2) based on house owners’ preferences
input in the man sheet (Subsect.2.1). You can enter the data of actual
allocation you have in the result sheet and press eval button, without pressing
run. The ineﬃciency of the actual allocation can be examined in the way
described above, given house owners’ preferences over houses. The strict
core allocation calculated by the TTC algorithm is (Pareto) eﬃcient.

4

Troubleshooting

4.1

Developer ribbon does not appear

In the default, Microsoft Oﬃce Excel does not show the Developer ribbon.
Complete the following procedure (in the case of Microsoft Oﬃce Excel 2016).
1. Click on the File ribbon.
2. Click on the Option ribbon.
3. Click on the Customize Ribbons in Excel Options window.
4. Confirm whether Main Tab appears in the Customize Ribbons field(Fig.5), and then look for Developer in the list of ribbons in Main
Tab. Check the check box for Developer
5. Click on the OK button.
6. Close the Excel’s Option window, and then the Developer button
appears. If the button does not, then open the Excel file again.

12

Figure 5: A Screen-shot of Excel Options

4.2

Error messages appearConfirm the following points, when error messages appear after pressing thebuttons to run the program.
• Did you input data in Arabic numerals with single-byte characters inthe VBA window and man sheet?
• Does the number of house owners initially set in the VBA window
coincide with the one which appears in man sheet?

4.3

No error message but incorrect allocation

Confirm the following points, when error messages appear but the software
does not generate a correct allocation after pressing the buttons to run theprogram.
• Did you open your Excel file in Protected View (Fig.6)? In that case,click on the Enable Editing button to end Protected View.
13

Figure 6: A Screen-shot of Protected View
• The previous result remains in the analyze sheet. Press the eval buttonin the result sheet for updating the result shown in the analyze sheet.
• If there is a blank space (missing value) in the man sheet, the following
error message (Fig.7) appears, when you press the eval button in theresult sheet.

Figure 7: An Error Message: A Blank Space in the Man Sheet
Then, click on the OK button and open the man sheet. The blankspace is indicated in pink (Fig.8) there .
• Are there any multiple numbers for a man id in the man sheet? In thatcase, the following error message (Fig.9) appears, when you press theeval button in the result sheet.
14

Figure 8: A Blank Space Indicated in the Man Sheet

Figure 9: An Error Message: Multiple Values for a House Owner
Then, click on the OK button and open the man sheet. The multiple
numbers are indicated in pink (Fig.10) there.
• You may leave a blank space (missing value) in the result sheet, whenyou enter some values by your own hand. In that case, the following
error message (Fig.11) appears, when you press the eval button in theresult sheet.
15

Figure 10: Multiple Values Indicated in the Man Sheet

Figure 11: An Error Message: A Blank Space in the Result Sheet
Then, click on the OK button and find the blank space indicated inpink (Fig.12) in the result sheet.
• You may enter the same number for several house owners in the resultsheet, when you enter the data by your own hand. In that case, the following error message (Fig.13) appears, when you press the eval button
16

Figure 12: A Blank Space Indicated in the Result Sheetin the result sheet.

Figure 13: An Error Message: The Same Numbers in the Result Sheet
Then, click on the OK button and find the same numbers indicated inpink (Fig.14) in the result sheet.

17Figure 14: The Same Numbers Indicated in the Result Sheet

18