Sketchy Polytopes

EC'14 - some intriguing papers

Bandits with concave rewards and convex knapsacks.

Paper by Shipra Agrawal and Nikhil R. Devanur. Introduces and gives polynomial-time near-optimal algorithms for a general model for bandit exploration-exploitation. The algorithm is an extension of the Upper Confidence Bound (UCB) algorithm for the multi-armed bandits problem. The new framework allows them to give more efficient algorithms for other problems such as Blackwell approachability, online convex optimization and conditional-gradient/projection-free/Frank-Wolfe algorithm.

Managing congestion in decentralized matching markets,

Paper by Nick Arnosti, Ramesh Johari and Yash Kanoria. Shows that in decentralized two-sided markets with asynchronous arrivals and departures and no information about seller availability, limited seller visibility can improve general welfare.

Optimising Trade-offs Among Stakeholders in Ad Auctions

Paper by Yoram Bachrach, Sofia Ceppi, Ian Kash, Peter Key and David Kurokaw. Optimizes linear combinations of the utilities of competing stakeholders (auctioneer, user, advertiser) in ad auctions using a generalized second-price (GSP) auction with per-click reserve prices.

Multiplicative Bidding in Online Advertising

Paper by MohammadHossein Bateni, Jon Feldman, Vahab Mirrokni and Sam Chiu-wai Wong. Establishes the optimization problem behind multiplicative bidding, a bid adjustment technique used by many search engines. They also study the complexity of approximating the solution and give algorithms under various assumptions.

Why Marketplace Experimentation is Harder than it Seems: The Role of Test-Control Interference

Paper by Dominic Coey and Thomas Blake. Discusses role of and conditions for test-control (A/B) interference in determining the effectiveness of marketplace campaigns

Incentivized Optimal Advert Assignment via Utility Decomposition,

Paper by Frank Kelly, Peter Key and Neil Walton. Kelly extends his primal-dual optimization framework (originally introduced for communication networks) to formulate a network utility maximization framework for platform and advertisers together. The mechanism introduced is also incentive compatible.

The Complexity of Fairness through Equilibrium,

Paper by Abraham Othman, Christos Papadimitriou and Aviad Rubinstein. Discusses the complexity of approximating Competitive Equilibrium with Equal Income (CEEI, a particular market clearing mechanism that offers efficiency, feasibility and fairness. In short, approximating CEEI in general is hard.

Asymptotically Truthful Equilibrium Selection in Large Congestion Games,

Paper by Ryan Rogers and Aaron Roth. For congestion games with large number of players and incomplete information, this paper introduces mechanism that guarantees a Nash equilibrium improving on previous mechanisms that could only guarantee correlated equilibrium.

Neutrality and Geometry of Mean Voting

Paper by Sébastien Lahaie and Nisarg Shah. Integrates the neutrality axiom into mean proximity framework for voting to achieve consensus amongst agents, and shows that the new axiom allows a more compact representation for every mean proximity rule.

A complete list of papers is available here.