Earlier in 2011, Prof. Silvio Micali, Alessandro Chiesa and I discovered a new area in game theory, that is to study auctions (or more general games) when the participating players do not exactly know their valuations. This page is my attempt to keep track of all of our published papers and technical reports, and to resolve potential confusions on the model.

Our Knightian Valuation Model

Through detailed notations and motivations can be found in our paper, the one-line version of our model is as follows.

Our Knightian Valuation Model. We focus on auctions where the designer has no information about the players, and in addition, the only information a player \(i\) has about the profile of true valuations, \(\theta^*\), consists of a set of distributions \(\mathcal{K}_i\), from one of which \(\theta^*_i\) has been drawn.

We refer interested readers to our paper for motivations and examples for such setting. Clearly, when \(\mathcal{K}_i\) is a singleton for each \(i\), this setting collapses to that of the classical second-price, Vickrey, and VCG mechanisms. We observe in our paper that, at least in auctions, this model is mathematically equivalent to the following distribution-free version.

Our Knightian Valuation Model (distribution-free). Each player \(i\)'s sole information about \(\theta^*\) consists of a set of valuations \(K_i\) such that \(\theta^*_i \in K_i \subseteq \Theta_i\). We call \(K_i\) the candidate set of player \(i\) (or approximate valuation of player \(i\) in our earlier version of the paper).

Our goal is to study the social-welfare efficiency of auction mechanisms, as a function of \(\delta\), the maximum inaccuracy of the candidate sets \(K_i\).

Our Results

We have presented our results in two computer science conferences, ITCS 2012 and ACM-EC 2014. We refer these two papers as [CMZ12] and [CMZ14]. Our journal version of the paper [CMZ15] is published in Econometrica. We have also produced 4 related technical reports [CMZ-bridge], [CMZ-vcg-regret], [CMZ-vcg-utility] and [CMZ-single-param] that we may choose to submit independently in the future. The table below provides a visual summary of these papers.

Results Solution Concept [CMZ12] [CMZ14] [CMZ15] [CMZ-single-param] [CMZ-vcg-utility] [CMZ-vcg-regret]
(1). dominant-strategy and ex-post-Nash mechanisms fail to work even for single-good auctions dominant-strategy
ex-post Nash
included   included      
(2). the second-price mechanism produces great social-welfare under undominated strategies for single-good auctions undominated
strategies
included          
(2'). 2 is essentially optimal among all finite mechanisms for single-good auctions undominated
strategies
included          
(3). there is a probabilistic mechanism that slightly outperforms the second-price one for single-good auctions undominated
strategies
included          
(4). the Vickrey mechanism produces great social-welfare under undominated strategies for multi-unit auctions undominated
strategies
    included      
(4'). 4 is essentially optimal among all finite mechanisms for multi-unit auctions undominated
strategies
    included      
(5). classical DST mechanisms continue to work under Knightian uncertainty in undominated strategies for single-parameter domains undominated
strategies
      included    
(6). the VCG mechanism performs poorly in undominated strategies for unrestricted combinatorial auctions undominated
strategies
  included     included  
(7). the VCG mechanism performs well in regret-minimizing strategies for unrestricted combinatorial auctions regret-minimizing
strategies
  included       included
(7'). 7 continues to hold for utility maximizers who only resort to regret to break ties regret-elimination after undominated strategies
see [CMZ-bridge]
  included       included
 

References

  • [CMZ12] "Mechanism Design with Approximate Valuations".
    By (α-β order): Alessandro Chiesa, Silvio Micali and Zeyuan A. Zhu.
    ITCS 2012: 3rd ACM Innovations in Theoretical Computer Science.
    Note: this paper is in an earlier language of our model, where we have adopted multiplicative \(\delta\) rather than additive \(\delta\).
  • [CMZ14] "Knightian Self Uncertainty in the VCG Mechanism for Unrestricted Combinatorial Auctions".
    By (α-β order): Alessandro Chiesa, Silvio Micali and Zeyuan A. Zhu.
    ACM-EC 2014: 15th ACM Conference on Economics and Computation.
  • [CMZ15] "Knightian Analysis of the Vickrey Mechanism".
    By (α-β order): Alessandro Chiesa, Silvio Micali and Zeyuan A. Zhu.
    Econometrica: Volume 83, Issue 5, pages 1727–1754.
  • [CMZ14-single-param] "Knightian Robustness of Single-Parameter Domains".
    By (α-β order): Alessandro Chiesa, Silvio Micali and Zeyuan A. Zhu.
    Technical report.
  • [CMZ14-vcg-utility] "Knightian Analysis of the VCG Mechanism in Unrestricted Combinatorial Auctions".
    By (α-β order): Alessandro Chiesa, Silvio Micali and Zeyuan A. Zhu.
    Technical report.
  • [CMZ14-vcg-regret] "Knightian Robustness from Regret Minimization".
    By (α-β order): Alessandro Chiesa, Silvio Micali and Zeyuan A. Zhu.
    Technical report.
  • [CMZ14-bridge] "Bridging Utility Maximization and Regret Minimization".
    By (α-β order): Alessandro Chiesa, Silvio Micali and Zeyuan A. Zhu.
    Technical report.