About Me
My name is Annie Zeng, and I am an undergraduate student at UIUC interested in combinatorics and theoretical computer science. My CV can be found
here. This is the website for my research at DIMACS during Summer 2024.
Project Description
Clock auctions are auctions frequently used in practice where the price each bidder has to pay for an item is gradually increased, possibly varying based on bidder. We are interested in maximizing the welfare of the auction participations over combinatorial structures. In many instances, an item can be served to multiple people, for example, auctioning a radio frequency to two cell towers too far away to affect each other, which can be modelled as serving an item to an independent set on a graph. We can also hold auctions on a knapsack, like selling seats for a movie when some people may want to buy multiple seats. We will explore how randomization improves the outcomes for clock auctions on both structures.
Research Log
Week 1 (5/28-5/31)
For this week I focused on a very specific graph: the K1,2. For practice, I wrote a deterministic approximation algorithm for maximizing welfare over the K1,2, and proved that it is impossible for any deterministic algorithm to yield a better result. Furthermore, I wrote a randomized algorithm that on expectation, produces better results than the deterministic algorithm, which seperates the performance of deterministic vs randomized in this setting. I also learned about Yao's Lemma, which is used to upper bound the performance of randomized algorithms.
Week 2 (6/3-6/7)
For this week I self studied the basics of linear programming. For practice, I worked on continuing to improve the upper and lower bounds for an approximation algorithm on a K1,2, and arrived at the best known upper and lower bounds in the literature as of now. My mentor and I began experimenting with a linear program in Python to optimize our randomized algorithm on the K1,2, and we made a conjecture about whether the upper or lower bound was closer to the truth. I started working on auctions on star graphs with an arbitrary number of vertices, and using Yao's Lemma, improved the best known upper bound for the approximation ratio by a very small (but constant!) amount.
Week 3 (6/10-6/14)
For this week I spent most of my time at a mathematics workshop at DIMACS, which was intended to introduce and give an overview of various areas of math. I attended talks on Ramsey theory and additive combinatorics, number theory, Schubert calculus, integrable systems, and random matrix theory. I improved the upper bound on the approximation constant over a star graph by a small but more noticable amount. I also made a slight (but constant) improvement on the lower bound on the approximation ratio of K1,2, breaking past the current best lower bound in the literature. Finally, I wrote a simple deterministic approximation algorithm for an auction over a C4.
Week 4 (6/17-6/20)
For this week I moved to a much more general case - auctioning something to a matching on a graph by raising prices on the edges, which represent the bidders. I read a paper on the previous progress on this problem, and I came up with a quick modification to the current best deteriministic algorithm by utilizing randomization, which doubled the approximation constant yielded by that algorithm. In addition to my research, I also gave a short talk in front of my peers at the DIMACS REU, where I demonstrated Erdos's probabilistic construction of graphs with arbitrarily high chromatic number and girth.
Week 5 (6/24-6/28)
Due to the fact that the edges on a graph incident to the same vertex form a clique on the corresponding line graph, this made auctions on matchings much easier to do than on independent sets. I started this week attempting to extend these ideas to graphs whose cliques formed a nice structure like chordal graphs, but unfortunantely came up empty-handed. I wrote a general formula for the approximation ratio on a K1,2 auction, and have yet to select the best probability distribution that optimizes this result. My mentor and I also began discussing various ways to increase the lower bound on an auction over a star graph.
Week 6 (7/1-7/5)
We were visited by the NYC Discrete Math REU this week, and I gave a presentation during the visit about my project and my current results. I spent most of this week reading papers, which covered probabilistic techniques and touched on cases involving hypergraphs. To get a better bound for the matching case, I focused on how to optimize auctions on paths, and was able to obtain a better lower bound on the approximation ratio for a path with four vertices using a deterministic auction.
Week 7 (7/8-7/12)
We started this week by visiting Bell Labs, where we got to see many cool things like anechoic chamber, the first transistor ever invented, and the original copy of Shannon's paper on information theory. I continued studying auctions on paths to get a better lower bound for the matching case, and I was able to find a more optimal way on how to handle an auction on a path. This led to me discovering a better deterministic algorithm for an auction over a matching, improving the current best lower bound by a significant amount for a pretty general case.
Project Summary
References
Acknowledgements
This work was carried out while the author Jinghan A Zeng was a participant in the 2024 DIMACS REU program at Rutgers University, supported by NSF grant CNS-2150186.