[pt] Este trabalho se concentra no desenvolvimento de mecanismos de leilões reveladores aleatorizados que buscam maximizar simultaneamente a receita e a eficiência econômica, ou função social, de leilões de demanda unitária. Em um leilão de demanda unitária, um conjunto de k bens é leiloado para um conjunto de n consumidores, com a restrição de que nenhum consumidor pode comprar mais de um bem. É apresentado um arcabouço para o desenvolvimento de mecanismos reveladores aleatorizados de complexidade polinomial derivados do mecanismo de Vickrey-Clarke- Groves, ou VCG. Ao invés de utilizar preços de reserva, estas variantes do VCG utilizam como parâmetro o número de bens que devem ser efetivamente vendidos. Os mecanismos se diferenciam entre si pela maneira como é feito o cálculo do número de bens que devem ser vendidos e permitem um balanço interessante entre receita e eficiência econômica, ao mesmo tempo que melhoram os resultados teóricos alcançados para o problema de Leilões de Demanda Unitária. / [en] This work focuses on the development of randomized truthful mechanisms that seek to maximize both the revenue and the economic efficiency, or social welfare, of unit-demand auctions. In a unit-demand auction a set of k items is auctioned to a set of n consumers and no consumer can purchase more than one item. A framework is presented for devising polynomial-time randomized truthful mechanisms that are based on a new variant of the Vickrey-Clarke-Groves (VCG) mechanism. Instead of using reserve prices, this variant of VCG uses the number of objects that we wish to sell as a parameter. The mechanisms obtained differ er from each other in the way they select the number of items to be sold and allow an interesting trade-off between revenue and economic effciency, while improving upon the stateof- the-art results for the Unit-Demand Auction problem (09).

[pt] Consideramos, nesta dissertação, a questão de determinar se um grafo tem uma propriedade P, tal como G é livre de triângulos ou G é 4- colorível. Em particular, consideramos para quais propriedades P existe um algoritmo aleatório com probabilidades de erro constantes que aceita grafos que satisfazem P e rejeita grafos que são epsilon-longe de qualquer grafo que o satisfaça. Se, além disso, o algoritmo tiver complexidade independente do tamanho do grafo, a propriedade é dita testável. Discutiremos os resultados de Alon, Fischer, Newman e Shapira que obtiveram uma caracterização combinatória de propriedades testáveis de grafos, resolvendo um problema em aberto levantado em 1996. Essa caracterização diz informalmente que uma propriedade P de um grafo é testável se e somente se testar P pode ser reduzido a testar a propriedade de satisfazer uma das finitas partições Szemerédi. / [en] We consider, in this thesis, the question of determining if a graph has a property P such as G is triangle-free or G is 4-colorable. In particular, we consider for which properties P there exists a random algorithm with constant error probabilities that accept graphs that satisfy P and reject graphs that are epsilon-far from any graph that satisfies it. If, in addition, the algorithm has complexity independent of the size of the graph, the property is called testable. We will discuss the results of Alon, Fischer, Newman, and Shapira that obtained a combinatorial characterization of testable graph properties, solving an open problem raised in 1996. This characterization informally says that a graph property P is testable if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions.