Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

There has been much work on exhibiting mechanisms that implement various bargaining solutions, in particular, the KalaiSmorodinsky solution \cite{moulin1984implementing} and the Nash Bargaining solution. Another wellknown and axiomatically wellstudied solution is the lexicographic maxmin solution. However, there is no mechanism known for its implementation. To fill this gap, we construct a mechanism that implements the lexicographic maxmin solution as the unique subgame perfect equilibrium outcome in the nplayer setting. As is standard in the literature on implementation of bargaining solutions, we use the assumption that any player can grab the entire surplus. Our mechanism consists of a binary game tree, with each node corresponding to a subgame where the players are allowed to choose between two outcomes. We characterize novel combinatorial properties of the lexicographic maxmin solution which are crucial to the design of our mechanism.more » « less

We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these costs are given by an underlying metric on the set of all agents plus alternatives. Social choice rules have access to only the ordinal preferences of agents but not the latent cardinal costs that induce them. Distortion is then defined as the ratio between the social cost (typically the sum of agent costs) of the alternative chosen by the mechanism at hand, and that of the optimal alternative chosen by an omniscient algorithm. The worstcase distortion of a social choice rule is, therefore, a measure of how close it always gets to the optimal alternative without any knowledge of the underlying costs. Under this model, it has been conjectured that Ranked Pairs, the wellknown weightedtournament rule, achieves a distortion of at most 3 (Anshelevich et al. 2015). We disprove this conjecture by constructing a sequence of instances which shows that the worstcase distortion of Ranked Pairs is at least 5. Our lower bound on the worstcase distortion of Ranked Pairs matches a previously known upper bound for the Copeland rule, proving that in the worst case, the simpler Copeland rule is at least as good as Ranked Pairs. And as long as we are limited to (weighted or unweighted) tournament rules, we demonstrate that randomization cannot help achieve an expected worstcase distortion of less than 3. Using the concept of approximate majorization within the distortion framework, we prove that Copeland and Randomized Dictatorship achieve low constant factor fairnessratios (5 and 3 respectively), which is a considerable generalization of similar results for the sum of costs and single largest cost objectives. In addition to all of the above, we outline several interesting directions for further research in this space.more » « less