Simultaneous auctions with item bidding

A major challenge in combinatorial auction is to achieve economically efficient outcomes in a computationally efficient manner. William Vickrey's remarkable work demonstrated that welfare can be exactly optimized, as long as we have unbounded computational and communication resources. Because of many well-known disadvantages, applications of Vickrey's design are rare at best. A practically useful and recently studied solution is to hold simultaneous auctions for individual items. In this thesis we survey the welfare guarantees for simultaneous auctions. Most of them are positive results on the price of anarchy. Despite good performance of simultaneous auctions, it has been proved that finding a Bayesian Nash equilibrium for simultaneous second price auctions is still intractable. We prove that finding a Bayesian Nash equilibrium for simultaneous first price auction is also computational intractable. Furthermore, even finding an approximate equilibrium is as hard as NP. Our negative results can be extend to Bayesian no-regret dynamics.Un défi majeur dans la vente aux enchères combinatoire est d'atteindre des résultats économiquement efficaces d'une manière efficace sur le plan informatique. Le travail remarquable de William Vickrey a démontré que le bien-être peut être exactement optimisé, tant que nous avons des ressources de calcul et de communication illimitées. En raison de nombreux inconvénients bien connus, les applications du design de Vickrey sont au mieux rares. Une solution pratique et récemment étudiée consiste à organiser des enchères simultanées pour des articles individuels. Dans cette thèse, nous examinons les garanties de bien-être pour les enchères simultanées. La plupart d'entre eux sont des résultats positifs sur le prix de l'anarchie. Malgré la bonne performance des ventes aux enchères simultanées, il a été prouvé que trouver un équilibre bayésien de Nash pour des enchères simultanées de second prix est toujours intraitable. Nous montrons que la recherche d'un équilibre bayésien de Nash pour une vente aux enchères simultanée au premier prix est également intraitable. De plus, même trouver un équilibre approximatif est aussi difficile que NP. Nos résultats négatifs peuvent s'étendre à la dynamique bayésienne sans regret