{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T10:58:07Z","timestamp":1781693887713,"version":"3.54.5"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T00:00:00Z","timestamp":1781654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>A college applicant submits costly applications to a set of colleges while uncertain which colleges will admit her. If she knows the application costs, her utility of attending each college, and her probability of being admitted to each college, which subset of colleges should she apply to maximize her expected net payoff? The problem is an instance of non-monotone submodular maximization. There are two principal variants in the literature, one where the events of getting into different colleges are independent, and the other where they are correlated. The main results in the literature handle cases where all application costs are the same. We provide exact and approximate algorithms for the problem when college application costs vary.<\/jats:p>","DOI":"10.1145\/3795138","type":"journal-article","created":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T20:35:42Z","timestamp":1770150942000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["College Applications with Non-Homogeneous Application Costs"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-2988-2491","authenticated-orcid":false,"given":"Eshwar","family":"Arunachaleswaran","sequence":"first","affiliation":[{"name":"Computer Science, University of Pennsylvania","place":["Philadelphia, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-3028-4198","authenticated-orcid":false,"given":"Sampath","family":"Kannan","sequence":"additional","affiliation":[{"name":"Computer Science, University of Pennsylvania","place":["Philadelphia, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1049-0827","authenticated-orcid":false,"given":"Rakesh","family":"Vohra","sequence":"additional","affiliation":[{"name":"Economics, University of Pennsylvania","place":["Philadelphia, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,17]]},"reference":[{"key":"e_1_3_4_2_2","volume-title":"An Empirical Analysis of School Choice Under Uncertainty","author":"Ajayi Kehinde F.","year":"2015","unstructured":"Kehinde F. Ajayi and Modibo Sidib\u00e9. 2015. An Empirical Analysis of School Choice Under Uncertainty. Technical Report."},{"key":"e_1_3_4_3_2","volume-title":"The College Portfolio Problem","author":"Ali S. Nageeb","year":"2021","unstructured":"S. Nageeb Ali and Ran I. Shorrer. 2021. The College Portfolio Problem. Technical Report. Pennsylvania State University."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"issue":"3","key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1093\/restud\/rdu003","article-title":"Student portfolios and the college admissions problem","volume":"81","author":"Chade Hector","year":"2013","unstructured":"Hector Chade, Gregory Lewis, and Lones Smith. 2013. Student portfolios and the college admissions problem. Review of Economic Studies 81, 3 (2013), 971\u20131002.","journal-title":"Review of Economic Studies"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2006.00705.x"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9646-2"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1086\/675503"},{"issue":"1","key":"e_1_3_4_9_2","first-page":"20","article-title":"How to probe for an extreme value","volume":"7","author":"Goel Ashish","year":"2010","unstructured":"Ashish Goel, Sudipto Guha, and Kamesh Munagala. 2010. How to probe for an extreme value. ACM Trans. Algorithms 7, 1 (2010), 20 pages.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_4_10_2","first-page":"2634","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Harshaw Chris","year":"2019","unstructured":"Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. 2019. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In Proceedings of the International Conference on Machine Learning. PMLR, 2634\u20132643."},{"key":"e_1_3_4_11_2","volume-title":"Integrating New York City Schools: The Role of Admission Criteria and Family Preferences","author":"Idoux Clemence","year":"2022","unstructured":"Clemence Idoux. 2022. Integrating New York City Schools: The Role of Admission Criteria and Family Preferences. Technical Report."},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467866"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","unstructured":"Max Kapur and Sung-Pil Hong. 2022. The college application problem. In 2022 IEEE 61st Conference on Decision and Control (CDC). IEEE 5555\u20135561. DOI:10.1109\/CDC51059.2022.9993175","DOI":"10.1109\/CDC51059.2022.9993175"},{"key":"e_1_3_4_14_2","volume-title":"Dynamic College Admissions and the Determinants of Students\u2019 College Retention","author":"Larroucau Tom\u00e1s","year":"2020","unstructured":"Tom\u00e1s Larroucau and Ignacio Rios. 2020. Dynamic College Admissions and the Determinants of Students\u2019 College Retention. Technical Report."},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2017.10.016"},{"key":"e_1_3_4_16_2","first-page":"15800","volume-title":"Proceedings of the Advances in Neural Information Processing Systems.","volume":"33","author":"Mehta Aranyak","year":"2020","unstructured":"Aranyak Mehta, Uri Nadav, Alexandros Psomas, and Aviad Rubinstein. 2020. Hitting the high notes: Subset selection for maximizing expected order statistics. In Proceedings of the Advances in Neural Information Processing Systems.H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33, Curran Associates, Inc., 15800\u201315810."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.07.010"},{"issue":"4","key":"e_1_3_4_18_2","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1007\/s00199-001-0248-5","article-title":"Verifying gross substitutability","volume":"20","author":"Reijnierse Hans","year":"2002","unstructured":"Hans Reijnierse, Anita van Gellekom, and Jos AM Potters. 2002. Verifying gross substitutability. Economic Theory 20, 4 (2002), 767\u2013776.","journal-title":"Economic Theory"},{"key":"e_1_3_4_19_2","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/3328526.3329599","volume-title":"Proceedings of the 2019 ACM Conference on Economics and Computation","author":"Shorrer Ran I.","year":"2019","unstructured":"Ran I. Shorrer. 2019. Simultaneous search: Beyond independent successes. In Proceedings of the 2019 ACM Conference on Economics and Computation (Phoenix, AZ, USA). Association for Computing Machinery, New York, NY, USA, 347\u2013348."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3795138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T10:44:55Z","timestamp":1781693095000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3795138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,17]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3795138"],"URL":"https:\/\/doi.org\/10.1145\/3795138","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,17]]},"assertion":[{"value":"2025-01-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}