Brief Summary: This randomized phase II trial studies how well nivolumab with or without ipilimumab or relatlimab before surgery works in treating patients with stage IIIB-IV melanoma that can be removed by surgery. Immunotherapy with monoclonal antibodies, such as nivolumab, ipilimumab, and relatlimab, may help the body's immune system attack the cancer, and may interfere with the ability of tumor cells to grow and spread. Giving nivolumab alone or in combination with ipilimumab or relatlimab before surgery may make the tumor smaller and reduce the amount of normal tissue that needs to be removed.

Detailed Description: PRIMARY OBJECTIVES: I. To assess the pathologic response of nivolumab monotherapy and nivolumab and ipilimumab dual therapy administered in the neoadjuvant setting in patients with high-risk resectable melanoma. Pathologic response will be assessed by percent viable tumor cells, percent tumor necrosis, presence of fibrosis and melanoma proliferation as assessed by phosphohistone H3 from baseline, to on-treatment and surgical specimens. (Arm A and Arm B) II. To assess the pathologic response rate of combination relatlimab with nivolumab in the neoadjuvant setting in patients with high-risk resectable Stage IIIB/C or oligometastatic Stage IV melanoma. Pathologic response will be assessed by percent viable tumor cells, percent tumor necrosis, presence of fibrosis and melanoma proliferation as assessed by phosphohistone H3 from baseline, to on- treatment and surgical specimens. (Arm C) SECONDARY OBJECTIVES: I. To assess the immunologic response of neoadjuvant nivolumab monotherapy and neoadjuvant nivolumab and ipilimumab dual therapy in patients with high-risk resectable melanoma. Immunologic response will be determined by change in T cell infiltrate from baseline to on-treatment and surgical specimens in response to therapy. (Arm A and Arm B) II. To assess the objective response rate (ORR) of nivolumab monotherapy and nivolumab and ipilimumab dual therapy administered in the neoadjuvant setting as assessed by imaging (Response Evaluation Criteria in Solid Tumors \[RECIST\] 1.1 criteria) in patients with high-risk resectable melanoma. (Arm A and Arm B) III. To assess the 12-month recurrence-free survival (RFS) and overall survival (OS) of patients with high-risk resectable melanoma treated with neoadjuvant nivolumab monotherapy or nivolumab and ipilimumab dual therapy followed by adjuvant nivolumab. (Arm A and Arm B) IV. To evaluate the safety of nivolumab monotherapy and dual ipilimumab and nivolumab in the neoadjuvant setting and peri-operatively as well as assess the safety of adjuvant nivolumab. (Arm A and Arm B) V. To evaluate safety and feasibility of relatlimab with nivolumab delivered in the neoadjuvant setting. (Arm C) VI. To assess the objective response rate (ORR) of relatlimab with nivolumab administered in the neoadjuvant setting as assessed by imaging (RECIST 1.1 criteria) in patients with high-risk resectable melanoma. (Arm C) VII. To assess the 12-month recurrence-free survival (RFS) and overall survival (OS) of patients with high-risk resectable melanoma treated with neoadjuvant and adjuvant relatlimab with nivolumab. (Arm C) VIII. To evaluate immunologic and molecular mechanisms of response and resistance to relatlimab with nivolumab. (Arm C) EXPLORATORY OBJECTIVES: I. Identification of immunologic and genomic markers correlating with clinical response or resistance to nivolumab monotherapy and ipilimumab with nivolumab combination therapy. OUTLINE: Patients are randomized to 1 of 3 arms. ARM A: Patients receive nivolumab intravenously (IV) over 30 minutes on days 1, 15, 29, and 43. Patients then undergo surgery on day 57. After surgery, patients receive nivolumab IV over 30 minutes every 2 weeks for 13 doses in the absence of disease progression or unacceptable toxicity. (CLOSED TO ENROLLMENT AS OF 10/3/2018) ARM B: Patients receive nivolumab IV over 1 hour and ipilimumab IV over 90 minutes on days 1, 22, and 43. Patients then undergo surgery on day 57. After surgery, patients receive nivolumab IV over 30 minutes every 2 weeks for 13 doses in the absence of disease progression or unacceptable toxicity. (CLOSED TO ENROLLMENT AS OF 10/3/2018) ARM C: Patients receive nivolumab IV over 1 hour and relatlimab IV over 1 hour on days 1 and 29. Patients then undergo surgery on day 57. After surgery, patients receive nivolumab IV over 1 hour and relatlimab IV over 1 hour every 4 weeks for 10 doses in the absence of disease progression or unacceptable toxicity. After completion of study treatment, patients are followed up every 12 weeks for 2 years.