Identifying high-revenue mechanisms that are both dominant strategy incentive compatible (DSIC) and individually rational (IR) is a fundamental challenge in auction design. While theoretical approaches have encountered bottlenecks in multi-item combinatorial auctions, there has been much empirical progress in the automated design of such mechanisms using machine learning. However, existing research primarily focuses on randomized auctions, with less attention given to more practical deterministic auctions. Therefore, in this paper, we introduce OD-VVCA, an objective decomposition approach for automated designing revenue-maximizing deterministic Virtual Valuations Combinatorial Auctions (VVCAs), which are inherently DSIC and IR. We use a parallelizable dynamic programming algorithm to compute the allocation and revenue outcomes of a VVCA efficiently. We then decompose the revenue objective function into continuous and piecewise-constant discontinuous components, optimizing each using distinct methods. Extensive experiments show that OD-VVCA achieves high revenue in multi-item auctions, especially in large-scale settings where it outperforms both randomized and deterministic baselines, indicating its efficacy and scalability.

On e-commerce platforms, sellers typically bid for impressions from ad traffic to promote their products. However, for most sellers, the majority of their sales come from organic traffic. Consequently, the relationship between their ad spending and total sales remains uncertain, resulting in operational inefficiency. To address this issue, e-commerce platforms have recently introduced a novel platform-wide marketing service known as QuanZhanTui, which has reportedly enhanced marketing efficiency for sellers and driven substantial revenue growth for platforms. QuanZhanTui allows sellers to bid for impressions from the platform's entire traffic to boost their total sales without compromising the platform's user experience. In this paper, we investigate the mechanism design problem that arises from QuanZhanTui. The problem is formulated as a multi-objective optimization to balance sellers' welfare and platform's user experience. We first introduce the stock-constrained value maximizer model, which reflects sellers' dual requirements on marketing efficiency and platform-wide ROI. Then, we propose the Liquid Payment Auction (LPA), an auction designed to optimize the balanced objectives while accounting for sellers' requirements in the auto-bidding environment. It employs a simple payment rule based on sellers' liquid welfare, providing a clearer link between their investment and total sales. Under mild assumptions, we theoretically prove desirable properties of LPA, such as optimality and incentive compatibility. Extensive experiments demonstrate LPA's superior performance over conventional auctions in QuanZhanTui.

In online advertising, advertisers commonly utilize auto-bidding services to bid for impression opportunities. A typical objective of the auto-bidder is to optimize the advertiser's cumulative value of winning impressions within specified budget constraints. However, such a problem is challenging due to the complex bidding environment faced by diverse advertisers. To address this challenge, we introduce ABPlanner, a few-shot adaptable budget planner designed to improve budget-constrained auto-bidding. ABPlanner is based on a hierarchical bidding framework that decomposes the bidding process into shorter, manageable stages. Within this framework, ABPlanner allocates the budget across all stages, allowing a low-level auto-bidder to bids based on the budget allocation plan. The adaptability of ABPlanner is achieved through a sequential decision-making approach, inspired by in-context reinforcement learning. For each advertiser, ABPlanner adjusts the budget allocation plan episode by episode, using data from previous episodes as prompt for current decisions. This enables ABPlanner to quickly adapt to different advertisers with few-shot data, providing a sample-efficient solution. Extensive simulation experiments and real-world A/B testing validate the effectiveness of ABPlanner, demonstrating its capability to enhance the cumulative value achieved by auto-bidders.

The standard framework of online bidding algorithm design assumes that the seller commits himself to faithfully implementing the rules of the adopted auction.However, the seller may attempt to cheat in execution to increase his revenue if the auction belongs to the class of non-credible auctions.For example, in a second-price auction, the seller could create a fake bid between the highest bid and the second highest bid.This paper focuses on one such case of online bidding in repeated second-price auctions.At each time 𝑡, the winner with bid 𝑏 𝑡 is charged not the highest competing bid 𝑑 𝑡 but a manipulated price 𝑝 𝑡 = 𝛼 0 𝑑 𝑡 + (1 -𝛼 0 )𝑏 𝑡 , where the parameter 𝛼 0 ∈ [0, 1] in essence measures the seller's credibility.Unlike classic repeated-auction settings where the bidder has access to samples (𝑑 𝑠 ) 𝑡 -1 𝑠=1 , she can only receive mixed signals of𝑠=1 and 𝛼 0 in this problem.The task for the bidder is to learn not only the bid distributions of her competitors but also the seller's credibility.We establish regret lower bounds in various information models and provide corresponding online bidding algorithms that can achieve near-optimal performance.Specifically, * Both authors contributed equally to this research.

In the digital age, resources such as open-source software and publicly accessible databases form a crucial category of digital public goods, providing extensive benefits for Internet. However, these public goods' inherent non-exclusivity and non-competitiveness frequently result in under-provision, a dilemma exacerbated by individuals' tendency to free-ride. This scenario fosters both cooperation and competition among users, leading to the public goods games. This paper investigates networked public goods games involving heterogeneous players and convex costs, focusing on the characterization of Nash Equilibrium (NE). In these games, each player can choose her effort level, representing her contributions to public goods. Network structures are employed to model the interactions among participants. Each player's utility consists of a concave value component, influenced by the collective efforts of all players, and a convex cost component, determined solely by the individual's own effort. To the best of our knowledge, this study is the first to explore the networked public goods game with convex costs. Our research begins by examining welfare solutions aimed at maximizing social welfare and ensuring the convergence of pseudo-gradient ascent dynamics. We establish the presence of NE in this model and provide an in-depth analysis of the conditions under which NE is unique. We also delve into comparative statics, an essential tool in economics, to evaluate how slight modifications in the model--interpreted as monetary redistribution--affect player utilities. In addition, we analyze a particular scenario with a predefined game structure, illustrating the practical relevance of our theoretical insights. Overall, our research enhances the broader understanding of strategic interactions and structural dynamics in networked public goods games, with significant implications for policy design in internet economic and social networks.

In today's online advertising markets, it is common for advertisers to set long-term budgets. Correspondingly, advertising platforms adopt budget control methods to ensure that advertisers' payments lie within their budgets. Most budget control methods rely on the value distributions of advertisers. However, due to the complex advertising landscape and potential privacy concerns, the platform hardly learns advertisers' true priors. Thus, it is crucial to understand how budget control auction mechanisms perform under unassured priors.

On typical e-commerce platforms, a product can be displayed to users in two possible forms, as an ad item or an organic item. Usually, ad and organic items are separately selected by the advertising system and recommendation system, and then combined by a content merging mechanism. Although the design of the content merging mechanism has been extensively studied, little attention has been given to a crucial situation where there is an overlap between candidate ad and organic items. Despite its common occurrence, this situation is not correctly handled by almost all existing works, potentially leading to incentive problems for advertisers and the violation of economic constraints. To address these issues, we revisit the design of the content merging mechanism. We introduce a necessary property called form stability, and provide simplification results of the mechanism design problem. Furthermore, we design two simple mechanisms strictly ensuring desired economic properties including incentive compatibility, and demonstrate their guaranteed performance through competitive ratio analysis under certain conditions.

Learning-based ad auctions have increasingly been adopted in online advertising. However, existing approaches neglect externalities, such as the interaction between ads and organic items. In this paper, we propose a general framework, namely Score-Weighted VCG, for designing learning-based ad auctions that account for externalities. The framework decomposes the optimal auction design into two parts: designing a monotone score function and an allocation algorithm, which facilitates data-driven implementation. Theoretical results demonstrate that this framework produces the optimal incentive-compatible and individually rational ad auction under various externality-aware CTR models while being data-efficient and robust. Moreover, we present an approach to implement the proposed framework with a matching-based allocation algorithm. Experiment results on both real-world and synthetic data illustrate the effectiveness of the proposed approach.

Understanding the convergence properties of learning dynamics in repeated auctions is a timely and important question in the area of learning in auctions, with numerous applications in, e.g., online advertising markets. This work focuses on repeated first price auctions where bidders with fixed values for the item learn to bid using mean-based algorithms – a large class of online learning algorithms that include popular no-regret algorithms such as Multiplicative Weights Update and Follow the Perturbed Leader. We completely characterize the learning dynamics of mean-based algorithms, in terms of convergence to a Nash equilibrium of the auction, in two senses: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium approaches 1 in the limit; (2) last-iterate: the mixed strategy profile of bidders approaches a Nash equilibrium in the limit. Specifically, the results depend on the number of bidders with the highest value: Our discovery opens up new possibilities in the study of convergence dynamics of learning algorithms.

In this paper, We revisit the sponsored search auction as a repeated auction. We view it as a learning and exploiting task of the seller against the private data distribution of the buyers. We model such a game between the seller and buyers by a Private Data Manipulation (PDM) game: the auction seller first announces an auction for which allocation and payment rules are based on the value distributions submitted by buyers. The seller’s expected revenue depends on the design of the protocol and the game played among the buyers in their choice on the submitted (fake) value distributions.

In this paper, we propose a phrase-based document similarity to compute the pair-wise similarities of documents based on the suffix tree document (STD) model. By mapping each node in the suffix tree of STD model into a unique feature term in the vector space document (VSD) model, the phrase-based document similarity naturally inherits the term tf-idf weighting scheme in computing the document similarity with phrases. We apply the phrase-based document similarity to the group-average Hierarchical Agglomerative Clustering (HAC) algorithm and develop a new document clustering approach. Our evaluation experiments indicate that, the new clustering approach is very effective on clustering the documents of two standard document benchmark corpora OHSUMED and RCV1. The quality of the clustering results significantly surpass the results of traditional single-word \textit{tf-idf} similarity measure in the same HAC algorithm, especially in large document data sets. Furthermore, by studying the property of STD model, we conclude that the feature vector of phrase terms in the STD model can be considered as an expanded feature vector of the traditional single-word terms in the VSD model. This conclusion sufficiently explains why the phrase-based document similarity works much better than the single-word tf-idf similarity measure.

In this paper, we propose a new similarity measure to compute the pairwise similarity of text-based documents based on suffix tree document model. By applying the new suffix tree similarity measure in Group-average Agglomerative Hierarchical Clustering (GAHC) algorithm, we developed a new suffix tree document clustering algorithm (NSTC). Experimental results on two standard document clustering benchmark corpus OHSUMED and RCV1 indicate that the new clustering algorithm is a very effective document clustering algorithm. Comparing with the results of traditional word term weight tf-idf similarity measure in the same GAHC algorithm, NSTC achieved an improvement of 51% on the average of F-measure score. Furthermore, we apply the new clustering algorithm in analyzing the Web documents in online forum communities. A topic oriented clustering algorithm is developed to help people in assessing, classifying and searching the the Web documents in a large forum community.

A severe potential security problem in utilization of Unicode on the Web is identified, which is resulted from the fact that there are many similar characters in the Universal Character Set (UCS). The foundation of our solution relies on evaluating the similarity of characters in UCS. We develop a solution based on the renowned Kernel Density Estimation (KDE) method to establish such a Unicode Similarity List (UC-SimList).

An approach to detection of phishing Web pages based on visual similarity is proposed, which can be utilized as a part of an enterprise solution to antiphishing. A legitimate Web page owner can use this approach to search the Web for suspicious Web pages which are visually similar to the true Web page. The approach first decomposes the Web pages into salient (visually distinguishable) block regions. The visual similarity between two Web pages is then evaluated in three metrics: block level similarity, layout similarity, and overall style similarity. A Web page is reported as a phishing suspect if any of them (with regards to the true one) is higher than its corresponding preset threshold. Preliminary experiments show that the approach can successfully detect those phishing Web pages with few false alarms at a speed adequate for online application.

With advances in World-Wide Web applications and technologies, research on measurement and modeling of Internet and Web-based information systems has become increasingly important This paper focuses on continuously monitoring Web traffic by packet sniffing on high-speed links, which is the foundation of analyzing theoretical models of Web characteristics and evolvement. The author presents MOT, a memory online tracing system of Web traffic. MOT parses all packets in memory directly without involving unnecessary I/0 operations with magnetic disks to enhance the system performance. Event-driven design pattern and several other techniques are adopted in MOT to overcome the difficulties of buffering huge volume of traffic. MOT provides a fast, accurate and safe way to obtain the source data for many Web-related studies.

Metasearch Engine is popular for facilitating users' queries over multiple search engines and increasing the coverage of the WWW. How to rank the merged results becomes crucial for the success of metasearch engines. Many current metasearch engines have poor precision, for one or more of selected source search engine returns irrelevant results. On the other hand, users with different interests may prefer distinct ranking order even for the same query. In this work, we try to use online relevance feedback to improve precision of the search results. At the same time, Users' preferences are recorded during the process of feedback for future ranking. Our elementary experiment shows that it is effective in improving precision of the metasearch engine.

Abstract In this paper we give an optimal parallel algorithm for two-dimensional linear programming with processor-time complexity ( n /log n , log n ) on a CRCW PRAM.