<jupyter_start><jupyter_text>Team submitting this assignment:  _list each member of your team here_External resources used:  _it is not necessary to list the course materials, but if you used any other resources, including discussing problems with students not on your team, list them here_  Project 3: Matchmaker, Matchmaker Due: 3:59pm, Friday, 22 February 2019This project focuses on the allocation of discrete goods without the use of money. You will examine the market for kidney donation in the United States. The National Organ Transplant Act of 1984 outlawed the purchase and sale of kidneys, preventing a pricing-based market. Since the early 2000s, economists and medical professionals have developed different solutions to the problem of allocating kidneys from donors to recipients. This project will guide you through the basics of discrete exchanges, and you will propose and implement your own method at the end.   For this assignment, you should form your own team with the following constraints:- It must be three or four people.- At least one team member must be in the Economics section; at least one team member must be in the Computer Science section.- Your team cannot include a group of more than two people who have already worked together. (That is, it is okay if there are two pairs of people who have worked together on a previous assignment in a team of four, but not if there is a group of three people on a team who have worked together previously.)You should have your team formed by **Monday, 11 February** at the latest. If you are not on a team by then, contact the course staff. You are encouraged to use the `teaming` channel in the course slack to find teammates.         Kidney Exchange Humans are born with two kidneys, but can live well with just one healthy kidney. Hence, there is an opportunity for a live donor to donate a kidney to a patient whose kidneys have failed. There are two important factors when considering recipient and donor compatibility: blood type and tissue type. A recipient, $R$, and a donor, $D$, must pass both a blood type and tissue type compatibility test to be considered compatible for a transplant. 1.  Blood Type Compatibility: The four blood types are O, A, B, and AB.    -   Type O is compatible with all other types (that is, a kidney from a donor with type **O** can be matched with a recipient with any blood type).    -   Type A is compatible with types A and **AB**.    -   Type B is compatible with types B and **AB**.    -   Type **AB** is compatible with type **AB**.    2.  Tissue Compatibility: Each recipient $R_i$ can be tissue-type incompatible with a donor. Tissue compatibility depends on the compatibility of immune system markers (HLA) between the donor and recipient. Roughly, the closeness of the HLA match required depends on the recipient's reactve immune system, measured as *percent reactive antibody* (PRA). For this project we discretize these values:    -   _Low-PRA_ individuals (about 70% of population) have less active antibodies. A _Low-PRA_ recipient has a 95% chance of being tissue-compatible with a randomly-selected donor.    -   _Medium-PRA_ individuals (about 20% of population) have a 55% chance of being tissue-compatible as a recipient for a randomly-selected donor.    -   _High-PRA_ individuals (about 10% of population) have a 10% changes of being tissue-compatible as a recipient for a randomly-selected donor.These tests are independent of one another. In order for a donor kidney to be acceptable, it must be both blood type compatible and tissue-type compatible with the recipient.  Modeling Kidney ExchangeThe goal of a kidney exchange is to enable patients in need of a kidney who have someone willing to donate to them, but whose kidney is incompatible, find a chain of donor-recipients that enable the patient to receive a compatible kidney from another donor in exchange for this patient's willing donor donating a kidney to another patient.It is common to organize the market in the following way. Each recipient, $R_i$, is paired with their incompatible but willing donor, $D_i$. A market of size $N$ will have $N$ incompatible pairs {$(R_1-D_1),...,(R_n-D_n)$}. A donor will donate her kidney if and only if her paired but incompatible recipient also receives a kidney. We can model the market is a directed graph where each edge connects a donor with a compatible recipient. Thus, the edges represent all directly compatible exchanges. The problem the market designer faces is finding a method that will maximize the survival rate while accounting for the constraints on donations.Donation is usually done through _k_-way exchanges, which can be represented as cycles in the directed graph.A _two-way exchange_ is when a donor, $D_i$, donates to a recipient, $R_j$, whose incompatible partner $D_j$ then donates to $R_i$. For this exchange to work, $D_i$ must be compatible with $R_j$ and $D_j$ must be compatible with $R_i$. There are a total of two incompatible pairs, two donors and two recipients, in a two-way exchange. In a _three-way exchange_, the donor in pair 1 donates to pair 2, whose donor donates to pair 3, whose donor donates to pair 1. A _k-way exchange_ would have $k$ pairs donating in a cycle of length $k$.For more information, see [_Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences_](http://uvammm.github.io/docs/kidneyexchange.pdf) by <NAME>, <NAME> and <NAME>, American Economic Review 2007.   DataSince the medical data such as what is needed for kidney exchange is sensitive, we will use simulated data. We have provided some simulated data in [`patients.csv`](https://raw.githubusercontent.com/uvammm/uvammm.github.io/master/projects/project3/patients.csv) drawn from the empirical distribution of characteristics. You should download this file, and save it in the directory where you are working on the notebook.The code we used to generate that data is here: [`simulator.py`](https://raw.githubusercontent.com/uvammm/uvammm.github.io/master/projects/project3/simulator.py) (you are welcome to run or modify that code to produce your own data, but the results you report for the problems should be done using the provided data).Each row represents an incompatible pair with the following fields:- `TimePeriod`: The time period when the pair entered the kidney exchange pool- `ReceiverTissueID`: A number representing the receiver's tissue characteristics- `ReceiverBloodType`: The receiver's blood type (`A`, `B`, `O` or `AB`)- `ReceiverPRA`: The receiver's PRA (`Low`, `Medium` or  `High`)- `ReceiverSurvivalPrb`: The probability that an unmatched receiver will survive till the next time period.- `DonorTissueID`: A number representing the donor's tissue characteristics- `DonorBloodType`: The donor's blood type (`A`, `B`, `O` or `AB`)Here is some sample code for reading that file:<jupyter_code>import csv

pairs = [] # list of (patient, donor) pairs
with open('patients.csv', newline='') as csvfile:
    simreader = csv.reader(csvfile, delimiter=',')
    headers = next(simreader)
    print(str(headers))
    for row in simreader:
        pairs.append({key: value for key, value in zip(headers, row)})
print ("Number of patients: " + str(len(pairs)))
print ("Patient 37 blood type: " + pairs[37]['ReceiverBloodType'])
print ("Patient 598 donor tissue ID: " + pairs[598]['DonorTissueID'])<jupyter_output>Number of patients: 600
Patient 37 blood type: O
Patient 598 donor tissue ID: 4902<jupyter_text>Two-Way ExchangeIn the first part of the assignment, you will clear the kidney exchange market using only two-way exchanges. The steps below will guide you through the process of computing a solution to the matching problem.We will take the given data as static, ignoring the TimePeriod and assuming all pairs are present and ready to be matched. Since the matching will occur over a single period, we will also ignore the ReceiverSurvivalPrb. Therefore, we will have a market with 599 pairs of agents.We have provided two functions that you can use to test for blood type, `is_blood_compatible`, and tissue type `is_tissue_compatible` compatibility.<jupyter_code>def is_blood_compatible(blood_don, blood_recv):
    """
    This function returns True if the donor with blood type blood_don is
    compatible with receiver with bood type blood_recv.
    """
    if blood_don == 'O':
        return True
    elif blood_don == 'A':
        return blood_recv in ('A', 'AB')
    elif blood_don == 'B':
        return blood_recv in ('B', 'AB')
    elif blood_don == 'AB':
        return blood_recv == 'AB'
    else:
        raise InvalidParameterException("Invalid blood type: " 
                                        + blood_don)

def is_tissue_compatible(recv_pra, recv_tissueid, don_tissueid):
    """
    Modeling actual tissue compatibility is complex, and depends on
    properties of different HLA markers and various other complications.
    Instead of dealing with the medical complexities, we use a simple 
    model that produces a uniformly-distributed value that is dependent
    on the two inputs, and outputs a discretized probability.
    
    It's not important to understand the following code. But you should 
    call this function with the receiver's PRA-type, receiver's tissue 
    ID, and the donor's tissue ID to check if their tissues are 
    compatible or not.
    
    Example usage: is_tissue_compatible('Low', 4474, 3587)
    """
    
    # This code is a convoluted way to approximate a random oracle on 
    # the tissue ids (so the output is uniformly random in [0, 1), 
    # but for a given tissue pair, the same output is always produced). 
    import hashlib
    hexval = hashlib.md5((str(recv_tissueid) 
                          + str(don_tissueid)).encode()).hexdigest()
    intval = int(hexval, 16)
    b = intval / (1 << 129 - 1)  # map 128-bit number to 0-1
    
    if recv_pra == 'Low':
        return b <= 0.95
    elif recv_pra == 'Medium':
        return b <= 0.45
    else:  # high pra
        assert recv_pra == 'High'
        return b <= 0.10<jupyter_output><empty_output><jupyter_text>Problem 1. Compute the mutual compatibility matrix, $\textbf{C}$, for time period 1, where $c_{i,j}=1$ if recipient $i$ is compatible with donor $j$ and zero otherwise. You need to account for blood type and tissue type compatilbility when determining overall compatilbility of two agents.<jupyter_code># Write your code here<jupyter_output><empty_output><jupyter_text>*Write your explanation here*    Problem 2. Find the maximum matching given $\textbf{C}$ if only two-way exchanges are allowed. For this, you may find the [_Top Trading Cycles algorithm_](https://people.cs.umass.edu/~sheldon/teaching/mhc/cs312/2014sp/Slides/top-trading-cycles.pdf) helpful. Your code should report total number of matched pairs. The target number of matched pairs should be around 320.<jupyter_code># Write your code here<jupyter_output><empty_output><jupyter_text>Write your explation here    Problem 3. Analyze the execution cost of your matching algorithm (for problem 2). A good answer will include both an asymptotic analysis, and a concrete discussion of how large an exchange problem it could reasonably scale to support.  Three-Way ExchangeFor the second part of the assignment, you will extend your matching algorithm to allow both two- and three-way exchanges. You may also use $k$-way exchanges where $k\geq4$. For this question, you will continue to use $\textbf{C}$ from problem 1 in order to compare your results from both parts. (We will again take the given data as static, ignoring the `TimePeriod` and assuming all pairs are present and ready to be matched, just as in problem 1.)Problem 4. Find the maximum matching given $\textbf{C}$ from problem 1 and using two- and three-way exchanges (and optionally, support exchanges up to higher $k$. You will need to modify your code from the previous part to allow for cycles of up to 3 (or more) pairs. Your code should report the total number of matched pairs (not the number of cycles). You should see an increase of about 10% from your earlier two-way exchange.<jupyter_code># write your code here<jupyter_output><empty_output><jupyter_text>*Explain your answer here*  Efficiency in Two and Three-Way Exchanges[_Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences_](http://uvammm.github.io/docs/kidneyexchange.pdf) by <NAME>, <NAME> and <NAME> provides the bound on the number of two-way and three-way matches.Problem 5.How does the number of matches provided by your algorithm compare with the bound in the paper? If there is a discrepency, explain why. _Explain your answer here_  Dynamic ExchangeFor the final part of the assignment, we will now take the market to be dynamic - instead of having a fixed set of patients and donors, new patients arrive over time (and old patients die if they do not receive a donor kidney). The goal is to maximize the overall survival of the population.We have provided a function that simulates patient survival with a simple random draw. For each unmatch patient at the end of a time period, their probability of surviving to the next time period is given by the `ReceiverSurvivalPrb` field in the data.<jupyter_code># This function returns True if an unmatched receiver survives
def survival(survivalprob):
    import random
    draw = random.random()
    return draw <= survivalprob<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0624722098710538, 'fraction_numerical': 0.009485697346969022, 'mean_word_length': 4.238742236024844, 'pattern_counts': {'":': 0, '<': 36, '<?xml version=': 0, '>': 30, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '23007', 'license': 'MIT', 'n_tokens_mistral': 3613, 'n_tokens_neox': 3316, 'n_words': 1904, 'path': 'project3/project3.ipynb', 'repo_name': 'uvammm/notebooks', 'size': '13536'}