Mechanism Design for the Online Allocation of Items without Monetary Payments

We consider online mechanism design without money, where agents are allowed to trade items with other agents, in an attempt to improve their own allocation. In an off-line context, this problem is known as the House Allocation Problem (HAP). We extend HAP to an online problem and call it the Online House Allocation Problem (OHAP). In OHAP,...

P³C: A New Algorithm for the Simple Temporal Problem

The Simple Temporal Problem (STP) is a sub-problem of almost any planning or scheduling problem involving time constraints. An existing efficient method to solve the STP, called ?STP, is based on partial path consistency and starts from a chordal constraint graph. In this paper, we analyse this algorithm and show that there exist instances for...