Duke Computer Science's Theory Group members are honored to have eight papers accepted at the January 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA) conference, with six of the Duke CS papers co-written by our graduate students. Read a brief summary of one of these papers, "Fair Price Discrimination," below.
Imagine a scenario where a seller is selling copies of an item, like tickets to a museum or copies of a computer software. Each buyer can potentially value the item differently. For example, some might be willing to pay more for a ticket because they love art more than others. With the rise of modern machine learning tools, it has become easier for an online retailer to ascertain the amount a buyer is willing to pay without asking the buyer directly. The seller can hence "price discriminate," meaning it can charge different buyers different amounts for the same product. For example, if the seller knows you really love art, she might charge you more for a museum ticket than someone who's just mildly interested.
At one extreme, the seller can decide to make the most money by charging everyone exactly what they are willing to pay. However, this takes away all the joy of buying since buyers are paying as much as they think the item is worth. A compromise between setting one price and setting prices at the buyers' willingness to pay is to split the market into a few price segments and assign each buyer to one of these segments. For instance, the segments could be "low" and "high," with one price for each. This can be implemented by an intermediary, say the machine algorithm, that learns buyer value, selectively revealing this value information to the seller.
The question then becomes, what is a good way to segment the market? First off, the seller’s revenue should not be hurt by the segmentation. Second, we want happiness to be spread fairly across buyers, so that neither low-valued nor high-valued buyers are inordinately happier than the other type. We formalize these notions mathematically and show somewhat surprisingly that there is a single market segmentation that approximately optimizes any fairness function over buyer happiness, while also being fair to the seller.
