Conference presentations at the Workshop on EFFICIENT ALGORITHMS, AUTOMATA AND DATA STRUCTURES:
Péter Biró: Complexity of finding Pareto-efficient allocations of highest welfare
We allocate objects to agents as exemplified primarily by school choice. Welfare judgments of the object-allocating agency are encoded as edge weights in the acceptability graph. In this way, the welfare of an allocation is the sum of its weights. We introduce the constrained welfare-maximizing solution, which is given by the allocation of highest welfare among the Pareto-efficient allocations. From a computational point of view, we identify conditions under which this solution is easily determined. For the general, unrestricted case, we formulate an integer program. We find that this is a viable option in practice, solving a real-world instance quickly. Incentives to report preferences truthfully is discussed briefly.
Tamás Fleiner: The complexity of cake cutting with unequal shares
We study the complexity of a particular proportional division problem. On one hand, we offer an efficient protocol and on the other hand, we prove a lower bound on the complexity, as well. The robustness of our approach is illustrated by the fact that it can be extended to a more general division model in a straightforward way. We also present a method that guarantees proportional division in case of demands with irrational ratio. Joint work with Agnes Cseh.
Ágnes Cseh: Popular matchings in complete graphs
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. Joint work with T. Kavitha.
Attila Juhos: Pairwise preferences in the stable marriage problem
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability—weak, strong and super-stability—under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.
