Motivated by real-world applications, we study the fair allocation of graphical resources, where the resources are the vertices in a graph. Upon receiving a set of resources, an agent's utility equals the weight of a maximum matching in the induced subgraph. We care about maximin share (MMS) fairness and envy-freeness up to one item (EF1). Regarding MMS fairness, the problem does not admit a finite approximation ratio for heterogeneous agents. For homogeneous agents, we design constant-approximation polynomial-time algorithms, and also note that significant amount of social welfare is sacrificed inevitably in order to ensure (approximate) MMS fairness. We then consider EF1 allocations whose existence is guaranteed. However, the social welfare guarantee of EF1 allocations cannot be better than $1/n$ for the general case, where $n$ is the number of agents.Fortunately, for three special cases, binary-weight, two-agents and homogeneous-agents, we are able to design polynomial-time algorithms that also ensure a constant fractions of the maximum social welfare.

翻译：在现实应用的激励下,我们研究了图形资源的公平分配,资源是图表中的顶点。在收到一组资源时,代理商的效用等于引导子体中最大匹配的重量。我们关心的是最大份额(MMS)的公平和无嫉妒程度,直到一个项目(EF1)。关于MMS的公平性,问题并不承认不同代理商的有限近似比率。对于同质剂,我们设计了经常使用多时混合算法,并注意到大量社会福利不可避免地被牺牲,以确保(近似)MMS的公平性。我们然后考虑EF1分配款的存在得到保证。然而,EF1分配款的社会福利保证不能比一般案例的1美元/n美元好,因为一般案例的代理商数量为$。对于三种特殊案例,即二重、两剂和同质试剂,我们有能力设计多时算法,确保最高社会福利的固定部分。