An Experimental Evaluation of Regret-Based Econometrics

Noam Nisan, Gali Noti

This paper, authored by Noam Nisan and Gali Noti, puts a new theory of "regret-based econometrics" to the test using real-world human data. By comparing it against traditional equilibrium-based models in a controlled ad-auction experiment, the authors demonstrate that assuming players simply try to minimize their own frustration (regret) is just as effective—and sometimes more robust—than assuming they are perfectly rational agents in a stable equilibrium.

TL;DR

The authors evaluate a novel econometric approach that assumes bidders minimize "regret" rather than reaching a Nash equilibrium. Using experimental data where true valuations are known, they find that this regret-based method is as accurate as traditional methods while revealing a fascinating behavioral bias: high-value players act rationally, but low-value players consistently overbid out of a desire to "win."

What Problem Does This Paper Address?

In econometrics, researchers try to work backward from observed data (like auction bids) to estimate hidden parameters (like how much a bidder actually values a click). Traditionally, this relies on the equilibrium assumption: the idea that all players have settled into a state where no one can improve their outcome by changing their strategy.

However, in the fast-paced, complex world of electronic auctions (like Google or Bing ads), humans rarely reach a perfect Nash equilibrium. They learn, they make mistakes, and they react to others in real-time. If the underlying assumption of equilibrium is wrong, the resulting value estimates will be wrong too. This paper investigates whether a weaker, more realistic assumption—regret minimization—can provide better estimates when dealing with actual human behavior.

Methods

The researchers used data from a controlled experiment involving 120 human participants. Players were assigned private "valuations" (the ground truth) and competed in a stream of 1,500 ad auctions over 25 minutes.

They implemented a Regret-Minimization algorithm (Algorithm 1) which estimates a player's value by finding the number that would have resulted in the lowest "regret" given their actual bids. Regret is defined as the difference between the utility a player actually received and the utility they could have received if they had played the single best fixed bid in hindsight.

They compared this against "classic" methods:

  • Average-Bid: For VCG auctions (where truthful bidding is theoretically dominant).
  • VCG-like-NE and Best-Response: For GSP auctions (the standard "Generalized Second Price" auction used by search engines), which are more complex and have multiple possible equilibria.

Datasets

The study utilizes a dataset from a previous controlled experiment [Noti et al., 2014]. Unlike field data from tech giants, this dataset is unique because the researchers know the true valuations assigned to each player. This allows them to calculate the exact estimation error of each econometric method. The experiment covered four conditions: two auction types (VCG vs. GSP) and two levels of information (whether players were told their value or had to deduce it from payoffs).

Key Insights and Ideas

  • Humans Learn, but Don't Stabilize: Players modified their bids constantly throughout the 25-minute sessions. While they didn't converge to a static equilibrium, their "momentary regret" decreased over time as they learned the game.
  • The "Poor" Act Irrationally: A major finding was the "type-based bias." High-value players ("rich" types) were quite rational and successfully minimized their regret. However, low-value players ("poor" types) consistently overbid, leading to high regret (see Figure 4b).
  • Auction Fever: The authors suggest that low-type players become frustrated by losing and try to "win" slots even when the cost exceeds their valuation—a form of "illusion of control" or a psychological bias toward winning at any cost.
  • Simplicity Wins: The regret-based method is general. Unlike equilibrium methods that require complex tailoring for different auction rules (VCG vs. GSP), the same regret-minimization logic works across the board.
Relative total regret by player types. Note the high regret for lower types (21, 27).

Key Results

  • Competitive Accuracy: In VCG auctions, the regret-based method performed almost identically to the standard "Average-Bid" method (~23% error).
  • Superiority in GSP: In the more complex GSP auctions, Regret-Minimization (25.5% error) outperformed the classic VCG-like-NE method (30.6% error).
  • Bias Correction: The authors showed that if you account for the fact that low-type players overbid, you can "un-bias" the estimates and significantly improve accuracy (Figure 8a).
  • Refining the Estimate: Instead of just looking for the single point of minimum regret, the authors found that using the entire "regret curve" (a weighted average of possible values) yielded even better results.
Comparison of estimation errors. Un-biasing the estimates (Fixed) significantly reduces error across all methods.

Limitations and Future Work

The primary limitation is that the "un-biasing" factor was calculated using the ground truth values from the experiment. In a real-world scenario where valuations are unknown, quantifying this bias is much harder.

The authors suggest that future work should focus on incorporating these behavioral insights—specifically the irrationality of low-valuation players—directly into econometric models. They also point toward a "quantal regret" method (explored in their subsequent 2017 paper) as a promising way to handle the fact that humans minimize regret imperfectly.

Summary updated

Abstract

Using data obtained in a controlled ad-auction experiment that we ran, we evaluate the regret-based approach to econometrics that was recently suggested by Nekipelov, Syrgkanis, and Tardos (EC 2015). We found that despite the weak regret-based assumptions, the results were (at least) as accurate as those obtained using classic equilibrium-based assumptions. En route we studied to what extent humans actually minimize regret in our ad auction, and found a significant difference between the "high types" (players with a high valuation) who indeed rationally minimized regret and the "low types" who significantly overbid. We suggest that correcting for these biases and adjusting the regret-based econometric method may improve the accuracy of estimated values.
BibTeX
@inproceedings{nisan2016experimental,
  author = {Noam Nisan and Gali Noti},
  title = {{An Experimental Evaluation of Regret-Based Econometrics}},
  booktitle = {The Web Conference},
  year = {2016},
  doi = {10.1145/3038912.3052621},
}
Figure