Report from SODA 2012: Part 1

Guest post by Hu Fu.

SODA took place in the charming city of Kyoto. The conference was well attended and was meticulously organized, as so many things in Japan are. The hotel was located right in Higashiyama (east hill), with a few major attractions in walking distance. A walk around the area quickly brings one to the most serene other world of temples and gardens.

The afternoon of the second day was packed with two game theory sessions. Here I’m going to report from the first one on mechanism design, and my colleague Ashwinkumar Badanidiyuru will cover the second session.

Berthold Vöcking started the first session with a superbly clear presentation of a universally truthful mechanism for multi-unit auctions, which gives a PTAS for social welfare maximization. This answers a question left open by Dobzinski and Dughmi, who showed a by-now well-known truthful-in-expectation FPTAS for the problem and a separation between universal truthfulness and truthfulness-in-expectation in approximation power for a restricted version of multi-unit auctions. Vöcking’s work shows that there is essentially no such separation if one considers general multi-unit auctions. A starting point of the work is the observation from smoothed analysis that the computational problem of social welfare maximization is solvable in expected polynomial time if the valuations are perturbed by some random noise. However, the magnitude of the noise needs to depend on the maximum value, while truthfulness disallows “naive” use of such private data. Two ideas combined to solve the problem. One is a subjective variant of VCG mechanisms, in which different affine maximizers are used for different bidders; the other is the use of consensus estimate functions, which was first introduced in mechanism design by Goldberg and Hartline.

Another talk in the same session by Bach Ha also involves consensus estimates. This work with Jason Hartline gives a 30.5 approximation for revenue maximization in prior-free downward closed environments. Following the approach in Hartline and Yan (EC 11), the benchmark is the revenue of an envy-free mechanism. When applying consensus estimates, this work and the previous talk both face feasibility problems when there is no consensus. Vöcking solved the problem by designing new consensus functions, while Ha and Hartline introduced a cross-checking process.

The second talk in the session was by Balu Sivan on his work with Shuchi Chawla and Jason Hartline on optimal crowdsourcing contests. As pointed out in previous works, crowdsourcing has much similarity with all-pay auctions, but the auctioneer benefits only from the highest payment. Sivan first shows that the optimal static contest lets the winner take all bonus. For contests that are allowed to set up concrete rules after seeing the bids, the optimal contest is shown to be a “virtual valuation” maximizer.

Our Cornell colleague Vasilis Syrgkanis talked about his work with Renato Paes Leme and Eva Tardos on sequential auctions. In combinatorial auctions, much work has been done on simultaneous auctions for each item, and this work shows that if these auctions are run sequentially and the bidders are foreseeing what’s going to happen later, then sequential auctions behave quite differently and may have very good properties. Two such examples from the talk: pure subgame perfect Nash equilibrium always exists for sequential first price auctions, and in a matroid setting such an auction implements exactly the VCG outcome at equilibrium.

Chaitanya Swamy‘s talk concludes the session on mechanism design. In his work with Konstantinos Georgiou, Swamy gives black-box reductions that essentially reduce strategyproof cost-sharing mechanism design problems to the algorithmic problem of social welfare minimization, with a logarithmic loss in the approximation ratio. The reduction comprises of two reductions, taking as bridge the problem of truthful mechanism design with a slight technical constraint. As is true for black-box reductions in general, this reduction finds applications in a variety of problems.

Besides the main game theory sessions, there were other talks on topics that have economics applications, two of which took place towards the very end of the conference in an on-line algorithm session. Vahab Mirrokni talked about his work on on-line matching with Shayan Oveis Gharan and Morteza Zadimoghaddam. They aim at algorithms which perform well in both the adversarial model and the random arrival model. For unweighted matchings, they showed that the existing algorithm Balance achieves optimal competitive ratios in both models, while for weighted matching this is not possible, though the algorithm in the classic Mehta-Saberi-Vazirani-Vazirani paper was shown to be 0.76-competitive in the random arrival model. In the last talk of the conference, Sourav Chakraborty presented his result with Oded Lachish, which was the first improvement on the competitive ratio for general matroid secretary problem since the problem was posed in 2007 by Babaioff, Immorlica and Kleinberg. Chakraborty and Lachish improved the ratio from O(log ρ) to O(√log ρ), where ρ is the rank of the matroid. The appealing question whether there is O(1)-competitive algorithm is left open.

Advertisement