Redistribution in online mechanisms

Victor Naroditskiy, Sofia Ceppi, Valentin Robu, Nicholas R. Jennings

Research output: Contribution to conferencePaperpeer-review

2 Citations (Scopus)


Following previous work on payment redistribution in static mechanisms, we develop the theory of redistribution in online mechanisms (e.g., [2, 10, 8]). In static mechanisms, redistribution is important as it increases social welfare in scenarios with no residual claimant. Many online scenarios also do not have a natural residual claimant, and redistribution there is equally important. In this work, we adopt a fundamental online mechanism design model where a single expiring item is allocated in each of T periods. Agents with unit demand are present in the market between their arrival and departure periods, which are private information along with the value an agent attributes to the item. For this model, we derive a number of properties characterizing redistribution in online mechanisms (including revenue monotonicity properties, and quantifying the effect an agent can have on the total revenue). We then design two redistribution functions. The first one generalizes the static redistribution proposed by Cavallo [2] making redistribution after the departure of the last agent. For this redistribution function we provide theoretical worst-case guarantees. The second function is truly "online" making redistribution to each agent on her departure. The performance of both functions is evaluated using numerical simulations.

Original languageEnglish
Number of pages8
Publication statusPublished - 1 Jan 2013
Externally publishedYes
Event12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013 - Saint Paul, MN, United States
Duration: 6 May 201310 May 2013


Conference12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013
CountryUnited States
CitySaint Paul, MN


  • Online mechanism design
  • Payment redistribution


Dive into the research topics of 'Redistribution in online mechanisms'. Together they form a unique fingerprint.

Cite this