An official website of the United States government
In the assignment problem, the goal is to assign indivisible items to agents who have ordinal preferences, efficiently and fairly, in a strategyproof manner. In practice, first-choice maximality, i.e., assigning a maximal number of agents their top items, is often identified as an important efficiency criterion and measure of agents' satisfaction. In this paper, we propose a natural and intuitive efficiency property, favoring-eagerness-for-remaining-items (FERI), which requires that each item is allocated to an agent who ranks it highest among remaining items, thereby implying first-choice maximality. Using FERI as a heuristic, we design mechanisms that satisfy ex-post or ex-ante variants of FERI together with combinations of other desirable properties of efficiency (Pareto-efficiency), fairness (strong equal treatment of equals and sd-weak-envy-freeness), and strategyproofness (sd-weak-strategyproofness). We also explore the limits of FERI mechanisms in providing stronger efficiency, fairness, or strategyproofness guarantees through impossibility results.
more »
« less
Describing Deferred Acceptance and Strategyproofness to Participants: Experimental Analysis
We conduct an incentivized lab experiment to test participants' ability to understand the DA matching mechanism and the strategyproofness property, conveyed in different ways. We find that while many participants can (using a novel GUI) learn DA's mechanics and calculate its outcomes, such understanding does not imply understanding of strategyproofness (as measured by specially designed tests). However, a novel menu description of strategyproofness conveys this property significantly better than other treatments. While behavioral effects are small on average, participants with levels of strategyproofness understanding above a certain threshold play the classical dominant strategy at very high rates.
more »
« less
- Award ID(s):
- 2343922
- PAR ID:
- 10564606
- Publisher / Repository:
- ACM
- Date Published:
- ISBN:
- 9798400707049
- Page Range / eLocation ID:
- 416 to 417
- Format(s):
- Medium: X
- Location:
- New Haven CT USA
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the facility location problems (FLPs) with altruistic agents who act to benefit others in their affiliated groups. Our aim is to design mechanisms that elicit true locations from the agents in different overlapping groups and place a facility to serve agents to approximately optimize a given objective based on agents' costs to the facility. Existing studies of FLPs consider myopic agents who aim to minimize their own costs to the facility. We mainly consider altruistic agents with well-motivated group costs that are defined over costs incurred by all agents in their groups. Accordingly, we define Pareto strategyproofness to account for altruistic agents and their multiple group memberships with incomparable group costs. We consider mechanisms satisfying this strategyproofness under various combinations of the planner's objectives and agents' group costs. For each of these settings, we provide upper and lower bounds of approximation ratios of the mechanisms satisfying Pareto strategyproofness.more » « less
-
We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller’s true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed the buyer’s budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of very appealing properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer’s valuation function is submodular over the set of services. In addition to this, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior workmore » « less
-
We initiate the study of matching roommates and rooms wherein the preferences of agents over other agents and rooms are complementary and represented by Leontief utilities. In this setting, 2n agents must be paired up and assigned to n rooms. Each agent has cardinal valuations over the rooms as well as compatibility values over all other agents. Under Leontief preferences, an agent’s utility for a matching is the minimum of the two values. We focus on the tradeoff between maximizing utilitarian social welfare and strategyproofness. Our main result shows that—in a stark contrast to the additive case— under binary Leontief utilities, there exist strategyproof mechanisms that maximize the social welfare. We further devise a strategyproof mechanism that implements such a welfare maximizing algorithm and is parameterized by the number of agents. Along the way, we highlight several possibility and impossibility results, and give upper bounds and lower bounds for welfare with or without strategyproofness.more » « less
-
In everyday life, people routinely make decisions that involve irredeemable risks such as death (e.g., while driving). Even though these decisions under extinction risk are common, practically important, and have different properties compared to the types of decisions typically studied by decision scientists, they have received little research attention. The present work advances the formal understanding of decision making under extinction risk by introducing a novel experimental paradigm, the Extinction Gambling Task (EGT). We derive optimal strategies for three different types of extinction and near-extinction events, and compare them to participants’ choices in three experiments. Leveraging computational modelling to describe strategies at the individual level, we document strengths and shortcomings in participants’ decisions under extinction risk. Specifically, we find that, while participants are relatively good in terms of the qualitative strategies they employ, their decisions are nevertheless affected by loss chasing, scope insensitivity, and opportunity cost neglect. We hope that by formalising decisions under extinction risk and providing a task to study them, this work will facilitate future research on an important topic that has been largely ignored.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3670865.3673600
