Search

Efficient computability is an important property of solution concepts. We consider the computational complexity of finding and verifying various solution concepts in trading networks—multi-sided matching markets with bilateral contracts and without transferable utility—under the assumption of full substitutability of agents' preferences. It is known that outcomes that satisfy trail stability always exist and can be found in linear time. However, we show that the existence of stable outcomes—immune to deviations by arbitrary sets of agents—is an N P -hard problem in trading networks. We also show that even verifying whether a given outcome is stable is N P -hard in trading networks. [ABSTRACT FROM AUTHOR]

We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game-including monotonic minimum cost spanning tree games-can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the associated DAG-game. We introduce a network canonization process and prove various structural results for the core of canonized DAG-games. In particular, we characterize classes of coalitions that have a constant payoff in the core. In addition, we identify a subset of the coalitions that is sufficient to determine the core. This result also guarantees that the nucleolus can be found in polynomial time for a large class of DAG-games. [ABSTRACT FROM AUTHOR]

We consider Pareto optimal matchings (POMs) in a many-to-many market of applicants and courses where applicants have preferences, which may include ties, over individual courses and lexicographic preferences over sets of courses. Since this is the most general setting examined so far in the literature, our work unifies and generalizes several known results. Specifically, we characterize POMs and introduce the Generalized Serial Dictatorship Mechanism with Ties (GSDT) that effectively handles ties via properties of network flows. We show that GSDT can generate all POMs using different priority orderings over the applicants, but it satisfies truthfulness only for certain such orderings. This shortcoming is not specific to our mechanism; we show that any mechanism generating all POMs in our setting is prone to strategic manipulation. This is in contrast to the one-to-one case (with or without ties), for which truthful mechanisms generating all POMs do exist. [ABSTRACT FROM AUTHOR]

Scarf's algorithm (Scarf, H. E. Econometrica 35, 50-69 1967) provides fractional core elements for NTU-games. Biró and Fleiner [4] showed that Scarf's algorithm can be extended for capacitated NTU-games. In this setting agents can be involved in more than one coalition at a time, cooperations may be performed with different intensities up to some limits, and the contribution of the agents can also differ in a coalition. The fractional stable solutions for the above model, produced by the extended Scarf algorithm, are called stable allocations. In this paper we apply this solution concept for the Hospitals / Residents problem with Couples (HRC). This is one of the most important general stable matching problems due to its relevant applications, also well-known to be NP-hard. We show that if a stable allocation yielded by the Scarf algorithm turns out to be integral then it provides a stable matching for an instance of HRC, so this method can be used as a heuristic. In an experimental study, we compare this method with other heuristics constructed for HRC that have been applied in practice in the American and Scottish resident allocation programs, respectively. Our main finding is that the Scarf algorithm outperforms all the other known heuristics when the proportion of couples is high. [ABSTRACT FROM AUTHOR]

A recent result of Aharoni Berger and Gorelik (Order 31(1), 35-43, ) is a weighted generalization of the well-known theorem of Sands Sauer and Woodrow (Theory Ser. B 33(3), 271-275, ) on monochromatic paths. The authors prove the existence of a so called weighted kernel for any pair of weighted posets on the same ground set. In this work, we point out that this result is closely related to the stable marriage theorem of Gale and Shapley (Amer. Math. Monthly 69(1), 9-15, ), and we generalize Blair's theorem by showing that weighted kernels form a lattice under a certain natural order. To illustrate the applicability of our approach, we prove further weighted generalizations of the Sands Sauer Woodrow result. [ABSTRACT FROM AUTHOR]

We prove an extension of Galvin's theorem, namely that any graph is L-edge-choosable if |L(e)|≥χ′(G) and the edge-lists of no odd cycle contain a common colour. [ABSTRACT FROM AUTHOR]

Several countries successfully use centralized matching schemes for assigning students to study places or fresh graduates to their first positions. In this paper we explore the computational aspects of a possible similar scheme for assigning trainee teachers to schools. Our model is motivated by the situation characteristic for Slovak and Czech education system where each pre-service teacher specializes in two subjects. We show that if the two subjects can be performed independently in two different schools, then a feasible assignment can be found efficiently by employing network flow techniques. By contrast, the requirement to perform both subjects at the same school leads to intractable problems even under several strict restrictions concerning the total number of subjects, partial capacities of schools and the number of acceptable schools each teacher is allowed to list. Finally, we report on an integer programming model for solving the 'inseparable subjects' case of the teachers assignment problem and the results of its application to real data. [ABSTRACT FROM AUTHOR]

Peer evaluation of research grant applications is a crucial step in the funding decisions of many science funding agencies. Funding bodies take various measures to increase the independence and quality of this process, sometimes leading to difficult combinatorial problems. We propose a novel method based on network flow theory to find assignments of evaluators to grant applications that obey the rules formulated by the Slovak Research and Development Agency. [ABSTRACT FROM AUTHOR]

In this paper, we study a many-to-many matching model with contracts. We extend the economic model of Hatfield and Milgrom by allowing a partial order on the possible bilateral contracts of the agents in a two-sided market economy. To prove that a generalized stable allocation exists, we use generalized form of properties like path-independence and substitutability. The key to our results is the well-known lattice theoretical fixed point theorem of Tarski. The constructive proof of this fixed point theorem for finite sets turns out to be the appropriate generalization of the Gale-Shapley algorithm also in our general setting. [ABSTRACT FROM AUTHOR]

Housing market is a special type of exchange economy where each agent is endowed with one unit of an indivisible good (house) and wants to end up again with one unit, possibly the best one according to his preferences. If the endowments of all agents are pairwise different, an equilibrium as well as a core allocation always exist. However, for markets in which some agents’ houses are equivalent, the existence problem for the economic equilibrium is NP-complete. In this paper we show that the hardness result is not valid if the preferences of all agents are strict, but it remains true in markets with trichotomous preferences. Further, we extend some known results about housing markets to the case with equivalent houses using graph-theoretical methods. [ABSTRACT FROM AUTHOR]

The stable marriage theorem of Gale and Shapley states that for n men and n women there always exists a stable marriage scheme, that is, a set of marriages such that no man and woman mutually prefer one another to their partners. The stable marriage theorem was generalized in two directions: the stable roommates problem is the “one-sided” version, where any two agents on the market can form a partnership. The generalization by Kelso and Crawford is in the “two-sided” model, but on one side of the market agents have a so-called substitutable choice function, and stability is interpreted in a natural way. It turned out that even if both sides of the market have substitutable choice functions, there still exists a stable assignment. The latter version contains the “many-to-many” model where up to a personal quota, polygamy is allowed for both men and women in the two-sided market. The goal of this work is to solve the stable partnership problem, a generalization of the one-sided model with substitutable choice functions. We do not quite reach that: besides substitutability, we also need for the result the so called increasing property (or, in other terminology, the law of aggregate demand). Luckily, choice functions in well-known stable matching theorems comply with this property. The main result is a generalization of Irving’s algorithm, the first efficient method to solve the stable roommates problem. We deduce from the algorithm a generalization of Tan’s result on characterizing the existence of a stable matching and prove a generalization of the rural hospital theorem and the so-called splitting property of many-to-many stable matchings. We show that our algorithm is linear-time in some sense and indicate that for general (i.e. not necessarily increasing) substitutable choice functions the stable partnership problem is NP-complete. [ABSTRACT FROM AUTHOR]

We study the dynamics of stable marriage and stable roommates markets. Our main tool is the incremental algorithm of Roth and Vande Vate and its generalization by Tan and Hsueh. Beyond proposing alternative proofs for known results, we also generalize some of them to the nonbipartite case. In particular, we show that the lastcomer gets his best stable partner in both incremental algorithms. Consequently, we confirm that it is better to arrive later than earlier to a stable roommates market. We also prove that when the equilibrium is restored after the arrival of a new agent, some agents will be better off under any stable solution for the new market than at any stable solution for the original market. We also propose a procedure to find these agents. [ABSTRACT FROM AUTHOR]

We give a short and simple proof for the theorem that the size of a 3-cross-free family is linear in the size of the groundset. A family is 3-cross-free if it has no 3 pairwise crossing members. [ABSTRACT FROM AUTHOR]

Frank and Jordán [1] proved an important min-max result on covering a crossing family of set-pairs. As an application, among others they can solve the unweighted node-connectivity augmentation problem for directed graphs in polynomial time. In this paper, we show how to solve the dual packing problem in polynomial time. To decompose a fractional dual optimum as a convex combination of integer vertices, besides the ellipsoid method, we use a polynomial-time algorithm for uncrossing a family of set-pairs. Our main result is this uncrossing algorithm. [ABSTRACT FROM AUTHOR]

Abstract. Let F be a symmetric and crossing family of subsets of V. Our first result is a min-max equality for the size of a smallest family K of k-element subsets of V which covers each member of F, where X is an element of F is said to be covered by Y is an element of K if X Intersection Y is not equal to 0 is not equal to Y - X. Our formula generalizes, among others, a recent result of Cheng on optimally augmenting the edge-connectivity of a hypergraph by one. The second problem we consider is to find a compact representation of F. We prove that there exists a so-called hypercactus K of size O(|V|), consisting of cycles and (hyper)edges arranged in a tree-like manner, and a mapping from V to V(K) in such a way that there is a bijection between the minimum cuts of K and the members of F. If F corresponds to the minimum cuts of a k-edge-connected graph then K reduces to the well-known cactus representation of minimum cuts due to Dinitz et al. [ABSTRACT FROM AUTHOR]

We prove a min-max result on special partially ordered sets, a conjecture of András Frank. As corollaries we deduce Dilworth's theorem and the well-known min-max formula for the minimum size edge cover of a graph. [ABSTRACT FROM AUTHOR]