Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSelecting a Match: Exploration vs Decision
72
0
0.0
(
0
)
Added by
Ishan Agarwal
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In a dynamic matching market, such as a marriage or job market, how should agents balance accepting a proposed match with the cost of continuing their search? We consider this problem in a discrete setting, in which agents have cardinal values and finite lifetimes, and proposed matches are random. We seek to quantify how well the agents can do. We provide upper and lower bounds on the collective losses of the agents, with a polynomially small failure probability, where the notion of loss is with respect to a plausible baseline we define. These bounds are tight up to constant factors. We highlight two aspects of this work. First, in our model, agents have a finite time in which to enjoy their matches, namely the minimum of their remaining lifetime and that of their partner; this implies that unmatched agents become less desirable over time, and suggests that their decision rules should change over time. Second, we use a discrete rather than a continuum model for the population. The discreteness causes variance which induces localized imbalances in the two sides of the market. One of the main technical challenges we face is to bound these imbalances. In addition, we present the results of simulations on moderate-sized problems for both the discrete and continu
rate research
Read More
We initiate the study of an interesting aspect of sponsored search advertising, namely the consequences of broad match-a feature where an ad of an advertiser can be mapped to a broader range of relevant queries, and not necessarily to the particular keyword(s) that ad is associated with. Starting with a very natural setting for strategies available to the advertisers, and via a careful look through the algorithmic lens, we first propose solution concepts for the game originating from the strategic behavior of advertisers as they try to optimize their budget allocation across various keywords. Next, we consider two broad match scenarios based on factors such as information asymmetry between advertisers and the auctioneer, and the extent of auctioneers control on the budget splitting. In the first scenario, the advertisers have the full information about broad match and relevant parameters, and can reapportion their own budgets to utilize the extra information; in particular, the auctioneer has no direct control over budget splitting. We show that, the same broad match may lead to different equilibria, one leading to a revenue improvement, whereas another to a revenue loss. This leaves the auctioneer in a dilemma - whether to broad-match or not. This motivates us to consider another broad match scenario, where the advertisers have information only about the current scenario, and the allocation of the budgets unspent in the current scenario is in the control of the auctioneer. We observe that the auctioneer can always improve his revenue by judiciously using broad match. Thus, information seems to be a double-edged sword for the auctioneer.
Constructive election control considers the problem of an adversary who seeks to sway the outcome of an electoral process in order to ensure that their favored candidate wins. We consider the computational problem of constructive election control via issue selection. In this problem, a party decides which political issues to focus on to ensure victory for the favored candidate. We also consider a variation in which the goal is to maximize the number of voters supporting the favored candidate. We present strong negative results, showing, for example, that the latter problem is inapproximable for any constant factor. On the positive side, we show that when issues are binary, the problem becomes tractable in several cases, and admits a 2-approximation in the two-candidate case. Finally, we develop integer programming and heuristic methods for these problems.
Accurate pedestrian classification and localization have received considerable attention due to their wide applications such as security monitoring, autonomous driving, etc. Although pedestrian detectors have made great progress in recent years, the fixed Intersection over Union (IoU) based assignment-regression manner still limits their performance. Two main factors are responsible for this: 1) the IoU threshold faces a dilemma that a lower one will result in more false positives, while a higher one will filter out the matched positives; 2) the IoU-based GT-Proposal assignment suffers from the inconsistent supervision problem that spatially adjacent proposals with similar features are assigned to different ground-truth boxes, which means some very similar proposals may be forced to regress towards different targets, and thus confuses the bounding-box regression when predicting the location results. In this paper, we first put forward the question that textbf{Regression Direction} would affect the performance for pedestrian detection. Consequently, we address the weakness of IoU by introducing one geometric sensitive search algorithm as a new assignment and regression metric. Different from the previous IoU-based textbf{one-to-one} assignment manner of one proposal to one ground-truth box, the proposed method attempts to seek a reasonable matching between the sets of proposals and ground-truth boxes. Specifically, we boost the MR-FPPI under R$_{75}$ by 8.8% on Citypersons dataset. Furthermore, by incorporating this method as a metric into the state-of-the-art pedestrian detectors, we show a consistent improvement.
Given a set of agents with approval preferences over each other, we study the task of finding $k$ matchings fairly representing everyones preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of all possible matchings and agents preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmen) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting. Assuming that approvals are symmetric, we show that proportional approval voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and its sequential variant (seq-PAV), which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our positive computational results extend to other types of compactly representable elections with an exponential candidate space.
We consider a ubiquitous scenario in the Internet economy when individual decision-makers (henceforth, agents) both produce and consume information as they make strategic choices in an uncertain environment. This creates a three-way tradeoff between exploration (trying out insufficiently explored alternatives to help others in the future), exploitation (making optimal decisions given the information discovered by other agents), and incentives of the agents (who are myopically interested in exploitation, while preferring the others to explore). We posit a principal who controls the flow of information from agents that came before, and strives to coordinate the agents towards a socially optimal balance between exploration and exploitation, not using any monetary transfers. The goal is to design a recommendation policy for the principal which respects agents incentives and minimizes a suitable notion of regret. We extend prior work in this direction to allow the agents to interact with one another in a shared environment: at each time step, multiple agents arrive to play a Bayesian game, receive recommendations, choose their actions, receive their payoffs, and then leave the game forever. The agents now face two sources of uncertainty: the actions of the other agents and the parameters of the uncertain game environment. Our main contribution is to show that the principal can achieve constant regret when the utilities are deterministic (where the constant depends on the prior distribution, but not on the time horizon), and logarithmic regret when the utilities are stochastic. As a key technical tool, we introduce the concept of explorable actions, the actions which some incentive-compatible policy can recommend with non-zero probability. We show how the principal can identify (and explore) all explorable actions, and use the revealed information to perform optimally.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
