We study an important crowdsourcing setting where agents evaluate one another and, based on these evaluations, a subset of agents are selected. This setting is ubiquitous when peer review is used for distributing awards in a team, allocating funding to scientists, and selecting publications for conferences. The fundamental challenge when applying crowdsourcing in these settings is that agents may misreport their reviews of others to increase their chances of being selected. We propose a new strategyproof (impartial) mechanism called Dollar Partition that satisfies desirable axiomatic properties. We then show, using a detailed experiment with parameter values derived from target real world domains, that our mechanism performs better on average, and in the worst case, than other strategyproof mechanisms in the literature.

We consider a strategic variant of the facility location problem. We would like to locate a facility on a closed interval. There are n agents located on that interval, divided into two types: type 1 agents, who wish for the facility to be as far from them as possible, and type 2 agents, who wish for the facility to be as close to them as possible. Our goal is to maximize a form of aggregated social benefit: maxisum– the sum of the agents’ utilities, or the egalitarian objective– the minimal agent utility. The strategic aspect of the problem is that the agents’ locations are not known to us, but rather reported to us by the agents– an agent might misreport his location in an attempt to move the facility away from or towards to his true location. We therefore require the facility-locating mechanism to be strategyproof, namely that reporting truthfully is a dominant strategy for each agent. As simply maximizing the social benefit is generally not strategyproof, our goal is to design strategyproof mechanisms with good approximation ratios. In this paper, we provide a best-possible 3approximate deterministic strategyproof mechanism, as well as a 23/13 approximate randomized strategyproof mechanism, both for the maxisum objective. We provide lower bounds of 3 and 3/2 on the approximation ratio attainable for maxisum, in the deterministic and randomized settings, respectively. For the egalitarian objective, we show that no bounded approximation ratio is attainable in the deterministic setting, and provide a lower bound of 3/2 for the randomized setting. To obtain our deterministic lower bounds, we characterize all deterministic strategyproof mechanisms when all agents are of type 1. Finally, while still restricting ourselves to agents of type 1 only, we consider a generalized model that allows an agent to control more than one location. In this generalized model, we provide best-possible 3and 3 approximate strategyproof 2 mechanisms for the maxisum objective in the deterministic and randomized settings, respectively.

We consider the problem of repeatedly matching a set of alternatives to a set of agents in the absence of monetary transfer. We propose a generic framework for evaluating sequential matching mechanisms with dynamic preferences, and show that unlike single-shot settings, the random serial dictatorship mechanism is manipulable.

We study the mechanism design problem of a social planner for locating two facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities. We consider the requirement of a minimum distance 0 ≤ d ≤ 1 between the two facilities. Given the two facilities are heterogeneous, we model the cost/utility of an agent as the sum of his distances to both facilities. In the heterogeneous two-facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. We also design a strategyproof mechanism minimizing the maximum cost. Given the two facilities are homogeneous, we model the cost/utility of an agent as his distance to the closer facility. In the homogeneous two-facility location game for minimizing the social cost, we show that any deterministic strategyproof mechanism has unbounded approximation ratio. Moreover, in the obnoxious heterogeneous two-facility location game for maximizing the social utility, we propose new deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound (7 − d)/6 for any deterministic strategyproof mechanism. We also design a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game for maximizing the social utility, we propose deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound 4/3. Besides, in the two-facility location game with triple-preference, where each facility may be favorable, obnoxious, indifferent for any agent, we further motivate agents to report both their locations and preferences towards the two facilities truthfully, and design a deterministic group strategyproof mechanism with an approximation ratio 4.

In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of minimizing total cost is at least Ω(n^1/3). Hence, we use the utility function to analyze the agents' satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2-approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategy-proof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1.06. For the objective of maximizing the minimum utility, we give a lower-bound of 1.5 and present a 2-approximation deterministic strategy-proof mechanism where agents can misreport both the preference and location.