Person:

Parkes, David

Cake cutting is a common metaphor for the division of a heterogeneous divisible good. There are numerous papers that study the problem of fairly dividing a cake; a small number of them also take into account self-interested agents and consequent strategic issues, but these papers focus on fairness and consider a strikingly weak notion of truthfulness. In this paper we investigate the problem of cutting a cake in a way that is truthful and fair, where for the first time our notion of dominant strategy truthfulness is the ubiquitous one in social choice and computer science. We design both deterministic and randomized cake cutting algorithms that are truthful and fair under different assumptions with respect to the valuation functions of the agents.

The next decade will see an abundance of new intelligent systems, many of which will be market-based. Soon, users will interact with many new markets, perhaps without even knowing it: when driving their car, when listening to a song, when backing up their files, or when surfing the web. We argue that these new systems can only be successful if a new approach is chosen towards designing them. In this paper we introduce the general problem of "Hidden Market Design." The design of a "weakly hidden" market involves reducing some of the market complexities and providing a user interface (UI) that makes the interaction seamless for the user. A "strongly hidden market" is one where some semantic aspect of a market is hidden altogether (e.g., budgets, prices, combinatorial constraints). We show that the intersection of UI design and market design is of particular importance for this research agenda. To illustrate hidden market design, we give a series of potential applications. We hope that the problem of hidden market design will inspire other researchers and lead to new research in this direction, paving the way for more successful market-based systems in the future.

Reputation mechanisms at online opinion forums, such as Amazon Reviews, elicit ratings from their users about the experiences with products of unknown quality and critically rely on these ratings being truthful. The peer prediction method by Miller, Resnick and Zeckhauser is arguably the most prominent truthful feedback mechanism in the literature. An obstacle with regard to its application are the strong common knowledge assumptions. Especially the commonly held prior belief about a product’s quality, although prevailing in economic theory, is too strict for this setting. Two issues stand out in particular: first, that different buyers hold different beliefs and, second, that the buyers’ beliefs are often unknown to the mechanism. In this paper, we develop an incentive-compatible peer prediction mechanism for these reputation settings where the buyers have private beliefs about the product’s inherent quality and the likelihood of a positive experience given a particular quality. We show how to exploit the temporal structure and truthfully elicit two reports: one before and one after the buyer’s experience with the product. The key idea is to infer the experience from the direction of the belief change and to use this direction as the event that another buyer is asked to predict.

We study a problem of dynamic allocation without money. Agents have arrivals and departures and strict preferences over items. Strategyproofness requires the use of an arrival-priority serial-dictatorship (APSD) mechanism, which is ex post Pareto efficient but has poor ex ante efficiency as measured through average rank efficiency. We introduce the scoring-rule (SR) mechanism, which biases in favor of allocating items that an agent values above the population consensus. The SR mechanism is not strategyproof but has tolerable manipulability in the sense that: (i) if every agent optimally manipulates, it reduces to APSD, and (ii) it significantly outperforms APSD for rank efficiency when only a fraction of agents are strategic. The performance of SR is also robust to mistakes by agents that manipulate on the basis of inaccurate information about the popularity of items.

We study dynamic matching without money when one side of the market is dynamic with arrivals and departures and the other is static and agents have strict preferences over agents on the other side of the market. In enabling stability properties, so that no pair of agents can usefully deviate from the match, we consider the use of a fall-back option where the dynamic agents can be matched, if needed, with a limited number of agents from a separate “reserve” pool. We introduce the GSODAS mechanism, which is truthful for agents on the static side of the market and stable. In simulations, we establish that GSODAS dominates in rank-efficiency a pair of randomized mechanisms that operate without the use of a fall-back option. In addition, we demonstrate good rank-efficiency in comparison to a non-truthful mechanism that employs online stochastic optimization.

Establishing trust amongst agents is of central importance to the development of well-functioning multi-agent systems. For example, the anonymity of transactions on the Internet can lead to inefficiencies; e.g., a seller on eBay failing to ship a good as promised, or a user free-riding on a file-sharing network. Trust (or reputation) mechanisms can help by aggregating and sharing trust information between agents. Unfortunately these mechanisms can often be manipulated by strategic agents. Existing mechanisms are either very robust to manipulation (i.e., manipulations are not beneficial for strategic agents), or they are very informative (i.e., good at aggregating trust data), but never both. This paper explores this trade-off between these competing desiderata. First, we introduce a metric to evaluate the informativeness of existing trust mechanisms. We then show analytically that trust mechanisms can be combined to generate new hybrid mechanisms with intermediate robustness properties. We establish through simulation that hybrid mechanisms can achieve higher overall efficiency in environments with risky transactions and mixtures of agent types (some cooperative, some malicious, and some strategic) than any previously known mechanism.

A central challenge in human computation is in understanding how to design task environments that effectively attract participants and coordinate the problem solving process. In this paper, we consider a common problem that requesters face on Amazon Mechanical Turk: how should a task be designed so as to induce good output from workers? In posting a task, a requester decides how to break down the task into unit tasks, how much to pay for each unit task, and how many workers to assign to a unit task. These design decisions affect the rate at which workers complete unit tasks, as well as the quality of the work that results. Using image labeling as an example task, we consider the problem of designing the task to maximize the number of quality tags received within given time and budget constraints. We consider two different measures of work quality, and construct models for predicting the rate and quality of work based on observations of output to various designs. Preliminary results show that simple models can accurately predict the quality of output per unit task, but are less accurate in predicting the rate at which unit tasks complete. At a fixed rate of pay, our models generate different designs depending on the quality metric, and optimized designs obtain significantly more quality tags than baseline comparisons.

We consider a setting in which a worker and a manager may each have information about the likely completion time of a task, and the worker also affects the completion time by choosing a level of effort. The task itself may further be composed of a set of subtasks, and the worker can also decide how many of these subtasks to split out into an explicit prediction task. In addition, a worker can learn about the likely completion time of a task as work on subtasks completes. We characterize a family of scoring rules for the worker and manager such that information is truthfully reported, best effort is exerted by the worker in completing tasks as quickly as possible, and collusion is not possible. We study the factors influencing when a worker will split a task into subtasks, each forming a separate prediction target.

We present a direction of research on principles and methods that can enable general problem solving via human computation systems. A key challenge in human computation is the effective and efficient coordination of problem solving. While simple tasks may be easy to partition across individuals, more complex tasks highlight challenges and opportunities for more sophisticated coordination and optimization, leveraging such core notions as problem decomposition, subproblem routing and solution, and the recomposition of solved subproblems into solutions. We discuss the interplay between algorithmic paradigms and human abilities,and illustrate through examples how members of a crowd can play diverse roles in an organized problem-solving process, serving not only as "data oracles" at the endpoints of computation, but also as modules for decomposing problems, controlling the algorithmic progression, and performing human program synthesis.

In this paper, we study the combinatorial agency problem introduced by Babaioff, Feldman and Nisan and resolve some open questions posed in their original paper. Our results include a characterization of the transition behavior for the class of threshold functions. This result confirms a conjecture of, and generalizes their results for the transition behavior for the OR technology and the AND technology. In addition to establishing a (tight) bound of 2 on the social Price of Unaccountability (POU) for the OR technology for the general case of n > 2 agents (the initial paper established this for n = 2, an extended version establishes a bound of 2.5 for the general case), we establish that the POU is unbounded for all other threshold functions (the initial paper established this only for the case of AND technology). We also obtain a characterization result for certain compositions of anonymous technologies and establish an unbounded POU for these cases.