Florin Constantin

AAAI Conference 2011 Conference Paper

On Expressing Value Externalities in Position Auctions

• Florin Constantin
• Malvika Rao
• Chien-Chung Huang
• David Parkes

We introduce a bidding language for expressing negative value externalities in position auctions for online advertising. The unit-bidder constraints (UBC) language allows a bidder to condition a bid on its allocated slot and on the slots allocated to other bidders. We introduce a natural extension of the Generalized Second Price (GSP) auction, the expressive GSP (eGSP) auction, that induces truthful revelation of constraints for a rich subclass of unit-bidder types, namely downward-monotonic UBC. We establish the existence of envy-free Nash equilibrium in eGSP under a further restriction to a subclass of exclusion constraints, for which the standard GSP has no pure strategy Nash equilibrium. The equilibrium results are obtained by reduction to equilibrium analysis for reserve price GSP (Even-Dar et al. 2008). In considering the winner determination problem, which is NPhard, we bound the approximation ratio for social welfare in eGSP and provide parameterized complexity results.

SODA Conference 2009 Conference Paper

An online mechanism for ad slot reservations with cancellations

• Florin Constantin
• Jon Feldman
• S. Muthukrishnan 0001
• Martin Pál

AAMAS Conference 2007 Conference Paper

Online Auctions for Bidders with Interdependent Values

• Florin Constantin
• Takayuki Ito
• David C. Parkes

Interdependent values (IDV) is a valuation model allowing bidders in an auction to express their value for the item(s) to sell as a function of the other bidders' information. We investigate the incentive compatibility (IC) of single-item auctions for IDV bidders in dynamic environments. We provide a necessary and sufficient characterization for IC in this setting. We show that if bidders can misreport departure times and private signals, no reasonable auction can be IC. We present a reasonable IC auction for the case where bidders cannot misreport departures.

IJCAI Conference 2005 Conference Paper

More on the Power of Demand Queries in Combinatorial Auctions: Learning Atomic Languages and Handling Incentives

• Sébastien Lahaie
• Florin Constantin
• David C

Query learning models from computational learning theory (CLT) can be adopted to perform elicitation in combinatorial auctions. Indeed, a recent elicitation framework demonstrated that the equivalence queries of CLT can be usefully simulated with price-based demand queries. In this paper, we validate the flexibility of this framework by defining a learning algorithm for atomic bidding languages, a class that includes XOR and OR. We also handle incentives, characterizing the communication requirements of the Vickrey-Clarke- Groves outcome rule. This motivates an extension to the earlier learning framework that brings truthful responses to queries into an equilibrium.