1,357,607 research outputs found
Hardness Results for Consensus-Halving
No full textThe Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in [Filos-Ratsikas and Goldberg, 2018] that the problem of computing an epsilon-approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n-1 cuts exists for the problem is NP-hard
Peeking behind the ordinal curtain: Improving distortion via cardinal queries
No full textAggregating the preferences of individuals into a collective decision is the core subject of study of social choice theory. In 2006, Procaccia and Rosenschein considered a utilitarian social choice setting, where the agents have explicit numerical values for the alternatives, yet they only report their linear orderings over them. To compare different aggregation mechanisms, Procaccia and Rosenschein introduced the notion of distortion, which quantifies the inefficiency of using only ordinal information when trying to maximize the social welfare, i.e., the sum of the underlying values of the agents for the chosen outcome. Since then, this research area has flourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents over the alternatives. In this paper, we take a more expressive approach, and consider mechanisms that are allowed to further ask a few cardinal queries in order to gain partial access to the underlying values that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms that achieve significantly improved distortion bounds and, in many cases, outperform the best-known randomized ordinal mechanisms. We paint an almost complete picture of the number of queries required by deterministic mechanisms to achieve specific distortion bounds
Fair Division of Indivisible Goods: A Survey
No full textAllocating resources to individuals in a fair manner has been a topic of interest since the ancient times, with most of the early rigorous mathematical work on the problem focusing on infinitely divisible resources. Recently, there has been a surge of papers studying computational questions regarding various different notions of fairness for the indivisible case, like maximin share fairness (MMS) and envy-freeness up to any good (EFX). We survey the most important results in the discrete fair division literature, focusing on the case of additive valuation functions and paying particular attention to the progress made in the last 10 years
Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
No full textIn most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitably leads to poor performance with respect to optimizing a cardinal objective, such as the social welfare, since the values of the agents remain virtually unknown. This loss in performance because of lack of information is measured by the notion of distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make better-informed decisions, thus improving distortion. Following this agenda, in this work we focus on a class of combinatorial problems that includes most well-known matching problems and several of their generalizations, such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and kConstrained Resource Allocation. We design two-query mechanisms that achieve the best-possible worst-case distortion in terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms
Consensus-halving: does it ever get easier?
No full textIn the ε-Consensus-Halving problem, a fundamental problem in fair division, there are n agents with valuations over the interval [0,1], and the goal is to divide the interval into pieces and assign a label “+” or “−” to each piece, such that every agent values the total amount of “+” and the total amount of “−” almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg [Proceedings of the 50th Annual ACM Symposium on Theory of Computing, 2018, pp. 51–64; Proceedings of the 51st Annual ACM Symposium on Theory of Computing, 2019, pp. 638–649] to be the first “natural” complete problem for the computational class PPA, answering a decade-old open question. In this paper, we examine the extent to which the problem becomes easy to solve if one restricts the class of valuation functions. To this end, we provide the following contributions. First, we obtain a strengthening of the PPA-hardness result of Filos-Ratsikas and Goldberg [Proceedings of the 51st Annual ACM Symposium on Theory of Computing, 2019, pp. 638–649] to the case when agents have piecewise uniform valuations with only two blocks. We obtain this result via a new reduction, which is in fact conceptually much simpler than the corresponding one in Filos-Ratsikas and Goldberg [Proceedings of the 51st Annual ACM Symposium on Theory of Computing, 2019, pp. 638–649]. Then, we consider the case of single-block (uniform) valuations and provide a parameterized polynomial-time algorithm for solving ε-Consensus-Halving for any ε, as well as a polynomial-time algorithm for ε=1/2. Finally, an important application of our new techniques is the first hardness result for a generalization of Consensus-Halving, the Consensus-1/k1-Division problem [F. W. Simmons and F. E. Su, Math. Social Sci., 45 (2003), pp. 15–25]. In particular, we prove that ε-Consensus-1/3-Division is PPAD-hard
A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
No full textWe consider the one-sided matching problem, where n agents have preferences over n items, and these preferences are induced by underlying cardinal valuation functions. The goal is to match every agent to a single item so as to maximize the social welfare. Most of the related literature, however, assumes that the values of the agents are not a priori known, and only access to the ordinal preferences of the agents over the items is provided. Consequently, this incomplete information leads to loss of efficiency, which is measured by the notion of distortion. In this paper, we further assume that the agents can answer a small number of queries, allowing us partial access to their values. We study the interplay between elicited cardinal information (measured by the number of queries per agent) and distortion for one-sided matching, as well as a wide range of well-studied related problems. Qualitatively, our results show that with a limited number of queries, it is possible to obtain significant improvements over the classic setting, where only access to ordinal information is given
The Pareto Frontier of Inefficiency in Mechanism Design
No full textWe study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms (formula presented) that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter (formula presented) across the frontier, between the First-Price (formula presented) and Second-Price (formula presented) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether non-truthful mechanisms can provide better makespan guarantees in the equilibrium, compared to truthful ones. We answer this question in the negative, by proving that the Price of Anarchy of all scheduling mechanisms is at least n, where n is the number of machines
The Pareto Frontier of Inefficiency in Mechanism Design
No full textWe study the trade-off between the price of anarchy (PoA) and the price of stability (PoS) in mechanism design in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to these metrics and observe that two fundamental mechanisms, namely the first price (FP) and the second price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms SPα that lie exactly on this frontier. In particular, these mechanisms range smoothly with respect to parameter α ≥ 1 across the frontier, between the first price (SP1) and second price (SP∞) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether nontruthful mechanisms can provide better makespan guarantees in the equilibrium compared with truthful ones. We answer this question in the negative by proving that the price of anarchy of all scheduling mechanisms is at least n, where n is the number of machines
On the Complexity of Equilibrium Computation in First-Price Auctions
No full textWe consider the problem of computing a (pure) Bayes-Nash equilibrium in the
first-price auction with continuous value distributions and discrete bidding
space. We prove that when bidders have independent subjective prior beliefs
about the value distributions of the other bidders, computing an
-equilibrium of the auction is PPAD-complete, and computing an
exact equilibrium is FIXP-complete. We also provide an efficient algorithm for
solving a special case of the problem, for a fixed number of bidders and
available bids.Comment: Journal version. Preliminary version appeared at EC '2
Peeking behind the ordinal curtain: Improving distortion via cardinal queries
No full textThe notion of distortion was introduced by Procaccia and Rosenschein (2006) to quantify the inefficiency of using only ordinal information when trying to maximize the social welfare. Since then, this research area has flourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents over the alternatives. In this paper, we take a more expressive approach, and consider mechanisms that are allowed to further ask a few cardinal queries in order to gain partial access to the underlying values that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms that achieve significantly improved distortion bounds and outperform the best-known randomized ordinal mechanisms. We draw an almost complete picture of the number of queries required to achieve specific distortion bounds
- …
