- Clock auctions as optimal independent sets on graphs
- Project Year:
2024
- REU Student (s):
Jinghan Zeng | University of Illinois at Urbana-Champaign IL
- Student 1 Institution:
University of Illinois at Urbana-Champaign
- Project Mentor:
Daniel Schoepflin
- Project Mentor Area:
DIMACS
- Project Abstract:
This project focused on clock auctions, which are auctions where the price is gradually raised according to a clock and the item is awarded to the last bidder who stays in the auction. We studied how clock auctions perform on graphs, where the agents are the vertices, and our goal is to serve an item to an independent set on a graph with the aim of maximizing the total welfare. The three types of graphs we focused on were the K1,2, star graph, and serving a matching on a graph with weighted edges rather than weighted vertices. For the K1,2 case, we gave a randomized auction with an approximation ratio close to the current best upper bound. We also lowered the upper bound on the approximation ratio of a randomized auction over a star graph. Finally, we gave a deterministic auction for the matching case, which improves the current best auction in the literature.
