Bounded Incentives in Manipulating the Probabilistic Serial Rule

• URL: http://arxiv.org/abs/2001.10640v1
• Date: Tue, 28 Jan 2020 23:53:37 GMT
• Title: Bounded Incentives in Manipulating the Probabilistic Serial Rule
• Authors: Zihe Wang and Zhide Wei and Jie Zhang
• Abstract summary: Probabilistic Serial is not incentive-compatible. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism. We show that the incentive ratio of the mechanism is $frac32$.
• Score: 8.309903898123526
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Probabilistic Serial mechanism is well-known for its desirable fairness and efficiency properties. It is one of the most prominent protocols for the random assignment problem. However, Probabilistic Serial is not incentive-compatible, thereby these desirable properties only hold for the agents' declared preferences, rather than their genuine preferences. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism and would subvert the very foundation of adopting the mechanism in practice. In this paper, we characterize the extent to which an individual agent can increase its utility by strategic manipulation. We show that the incentive ratio of the mechanism is $\frac{3}{2}$. That is, no agent can misreport its preferences such that its utility becomes more than 1.5 times of what it is when reports truthfully. This ratio is a worst-case guarantee by allowing an agent to have complete information about other agents' reports and to figure out the best response strategy even if it is computationally intractable in general. To complement this worst-case study, we further evaluate an agent's utility gain on average by experiments. The experiments show that an agent' incentive in manipulating the rule is very limited. These results shed some light on the robustness of Probabilistic Serial against strategic manipulation, which is one step further than knowing that it is not incentive-compatible.

Related papers

• Strategic Classification With Externalities [11.36782598786846]
  We propose a new variant of the strategic classification problem. Motivated by real-world applications, our model crucially allows the manipulation of one agent to affect another. We show that under certain assumptions, the pure Nash Equilibrium of this agent manipulation game is unique and can be efficiently computed.
  arXiv  Detail & Related papers  (2024-10-10T15:28:04Z)
• Criticality and Safety Margins for Reinforcement Learning [53.10194953873209]
  We seek to define a criticality framework with both a quantifiable ground truth and a clear significance to users. We introduce true criticality as the expected drop in reward when an agent deviates from its policy for n consecutive random actions. We also introduce the concept of proxy criticality, a low-overhead metric that has a statistically monotonic relationship to true criticality.
  arXiv  Detail & Related papers  (2024-09-26T21:00:45Z)
• Select to Perfect: Imitating desired behavior from large multi-agent data [28.145889065013687]
  Desired characteristics for AI agents can be expressed by assigning desirability scores. We first assess the effect of each individual agent's behavior on the collective desirability score. We propose the concept of an agent's Exchange Value, which quantifies an individual agent's contribution to the collective desirability score.
  arXiv  Detail & Related papers  (2024-05-06T15:48:24Z)
• Mistake, Manipulation and Margin Guarantees in Online Strategic Classification [0.0]
  We consider an online strategic classification problem where each arriving agent can manipulate their true feature vector to obtain a positive predicted label. We prove convergence, finite mistake and finite manipulation guarantees for a variety of agent cost structures. Our numerical study on real and synthetic data demonstrates that the new algorithms outperform previous ones in terms of margin, number of manipulation and number of mistakes.
  arXiv  Detail & Related papers  (2024-03-27T01:05:45Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  Multi-armed bandits are a sequential-decision-making framework, where, at each interaction step, the learner selects an arm and observes a reward. We consider the scenario in which the learner has access to a set of mediators, each of which selects the arms on the agent's behalf according to a and possibly unknown policy. We propose a sequential decision-making strategy for discovering the best arm under the assumption that the mediators' policies are known to the learner.
  arXiv  Detail & Related papers  (2023-08-29T18:18:21Z)
• Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards [4.742123770879715]
  In practice, incentive providers often cannot observe the reward realizations of incentivized agents. This paper explores a repeated adverse selection game between a self-interested learning agent and a learning principal. We introduce an estimator whose only input is the history of principal's incentives and agent's choices.
  arXiv  Detail & Related papers  (2023-08-13T08:12:01Z)
• Do the Rewards Justify the Means? Measuring Trade-Offs Between Rewards and Ethical Behavior in the MACHIAVELLI Benchmark [61.43264961005614]
  We develop a benchmark of 134 Choose-Your-Own-Adventure games containing over half a million rich, diverse scenarios. We evaluate agents' tendencies to be power-seeking, cause disutility, and commit ethical violations. Our results show that agents can both act competently and morally, so concrete progress can be made in machine ethics.
  arXiv  Detail & Related papers  (2023-04-06T17:59:03Z)
• Principal-Agent Hypothesis Testing [54.154244569974864]
  We consider the relationship between a regulator (the principal) and an experimenter (the agent) such as a pharmaceutical company. The efficacy of the drug is not known to the regulator, so the pharmaceutical company must run a costly trial to prove efficacy to the regulator. We show how to design protocols that are robust to an agent's strategic actions, and derive the optimal protocol in the presence of strategic entrants.
  arXiv  Detail & Related papers  (2022-05-13T17:59:23Z)
• Cursed yet Satisfied Agents [15.104201344012344]
  Winner's high bid implies that the winner often over-estimates the value of the good for sale, resulting in an incurred negative utility. We propose mechanisms that incentivize agents to bid their true signal even though they are cursed.
  arXiv  Detail & Related papers  (2021-04-02T01:15:53Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space. We derive optimal strategies that maximize agents' expected payoffs.
  arXiv  Detail & Related papers  (2020-10-29T03:08:22Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.