Sign In

Communications of the ACM

Last byte

Upstart Puzzles: Auction Triplets

Auction Triplets, illustration

Credit: Andrij Borys Associates / Shutterstock

There are objects of four types and n people, each with a budget of $99. The objective of each one is to acquire three objects of the same type (any type) before anyone else does; for example, if player A acquires three type 1 objects before any other player acquires any three objects of any type, A wins. Assume each auction is resolved through a highest-bid method; that is, the highest bidder pays the amount he or she bids (Vickrey auctions are a possible variant.) Every bid must be an integral number of dollars. If there is a tie, the bidder (if any) who won the immediately preceding auction gets the item if that bidder is one of those who tied. In every other case, the tie ends in a draw, and nobody takes the item in that auction.

By symmetry, there cannot be a guaranteed winning strategy, but the general challenge is to work out probabilistically good strategies, given knowledge of the sequence of item types to be auctioned.


No entries found

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
ACM Resources