Oregon State University

Calendar

Calendars

Event Details

MS Final Examination – Béatrice Moissinac


Friday, November 22, 2013 10:00 AM - 12:00 PM

Reinforcement Learning-Based Off-Equilibrium Incentives to Approximate the VCG Mechanism
Auctions are used to solve resource allocation problem between many agents and many items in real-world settings. Unfortunately, in most cases, it is possible for selfish agents to manipulate the system for their own interest at the expense of the social welfare. Such manipulation can be prevented using the Vickrey-Clarke-Groves mechanism, which guarantees complete truthfulness from the agents, and therefore, preserve optimal social welfare. However, the Vickrey-Clarke-Groves mechanism is computationally expensive, mainly due to the search for the optimal allocation of items (the “Winner Determination Problem").

In this work, we propose the use of off-equilibrium incentives to approximate the VCG mechanism, where the agents use reinforcement learning using "difference rewards" to compute those incentives. In one round of the reinforcement learning, the agents: (i) declare their preferences in terms of allocation; (ii) compute their reward using the difference reward; (iii) and update their Q-table and move toward system efficiency. We demonstrate theoretically the equivalence of the off-equilibrium incentives and the VCG mechanism, and empirically show that this approximation of VCG mechanism leads to desirable outcomes in a congestion game.

Major Advisor: Kagan Tumer
Committee: Prasad Tadepalli
Committee: Raviv Raich
GCR: Hector Vergara 


Kelley Engineering Center (campus map)
1114
Nicole Thompson
1 541 737 3617
Nicole.Thompson at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: