{"authors":[{"id":null,"fullName":"Xiaowei Wu 0001","name":null,"surname":null,"rank":1,"pid":null},{"id":"orcid_______::496bdc74ee541a2ec38a0c020f361d2c","fullName":"Bo Li 0037","name":null,"surname":null,"rank":2,"pid":{"id":{"scheme":"orcid","value":"0000-0001-7500-8355"},"provenance":null}},{"id":null,"fullName":"Jiarui Gan","name":null,"surname":null,"rank":3,"pid":null}],"openAccessColor":"bronze","publiclyFunded":false,"eoscIfGuidelines":null,"type":"publication","language":{"code":"und","label":"Undetermined"},"countries":[{"code":"GB","label":"United Kingdom","provenance":null}],"subjects":[{"subject":{"scheme":"FOS","value":"0202 electrical engineering, electronic engineering, information engineering"},"provenance":null},{"subject":{"scheme":"SDG","value":"1. No poverty"},"provenance":null},{"subject":{"scheme":"FOS","value":"02 engineering and technology"},"provenance":null},{"subject":{"scheme":"FOS","value":"0102 computer and information sciences"},"provenance":null},{"subject":{"scheme":"SDG","value":"10. No inequality"},"provenance":null},{"subject":{"scheme":"FOS","value":"01 natural sciences"},"provenance":null}],"mainTitle":"Budget-feasible Maximum Nash Social Welfare is Almost Envy-free","subTitle":null,"descriptions":["<jats:p>The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.</jats:p>"],"publicationDate":"2021-08-01","publisher":"International Joint Conferences on Artificial Intelligence Organization","embargoEndDate":null,"sources":["Crossref"],"formats":null,"contributors":null,"coverages":null,"bestAccessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/"},"container":{"name":"Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence","issnPrinted":null,"issnOnline":null,"issnLinking":null,"ep":"471","iss":null,"sp":"465","vol":null,"edition":null,"conferencePlace":null,"conferenceDate":null},"documentationUrls":null,"codeRepositoryUrl":null,"programmingLanguage":null,"contactPeople":null,"contactGroups":null,"tools":null,"size":null,"version":null,"geoLocations":null,"id":"doi_dedup___::a5508488fc64e96acef6c52ca896c4d0","originalIds":["10.24963/ijcai.2021/65","50|doiboost____|a5508488fc64e96acef6c52ca896c4d0","50|dblp________::c38eb25c05fcccb7c5fab7c5300749a5","3189849428","oai:ora.ox.ac.uk:uuid:6099c717-0c4d-433e-8c7d-f7cfa2b896d5","50|od______1064::4d6786258be7b20109564bad1c6d42bd"],"pids":[{"scheme":"doi","value":"10.24963/ijcai.2021/65"}],"dateOfCollection":null,"lastUpdateTimeStamp":null,"indicators":{"citationImpact":{"citationCount":11.0,"influence":2.777486E-9,"popularity":8.534193E-9,"impulse":6.0,"citationClass":"C4","influenceClass":"C4","impulseClass":"C4","popularityClass":"C4"}},"projects":[{"id":"corda__h2020::83d6aa753c4b6e94582f4ef733616892","code":"945719","acronym":"HumanML","title":"Human-Centric Machine Learning","funder":"European Commission","pids":[{"scheme":"doi","value":"10.3030/945719"}]}],"organizations":[{"legalName":"Max Planck Society","acronym":"MPG","id":"openorgs____::5a405a89387d1881afa956f475994e10","pids":[{"scheme":"ISNI","value":"0000000121051091"},{"scheme":"ROR","value":"https://ror.org/01hhn8329"},{"scheme":"GRID","value":"grid.4372.2"},{"scheme":"PIC","value":"999990267"},{"scheme":"RRID","value":"RRID:nlx_55250"},{"scheme":"FundRef","value":"501100004189"},{"scheme":"RRID","value":"RRID:SCR_011366"},{"scheme":"Wikidata","value":"Q158085"},{"scheme":"OrgRef","value":"614753"},{"scheme":"mag_id","value":"149899117"},{"scheme":"wikidata","value":"Q158085"},{"scheme":"fundref","value":"501100004189"}],"countries":[{"code":"DE","label":"Germany"}],"websiteurl":"http://www.mpg.de/en"},{"legalName":"University of Macau","acronym":"University of Macau","id":"pending_org_::fe48fd3712fd63e5eedcdf208e666cea","pids":null,"countries":[{"code":"UNKNOWN","label":"Unknown"}],"websiteurl":null},{"legalName":"University of Macau","acronym":"University of Macau","id":"pending_org_::bbc264c46abb28ae560343ea462ad06e","pids":null,"countries":[{"code":"UNKNOWN","label":"Unknown"}],"websiteurl":null},{"legalName":"University of Macau","acronym":"UM","id":"openorgs____::86b0e38fc825bd757aa2345ec66e4a8f","pids":[{"scheme":"ROR","value":"https://ror.org/01r4q9n85"},{"scheme":"OrgRef","value":"919926"},{"scheme":"mag_id","value":"204512498"},{"scheme":"Wikidata","value":"Q1563050"},{"scheme":"wikidata","value":"Q1563050"},{"scheme":"GRID","value":"grid.437123.0"},{"scheme":"fundref","value":"501100004733"},{"scheme":"FundRef","value":"501100004733"},{"scheme":"ISNI","value":"0000000417948068"}],"countries":[{"code":"MO","label":"Macao"}],"websiteurl":"http://www.umac.mo/"},{"legalName":"Max Planck Institute for Software Systems","acronym":"MPI-SWS","id":"openorgs____::a6be3b23fdb0e61554b444ec8c1e8d1c","pids":[{"scheme":"Wikidata","value":"Q881238"},{"scheme":"GRID","value":"grid.469860.5"},{"scheme":"ISNI","value":"000000040492020X"},{"scheme":"ROR","value":"https://ror.org/02pe2kf23"},{"scheme":"wikidata","value":"Q881238"}],"countries":[{"code":"DE","label":"Germany"}],"websiteurl":"https://www.mpi-sws.org/index.php"},{"legalName":"University of Oxford","acronym":"University of Oxford","id":"openorgs____::6a7b1b4c40a067a1f209de6867fe094d","pids":[{"scheme":"OrgRef","value":"48518"},{"scheme":"FundRef","value":"100010354"},{"scheme":"wikidata","value":"Q6786826"},{"scheme":"fundref","value":"501100021079"},{"scheme":"FundRef","value":"100010350"},{"scheme":"FundRef","value":"100010359"},{"scheme":"OrgRef","value":"53554"},{"scheme":"OrgRef","value":"128294"},{"scheme":"fundref","value":"501100022752"},{"scheme":"OrgRef","value":"128380"},{"scheme":"FundRef","value":"100010369"},{"scheme":"Wikidata","value":"Q34433"},{"scheme":"FundRef","value":"100010349"},{"scheme":"fundref","value":"501100000649"},{"scheme":"fundref","value":"100010352"},{"scheme":"wikidata","value":"Q56612600"},{"scheme":"fundref","value":"501100000645"},{"scheme":"FundRef","value":"100010353"},{"scheme":"fundref","value":"100010361"},{"scheme":"fundref","value":"100010368"},{"scheme":"UKPRN","value":"10007774"},{"scheme":"fundref","value":"501100000734"},{"scheme":"FundRef","value":"501100022752"},{"scheme":"OrgRef","value":"128345"},{"scheme":"FundRef","value":"501100021079"},{"scheme":"OrgRef","value":"31797"},{"scheme":"fundref","value":"501100000747"},{"scheme":"fundref","value":"501100000744"},{"scheme":"fundref","value":"100010369"},{"scheme":"FundRef","value":"100007718"},{"scheme":"OrgRef","value":"128351"},{"scheme":"OrgRef","value":"128373"},{"scheme":"OrgRef","value":"128300"},{"scheme":"fundref","value":"100010354"},{"scheme":"FundRef","value":"100010362"},{"scheme":"FundRef","value":"501100001622"},{"scheme":"FundRef","value":"100010355"},{"scheme":"FundRef","value":"501100013389"},{"scheme":"fundref","value":"100010349"},{"scheme":"wikidata","value":"Q1095537"},{"scheme":"fundref","value":"100010371"},{"scheme":"FundRef","value":"501100014748"},{"scheme":"OrgRef","value":"128381"},{"scheme":"UCAS","value":"O33"},{"scheme":"FundRef","value":"501100006558"},{"scheme":"OrgReg","value":"UK0090"},{"scheme":"fundref","value":"501100000696"},{"scheme":"FundRef","value":"501100000747"},{"scheme":"FundRef","value":"100010364"},{"scheme":"wikidata","value":"Q5260389"},{"scheme":"fundref","value":"501100006561"},{"scheme":"fundref","value":"100010367"},{"scheme":"OrgRef","value":"128378"},{"scheme":"fundref","value":"501100001622"},{"scheme":"OrgRef","value":"9491409"},{"scheme":"fundref","value":"100010348"},{"scheme":"OrgRef","value":"128383"},{"scheme":"fundref","value":"100010353"},{"scheme":"FundRef","value":"100010356"},{"scheme":"fundref","value":"100010359"},{"scheme":"FundRef","value":"100010367"},{"scheme":"OrgRef","value":"128382"},{"scheme":"wikidata","value":"Q34433"},{"scheme":"fundref","value":"501100023929"},{"scheme":"OrgRef","value":"128375"},{"scheme":"FundRef","value":"501100000718"},{"scheme":"FundRef","value":"501100000769"},{"scheme":"fundref","value":"100010355"},{"scheme":"fundref","value":"100010357"},{"scheme":"OrgRef","value":"128374"},{"scheme":"fundref","value":"100010347"},{"scheme":"FundRef","value":"501100000696"},{"scheme":"OrgRef","value":"128390"},{"scheme":"fundref","value":"100010364"},{"scheme":"Wikidata","value":"Q6786826"},{"scheme":"FundRef","value":"501100000645"},{"scheme":"FundRef","value":"501100015505"},{"scheme":"FundRef","value":"501100000524"},{"scheme":"fundref","value":"501100000524"},{"scheme":"fundref","value":"501100000666"},{"scheme":"OrgRef","value":"128385"},{"scheme":"FundRef","value":"501100023929"},{"scheme":"OrgRef","value":"128357"},{"scheme":"fundref","value":"100007724"},{"scheme":"fundref","value":"100010350"},{"scheme":"OrgRef","value":"128362"},{"scheme":"FundRef","value":"501100000734"},{"scheme":"FundRef","value":"100010352"},{"scheme":"fundref","value":"501100000719"},{"scheme":"GRID","value":"grid.4991.5"},{"scheme":"fundref","value":"501100000728"},{"scheme":"Wikidata","value":"Q7529574"},{"scheme":"fundref","value":"501100000718"},{"scheme":"FundRef","value":"100010361"},{"scheme":"FundRef","value":"100010360"},{"scheme":"fundref","value":"501100014748"},{"scheme":"FundRef","value":"100010351"},{"scheme":"fundref","value":"100010360"},{"scheme":"OrgRef","value":"128099"},{"scheme":"FundRef","value":"501100004789"},{"scheme":"Wikidata","value":"Q5260389"},{"scheme":"FundRef","value":"100010366"},{"scheme":"FundRef","value":"100010348"},{"scheme":"wikidata","value":"Q7529574"},{"scheme":"fundref","value":"501100004211"},{"scheme":"FundRef","value":"501100006561"},{"scheme":"fundref","value":"501100004789"},{"scheme":"OrgRef","value":"128349"},{"scheme":"FundRef","value":"100010357"},{"scheme":"mag_id","value":"40120149"},{"scheme":"Wikidata","value":"Q56612600"},{"scheme":"FundRef","value":"501100000719"},{"scheme":"ISNI","value":"0000000419368948"},{"scheme":"fundref","value":"100010366"},{"scheme":"FundRef","value":"501100000649"},{"scheme":"fundref","value":"100013964"},{"scheme":"FundRef","value":"501100004211"},{"scheme":"HESA","value":"0156"},{"scheme":"OrgRef","value":"128346"},{"scheme":"FundRef","value":"100010358"},{"scheme":"FundRef","value":"100010370"},{"scheme":"fundref","value":"100010363"},{"scheme":"FundRef","value":"100010365"},{"scheme":"fundref","value":"100010358"},{"scheme":"FundRef","value":"100010347"},{"scheme":"fundref","value":"501100000769"},{"scheme":"FundRef","value":"100013964"},{"scheme":"FundRef","value":"100007724"},{"scheme":"fundref","value":"100010370"},{"scheme":"Wikidata","value":"Q1095537"},{"scheme":"FundRef","value":"100010368"},{"scheme":"fundref","value":"100007718"},{"scheme":"OrgRef","value":"128284"},{"scheme":"fundref","value":"100010362"},{"scheme":"ROR","value":"https://ror.org/052gg0110"},{"scheme":"RRID","value":"RRID:SCR_006361"},{"scheme":"fundref","value":"100010365"},{"scheme":"FundRef","value":"501100000728"},{"scheme":"fundref","value":"501100015505"},{"scheme":"fundref","value":"100010351"},{"scheme":"FundRef","value":"501100000744"},{"scheme":"OrgRef","value":"128344"},{"scheme":"fundref","value":"100010356"},{"scheme":"FundRef","value":"100010363"},{"scheme":"FundRef","value":"100010371"},{"scheme":"fundref","value":"501100006558"},{"scheme":"FundRef","value":"501100000666"},{"scheme":"fundref","value":"501100013389"},{"scheme":"OrgRef","value":"128386"}],"countries":[{"code":"GB","label":"United Kingdom"}],"websiteurl":"http://www.ox.ac.uk/"},{"legalName":"Hong Kong Polytechnic University","acronym":"HKPU","id":"openorgs____::5f8471cfd1554660ddb736792f1ab7f8","pids":[{"scheme":"OrgRef","value":"23757778"},{"scheme":"OrgRef","value":"268987"},{"scheme":"OrgRef","value":"268078"},{"scheme":"Wikidata","value":"Q1333303"},{"scheme":"FundRef","value":"501100006066"},{"scheme":"fundref","value":"501100004377"},{"scheme":"FundRef","value":"501100011650"},{"scheme":"fundref","value":"501100011650"},{"scheme":"wikidata","value":"Q1187271"},{"scheme":"ROR","value":"https://ror.org/00q4vv597"},{"scheme":"GRID","value":"grid.24515.37"},{"scheme":"fundref","value":"501100022174"},{"scheme":"PIC","value":"999463169"},{"scheme":"fundref","value":"501100006066"},{"scheme":"GRID","value":"grid.16890.36"},{"scheme":"wikidata","value":"Q99229082"},{"scheme":"FundRef","value":"501100004377"},{"scheme":"fundref","value":"501100014819"},{"scheme":"ROR","value":"https://ror.org/0030zas98"},{"scheme":"ISNI","value":"0000000417646123"},{"scheme":"PIC","value":"997262918"},{"scheme":"FundRef","value":"501100022174"},{"scheme":"ISNI","value":"0000000484971137"},{"scheme":"mag_id","value":"200769079"},{"scheme":"ROR","value":"https://ror.org/050h0vm43"},{"scheme":"ISNI","value":"0000000419371450"},{"scheme":"FundRef","value":"501100014819"},{"scheme":"PIC","value":"886266012"},{"scheme":"Wikidata","value":"Q1187271"},{"scheme":"mag_id","value":"14243506"},{"scheme":"wikidata","value":"Q1333303"},{"scheme":"FundRef","value":"501100005950"},{"scheme":"fundref","value":"501100005950"}],"countries":[{"code":"CN","label":"China (People's Republic of)"}],"websiteurl":"http://www.polyu.edu.hk/web/en/home/index.html"},{"legalName":"University of Macau","acronym":"澳門大學 (Universidade de Macau)","id":"pending_org_::8146491ee5bba5d8dbf9c059b7e7cc02","pids":null,"countries":[{"code":"CN","label":"China (People's Republic of)"}],"websiteurl":"http://www.umac.mo/"},{"legalName":"The Hong Kong Polytechnique University","acronym":"The Hong Kong Polytechnique University","id":"pending_org_::50cce90f881bc1b9193c871de9fb734b","pids":null,"countries":[{"code":"HK","label":"Hong Kong"}],"websiteurl":null}],"communities":[{"code":"uarctic","label":"UArctic","provenance":null}],"collectedFrom":[{"key":"openaire____::8ac8380272269217cb09a928c8caa993","value":"UnpayWall"},{"key":"opendoar____::2290a7385ed77cc5592dc2153229f082","value":"Oxford University Research Archive"},{"key":"openaire____::081b82f96300b6a6e3d282bad31cb6e2","value":"Crossref"},{"key":"openaire____::5f532a3fc4f1ea403f37070f59a7a53a","value":"Microsoft Academic Graph"},{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}],"instances":[{"pids":[{"scheme":"doi","value":"10.24963/ijcai.2021/65"}],"type":"Article","urls":["https://doi.org/10.24963/ijcai.2021/65"],"publicationDate":"2021-08-01","refereed":"peerReviewed","hostedBy":{"key":"openaire____::55045bd2a65019fd8e6741a755395c8c","value":"Unknown Repository"},"collectedFrom":{"key":"openaire____::081b82f96300b6a6e3d282bad31cb6e2","value":"Crossref"}},{"pids":[{"scheme":"doi","value":"10.24963/ijcai.2021/65"}],"accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":"bronze"},"type":"Article","urls":["https://www.ijcai.org/proceedings/2021/0065.pdf"],"refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::55045bd2a65019fd8e6741a755395c8c","value":"Unknown Repository"},"collectedFrom":{"key":"openaire____::8ac8380272269217cb09a928c8caa993","value":"UnpayWall"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.24963/ijcai.2021/65"}],"type":"Conference object","urls":["https://doi.org/10.24963/ijcai.2021/65","https://dblp.org/rec/conf/ijcai/00010G21.html"],"refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},"collectedFrom":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.24963/ijcai.2021/65"},{"scheme":"mag_id","value":"3189849428"}],"type":"Article","urls":["https://dx.doi.org/10.24963/ijcai.2021/65"],"refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::55045bd2a65019fd8e6741a755395c8c","value":"Unknown Repository"},"collectedFrom":{"key":"openaire____::5f532a3fc4f1ea403f37070f59a7a53a","value":"Microsoft Academic Graph"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.24963/ijcai.2021/65"}],"accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":null},"type":"Conference object","urls":["https://doi.org/10.24963/ijcai.2021/65","https://ora.ox.ac.uk/objects/uuid:6099c717-0c4d-433e-8c7d-f7cfa2b896d5"],"publicationDate":"2022-04-05","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::2290a7385ed77cc5592dc2153229f082","value":"Oxford University Research Archive"},"collectedFrom":{"key":"opendoar____::2290a7385ed77cc5592dc2153229f082","value":"Oxford University Research Archive"}},{"alternateIdentifiers":[{"scheme":"mag_id","value":"3189849428"},{"scheme":"doi","value":"10.24963/ijcai.2021/65"}],"type":"Article","urls":["https://dx.doi.org/10.24963/ijcai.2021/65"],"refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::55045bd2a65019fd8e6741a755395c8c","value":"Unknown Repository"},"collectedFrom":{"key":"openaire____::5f532a3fc4f1ea403f37070f59a7a53a","value":"Microsoft Academic Graph"}}],"links":[{"header":{"relationType":"resultProject","relationClass":"isProducedBy","relatedIdentifier":"corda__h2020::83d6aa753c4b6e94582f4ef733616892","relatedRecordType":"project","relationProvenance":"iis","trust":"0.897"},"collectedfrom":[{"dsId":"openaire____::a55eb91348674d853191f4f4fd73d078","dsName":"CORDA - COmmon Research DAta Warehouse - Horizon 2020"}],"projectTitle":"Human-Centric Machine Learning","code":"945719","funding":{"funder":{"id":"ec__________::EC","shortname":"EC","name":"European Commission","jurisdiction":{"code":"EU","label":"European Union"},"pid":null},"level0":{"id":"ec__________::EC::H2020","description":"Horizon 2020 Framework Programme","name":"H2020"},"level1":{"id":"ec__________::EC::H2020::ERC","description":"European Research Council","name":"ERC"},"level2":{"id":"ec__________::EC::H2020::ERC::ERC-STG","description":"Starting Grant","name":"ERC-STG"}},"startDate":"2020-11-01","endDate":"2025-10-31"}],"otherTitles":null,"inDiamondJournal":false,"green":true,"isGreen":true,"isInDiamondJournal":false}