Introduction Electronic markets generate significant new trading opportunities and expand the opportunity for the dynamic pricing of goods, and lead to improved market efficiency in many settings [11, 12, 64] . Electronic markets find application not only for person-to-person transactions (e.g., auctions), but also increasingly for business-to-consumer auctions such as selling surplus inventory [39] and business-to-business sourcing events [59] . Introduction But despite the new efficiencies offered by electronic markets, for example by enabling the application of optimization to decision making in many parts of the supply chain, the role of automated trading agents -although long envisioned by artificial intelligence researchers [1, 26, 60] -remains more fiction than reality. (One notable exception is the significant role of automated trading for financial securities [23] .) One major impediment to the adoption of automated trading agents is that users often have insufficient trust of software agents that would work on their behalf [16, 37] . Users may even have higher expectations for automated agents than human agents in regard to what constitutes acceptable behavior [62] . For example, the proposal by the London International Financial Futures Exchange (Liffe) to introduce automated trading was and buyers can visit the marketplace at times of their own choosing. The VCG mechanism on the other hand requires that buyers and sellers be grouped into a single, coordinated auction with all bids placed at the same time and all goods sold at the same time. Introduction In fact, the individual auctions on eBay are very similar to single-item second-price (Vickrey) auctions. The most significant difference is that eBay provides, via the use of a mandatory proxy agent that bids on behalf of a buyer, a "staged Vickrey auction" such that a buyer can effectively increase her bid price at any time until an auction closes. 5 Electronic markets such as eBay do not provide a large-scale combinatorial auction, structured as a VCG mechanism (e.g., for all LCD monitors in the market), arguably because this would require too much temporal coordination on the part of buyers and sellers. A second issue would be determining how to define the scope for such an event to include a suitable domain of goods likely to subsume most of those of interest to a set of potential buyers. A third issue is that at some point the computational cost for running such a large, coordinated mechanism would also get prohibitive given that winner-determination for combinatorial auctions is NP-hard [56] . Problems of communication complexity and preference elicitation could also become a concern [57, 63] . Introduction The absence of such a large-scale coordination mechanism in markets such as eBay leads to strategic complexity for participants. Despite a (weak) strategic equivalence between an individual auction on eBay and the Vickrey auction [40, 65] , there are many reasons for buyers not to truthfully bid their value in any one auction. One reason follows from the auction being staged rather than sealed-bid. Because some bidders may be "followers" -bidding up when others do -it can be rational to delay until the last minute and "snipe" to avoid driving up competitors' bid prices [4, 46] . The sequential auction problem provides another reason. This relates to issues that arise when composing strategies across a sequence of auctions. Introduction For example, suppose that multiple copies of essentially identical items are offered for sale sequentially. For example, Alice may want an LCD monitor, and could potentially bid in either a 1 o'clock or 3 o'clock auction. Alice would prefer to participate in the auction that will have the lower winning price, but she cannot determine beforehand which auction that will be. As a result, she could end up winning in the "wrong" auction, that is the auction with the higher price. A related example of the sequential auction problem is familiar from the exposure problem studied in simultaneous ascending price auctions [14] , which also exists in our setting when a buyer desires a bundle of goods but must participate in auctions on individual items. For example, if Alice values a video game console by itself for $200, a video game by itself for $30, and both a console and game for $250, she must determine how much of the $20 of synergy value to include in her bid when bidding for the console alone. If Alice incorporates some of the synergy value (e.g., by placing a bid of $210 and paying her bid), she may incur a loss if she can not subsequently win the video game for less than $40. 6 The main technical question addressed in this paper is: can one design a marketplace for temporally uncoordinated buyers and sellers, and distinct goods, in which buyers have a simple, dominant bidding strategy? As a solution we propose a real-options based market infrastructure, coupled with proxy bidding, that enables simple, yet optimal, bidding strategies while retaining the dynamic arrivals and departures that are a defining feature of electronic markets such as eBay. Our main assumptions (in increasing order of strength) are that: Introduction • Each buyer has an arrival time and a departure time in the market, and is indifferent between buying items at any time before her departure and with zero value after her departure. Introduction • Buyers may have general valuations on bundles of distinct goods, but are interested in at most one unit of each of these goods. 3 The Financial Times said at the time that "Electronic trading is the biggest single issue to face the futures community today and the industry has long confronted a philosophical split on its merits", in an article "Liffe's new automated trading system has sparked a debate on automated trading", November 30, 1989 . 4 www.ebay.com. 5 While an eBay auction is open, a buyer provides her automated proxy agent with a bid ceiling. While the ceiling the agent has received is greater than the winning price and the agent is not winning, the agent will submit a bid some amount, , above the current winning price (where > 0 is set by eBay Introduction anywhere from cents to dollars depending on the value of the item). Therefore, when an auction ends, the winning buyer will pay a price above the highest ceiling another buyer submitted, and the outcome is nearly identical to the outcome of the Vickrey auction. 6 A third reason for strategic complexity in markets such as eBay can be that the quality of items may be uncertain and buyers may adjust their belief about the value of the item based on others' bids; this is the so-called interdependent values model of auction theory. We do not consider interdependent value domains in this paper. This makes our results applicable instead to markets in which buyers know their value for goods and can determine this without seeing the bids from others. An example of such a domain is provided by our empirical study on the eBay market for a Dell LCD monitor. Introduction In our options-based solution, a seller auctions an option for her good rather than auctioning the good directly. The option will ultimately either lead to a sale or require the seller to return to the market and offer another option on the same good if so interested. By participation in the framework, sellers agree to allow proxy agents to price-match their goods against others of equal type, with the payment a seller finally receives defined in terms of the minimal price that the winning bidder could have bid and still traded with some seller in some auction for a good of equal type during the bidder's arrivaldeparture interval. As noted above, all sellers are assumed to behave non-strategically and to truthfully report their temporal constraints in the marketplace. Furthermore, we assume that sellers do not have an intrinsic value for the good. Introduction All buyers in our framework must interact through a mandatory proxy agent, and do so by reporting a value on all possible bundles of goods of interest along with a departure time. While such an enumeration may seem daunting at first glance, there are several reasons not to view this as a major concern in consumer markets. First, a very common purchasing scenario is for a buyer to want a single item or to be indifferent among only a few different items. Second, Cantillon and Pesendorfer [15] and Sandholm [59] provide empirical support that buyers can manage to construct bids in large combinatorial settings. Third, a number of expressive, concise bidding languages have been developed for combinatorial auctions [9, 17, 45] . It is also possible to allow buyers to provide lower-bounds on values, and increase these bounds over time just as with the mandatory proxy bidding agents of eBay (see Section 6 for further discussion on this point). Introduction A buyer's proxy agent uses the reported information about value and departure time to determine how to bid for options and also to determine which options held at the buyer's reported departure time to exercise. The options that maximize the buyer's surplus given the reported valuation are exercised and all other options returned to the sellers. The options-based protocol is useful because it makes truthful and immediate revelation to a proxy a dominant strategy for buyers, whatever the future auction dynamics. Thus it can be seen as a method to generalize eBay's existing proxy scheme to handle the sequential auction problem in suitable categories of goods, while extending to embrace dynamic, combinatorial auctions. Introduction In addressing questions about market efficiency and revenue we perform an empirical analysis using data on eBay auctions for 19 Dell LCD monitors (Model E193FP) sold from 27 May, 2005 through 1 October, 2005. A conservative estimate is that an improvement in efficiency and revenue of around 4% and 9% respectively would be enabled through an optionsbased scheme. This estimate is generated on the basis of non-parametric estimation of the true value of buyers for items, generalizing a method due to Haile and Tamer [28] to sequential auctions. The eBay analysis also informs an extensive set of simulation experiments, in which we explore the effect of substitutes ("I want A or B") and complements ("I only want A if I also get B") valuations on the efficiency of the options-based scheme and also consider the impact of market liquidity. Buyer populations with substitutes valuations can hamper the efficiency of the marketplace because of hold-up problems in which a buyer's proxy holds a number of options that ultimately go unexercised but were unavailable to other buyers. However we find that this effect is mitigated when individual buyers have negatively correlated values across items. We also find that the buyer-to-seller ratio (a measure of liquidity) plays a critical role in market efficiency in the context of substitutes valuations. Efficiency first decreases and then increases as the buyer-to-seller ratio increases and the market becomes more competitive. For a low buyer-to-seller ratio the market remains efficient with substitutes valuations because there is plenty of supply. Market efficiency is also high for relatively large buyer-to-seller ratios (above 4:1 in our simulations) and substitutes valuations because increased competition segments the market; buyers tend to be competitive on only a small number of goods. In the context of complements valuations we find that market efficiency is fairly insensitive to positive or negative correlation in value across items and remains reasonably high. Introduction We also provide a worst-case analysis for the practically important special case in which buyers are interested in only one kind of good. This analysis is a slight extension of that due to Hajiaghayi et al. [29] . In our analysis, we parameterize the competitive ratio in terms of the maximal spread of upper and lower valuations across all buyers. The main focus of our evaluation remains empirical, and we do not provide any worst-case analysis for the general, combinatorial case. Introduction By providing a system in which buyers possess a simple, dominant strategy, the proxy-based solution arguably reduces the participation costs of buyers. While the impact of this improvement is hard to estimate, this can be expected to both improve buyer loyalty to sellers and also make the market more appealing for new entrants. These two effects ought to preserve and enhance the health of the market and maintain seller revenue in the long term. Introduction In outline, we first discuss related work, and then use Section 2 to introduce the model and define and characterize the sequential auction problem. Section 3 describes the options-based scheme, giving examples and a complexity analysis. Section 4 provides a strategic analysis and a worst-case efficiency analysis. Section 5 presents an experimental study, first on eBay data (the LCD market) and then extending -in simulation -to consider substitutes and complements preferences and the effect of market liquidity. Section 6 discusses the challenges of allowing proxy agents to bid less aggressively, thus mitigating hold-up. Section 7 concludes. Related work A number of authors have analyzed sequential auctions selling the same item with buyers interested in buying just a single item. This "multiple copies problem" is often studied in the context of explaining sniping behavior; see also Ockenfels and Roth [46] , who give a collusion-based explanation for sniping. From the perspective of developing models for the multiple copies problem, Stryszowska [66] models the problem as one of a dynamic multi-unit auction, allowing for explanations of sniping as well as for bidding multiple times within an auction. Hendricks et al. [32] demonstrate that sniping is a symmetric equilibrium in the absence of a "BuyItNow" opportunity (wherein a buyer can choose to buy an item at any point for some fixed price). Wang [68] demonstrates, using a two-period model, how sniping in the first period is a unique equilibrium and Zeithammer [71] provides an equilibrium model for strategic sellers and forward-looking buyers. Notably, none of this prior work considers buyers that are able to participate in more than two auctions, while we consider settings in which buyers may participate in an arbitrary number of auctions. Peters and Severinov [52] also allow this more general capability and characterize a perfect Bayesian equilibrium where sellers set a reserve price equal to their true costs. These authors consider neither buyers entering at random times nor auctions closing at different times, both of which are addressed in our work. While these papers provide a Bayesian-Nash analysis of models that approximate current eBay-like markets, we study the dominant strategy equilibrium in an options-based variation on current markets. Related work Problems of the same kind as the sequential auction problem were previously observed by Wellman and Wurman [69] in the context of boundaries between multiple mechanisms, and later discussed by Parkes [48] and Ng et al. [43, 44] in the context of "strategyproof computing". The problem has often been identified in the context of simultaneous ascending price auctions, where it is termed the exposure problem [14] . Previous work addressing the exposure problem has considered two different directions. First, one can change the mechanism and define an expressive bidding language and a strategyproof mechanism, as seen in work on combinatorial auctions [56] . Second, one can attempt to provide automated bidding agents with sophisticated strategies, as seen for example in the work of Boutilier et al. [8] , Byde et al. [13] , Anthony and Jennings [1] , Reeves et al. [53] , and Gerding et al. [24] . Unfortunately, it seems hard to design artificial agents with equilibrium bidding strategies, even for a simultaneous ascending price auction (i.e., without dynamic arrivals of new sellers) and all these papers make significant assumptions. Related work Iwasaki et al. [34] have previously considered the use of options in the context of a single, monolithic, auction design to help buyers with increasing marginal values avoid exposure in a multi-unit, homogeneous item auction. Sandholm and Lesser [61] have considered options in the form of leveled commitment contracts for facilitating multi-way recontracting in a completely decentralized market place. Rothkopf and Engelbrecht-Wiggans [55] discuss the advantages associated with the use of options for selling coal mine leases. To the best of our knowledge, ours is the first work to study the role of options as a method to enable dominant strategies in the context of dynamic auctions. Gopal et al. [25] have considered the use of options for reducing exposure to risk in the context of the sequential auction problem. Our work differs in a number of ways, including how the options are priced, which buyers obtain options, and in how much risk remains with buyers once options are used. Buyers still face risk and have no dominant strategy in the method of Gopal et al. [25] . Related work The technical contribution of this paper is related to online mechanism design [30, 36, 49, 50] . In online mechanism design (online MD), one seeks an incentive mechanism for a dynamic environment in which agents arrive and depart and in which there is uncertainty about the future. In the analysis of our protocol, we slightly generalize the price-based characterization of Hajiaghayi et al. [29] to establish a dominant strategy equilibrium for buyers, creating a truthful online combinatorial auction from an uncoordinated sequence of single item auctions. The options-based scheme extends the earlier protocol in Hajiaghayi et al. [29] to combinatorial settings, although without providing any worst-case analysis. The mechanism presented here reduces to this earlier mechanism in an environment in which everyone is buying and selling a single unit of the same kind of good, although reinterpreted here within a decentralized architecture. Related work A dynamic VCG mechanism [18, [49] [50] [51] could, in principle, be used in this environment because we consider only onesided private information (and ignore strategic considerations on the sell side). But on the other hand, these mechanisms require optimal allocation policies (which may be intractable in domains of interest) together with a probabilistic model of agent arrivals and valuations, and provide within-period ex post incentive-compatibility rather than dominant-strategy incentive-compatibility [6, 18] . One would also need to consider how to divide the revenue collected by the mechanism across multiple sellers. A dynamic extension of the expected externality mechanism [2, 21] is available for dynamic two-sided markets [3] , but would again require an optimal policy and provide only a weak guarantee about the relationship between a buyer's payment and her bid price. Bredin et al. [10] develop a framework for constructing dynamic double auctions with dominant-strategy incentive-compatibility on both sides of the market, but their methods are applicable only in the limited setting in which all agents trade only a single unit of the same good. Related work It is interesting to note that some of the strategic difficulties that buyers face in uncoordinated electronic auctions such as eBay are also faced by consumers acquiring items in the retail sector and it is interesting that retail stores have developed policies that can be interpreted as assisting customers in this regard. Return policies alleviate the exposure problem by allowing customers to return goods at the purchase price while price matching alleviates the multiple copies problem by allowing buyers to receive from sellers after purchase the difference between the price paid for a good and a lower price found elsewhere [19, 38] . A concern that is discussed in the academic literature in regard to these practices in the retail sector is that they can be anti-competitive, with sellers using them as a commitment device for avoiding price competition [33] . We do not foresee this issue in the context of proxied, sequential auctions as proposed in this paper because the prices are not set by sellers but rather determined by competition on the buy side. Related work There has been some follow-up work to an earlier version of this paper. Mous et al. [42] present work on a variation of our scheme in which options are priced, and adopt a decision-theoretic analysis in exploring the effect on the sequential auction problem. This stands in contrast to our game-theoretic analysis, but has interest because it provides for less aggressive options accumulation by buyers. Preliminaries: The sequential auction problem In this section we introduce the formal model and define and characterize the sequential auction problem which motivates our work. The model where Θ is the set of all possible types, defining her arrival time a i ∈ T , departure time d i a i ∈ T , and valuation v i (L) 0 for every possible bundle of goods L ⊆ G. There are multiple copies of each good G k for sale but no buyer demands more than a single unit of each good and we write L k ∈ {0, 1} to denote whether or not bundle L contains a unit of good G k . 8 We The model The semantics of arrival and departure are such that buyer i has value v i (L) 0 for a bundle of goods L ⊆ G that is allocated (potentially in multiple pieces) across periods [a i , . . . , d i ] but has no value for goods allocated outside of this time interval. Buyers have quasi-linear utilities, so that the utility of buyer i for receiving bundle L and paying p ∈ R 0 , in some period no later than The model For the sake of analysis it is convenient to assume the existence of a maximal patience, such that d i − a i ∆ max , for some constant ∆ max . The model We motivate the semantics of the arrival time by associating this with the period in which a buyer first realizes her demand for the good(s), or as the period at which a buyer first realizes that the market exists. The departure time models the period in which a buyer loses interest in acquiring the good(s) from this marketplace. For example, a buyer may lose interest in items whose value is realized at a specific past moment in time (e.g., Saturday night movie tickets), or because she simply wishes to take advantage of an outside opportunity to acquire the item (e.g., a buyer deciding to acquire an item at a posted price on a certain date). The model is restrictive in that it precludes a buyer having probabilistic beliefs about her value before arrival. 9 The model also requires that a buyer has constant value during the arrival-departure interval. The model This seems reasonable when this interval is small in relation to the time over which the good(s) will be used; e.g., an LCD monitor that a buyer plans on using for 3 years provides a buyer with roughly equivalent value if held for 1000 days or 998 days. The model Each seller j ∈ S brings a single unit of one kind of good, denoted k j ∈ G to the market and is assumed to have no intrinsic value for the good. Seller j has an arrival time, a j ∈ T , which models the period in which she is first interested in listing the item, and a departure time, d j a j ∈ T , which defines the latest period in which she is willing to consider having an auction for the item close. By listing a good for sale until d j , a seller is indicating her willingness to receive payment by the end of the reported departure of the winning buyer in an auction closing at d j , while preferring to exit the market 8 The static version of this model was earlier referred to by Bartal et al. [5] as the "k-duplicates" combinatorial auction, with in their terminology k-units of each good and each buyer restricted to buying at most one unit of each good. We adopt k to reflect the number of kinds of goods rather than the number of units of each good. 9 One reviewer suggested that another justification could be that the arrival time simply represents a constraint on the earliest period at which a bidder is able to participate. The model to each buyer. The outcome also depends on the sell-side, i.e., the goods that are brought to market, but we leave this dependence silent in the notation. Since this is an online setting, where the bids are reported over time, the allocation and payment functions must be online computable; i.e., if a buyer is to be allocated an item for sale in period t then this must be known based on information available up to and including period t. We adopt the standard assumption of limited misreports [29, 30, 36] , with buyers unable to bid before their true arrival period. This is equivalent to requiring that reported type, The model Given that the arrival time models the period in which a buyer first realizes her demand and enters the market, this assumption simply asserts that a buyer will not enter a market for goods for which she currently has no perceived value. Given this assumption, then strategy The model Given this assumption of limited misreports, which we make for the rest of our analysis, a mechanism is said to be strategyproof (for the buy-side) when reporting the true type is a dominant strategy equilibrium for buyers. Truthful reporting by buyers is required to be a dominant strategy for all realizations of supply. Moreover, and even though we are not concerned with strategic sellers here, this also provides robustness for buyers against strategic seller behavior. The model Our concern here is with online markets that are structured as a sequence of separate auctions. For this reason, it is helpful to adopt the terminology locally strategyproof, in describing an auction in which truthful bidding is a dominant strategy if a buyer was restricted to bidding in that one auction [48] . This would be true, for example, if the auction is for a unique item that is only available for auction once in a buyer's lifetime (e.g., a piece of artwork for which there is no substitute), or if a buyer is very impatient. In Section 5 we present empirical evidence to suggest that this is generally not a good assumption in markets such as eBay, and it is this observation that leads to the sequential auction problem. The model One metric for the performance of our mechanism will be efficiency. The efficiency is a measure of the total value of buyers for an allocation of goods. For the empirical analysis, we will generally adopt one of the following two metrics for efficiency: The model • average buyer value, • total buyer value normalized by the value of an online benchmark. The model Average buyer value provides a suitable efficiency metric when buyers are each interested in one unit of one good, i.e. the "single item demand" setting. No normalization is required when comparing the options-based scheme with the efficiency of eBay in this setting, because all goods are sold under both mechanisms and thus the total number of winning buyers is the same. The model But when considering buyers with substitutes valuations, we normalize to an online benchmark because the total number of winning buyers varies between our simulation of eBay and the options-based scheme. The benchmark is explained in Section 5.2. For the case of complements valuations, it will be sufficient for our analysis (which is focused on the effect of correlations on values across items) to consider the total buyer value. We will adopt analogous metrics for seller revenue and buyer surplus; see Section 5. The model For the purpose of theoretical analysis, we will also adopt a worst-case analysis for the single item demand setting, where we bound the worst-case efficiency of the options-based mechanism as a fraction of the value of the best offline solution, i.e., the best omniscient solution. The sequential auction problem The sequential auction problem describes the strategic problem that can face a buyer even though she faces a sequence of locally strategyproof auctions. Consider the following two motivating examples: Example 1. Alice values acquiring one ton of sand before Wednesday for $1000. Bob will hold a Vickrey auction for one ton of sand on Monday, and another such auction on Tuesday. Alice has no dominant bidding strategy because she cannot predict whether the price of the Tuesday auction will be greater or less than the price of the Monday auction, and she needs to know this price when deciding on an optimal bidding strategy on Monday. The sequential auction problem Example 2. Alice values one ton of sand with one ton of stone at $2000. Bob holds a Vickrey auction for one ton of sand on Monday. Charlie holds a Vickrey auction for one ton of stone on Tuesday. Alice has no dominant bidding strategy because she needs to know the price for stone on Tuesday in order to know how much to bid for sand on Monday. If Alice bids too high on Monday, she may be left with one ton of sand but no ability to buy the one ton of stone required to complete her construction project. If Alice bids too low on Monday, she might forfeit the opportunity to buy both the sand and stone, for example if the price of stone on Tuesday is low. Definition 1 (sequential auction problem). The sequential auction problem exists when a buyer has no dominant bidding strategy in a sequence of auctions, despite each auction being locally strategyproof. Definition 1 (sequential auction problem). There are a variety of ways in which an absence of a dominant strategy may arise. First, consider a buyer who values one ton of sand for $1000, one ton of stone for $2000 and both for $2000 (i.e., substitutes valuations). Suppose the buyer faces one auction for sand followed by one for stone and that the possible prices for either goods are unconstrained. She faces the sequential auction problem because there are future prices for which it is optimal to purchase sand and some for which it is optimal to purchase stone. In general, buyers with substitutes valuations face the sequential auction problem. As a second example, consider a buyer who values one ton of sand for $1000 and one ton of sand and one ton of stone together for $1500. Suppose that the buyer faces an auction for sand and another for stone and that either bundle {sand} or {sand, stone} may be the utility maximizing bundle given possible prices. She faces the sequential auction problem because the good that first goes to auction has uncertain marginal value; this value is either $1000 or $1500 if the good is sand and $0 or $500 if the good is stone. In general, buyers who are interested in goods whose marginal values are dependent on the acquisition of other goods face the sequential auction problem. Definition 1 (sequential auction problem). As another example, consider a buyer who values one ton of sand for $1000 and faces two auctions for sand, either of which may have the lowest price. She faces the sequential auction problem because even though the value of the sand is $1000 and constant in both auctions, either auction may have the best price. In general, buyers who are interested in fewer instances of a good than there are auctions selling that good face the sequential auction problem. For a final example, consider a buyer who values sand for $1000, stone for $500 and sand and stone together for $1500 (i.e., a linear valuation) and suppose just two auctions, one for sand and then one for stone. Suppose one other buyer competes in both auctions. If the competitor may bid $1,000,000 for stone if the buyer bids more than $300 for sand, and $10 otherwise, the buyer is better off bidding below $300 for sand, even if this involves losing that auction, because she will then receive the stone for a payoff of $1490. In general, buyers whose competitors condition future bids on the buyers' past bids face the sequential auction problem. An options-based scheme In what follows we focus exclusively on domains in which the underlying auctions are Vickrey auctions for individual items (i.e., second price, sealed-bid auctions). Vickrey auctions are selected not only because of convenience, but also because they nicely model eBay auctions. An options-based scheme The solution that we propose, in resolving the sequential auction problem in this context, consists of two primary components: the use of real options to allow buyers to secure the lowest possible prices and the use of mandatory proxy agents to prevent the abuse of these options through costless hoarding. A real option is a right to acquire a real good at a certain price, called the exercise price; see Dixit and Pindyck [22] . For instance, Alice may obtain from Bob the right to buy sand from him at an exercise price of $1000. An option gives the right to purchase a good at an exercise price but does not imply an obligation. We will see that this flexibility makes options useful in addressing the sequential auction problem. Proxy agents acting on behalf of buyers can put together a collection of options, and then decide which options (perhaps none) to exercise. An options-based scheme While the buyer of an option has the right but not the obligation to purchase the good, the seller must honor the contract if the option is exercised. For this reason, options are typically sold at a premium called the option price. Several factors are often considered when a seller tries to determine how to price an option with a particular exercise price, including the relationship between the exercise price and the perceived value of the good available in the option, the volatility of value the good may experience over time, and the length of time over which a buyer can decide to exercise the option. Real options are often difficult to price as the metrics for determining a price are difficult to quantify. However, among traded options (i.e., options for traded securities such as stock), much progress has been made in determining the prices of options, with one of the most celebrated being the formula of Black and Scholes [7] . An options-based scheme The problem with options with a non-zero option price in our setting is that they cannot support a simple, dominant bidding strategy because a buyer would need to compute the expected value of an option to justify the cost. But this expected value requires a probabilistic model of the future, which in turn requires the buyer to model the bidding strategies and values of other buyers. This is the very pattern of reasoning that we are trying to avoid in designing the options-based marketplace! For this reason, we adopt costless options, which always have an option price of zero. The exercise price is set competitively in the marketplace. An options-based scheme The traditional issue with costless options is that buyers are always weakly better off with a costless option than without one, whatever the exercise price. A buyer need exercise only those option(s) that result in a gain of surplus and bears no cost by not exercising an option. But having buyers that pursue options that they have no intention of exercising would cause market efficiency to unravel. To prevent this kind of hoarding of options, we adopt mandatory proxy agents. These proxy agents provide buyers with an obligation to exercise those options that maximize their reported utility -as defined by reported valuationv i -given the exercise price. The proxy agents also act to restrict buyers to acquiring only options that they might credibly choose to exercise. 10 Only proxy agents place bids in the underlying auctions. An options-based scheme In Section 3.1 we give details about the proxied, options-based solution. Section 3.2 provides a number of detailed examples and Section 3.3 provides a complexity analysis. We delay until future sections a formal proof of strategyproofness and any analysis of the efficiency and revenue properties. The bidding proxy and price-matching rules In our framework we first modify each individual Vickrey auction to sell a real option for the underlying good to the highest bidder with an initial exercise price equal to the second-highest bid price received. 11 Each option is costless, and is set to expire at the end of the winning proxy's patience. Proxy agents bid in these auctions. In opting into the options-based protocol, a seller gives the winning proxy agent the right to reduce the exercise price on the option issued by the seller given evidence that a lower price would have been available had the proxy waited and bid instead in some future auction. This is what we mean by "price matching." The bidding proxy and price-matching rules Buyers must compete in the market by submitting a bid to their proxy agent. For buyer i ∈ B, this bid occurs in some reported arrival time,â i a i , and is a claim about her valuationv i (perhaps untruthful) for different bundles of goods and also about her departure timed i â i . All transactions are intermediated by proxy agents. In what follows, we describe the three steps that are followed by a proxy agent: (a) acquiring options, (b) setting the exercise price on options via seller-sanctioned price matching, and (c) exercising options. This completely defines the options-based mechanism. The bidding proxy and price-matching rules Step one: Acquiring options. When an option for a good in which a buyer is interested is available in an auction and the proxy does not hold an option, the proxy submits a bid equal to the buyer's (reported) maximum marginal value for the item. A proxy does not bid for an item on which it already holds an option. The maximum marginal value for an item G k , given reported valuationv i , is defined as: By bidding this value, a proxy will compete for any option that could possibly be of benefit to the buyer and choose not to bid only on those options that could never be of value to the buyer. Note that this is a static determination, made entirely in terms of the valuation of a buyer and without considering the prices for which the proxy already holds options. In bidding up to the maximal possible value of some item, the proxy is considering the case that all goods in bundle L that go together with this good will be available and for a price of $0. 12 Step two: Setting the exercise price. Rather than acquire more than one option on the same kind of good, proxy agents are authorized by sellers to adjust the exercise price of an option that they win downwards (from the initially set price of the second-highest bid). Such an adjustment is made whenever a proxy discovers that it could have achieved a better exercise price for an option on the same kind of good by waiting to bid in a later auction. A proxy is able to identify such a missed opportunity by storing locally, for each good on which it holds an option, the identity of the active bidder (if any) that would have already won an option had the proxy itself not won an option. Initially, when a proxy wins an option it stores in its local memory the identity (which may be a pseudonym) of the proxy agent that it "bumped" from winning, if such a proxy exists (i.e., the second-highest bidder). 12 To see how price matching works, fix some good G k on which Proxy A holds an option. Proxy A now monitors each future auction for the same kind of good and determines what the buyer population would be had Proxy A delayed its own bid until that auction. To make this determination, Proxy A requests from the auction the identities of the buyer proxies (if any) and their bids. 13 Proxy A identifies the highest bid across those proxies whose identity is not stored in A's local memory. This is the bid against which Proxy A would be competing had A delayed its entry until this auction. If the bid price of Proxy B is lower than Proxy A's current exercise price, Proxy A price matches down to Proxy B's bid price, since this is exactly the price that Proxy A could have achieved by delaying its bid until this later auction. If there is no such bid from another proxy then the price is matched down to zero (or a reserve price, if any). 10 Unlike in the financial markets, our solution does not permit option holders to sell their options to others. Therefore, proxies have no incentives to hoard costless options speculating on future option reselling opportunities. 11 The system can also set a reserve price for each kind of good, provided that the same reserve is adopted for all auctions selling the same good. Without such an invariant reserve price, price matching would not be possible as a seller might be required to match a price below their personal reserve price. Exploring how limiting this may be in scenarios where sellers actually have different reservation values is an area of future work. 12 If the proxy has knowledge that some items will not be for sale, or can lower-bound the possible price on other items (e.g., because of a market-wide reservation price adopted by sellers -see Footnote 11), then the marginal value can be modified downwards to preclude such bundles or adjust downward by lower bounds on the price of items. Care must be taken, though. We return to this issue in Section 6. 13 In a marketplace such as eBay, this information could be provided (again in pseudonymous form) by the market infrastructure. Moreover, the only information that is minimally required is the highest bid price across all buyer proxies except one stated by the proxy, and the identity of the highest proxy if it was not the winner of the auction. Formally, the exercise price p t (k) in period t on good G k on which the proxy holds an option is set to minâ i τ t {p τ 12 (k) is the maximal bid price across other proxies in period τ on good G k , but excluding any bid from a proxy whose identity is stored in i's local memory in period τ . If there are no such bids from other proxies, then p τ 12 (k) is set to zero (or a reserve price, if any). 12 After price matching, one of two adjustments is made by Proxy A for bookkeeping purposes. First, if Proxy B was the winner of this latest auction, Proxy A's local memory as it relates to this good can be cleared. This is because the proxy earlier bumped by Proxy A must no longer be bidding (otherwise it would have won this latest auction before Proxy B), and thus Proxy A's earlier win no longer affects the set of active bidders for this good going forward. On the other hand, if Proxy B is the second-highest bidder in this latest auction (having been outbid by the proxy stored in Proxy A's local memory), Proxy B will now be stored in Proxy A's local memory, as Proxy B would have won the good without the presence of Proxy A in the market (because the proxy stored in Proxy A's local memory would not have competed against Proxy B in this latest auction had Proxy A never been around to bump it from the auction that Proxy A won). 12 Step three: Exercising options. At the reported departure time,d i , the proxy for buyer i chooses which options (if any) to exercise. The option(s) that are exercised, L * i , are those that maximize the reported utility of the buyer given the final exercise price on each good: 12 where O is the set of all options held by the proxy, γ (L) ⊆ G are the goods that correspond to some subset L ⊆ O of these options, and p(L) = k∈L p(k) is the total exercise price for this set of options where p(k) is the exercise price on the option corresponding to good G k (as determined via price-matching). All other options are returned. No options are exercised when there is no bundle of options with (weakly) positive utility. 12 Remark: Re-posting seller options. An auction for the good brought to market by a seller will first occur at the arrival period of the seller. If at some point later the buyer that wins this auction returns the option unexercised and the time period is before the seller's departure then it would be ideal to be able to initiate another auction for an option on the seller's good. However, the system prevents a seller from re-auctioning an option until the maximal patience, ∆ max , after the option was first allocated. Recall that ∆ max defines the maximal patience (departure-arrival) over all possible buyers in the market. 12 14 This maintains a truthful mechanism by preventing a buyer from acquiring an option with a view to holding it, returning it unexercised, and later re-entering the market when the option is again auctioned and achieving a lower price. 15 In the absence of strong identities, where the market definitively knows the identity of each market participant, the market prevents buyers from affecting future supply in a useful way by waiting a sufficiently long amount of time before reauctioning a returned option. 16 However, in the presence of strong identities, the market can explicitly prevent a proxy's buyer who has returned an option from bidding on that option for ∆ max into the future. Consequently, a seller can reauction an option as soon as it is returned, increasing the likelihood of selling the item before her departure. Examples of proxy behavior We first provide an example to illustrate the price-matching logic that is followed by proxies (also illustrated as Table 1) : Examples of proxy behavior Consider three buyers, all of whom enter the market on Monday and depart the market after Tuesday. Molly values an item for $8, Nancy for $6 and Polly for $4. On Monday, an auction occurs where all three proxies bid, with Molly's 14 In practice one might choose to make a tradeoff here, in which that gain from allowing earlier reposting of an item can be traded for the cost of losing strategyproofness for the most patient buyers. 15 Here 16 One common technique that is used at present to achieve strong, or almost strong, identities in electronic markets is to require a unique cell phone number or credit card number of every registration. Examples of proxy behavior proxy winning with the highest bid of $8 and receiving an option for $6. Molly's proxy adds Nancy to its local memory. On Tuesday, another auction occurs where only Nancy's and Polly's proxies bid, with Nancy's proxy winning an option for $4 and noting that it bumped Polly's proxy. At this time, Molly's proxy will price match its option down to $4 (because Nancy is already in memory) and replace Nancy with Polly in its local memory for bookkeeping purposes, as Polly would be holding an option had Molly delayed her bid past this round. Examples of proxy behavior To illustrate how the options-based scheme handles the exposure problem, consider the following example where Alice desires a bundle of two goods: Example 4. Alice values one ton of sand and one ton of stone together for $3000 (but has no value for either by itself). Bob values one ton of sand for $800. Charlie values one ton of stone for $2000. All buyers have a patience of 2 days. On day one, a stone auction is held, where Alice's proxy bids $3000 and Charlie's bids $2000. Alice's proxy wins an option to purchase stone for $2000. On day two, a sand auction is held, where Alice's proxy bids $3000 and Bob's bids $800. Alice's proxy wins an option to purchase sand for $800. At the end of the second day, Alice's proxy holds an option to buy stone for $2000 and sand for $800 and exercises both options spending a total of $2800. Examples of proxy behavior As an illustration of how the options-based scheme handles substitutes values consider the following example: Examples of proxy behavior Example 5. Alice values either one ton of coarse sand for $1000, or one ton of fine sand for $800 (but only $1000 for both). Bob values coarse sand for $800. Charlie values fine sand for $900. On day one, a coarse sand auction is held where Alice's proxy bids $1000 and Bob's proxy bids $800, resulting in Alice's proxy winning an option for the coarse sand with an exercise price of $800. On day two, a fine sand auction is held where Alice's proxy bids $800 and Charlie's proxy bids $900, resulting in Charlie's proxy winning an option for the fine sand with an exercise price of $800. At the end of day two, Alice's proxy exercises its coarse sand option and Charlie's proxy exercises its fine
{'paper_id': '12246390', 'title': 'An Options-Based Solution to the Sequential Auction Problem', 's2_url': 'https://api.semanticscholar.org/CorpusID:12246390', 'source': 'S2ORC'}