We consider a matching problem in a bipartite graph $G$ where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function …
We consider a matching problem in a bipartite graph $G$ where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume $G$ admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible for us and we are interested in those perfect matchings that are popular within the set of perfect matchings. It is known that such matchings (called popular perfect matchings) always exist and can be efficiently computed. What we seek here is not any popular perfect matching, but a min-cost one. We show a polynomial-time algorithm for finding such a matching; this is via a characterization of popular perfect matchings in $G$ in terms of stable matchings in a colorful auxiliary instance. This is a generalization of such a characterization that was known in the one-to-one setting.
In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an …
In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we give a pseudo-polynomial time algorithm that always finds an EFX allocation of chores. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are {0,+1}-valued functions, and negative Boolean utilities that are {0,−1}-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.
.Let \(G = (A \cup B, E)\) be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally …
.Let \(G = (A \cup B, E)\) be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching \(M\) in \(G\) is a popular max-matching if there is no maximum matching more popular than \(M\). In other words, for any maximum matching \(N\), the number of nodes that prefer \(M\) to \(N\) is at least the number of nodes that prefer \(N\) to \(M\). It is known that popular max-matchings always exist in \(G\) and one such matching can be efficiently computed. In this paper we are in the weighted setting, i.e., there is a cost function \(c: E \rightarrow \mathbb{R}\), and our goal is to find a min-cost popular max-matching. We prove that such a matching can be computed in polynomial time by showing a compact extended formulation for the popular max-matching polytope. By contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard. We also consider Pareto-optimality. Though it is easy to find a Pareto-optimal matching/max-matching, we show that it is NP-hard to find a min-cost Pareto-optimal matching/max-matching.Keywordsbipartite graphsstable matchingsdual certificatesMSC codes68W9968Q17
Our input is a directed, rooted graph G = (V ∪ {r}, E) where each vertex in V has a partial order preference over its incoming edges. The preferences of …
Our input is a directed, rooted graph G = (V ∪ {r}, E) where each vertex in V has a partial order preference over its incoming edges. The preferences of a vertex extend naturally to preferences over arborescences rooted at r. We seek a popular arborescence in G, i.e., one for which there is no "more popular" arborescence. Popular arborescences have applications in liquid democracy or collective decision making; however, they need not exist in every input instance. The popular arborescence problem is to decide if a given input instance admits a popular arborescence or not. We show a polynomial-time algorithm for this problem, whose computational complexity was not known previously.
Let G = (A ∪ B, E) be a bipartite graph where the set A consists of agents or main players and the set B consists of jobs or secondary …
Let G = (A ∪ B, E) be a bipartite graph where the set A consists of agents or main players and the set B consists of jobs or secondary players. Every vertex in A ∪ B has a strict ranking of its neighbors. A matching M is popular if for any matching N , the number of vertices that prefer M to N is at least the number that prefer N to M . Popular matchings always exist in G since every stable matching is popular. A matching M is A -popular if for any matching N , the number of agents (i.e., vertices in A ) that prefer M to N is at least the number of agents that prefer N to M . Unlike popular matchings, A -popular matchings need not exist in a given instance G and there is a simple linear time algorithm to decide if G admits an A -popular matching and compute one, if so. We consider the problem of deciding if G admits a matching that is both popular and A -popular and finding one, if so. We call such matchings fully popular . A fully popular matching is useful when A is the more important side—so along with overall popularity, we would like to maintain “popularity within the set A ”. A fully popular matching is not necessarily a min-size/max-size popular matching and all known polynomial-time algorithms for popular matching problems compute either min-size or max-size popular matchings. Here we show a linear time algorithm for the fully popular matching problem, thus our result shows a new tractable subclass of popular matchings.
Our input is a directed, rooted graph $G = (V \cup \{r\},E)$ where each vertex in $V$ has a partial order preference over its incoming edges. The preferences of a …
Our input is a directed, rooted graph $G = (V \cup \{r\},E)$ where each vertex in $V$ has a partial order preference over its incoming edges. The preferences of a vertex extend naturally to preferences over arborescences rooted at $r$. We seek a popular arborescence in $G$, i.e., one for which there is no "more popular" arborescence. Popular arborescences have applications in liquid democracy or collective decision making; however, they need not exist in every input instance. The popular arborescence problem is to decide if a given input instance admits a popular arborescence or not. We show a polynomial-time algorithm for this problem, whose computational complexity was not known previously. Our algorithm is combinatorial, and can be regarded as a primal-dual algorithm. It searches for an arborescence along with its dual certificate, a chain of subsets of $E$, witnessing its popularity. In fact, our algorithm solves the more general popular common base problem in the intersection of two matroids, where one matroid is the partition matroid defined by any partition $E = \bigcup_{v\in V} \delta(v)$ and the other is an arbitrary matroid on $E$ of rank $|V|$, with each $v \in V$ having a partial order over elements in $\delta(v)$. We extend our algorithm to the case with forced or forbidden edges. We also study the related popular colorful forest (or more generally, the popular common independent set) problem where edges are partitioned into color classes, and the task is to find a colorful forest that is popular within the set of all colorful forests. For the case with weak rankings, we formulate the popular colorful forest polytope, and thus show that a minimum-cost popular colorful forest can be computed efficiently. By contrast, we prove that it is NP-hard to compute a minimum-cost popular arborescence, even when rankings are strict.
Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 5 March 2019Accepted: 07 June 2021Published online: 10 January 2022Keywordspopular matching, stable matching, …
Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 5 March 2019Accepted: 07 June 2021Published online: 10 January 2022Keywordspopular matching, stable matching, complexity, dominant matchingAMS Subject Headings05C85, 68R10, 68Q17Publication DataISSN (print): 0895-4801ISSN (online): 1095-7146Publisher: Society for Industrial and Applied MathematicsCODEN: sjdmec
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)The popular assignment problem: when cardinality is more important than popularityTelikepalli Kavitha, Tamás Király, …
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)The popular assignment problem: when cardinality is more important than popularityTelikepalli Kavitha, Tamás Király, Jannik Matuschke, Ildikó Schlotter, and Ulrike Schmidt-KraepelinTelikepalli Kavitha, Tamás Király, Jannik Matuschke, Ildikó Schlotter, and Ulrike Schmidt-Kraepelinpp.103 - 123Chapter DOI:https://doi.org/10.1137/1.9781611977073.6PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We consider a matching problem in a bipartite graph G = (A∪B, E) where each node in A is an agent having preferences in partial order over her neighbors, while nodes in B are objects with no preferences. The size of our matching is more important than node preferences–thus, we are interested in maximum matchings only. Any pair of maximum matchings in G (equivalently, perfect matchings or assignments) can be compared by holding a head-to-head election between them where agents are voters. The goal is to compute an assignment such that there is no better or "more popular" assignment. This is the popular assignment problem and it generalizes the well-studied popular matching problem (Abraham et al., 2007). Popular assignments need not exist in every input instance. We show a polynomial-time algorithm that decides if the given instance admits one or not, and computes one, if so. In instances with no popular assignment, we consider the problem of finding an almost popular assignment, i.e., an assignment with minimum unpopularity margin. We show an O∗ (|E|k) time algorithm for deciding if there exists an assignment with unpopularity margin at most k. We then show that this algorithm is essentially optimal by proving that the problem is NP-complete and Wl[1]-hard with parameter k. We also consider the minimum-cost popular assignment problem when there are edge costs, and show this problem to be NP-hard. This hardness holds even when all edge costs are in {0,1} and agents have strict preferences. By contrast, we propose a polynomial-time algorithm to the problem of deciding if there exists a popular assignment with a given set of forced/forbidden edges (this tractability holds even for partially ordered preferences). Our algorithms are combinatorial and based on LP duality. They search for an appropriate witness or dual certificate, and when a certificate cannot be found, we prove that the desired assignment does not exist in G. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771
Let $G = (A \cup B,E)$ be a bipartite graph where the set $A$ consists of agents or main players and the set $B$ consists of jobs or secondary players. …
Let $G = (A \cup B,E)$ be a bipartite graph where the set $A$ consists of agents or main players and the set $B$ consists of jobs or secondary players. Every vertex has a strict ranking of its neighbors. A matching $M$ is popular if for any matching $N$, the number of vertices that prefer $M$ to $N$ is at least the number that prefer $N$ to $M$. Popular matchings always exist in $G$ since every stable matching is popular. A matching $M$ is $A$-popular if for any matching $N$, the number of agents (i.e., vertices in $A$) that prefer $M$ to $N$ is at least the number of agents that prefer $N$ to $M$. Unlike popular matchings, $A$-popular matchings need not exist in a given instance $G$ and there is a simple linear time algorithm to decide if $G$ admits an $A$-popular matching and compute one, if so. We consider the problem of deciding if $G$ admits a matching that is both popular and $A$-popular and finding one, if so. We call such matchings fully popular. A fully popular matching is useful when $A$ is the more important side -- so along with overall popularity, we would like to maintain ``popularity within the set $A$''. A fully popular matching is not necessarily a min-size/max-size popular matching and all known polynomial-time algorithms for popular matching problems compute either min-size or max-size popular matchings. Here we show a linear time algorithm for the fully popular matching problem, thus our result shows a new tractable subclass of popular matchings.
Let [Formula: see text] be an instance of the stable marriage problem in which every vertex ranks its neighbors in a strict order of preference. A matching [Formula: see text] …
Let [Formula: see text] be an instance of the stable marriage problem in which every vertex ranks its neighbors in a strict order of preference. A matching [Formula: see text] in [Formula: see text] is popular if [Formula: see text] does not lose a head-to-head election against any matching. Popular matchings generalize stable matchings. Unfortunately, when there are edge costs, to find or even approximate up to any factor a popular matching of minimum cost is NP-hard. Let [Formula: see text] be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most [Formula: see text] by paying the price of mildly relaxing popularity. Our main positive results are two bicriteria algorithms that find in polynomial time a “quasi-popular” matching of cost at most [Formula: see text]. Moreover, one of the algorithms finds a quasi-popular matching of cost at most that of a min-cost popular fractional matching, which could be much smaller than [Formula: see text]. Key to the other algorithm is a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity.
Given a graph $G = (V,E)$ where every vertex has weak preferences over its neighbors, we consider the problem of computing an optimal matching as per agent preferences. The classical …
Given a graph $G = (V,E)$ where every vertex has weak preferences over its neighbors, we consider the problem of computing an optimal matching as per agent preferences. The classical notion of optimality in this setting is stability. However stable matchings, and more generally, popular matchings need not exist when $G$ is non-bipartite. Unlike popular matchings, Copeland winners always exist in any voting instance -- we study the complexity of computing a matching that is a Copeland winner and show there is no polynomial-time algorithm for this problem unless $\mathsf{P} = \mathsf{NP}$.
We introduce a relaxation of both popular matchings and Copeland winners called semi-Copeland winners. These are matchings with Copeland score at least $\mu/2$, where $\mu$ is the total number of matchings in $G$; the maximum possible Copeland score is $(\mu-1/2)$. We show a fully polynomial-time randomized approximation scheme to compute a matching with Copeland score at least $\mu/2\cdot(1-\varepsilon)$ for any $\varepsilon > 0$.
Abstract Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings , i.e., directed forests; …
Abstract Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings , i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate the popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin . When preferences are strict rankings, we show that “approximately popular” branchings always exist.
The fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute $m$ goods to $n$ agents in a "fair" manner, where every …
The fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute $m$ goods to $n$ agents in a "fair" manner, where every agent has a valuation for each subset of goods. We assume monotone valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is "envy-freeness up to any good," EFX, where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists. We show there is always a partition of the set of goods into $n+1$ subsets $(X_1,\ldots,X_n,P)$, where for $i \in [n]$, $X_i$ is the bundle allocated to agent $i$ and the set $P$ is unallocated (or donated to charity) such that we have (1) envy-freeness up to any good, (2) no agent values $P$ higher than her own bundle, and (3) fewer than $n$ goods go to charity, i.e., $|P| < n$ (typically $m \gg n$). Our proof is constructive and leads to a pseudopolynomial time algorithm to find such an allocation. When agents have additive valuations and $|{P}|$ is large (i.e., when $|P|$ is close to $n$), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation that is 4/7 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 1/2 known for an approximate GMMS allocation. (Very recently and independently, Amanatidis, Ntokos, and Markakis [Theoret. Comput. Sci., 841 (2020), pp. 94--109], also showed the existence of a 4/7-GMMS allocation.)
We consider a matching problem in a bipartite graph $G=(A\cup B,E)$ where nodes in $A$ are agents having preferences in partial order over their neighbors, while nodes in $B$ are …
We consider a matching problem in a bipartite graph $G=(A\cup B,E)$ where nodes in $A$ are agents having preferences in partial order over their neighbors, while nodes in $B$ are objects without preferences. We propose a polynomial-time combinatorial algorithm based on LP duality that finds a maximum matching or assignment in $G$ that is popular among all maximum matchings, if there exists one. Our algorithm can also be used to achieve a trade-off between popularity and cardinality by imposing a penalty on unmatched nodes in $A$. We also provide an $O^*(|E|^k)$ algorithm that finds an assignment whose unpopularity margin is at most $k$; this algorithm is essentially optimal, since the problem is $\mathsf{NP}$-complete and $\mathsf{W}_l[1]$-hard with parameter $k$. We also prove that finding a popular assignment of minimum cost when each edge has an associated binary cost is $\mathsf{NP}$-hard, even if agents have strict preferences. By contrast, we propose a polynomial-time algorithm for the variant of the popular assignment problem with forced/forbidden edges. Finally, we present an application in the context of housing markets.
Given a graph $G = (V,E)$ where every vertex has a weak ranking over its neighbors, we consider the problem of computing an optimal matching as per agent preferences. Classical …
Given a graph $G = (V,E)$ where every vertex has a weak ranking over its neighbors, we consider the problem of computing an optimal matching as per agent preferences. Classical notions of optimality such as stability and its relaxation popularity could fail to exist when $G$ is non-bipartite. In light of the non-existence of a popular matching, we consider its relaxations that satisfy universal existence. We find a positive answer in the form of semi-popularity. A matching $M$ is semi-popular if for a majority of the matchings $N$ in $G$, $M$ does not lose a head-to-head election against $N$. We show that a semi-popular matching always exists in any graph $G$ and complement this existence result with a fully polynomial-time randomized approximation scheme (FPRAS). A special subclass of semi-popular matchings is the set of Copeland winners -- the notion of Copeland winner is classical in social choice theory and a Copeland winner always exists in any voting instance. We study the complexity of computing a matching that is a Copeland winner and show there is no polynomial-time algorithm for this problem unless $\mathsf{P} = \mathsf{NP}$.
In fair division problems, we are given a set $S$ of $m$ items and a set $N$ of $n$ agents with individual preferences, and the goal is to find an …
In fair division problems, we are given a set $S$ of $m$ items and a set $N$ of $n$ agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial-time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we prove that an EFX allocation of chores always exists. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are $\{0,+1\}$-valued functions, and negative Boolean utilities that are $\{0,-1\}$-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.
In fair division problems, we are given a set $S$ of $m$ items and a set $N$ of $n$ agents with individual preferences, and the goal is to find an …
In fair division problems, we are given a set $S$ of $m$ items and a set $N$ of $n$ agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial-time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we prove that an EFX allocation of chores always exists. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are $\{0,+1\}$-valued functions, and negative Boolean utilities that are $\{0,-1\}$-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.
Let $G$ be a bipartite graph where every node has a strict ranking of its neighbors. For every node, its preferences over neighbors extend naturally to preferences over matchings. Matching …
Let $G$ be a bipartite graph where every node has a strict ranking of its neighbors. For every node, its preferences over neighbors extend naturally to preferences over matchings. Matching $N$ is more popular than matching $M$ if the number of nodes that prefer $N$ to $M$ is more than the number that prefer $M$ to $N$. A maximum matching $M$ in $G$ is a "popular max-matching" if there is no maximum matching in $G$ that is more popular than $M$. Such matchings are relevant in applications where the set of admissible solutions is the set of maximum matchings and we wish to find a best maximum matching as per node preferences. It is known that a popular max-matching always exists in $G$. Here we show a compact extended formulation for the popular max-matching polytope. So when there are edge costs, a min-cost popular max-matching in $G$ can be computed in polynomial time. This is in contrast to the min-cost popular matching problem which is known to be NP-hard. We also consider Pareto-optimality, which is a relaxation of popularity, and show that computing a min-cost Pareto-optimal matching/max-matching is NP-hard.
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Quasi-popular Matchings, Optimality, and Extended FormulationsYuri Faenza and Telikepalli KavithaYuri Faenza and Telikepalli Kavithapp.325 - …
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Quasi-popular Matchings, Optimality, and Extended FormulationsYuri Faenza and Telikepalli KavithaYuri Faenza and Telikepalli Kavithapp.325 - 344Chapter DOI:https://doi.org/10.1137/1.9781611975994.20PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Let G = (A ∪ B, E) be an instance of the stable marriage problem where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if M does not lose a head-to-head election against any matching. Popular matchings are a well-studied generalization of stable matchings, introduced with the goal of enlarging the set of admissible solutions, while maintaining a certain level of fairness. Every stable matching is a min-size popular matching. Unfortunately, when there are edge costs, it is NP-hard to find a popular matching of minimum cost – even worse, the min-cost popular matching problem is hard to approximate up to any factor. Let opt be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most opt by paying the price of mildly relaxing popularity. Our main positive result is a bi-criteria algorithm that finds in polynomial time a near-popular or "quasi-popular" matching of cost at most opt. Key to the algorithm are a number of results for certain polytopes related to matchings. In particular, we give a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost, and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)A Little Charity Guarantees Almost Envy-FreenessBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini SgouritsaBhaskar …
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)A Little Charity Guarantees Almost Envy-FreenessBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini SgouritsaBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsapp.2658 - 2672Chapter DOI:https://doi.org/10.1137/1.9781611975994.162PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute m goods to n agents in a “fair” manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is “envy-freeness up to any good” (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when n = 3. We show there is always a partition of the set of goods into n + 1 subsets (X1, …, Xn, P) where for i ϵ [n], Xi is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that we have: (1)envy-freeness up to any good,(2)no agent values P higher than her own bundle, and(3)fewer than n goods go to charity, i.e., |P| < n (typically m ≫ n). Our proof is constructive. When agents have additive valuations and |P| is large (i.e., when |P| is close to n), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is 4/7 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 1/2 known for an approximate GMMS allocation. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011
Let $G$ be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching …
Let $G$ be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching $B$ is if $B$ does not lose a head-to-head election (where nodes cast votes) against any branching. Such branchings have a natural application in liquid democracy. The branching problem is to decide if $G$ admits a branching or not. We give a characterization of branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the branching problem. When preferences are weak rankings, we use our characterization to formulate the branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that approximately popular branchings always exist.
We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of …
We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs: they always exist and there is a simple linear time algorithm to find one.We show that it is NP-complete to decide if a bipartite graph admits a popular matching that is neither stable nor dominant. This gives rise to the anomaly that though it is easy to find min-size and max-size popular matchings in bipartite graphs, it is NP-complete to decide if there exists any popular matching whose size is sandwiched between the two extremes. We also show a number of related hardness results, such as (tight) 1/2-inapproximability of the maximum cost popular matching problem when costs are nonnegative. In non-bipartite graphs, we show a strong negative result: it is NP-hard to decide whether a popular matching exists or not, and the same result holds if we replace popular with dominant. On the positive side, we show the following results in any graph:•we identify a subclass of dominant matchings called strongly dominant matchings and show a linear time algorithm to decide if a strongly dominant matching exists or not;•we show an efficient algorithm to compute a popular matching of minimum cost in a graph with edge costs and bounded treewidth, or decide there is no popular matching.
Let $G$ be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching …
Let $G$ be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching $B$ is popular if $B$ does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if $G$ admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate the popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that "approximately popular" branchings always exist.
Let G = ((A,B),E) be an instance of the stable marriage problem where every vertex ranks its neighbors in a strict order of preference. A matching M in G is …
Let G = ((A,B),E) be an instance of the stable marriage problem where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if M does not lose a head-to-head election against any matching. Popular matchings are a well-studied generalization of stable matchings, introduced with the goal of enlarging the set of admissible solutions, while maintaining a certain level of fairness. Every stable matching is a min-size popular matching. Unfortunately, when there are edge costs, it is NP-hard to find a popular matching of minimum cost -- even worse, the min-cost popular matching problem is hard to approximate up to any factor. Let opt be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most opt by paying the price of mildly relaxing popularity. Our main positive results are two bi-criteria algorithms that find in polynomial time a near-popular or quasi-popular matching of cost at most opt. Moreover, one of the algorithms finds a quasi-popular matching of cost at most that of a min-cost popular fractional matching, which could be much smaller than opt. Key to the other algorithm is a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost, and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity. This version of the paper goes beyond the conference version [12] in the following two points: (i) the algorithm for finding a quasi-popular matching of cost at most that of a min-cost popular fractional matching is new; (ii) the proofs from Section 6.1 and Section 7.3 are now self-contained (the conference version used constructions from [10] to show these lower bounds).
Let $G = (A \cup B, E)$ be an instance of the stable marriage problem with strict preference lists. A matching $M$ is popular in $G$ if $M$ does not …
Let $G = (A \cup B, E)$ be an instance of the stable marriage problem with strict preference lists. A matching $M$ is popular in $G$ if $M$ does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is popular; another subclass of popular matchings that always exist and can be easily computed is the set of dominant matchings. A popular matching $M$ is dominant if $M$ wins the head-to-head election against any larger matching. The set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph.
In this paper, we investigate the difference between the tractability of stable and dominant matchings, and its consequence for popular matchings. We give the first known complete description of the dominant matching polytope in the original space and show that it has an exponential number of facets (recall that the stable matching polytope has a linear number of facets). This polyhedral asymmetry is reflected by a complexity asymmetry: We show that it is easy to decide if every popular matching in $G$ is also stable, however it is co-NP hard to decide if every popular matching in $G$ is also dominant.
We show that several hardness results in popular matchings, including the above result and the hardness of finding a popular matching in a non-bipartite graph, can be attributed to the NP-hardness of the following two stable matching problems:
- does $G$ admit a stable matching that is not dominant?
- does $G$ admit a stable matching that is also dominant?
Let $G = (A \cup B, E)$ be an instance of the stable marriage problem with strict preference lists. A matching $M$ is popular in $G$ if $M$ does not …
Let $G = (A \cup B, E)$ be an instance of the stable marriage problem with strict preference lists. A matching $M$ is popular in $G$ if $M$ does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exist and can be easily computed is the set of dominant matchings. A popular matching $M$ is dominant if $M$ wins the head-to-head election against any larger matching. Thus every dominant matching is a max-size popular matching and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings.
The goal of this paper is to show that indeed there are differences in the tractability of stable and dominant matchings, and to investigate further their importance for popular matchings. First, we show that it is easy to check if all popular matchings are also stable, however it is co-NP hard to check if all popular matchings are also dominant. Second, we show how some new and recent hardness results on popular matching problems can be deduced from the NP-hardness of certain problems on stable matchings, also studied in this paper, thus showing that stable matchings can be employed not only to show positive results on popular matching (as is known), but also most negative ones. Problems for which we show new hardness results include finding a min-size (resp. max-size) popular matching that is not stable (resp. dominant). A known result for which we give a new and simple proof is the NP-hardness of finding a popular matching when $G$ is non-bipartite.
Our input is a complete graph $G = (V,E)$ on $n$ vertices where each vertex has a strict ranking of all other vertices in $G$. Our goal is to construct …
Our input is a complete graph $G = (V,E)$ on $n$ vertices where each vertex has a strict ranking of all other vertices in $G$. Our goal is to construct a matching in $G$ that is popular. A matching $M$ is popular if $M$ does not lose a head-to-head election against any matching $M'$, where each vertex casts a vote for the matching in $\{M,M'\}$ where it gets assigned a better partner. The popular matching problem is to decide whether a popular matching exists or not. The popular matching problem in $G$ is easy to solve for odd $n$. Surprisingly, the problem becomes NP-hard for even $n$, as we show here.
We consider the max-size popular matching problem in a roommates instance G = (V,E) with strict preference lists. A matching M is popular if there is no matching M' in …
We consider the max-size popular matching problem in a roommates instance G = (V,E) with strict preference lists. A matching M is popular if there is no matching M' in G such that the vertices that prefer M' to M outnumber those that prefer M to M'. We show it is NP-hard to compute a max-size popular matching in G. This is in contrast to the tractability of this problem in bipartite graphs where a max-size popular matching can be computed in linear time. We define a subclass of max-size popular matchings called strongly dominant matchings and show a linear time algorithm to solve the strongly dominant matching problem in a roommates instance. We consider a generalization of the max-size popular matching problem in bipartite graphs: this is the max-weight popular matching problem where there is also an edge weight function w and we seek a popular matching of largest weight. We show this is an NP-hard problem and this is so even when w(e) is either 1 or 2 for every edge e. We also show an algorithm with running time O*(2^{n/4}) to find a max-weight popular matching matching in G = (A U B,E)$ on n vertices.
We consider the popular matching problem in a roommates instance with strict preference lists. While popular matchings always exist in a bipartite instance, they need not exist in a roommates …
We consider the popular matching problem in a roommates instance with strict preference lists. While popular matchings always exist in a bipartite instance, they need not exist in a roommates instance. The complexity of the popular matching problem in a roommates instance has been an open problem for several years and here we show it is NP-hard. A sub-class of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs. We show that the dominant matching problem in a roommates instance is also NP-hard and this is the case even when the instance admits a stable matching.
Let $G = (A \cup B, E)$ be an instance of the stable marriage problem with strict preference lists. A matching $M$ is popular in $G$ if $M$ does not …
Let $G = (A \cup B, E)$ be an instance of the stable marriage problem with strict preference lists. A matching $M$ is popular in $G$ if $M$ does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exist and can be easily computed is the set of dominant matchings. A popular matching $M$ is dominant if $M$ wins the head-to-head election against any larger matching. Thus every dominant matching is a max-size popular matching and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings. The goal of this paper is to show that indeed there are differences in the tractability of stable and dominant matchings, and to investigate further their importance for popular matchings. First, we show that it is easy to check if all popular matchings are also stable, however it is co-NP hard to check if all popular matchings are also dominant. Second, we show how some new and recent hardness results on popular matching problems can be deduced from the NP-hardness of certain problems on stable matchings, also studied in this paper, thus showing that stable matchings can be employed not only to show positive results on popular matching (as is known), but also most negative ones. Problems for which we show new hardness results include finding a min-size (resp. max-size) popular matching that is not stable (resp. dominant). A known result for which we give a new and simple proof is the NP-hardness of finding a popular matching when $G$ is non-bipartite.
Our input is a complete graph $G = (V,E)$ on $n$ vertices where each vertex has a strict ranking of all other vertices in $G$. Our goal is to construct …
Our input is a complete graph $G = (V,E)$ on $n$ vertices where each vertex has a strict ranking of all other vertices in $G$. Our goal is to construct a matching in $G$ that is popular. A matching $M$ is popular if $M$ does not lose a head-to-head election against any matching $M'$, where each vertex casts a vote for the matching in $\{M,M'\}$ where it gets assigned a better partner. The popular matching problem is to decide whether a popular matching exists or not. The popular matching problem in $G$ is easy to solve for odd $n$. Surprisingly, the problem becomes NP-hard for even $n$, as we show here.
We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of …
We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs: they always exist and there is a simple linear time algorithm to find one. We show that stable and dominant matchings are the only two tractable subclasses of popular matchings in bipartite graphs; more precisely, we show that it is NP-complete to decide if $G$ admits a popular matching that is neither stable nor dominant. We also show a number of related hardness results, such as (tight) inapproximability of the maximum weight popular matching problem. In non-bipartite graphs, we show a strong negative result: it is NP-hard to decide whether a popular matching exists or not, and the same result holds if we replace popular with dominant. On the positive side, we show the following results in any graph: - we identify a subclass of dominant matchings called strongly dominant matchings and show a linear time algorithm to decide if a strongly dominant matching exists or not; - we show an efficient algorithm to compute a popular matching of minimum cost in a graph with edge costs and bounded treewidth.
We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: In particular, every $a \in A$ ranks its …
We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: In particular, every $a \in A$ ranks its neighbors in a strict order of preference, whereas the preference list of any $b \in B$ may contain ties. A matching $M$ is popular if there is no matching $M'$ such that the number of vertices that prefer $M'$ to $M$ exceeds the number of vertices that prefer $M$ to $M'$. We show that the problem of deciding whether $G$ admits a popular matching or not is $\mathsf{NP}$-hard. This is the case even when every $b \in B$ either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each $b \in B$ puts all its neighbors into a single tie. That is, all neighbors of $b$ are tied in $b$'s list and $b$ desires to be matched to any of them. Our main result is an $O(n^2)$ algorithm (where $n = |A \cup B|$) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in $B$ have no preferences and do not care whether they are matched or not.
This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need …
This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts.
We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.
Here we discuss some results on the group of all closure isomorphisms of a \u{C}ech closure space. A subgroup \(H\) of the symmetric group \(S(X)\) is \(c\) representable on $X$ …
Here we discuss some results on the group of all closure isomorphisms of a \u{C}ech closure space. A subgroup \(H\) of the symmetric group \(S(X)\) is \(c\) representable on $X$ if there exists a closure operator \(V\) on $X$ such that the group of closure isomorphisms of the closure space \((X,\ V)\) is \(H\). In this paper, we prove a non trivial normal subgroup of the symmetric group \(S(X)\) is \(c\)-representable on \(X\) if and only if the cardinality of \(X\) is three.
We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: in particular, every $a \in A$ ranks its …
We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: in particular, every $a \in A$ ranks its neighbors in a strict order of preference, whereas the preference lists of $b \in B$ may contain ties. A matching $M$ is popular if there is no matching $M'$ such that the number of vertices that prefer $M'$ to $M$ exceeds the number of vertices that prefer $M$ to~$M'$. We show that the problem of deciding whether $G$ admits a popular matching or not is NP-hard. This is the case even when every $b \in B$ either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each $b \in B$ puts all its neighbors into a single tie. That is, all neighbors of $b$ are tied in $b$'s list and $b$ desires to be matched to any of them. Our main result is an $O(n^2)$ algorithm (where $n = |A \cup B|$) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in $B$ have no preferences and do not care whether they are matched or not.
Our input is a bipartite graph $G = (A \cup B,E)$ where each vertex in $A \cup B$ has a preference list strictly ranking its neighbors. The vertices in $A$ …
Our input is a bipartite graph $G = (A \cup B,E)$ where each vertex in $A \cup B$ has a preference list strictly ranking its neighbors. The vertices in $A$ and in $B$ are called students and courses, respectively. Each student $a$ seeks to be matched to $\mathsf{cap}(a) \ge 1$ courses while each course $b$ seeks $\mathsf{cap}(b) \ge 1$ many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in $G$ in linear time. We consider the problem of computing a popular matching in $G$ -- a matching $M$ is popular if $M$ cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in $G$ can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.
This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need …
This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts. We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.
We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: in particular, every $a \in A$ ranks its …
We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: in particular, every $a \in A$ ranks its neighbors in a strict order of preference, whereas the preference lists of $b \in B$ may contain ties. A matching $M$ is popular if there is no matching $M'$ such that the number of vertices that prefer $M'$ to $M$ exceeds the number of vertices that prefer $M$ to~$M'$. We show that the problem of deciding whether $G$ admits a popular matching or not is NP-hard. This is the case even when every $b \in B$ either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each $b \in B$ puts all its neighbors into a single tie. That is, all neighbors of $b$ are tied in $b$'s list and $b$ desires to be matched to any of them. Our main result is an $O(n^2)$ algorithm (where $n = |A \cup B|$) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in $B$ have no preferences and do not care whether they are matched or not.
Given a bipartite graph G = (A u B, E) with strict preference lists and and edge e*, we ask if there exists a popular matching in G that contains …
Given a bipartite graph G = (A u B, E) with strict preference lists and and edge e*, we ask if there exists a popular matching in G that contains the edge e*. We call this the popular edge problem. A matching M is popular if there is no matching M' such that the vertices that prefer M' to M outnumber those that prefer M to M'. It is known that every stable matching is popular; however G may have no stable matching with the edge e* in it. In this paper we identify another natural subclass of popular called matchings and show that if there is a popular matching that contains the edge e*, then there is either a stable matching that contains e* or a dominant matching that contains e*. This allows us to design a linear time algorithm for the popular edge problem. We also use dominant to efficiently test if every popular matching in G is stable or not.
Given a bipartite graph G = (A u B, E) with strict preference lists and and edge e*, we ask if there exists a popular matching in G that contains …
Given a bipartite graph G = (A u B, E) with strict preference lists and and edge e*, we ask if there exists a popular matching in G that contains the edge e*. We call this the popular edge problem. A matching M is popular if there is no matching M' such that the vertices that prefer M' to M outnumber those that prefer M to M'. It is known that every stable matching is popular; however G may have no stable matching with the edge e* in it. In this paper we identify another natural subclass of popular matchings called "dominant matchings" and show that if there is a popular matching that contains the edge e*, then there is either a stable matching that contains e* or a dominant matching that contains e*. This allows us to design a linear time algorithm for the popular edge problem. We also use dominant matchings to efficiently test if every popular matching in G is stable or not.
Given an undirected $n$-node unweighted graph $G = (V, E)$, a spanner with stretch function $f(\cdot)$ is a subgraph $H\subseteq G$ such that, if two nodes are at distance $d$ …
Given an undirected $n$-node unweighted graph $G = (V, E)$, a spanner with stretch function $f(\cdot)$ is a subgraph $H\subseteq G$ such that, if two nodes are at distance $d$ in $G$, then they are at distance at most $f(d)$ in $H$. Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function.
In this paper we study pairwise spanners, where we require to approximate the $u$-$v$ distance only for pairs $(u,v)$ in a given set $\cP \subseteq V\times V$. Such $\cP$-spanners were studied before [Coppersmith,Elkin'05] only in the special case that $f(\cdot)$ is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers).
Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same $\cP$) and of the best known spanners (with the same $f(\cdot)$). In more detail, for arbitrary $\cP$, we show that there exists a $\mathcal{P}$-spanner of size $O(n(|\cP|\log n)^{1/4})$ with $f(d)=d+4\log n$. Alternatively, for any $\eps>0$, there exists a $\cP$-spanner of size $O(n|\cP|^{1/4}\sqrt{\frac{\log n}{\eps}})$ with $f(d)=(1+\eps)d+4$. We also consider the relevant special case that there is a critical set of nodes $S\subseteq V$, and we wish to approximate either the distances within nodes in $S$ or from nodes in $S$ to any other node. We show that there exists an $(S\times S)$-spanner of size $O(n\sqrt{|S|})$ with $f(d)=d+2$, and an $(S\times V)$-spanner of size $O(n\sqrt{|S|\log n})$ with $f(d)=d+2\log n$. All the mentioned pairwise spanners can be constructed in polynomial time.
We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: In particular, every $a \in A$ ranks its …
We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: In particular, every $a \in A$ ranks its neighbors in a strict order of preference, whereas the preference list of any $b \in B$ may contain ties. A matching $M$ is popular if there is no matching $M'$ such that the number of vertices that prefer $M'$ to $M$ exceeds the number of vertices that prefer $M$ to $M'$. We show that the problem of deciding whether $G$ admits a popular matching or not is $\mathsf{NP}$-hard. This is the case even when every $b \in B$ either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each $b \in B$ puts all its neighbors into a single tie. That is, all neighbors of $b$ are tied in $b$'s list and $b$ desires to be matched to any of them. Our main result is an $O(n^2)$ algorithm (where $n = |A \cup B|$) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in $B$ have no preferences and do not care whether they are matched or not.
We consider the max-size popular matching problem in a roommates instance G = (V,E) with strict preference lists. A matching M is popular if there is no matching M' in …
We consider the max-size popular matching problem in a roommates instance G = (V,E) with strict preference lists. A matching M is popular if there is no matching M' in G such that the vertices that prefer M' to M outnumber those that prefer M to M'. We show it is NP-hard to compute a max-size popular matching in G. This is in contrast to the tractability of this problem in bipartite graphs where a max-size popular matching can be computed in linear time. We define a subclass of max-size popular matchings called strongly dominant matchings and show a linear time algorithm to solve the strongly dominant matching problem in a roommates instance. We consider a generalization of the max-size popular matching problem in bipartite graphs: this is the max-weight popular matching problem where there is also an edge weight function w and we seek a popular matching of largest weight. We show this is an NP-hard problem and this is so even when w(e) is either 1 or 2 for every edge e. We also show an algorithm with running time O*(2^{n/4}) to find a max-weight popular matching matching in G = (A U B,E)$ on n vertices.
We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of …
We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs: they always exist and there is a simple linear time algorithm to find one.We show that it is NP-complete to decide if a bipartite graph admits a popular matching that is neither stable nor dominant. This gives rise to the anomaly that though it is easy to find min-size and max-size popular matchings in bipartite graphs, it is NP-complete to decide if there exists any popular matching whose size is sandwiched between the two extremes. We also show a number of related hardness results, such as (tight) 1/2-inapproximability of the maximum cost popular matching problem when costs are nonnegative. In non-bipartite graphs, we show a strong negative result: it is NP-hard to decide whether a popular matching exists or not, and the same result holds if we replace popular with dominant. On the positive side, we show the following results in any graph:•we identify a subclass of dominant matchings called strongly dominant matchings and show a linear time algorithm to decide if a strongly dominant matching exists or not;•we show an efficient algorithm to compute a popular matching of minimum cost in a graph with edge costs and bounded treewidth, or decide there is no popular matching.
An input to the Popular Matching problem, in the roommates setting, consists of a graph G where each vertex ranks its neighbors in strict order, known as its preference. In …
An input to the Popular Matching problem, in the roommates setting, consists of a graph G where each vertex ranks its neighbors in strict order, known as its preference. In the Popular Matching problem the objective is to test whether there exists a matching M* such that there is no matching M where more people (vertices) are happier (in terms of the preferences) with M than with M*. In this paper we settle the computational complexity of the Popular Matching problem in the roommates setting by showing that the problem is NP-complete. Thus, we resolve an open question that has been repeatedly and explicitly asked over the last decade.
Liquid democracy is a proxy voting method where proxies are delegable. We propose and study a game-theoretic model of liquid democracy to address the following question: when is it rational …
Liquid democracy is a proxy voting method where proxies are delegable. We propose and study a game-theoretic model of liquid democracy to address the following question: when is it rational for a voter to delegate her vote? We study the existence of pure-strategy Nash equilibria in this model, and how group accuracy is affected by them. We complement these theoretical results by means of agent-based simulations to study the effects of delegations on group’s accuracy on variously structured social networks.
The paper provides an analysis of the voting method known as delegable proxy voting, or liquid democracy. The analysis first positions liquid democracy within the theory of binary aggregation. It …
The paper provides an analysis of the voting method known as delegable proxy voting, or liquid democracy. The analysis first positions liquid democracy within the theory of binary aggregation. It then focuses on two issues of the system: the occurrence of delegation cycles; and the effect of delegations on individual rationality when voting on logically interdependent propositions. It finally points to proposals on how the system may be modified in order to address the above issues.
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of …
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all ε>0, there is a constant kε such that every graph has a spanner on O(n1+ε) edges that preserves its pairwise distances up to +kε? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have +2 spanners on O(n3/2) edges, +4 spanners on Õ(n7/5) edges, and +6 spanners on O(n4/3) edges. However, progress has mysteriously halted at the n4/3 bound, and despite significant effort from the community, the question has remained open for all 0 < ε < 1/3.
Given an undirected $n$-node unweighted graph $G = (V, E)$, a spanner with stretch function $f(\cdot)$ is a subgraph $H\subseteq G$ such that, if two nodes are at distance $d$ …
Given an undirected $n$-node unweighted graph $G = (V, E)$, a spanner with stretch function $f(\cdot)$ is a subgraph $H\subseteq G$ such that, if two nodes are at distance $d$ in $G$, then they are at distance at most $f(d)$ in $H$. Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function.
In this paper we study pairwise spanners, where we require to approximate the $u$-$v$ distance only for pairs $(u,v)$ in a given set $\cP \subseteq V\times V$. Such $\cP$-spanners were studied before [Coppersmith,Elkin'05] only in the special case that $f(\cdot)$ is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers).
Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same $\cP$) and of the best known spanners (with the same $f(\cdot)$). In more detail, for arbitrary $\cP$, we show that there exists a $\mathcal{P}$-spanner of size $O(n(|\cP|\log n)^{1/4})$ with $f(d)=d+4\log n$. Alternatively, for any $\eps>0$, there exists a $\cP$-spanner of size $O(n|\cP|^{1/4}\sqrt{\frac{\log n}{\eps}})$ with $f(d)=(1+\eps)d+4$. We also consider the relevant special case that there is a critical set of nodes $S\subseteq V$, and we wish to approximate either the distances within nodes in $S$ or from nodes in $S$ to any other node. We show that there exists an $(S\times S)$-spanner of size $O(n\sqrt{|S|})$ with $f(d)=d+2$, and an $(S\times V)$-spanner of size $O(n\sqrt{|S|\log n})$ with $f(d)=d+2\log n$. All the mentioned pairwise spanners can be constructed in polynomial time.
We study the broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size $n$ can send the …
We study the broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size $n$ can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized $(2+o(1))$-approximation algorithm to compute all pairs shortest paths (APSP) in time $\tilde{O}(\sqrt{n})$ on weighted graphs, where we use the convention that $\tilde{\Omega}(f(n))$ is essentially $\Omega(f(n)/$polylog$f(n))$ and $\tilde{O}(f(n))$ is essentially $O(f(n) $polylog$f(n))$. We complement this result by proving that any randomized $(2-o(1))$-approximation of APSP and $(2-o(1))$-approximation of the diameter of a graph takes $\tilde\Omega(n)$ time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a $(2-o(1))$-approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST CLIQUE model and contrasts a recent $(1+o(1))$-approximation for APSP that runs in time $O(n^{0.15715})$ in the unicast version of the CONGEST CLIQUE model. On the positive side we provide a deterministic version of Nanongkai's $(2+o(1))$-approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model presented by Lenzen and Peleg at PODC'13.
A fundamental problem in distributed network algorithms is to manage congestion and obtain information flow matching the graph's connectivity. In this paper, we present time-efficient distributed algorithms for decomposing graphs …
A fundamental problem in distributed network algorithms is to manage congestion and obtain information flow matching the graph's connectivity. In this paper, we present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. These decompositions allow us to achieve a flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: - A decomposition of each undirected graph with vertex-connectivity k into (fractionally) vertex-disjoint weighted dominating trees with total weight Ω(k/log n), in ~O(D+√n) rounds. - A decomposition of each undirected graph with edge-connectivity λ into (fractionally) edge-disjoint weighted spanning trees with total weight ⌈λ-1/2⌉(1-ε), in ~{O}(D+√nλ) rounds.
We study the problem of assigning jobs to applicants. Each applicant has a weight and provides a preference list , which may contain ties, ranking a subset of the jobs. …
We study the problem of assigning jobs to applicants. Each applicant has a weight and provides a preference list , which may contain ties, ranking a subset of the jobs. An applicant x may prefer one matching to another (or be indifferent between them, in case of a tie) based on the jobs x gets in the two matchings and x ’s personal preference. A matching M is popular if there is no other matching M ′ such that the weight of the applicants who prefer M ′ to M exceeds the weight of those who prefer M to M ′. We present algorithms to find a popular matching, or if none exists, to establish so. For instances with strict preference lists, we give an O ( n + m time algorithm. For preference lists with ties, we give a more involved algorithm that solves the problem in O (min ( k √ n ;, n ) m ) time, where k is the number of distinct weights the applicants are given.
We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity …
We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth.
We present two algorithms for maintaining the topological order of a directed acyclic graph with n vertices, under an online edge insertion sequence of m edges. Efficient algorithms for online …
We present two algorithms for maintaining the topological order of a directed acyclic graph with n vertices, under an online edge insertion sequence of m edges. Efficient algorithms for online topological ordering have many applications, including online cycle detection, which is to discover the first edge that introduces a cycle under an arbitrary sequence of edge insertions in a directed graph. In this paper we present efficient algorithms for the online topological ordering problem. We first present a simple algorithm with running time O(n^{5/2}) for the online topological ordering problem. This is the current fastest algorithm for this problem on dense graphs, i.e., when m > n^{5/3}. We then present an algorithm with running time O((m + nlog n)\sqrt{m}); this is more efficient for sparse graphs. Our results yield an improved upper bound of O(min(n^{5/2}, (m + nlog n)sqrt{m})) for the online topological ordering problem.
Let [Formula: see text] be an instance of the stable marriage problem in which every vertex ranks its neighbors in a strict order of preference. A matching [Formula: see text] …
Let [Formula: see text] be an instance of the stable marriage problem in which every vertex ranks its neighbors in a strict order of preference. A matching [Formula: see text] in [Formula: see text] is popular if [Formula: see text] does not lose a head-to-head election against any matching. Popular matchings generalize stable matchings. Unfortunately, when there are edge costs, to find or even approximate up to any factor a popular matching of minimum cost is NP-hard. Let [Formula: see text] be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most [Formula: see text] by paying the price of mildly relaxing popularity. Our main positive results are two bicriteria algorithms that find in polynomial time a “quasi-popular” matching of cost at most [Formula: see text]. Moreover, one of the algorithms finds a quasi-popular matching of cost at most that of a min-cost popular fractional matching, which could be much smaller than [Formula: see text]. Key to the other algorithm is a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity.
A popular method in combinatorial optimization is to express polytopes P , which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to …
A popular method in combinatorial optimization is to express polytopes P , which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so-called extension complexity , which for a polytope P denotes the smallest number of inequalities necessary to describe a higher-dimensional polytope Q that can be linearly projected on P . However, the central question in this field remained wide open: can the perfect matching polytope be written as an LP with polynomially many constraints? We answer this question negatively. In fact, the extension complexity of the perfect matching polytope in a complete n -node graph is 2 Ω ( n ) . By a known reduction, this also improves the lower bound on the extension complexity for the TSP polytope from 2 Ω (√ n ) to 2 Ω ( n ) .
We study the verification problem in distributed networks, stated as follows. Let $H$ be a subgraph of a network $G$ where each vertex of $G$ knows which edges incident on …
We study the verification problem in distributed networks, stated as follows. Let $H$ be a subgraph of a network $G$ where each vertex of $G$ knows which edges incident on it are in $H$. We would like to verify whether $H$ has some properties, e.g., if it is a tree or if it is connected (every node knows at the end of the process whether $H$ has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. In this paper we initiate a systematic study of distributed verification and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and $s$-$t$ cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree (MST), shortest paths, and minimum cut. Many of these results are the first nontrivial lower bounds for both exact and approximate distributed computation, and they resolve previous open questions. Moreover, our unconditional lower bound of approximating MST subsumes and improves upon the previous hardness of approximation bound of Elkin [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [D. Peleg and V. Rubinovich, SIAM J. Comput., 30 (2000), pp. 1427--1442]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm for any approximation factor. Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computation of many problems.
Abstract Given a graph G = (V, E) , a subgraph Gapos; = (V, Eapos;) is a t‐ spanner of G if for every u, v ∈ V , the …
Abstract Given a graph G = (V, E) , a subgraph Gapos; = (V, Eapos;) is a t‐ spanner of G if for every u, v ∈ V , the distance from u to v in Gapos; is at most t times longer than that distance in G. This paper presents some results concerning the existence and efficient constructability of sparse spanners for various classes of graphs, including general undirected graphs, undirected chordal graphs, and general directed graphs.
We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin …
We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focussed on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee.
Let $G$ be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching …
Let $G$ be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching $B$ is if $B$ does not lose a head-to-head election (where nodes cast votes) against any branching. Such branchings have a natural application in liquid democracy. The branching problem is to decide if $G$ admits a branching or not. We give a characterization of branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the branching problem. When preferences are weak rankings, we use our characterization to formulate the branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that approximately popular branchings always exist.
We make improvements to the upper bounds on several popular types of distance preserving graph sketches. The first part of our paper concerns pairwise distance preservers, which are sparse subgraphs …
We make improvements to the upper bounds on several popular types of distance preserving graph sketches. The first part of our paper concerns pairwise distance preservers, which are sparse subgraphs that exactly preserve the pairwise distances for a set of given pairs of vertices. Our main result here is that all unweighted, undirected n-node graphs G and all pair sets P have distance preservers on |H| = O(n2/3|P|2/3 + n|P|1/3) edges. This improves the known bounds whenever |P| = ω(n3/4).We then develop a new graph clustering technique, based on distance preservers, and we apply this technique to show new upper bounds for additive (standard) spanners, in which all pairwise distances must be preserved up to an additive error function, and for subset spanners, in which only distances within a given node subset must be preserved up to an error function. For both of these objects, we obtain the new best tradeoff between spanner sparsity and error allowance in the regime where the error is polynomial in the graph size.We leave open a conjecture that O(n2/3|P|2/3 + n) pairwise distance preservers are possible for undirected unweighted graphs. Resolving this conjecture in the affirmative would improve and simplify our upper bounds for all the graph sketches mentioned above.
We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin …
We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share , which is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations, a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee. Furthermore, we initiate the study of approximate maximin fair division under submodular valuations . Specifically, we show that when the valuations of the agents are nonnegative , monotone , and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the article is to analyze the performance of this combinatorial algorithm by employing the concept of multilinear extensions .
We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if …
We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. In addition, an allocation is deemed efficient if it satisfies Pareto efficiency. While each of these well-studied properties is easy to achieve separately, achieving them together is far from obvious. Recently, Caragiannis et al. (2016) established the surprising result that when agents have additive valuations for the goods, there always exists an allocation that simultaneously satisfies these two seemingly incompatible properties. Specifically, they showed that an allocation that maximizes the Nash social welfare objective is both EF1 and Pareto efficient. However, the problem of maximizing Nash social welfare is NP-hard. As a result, this approach does not provide an efficient algorithm for finding a fair and efficient allocation. In this paper, we bypass this barrier, and develop a pseudopolynomial time algorithm for finding allocations that are EF1 and Pareto efficient; in particular, when the valuations are bounded, our algorithm finds such an allocation in polynomial time. Furthermore, we establish a stronger existence result compared to Caragiannis et al. (2016): For additive valuations, there always exists an allocation that is EF1 and fractionally Pareto efficient. Another key contribution of our work is to show that our algorithm provides a polynomial-time 1.45-approximation to the Nash social welfare objective. This improves upon the best known approximation ratio for this problem (namely, the 2-approximation algorithm of Cole et al., 2017), and also matches the lower bound on the integrality gap of the convex program of Cole et al. (2017). Unlike many of the existing approaches, our algorithm is completely combinatorial, and relies on constructing integral Fisher markets wherein specific equilibria are not only efficient, but also fair.
We present an on-line algorithm for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our algorithm takes …
We present an on-line algorithm for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our algorithm takes O(m^{1/2}) amortized time per arc, where m is the total number of arcs. For sparse graphs, this bound improves the best previous bound by a logarithmic factor and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the bidirectional search method of previous algorithms does not require an ordered search, but can be more general. This allows us to avoid the use of heaps (priority queues) entirely. Instead, the deterministic version of our algorithm uses (approximate) median-finding. The randomized version of our algorithm avoids this complication, making it very simple. We extend our topological ordering algorithm to give the first detailed algorithm for maintaining the strong components of a directed graph, and a topological order of these components, as arcs are added. This extension also has an amortized time bound of O(m^{1/2}) per arc.
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Quasi-popular Matchings, Optimality, and Extended FormulationsYuri Faenza and Telikepalli KavithaYuri Faenza and Telikepalli Kavithapp.325 - …
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Quasi-popular Matchings, Optimality, and Extended FormulationsYuri Faenza and Telikepalli KavithaYuri Faenza and Telikepalli Kavithapp.325 - 344Chapter DOI:https://doi.org/10.1137/1.9781611975994.20PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Let G = (A ∪ B, E) be an instance of the stable marriage problem where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if M does not lose a head-to-head election against any matching. Popular matchings are a well-studied generalization of stable matchings, introduced with the goal of enlarging the set of admissible solutions, while maintaining a certain level of fairness. Every stable matching is a min-size popular matching. Unfortunately, when there are edge costs, it is NP-hard to find a popular matching of minimum cost – even worse, the min-cost popular matching problem is hard to approximate up to any factor. Let opt be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most opt by paying the price of mildly relaxing popularity. Our main positive result is a bi-criteria algorithm that finds in polynomial time a near-popular or "quasi-popular" matching of cost at most opt. Key to the algorithm are a number of results for certain polytopes related to matchings. In particular, we give a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost, and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011
The goal of fair division is to distribute resources among competing players in a “fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do …
The goal of fair division is to distribute resources among competing players in a “fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.
We give a new characterization of those topologies which have an immediate successor or cover in the lattice of T1-topologies on a set and show that certain classes of compact …
We give a new characterization of those topologies which have an immediate successor or cover in the lattice of T1-topologies on a set and show that certain classes of compact and countably compact topologies do not have covers.
A randomised approximation scheme for the permanent of a 0–1s presented. The task of estimating a permanent is reduced to that of almost uniformly generating perfect matchings in a graph; …
A randomised approximation scheme for the permanent of a 0–1s presented. The task of estimating a permanent is reduced to that of almost uniformly generating perfect matchings in a graph; the latter is accomplished by simulating a Markov chain whose states are the matchings in the graph. For a wide class of 0–1 matrices the approximation scheme is fully-polynomial, i.e., runs in time polynomial in the size of the matrix and a parameter that controls the accuracy of the output. This class includes all dense matrices (those that contain sufficiently many 1's) and almost all sparse matrices in some reasonable probabilistic model for 0–1 matrices of given density. For the approach sketched above to be computationally efficient, the Markov chain must be rapidly mixing: informally, it must converge in a short time to its stationary distribution. A major portion of the paper is devoted to demonstrating that the matchings chain is rapidly mixing, apparently the first such result for a Markov chain with genuinely complex structure. The techniques used seem to have general applicability, and are applied again in the paper to validate a fully-polynomial randomised approximation scheme for the partition function of an arbitrary monomer-dimer system.