In mechanism design, a regret-free truth-telling mechanism (RFTT, or regret-free mechanism for short) is a mechanism in which each player who reveals his true private information does not feel regret after seeing the mechanism outcome. A regret-free mechanism incentivizes agents who want to avoid regret to report their preferences truthfully.

Regret-freeness is a relaxation of truthfulness: every truthful mechanism is regret-free, but there are regret-free mechanisms that are not truthful. As a result, regret-free mechanisms exist even in settings in which strong impossibility results prevent the existence of truthful mechanisms.

Formal definition

There is a finite set X of potential outcomes. There is a set N of agents. Each agent i has a preference P_i over X.

A mechanism or rule is a function f that gets as input the agents' preferences P1,...,Pn, and returns as output an outcome from X.

The agents' preferences are their private information; therefore, each agent can either report his true preference, or report some false preference.

It is assumed that, once an agent observes the outcome of the mechanism, he feels regret if his report is a dominated strategy "in hindsight". That is: given all possible preferences of other agents, which are compatible with the observed outcome, there is an alternative report that would have given him the same or a better outcome.

A regret-free truth-telling mechanism^[1] is a mechanism in which an agent who reports his truthful preferences never feels regret.

In matching

Frenandez^[2] studies RFTT in two-sided matching, particularly in connection with the Gale–Shapley algorithm.

Chen and Moller^[3] study RFTT mechanisms in school choice mechanisms.

In voting

Arribillaga, Bonifacio and Fernandez^[1] study RFTT voting rules. They show that:

• When a voting rule depends only on the top alternative of each agent (e.g. plurality voting), RFTT is equivalent to strategyproofness. This means that, for 3 or more outcomes, the only RFTT mechanisms are dictatorships (by the Gibbard–Satterthwaite impossibility theorem); and for 2 outcomes, a mechanism is RFTT if and only if it is an extended majority rule.
• For egalitarian voting rules: all neutral variants (i.e., breaking ties by a fixed order on agents) are RFTT. The anonymous variants (breaking ties by a fixed order on candidates) are RFTT iff there are at least m-1 voters, or the number of voters divides m-1.
• For the veto voting rule (a scoring rule where all candidates receive 1 point except the least-preferred one who gets 0), the results are similar to the egalitarian rules. Similarly, k-approval is RFTT.
• Other scoring rules may not be RFTT. In particular, Borda voting, plurality voting and Dowdall voting, and all efficient anonymous rules, are not RFTT.
• All Condorcet-consistent voting rules that also satisfy a weak monotonicity condition are not RFTT. This condition holds, in particular, for the rules of Simpson, Copeland, Young, Dodgson, Fishburn and Black (in both anonymous and neutral versions). Successive elimination rules are also not RFTT.

In fair division

Tamuz, Vardi and Ziani^[4] study regret in fair cake-cutting.

Cresto and Tajer^[5] also study regret in fair cake-cutting among two agents, where the regret comes from a change in preferences: after one player sees the choice of the other player, his preferences may change. They suggest a variant of cut and choose that avoids this kind of regret.

References