乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,21]],"date-time":"2023-01-21T05:48:19Z","timestamp":1674280099859},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T00:00:00Z","timestamp":1640217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T00:00:00Z","timestamp":1640217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NTNU Norwegian University of Science and Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2022,4]]},"abstract":"Abstract<\/jats:title>We study fair allocation of indivisible items, where the items are furnished with a set ofconflicts<\/jats:italic>, and agents are not permitted to receive conflicting items. This kind of constraint captures, for example, participating in events that overlap in time, or taking on roles in the presence of conflicting interests. We demonstrate, both theoretically and experimentally, that fairness characterizations such as EF1, MMS and MNW still are applicable and useful under item conflicts. Among other existence, non-existence and computability results, we show that a

$$1\/\\Delta $$<\/jats:tex-math>1<\/mml:mn>\/<\/mml:mo>\u0394<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate MMS allocation forn<\/jats:italic>agents may be found in polynomial time when

$$n>\\Delta >2$$<\/jats:tex-math>n<\/mml:mi>><\/mml:mo>\u0394<\/mml:mi>><\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for any conflict graph with maximum degree

$$\\Delta$$<\/jats:tex-math>\u0394<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and that, if

$$n > \\Delta $$<\/jats:tex-math>n<\/mml:mi>><\/mml:mo>\u0394<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, a 1\/3-approximate MMS allocation always exists.<\/jats:p>","DOI":"10.1007\/s10458-021-09537-3","type":"journal-article","created":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T08:13:21Z","timestamp":1640247201000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fair allocation of conflicting items"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-5691-8177","authenticated-orcid":false,"given":"Halvard","family":"Hummel","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0003-4204-2017","authenticated-orcid":false,"given":"Magnus Lie","family":"Hetland","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,23]]},"reference":[{"issue":"1","key":"9537_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., & Barab\u00e1si, A. L. (2002). Statistical mechanics of complex networks. Reviews of modern physics, 74(1), 47.","journal-title":"Reviews of modern physics"},{"issue":"4","key":"9537_CR2","doi-asserted-by":"publisher","first-page":"52:1","DOI":"10.1145\/3147173","volume":"13","author":"G Amanatidis","year":"2017","unstructured":"Amanatidis, G., Markakis, E., Nikzad, A., & Saberi, A. (2017). Approximation Algorithms for Computing Maximin Share Allocations. ACM Transactions on Algorithms, 13(4), 52:1-52:28. https:\/\/doi.org\/10.1145\/3147173.","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"9537_CR3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/141000671","volume":"59","author":"J Bezanson","year":"2017","unstructured":"Bezanson, J., Edelman, A., Karpinski, S., & Shah, V. B. (2017). Julia: A fresh approach to numerical computing. SIAM review, 59(1), 65\u201398. https:\/\/doi.org\/10.1137\/141000671","journal-title":"SIAM review"},{"key":"9537_CR4","doi-asserted-by":"crossref","unstructured":"Biswas, A., & Barman, S. (2018). Fair division under cardinality constraints. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, pp 91\u201397","DOI":"10.24963\/ijcai.2018\/13"},{"key":"9537_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs (2nd ed.). Cambridge University Press.","edition":"2"},{"issue":"2","key":"9537_CR6","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s10458-015-9287-3","volume":"30","author":"S Bouveret","year":"2016","unstructured":"Bouveret, S., & Lema\u00eetre, M. (2016). Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, 30(2), 259\u2013290. https:\/\/doi.org\/10.1007\/s10458-015-9287-3","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"9537_CR7","doi-asserted-by":"publisher","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A., & Peters, D. (2017). Fair division of a graph. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, Melbourne, Australia, pp 135\u2013141, https:\/\/doi.org\/10.24963\/ijcai.2017\/20","DOI":"10.24963\/ijcai.2017\/20"},{"key":"9537_CR8","doi-asserted-by":"crossref","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A.D. (eds) (2016). Handbook of computational social choice. Cambridge University Press","DOI":"10.1017\/CBO9781107446984.002"},{"key":"9537_CR9","doi-asserted-by":"publisher","unstructured":"Bromberger, S., & Fairbanks, J. et\u00a0al. (2017). JuliaGraphs\/LightGraphs.jl: LightGraphs. https:\/\/doi.org\/10.5281\/zenodo.889971,","DOI":"10.5281\/zenodo.889971"},{"key":"9537_CR10","doi-asserted-by":"publisher","unstructured":"Brooks, R. L. (1941). On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2), 194\u2013197. https:\/\/doi.org\/10.1017\/S030500410002168X, publisher: Cambridge University Press","DOI":"10.1017\/S030500410002168X"},{"key":"9537_CR11","doi-asserted-by":"publisher","unstructured":"Budish, E. (2011). The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6), 1061\u20131103. https:\/\/doi.org\/10.1086\/664613, publisher: The University of Chicago Press","DOI":"10.1086\/664613"},{"issue":"3","key":"9537_CR12","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/3355902","volume":"7","author":"I Caragiannis","year":"2019","unstructured":"Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., & Wang, J. (2019). The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3), 12:1-12:32.","journal-title":"ACM Transactions on Economics and Computation"},{"key":"9537_CR13","doi-asserted-by":"publisher","unstructured":"Chiarelli, N., Krnc, M., Milani\u010d, M., Pferschy, U., Piva\u010d, N., & Schauer, J. (2020). Fair packing of independent sets. In: Combinatorial Algorithms, Springer International Publishing, Cham, Lecture Notes in Computer Science, pp 154\u2013165, https:\/\/doi.org\/10.1007\/978-3-030-48966-3_12","DOI":"10.1007\/978-3-030-48966-3_12"},{"issue":"2","key":"9537_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1137\/15M1020575","volume":"59","author":"I Dunning","year":"2017","unstructured":"Dunning, I., Huchette, J., & Lubin, M. (2017). Jump: A modeling language for mathematical optimization. SIAM Review, 59(2), 295\u2013320. https:\/\/doi.org\/10.1137\/15M1020575","journal-title":"SIAM Review"},{"key":"9537_CR15","doi-asserted-by":"publisher","unstructured":"Garg, J., & Taki, S. (2020). An Improved Approximation Algorithm for Maximin Shares. In: Proceedings of the 21st ACM Conference on Economics and Computation, Association for Computing Machinery, New York, NY, USA, EC \u201920, pp 379\u2013380, https:\/\/doi.org\/10.1145\/3391403.3399526","DOI":"10.1145\/3391403.3399526"},{"key":"9537_CR16","doi-asserted-by":"publisher","unstructured":"Garg, J., McGlaughlin, P., & Taki, S. (2018). Approximating Maximin Share Allocations. In: Fineman JT, Mitzenmacher M (eds) 2nd Symposium on Simplicity in Algorithms (SOSA 2019), Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, OpenAccess Series in Informatics (OASIcs), vol\u00a069, pp 20:1\u201320:11, https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.20","DOI":"10.4230\/OASIcs.SOSA.2019.20"},{"key":"9537_CR17","doi-asserted-by":"publisher","unstructured":"Ghodsi, M., Hajiaghayi, M., Seddighin, M., Seddighin, S., & Yami, H. (2018). Fair allocation of indivisible goods: Improvements and generalizations. In: Proceedings of the 2018 ACM Conference on Economics and Computation, Association for Computing Machinery, EC \u201918, pp 539\u2013556, https:\/\/doi.org\/10.1145\/3219166.3219238","DOI":"10.1145\/3219166.3219238"},{"key":"9537_CR18","doi-asserted-by":"publisher","unstructured":"Gourv\u00e8s, L., Monnot, J., & Tlilane, L. (2013). A Protocol for Cutting Matroids Like Cakes. In: Chen Y, Immorlica N (eds) Web and Internet Economics, Springer, Berlin, Heidelberg, Lecture Notes in Computer Science, pp 216\u2013229, https:\/\/doi.org\/10.1007\/978-3-642-45046-4_18","DOI":"10.1007\/978-3-642-45046-4_18"},{"key":"9537_CR19","unstructured":"Gurobi Optimization L (2021). Gurobi optimizer reference manual. http:\/\/www.gurobi.com"},{"key":"9537_CR20","doi-asserted-by":"publisher","unstructured":"Halldorsson, M. M., & Lau, H. C. (1997). Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring. Journal of Graph Algorithms and Applications, 1(3), 1\u201313. https:\/\/doi.org\/10.7155\/jgaa.00003, https:\/\/ink.library.smu.edu.sg\/sis_research\/173","DOI":"10.7155\/jgaa.00003"},{"issue":"2","key":"9537_CR21","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1017\/S0963548307008619","volume":"17","author":"HA Kierstead","year":"2008","unstructured":"Kierstead, H. A., & Kostochka, A. V. (2008). A short proof of the Hajnal-Szemer\u00e9di theorem on equitable colouring. Combinatorics, Probability and Computing, 17(2), 265\u2013270. https:\/\/doi.org\/10.1017\/S0963548307008619","journal-title":"Combinatorics, Probability and Computing"},{"issue":"3","key":"9537_CR22","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/jgt.10137","volume":"44","author":"AV Kostochka","year":"2003","unstructured":"Kostochka, A. V., Pelsmajer, M. J., & West, D. B. (2003). A list analogue of equitable coloring. Journal of Graph Theory, 44(3), 166\u2013177. https:\/\/doi.org\/10.1002\/jgt.10137","journal-title":"Journal of Graph Theory"},{"key":"9537_CR23","doi-asserted-by":"crossref","unstructured":"Kurokawa, D., Procaccia, A.D., & Wang, J. (2016). When can the maximin share guarantee be guaranteed? In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press, Phoenix, Arizona, AAAI\u201916, pp 523\u2013529","DOI":"10.1609\/aaai.v30i1.10041"},{"key":"9537_CR24","unstructured":"Lewis, RMR. (2016). A Guide to Graph Coloring. Springer International Publishing"},{"key":"9537_CR25","doi-asserted-by":"publisher","unstructured":"Lih, K.W. (2013). Equitable coloring of graphs. In: Pardalos PM, Du DZ, Graham RL (eds) Handbook of Combinatorial Optimization, Springer, New York, NY, pp 1199\u20131248, https:\/\/doi.org\/10.1007\/978-1-4419-7997-1_25","DOI":"10.1007\/978-1-4419-7997-1_25"},{"key":"9537_CR26","doi-asserted-by":"publisher","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM conference on Electronic commerce, Association for Computing Machinery, New York, NY, USA, EC \u201904, pp 125\u2013131, https:\/\/doi.org\/10.1145\/988772.988792","DOI":"10.1145\/988772.988792"},{"issue":"3","key":"9537_CR27","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L. (1975). Three short proofs in graph theory. Journal of Combinatorial Theory, Series B, 19(3), 269\u2013271. https:\/\/doi.org\/10.1016\/0095-8956(75)90089-1","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"9537_CR28","doi-asserted-by":"publisher","first-page":"1505","DOI":"10.1137\/19M1279125","volume":"34","author":"P Manurangsi","year":"2018","unstructured":"Manurangsi, P., & Suksompong, W. (2018). When Do Envy-Free Allocations Exist? SIAM Journal on Discrete Mathematics, 34(3), 1505\u20131521. https:\/\/doi.org\/10.1137\/19M1279125","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"3","key":"9537_CR29","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G. J. (1980). On maximal independent sets of vertices in claw-free graphs. Journal of Combinatorial Theory, Series B, 28(3), 284\u2013304. https:\/\/doi.org\/10.1016\/0095-8956(80)90074-X","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9537_CR30","doi-asserted-by":"publisher","unstructured":"Pemmaraju, S., & Srinivasan, A. (2008). The randomized coloring procedure with symmetry-breaking. In: Aceto L, Damg\u00e5rd I, Goldberg LA, Halld\u00f3rsson MM, Ing\u00f3lfsd\u00f3ttir A, Walukiewicz I (eds) Automata, Languages and Programming, Springer, Berlin, Heidelberg, Lecture Notes in Computer Science, pp 306\u2013319, https:\/\/doi.org\/10.1007\/978-3-540-70575-8_26","DOI":"10.1007\/978-3-540-70575-8_26"},{"issue":"1","key":"9537_CR31","first-page":"101","volume":"16","author":"H Steinhaus","year":"1948","unstructured":"Steinhaus, H. (1948). The problem of fair division. Econometrica, 16(1), 101\u2013104.","journal-title":"Econometrica"},{"issue":"6684","key":"9537_CR32","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of \u2018small-world\u2019 networks. Nature, 393(6684), 440\u2013442.","journal-title":"Nature"},{"issue":"4","key":"9537_CR33","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0167-6377(96)00055-7","volume":"20","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G. J. (1997). A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4), 149\u2013154. https:\/\/doi.org\/10.1016\/S0167-6377(96)00055-7","journal-title":"Operations Research Letters"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-021-09537-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-021-09537-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-021-09537-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T04:48:09Z","timestamp":1674190089000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-021-09537-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,23]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["9537"],"URL":"https:\/\/doi.org\/10.1007\/s10458-021-09537-3","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,23]]},"assertion":[{"value":"18 November 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"8"}}