When are Equilibria of Simple Auctions Near-Optimal?
Alberto Marchesi
DEIB PhD student
DEIB - Seminar Room "Alessandra Alario" (building 21 - second floor)
January 23rd, 2018
12.30 pm
Contact:
Nicola Gatti
Research Line:
Artificial intelligence and robotics
DEIB PhD student
DEIB - Seminar Room "Alessandra Alario" (building 21 - second floor)
January 23rd, 2018
12.30 pm
Contact:
Nicola Gatti
Research Line:
Artificial intelligence and robotics
Abstract
In this seminar, we outline some results concerning approximation guarantees for equilibria of auctions in complex settings.
These results are derived using tools from theoretical computer science that complement traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings. We provide positive and negative results. On the positive side, under suitable assumptions on bidders’ valuations over items, we prove some lower-bounds on the quality of equilibria of simple auctions in complex scenarios, i.e., settings where multiple items are sold simultaneously. Instead, on the negative side, we show that, when valuations are general, there are no provable non-trivial lower-bounds on the quality of equilibria in simple auctions in complex settings.
This seminar is based on the talk given by Prof. Tim Roughgarden (Stanford University) at 28th Jerusalem Summer School in Economic Theory: Mechanism Design.
These results are derived using tools from theoretical computer science that complement traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings. We provide positive and negative results. On the positive side, under suitable assumptions on bidders’ valuations over items, we prove some lower-bounds on the quality of equilibria of simple auctions in complex scenarios, i.e., settings where multiple items are sold simultaneously. Instead, on the negative side, we show that, when valuations are general, there are no provable non-trivial lower-bounds on the quality of equilibria in simple auctions in complex settings.
This seminar is based on the talk given by Prof. Tim Roughgarden (Stanford University) at 28th Jerusalem Summer School in Economic Theory: Mechanism Design.