Models for Truthful Online Double AuctionsJonathan BredinDepartment of MathematicsColorado CollegeColorado Springs, CO [email protected] C. ParkesDivision of Engineering and Applied SciencesHarvard UniversityCambridge, MA [email protected] double auctions (DAs) model a dy-namic two-sided matching problem with pri-vate information and self-interest, and arerelevant for dynamic resource and task al-location problems. We present a generalmethod to design truthful DAs, such that noagent can benefit from misreporting its ar-rival time, duration, or value. The familyof DAs is parameterized by a pricing rule,and includes a generalization of McAfee’struthful DA to this dynamic setting. Wepresent an empirical study, in which we studythe allocative-surplus and agent surplus fora number of different DAs. Our results il-lustrate that dynamic pricing rules are im-portant to provide good market efficiency formarkets with high volatility or low volume.1 INTRODUCTIONWe consider the problem of matching self-interestedparties in dynamic multi-agent systems. Cast as atask-allocation problem, each agent arrives in someperiod and is present in the system for some finiteperiod of time. An agent is either a seller, able to per-form a single job while present, or a buyer, with a jobto complete. All jobs are identical, and any presentagent can perform a job. All jobs are completed in aunit period of time. The arrival, departure, and cost(if a seller) or value (if a buyer) are all private infor-mation to agents. Moreover, each agent is assumed tobe self-interested and willing to misreport its privateinformation (including arrival and departure times) ifthis can improve the outcome in its favor.We model this problem as an online double auctionfor identical items. The matchmaker becomes the auc-tioneer. For dynamic task allocation, an item repre-sents a task to be performed. Each agent is only willingto buy (or sell) a single unit of the item. Uncertaintyabout the future coupled with the two-sided nature ofthe market leads to an interesting mechanism designproblem.For example, consider the scenario where the auction-eer must decide how (and whether) to pair an imme-diately departing seller with reported cost of $6 withbuyers, one of which has a reported value of $8 and onea reported value of $9. Should the auctioneer pair thehigher bidder with the seller? What happens if a sellerwilling to sell for $4 arrives after the auctioneer actsupon the matching decision? How should the match-ing algorithm be designed so that no agent can benefitfrom misstating its private constraints on arrival anddeparture, and its private cost or value information?We introduce a general framework for the design oftruthful double auctions (DAs) in this dynamic model.The DAs are truthful in the sense that the optimalstrategy for an agent, whatever the future auction dy-namics and whatever the bids from other agents, is toreport its true value (or cost for sellers) and true depar-ture period immediately upon arrival into the auction.We obtain auctions that are truthful in a dominant-strategy equilibrium (DSE). This is useful because itsimplifies the decision problem facing bidders. Anagent can determine its optimal bidding strategy with-out a model of either the auction dynamics or the otheragents.The main technical challenge is to provide truthfulnesswhile also ensuring (weak) budget-balance. We requirethat DAs do not run at a deficit, i.e. at no point intime should the auctioneer have paid more than it hasreceived. In developing a family of truthful auctionswe apply the price-based characterization from Haji-aghayi et al. [9] to develop an implementable pricerule that satisfies the required properties of agent-independence and monotonicity. This ensures truth-fulness in a DSE. To prevent the auction running ata deficit, the individualized price faced by each agentto trade must increase across time. We make no suchassumption, however, on the global price schedule, forinstance as in Lavi and Nisan [13], because we studyan infinite time horizon setting that continuously runsaDA.Truthfulness in DAs also requires new elements, for in-stance an agent’s bid value can only influence the pricefaced by other agents once it is determined whetherthe agent will trade or not. This is important becausethe availability of trades depends on the price faced byother agents. For example, a buyer that is requiredto pay $4 in the DA to trade might like to decreasethe price that a potentially matching seller will receivefrom $6 to $3 to allow for trade. In this aspect, ourapproach generalizes the truthful DA of McAfee [14]to the online setting.Our main contribution is the characterization of afamily of parameterized truthful DAs. Different priceschedules can be substituted and used within match-ing. From within this class we describe a fixed pricescheme, exponentially-weighted moving average andwindowed-average schemes, and a scheme based onMcAfee’s rules for a static DA [14]. An empirical anal-ysis illustrates the market efficiency of each auction fordifferent market conditions. For high-volume and lowvolatility markets, setting a single well-chosen priceis reasonably effective in supporting efficient trades.However, when volume is lower or when demand isvolatile, then DAs with dynamic pricing rules, perhapsmoving-average or McAfee-based, are most efficient.1.1 RELATED WORKStatic two-sided market problems have been widelystudied [15, 4, 17, 21, 7]. In a classic result, Myer-son and Satterthwaite [15] proved that it was impos-sible to achieve efficiency with voluntary participationand without running a deficit, even relaxing DSE to aBayesian-Nash equilibrium.1Our problem is also similar to a traditional continuousdouble auction (CDA), where buyers and sellers mayat any time submit offers to a market that pairs anoffer as soon as a matching offer is submitted. Earlywork considered market efficiency of CDAs with hu-man experiments in labs [18], while recent work inves-tigates the use of software agents to execute trades [19].While these markets have no dominant strategy equi-libria, populations of software trading agents can learnto extract virtually all available surplus, and even sim-ple automated trading strategies outperform humantraders [6]. However, these studies of CDAs assumethat all traders share a known deadline by which trades1In a Bayesian-Nash equilibrium each strategy mustmaximize the