Florin Constantin

Game-theoretic Couplings and Applications.

by Maria-Florina Balcan, Florin Constantin, Georgios Piliouras and Jeff Shamma.

We introduce coupling, a natural game-theoretic construct that stitches together the payoff structures of two games.
Coupling models heterogeneity (intrinsic or by design) in the population of players.
We provide conditions for game couplings to preserve or to enhance desirable properties of the original games, such as convergence of best response dynamics, payoff smoothness and low price of anarchy.

On Expressing Value Externalities in Position Auctions

by Florin Constantin, Malvika Rao, David C. Parkes and Chien-Chung Huang.

We model the negative effect of another ad on the value per click in position auctions. We propose a general model of externalities, in which a bidder has no value for a slot under a set of certain conditions, each on one other bidder's allocated slot. For downward-monotonic externalities, a greedy algorithm following current practice provides no new opportunities for manipulation beyond the ones already available via untruthful claims about bid value in GSP under the standard slot auction model. We provide a class of externalities under which GSP may have no pure Nash equilibrium, but our greedy algorithm coupled with a natural payment scheme always has a Nash equilibrium.

The Snowball Effect of Uncertainty in Congestion Games.

by Maria-Florina Balcan, Florin Constantin and Steven Ehrlich

Learning Valuation Functions.

by Maria-Florina Balcan, Satoru Iwata, Lei Wang and Florin Constantin

Sequential Item Pricing for Unlimited Supply

by Maria-Florina Balcan and Florin Constantin.

We investigate the extent to which price updates can increase the revenue of a seller with little prior information on demand. We study prior-free revenue maximization for a seller with unlimited supply of n item types facing m myopic buyers present for k < log n days. Our main result is a non-increasing, randomized, schedule of k equal item prices with expected revenue within a O((log m + log n) / k) factor of optimum for private valuations with hereditary maximizers. This factor is almost tight: we show that any pricing scheme over k days has a revenue approximation factor of at least (log m + log n) / (3k). We extend our algorithm to a setting with allocative externalities (i.e. influences) between buyers with combinatorial valuations.

Dynamic Incentive Mechanisms

by David C. Parkes, Florin Constantin, Ruggiero Cavallo and Satinder Singh.

Starting with a short background on mechanism design theory, we provide an exposition, aimed at readers with an interest in artificial intelligence, of recent results on dynamic mechanisms and illustrate ongoing research challenges in the area.

Self-Correcting Sampling-Based Dynamic Multi-Unit Auctions

by Florin Constantin and David C. Parkes.

We present the first use of online stochastic optimization for incentive-compatible dynamic auctions with partially patient, multi-unit demand bidders.
We achieve strategyproofness via a self-correcting procedure applied to a heuristic version of the Consensus algorithm.
We show empirically that the price of strategyproofness is limited with respect to both performance and computation requirements.

Online Ad Slotting With Cancellations

by Florin Constantin, Jon Feldman, S. Muthukrishnan and Martin Pál.

An Online Mechanism for Ad Slot Reservations with Cancellations

by Florin Constantin, Jon Feldman, S. Muthukrishnan and Martin Pál.

Many display advertisements (ads) are sold via spot auctions. A currently missing, desirable, feature is the reservation of ad slots in advance. We introduce a simple model for auctioning ad slot reservations, in which impatient private-value unit-demand bidders arrive sequentially. The seller can cancel at any time an earlier reservation, resulting in a utility loss to the reservation holder of a fraction of her value.

Our main result is an online mechanism with many desirable game-theoretic and optimization properties. Winners have an incentive to be honest and bidding one's true value dominates any lower bid. Our mechanism's revenue is within a constant fraction of the a posteriori revenue of the Vickrey-Clarke-Groves mechanism. Our mechanism's efficiency is within a constant fraction of the a posteriori optimally efficient solution. If efficiency also takes into account the utility losses of bidders whose reservation was canceled, our mechanism can match an upper bound on the competitive ratio of any deterministic online algorithm.

Online Auctions for Bidders with Interdependent Values

by Florin Constantin, Takayuki Ito and 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 seting. 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.

On Revenue-Optimal Dynamic Auctions for Bidders with Interdependent Values

by Florin Constantin and David C. Parkes.

We adopt a computational approach to design single-item revenue-optimal dynamic auctions with known arrivals and departures but (private) signals that arrive online.
In leveraging a characterization of truthful auctions, we present a mixed-integer programming formulation of the design problem.
We highlight general properties of revenue-optimal dynamic auctions in a simple parameterized example and study the sensitivity of prices and revenue to model parameters.

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

by Sébastien Lahaie, Florin Constantin and David C. Parkes.

We define a learning algorithm for atomic bidding languages, a class of languages that includes both OR and XOR.
We characterize the communication requirements of the Vickrey-Clarke-Groves outcome rule and show how to bring truthful responses to demand queries in an equilibrium.

Preference-Based Characterizations of Truthfulness and the Limited Expressiveness of Order-Based Domains

by Florin Constantin and David C. Parkes.

We highlight the limited applicability of existing characterizations of truthfulness when applied to relevant domains.
We suggest relevant domain classes that are modular extensions to ones for which characterizations of truthfulness exist.
We also advocate the use of natural (critical-value-based) payment schemes.

Tracking a moving object with a binary sensor network

by Javed Aslam, Zack Butler, Florin Constantin, Valentino Crespi, George Cybenko and Daniela Rus (my advisor at Dartmouth College).

We propose a binary sensor model where each sensor can only detect whether a tracked object is moving towards or away from it.
We highlight geometric properties induced by this model and incorporate them in a particle-filtering tracking algorithm.
We present an analysis of a fundamental limitation of this model and show how it can be overcome with the addition of a proximity bit for each sensor.