Página 1 dos resultados de 23 itens digitais encontrados em 0.010 segundos

## Seleção de fornecedores de serviço de transporte utilizando leilão combinatório de compras: adaptação e aplicação do algoritmo Iterative Deepening Search A* (IDA*).; Supplier selection of transportation services using reverse combinatorial auction: adaptation and aplication of Iterative Deepening Search A* (IDA*).

Higuita Salazar, Catalina
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Relevância na Pesquisa
66.37%

Ribeiro, Guida Maria Pereira
Fonte: Instituto Politécnico de Lisboa Publicador: Instituto Politécnico de Lisboa
Relevância na Pesquisa
35.8%

## An Options-Based Solution to the Sequential Auction Problem

Juda, Adam I.; Parkes, David C.
Tipo: Artigo de Revista Científica
EN_US
Relevância na Pesquisa
35.92%
The sequential auction problem is commonplace in open, electronic marketplaces such as eBay. This is the problem where a buyer has no dominant strategy in bidding across multiple auctions when the buyer would have a simple, truth-revealing strategy if there was but a single auction event. Our model allows for multiple, distinct goods and market dynamics with buyers and sellers that arrive over time. Sellers each bring a single unit of a good to the market while buyers can have values on bundles of goods. We model each individual auction as a second-price (Vickrey) auction and propose an options-based, proxied solution to provide price and winner-determination coordination across auctions. While still allowing for temporally uncoordinated market participation, this options-based approach solves the sequential auction problem and provides truthful bidding as a weakly dominant strategy for buyers. An empirical study suggests that this coordination can enable a significant efficiency and revenue improvement over the current eBay market design, and highlights the effect on performance of complex buyer valuations (buyers with substitutes and complements valuations) and varying the market liquidity.; Engineering and Applied Sciences

## Cryptographic Combinatorial Clock-Proxy Auctions

Parkes, David C.; Rabin, Michael O.; Thorpe, Christopher Andrew
Fonte: Springer Verlag Publicador: Springer Verlag
Tipo: Monograph or Book
EN_US
Relevância na Pesquisa
36.1%
We present a cryptographic protocol for conducting efficient, provably correct and secrecy-preserving combinatorial clock-proxy auctions. The "clock phase" functions as a trusted auction despite price discovery: bidders submit encrypted bids, and prove for themselves that they meet activity rules, and can compute total demand and thus verify price increases without revealing any information about individual demands. In the sealed-bid "proxy phase", all bids are revealed the auctioneer via time-lapse cryptography and a branch-and-bound algorithm is used to solve the winner-determination problem. Homomorphic encryption is used to prove the correctness of the solution, and establishes the correctness of the solution to any interested party. Still an NP-hard optimization problem, the use of homomorphic encryption imposes additional computational time on winner-determination that is linear in the size of the branch-and-bound search tree, and thus roughly linear in the original (search-based) computational time. The result is a solution that avoids, in the usual case, the exponential complexity of previous cryptographically-secure combinatorial auctions.; Engineering and Applied Sciences

## On Expressing Value Externalities in Position Auctions

Constantin, Florin; Rao, Malvika; Huang, Chien-Chung; Parkes, David C.
Fonte: American Association for Artificial Intelligence Publicador: American Association for Artificial Intelligence
Tipo: Monograph or Book
EN_US
Relevância na Pesquisa
35.8%
We introduce a bidding language for expressing negative value externalities in position auctions for online advertising. The unit-bidder constraints (UBC) language allows a bidder to condition a bid on its allocated slot and on the slots allocated to other bidders. We introduce a natural extension of the Generalized Second Price (GSP) auction, the expressive GSP (eGSP) auction, that induces truthful revelation of constraints for a rich subclass of unit-bidder types,namely downward-monotonic UBC. We establish the existence of envy-free Nash equilibrium in eGSP under a further restriction to a subclass of exclusion constraints, for which the standard GSP has no pure strategy Nash equilibrium. The equilibrium results are obtained by reduction to equilibrium analysis for reserve price GSP (Even-Dar et al. 2008). In considering the winner determination problem, which is NPhard, we bound the approximation ratio for social welfare in eGSP and provide parameterized complexity results.; Engineering and Applied Sciences

## Estratégias de participação em leilões combinatoriais aplicadas em um problema de transporte de derivados de petróleo

Vieira, Kely Plucinski
POR
Relevância na Pesquisa
25.92%
Recent researches have shown that approaches based on multi-agent systems (MAS) and market mechanisms like auctions are efficient on the resolution of planning problems in supply chains. This work uses the combinatorial auction-based MAS paradigm and participation strategies in auctions for solving the problem of transporting oil derivatives of PETROBRAS - Petroleo Brasileiro S/A, called Simplified Problem of Transporting Oil Derivatives (SPTOD), which is characterized as a planning problem in supply chains. In combinatorial auctions, the winner determination is a NP-Complete problem without approximation algorithms, whose computational cost increases with the number of bids received by the auctioneer. In this context, this work aims at enlarging the scope of application of combinatorial-auction mechanisms in planning problems by using a heuristic strategy for participation in auctions, besides serving as a support tool for decision-making process by specialists of industrial oil. The results were drawn from several scenarios where the MAS was used with the proposed strategy (global evaluation of needs) and with other strategies for comparison (general – all possible auctions – and greedy – only one auction). The results show that the use of the proposed strategy reduces the processing time when compared to the general strategy and that the quality of the solution is preserved in comparison with the general and greedy strategies. Other contributions of this work are the development of a MAS to realize the planning of transporting oil derivatives between producing and consuming basis having as negotiation model the combinatorial auction-based mechanism and a proposition of a decentralized model where several combinatorial auctions can be run simultaneously.; Pesquisas recentes mostram que abordagens baseadas em sistemas multiagentes (SMA) e mecanismos de mercado como leilões são eficazes para encontrar soluções factíveis para problemas de planejamento em cadeias de suprimento. Esta dissertação aborda a utilização do paradigma de SMA baseado em Leilões Combinatoriais e o uso de estratégias de participação em leilões na resolução do problema de transporte de derivados de petróleo em uma rede multimodal da PETROBRAS – Petróleo Brasileiro S/A...

## Testing BOI and BOB algorithms for solving the Winner Determination

Sáez, Yago; Mochón, Asunción; Gómez-Barroso, J.L.; Isasi, Pedro
Tipo: info:eu-repo/semantics/conferenceObject; info:eu-repo/semantics/bookPart Formato: application/pdf
Relevância na Pesquisa
86.31%
Combinatorial auctions are a promising auction format for allocating radio spectrum, as well as other goods. An important handicap of combinatorial auctions is determining the winner bids among many options, that is, solving the winner determination problem (WDP). This paper tackles this computational problem using two approaches in a combinatorial first-price sealed bid auction. The first one, is an A* based on items (BOI). The second one, is an A* based on bids (BOB). These two techniques are tested in several scenarios for allocating radio spectrum licenses. The results obtained reveal that the search algorithm A* with the BOB formulation outperforms the other and always finds the optimal solution very quickly.; Eighth International Conference on Hybrid Intelligent Systems, 2008. HIS '08. Barcelona, 10-12 September 2008

## Payment Rules through Discriminant-Based Classifiers

Dütting, Paul; Fischer, Felix; Jirapinyo, Pichayut; Lai, John Kwang; Lubin, Benjamin; Parkes, David C.
Fonte: ACM Press Publicador: ACM Press
Tipo: Conference Paper
EN_US
Relevância na Pesquisa
25.8%
In mechanism design it is typical to impose incentive compatibility and then derive an optimal mechanism subject to this constraint. By replacing the incentive compatibility requirement with the goal of minimizing expected ex post regret, we are able to adapt statistical machine learning techniques to the design of payment rules. This computational approach to mechanism design is applicable to domains with multi-dimensional types and situations where computational efficiency is a concern. Specifically, given an outcome rule and access to a type distribution, we train a support vector machine with a special discriminant function structure such that it implicitly establishes a payment rule with desirable incentive properties. We discuss applications to a multi-minded combinatorial auction with a greedy winner-determination algorithm and to an assignment problem with egalitarian outcome rule. Experimental results demonstrate both that the construction produces payment rules with low ex post regret, and that penalizing classification errors is effective in preventing failures of ex post individual rationality.; Engineering and Applied Sciences

Rao, Malvika
Fonte: Harvard University Publicador: Harvard University
Tipo: Thesis or Dissertation; text Formato: application/pdf
EN
Relevância na Pesquisa
25.9%
The design of incentives becomes challenging when faced with externalities. In this thesis I resolve this difficulty in two settings: position auctions and software economies. The first part of the thesis studies value externalities in position auctions. I develop a constraint-based model that allows an advertiser to submit, along with its bid, additional constraints to state how its value for clicks depends on the positions of the other ads with which it is allocated. I establish complexity results for winner determination and prove the existence of Nash and envy-free equilibria under certain conditions. A significant contribution of this thesis is that it proposes a foundation for software economies. I first study a setting in the private software economy consisting of a single task, a worker, and a manager. This is a combination of a repeated principal-agent problem and a prediction problem. I characterize a scoring system that elicits truthful information, leading to accurate predictions from both agents and best effort from the worker. In the public software economy, I consider the problem of how to incentivize deep fixes to bugs from both computational as well as theoretical perspectives. In the computational work, I introduce a dynamic model of the software ecosystem and propose subsumption mechanisms as a solution. Next...

## On the Computation of Fully Proportional Representation

Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.04%
We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.

## Complexity of Judgment Aggregation

Endriss, Ulle; Grandi, Umberto; Porello, Daniele
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
35.9%
We analyse the computational complexity of three problems in judgment aggregation: (1) computing a collective judgment from a profile of individual judgments (the winner determination problem); (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the strategic manipulation problem); and (3) deciding whether a given judgment aggregation scenario is guaranteed to result in a logically consistent outcome, independently from what the judgments supplied by the individuals are (the problem of the safety of the agenda). We provide results both for specific aggregation procedures (the quota rules, the premise-based procedure, and a distance-based procedure) and for classes of aggregation procedures characterised in terms of fundamental axioms.

## Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control

Erdelyi, Gabor; Nowak, Markus; Rothe, Joerg
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
25.95%
We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [Electoral Studies, 25(2):287-305, 2006], and here adjusted so as to coerce admissibility of the votes (rather than excluding inadmissible votes a priori), with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding/deleting/partitioning either candidates or voters. SP-AV combines the voters' preference rankings with their approvals of candidates, where in elections with at least two candidates the voters' approval strategies are adjusted--if needed--to approve of their most-preferred candidate and to disapprove of their least-preferred candidate. This rule coerces admissibility of the votes even in the presence of control actions, and hybridizes, in effect, approval with pluralitiy voting. We prove that this system is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, SP-AV has more resistances to control than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting...

## Payment Rules through Discriminant-Based Classifiers

Duetting, Paul; Fischer, Felix; Jirapinyo, Pitchayut; Lai, John K.; Lubin, Benjamin; Parkes, David C.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
25.8%
In mechanism design it is typical to impose incentive compatibility and then derive an optimal mechanism subject to this constraint. By replacing the incentive compatibility requirement with the goal of minimizing expected ex post regret, we are able to adapt statistical machine learning techniques to the design of payment rules. This computational approach to mechanism design is applicable to domains with multi-dimensional types and situations where computational efficiency is a concern. Specifically, given an outcome rule and access to a type distribution, we train a support vector machine with a special discriminant function structure such that it implicitly establishes a payment rule with desirable incentive properties. We discuss applications to a multi-minded combinatorial auction with a greedy winner-determination algorithm and to an assignment problem with egalitarian outcome rule. Experimental results demonstrate both that the construction produces payment rules with low ex post regret, and that penalizing classification errors is effective in preventing failures of ex post individual rationality.

## Virtualization of 5G Cellular Networks as a Hierarchical Combinatorial Auction

Zhu, Kun; Hossain, Ekram
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
25.8%
Virtualization has been seen as one of the main evolution trends in the forthcoming fifth generation (5G) cellular networks which enables the decoupling of infrastructure from the services it provides. In this case, the roles of infrastructure providers (InPs) and mobile virtual network operators (MVNOs) can be logically separated and the resources (e.g., subchannels, power, and antennas) of a base station owned by an InP can be transparently shared by multiple MVNOs, while each MVNO virtually owns the entire BS. Naturally, the issue of resource allocation arises. In particular, the InP is required to abstract the physical resources into isolated slices for each MVNO who then allocates the resources within the slice to its subscribed users. In this paper, we aim to address this two-level hierarchical resource allocation problem while satisfying the requirements of efficient resource allocation, strict inter-slice isolation, and the ability of intra-slice customization. To this end, we design a hierarchical combinatorial auction mechanism, based on which a truthful and sub-efficient resource allocation framework is provided. Specifically, winner determination problems (WDPs) are formulated for the InP and MVNOs, and computationally tractable algorithms are proposed to solve these WDPs. Also...

## Fishing out Winners from Vote Streams

Bhattacharyya, Arnab; Dey, Palash
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.26%
We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined by popular voting rules. As we show, finding the exact winner requires storing essentially all the votes. So, we focus on the problem of finding an {\em $\eps$-winner}, a candidate who could win by a change of at most $\eps$ fraction of the votes. We show non-trivial upper and lower bounds on the space complexity of $\eps$-winner determination for several voting rules, including $k$-approval, $k$-veto, scoring rules, approval, maximin, Bucklin, Copeland, and plurality with run off.; Comment: Adding Acknowledgement

## Rationalizations of Condorcet-Consistent Rules via Distances of Hamming Type

Tipo: Artigo de Revista Científica
Relevância na Pesquisa
35.95%
The main idea of the {\em distance rationalizability} approach to view the voters' preferences as an imperfect approximation to some kind of consensus is deeply rooted in social choice literature. It allows one to define ("rationalize") voting rules via a consensus class of elections and a distance: a candidate is said to be an election winner if she is ranked first in one of the nearest (with respect to the given distance) consensus elections. It is known that many classic voting rules can be distance rationalized. In this paper, we provide new results on distance rationalizability of several Condorcet-consistent voting rules. In particular, we distance rationalize Young's rule and Maximin rule using distances similar to the Hamming distance. We show that the claim that Young's rule can be rationalized by the Condorcet consensus class and the Hamming distance is incorrect; in fact, these consensus class and distance yield a new rule which has not been studied before. We prove that, similarly to Young's rule, this new rule has a computationally hard winner determination problem.

## A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction

Buer, Tobias; Kopfer, Herbert
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
66.1%
The bi-objective winner determination problem (2WDP-SC) of a combinatorial procurement auction for transport contracts is characterized by a set B of bundle bids, with each bundle bid b in B consisting of a bidding carrier c_b, a bid price p_b, and a set tau_b transport contracts which is a subset of the set T of tendered transport contracts. Additionally, the transport quality q_{t,c_b} is given which is expected to be realized when a transport contract t is executed by a carrier c_b. The task of the auctioneer is to find a set X of winning bids (X subset B), such that each transport contract is part of at least one winning bid, the total procurement costs are minimized, and the total transport quality is maximized. This article presents a metaheuristic approach for the 2WDP-SC which integrates the greedy randomized adaptive search procedure with a two-stage candidate component selection procedure, large neighborhood search, and self-adaptive parameter setting in order to find a competitive set of non-dominated solutions. The heuristic outperforms all existing approaches. For seven small benchmark instances, the heuristic is the sole approach that finds all Pareto-optimal solutions. For 28 out of 30 large instances, none of the existing approaches is able to compute a solution that dominates a solution found by the proposed heuristic.; Comment: Accepted for publication in Computers & Operations Research...

## The Complexity of Fully Proportional Representation for Single-Crossing Electorates

Skowron, Piotr; Yu, Lan; Faliszewski, Piotr; Elkind, Edith
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.04%
We study the complexity of winner determination in single-crossing elections under two classic fully proportional representation rules---Chamberlin--Courant's rule and Monroe's rule. Winner determination for these rules is known to be NP-hard for unrestricted preferences. We show that for single-crossing preferences this problem admits a polynomial-time algorithm for Chamberlin--Courant's rule, but remains NP-hard for Monroe's rule. Our algorithm for Chamberlin--Courant's rule can be modified to work for elections with bounded single-crossing width. To circumvent the hardness result for Monroe's rule, we consider single-crossing elections that satisfy an additional constraint, namely, ones where each candidate is ranked first by at least one voter (such elections are called narcissistic). For single-crossing narcissistic elections, we provide an efficient algorithm for the egalitarian version of Monroe's rule.; Comment: 23 pages

## Sample Complexity for Winner Prediction in Elections

Bhattacharyya, Arnab; Dey, Palash
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.35%
Predicting the winner of an election is a favorite problem both for news media pundits and computational social choice theorists. Since it is often infeasible to elicit the preferences of all the voters in a typical prediction scenario, a common algorithm used for winner prediction is to run the election on a small sample of randomly chosen votes and output the winner as the prediction. We analyze the performance of this algorithm for many common voting rules. More formally, we introduce the $(\epsilon, \delta)$-winner determination problem, where given an election on $n$ voters and $m$ candidates in which the margin of victory is at least $\epsilon n$ votes, the goal is to determine the winner with probability at least $1-\delta$. The margin of victory of an election is the smallest number of votes that need to be modified in order to change the election winner. We show interesting lower and upper bounds on the number of samples needed to solve the $(\epsilon, \delta)$-winner determination problem for many common voting rules, including scoring rules, approval, maximin, Copeland, Bucklin, plurality with runoff, and single transferable vote. Moreover, the lower and upper bounds match for many common voting rules in a wide range of practically appealing scenarios.; Comment: Accepted in AAMAS 2015

## Toward Expressive and Scalable Sponsored Search Auctions

Martin, David J.; Gehrke, Johannes; Halpern, Joseph Y.