Relevant bibliographies by topics / Fair-division problems

Academic literature on the topic 'Fair-division problems'

Author: Grafiati
Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Fair-division problems.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Fair-division problems"

1

Aleksandrov, Martin, and Toby Walsh. "Online Fair Division: A Survey." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 09 (April 3, 2020): 13557–62. http://dx.doi.org/10.1609/aaai.v34i09.7081.

Full text
Abstract:
We survey a burgeoning and promising new research area that considers the online nature of many practical fair division problems. We identify wide variety of such online fair division problems, as well as discuss new mechanisms and normative properties that apply to this online setting. The online nature of such fair division problems provides both opportunities and challenges such as the possibility to develop new online mechanisms as well as the difficulty of dealing with an uncertain future.
APA, Harvard, Vancouver, ISO, and other styles
2

Herreiner, Dorothea K., and Clemens D. Puppe. "Envy Freeness in Experimental Fair Division Problems." Theory and Decision 67, no. 1 (July 18, 2007): 65–100. http://dx.doi.org/10.1007/s11238-007-9069-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Dall'Aglio, Marco, and Theodore P. Hill. "Maximin share and minimax envy in fair-division problems." Journal of Mathematical Analysis and Applications 281, no. 1 (May 2003): 346–61. http://dx.doi.org/10.1016/s0022-247x(03)00107-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Sagara, Nobusumi. "A characterization of α-maximin solutions of fair division problems." Mathematical Social Sciences 55, no. 3 (May 2008): 273–80. http://dx.doi.org/10.1016/j.mathsocsci.2007.09.007.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Moulin, H. "Fair division under joint ownership: Recent results and open problems." Social Choice and Welfare 7, no. 2 (April 1990): 149–70. http://dx.doi.org/10.1007/bf01560582.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Vetschera, Rudolf. "A general branch-and-bound algorithm for fair division problems." Computers & Operations Research 37, no. 12 (December 2010): 2121–30. http://dx.doi.org/10.1016/j.cor.2010.03.001.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Arunachaleswaran, Eshwar Ram, Siddharth Barman, and Nidhi Rathi. "Fair Division with a Secretive Agent." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 1732–39. http://dx.doi.org/10.1609/aaai.v33i01.33011732.

Full text
Abstract:
We study classic fair-division problems in a partial information setting. This paper respectively addresses fair division of rent, cake, and indivisible goods among agents with cardinal preferences. We will show that, for all of these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n − 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation.For the rent-division setting we prove that well-behaved utilities of n − 1 agents suffice to find a rent division among n rooms such that, for every possible room selection of the secretive agent, there exists an allocation (of the remaining n − 1 rooms among the n − 1 agents) which ensures overall envy freeness (fairness). We complement this existential result by developing a polynomial-time algorithm for the case of quasilinear utilities. In this partial information setting, we also develop efficient algorithms to compute allocations that are envy-free up to one good (EF1) and ε-approximate envy free. These two notions of fairness are applicable in the context of indivisible goods and divisible goods (cake cutting), respectively.One of the main technical contributions of this paper is the development of novel connections between different fairdivision paradigms, e.g., we use our existential results for envy-free rent-division to develop an efficient EF1 algorithm.
APA, Harvard, Vancouver, ISO, and other styles
8

Goetz, Albert. "Cost Allocation: An Application of Fair Division." Mathematics Teacher 93, no. 7 (October 2000): 600–603. http://dx.doi.org/10.5951/mt.93.7.0600.

Full text
Abstract:
Although the subject of cost allocation has been extensively discussed in the literature of political economics, it has been generally neglected in mathematical literature. However, cost allocation affords a practical extension of fair-division techniques–one that is readily accessible to secondary school students and that gives them a simple yet powerful application of mathematics to real-world problem solving. A study of the concepts and the mathematics involved in cost allocation is most appropriate in a discrete mathematics course or a modeling course, but a case can be made for including this topic in other courses, as well. This article presents a typical cost-allocation problem with possible solutions and includes suggestions for presenting similar problems in the classroom. The basics of the problem follow closely from Young (1994).
APA, Harvard, Vancouver, ISO, and other styles
9

Bei, Xiaohui, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong. "The Price of Connectivity in Fair Division." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 6 (May 18, 2021): 5151–58. http://dx.doi.org/10.1609/aaai.v35i6.16651.

Full text
Abstract:
We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on the well-studied fairness notion of maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.
APA, Harvard, Vancouver, ISO, and other styles
10

Dror, Amitay, Michal Feldman, and Erel Segal-Halevi. "On Fair Division under Heterogeneous Matroid Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 6 (May 18, 2021): 5312–20. http://dx.doi.org/10.1609/aaai.v35i6.16670.

Full text
Abstract:
We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors, and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints, or allow free disposal of items. An open problem is the existence of EF1 complete allocations among heterogeneous agents, where the heterogeneity is both in the agents' feasibility constraints and in their valuations. In this work, we make progress on this problem by providing positive and negative results for different matroid and valuation types. Among other results, we devise poly-time algorithms for finding EF1 allocations in the following settings: (i) n agents with heterogeneous partition matroids and heterogeneous binary valuations, (ii) 2 agents with heterogeneous partition matroids and heterogeneous valuations, and (iii) at most 3 agents with heterogeneous binary valuations and identical base-orderable matroids.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Fair-division problems"

1

Rathi, Nidhi. "Algorithmic and Hardness Results for Fundamental Fair-Division Problems." Thesis, 2021. https://etd.iisc.ac.in/handle/2005/5205.

Full text
Abstract:
The theory of fair division addresses the fundamental problem of dividing a set of resources among the participating agents in a satisfactory or meaningfully fair manner. This thesis examines the key computational challenges that arise in various settings of fair-division problems and complements the existential (and non-constructive) guarantees and various hardness results by way of developing efficient (approximation) algorithms and identifying computationally tractable instances. • Our work in fair cake division develops several algorithmic results for allocating a divisible resource (i.e., the cake) among a set of agents in a fair/economically efficient manner. While strong existence results and various hardness results exist in this setup, we develop a polynomial-time algorithm for dividing the cake in an approximately fair and efficient manner. Furthermore, we identify an encompassing property of agents’ value densities (over the cake)—the monotone likelihood ratio property (MLRP)—that enables us to prove strong algorithmic results for various notions of fairness and (economic) efficiency. • Our work in fair rent division develops a fully polynomial-time approximation scheme (FPTAS) for dividing a set of discrete resources (the rooms) and splitting the money (rents) among agents having general utility functions (continuous, monotone decreasing, and piecewise-linear), in a fair manner. Prior to our work, efficient algorithms for finding such solutions were known only for a specific set of utility functions. We com- plement the algorithmic results by proving that the fair rent division problem (under general utilities) lies in the intersection of the complexity classes, PPAD (Polynomial Parity Arguments on Directed graphs) and PLS (Polynomial Local Search). • Our work respectively addresses fair division of rent, cake (divisible), and discrete (in- divisible) goods in a partial information setting. We show that, for all these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation.
IBM Ph.D. Fellowship 2020
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Fair-division problems"

1

At the food fair: Represent and solve problems involving division. New York: Rosen Classroom, 2015.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Brams, Steven J. Fair Division. Edited by Donald A. Wittman and Barry R. Weingast. Oxford University Press, 2009. http://dx.doi.org/10.1093/oxfordhb/9780199548477.003.0024.

Full text
Abstract:
This article provides a review of the literature on fair division, which has flourished in recent years. It focuses on three different literatures in the field: the allocation of several indivisible goods, the division of a single heterogeneous good, and the division, in whole or in part, of several divisible goods. The article discusses problems that arise in allocating indivisible goods, and highlights the trade-offs that must be made when not all of the criteria of fairness can be satisfied at the same time. It also describes and provides the procedures for dividing divisible goods fairly, which is based on different criteria of fairness.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Fair-division problems"

1

de Longueville, Mark. "Fair-Division Problems." In A Course in Topological Combinatorics, 1–35. New York, NY: Springer New York, 2012. http://dx.doi.org/10.1007/978-1-4419-7910-0_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Guo, Rongxing. "Solving Fair Division Problems." In Cross-Border Management, 119–33. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-662-45156-4_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Raith, Matthias G. "The Structure of Fair-Division Problems and the Design of Fair-Negotiation Procedures." In Theory and Decision Library, 205–23. Boston, MA: Springer US, 2000. http://dx.doi.org/10.1007/978-1-4615-4627-6_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Trudeau, Christian. "When Are Operations Research Algorithms Useful in Fair Division Problems?" In The Future of Economic Design, 305–8. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-18050-8_41.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Legut, Jerzy. "On Cooperative Games Arising from a Problem of Fair Division." In Transactions of the Tenth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes, 117–20. Dordrecht: Springer Netherlands, 1988. http://dx.doi.org/10.1007/978-94-010-9913-4_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Dall’Aglio, Marco. "Optimization Problems in Fair Division Theory." In Handbook of Analytic Computational Methods in Applied Mathematics. Chapman and Hall/CRC, 2000. http://dx.doi.org/10.1201/9781420036053.ch20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Dall’Aglio, Marco. "Optimization Problems in Fair Division Theory." In Handbook of Analytic-Computational Methods in Applied Mathematics, 909–46. Chapman and Hall/CRC, 2019. http://dx.doi.org/10.1201/9780429123610-20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Hausman, Daniel M. "Theories of Fair Distribution." In How Health Care Can Be Cost-Effective and Fair, 62—C4T4. Oxford University PressNew York, 2023. http://dx.doi.org/10.1093/oso/9780197656969.003.0005.

Full text
Abstract:
Abstract This chapter develops the main contemporary theories concerned with the fair distribution of both divisible and indivisible goods. It begins by discussing vague generalizations about fairness, which guide the formulation and assessment of more specific theories. Next, it characterizes problems of fair division, a simple example of which is presented. It also discusses how cooperative game theory bears on questions of fair distribution. It presents John Broome’s influential account of how to allocate divisible goods fairly among the claimants as well as Broome’s view of the fair distribution of indivisible goods. The chapter turns to problems for Broome’s theory, and it considers what fairness requires when claims to goods differ both quantitatively and in strength, and it defends a fragment of a theory of fairness. The chapter ends with a discussion of two other philosophical theories of fairness, which are due to Larry Temkin and Matthew Adler.
APA, Harvard, Vancouver, ISO, and other styles
9

Wiggins, Benjamin. "Conclusion." In Calculating Race, 97–102. Oxford University Press, 2020. http://dx.doi.org/10.1093/oso/9780197504000.003.0006.

Full text
Abstract:
Can risk assessment be made fair? The conclusion of Calculating Race returns to actuarial science’s foundations in probability. The roots of probability rest in a pair of problems posed to Blaise Pascal and Pierre de Fermat in the summer of 1654: “the Dice Problem” and “the Division Problem.” From their very foundation, the mathematics of probability offered the potential not only to be used to gain an advantage (as in the case of the Dice Problem), but also to divide material fairly (as in the case of the Division Problem). As the United States and the world enter an age driven by Big Data, algorithms, artificial intelligence, and machine learning and characterized by an actuarialization of everything, we must remember that risk assessment need not be put to use for individual, corporate, or government advantage but, rather, that it has always been capable of guiding how to distribute risk equitably instead.
APA, Harvard, Vancouver, ISO, and other styles
10

Morgan, Polly. "4. Property Division on Divorce." In Family Law, 129–82. Oxford University Press, 2022. http://dx.doi.org/10.1093/he/9780192893536.003.0004.

Full text
Abstract:
At the end of a marriage or civil partnership, it is necessary to consider the practical and financial arrangements for the parties’ future: how they will share the value of the house(s), the pensions, and the savings and investments; who pays the debts; who gets personal belongings and furniture; and who has what income to live on. The law will only give effect to agreements that are objectively fair. If the parties cannot agree on a fair settlement, then courts have the power to impose a settlement on them by making a ‘financial remedy’ order in whatever terms it thinks are objectively fair. This power does not apply to unmarried couples. This chapter looks at what the court can do, the legal principles and practicalities that govern property redistribution, and some contentious issues and problems that may arise in financial remedy practice.
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Fair-division problems"

1

Mirzakhani, Maryam, and Jan Vondrák. "Sperner's Colorings, Hypergraph Labeling Problems and Fair Division." In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014. http://dx.doi.org/10.1137/1.9781611973730.60.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Samieefar, Koosha. "A Meta-heuristic Approach for Strategic Fair Division Problems." In ISMSI 2023: 2023 7th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence. New York, NY, USA: ACM, 2023. http://dx.doi.org/10.1145/3596947.3596969.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Chakraborty, Mithun, Ulrike Schmidt-Kraepelin, and Warut Suksompong. "Picking Sequences and Monotonicity in Weighted Fair Division." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/12.

Full text
Abstract:
We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our focus is on picking sequences derived from common apportionment methods, including five traditional divisor methods and the quota method. We paint a complete picture of these methods in relation to known envy-freeness and proportionality relaxations for indivisible items as well as monotonicity properties with respect to the resource, population, and weights. In addition, we provide characterizations of picking sequences satisfying each of the fairness notions, and show that the well-studied maximum Nash welfare solution fails resource- and population-monotonicity even in the unweighted setting. Our results serve as an argument in favor of using picking sequences in weighted fair division problems.
APA, Harvard, Vancouver, ISO, and other styles
4

Nguyen, Trung Thanh, and Jörg Rothe. "Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/754.

Full text
Abstract:
Fair allocation of indivisible goods is a central topic in many AI applications. Unfortunately, the corresponding problems are known to be NP-hard for many fairness concepts, so unless P = NP, exact polynomial-time algorithms cannot exist for them. In practical applications, however, it would be highly desirable to find exact solutions as quickly as possible. This motivates the study of algorithms that—even though they only run in exponential time—are as fast as possible and exactly solve such problems. We present known complexity results for them and give a survey of important techniques for designing such algorithms, mainly focusing on four common fairness notions: max-min fairness, maximin share, maximizing Nash social welfare, and envy-freeness. We also highlight the most challenging open problems for future work.
APA, Harvard, Vancouver, ISO, and other styles
5

Amanatidis, Georgios, Georgios Birmpas, and Vangelis Markakis. "Comparing Approximate Relaxations of Envy-Freeness." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/6.

Full text
Abstract:
In fair division problems with indivisible goods it is well known that one cannot have any guarantees for the classic fairness notions of envy-freeness and proportionality. As a result, several relaxations have been introduced, most of which in quite recent works. We focus on four such notions, namely envy-freeness up to one good (EF1), envy-freeness up to any good (EFX), maximin share fairness (MMS), and pairwise maximin share fairness (PMMS). Since obtaining these relaxations also turns out to be problematic in several scenarios, approximate versions of them have also been considered. In this work, we investigate further the connections between the four notions mentioned above and their approximate versions. We establish several tight or almost tight results concerning the approximation quality that any of these notions guarantees for the others, providing an almost complete picture of this landscape. Some of our findings reveal interesting and surprising consequences regarding the power of these notions, e.g., PMMS and EFX provide the same worst-case guarantee for MMS, despite PMMS being a strictly stronger notion than EFX. We believe such implications provide further insight on the quality of approximately fair solutions.
APA, Harvard, Vancouver, ISO, and other styles
6

Huang, S. J., C. C. Kuo, and H. W. Kwan. "The Planning and Execution of Taiwan’s Largest Combined Cycle Plant." In ASME 2004 Power Conference. ASMEDC, 2004. http://dx.doi.org/10.1115/power2004-52060.

Full text
Abstract:
Taiwan’s continuous economic growth in the past 50 years has spurred a similar growth in electricity demand. Historically the reserve margin has been less than 20 percent, although new generation is introduced every year. In the planning for new plants, consideration must be given to the location, choice of fuel, environmental impact and in a democratic society, their public acceptance. Based on projected growth demand, a decision was made in 1996 to build a 4,000 MW gas fired combined cycle power plant at the Dah Tarn location. The project has offered many opportunities to international equipment suppliers and local contractors. As a government entity, Taiwan Power Company follows the Government Procurement Law in procurement of equipment and services which is designed for open and fair competition and protection of the interests of the Owner. The uniqueness of the site and its surroundings, and the division of work between participants has presented some design and engineering problems that need to be overcome in the execution of this plant.
APA, Harvard, Vancouver, ISO, and other styles
7

Li, Bo, Wenyang Li, and Yingkai Li. "Dynamic Fair Division Problem with General Valuations." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/52.

Full text
Abstract:
In this paper, we focus on how to dynamically allocate a divisible resource fairly among n players who arrive and depart over time. The players may have general heterogeneous valuations over the resource. It is known that the exact envy-free and proportional allocations may not exist in the dynamic setting [Walsh, 2011]. Thus, we will study to what extent we can guarantee the fairness in the dynamic setting. We first design two algorithms which are O(log n)-proportional and O(n)-envy-free for the setting with general valuations, and by constructing the adversary instances such that all dynamic algorithms must be at least Omega(1)-proportional and Omega(n/log n)-envy-free, we show that the bounds are tight up to a logarithmic factor. Moreover, we introduce the setting where the players' valuations are uniform on the resource but with different demands, which generalize the setting of [Friedman et al., 2015]. We prove an O(log n) upper bound and a tight lower bound for this case.
APA, Harvard, Vancouver, ISO, and other styles
8

Biswas, Arpita, and Siddharth Barman. "Fair Division Under Cardinality Constraints." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/13.

Full text
Abstract:
We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods---i.e., the goods are categorized---and a limit is specified on the number of goods that can be allocated from each category to any agent. The objective here is to find a fair allocation in which the subset of goods assigned to any agent satisfies the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied unconstrained fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and the (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist even under matroid constraints.
APA, Harvard, Vancouver, ISO, and other styles
9

Walsh, Toby. "Fair Division: The Computer Scientist’s Perspective." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/691.

Full text
Abstract:
I survey recent progress on a classic and challenging problem in social choice: the fair division of indivisible items. I discuss how a computational perspective has provided interesting insights into and understanding of how to divide items fairly and efficiently. This has involved bringing to bear tools such as those used in knowledge representation, computational complexity, approximation methods, game theory, online analysis and communication complexity.
APA, Harvard, Vancouver, ISO, and other styles
10

Deligkas, Argyrios, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak. "The Parameterized Complexity of Connected Fair Division." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/20.

Full text
Abstract:
We study the Connected Fair Division problem (CFD), which generalizes the fundamental problem of fairly allocating resources to agents by requiring that the items allocated to each agent form a connected subgraph in a provided item graph G. We expand on previous results by providing a comprehensive complexity-theoretic understanding of CFD based on several new algorithms and lower bounds while taking into account several well-established notions of fairness: proportionality, envy-freeness, EF1 and EFX. In particular, we show that to achieve tractability, one needs to restrict both the agents and the item graph in a meaningful way. We design (XP)-algorithms for the problem parameterized by (1) clique-width of G plus the number of agents and (2) treewidth of G plus the number of agent types, along with corresponding lower bounds. Finally, we show that to achieve fixed-parameter tractability, one needs to not only use a more restrictive parameterization of G, but also include the maximum item valuation as an additional parameter.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Fair-division problems' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography