{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:42Z","timestamp":1740109302611,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["K-128611"],"award-info":[{"award-number":["K-128611"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["J4047"],"award-info":[{"award-number":["J4047"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["K-124171"],"award-info":[{"award-number":["K-124171"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2016-3\/2018"],"award-info":[{"award-number":["LP2016-3\/2018"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the following control problem on fair allocation of indivisible goods. Given a set <jats:italic>I<\/jats:italic> of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem <jats:sc>Proportionality by Item Deletion (PID)<\/jats:sc>. Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number <jats:italic>k<\/jats:italic> of item deletions allowed is small\u2014we show that the problem is <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {W}}[3]$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>W<\/mml:mi>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard with respect to the parameter <jats:italic>k<\/jats:italic>. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of |<jats:italic>I<\/jats:italic>| and <jats:italic>k<\/jats:italic>. Considering the possibilities for approximation, we prove a strong inapproximability result for PID. Finally, we also study a variant of the problem where we are given an allocation <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c0<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in advance as part of the input, and our aim is to delete a minimum number of items such that <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c0<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is proportional in the remainder; this variant turns out to be <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\mathsf {N}}}{{\\mathsf {P}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mi>P<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard for six agents, but polynomial-time solvable for two agents, and we show that it is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {W[2]}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>W<\/mml:mi>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard when parameterized by the number <jats:italic>k<\/jats:italic> of<\/jats:p>","DOI":"10.1007\/s00453-020-00794-4","type":"journal-article","created":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T06:02:43Z","timestamp":1616738563000},"page":"1559-1603","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Obtaining a Proportional Allocation by Deleting Items"],"prefix":"10.1007","volume":"83","author":[{"given":"Britta","family":"Dorn","sequence":"first","affiliation":[]},{"given":"Ronald","family":"de Haan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0114-8280","authenticated-orcid":false,"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,26]]},"reference":[{"key":"794_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity - A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"794_CR2","unstructured":"Aziz, H., Bouveret, S., Caragiannis, I., Giagkousi, I., Lang, J.: Knowledge, fairness, and social constraints. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), pages 4638\u20134645, New Orleans, Louisiana, United States, (2018)"},{"key":"794_CR3","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.artint.2015.06.002","volume":"227","author":"H Aziz","year":"2015","unstructured":"Aziz, H., Gaspers, S., Mackenzie, S., Walsh, T.: Fair assignment of indivisible objects under ordinal preferences. Artif. Intel. 227, 71\u201392 (2015)","journal-title":"Artif. Intel."},{"key":"794_CR4","unstructured":"Aziz, H., Schlotter, I., Walsh, T.: Control of fair division. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), pages 67\u201373, (2016)"},{"issue":"8\u20139","key":"794_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0895-7177(92)90085-Y","volume":"16","author":"JJ Bartholdi III","year":"1992","unstructured":"Bartholdi III, J.J., Tovey, C.A., Trick, M.A.: How hard is it to control an election? Mathemat. Comp. Modelling 16(8\u20139), 27\u201340 (1992)","journal-title":"Mathemat. Comp. Modelling"},{"key":"794_CR6","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Chevaleyre, Y., Maudet, N.: Fair allocation of indivisible goods. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, pages 284\u2013310. Cambridge University Press, (2016)","DOI":"10.1017\/CBO9781107446984.013"},{"issue":"2","key":"794_CR7","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1090\/noti1075","volume":"61","author":"SJ Brams","year":"2014","unstructured":"Brams, S.J., Kilgour, D.M., Klamler, C.: Two-person fair division of indivisible items: An efficient, envy-free algorithm. Notic. American Mathemat. Soc. 61(2), 130\u2013141 (2014)","journal-title":"Notic. American Mathemat. Soc."},{"key":"794_CR8","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Gravin, N., Huang, X.: Envy-freeness up to any item with high nash welfare: The virtue of donating items. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC 2019), page 527\u2013545, New York, NY, USA, 2019. ACM (2019)","DOI":"10.1145\/3328526.3329574"},{"issue":"8","key":"794_CR9","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comp. Sys. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Comp. Sys. Sci."},{"key":"794_CR10","unstructured":"Chen, Y., Shah, N.: Ignorance is often bliss: Envy with incomplete information, 2017. Working paper (2017)"},{"issue":"4","key":"794_CR11","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comp. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comp."},{"key":"794_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"794_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Springer, London (2013)"},{"issue":"1:2","key":"794_CR14","first-page":"1","volume":"1","author":"J Flum","year":"2005","unstructured":"Flum, J., Grohe, M.: Model-checking problems as a basis for parameterized intractability. Logic. Methods. Comp. Sci. 1(1:2), 1\u201336 (2005)","journal-title":"Logic. Methods . Comp. Sci."},{"key":"794_CR15","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science, vol. XIV. An EATCS Series. Springer Verlag, Berlin (2006)"},{"key":"794_CR16","doi-asserted-by":"crossref","unstructured":"Halpern, D., Shah, N.: Fair division with subsidy. In : D. Fotakis and E. Markakis, editors, Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT 2019), Lecture Notes in Computer Science, pp. 374\u2013389. Springer, New york (2019)","DOI":"10.1007\/978-3-030-30473-7_25"},{"issue":"4","key":"794_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2(4), 225\u2013231 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"794_CR18","doi-asserted-by":"crossref","unstructured":"Hosseini, H., Sikdar, S., Vaish, R., Wang, H., Xia, L.: Fair division through information withholding. In The 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pages 2014\u20132021. AAAI Press, (2020)","DOI":"10.1609\/aaai.v34i02.5573"},{"issue":"4","key":"794_CR19","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comp. Sys. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comp. Sys. Sci."},{"key":"794_CR20","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In EC 2004: Proc. of the 5th ACM Conference on Electronic Commerce, pages 125\u2013131, (2004)","DOI":"10.1145\/988772.988792"},{"issue":"4","key":"794_CR21","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00454-001-0047-6","volume":"26","author":"C Moore","year":"2001","unstructured":"Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discret. Comput. Geom. 26(4), 573\u2013590 (2001)","journal-title":"Discret. Comput. Geom."},{"key":"794_CR22","doi-asserted-by":"crossref","unstructured":"Nguyen, T., Vohra, R.: Near feasible stable matchings. In Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC 2015), pages 41\u201342, (2015)","DOI":"10.1145\/2764468.2764471"},{"key":"794_CR23","doi-asserted-by":"crossref","unstructured":"Pruhs, K.R., Woeginger, G.J.: Divorcing made easy. In E. Kranakis, D. Krizanc, and F. Luccio, editors, Proceedings of the 6th International conference on Fun with Algorithms (FUN 2012), volume 7288 of LNCS, pages 305\u2013314. Springer, (2012)","DOI":"10.1007\/978-3-642-30347-0_30"},{"key":"794_CR24","unstructured":"Segal-Halevi, E., Hassidim, A., Aumann, Y.: Waste makes haste: Bounded time protocols for envy-free cake cutting with free disposal. In AAMAS 2014: In Proc. of the 14th International Conference on Autonomous Agents and Multi-Agent Systems, pages 901\u2013908, (2015)"},{"key":"794_CR25","doi-asserted-by":"crossref","unstructured":"Thulasiraman, K., Arumugam, S., Brandst\u00e4dt, A., Nishizeki, T.: Handbook of Graph Theory, Combinatorial Optimization, and Algorithms. CRC Press, Chapman & Hall\/CRC Computer and Information Science Series (2015)","DOI":"10.1201\/b19163"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00794-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00794-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00794-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T12:07:34Z","timestamp":1623931654000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00794-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,26]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["794"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00794-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,3,26]]},"assertion":[{"value":"18 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original article has been corrected: Open access funding information added.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}